Constant propagation with conditional branches
Mark N. Wegman, Frank Kenneth Zadeck · ACM Transactions on Programming Languages and Systems · 1991
Constant propagation is a well-known global flow analysis problem. The goal of constant propagation is to discover values that are constant on all possible executions of a program and to propagate these constant values as far foward through the program as possible. Expressions whose operands are all constants can be evaluated at compile time and the results propagated further. Using the algorithms presented in this paper can produce smaller and faster compiled programs. The same algorithms can be used for other kinds of analyses (e.g., type of determination). We present four algorithms in this paper, all conservitive in the sense that all constants may not be found, but each constant found is constant over all possible executions of the program. These algorithms are among the simplest, fastest, and most powerful global constant propagation algorithms known. We also present a new algorithm that performs a form of interprocedural data flow analysis in which aliasing information is gathered in conjunction with constant progagation. Several variants of this algorithm are considered.
Cited by 606 works. doi:10.1145/103135.103136 Open-access PDF
Authors
References
- Compilers: Principles, Techniques, and Tools
- Principles of Compiler Design
- A unified approach to global program optimization
- Control flow analysis
- Efficiently computing static single assignment form and the control dependence graph
- Programming languages and their compilers: Preliminary notes
- A Fast and Usually Linear Algorithm for Global Flow Analysis
- Bulldog: A Compiler for VLIW Architectures
- Global Data Flow Analysis and Iterative Algorithms
- Property extraction in well-founded property sets