J. Knoop:

"Constant Propagation w/ SSA- and Predicated SSA Form";

Vortrag: Static Single-Assignment Form Seminar, Autrans, Frankreich (eingeladen); 26.04.2009 - 30.04.2009.

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

Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.