Jeff Sandoval, Tuning an Adaptive Compilation Search Space with Loop Unrolling

This talk demonstrates that careful selection of compiler transformations can improve the output and reduce the compile time cost of current adaptive compilation techniques. Because compiler effectiveness is dependent on the order in which code transformations are applied, adaptive compilation has successfully employed empirical search to discover effective transformation sequences for each input program. This method often requires an unreasonable amount of time, however, because it reduces to the problem of searching for optimal points in a search space of exponential size. Related research focuses on pruning the search or reducing the cost of evaluating a single point, but these methods assume a fixed search space. Our approach, instead, improves the Rice University ILOC research adaptive compiler by augmenting the search space with a new transformation. Adding a loop unroller to address a deficiency in the set of transformations changes the search space contents, despite increasing the size, in a way that can facilitate more effective and efficient searching. Across nine benchmarks, the new search space allows the adaptive compiler to produce code, often in less time, that is an average of 10% faster. Unfortunately, adding a loop unroller is non-trivial within the context of our adaptive compiler. A secondary goal of this talk is to illustrate the complexity of identifying and unrolling loops in a low-level intermediate language, where high-level loop structures have been lost.