Interprocedural conditional branch elimination
- 1 May 1997
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 32 (5), 146-158
- https://doi.org/10.1145/258915.258929
Abstract
The existence of statically detectable correlation among conditional branches enables their elimination, an optimization that has a number of benefits. This paper presents techniques to determine whether an interprocedural execution path leading to a conditional branch exists along which the branch outcome is known at compile time, and then to eliminate the branch along this path through code restructuring. The technique consists of a demand driven interprocedural analysis that determines whether a specific branch outcome is correlated with prior statements or branch outcomes. The optimization is performed using a code restructuring algorithm that replicates code to separate out the paths with correlation. When the correlated path is affected by a procedure call, the restructuring is based on procedure transformation allows a procedure to return control to one of several return points in the caller. Our technique is efficient in that the correlation detection is demand driven, thus avoiding exhaustive analysis of the entire program, and the restructuring never increases the number of operations along a path through an interprocedural control flow graph. We describe the benefits of our interprocedural branch elimination optimization (ICBE). Our experimental results show that, for the same amount of code growth, the estimated reduction in executed conditional branches is about 2.5 times higher with the ICBE optimization than when only intraprocedural conditional branch elimination is applied.Keywords
This publication has 17 references indexed in Scilit:
- Type feedback vs. concrete type inferencePublished by Association for Computing Machinery (ACM) ,1995
- Elimination of redundant array subscript range checksACM SIGPLAN Notices, 1995
- Avoiding conditional branches by code replicationACM SIGPLAN Notices, 1995
- A comparative analysis of schemes for correlated branch predictionPublished by Association for Computing Machinery (ACM) ,1995
- Precise concrete type inference for object-oriented languagesACM SIGPLAN Notices, 1994
- Avoiding unconditional jumps by code replicationACM SIGPLAN Notices, 1992
- Lazy code motionACM SIGPLAN Notices, 1992
- A fresh look at optimizing array bound checkingACM SIGPLAN Notices, 1990
- Interprocedural analysis vs. procedure integrationInformation Processing Letters, 1989
- A study of a C function inlinerSoftware: Practice and Experience, 1988