An approach to incremental compilation of optimized code
Lori Pollock · 1986
Although code optimizations are frequently applied to reduce execution time and space, incremental programming environments are currently designed to support either no optimizations or limit optimizations within the boundary of the smallest recompilation unit. This dissertation studies the problem of incremental compilation of optimized code and presents a technique for incrementally compiling machine independent (local, global, and loop) optimizations in response to program edits. The effects of program modification on optimized code are first analyzed to identify those program changes that affect the validity of each optimization. The set of edits that can destroy conditions for an existing optimization are classified as well as those edits that can create sufficient conditions to permit a new optimization. The interdependencies among optimizations, which cause the rippling of affected optimizations, are detailed in a chart that illustrates the effects of reversing or performing each optimization on other optimizations. A model, MFAD, is developed to represent both the unoptimized and optimized code and maintain a history of existing optimizations. MFAD is a modified flow graph in which each basic block is portrayed as a set of augmented dags. MFAD and data flow are the vehicles for detection of created and destroyed conditions for optimizations. MFAD is also used in the source-to-generated code mapping when the optimized code is actually generated. Algorithms are constructed to incrementally update MFAD, extended data flow information, and the mapping, given the potential effects of different edits. When conditions for an optimization are destroyed, the optimization is reversed in order to maintain functional equivalence between the source and optimized code, and optimizations are performed when conditions permit with the goal of providing highly optimized code. Certain properties of the algorithms including termination, correctness, completeness, efficiency, and the effects of different orders of detection and update are examined. In addition to aiding in the development of an incremental optimizing compiler, these techniques could also be used in the symbolic debugging of optimized code. The rippling of optimizations presents another approach to traditional optimization, and the optimization dependency analysis provides insight into the order of executing traditional optimization passes.