cbril

A Bril IR toolchain written from scratch in C++20: parse Bril JSON, build a CFG, run analyses and optimization passes over it, and emit either Bril JSON back out or LLVM IR.

Currently implemented: CFG construction, a template dataflow framework, dominance tree and dominance frontier, natural-loop detection and loop simplification, semi-pruned SSA construction, DCE, LVN, GVN, sparse conditional constant propagation, and an LLVM backend with both an alloca-based and an SSA/phi-based code path.

This grew out of working through CS 6120, and the notes below double as a lab diary — each section records what is done, what is not, and the things that turned out to be subtle.

Building

Requirements:

• A C++20 compiler (developed with GCC 13)
• CMake 3.20 or newer
• LLVM 17 or newer, with its CMake package files available (developed against LLVM 23)
• bril2json from the Bril toolchain, to turn .bril text into the JSON this tool reads

Two dependencies are downloaded automatically at configure time, so there is nothing to install for them:

• nlohmann/json v3.11.3 — JSON parsing
• CLI11 v2.6.2 — command-line parsing

Both are header-only, so they are compiled into the tool rather than linked against.

Point CMake at your LLVM installation with -DLLVM_DIR:

cmake -S . -B build -DLLVM_DIR=$(llvm-config --cmakedir)
cmake --build build

If llvm-config is not on your PATH, pass the directory that contains LLVMConfig.cmake directly:

cmake -S . -B build -DLLVM_DIR=$HOME/llvm-project/build/lib/cmake/llvm

This builds two executables into build/: bril_tools and graph_test.

Running

bril_tools reads a Bril program as JSON, from a file argument or from stdin:

bril2json < tests/ssa/loop.bril | ./build/bril_tools
./build/bril_tools program.json -e llvm -o program.ll

Flag	Meaning
FILE	Bril JSON input (default: stdin)
-o, --output	Output file (default: stdout)
-e, --emit	Output format: json or llvm (default: json)

Which passes run is still decided by editing src/main.cpp — there is no flag for pass selection yet. Graph visualisations are written to a temporary .dot file and opened with xdot, so a working X or Wayland display is needed for those.

Layout

Path	Contents
src/ir/	Instruction hierarchy, CFG builder, JSON/string visitors
src/adt/	IndexVec, typed indices, small utilities
src/graph/	Abstract graph, traversals, dominators, natural loops, SCC
src/analysis/	Dataflow framework, dominance info, loop info, CFG adaptor
src/transform/	LVN, GVN, SCCP, SSA construction, loop simplification
src/codegen/	LLVM backends (alloca-based and SSA/phi-based)
tests/	.bril test inputs, grouped by the pass they exercise

---

Status and notes

IR and core instructions

• CFG construction from Bril JSON, with a lazy predecessor cache
• Types
• Beautified CFG rendering
• BlockIdx and IndexVec for type safety — an IndexVec can only be indexed by its own index type. This also set up the graph layer: there is now an abstract Graph class and an adaptor between the CFG and it. Algorithms are written against the abstract graph and get their information through the adaptor — separation of concerns.
• Turnt for snapshot testing, starting with the JSON parse

Missing core instructions, checked against bril/docs/lang/core.md. Everything else in core is covered.

• and, or
• not — unary, does not fit BinaryInstr. Needs a UnaryInstr (which could also absorb IdInstr).
• call — the biggest gap. Can be a value op or an effect op depending on whether the callee returns. Needs Program-level name resolution.
• Memory extension
• A type inference tool for Bril programs

Graphs, dominance and loops

• Dominance tree
• Dominance frontier. A node A is in DF(B) if B dominates a predecessor of A but does not strictly dominate A. A node can be in its own dominance frontier: let H be a loop header and L the latch. H dominates L, which is a predecessor of H, but H does not strictly dominate itself, so DF(H) = {H}. That is exactly why strict dominance is needed. Dominance frontiers are the join points, and where phi functions go later.
• Natural loop detection via back edges: if a node dominates one of its predecessors, that is a back edge. The LoopForest is built by backfilling from the latch. Inner loops are done first, so when an already-claimed node is reached the walk can skip to the header of the inner loop (technically its ancestor) and continue. Irreducible cycles are not detected, since the nodes stand in no dominance relationship — the algorithm just skips them and creates no loop, which is what we want.
• LoopInfo in the analysis layer, lifting loop structure back to BasicBlocks, plus helpers for preheaders, latches, exits and exiting blocks, and an isSimplified check.
• Loop simplification — a simplified loop has a preheader, a single latch, and exit blocks whose predecessors are all inside the loop.
  • Insert preheader
  • Merge latches: insert a new latch that all old latches target, and which branches back to the header
  • Dedicated exits: create new exit blocks for the exiting blocks to target, which then jump to the original exit blocks
• LICM
• Control dependence graph, which follows from postdominators and the postdominance frontier. Postdominators come from inverting the graph edges and running dominance on that, so this needs a graph transpose first.
• Loop detection via SCC and the condensed graph. Natural loops are the SCCs with a single entry, which the condensed graph makes visible. The real motivation is elsewhere though: SCC on the call graph gives an optimization order for mutually recursive functions, and SCC finds irreducible loops (two entry points via goto) that natural-loop detection misses. The tradeoff is that SCC collapses inner loops, so nesting information is lost — natural loops stay the primary representation.

SSA

