Publications [#237104] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH; Lewis, HR, Efficient symbolic analysis of programs, Journal of Computer and System Sciences, vol. 32 no. 3 (January, 1986), pp. 280-314, Elsevier BV, ISSN 0022-0000 [doi]
   (last updated on 2026/01/14)

   Abstract:
   This paper is concerned with constructing, for each expression in a given program text, a symbolic expression whose value is equal to the value of the text expression for all executions of the program. A cover is a mapping from text expressions to such symbolic expressions. Covers can be used for constant propagation, code motion, and a variety of other program optimizations. Covers can also be used as an aid in symbolic program execution and for finding loop invariants for program verification. We describe a direct (non-iterative) algorithm for computing a cover. The cover computed by our algorithm is characterized as a minimum of a certain fixed point equation, and is in general a better cover than might be computed by iteration methods (which can compute fixed point covers which are not minimal). Our algorithm is efficient and applicable to all flow graphs. A variant of our algorithm is implemented by Kalman and Kortesoja (IEEE Trans. Software Eng. SE-6 (1980), 512-519) in an optimizing compiler. © 1986.