Control Flow Optimization in Loops using Interval Analysis

We present a novel loop transformation technique, particu-larly well suited for optimizing embedded compilers, where an increase in compilation time is acceptable in exchange for significant performance increase. The transformation tech-nique optimizes loops containing nested conditional blocks. Specifically, the transformation takes advantage of the fact that the Boolean value of the conditional expression, deter-mining the true/false paths, can be statically analyzed using a novel interval analysis technique that can evaluate condi-tional expressions in the general polynomial form. Results from interval analysis combined with loop dependency infor-mation is used to partition the iteration space of the nested loop. In such cases, the loop nest is decomposed such as to eliminate the conditional test, thus substantially reducin