• phi and undef instructions, with a phi iterator on BasicBlock and a firstNonPhi
• Phi placement from the dominance frontier, with the supporting data structures
• Renaming. This is the trickiest part, and hard to debug because only names change. See tests/ssa/loop.bril: the header defines c: bool = lt i n, and since the header is in its own dominance frontier that gets a phi — but c is not defined in entry, so naive renaming crashes there. A dead-phi problem. Variables defined in only one branch have the same issue: they still need something on entry.
• Semi-pruned SSA as the fix. A name is non-local if it is used in some block before being defined in that block — the upward-exposed uses, an approximation of liveness. Names local to a single block need no phi.
• Pruned SSA: insert a phi for v at Y only if v ∈ live_in(Y). Needs the liveness pass wired in.
• SSA verifier: no name defined twice, and for each phi labels.size() == args.size() == preds(bb).size(). There are more conditions to add.
• Right now this uses phi instructions, but basic block arguments would be worth trying as an alternative, as would Pizlo-style SSA.

Optimizations

• Trivial DCE

• Local value numbering, with copy propagation, constant folding and CSE within a block

• Liveness analysis (backward, set-union merge) on the template dataflow framework

  • Dead code elimination driven by it
  • Recheck the analysis itself

• GVN, by reimplementing LVN on top of SSA — in SSA, values are instructions, so the value table falls out naturally.

• Sparse conditional constant propagation (SCCP) — the analysis. Computes the lattice and finds non-executable edges, propagating through phi nodes.

  • The transformation on top of it: replace values that came out constant, fold the branches whose conditions are now known, and delete the blocks left unreachable.

  GVN alone misses optimizations involving phis in loop headers. Outside loops, an instruction's operands are always dominated by their definitions; a phi in a loop header is not dominated by the definition in the body, so the SSA def-use graph has cycles and a fixpoint is genuinely needed.

  SCCP handles this with two worklists: one for CFG edges already visited, one for SSA values. A lattice tracks ⊤ (nothing known yet), ⊥ (not a constant), and the constant itself. br on a known-true condition pushes only the true edge, on false only the false edge, and jmp always pushes its edge — this edge marking is the conditional part. When a value's lattice element changes, all of its uses are pushed; that def-use propagation, rather than a full re-scan, is the sparse part, and it is why a use list has to be built up front.

  Two things that are easy to get wrong:

  • Edge executability ≠ block executability. A predecessor can be live while its edge into this block is dead, because its branch folded to the other target. Phi arms must be filtered on executable.contains({pred, bb}). Using block reachability instead silently pessimises everything to ⊥.

  • Do not push both edges of a br on ⊤. Staying optimistic is what lets a branch be deleted later; pushing both immediately throws that away. Consider this, after inlining process(buf, n, state):

    int state = MODE_FAST;             // 0
    for (int i = 0; i < n; i++) {
        if (state == MODE_SLOW)        // never true
            state = MODE_RETRY;
        emit(buf[i], state);
    }

    SSA introduces state1 = phi(0, preheader, state2, latch). Pessimistic constant propagation must set state1 to ⊥, because state2 is unknown and state2 depends on state1. SCCP starts state1 at ⊤; the latch edge is not executable yet, so the meet gives Const 0. That folds the if, which makes the retry block non-executable, so state2 loses its retry arm and also meets to Const 0.

• Interprocedural constant propagation through arguments and returns (IPSCCP)

• Partial redundancy elimination (PRE)

• CFG simplification. These opportunities appear as a result of other passes — once a branch folds, whole blocks become deletable.

LLVM codegen

• Alloca-based codegen. All instructions emit correct LLVM IR.
• Function arguments: types are tracked in the IR, used to derive the correct function types, and allocas are emitted for the parameters.
• SSA codegen: use the SSA construction here and emit real phi nodes instead of allocas. The two backends can share most of their implementation — factor it into define and use, binding a Bril name to a value. For allocas, define creates the alloca and stores, use loads; for SSA, define records the value directly and use returns it.
• Reimplement LVN, then GVN, as passes on LLVM IR (after mem2reg)

Further out

• Compile to MLIR. A Bril dialect with lambdas containing closures, lowered to a core Bril dialect. Needs to handle nested lambda bodies and implicit capture of free variables.
  • Needs the memory extension first
  • Needs a fork of briltxt.py to add lambda with an instruction list as an op
  • Needs icall, a closurize instruction, and an anonymous closure type
• Alive-style verified peephole optimizations. Verify local rewrites (the LVN and DCE ones) against an SMT encoding of Bril semantics.
• BLOKE / STOKE-style superoptimizer. Stochastic search for optimal instruction sequences. Shares the SMT equivalence-checking machinery with the Alive work, so that comes first.

Reference: past CS 6120 final projects worth reading

Several got merged into the Bril repo and are readable in a checkout:

• bril/brilift — Cranelift backend. Worth reading next to src/codegen/LLVMVisitor.h to see what LLVM actually buys over a simpler codegen path.
• bril/brilirs — fast interpreter (Rust)
• bril/type-infer, bril/flat-bril, bril/fastbril, bril/brench
• "C++ Infrastructure for Bril" (2023fa blog) — someone already did cbril
• "Vectorization for Bril" (2022sp) — needs the memory extension first
• "Implementing the Polyhedral Model" (2023fa) — connects to polly/ in llvm-project

AI note

AI was used to generate test cases as .bril files.

License

MIT — see LICENSE.