Polly Polyhedral Framework: LLVM's Mathematical Loop Optimizer

Polly is LLVM's polyhedral optimizer that transforms loop nests into mathematical representations to perform advanced optimizations like tiling, fusion, and automatic parallelization on Static Control Parts (SCoPs).

Polly is a high-level optimization framework integrated into the LLVM compiler infrastructure. According to the llvm/llvm-project repository, it analyzes and transforms loop nests using the polyhedral model—a mathematical approach that enables global optimization across entire computational kernels. The framework serves as a bridge between traditional compiler optimizations and advanced loop transformations typically found in high-performance computing.

How Polly Works: The Three-Stage Pipeline

Polly operates through a strictly defined pipeline of LLVM passes that convert imperative loop code into polyhedral representations, optimize them mathematically, then regenerate LLVM IR.

Front-End: Detection and Canonicalization

The first phase prepares LLVM IR and identifies optimizable regions. In polly/lib/Pass/PollyFunctionPass.cpp, the front-end orchestrates three critical passes:

• polly-canonicalize – Normalizes IR by expanding affine maps and inserting metadata to ensure subsequent analyses can recognize loop patterns
• polly-detect – Scans each function for Static Control Parts (SCoPs)—regions that satisfy polyhedral constraints such as affine loop bounds and memory accesses
• polly-scops – Emits a polyhedral description containing iteration domains and access functions for every detected SCoP, stored in internal data structures

These passes ensure that only well-formed loop nests with affine control flow enter the optimization pipeline.

Middle-End: Dependence Analysis and Scheduling

Once SCoPs are identified, Polly performs sophisticated mathematical optimization using the Integer Set Library (ISL) integrated in polly/lib/External/isl:

• polly-dependences – Computes precise data dependences between all memory accesses within a SCoP using ISL's polyhedral algorithms
• polly-opt-isl – Invokes ISL's optimizer to explore legal transformations (tiling, loop interchange, skewing) and selects optimal schedules according to cost models for latency, bandwidth, or parallelism

This stage provides research utilities including polly-export-jscop and polly-import-jscop, which serialize SCoPs to JSON format (.jscop files) for offline analysis and reproducible experiments. Visualization tools like dot-scops and view-scops generate Graphviz representations of the polyhedral structure.

Back-End: Code Generation

The final phase converts mathematical schedules back to executable code:

• polly-ast – Generates an Abstract Syntax Tree (AST) from ISL's optimized schedule, representing the transformed loop structure
• polly-codegen – Lowers the AST back to LLVM IR, producing the optimized loop nest with transformations applied

The entire pipeline is registered as an LLVM plugin in polly/lib/Plugin/Polly.cpp, which injects these passes into the LLVM pass manager when users enable the -polly flag. The PhaseManager (polly/include/polly/Pass/PhaseManager.h) coordinates execution based on command-line options.

Key Source Files in llvm-project

Understanding Polly's architecture requires familiarity with these critical files:

File Path	Role
polly/README	High-level overview of Polly's purpose and polyhedral model capabilities
polly/lib/Plugin/Polly.cpp	Plugin registration and command-line flag definitions (-polly, -polly-*)
polly/include/polly/Pass/PollyFunctionPass.h	Declaration of the function-level pass driver
polly/lib/Pass/PollyFunctionPass.cpp	Implementation orchestrating front-, middle-, and back-end phases for single functions
polly/lib/Pass/PollyModulePass.cpp	Module-level driver for inter-procedural analyses crossing function boundaries
polly/www/documentation/passes.html	Human-readable catalog of all Polly LLVM passes
polly/lib/External/isl	Integration of the ISL library providing the mathematical optimization engine

Practical Usage Examples

Enabling Polly in Clang

The most common entry point activates Polly through Clang's driver:

/* matmul.c */
int A[1024][1024], B[1024][1024], C[1024][1024];

void matmul(void) {
  for (int i = 0; i < 1024; ++i)
    for (int j = 0; j < 1024; ++j)
      for (int k = 0; k < 1024; ++k)
        C[i][j] += A[i][k] * B[k][j];
}

Compile with optimization flags:

clang -O3 -march=native -mllvm -polly -mllvm -polly-vectorizer-choose=latency matmul.c

The -mllvm -polly flag activates the plugin, automatically tiling and vectorizing the inner loops to reduce cache misses and expose SIMD parallelism.

Running Individual Passes with opt

For research or custom pipelines, load the plugin directly in opt:

opt -load=./lib/Polly.so \
    -polly-canonicalize -polly-detect -polly-scops \
    -polly-dependences -polly-opt-isl \
    -polly-ast -polly-codegen \
    -S < input.ll > optimized.ll

Each -polly-* flag corresponds to a specific pass, allowing fine-grained control over the optimization process.

Exporting SCoPs for Offline Analysis

Researchers can export the polyhedral representation to JSON:

opt -load=./lib/Polly.so -polly-export-jscop -S -o /dev/null input.ll

This generates .jscop files alongside the original IR, which can be inspected manually or re-imported via -polly-import-jscop for reproducible experiments.

Summary

• Polly is a LLVM plugin that applies the polyhedral model to optimize Static Control Parts (SCoPs)—loop nests with affine control flow and memory accesses.
• The framework provides a global view of entire loop nests, enabling cross-loop optimizations like tiling and fusion that traditional LLVM passes cannot perform.
• Optimization relies on the ISL (Integer Set Library) to solve integer-linear programming problems and find schedules minimizing latency or maximizing parallelism.
• The pipeline consists of distinct front-end (detection), middle-end (mathematical optimization), and back-end (code generation) phases implemented in PollyFunctionPass.cpp and related files.
• Users activate Polly via Clang's -polly flag or manually orchestrate individual passes through opt for research purposes.

Frequently Asked Questions

What exactly constitutes a SCoP in Polly?

A Static Control Part (SCoP) is a program region contained within polly/lib/Pass/PollyFunctionPass.cpp's detection logic that has strictly affine loop bounds, affine array subscripts, and no data-dependent control flow. This regularity allows Polly to represent the region as a polyhedron and apply mathematical transformations that preserve program semantics.

How does Polly differ from standard LLVM loop optimizations?

Standard LLVM loop passes operate locally on individual loops using heuristics, whereas Polly, as implemented in polly/lib/External/isl, considers the entire loop nest simultaneously through integer-linear programming. This global analysis enables transformations requiring cross-loop reasoning—such as full-program tiling and software pipelining—that traditional -O3 optimizations cannot legally perform.

Is Polly included in standard LLVM builds?

Polly is included in the llvm/llvm-project repository but may require explicit enabling during the build process. When building LLVM, set LLVM_ENABLE_POLLY=ON to compile the shared library (Polly.so) and headers. Once built, the plugin automatically registers passes with opt and Clang when loaded.

Can Polly optimize loops with non-affine array accesses?

No—Polly's polyhedral model requires affine relationships between loop iterators and memory addresses. The polly-detect pass strictly filters out non-affine regions, leaving them for LLVM's traditional loop optimization passes. This limitation ensures mathematical correctness but means Polly skips code with pointer chasing, indirect indexing, or data-dependent bounds.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}