PARALLELIZATION OF CONTROL RECURRENCES FOR ILP PROCESSORS

The performance of applications executing on processors with instructi on level parallelism is often limited by control and data dependences. Performance bottlenecks caused by dependences can frequently be elimi nated through transformations which reduce the height of critical path s through the program. The utility of these techniques can be demonstr ated in an increasingly broad range of important situations. This pape r focuses on the height reduction of control recurrences within loops with data dependent exits. Loops with exits are transformed so as to a lleviate performance bottlenecks resulting from control dependences. A compilation approach to effect these transformations is described. Th e techniques presented in this paper used in combination with prior wo rk 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 tradition ally 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 c ases, height reduction requires redundant computation or may not be fe asible.