Constant Propagation on the Value Graph: Simple Constants and Beyond Jens Knoop Vienna University of Technology 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 [19], 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. This is joint work with Oliver Ruething.