Modulo Scheduling with Isomorphic Control Transformations

This dissertation addresses the complexities involved with scheduling in the presence of con-ditional branches. This is a particularly important problem for processors that execute multiple operations per cycle and are not fully utilized by local scheduling techniques. Since conditional branches introduce multiple execution paths, it is di cult for a global scheduler to keep track of the various paths and to select the appropriate operations to schedule. A new approach to global instruction scheduling is presented that uses Isomorphic Control Transformations (ICTs). If-conversion is used to convert an acyclic control ow graph into a large basic block orhyper-block. Local scheduling techniques which are well-known and widely supported can then be applied to schedule operations. After scheduling, the control ow graph is regenerated using Reverse If-Conversion. One well-known local scheduling based technique is Modulo Scheduling. Modulo Schedul-ing is a software pipelining technique that e ectively schedules loops for high-performance processors. This dissertation highlights the bene ts of Modulo Scheduling over other software pipelining techniques based on global scheduling. The ICTs are applied to Modulo Scheduling to schedule loops with conditional branches. Experimental results show that this approac