Constant Propagation w/SSA- and Predicated SSA Form

                      Jens Knoop
                  TU Vienna, Austria

Constant propagation is concerned with statically detecting
program terms, which evaluate to a unique constant whenever 
they are evaluated at run-time. Constant propagation is known
to be hard. It is undecidable for unrestricted control-flow, and
it is co-NP-complete for acylic programs. In practice thus
algorithms computing so-called simple constants are still 
prevailing, which can efficiently be computed. The challenge 
of constant propagation in fact is to find algorithms which keep 
a fine balance between expressivity and efficiency. 

In this talk we argue that the value graph of Alpern,
Wegman, and Zadeck, and its extension to predicated code
which are derived from the SSA and the Predicated SSA form
of a program, allow for conceptually new constant progagation 
algorithms which are conceptually simple and elegant, 
and simultaneously expressive and efficient. They detect a 
large superset of simple constants, and are a neat example for 
demonstrating the benefits of the SSA form of programs for 
program analysis and optimization.

This is joint work with Oliver Rüthing.


References:
[1] Knoop, J., and O. Rüthing. Constant Propagation on 
    the Value Graph: Simple Constants and Beyond}. In 
    Proc. 9th Int. Conf. on Compiler Construction (CC 2000), 
    LNCS 1781 (2000), 94 - 109.
[2] Knoop, J., and O. Rüthing. Constant Propagation on 
    Predicated Code. J. of Universal Computer Science 9, 8 
    (2003), 829 - 850. (Special issue devoted to SBLP'03).
[3] Knoop, J., and O. Rüthing. Constant Propagation on 
    Predicated Code. In Proc. 7th Brazilian Symp. on 
    Programming Languages (SBLP 2003), 135 - 148.


This work has been partially supported by the research project
"Integrating European Timing Analysis Technology" (ALL-TIMES) under
contract No 215068 funded by the 7th EU R&D Framework Programme.