Ensuring Automated Update of Analysis Results Across Program Transformations During Compilation

What is it about?

Mainstream compilers perform a multitude of analyses and optimizations on the given input program. Each analysis (such as points-to analysis) may generate a program-abstraction (such as points-to graph). Each optimization is typically composed of multiple alternating phases of inspection of such program-abstractions and transformations of the program. Upon transformation of a program, the program-abstractions generated by various analyses may become inconsistent with the modified program. Consequently, the correctness of the downstream inspection (and consequent transformation) phases cannot be ensured until the relevant program- abstractions are stabilized; that is, the program-abstractions are either invalidated or made consistent with the modified program. In general, the existing compiler frameworks do not perform automated stabilization of the program-abstractions and instead leave it to the compiler pass writers to deal with the complex task of identifying the relevant program-abstractions to be stabilized, the points where the stabilization is to be performed, and the exact procedure of stabilization. In this paper, we address these challenges by providing the design and implementation of a novel compiler-design framework called "Homeostasis". Homeostasis automatically captures all the program changes performed by each transformation phase, and later, triggers the required stabilization using the captured information, if needed. We also provide a formal description of Homeostasis and a correctness proof thereof. To assess the feasibility of using Homeostasis in compilers of parallel programs, we have implemented our proposed idea in IMOP, a compiler framework for OpenMP C programs. Further, to illustrate the benefits of using Homeostasis, we have implemented a set of standard data-flow passes, and a set of involved optimizations that are used to remove redundant barriers in OpenMP C programs. Implementations of none of these optimizations in IMOP required any additional lines of code for stabilization of the program-abstractions. We present an evaluation in the context of these optimizations and analyses, which demonstrates that Homeostasis is efficient and easy to use.

Featured Image

Photo by David Clode on Unsplash

Photo by David Clode on Unsplash

Why is it important?

We observe that to avoid the generation of sub-optimal and/or incorrect programs upon compilation, three key stabilization-related questions need to be addressed while adding/modifying an optimization pass, in order to ensure that the existing analysis results remain consistent with the modified program: 1. Which analysis results need to be stabilized when adding the optimization? 2. Where should an analysis result be stabilized during the optimization? 3. How should the analysis result be stabilized, in the context of the optimization? Similar set of three questions need to be addressed when adding a new analysis pass. In conventional compilers, such as LLVM, GCC, Soot, Rose, JIT compilers (OpenJ9, HotSpot, V8), and so on, the onus of addressing these key questions lies mostly on the compiler pass writers. Some such instances are shown in the paper (see Fig. 3). This manual process often leads to complex and error-prone codes. Further, as the number and complexity of compiler passes increase (for example, LLVM has more than 347 passes), addressing these questions precisely and efficiently becomes progressively more difficult. This may lead to correctness/efficiency bugs (see the paper for citations of 14 bug-fixing commits from the LLVM's GitHub repo). With the compiler development effort spanning multiple decades involving (sometimes) hundreds of developers, it becomes extremely challenging to manually solve these problems, as no developer of a compiler pass might possess a clear understanding of the semantics of all the hundreds of other passes already present in the compiler. To mitigate these issues, the focus of this paper is to perform automatic stabilization of all the relevant program-abstractions, when needed, in response to any program modification. We term a compiler that provides this guarantee as a "self-stabilizing" compiler.

Perspectives