On accelerating the searches for compilation sequences in an adaptive compiler

Recent research show that adaptive compiler can produce consistent improvement over a traditional fixed-sequence compiler by conducting feedback-directed searches for good compilation sequences for specific programs, machines and performance objectives. However, such improvement is usually achieved at very high search cost. This thesis proposes two approaches to accelerate the searches for a good compilation sequence in an adaptive compiler. First, a local search algorithm, Greedy Neighbor Exploration algorithm (GNE), is proposed. It uses optimistic greedy construction and cleanup procedures to generate a richer set of meaningful variations by randomized insertion and removal of transformations. Experimental results on a range of standard benchmark suites show that GNE finds better compilation sequences in less than a quarter of the evaluations required by current search algorithms, such as genetic and hill climbing algorithms. Second, code normalization techniques are developed to hash programs and detect equivalent code. This can avoid unnecessary runs of programs