PGARA: Profile-Guided Adaptive Register Allocation
Team 14 · Compiler Design (L43+L44) · Vellore Institute of Technology · Release v1.0.0
PGARA is a complete compiler for MiniC, a small C subset, built around a new register allocator. A profiling run measures how often each branch is taken. Every SSA value is then modelled as a two-state Markov decision process (register or memory) to compute the cycles a register would save, and registers are sold in a sealed-bid auction on the chordal interference graph, settled by best-response dynamics into a Nash equilibrium. No graph colouring is used. A web interface, PGARA Compiler Studio, shows every phase of compilation as you type.
Repository contents
| # | Required item | Where |
|---|
| 1 | Manuscript LaTeX (zip, all images and class files, compiles on Overleaf) | manuscript/PGARA-Manuscript-LaTeX.zip (unzipped copy in manuscript/latex/) |
| 2 | Source code | pgara/ (compiler and allocators), web/ (GUI), server.py, api/ (Vercel entry point) |
| 3 | README | this file |
| 4 | Dependencies | requirements.txt (standard library only), requirements-dev.txt (optional tools) |
| 5 | Datasets and preprocessing | benchmarks/ (22 MiniC programs), datasets/benchmark_inputs.json, scripts/prepare_datasets.py |
| 6 | Trained models | none: PGARA learns nothing offline; its only "model" is the per-program profile, computed at compile time |
| 7 | Configuration files | configs/experiments.json, configs/server.example.env, vercel.json |
| 8 | Execution scripts | scripts/ (setup, tests, GUI, experiments, benchmark, single compile; .sh and .bat) |
| 9 | Results, metrics, sample outputs | results/ (see results/README.md) |
| 10 | Documentation | manuscript/PGARA-FINAL.pdf, guide/PGARA-Project-Guide.pdf, docs/screenshots/ |
| 11 | Demo video | docs/demo/ |
pgara/ compiler: lexer, parser, semantic, irgen, cfg, ssa, optimize, interp,
regalloc (PGARA + 6 baselines), codegen, simulator, pipeline, bench, experiments
tests/ 27 unit and end-to-end tests
benchmarks/ original suite (10) · extra/ independent suite (7, MiBench/BEEBS) · tuning/ (5)
datasets/ inputs and reference outputs of every program (generated, verified)
configs/ experiment settings and GUI settings template
scripts/ setup and execution scripts
results/ experimental results (JSON), summary tables, sample outputs
manuscript/ final PDF and LaTeX sources
docs/ demo video and script, full GUI screenshots
web/, server.py PGARA Compiler Studio (web GUI)
System requirements
- Python 3.8 or newer (tested with 3.12 and 3.13) on macOS, Linux or Windows.
- No third-party packages. Everything uses the Python standard library.
- A modern web browser for the GUI.
- About 50 MB of disk space; a full reproduction of the experiments takes 15–25 minutes on a laptop.
- Optional:
coverage and playwright (requirements-dev.txt) only to measure coverage or regenerate screenshots.
Installation
git clone https://github.com/shreyans-chowdry/pgara.git
cd pgara
python3 -m pip install -r requirements.txt # installs nothing: no runtime dependencies
scripts/setup.sh # checks Python and verifies all benchmark programs
On Windows use python instead of python3, and run the .bat scripts.
Configuration
configs/experiments.json holds every setting used for the manuscript: register budgets k = 3–32, hot-edge threshold θ = 0.75, gain policy and cost-model constants (load 4, store 2, σ = 1, c_mv = 1). Pass it with --config; scripts/run_experiments.sh does this for you.configs/server.example.env: copy it to configs/server.env to change the GUI port or stop the browser from opening.- No passwords, API keys or network services are needed.
Execution
| Task | Command | Time |
|---|
| Start the web GUI | scripts/run_gui.sh (or start.sh, start.command, start.bat, python3 server.py) → http://127.0.0.1:8765/ | instant |
| Run all tests | scripts/run_tests.sh (Windows: scripts\run_tests.bat) | 1–3 min |
| Reproduce every result of the paper | scripts/run_experiments.sh (Windows: scripts\run_experiments.bat) | 15–25 min |
| Run selected studies | scripts/run_experiments.sh main inputs | |
| Quick four-allocator study | scripts/run_benchmark.sh | 10 s |
| Compile one program | scripts/compile_example.sh benchmarks/05_rarebranch.mc 4 "7 10" "13 10" | 1 s |
| Rebuild sample outputs | python3 scripts/sample_outputs.py | 1 s |
| Summarise results | python3 scripts/summarise_results.py | 1 s |
There is no training step: PGARA's only learned quantity is the per-program profile, which is measured during compilation.
The studies of python3 -m pgara.experiments are:
| Study | What it does |
|---|
tuning | chooses θ on the held-out suite benchmarks/tuning (never used in reported results) |
main | 17 programs, seven allocators, k = 3, 4, 5, 6, 8, 16, 32 |
inputs | five test inputs per program at k = 4 |
errsweep | rare-branch, training error rate 1%–60% |
costs | sensitivity to the model constants σ and c_mv |
policy | realised (always-in-register) gain vs optimal-policy gain |
scaling | allocation time on generated programs of growing size |
The allocators are PGARA, Static-Prior PGARA, profiled-frequency priority (ablation), loop-depth priority, Chaitin–Briggs with static and with profile-weighted spill costs, and linear scan.
Verified in a fresh environment
A fresh clone was set up in a clean Python 3 environment with no extra packages. scripts/setup.sh, scripts/run_tests.sh (27 tests, OK) and scripts/run_experiments.sh main all ran successfully, and results/v2/main.json was reproduced exactly.
Key results
At k = 4, over 17 programs (geometric mean), PGARA needs:
- 21.8% fewer cycles than linear scan,
- 3.7% fewer than Chaitin–Briggs with profiled spill costs,
- 3.3% fewer than profiled-frequency priority,
- 2.6% fewer than Static-Prior.
It also executes 50% fewer spill memory operations than linear scan. All 1,428 compiled configurations match the reference output. See results/README.md.
Using the GUI
- Pick a program from the Program list (ten benchmarks), or type your own MiniC in the editor.
- Set Registers k, the number of allocatable registers (2–16).
- Set the Training input used for profiling and the Test input used for measurement. Separate the numbers with spaces; each call to
input() reads the next one.
- With Live compile ticked, the program recompiles as you type. Otherwise press Compile.
Errors appear under the editor and in red in the gutter. Click an error to jump to its line.
| Tab | What it shows |
|---|
| Tokens | The token stream from the maximal-munch DFA lexer, colour-coded by kind: keywords purple, identifiers blue, numbers orange, operators pink. Hover a token to highlight it in the source. |
| AST | An interactive syntax tree. Drag to pan, scroll to zoom, click a node to fold it. Colours show declarations (indigo), control flow (violet), statements (green), expressions (orange) and leaves (blue). |
| Symbols | The scoped symbol table, one card per scope, with unique IR names, kinds, types and reference counts. |
| TAC | Three-address code. Use the step buttons or Play to emit it one instruction at a time. |
| SSA & Optimiser | Pruned SSA with φ-functions, then the optimised SSA, with a log of each optimisation pass. |
| CFG | The control-flow graph. Block headers are coloured by how often they ran (blue for rare, red for hot). Each edge shows its profiled probability (static prior). Violet dashed edges are loop back edges. |
| Allocation | The interference graph, with each register in its own colour and spilled values in red dashed outline. A table lists each value's MDP gain G(v), coalition bid, live-range size and policy-iteration rounds. It also shows every sealed-bid auction round (winners green, losers red) and the perfect elimination ordering. |
| Target Code | PG-RISC assembly that you can step through. Spill loads and stores are tagged red, caller-save code amber, φ copies violet and forwarded loads green. Hover a line to see the IR it came from. |
| Run & Metrics | The output of the reference interpreter. It also compares all four allocators on cycles, instructions, loads and stores, spill memory operations, register utilisation, code size and realised gain, with bar charts. The best allocator is highlighted green. |
| Grammar | The LL(1) grammar (41 nonterminals, 94 productions), its FIRST and FOLLOW sets, and the predictive-table check. The only conflict is the dangling else. |
The pipeline
- Lexer: a maximal-munch DFA with line and column positions. It recovers from errors in panic mode.
- Parser: hand-written recursive descent for an LL(1) grammar, building an abstract syntax tree. It recovers from errors in panic mode.
- Semantic analysis: an L-attributed evaluation over a stack of hash-map scopes. It checks types, arity, arrays,
break/continue placement and missing returns, and gives every symbol a unique IR name.
- TAC generation: syntax-directed translation, with jumping code for
&&, || and !.
- CFG and SSA: basic blocks, critical-edge splitting, Cooper–Harvey–Kennedy dominators, dominance frontiers, natural loops, and pruned SSA (Cytron et al.).
- Optimiser: SCCP, copy propagation, algebraic simplification and strength reduction, dominator-scoped GVN, DCE, block merging and compare-branch fusion.
- Profiling: a reference interpreter runs the optimised SSA on the training input and counts how often each CFG edge is taken.
- PGARA allocation:
- Each SSA value is modelled as a two-state (register or memory) Markov decision process over its live range.
- Policy iteration solves it exactly, giving the value's expected gain G(v).
- φ-related values bid together as coalitions.
- Registers are awarded by a sealed-bid auction in maximum-cardinality-search order on the chordal interference graph.
- Best-response dynamics then settle the result into a Nash equilibrium.
- Code generation: out-of-SSA translation with parallel copies, spill slots shared per φ-web, caller-save around calls, and a peephole pass.
- Simulator: a cycle-counting PG-RISC machine. Each run is checked against the reference interpreter's output.
The GUI compares four allocators: PGARA, Static-Prior PGARA (no profile), loop-depth priority (Chow–Hennessy style) and linear scan (Poletto–Sarkar). The experiment harness adds profiled-frequency priority and Chaitin–Briggs with static and with profile-weighted spill costs.
MiniC in brief
int data[100]; // global array
int sum(int a[], int n) { // array parameters are passed by reference
int s = 0;
for (int i = 0; i < n; i++) s += a[i];
return s;
}
int main() {
int n = input(); // reads the next number from the input box
for (int i = 0; i < n; i++) data[i] = i * i;
if (n > 0 && sum(data, n) % 2 == 0) print(1); else print(0);
return 0;
}
| Feature | Supported forms |
|---|
| Types | int scalars, int arrays, void functions |
| Control flow | if/else, while, for, break, continue, return |
| Operators | + - * / %, < <= > >= == !=, `&& |
| Assignment | = += -= *= ++ -- |
| Input and output | input() and print(expr) |
Team
| Member | Registration No. | Role |
|---|
| Shreyans Chowdry | 24BDS0114 | Core pipeline design, lexical and syntax analysis, AST construction, intermediate code generation, web GUI; in the allocator: transition matrices, block frequencies, φ-web coalitions |
| Samrender Singh Saini | 24BCE2865 | Semantic analysis, scope resolution and symbol table management; in the allocator: interference graph, MCS order, sealed-bid auction and binding |
| Karthikeya Jami | 24BCE2136 | SSA, optimisation engine and PG-RISC code generation; in the allocator: residency MDP, policy iteration and gains |
| Abhishek Kumar | 24BCE0585 | Runtime environment, simulator, test suite and benchmarking; in the allocator: best response, coalition repair, baselines and ablations |
| Nishanth Kumar | 24BAI0194 | Documentation and interface testing support |
The guide folder holds PGARA-Project-Guide.pdf, a plain-language explanation of the project written for Draft 1; numbers in it predate the revised evaluation, which is in the manuscript.
