Efficient symbolic analysis of programs


Journal Article

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.

Full Text

Duke Authors

Cited Authors

  • Reif, JH; Lewis, HR

Published Date

  • January 1, 1986

Published In

Volume / Issue

  • 32 / 3

Start / End Page

  • 280 - 314

Electronic International Standard Serial Number (EISSN)

  • 1090-2724

International Standard Serial Number (ISSN)

  • 0022-0000

Digital Object Identifier (DOI)

  • 10.1016/0022-0000(86)90031-0

Citation Source

  • Scopus