Advanced Backend Optimization

4

Instruction Scheduling Before Register Allocation

Since controlling the register pressure during instruction scheduling is a difficult problem, lifetime-sensitive modulo schedulers have been proposed [HUF 93a], which aim at minimizing the cumulative register lifetimes. In this chapter, we show that in the case of resource-free modulo scheduling problems, the modulo schedule that minimizes the cumulative register lifetimes is easily computed by solving a network flow problem on the dependence graph suitably augmented with nodes and arcs.

4.1. Instruction scheduling for an ILP processor: case of a VLIW architecture

As a case of interest, this section presents instruction scheduling for the ST200 architecture.

4.1.1. Minimum cumulative register lifetime modulo scheduling

The minimization of the cumulative register lifetimes on the sample dependence graph is illustrated in Figure 4.1. This dependence graph has been simplified by removing the memory access operations after converting the uniform dependences into register transfers [CAL 90]. We assume that the target architecture is such that the lifetime of a register starts at the time when the operation that produces it is issued. When this is not the case, the only difference is a constant contribution to the cumulative register lifetimes that does not impact the minimization.

Figure 4.1. Original dependence graph

Taking the dependence ...