Status: Complete (Initial Implementation)
GitHub: github.com/rylanmalarchick/llvm-unroll-analyzer
Overview
A custom LLVM pass that analyzes loop structures and identifies unroll opportunities. This project demonstrates understanding of classical compiler infrastructure and serves as a foundation for quantum circuit compiler development.
Features
The pass traverses all functions in LLVM IR and:
- Detects loops and their nesting depth
- Distinguishes innermost vs outer loops
- Computes trip counts using Scalar Evolution
- Attaches unroll metadata recommendations
Unroll Recommendations
| Condition | Recommendation | Metadata |
|---|---|---|
| Innermost, trip count ≤ 16 | Full unroll | llvm.loop.unroll.full |
| Innermost, trip count > 16 | Partial unroll | llvm.loop.unroll.partial |
| Outer loop | No recommendation | — |
| Unknown bounds | No recommendation | — |
Technical Approach
New Pass Manager
Uses LLVM 18 New Pass Manager for modern pass infrastructure compatibility, providing better performance and flexibility compared to the legacy pass manager.
Scalar Evolution
Scalar Evolution (SE) is a powerful LLVM analysis that computes loop trip counts. It handles complex expressions and is essential for accurate loop analysis and optimization decisions.
Usage
# Compile test C code to LLVM IR
clang-18 -emit-llvm -S tests/test.c -o tests/test.ll
# Run the pass on the IR
opt-18 -load-pass-plugin=./libUnrollAnalyzerPass.so \
-passes="unroll-analyzer" tests/test.ll -S -o output.ll
Test Cases
| Test | Description |
|---|---|
| Simple loop | Constant bounds (trip count known) |
| Nested loop | 2-level nesting, identifies innermost |
| No loops | Baseline, no analysis needed |
| Variable bound | Unknown trip count handling |
| Triple nested | 3-level nesting depth |
| While loop | Variable bound pattern |
| Large constant | 1M iterations (partial unroll) |
Project Structure
| File | Description |
|---|---|
CMakeLists.txt |
CMake build configuration |
README.md |
Project documentation |
src/UnrollAnalyzer.cpp |
Main pass implementation |
tests/test.c |
Basic test cases |
tests/test.ll |
Pre-compiled LLVM IR |
tests/test_edge_cases.c |
Edge case tests |
tests/test_edge_cases.ll |
Edge case LLVM IR |
Technology Stack
| Category | Technology |
|---|---|
| LLVM Version | 18 |
| Language | C++ |
| Build | CMake |
| Analysis | Scalar Evolution, Loop Analysis |
Connection to Quantum Work
This project bridges classical compiler optimization with quantum circuit compilation:
| Classical Concept | Quantum Analog |
|---|---|
| LLVM Pass Infrastructure | Quantum circuit optimizer pass manager |
| Loop Analysis | Circuit depth analysis |
| Trip Count | Gate repetition patterns |
| Unroll Decisions | Gate cancellation/commutation decisions |
| SSA/Data Flow | Qubit dependency graphs |
Understanding classical compiler infrastructure (SSA, pass managers, analysis passes) directly translates to building effective quantum compilers.