Nordic Journal of Computing Bibliography

John L. Ross and Mooly Sagiv. Building a Bridge between Pointer Aliases and Program Dependences. Nordic Journal of Computing, 5(4):361-386, Winter 1998.

In this paper we present a surprisingly simple reduction of the program dependence problem to the may-alias problem. While both problems are undecidable, providing a reduction between them has great practical importance. Program dependence information is used extensively in compiler optimizations, automatic program parallelizations, code scheduling for super-scale machines, and software engineering tools such as code slicers. When working with languages that support pointers and references, these systems are forced to make very conservative assumptions. This leads to many superfluous program dependences and limits compiler performance and the usability of software engineering tools. Fortunately, there are many algorithms for computing conservative approximations to the may-alias problem. The reduction has the important property of always computing conservative program dependences when used with a conservative may-alias algorithm. We believe that the simplicity of the reduction and the fact that it takes linear time may make it practical for realistic applications.

Categories and Subject Descriptors: D.3.3 [Programming Languages]: Language Constructs and Features; D.3.4 [Programming Languages]: Processors

Additional Key Words and Phrases: alias analysis, dataflow analysis, pointer analysis, program dependences, static analysis

Selected references


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database