# Polly Polyhedral Framework: LLVM's Mathematical Loop Optimizer

> Discover Polly, LLVM's polyhedral optimizer. Transform loops mathematically for advanced optimizations like tiling and automatic parallelization on SCoPs. Boost your code's performance.

- Repository: [LLVM/llvm-project](https://github.com/llvm/llvm-project)
- Tags: deep-dive
- Published: 2026-09-11

---

**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`](https://github.com/llvm/llvm-project/blob/main/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`](https://github.com/llvm/llvm-project/blob/main/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`](https://github.com/llvm/llvm-project/blob/main/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`](https://github.com/llvm/llvm-project/blob/main/polly/lib/Plugin/Polly.cpp) | Plugin registration and command-line flag definitions (`-polly`, `-polly-*`) |
| [`polly/include/polly/Pass/PollyFunctionPass.h`](https://github.com/llvm/llvm-project/blob/main/polly/include/polly/Pass/PollyFunctionPass.h) | Declaration of the function-level pass driver |
| [`polly/lib/Pass/PollyFunctionPass.cpp`](https://github.com/llvm/llvm-project/blob/main/polly/lib/Pass/PollyFunctionPass.cpp) | Implementation orchestrating front-, middle-, and back-end phases for single functions |
| [`polly/lib/Pass/PollyModulePass.cpp`](https://github.com/llvm/llvm-project/blob/main/polly/lib/Pass/PollyModulePass.cpp) | Module-level driver for inter-procedural analyses crossing function boundaries |
| [`polly/www/documentation/passes.html`](https://github.com/llvm/llvm-project/blob/main/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:

```c
/* 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:

```bash
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`:

```bash
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:

```bash
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`](https://github.com/llvm/llvm-project/blob/main/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`](https://github.com/llvm/llvm-project/blob/main/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.