FI... HEWLETT a: ~ PACKARD Parallelization of Control Recurrences for ILP Processors

control dependences, recurrences, parallelism, control height reduction, back-substitution, blocked back-substitution, software pipeline, loop optimization The performance of applications executing on processors with instruction level parallelism is often limited by control and data dependences. Performance bottlenecks caused by dependences can frequently be eliminated through transformations which reduce the height of critical paths through the program. While height reduction techniques are not always helpful, their utility can be demonstrated in an increasingly broad range of important situations. This report focuses on the height reduction of control recurrences within loops with data dependent exits. Loops with data dependent exits are transformed so as to alleviate performance bottlenecks resulting from control dependences. A compilation approach to effect these transformations is described. The techniques presented in this report used in combination with prior work on reducing the height of data dependences provide a comprehensive approach to accelerating loops with conditional exits. In many cases, loops with conditional exits provide a degree of parallelism traditionally associated with vectorization. Multiple iterations of a loop can be retired in a single cycle on a processor with adequate instruction level parallelism with no cost in code redundancy. In more difficult cases, height reduction requires redundant computation or may not be feasible