Grant Wallace
CS597d

Observation 11:
The Partial Reverse If-Conversion Framework for Balancing Control Flow and Predication [1]

Strengths:
1. Removes the need to try to make optimal decisions on hyperblock formation early in the compilation process, which is difficult to do before optimizations have been performed.

2. Allows for aggressive predication (hyperblock formation) early in compilation. This allows optimizations to be performed on larger sections of predicated code.

3. Removes paths from the hyperblock that cause resource over utilization or dependence height mismatch. This is done during the scheduling phase when all optimizations have already been performed.

4. Shows significant performance improvement over traditional hyperblock formation, and more consistent performance improvement as compared to superblock formation.

Weaknesses:
1. Compilation time increased as compared to other hyperblock formation techniques (doing if-conversion during scheduling or using heuristics to form hyperblocks early, before optimizations). This increased time is primarily in comparing the 2p+1 schedules (where p is the number of predicates) available by performing reverse if-conversion.

2. Code size increases as compared to traditional hyperblock formation [2]. But code sizes would probably be quite similar (or even reduced due to optimizations) if compared to traditional hyperblock formation with a more accurate heuristic for basic block inclusion (i.e. a heuristic giving similar performance to reverse if-conversion, assuming such a heuristic is possible).

Further Research:
The reverse if-conversion process used for analysis in this paper starts with traditional hyperblock formation [2] as the input. Since traditional hyperblock formation must balance aggressively predicating and including paths with resource over-utilization and dependence height considerations, it seems this could be a sub-optimal starting point. I would be curious to see a performance analysis where the input hyperblocks are even more aggressively chosen. This would allow for more "global" optimizations. Would the gains in performance out-weigh the greater compile time due to more schedules being considered?

[1] August, Hwu, Mahlke, "The Partial Reverse If-Conversion Framework for Balancing Control Flow and Predication".

[2] Mahlke, Lin, Chen, Hank, Bringmann, "Effective Compiler Support for Predicated Execution Using the Hyperblock".