Intermediate compiler analysis via reference chaining
Eric Stoltz · 1995
When performing data-flow analysis on a compiler's intermediate form of a program, sparse representations have proven their value by propagating information only to those points that affect or use such information. Static Single Assignment form (where each variable use has exactly one reaching definition) is a translation that linearizes reaching definitions in a sparse manner. This dissertation extends the concept of Static Single Assignment to include information flow other than just reaching definitions, such as reaching uses, upward-exposed references, and definition-to-definition links. Information is coalesced at confluence points via merge operators. The general process of providing pointers (links) between arbitrary pairs of definition and usage sites of a variable is called reference chaining. A general reference chaining algorithm is developed and presented that allows parameters to be set that control the types of information to be propagated throughout the intermediate form. By providing this general algorithm, data-flow information (upward- or downward-exposed uses or definitions) is shown to be readily accessible in a compiler's intermediate representation. Many of the problems solved with reference chains utilize a demand-driven technique, where classification of any node is often dependent upon its data-flow predecessors. Calls are made to classify the predecessors in a recursive manner. The information provided by reference chains has led to the development of efficient intermediate analysis techniques, including demand-driven constant propagation, fast scalar dependence analysis, and live variable analysis, all within a unified sparse representation. Reference chaining has also been extended to parallel constructs, so that many of the same methods used to analyze sequential programs can be adapted to parallel programs. Complete algorithms both of a general nature and specifically tailored to address the applications mentioned above are provided. Experiments have been performed on a wide variety of scientific benchmarks to determine the effectiveness of reference chaining, and comparative results are given where possible. The results of these experiments have shown that the demand-driven approach is both fast and effective, and that reference chaining is generally applicable and useful for many data-flow analysis problems.