Incremental techniques for code generation problems

Abstract

Incremental compilation plays an important role in the functioning of integrated programming environments. The earlier phases of compilation like lexical analysis, parsing, semantic analysis, and dataflow analysis have been well studied from the incremental viewpoint. This thesis focuses on certain problems encountered in the design of the back-end of a compiler and, in particular, the code generation phase. In the case of one such problem, we propose a non-incremental or a batch algorithm as a solution followed by its incremental version, and in the case of the remaining problems, we consider the incremental version. The thesis also includes certain lower bound results on the incremental complexity of problems which have applications in the design of the back-end of a compiler. We first look at incremental basic block scheduling. We propose an incremental algorithm for computing the dependency directed acyclic graph (DDAG) of a basic block. We look at list scheduling based on the longest path length heuristic, and we adapt an existing algorithm for incrementally computing the longest path length information associated with the nodes of the DDAG. We have implemented the incremental scheduler for the IBM RS/6000 processor. We consider a generalized problem for scheduling expression trees on delayed-load architectures. We design an optimal non-incremental algorithm for this problem which generates an interlock-free schedule using the minimum possible number of registers. An extension to this algorithm handles spilling. Next, we propose an incremental solution to scheduling expression trees on delayed-load architecture. As a part of this work, we derive an unboundedness result for the problem of incrementally constructing the Sethi-Ullman (SU) listing of the nodes of the tree. The code selection problem is considered next. The bottom-up tree pattern matching problem is studied from the incremental viewpoint. Finally, we use the notion of incremental relative lower bounds (IRLB) to derive the IRLBs of three different problems connected to code generation. The following are the problems considered:

Interval partitioning of a flow graph Breadth-first search (BFS) of a directed graph Lexicographic depth-first search (DFS) of a directed graph

We conclude the thesis by listing a few directions in which further work may be carried out.