Currently I am working on my GSoC 2016 project on implementing Polly as an Analysis pass in LLVM. LLVM is a compiler infrastructure, which supports code optimization at compile time, link time and at runtime. LLVM is a modular project, consisting of many tools, where writing a new component is straight forward and can be plugged into the toolchain very easily.
The core concept of LLVM project is that every meaningful action is designed as a pass and user (in this case a pass) can use results from other passes by scheduling the required pass to run before itself. Having said that, LLVM consists mainly of three types of passes, Cannonicalization passes, Analysis passes and Transformation passes. Cannonicalization passes such as indvar(induction variable), loop-simplify, simplifycfg, ssa, lcssa etc. transform the AST to some cannonical form such that other analysis and transformations becomes easier. Analysis passes do not have side effects and hence never modify the AST. LLVM represents AST in an intermediate form called LLVM IR. It consists of Modules, Basic Blocks and Instructions. LLVM transformation passes takes LLVM IR as input, uses results from analysis passes, and finally produce, in the most cases, optimized LLVM IR. Some of the common analysis passes are dominator tree pass, alias analysis pass(group of passes), loop info pass, loop access info pass (performs dependence analysis), etc. Alias analysis and dependence analysis are very important with respect to reusable memory architecture. Hence, these analysis results are directly related to scope of more aggressive optimizations. Currently the dependence analyzer(DA) of LLVM(actually there are three DAs in LLVM) is not powerful enough. It relies on the alias analyzer and more on runtime memory checks. This limitation is partly because of the drawbacks of alias analyzer and partly because of parametric loop bounds and array references which requires a lot of runtime checks.
There is a polyhedral model of computing dependences in a loop because of array access. This model uses parametric integer linear programming to compute the dependences between array accesses and represents it as a relation. LLVM has a subproject called Polly, mostly developed by Tobias Grosser, which uses polyhedral model to analyze these dependences. Polly also does a lot of transformations in itself. The dependence analysis is exact analysis and provide more accurate results on the cost of more compile time. The current implementation of Polly does not expose any API to use its analysis results in LLVM passes, which is a very unfortunate thing. In this GSoC project, I am implementing an intrface to use the analysis results of Polly in LLVM. My work will go beyond this interface to actually show the use of its analysis results in LLVM transformation. For the initial implementation, I have proposed to use polyhedral analysis results in the Loop Vectorizer, a transformation pass in LLVM, and experiment with performance of transformed code.
GSoC coding started on 23-may-2016 and in the first week, I have provided a patch to provide compatibility of Polly to expose its analysis results with LLVM.
Happy Coding. Cheers! Utpal