From Machine Scheduling to VLIW Instruction Scheduling

This report discusses the similarities and the differencesbetween machine scheduling prob- lems, and instruction scheduling problems on modern VLIW processors such as the STMi- croelectronics ST200. Our motivations are to apply the machine scheduling techniques that are relevant to instruction scheduling in VLIW compilers, and to understand how processor micro-architecture features impact advanced instruction scheduling techniques. Based on this discussion, we present our theoretical contributions to the field of instruction scheduling that are applied in the STMicroelectronics ST200 production compiler, and we introduce a new time-indexed formulation for the register constrained instruction scheduling problems.