Finite Constants: Characterizations of a New Decidable Set of Constants

Bernhard Steffen and Jens Knoop

Abstract: Constant propagation - the replacement of program terms which represent a unique value at run time by their values - is a classical program optimization method. In spite of being treated for years, constant propagation still has been in the unsatisfactory phase of heuristics. We enhance the known constant propagation techniques to obtain an algorithm which is optimal for programs without loops. Fundamental is the introduction of a new decidable set of constants, the finite constants. This set has two different characterizations: a denotational one, which directly specifies our iterative algorithm and an operational one, which delivers the completeness or optimality of this algorithm for programs without loops. The algorithm is implemented in a commercial compiler project.


This report is an extended version of a paper which appeared in MFCS'89, Lecture Notes in Computer Science, Springer-Verlag, 1989.

Previous | Index | Next