An experimental analysis of a set of compiler algorithms*

The thesis of this dissertation is that experimental analysis in computer science is an essential component of understanding algorithmic behavior. In three different experiments, we compare and contrast well-chosen algorithms and show empirical evidence of performance differences. In all cases herein, the algorithms that were assumed to be the best are shown to have superior, sometimes surprising alternatives, justifying our thesis. In each case, we developed a set of solutions and evaluated and refined them until we discovered better methods. In the first experiment, we examine different methods for building an interference graph, the pivotal structure of a graph-coloring register allocator. Our results show that a twenty-year-old assumption about the graph's characteristics is flawed, and we show extensive data to explain the best way to build this graph. In the second experiment, we take an O(n 2) algorithm for computing dominance and show how to make it run, in general, faster than the commonly used dominator algorithm due to Lengauer and Tarjan, which runs in time proportional to the inverse of Ackermann's function. The dominance work led to our third experiment, which seeks to show the best way to compute iterative data-flow analyses. There is a well understood theoretical specification due to Kam and Ullman that bounds the time necessary to compute specific types of data-flow equations. We compare their algorithm against a simple worklist algorithm that takes its intuition from a study of how Kam and Ullman's algorithm propagates information, and we show that the worklist algorithm is faster, in practice. In many ways, the value of this work is in the engineering improvements to necessary and complicated phases of the compiler. *This work is based in part upon work supported by the Texas Advanced Technology Program under Grant No. 003604-015 and by Darpa through Army Contract DABT63-95-C-0115