Optimal instruction scheduling using integer programming

This paper presents a new approach to focal instruction scheduling based on integer programming that produces optimal instruction schedules in a reaso nable time, even for very large basic blocks. The new approach first uses a set of graph transformations to simplify the data-dependency graph while p reserving the optimality of the final schedule. The simplified graph result s in a simplified integer program which can be solved much faster. A new in teger-programming formulation is then applied to the simplified graph. Vari ous techniques are used to simplify the formulation, resulting in fewer int eger-program variables, fever integer-program constraints and fewer terms i n some of the remaining constraints, thus reducing integer-program solution time. The new formulation also uses certain adaptively added constraints ( cuts) to reduce solution time. The proposed optimal instruction scheduler i s built within the Gnu Compiler Collection (GCC) and is evaluated experimen tally using the SPEC95 floating point benchmarks. Although optimal scheduli ng for the target processor is considered intractable, all of the benchmark s' basic blocks are optimally scheduled, including blocks with up to 1000 i nstructions, while total compile time increases by only 14%.