[Back]

J. Knoop:
"Constant Propagation w/ SSA- and Predicated SSA Form";
Talk: Static Single-Assignment Form Seminar, Autrans, Frankreich (invited); 2009-04-26 - 2009-04-30.

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.

(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.)