Constant Propagation: A Fresh Demand-Driven Look

Constant propagation is a well-known static compiler technique in which values of variables which are determined to be integral constants can be passed to expressions which use these constants. Code reduction (preventing unnecessary compilation), bounds propagation, and dead-code elimination are some of the optimizations which can benefit from this analysis. In this paper, we present a new method for detecting constants, based upon an optimistic demand-driven recursive solver, as opposed to more traditional iterative solvers. The problem with iterative solvers is that they may require expression evaluation many times, while we only classify each node after all the definitions which reach the expressions within that node are classified. To consider conditional code, we augment the standard Static Single Assignment (SSA) form with merge operators called fl-functions, adapted from the interpretable Gated Single Assignment (GSA) model [16]. We show that our approach is fast and finds the ..