Improvement of PRE in the LLVM Compiler
The present LLVM framework lacks a wide scoped implementation of Partial Redundancy Elimination (PRE), which is an important global optimization. The current PRE implementation is not general as it caters to a special case having “Diamond control-flow pattern”. The aim of this project is to complete the current implementation of PRE in LLVM.
The objective of the proposed project is to enhance the present LLVM framework by inclusion of a complete GVN-PRE in its framework. The project will also study the impact of PRE in the Global Value Numbering (GVN) pass.
The following are the two broad objectives I aim to accomplish in my work.
The history of compiler optimization can be traced back to the history of compilers itself. The compiler based optimization is the process of analyzing the code to determine its properties and then to transform the code into more efficient or effective form. The transformations arising due to these optimizations can be of two main types one machine independent and other machine dependent. The machine independent transformations being the ones which does not rely on the specifics of a processor and hence improves the code or performance of the code on most target machines.
Partial redundancy elimination (PRE), a machine independent compiler optimization, first introduced by Morel and Renvoise in 1979 [2] has been one of the most important machine-independent global optimizations. This technique uses data flow analysis to determine the blocks of code which need to be moved/hoisted to removes partial redundancies in the program. PRE subsumes the common subexpression elimination and loop invariant computations. After the initial introduction of PRE by Morel-Renvoise, various versions of it were proposed at different points in time, each one proposing an improvement to its previous algorithm.
First noticeable algorithm was the Lazy Code Motion by Knoop et. al. [3] which improved the PRE algorithm proposed by Morel and Renvoise by avoiding unnecessary code motions and by removing bidirectional nature of the PRE data flow equations. Another noticeable PRE algorithm was proposed by Kennedy et al. in 1999 [4]. This paper introduced a Static Single Assignment (SSA) based PRE, and hence was called SSA-PRE.
The PRE algorithms discussed so far, eliminated the partial redundant expressions i.e. acts on only lexically similar algorithms. In 2004, Thomas VanDrunen in his PhD thesis [6] proposed the GVN-PRE [5] . A form of PRE which acted upon a lower level of semantical equivalence and redundancy, by unifying GVN into PRE. GVN-PRE also works on the SSA form and builds on the on concepts like availability, anticipatability and value numbering. Since one of the strengths of LLVM is its SSA form, it is appropriate that LLVM have a proper and complete implementation of GVN-PRE. The GCC implementation of GVN-PRE algorithm is well known to be quite scalable [8].
However, in the current LLVM, PRE finds a restricted presence. It is subsumed by GVN in the form of scalar PRE which performs partial redundancy elimination of only a special case, namely, the basic diamond case, i.e. the case where a value is computed in the successor and one predecessor but not the other predecessor, as mentioned in the comment in GVN.cpp [7] of the LLVM source code :
02625 /// Perform a purely local form of PRE that looks for diamond
02626 /// control flow patterns and attempts to perform simple PRE at the join point.
The above explanatory comment is enough to motivate completion of GVN-PRE implementation in LLVM. A recent bug-fix [11] led to a tripling (561 to 1517) of the number of instructions PRE’d by GVN PRE. This improvement inspires for completion of the PRE module in LLVM.
There is also a general need to improve the Load-PRE and Scalar-PRE and their interactions with the GVN module, which currently removes only fully redundant instructions, in LLVM.
I am Aradhya Biswas, currently in final semester of my senior year of undergraduate studies in the field of Computer Science and Engineering at Indian Institute of Technology Hyderabad (IITH). As I am in my final semester, and have no other professional bindings this summer other than this project, I plan to completely focus on it full-time.
I was first introduced to LLVM about a year ago in the course "Principles of Compiler Design" at IITH and am currently pursuing an advanced compiler course. Since the introduction, I have used LLVM for a multitude of my course assignments and mini-projects. This helped me gain good working knowledge of the LLVM framework.
Regarding my past research background, I had the opportunity to intern at Cyber Physical Systems Innovation Hub IITH and College of Computing at Georgia Institute of Technology. My work during my Internship at CPS Innovation hub IITH culminated in a publication in IEEE RAICS 2013. These internships added on with the plethora of projects I took up as part of my curriculum helped me develop proficiency in C and C++ coding.