Design-Space Exploration for Speculative Optimizations
To design and implement a design-space exploration scheme for speculative optimizations.
Previous research has shown that not all aliases within a program occur during a given execution run. However, the compiler has to optimize the code assuming that none of the memory dependences are violated during transformations. Speculative optimizations perform risky transformations on the code, and hope that the benefits in cases when the semantics are not violated, make up for the losses when they are. The latter is called misspeculation, and recovery mechanisms are required to maintain correct state. The gains from speculative optimizations therefore, define the performance gains achieved, and the threshold of misspeculation which can be tolerated. The phase ordering of optimizations plays a big role in determining how well the code performs. Hence, the phase ordering of speculative optimizations is especially important. In this project, I will perform a design-space exploration to find the right set of speculative optimizations to maximize performance given a set of sites for performing speculation.
In order to speculate, profitable sites need to be identified. Alias analysis queries offer opportunities for speculating, since the analysis conservatively assumes that all loads and stores alias, until it can prove otherwise. By speculating on that a set of loads and stores do not alias, optimizations within the compiler can re-order them with respect to one another. Besides helping code scheduling, this also enables other transformations like register allocation. In a typical compiler, the order of optimizations are chosen based on heuristics. These heuristics do not always guarantee the best performance. Hence, there is a necessity perform design-space exploration in cases where the best performance is required. Here, I will implement such a design-space exploration using LLVM[5] and Pin[4]. LLVM will be used to create multiple versions of the same function. Each version of the function will be put through a different set of optimizations. The execution environment with speculation checking and recovery mechanisms will be implemented in Pin. In addition, a first-order accurate performance model using data cache hierarchy will be implemented in Pin.
The program will be executed in two phases, namely, training phase and execution phase. In the training phase, each version of the function will be executed once, and the performance will be compared. The best performing version(s) of the function make it to the execution phase, where they will be used for the rest of the execution time.
Other works [1][2][3] have looked at various techniques for design space exploration of compilers. Their efforts have primarily focused on non-speculative, traditional compiler transformations.
To summarize, the contributions of this project will be:
Webpage: www4.ncsu.edu/~rvanka
[1] . Kulkarni, P. A., Whalley, D. B., and Tyson, G. S. 2007. Evaluating Heuristic Optimization Phase Order Search Algorithms. In Proceedings of the international Symposium on Code Generation and Optimization (March 11 - 14, 2007)
[2]Triantafyllis, S., Vachharajani, M., Vachharajani, N., and August, D. I. 2003. Compiler optimization-space exploration. In Proceedings of the international Symposium on Code Generation and Optimization: Feedback-Directed and Runtime Optimization (San Francisco, California, March 23 - 26, 2003)
[3] Kulkarni, P. A., Whalley, D. B., Tyson, G. S., and Davidson, J. W. 2006. Exhaustive Optimization Phase Order Space Exploration. In Proceedings of the international Symposium on Code Generation and Optimization (March 26 - 29, 2006)
[4] Lattner, C. and Adve, V. 2004. LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation. In Proceedings of the international Symposium on Code Generation and Optimization: Feedback-Directed and Runtime Optimization (Palo Alto, California, March 20 - 24, 2004)
[5]Luk, C., Cohn, R., Muth, R., Patil, H., Klauser, A., Lowney, G., Wallace, S., Reddi, V. J., and Hazelwood, K. 2005. Pin: building customized program analysis tools with dynamic instrumentation. In Proceedings of the 2005 ACM SIGPLAN Conference on Programming Language Design and Implementation (Chicago, IL, USA, June 12 - 15, 2005)