INTERPROCEDURAL CONDITIONAL BRANCH ELIMINATION

The existence of statically detectable correlation among conditional b ranches enables their elimination, an optimization that has a number o f benefits. This paper presents techniques to determine whether an int erprocedural execution path leading to a conditional branch exists alo ng which the branch outcome is known at compile time, and then to elim inate the branch along this path through code restructuring. The techn ique consists of a demand driven interprocedural analysis that determi nes whether a specific branch outcome is correlated with prior stateme nts or branch outcomes. The optimization is performed using a code res tructuring algorithm that replicates code to separate out the paths wi th correlation. When the correlated path is affected by a procedure ca ll, the restructuring is based on procedure entry splitting and exit s plitting The entry splitting transformation creates multiple entries t o a procedure, and the exit splitting transformation allows a procedur e to return control to one of several return points in the caller. Our technique is efficient in that the correlation detection is demand dr iven, thus avoiding exhaustive analysis of the entire program, and the restructuring never increases the number of operations along a path t hrough an interprocedural control flow graph. We describe the benefits of our interprocedural branch elimination optimization (ICBE). Our ex perimental results show that, for the same amount of code growth, the estimated reduction in executed conditional branches is about 2.5 time s higher with the ICBE optimization than when only intraprocedural con ditional branch elimination is applied.