Incremental generation of high-quality target code
Mary P. Bivens · afips · 1987
An incremental compiler, in response to a program change, recompiles only the part of the program affected by the change, resulting in more efficient use of system resources and in improved response time. Current incremental programming environments based on compilation do not combine a small incremental unit for recompilation with sophisticated local and global register allocation schemes. This dissertation studies the problems of incrementally allocating local and global registers and generating target code in response to program edits. The unit of change is an intermediate code statement, and the target code that is produced incrementally utilizes registers as efficiently as a non-incremental target code generator that uses the same register allocation heuristics. The first step in the design of an incremental target code generator is an analysis of the effects of program edits on existing local and global register allocation. From the analysis, a model of register histories is constructed that maintains the ideal and the actual register allocation for the program. The model is designed to be independent of the local and global register allocation heuristics that are used. However, it is particularly useful for the incremental allocation of both local and global registers using graph coloring. Using the analysis and the model, incremental techniques for allocating registers and generating target code are developed. To provide insight into the performance of the incremental target code generator, both incremental and non-incremental systems are implemented. Their performances are compared both in terms of the quality of the target code that is produced and in the time it takes to make changes incrementally rather than by completely regenerating the target code. The results of the experiments indicate that the same high-quality target code that is produced non-incrementally can be produced incrementally. Under certain conditions, the savings for incremental incorporation of changes are considerable. The savings in time depend on the amount of code that is changed and on the amount of disruption to the register allocation. For test cases that involve changes to global register allocation, the savings in time range from 34 to 96% when up to 16% of the program is changed.