Demand-Driven Interprocedural Constant Propagation: Implementation and Evaluation

We have developed a hybrid algorithm for interprocedural constant propagation combining the Wegman-Zadeck, Burke and Cytron, and demand-driven approaches. We use a modified Wegman-Zadeck algorithm as the incremental intraprocedural constant propagator in the demand-driven interprocedural framework. Wegman and Zadeck solve the interprocedural constant propagation problem by linking the SSA graphs of a set of procedures into a single large SSA graph and then use their Sparse Conditional Constant (SCC) algorithm on the constructed graph [WZ91]. SCC is an optimistic (assumes values are constant until proven otherwise) worklist algorithm. Burke and Cytron solve the interprocedural constant propagation problem with an algorithm that uses a pessimistic (assumes values are non-constants until proven otherwise) incremental intraprocedural constant propagator and iterates forward and backward over the call graph until no new information is discovered [BC86]. We will show that our hybrid algorith..