Polly: Polyhedral optimizations for LLVM

Polly is a project that works on advanced optimizations for data-locality and parallelism. It uses the polyhedral model, a high-level mathematical abstraction, to analyse and optimize the memory access pattern of a program. Due to the use of a polyhedral representation Polly can easily calculate detailed data dependency information which it uses to derive an optimized loop structure. Polly can speed up sequential code by improving memory locality and consequently the cache use. Furthermore, Polly is able to expose different kinds of parallelism which it exploits by introducing (basic) OpenMP and SIMD code. The automatic use of vector accelerators is planned and will take avantage of the ongoing work on the LLVM PTX backend.

Polly is still a research project, that is not production quality. We are working on a robust implementation of Polly's core. You are invited to join us by directly contributing to Polly or by using it for your own research.

Major changes in Polly

• July 2011 - Add Polly builder to the LLVM Buildbots
• June 2011 - Tobias is founded for three years through a Google Europe Fellowship in Efficient Computing.
• May 2011 - Tobias' diploma thesis and Raghesh's master thesis are published. For details see our list of publications.
• April 2011 - Polly moves to the LLVM infrastructure
• March 2011 - Polly is presented at CGO/IMPACT 2011, Polly can compile polybench 2.0 with vectorization and OpenMP code generation.
• Februar 2011 - pollycc - a script to automatically compile with polyhedral optimizations
• Januar 2011 - Basic OpenMP support, Alias analysis integration, Pluto/POCC support
• Dezember 2010 - Basic vectorization support
• November 2010 - Talk about Polly at the LLVM Developer Meeting
• October 2010 - Added dependency analysis
• October 2010 - Finished Phase 1 - Get something working
• October 2010 - Support for scalar dependences and sequential SCoPs
• August 2010 - RegionInfo pass committed to llvm
• August 2010 - llvm-test suite compiles
• July 2010 - Code generation works for normal SCoPs.
• June 2010 - OpenSCoP import/export works (as far as openscop is finished)
• May 2010 - The CLooG AST can be parsed
• April 2010 - SCoPs can automatically be detected (WIP)
• March 2010 - The RegionInfo framework is almost completed.
• February 2010 - Translating a simple loop to Polly-IR and passing it to CLooG-isl to regenerate a loop structure works.
• February 2010 - ISL and CLooG are integrated.
• January 2010 - The RegionInfo pass is finished.
• End of 2009 - Work on the infrastructure started.

The architecture of Polly