polly

polly/ is a polyhedral loop optimizer — a body of analysis and transformation passes that operate on LLVM IR loop nests using the polyhedral model. It plugs into the LLVM optimizer as an additional pass pipeline, can run on its own via opt, and ships its own dependency: the Integer Set Library (ISL).

Purpose

The polyhedral model represents loop nests as parametric polyhedra in an integer space. That representation makes a class of analyses precise that imperative analyses can only approximate: exact dependence analysis on affine accesses, tile-size selection, fusion/distribution legality. Polly is LLVM's way of getting those analyses without bolting them onto the standard pass pipeline.

Directory layout

polly/
├── include/polly/   # Public C++ headers
├── lib/             # Implementation
│   ├── Analysis/    # Scop detection, dependence analysis, schedule construction
│   ├── CodeGen/     # Polyhedral schedule → LLVM IR
│   ├── Exchange/    # JSCoP — JSON-formatted polyhedral input/output for external tools
│   ├── External/    # Vendored ISL and pet (see below)
│   ├── Plugin/      # opt-plugin glue
│   ├── Support/
│   └── Transform/   # Specific transformations (DeLICM, ScheduleOptimizer, ScopInliner, etc.)
├── tools/           # Binary drivers
├── test/            # lit regression tests
├── unittests/
├── docs/
├── cmake/
└── README

ISL — the bundled dependency

Polly's lib/External/ directory imports the Integer Set Library (ISL), the C library that performs the actual polyhedral computations (set/relation operations, schedule trees, code generation). Updating ISL involves a controlled re-import; the directory is treated as a vendored third-party tree.

This is part of why Polly's reported source-line count is large despite the relatively focused scope of the project itself.

Key abstractions

Type	File	Role
polly::Scop	polly/include/polly/ScopInfo.h	"Static Control Part" — the unit of polyhedral optimization
polly::ScopDetection	polly/include/polly/ScopDetection.h	Identifies SCoPs in IR
polly::Dependences	polly/include/polly/DependenceInfo.h	Polyhedral dependence analysis
polly::IslScheduleOptimizer	polly/lib/Transform/ScheduleOptimizer.cpp	Calls ISL's scheduler to produce an optimized polyhedral schedule
polly::IslNodeBuilder	polly/lib/CodeGen/IslNodeBuilder.cpp	Generates LLVM IR from an ISL schedule tree

How it works

graph LR
    ir[LLVM IR loop nest] --> detect[ScopDetection]
    detect --> scop[Scop]
    scop --> deps[Dependences]
    scop --> opt[IslScheduleOptimizer<br/>(tiling, fusion, parallelism)]
    deps --> opt
    opt --> schedule[New polyhedral schedule]
    schedule --> codegen[IslNodeBuilder]
    codegen --> ir2[Optimized LLVM IR]

A typical Polly invocation:

1. Run scop detection over the IR. Loops with affine bounds and affine memory accesses become candidate SCoPs.
2. For each SCoP, compute dependences using ISL.
3. Ask ISL's scheduler for a new schedule that respects dependences and improves locality / parallelism.
4. Generate IR for the new schedule, replacing the original loop nest.

Polly is opt-in. Pass -O3 -mllvm -polly (or the equivalent in the new pass manager) to enable it.

Integration points

• LLVM core (llvm) — Polly is a plugin pass that hooks into the IR pipeline.
• OpenMP — Polly can emit parallel-loop annotations consumed by the openmp runtime.
• External JSCoP — Polly can import/export polyhedral programs as JSON for cooperation with external polyhedral tools.

Entry points for modification

• Adding a transformation: a class in polly/lib/Transform/ that consumes a Scop and an ISL Schedule, computes a new schedule, and reschedules the SCoP.
• Tuning detection: edit polly/lib/Analysis/ScopDetection.cpp. Most "Polly didn't kick in for my loop" issues trace back here.
• Updating ISL: a controlled re-import; see the helper scripts under polly/utils/.

Reference

• Polly documentation
• Integer Set Library (ISL)