During the summer of code 2016, I worked on implementing Polly as an Analysis pass in LLVM. My proposal can be found here. The basic idea of my proposal was to use exact dependence analysis of Polly in LLVM transformations so as to enable better loop optimizations like loop vectorization.

In the first phase of my project, I worked on creating a necessary infrastructure to use Polly’s analysis results in LLVM. As part of this project, I modified the existing analysis passes ScopInfo and DependenceInfo [D20770,D20831,D20912] and introduced new function passes [D20962,D21105] to bypass the region pass manager. In doing so, I have decoupled the logic of these analyses from their passes.

In the next phase, I worked on an interface to Polly, PolyhedralInfo [D21486,D22402,D22407], exposing API’s to check for parallelism and vectorization legality of a loop along with methods to compute the minimum dependence distance of the loop. The minimum dependence distance can be used as the maximum vectorization factor, provided the cost model allows it.

To show the usefulness of this interface, I experimented with LLVM test suite and captured number of loops statically (without generating any runtime checks) marked vectorizable by this interface. We found that 37 new kernels (30 unique) were marked vectorizable using the PolyhedralInfo API in addition to the loop vectorizer legality checks. The detailed results can be found here. We believe that this number can be improved further by

  1. Generating runtime checks based on Polly’s assumptions
  2. Handling parametric iteration distances, and
  3. Splitting the iteration domain for different iteration distances

In order to achieve these, the major challenge will be to provide a mechanism to return these assumptions and parametric iteration distance such that they can be utilized by the loop vectorizer’s own loop versioning system. I also experimented with the number of loops detected parallel by PolyhedralInfo in LLVM test suite.

Here's the list of all patches submitted to Polly and LLVM as part of this project: patches. Everything related to this GSoC project can be found here.

In this project, I have enabled LLVM transformations to use polyhedral analysis information. Going further, we will introduce more functions to the PolyhedralInfo interface and allow more transformation passes to query it. Information that can be extracted from the polyhedral model include.

  1. Loop trip count
  2. Instruction wise dependence

Currently, this interface is in an experimental phase, where we have not focussed on the compile time. We are trying to improve it by making the analysis demand driven as much as possible.

My experience from this GSoC:
It was a very pleasant experience and I feel very proud to have been able to contribute to a production grade, open source compiler. I have learnt a lot of things from coding standards, to code reviews, to code move policies. It felt great to get code reviews on my code from different people, even though they were not obliged to do so.
The tough part I felt was communicating with people from different demographics and from different intellectual levels.
Another difficulty I faced was working on such a large project, it was difficult to send patches after merging with latest code from trunk and doing manual merge as most of the time many people were working on the same files.