Constant propagation, the replacement of program terms that represent a unique constant at runtime by their values, is a classical program optimization method. Constant propagation techniques generally use heuristics to identify as many replaceable terms as possible, since it is generally undecidable whether a term can be replaced by a constant. Such heuristics implicitly define a subset of all replaceable terms, but an equivalent explicit definition of this set (operational or denotational) is often difficult to derive. In contrast, Steffen and Knoop explicitly define a set of finite constants in both an operational and a denotational style. Finite constants generalize the set of constant terms calculated by the algorithm developed by Kam and Ullman in 1977 [1]. This paper proves that the two given characterizations are equivalent and shows that it is decidable if a term is a finite constant. Decidability is proven by using regular expressions to denote sets of paths in the flow graph. Then an enhanced algorithm is given. Moreover, the authors show that the algorithm is complete and optimal for programs without loops.
The paper is well written and organized. It can be read without a specific background. Nevertheless, readers interested in program optimization techniques and dataflow analysis constitute the natural audience.
A weakness of the paper is the lack of any comment on the complexity of the given algorithm. Actually, for programs without loops, I wonder whether some simpler algorithm could be found.