[Back]

J. Knoop:
"Constant Propagation on the Value Graph: Simple Constants and Beyond";
Talk: 20th Annual Workshop of the Fachgruppe 2.1.4 "Programmiersprachen und Rechenkonzepte" der Gesellschaft für Informatik, Physikzentrum Bad Honnef, Germany; 2003-05-09.

We present a new algorithm for constant propagation (CP),
which works on the value graph of a program. This algorithm
combines the (1) efficiency of the sparse CP-algorithms of
Reif and Lewis, Ferrante and Ottenstein, and
Wegman and Zadeck with the (2) conceptual simplicity
of their classic conventional counterparts of Kildall,
and Kam and Ullman, while (3) outperforming them in
power. It detects a proper superset of the simple constants
detected by the classical CP-algorithms, while avoiding the
exponential worst-case behaviour of the CP-algorithm for
finite constants of Steffen and Knoop allowing its
optimality for acyclic control flow. The class detected is a
well-balanced compromise between power and performance. In
fact, we show that CP is co-NP-hard for acyclic control flow
making the existence of efficient optimal algorithms for
acyclic control flow most unlikely. Nonetheless, the new
algorithm is open for extensions, e.g. towards conditional
constants in the fashion of Wegman and Zadeck's algorithm
in order to capture to a extent the determinism of
conditional branching.

http://www.informatik.uni-kiel.de/~wg/Honnef2003/Program.html