# LLVM Compiler Architecture — Research Notes **Purpose.** AIR ("Accounting Intermediate Representation") deliberately borrows its architecture from LLVM. This document records what LLVM actually does — IR structure, SSA form, the pass manager, target backends, TableGen, and diagnostics philosophy — from primary sources, then maps each concept to AIR. **Sources consulted on 2026-08-05** (see full list at the end): 1. LLVM Language Reference Manual — https://llvm.org/docs/LangRef.html 2. LLVM New Pass Manager — https://llvm.org/docs/NewPassManager.html 3. LLVM Target-Independent Code Generator — https://llvm.org/docs/CodeGenerator.html 4. Clang: Expressive Diagnostics — https://clang.llvm.org/diagnostics.html 5. Chris Lattner, "LLVM", *The Architecture of Open Source Applications* — https://aosabook.org/en/v1/llvm.html --- ## 1. The big picture: a three-phase design with the IR as the only interface LLVM implements the classic three-phase compiler model — **frontend → optimizer → backend** — but with one decisive twist: the intermediate representation (LLVM IR) is *fully specified* and is *the only interface* between phases (Lattner, AOSA). Consequences: - **M + N instead of M × N.** Supporting M source languages and N target architectures requires M frontends plus N backends, not M×N compilers. Any frontend that emits valid IR gains every backend for free. - **Three isomorphic forms.** The IR exists as (1) in-memory data structures, (2) a dense on-disk binary ("bitcode"), and (3) a human-readable textual assembly. All three are semantically equivalent, so any stage can be serialized, inspected, diffed, and replayed. - **Everything is a library.** Optimizer passes, code generators, and analyses ship as composable libraries; clients pick which passes run and in what order. This is what allowed LLVM to be reused far beyond `clang` (JITs, GPU stacks, etc.). > Contrast with GCC, where backends historically walked frontend ASTs — a tangling LLVM explicitly avoids. The IR being self-contained is the whole point. ## 2. LLVM IR structure and SSA form Source: LangRef (consulted 2026-08-05). ### 2.1 Containment hierarchy ``` Module — one "translation unit"; linkable with other modules ├── global variables — always accessed through pointers ├── functions (define) — a control-flow graph of basic blocks │ └── basic blocks — straight-line instruction lists │ └── instructions — typed operations; each block ends with exactly │ one *terminator* (br, ret, switch, ...) └── named metadata ``` - **Identifiers**: global symbols are prefixed `@` (functions, globals), local values `%` (registers, types). Unnamed temporaries are auto-numbered (`%0`, `%1`, ...) — compilers can mint temporaries without symbol-table clashes. - **Entry block**: the first basic block of a function has no predecessors and may not contain PHI nodes. - **Types**: every value has a static type; every instruction result is typed. There are no untyped "bags of bytes" at the IR level. - **Metadata** (`!name !N`) attaches to instructions, functions, and globals to carry debug info, provenance, and optimization hints *without changing execution semantics*. This is the sanctioned channel for "extra facts about a value." ### 2.2 SSA — Static Single Assignment LLVM IR is an SSA-based representation: **each value is defined exactly once**, and every use must be *dominated* by its definition (i.e., the definition provably executes before any use on every path). The verifier rejects IR where "the definition of `%x` does not dominate all of its uses." Why it matters: - Def-use chains are explicit and immutable → dataflow analyses become cheap and local. - A value's provenance is unambiguous: you can always walk from any use back to the single defining instruction. - Merging control-flow paths is explicit (PHI nodes) rather than implicit mutation. ### 2.3 The verifier A dedicated **verification pass** checks well-formedness (typing, dominance, terminator rules) after parsing, and the optimizer re-validates before emitting bitcode. Malformed IR is a hard error, not a warning. The invariant is structural: *no pass is allowed to leave the IR in an invalid state, even transiently across pass boundaries.* ## 3. The (new) Pass Manager Source: NewPassManager doc (consulted 2026-08-05). ### 3.1 Pass kinds by IR unit Passes are stratified by the IR unit they operate on: **Module → CGSCC (call-graph SCC) → Function → Loop**. A pass declares its level; **adaptors** (`createFunctionToLoopPassAdaptor`, etc.) let an outer-level pipeline embed inner-level passes. Grouping passes at the same level improves cache locality (run all function passes on one function before moving to the next). ### 3.2 Analyses vs transformations The design splits work into two disjoint kinds: - **Analysis passes** compute facts about the IR *without modifying it* (dominator trees, alias analysis, ...). Results are **cached** by an `AnalysisManager` and reused as long as they are valid. - **Transformation passes** modify the IR. After running, each returns a **`PreservedAnalyses`** set declaring which cached analyses are still valid: `all()` (nothing changed), `none()` (invalidate everything), or a selective set. The manager invalidates accordingly; analyses may also implement custom `invalidate()` logic. A deliberate constraint: an analysis manager only serves results *at the same IR level* as the requesting pass (a function pass cannot freely poke module-level analyses) — this prevents quadratic compile times and keeps the door open for concurrency. ### 3.3 Pipeline construction and ordering - A `PassBuilder` assembles standard pipelines (e.g., `buildPerModuleDefaultPipeline()`); ordering is explicit and centrally defined, not emergent. - Extension points (`registerPipelineStartEPCallback()`, etc.) let clients inject passes at defined seams without forking the pipeline. - Pipelines are scriptable as text: `opt -passes='function(pass1,pass2),module-pass' file.ll -S` — i.e., a pass schedule is *data*, reproducible and versionable. - **Pass instrumentation** hooks allow logging/timing/verification around every pass execution (this is how `-verify-each` style checking is done). ## 4. Backends: the target-independent code generator Source: CodeGenerator doc (consulted 2026-08-05). ### 4.1 Separation of algorithm and target description The code generator splits into (a) **target-independent algorithms** (instruction selection, scheduling, register allocation, code emission) and (b) **abstract target description interfaces** that each concrete target implements: | Class | Describes | |---|---| | `TargetMachine` | Entry point; virtual accessors to everything below | | `DataLayout` | Memory layout, alignment, pointer size, endianness (the one non-extensible class) | | `TargetLowering` | Which IR operations the target supports natively, and how to legalize the rest | | `TargetRegisterInfo` / `TargetInstrInfo` | Register file and instruction set | | `TargetFrameLowering` / `TargetSubtarget` | Stack conventions; chip-specific features and latencies | The pipeline: **instruction selection → scheduling → SSA machine optimizations → register allocation → prologue/epilogue → late peepholes → MC emission** (assembly or object file via `MCStreamer`/`MCInst`). ### 4.2 SelectionDAG and GlobalISel (conceptual) - **SelectionDAG**: the IR of each block is expanded into a dataflow DAG, then *legalized* — unsupported types are promoted/expanded, unsupported operations are expanded, promoted, or handled by custom target callbacks — then pattern-matched against target instructions and scheduled. Key idea: **a generic program representation is progressively lowered until everything in it is expressible on the concrete target**, with the target declaring its capabilities rather than the core knowing about targets. - **GlobalISel**: a newer, more modular instruction-selection framework operating across block boundaries; same philosophy, different machinery. ### 4.3 TableGen: declarative target descriptions Rather than hand-writing C++ for every target detail, LLVM targets are largely described **declaratively** in `.td` (TableGen) files: registers, instruction definitions, calling conventions, addressing modes, selection patterns. TableGen compiles these records into generated C++. Benefits called out in the docs: - drastically less boilerplate; the architecture spec lives in one place; - pattern fragments are expanded automatically, type inference propagates constraints, commutative variants are derived without duplication; - cross-cutting changes update all backends mechanically. The lesson: **domain rules belong in a declarative, checkable description language, not scattered through imperative engine code.** ## 5. Diagnostics philosophy (Clang) Source: clang.llvm.org/diagnostics.html (consulted 2026-08-05). Clang treats error messages as a first-class product: - **Exact location**: line *and column*, with a caret (`^`) pointing at the precise token — "even inside of a string" — not merely where the parser gave up. - **Ranges**: the operands/expressions involved are underlined, so the shape of the problem is visible without re-reading the line. - **Cause, not ceremony**: messages state the inferred facts that matter (e.g., the actual types of both sides of an operator), skipping the obvious. - **Fix-it hints**: where the correction is unambiguous, the compiler proposes the exact edit (e.g., insert a missing `typename`). - **Readable types**: typedefs are preserved, with `aka` unwrapping when helpful; template type diffing prints only what differs. - **Context chains**: errors inside macros automatically show the instantiation chain. The philosophy: a diagnostic must give **location + cause + suggested fix**, in the user's own vocabulary. --- ## 6. Transposition to AIR | LLVM | AIR | Notes | |---|---|---| | LLVM IR (module/function/block/instruction) | AIR `EconomicEvent` documents | The universal, fully-specified exchange format; the *only* interface between understanding (LLM) and rule application (AIC) | | SSA form + dominance verifier | Provenance graph: every amount has a single traceable origin | Invoice → Tax → Payment → FX → Settlement → Write-off | | Pass manager (analysis + transformation passes) | AIC pass pipeline: validation, tax, FX, fraud, approval, optimization | Balance invariant `Assets = Liabilities + Equity` checked after every pass, like `-verify-each` | | Target backends behind abstract `Target*` interfaces | ERP backends behind a common `Backend` interface | CSV, QuickBooks, Xero, Odoo, SAP; `capabilities()` ≈ `TargetLowering` legality | | TableGen `.td` target descriptions | ALSL declarative policy/tax/norm rules | No rates or thresholds in engine code | | Clang diagnostics | AIC compilation diagnostics | Location + cause + fix-it, pointing at the offending AIR field | ### 6.1 LLVM IR → AIR economic events LLVM's central bet — a **well-specified IR that is the only interface** — is exactly AIR's bet. An `EconomicEvent` is the common currency between M ingestion frontends (invoice OCR, email, bank feeds, POS, APIs, each possibly LLM-driven) and N accounting backends (ERPs and reporting frameworks): **M + N adapters instead of M × N point-to-point integrations**. Direct implications to adopt: - **Formal schema first** (JSON Schema as the LangRef equivalent); anything that fails validation is rejected outright, like IR the verifier refuses. - **Isomorphic forms**: a canonical serialized form (JSON/YAML documents at rest), an in-memory typed object model (Pydantic/Rust types), and a human-readable rendering — all provably equivalent, so any stage of compilation can be dumped, diffed, and replayed. - **`air_version` in every document**, mirroring how bitcode compatibility is managed explicitly. - **Metadata channel**: OCR scores, LLM model/confidence, `reasoning_hash`, policy version, and approver live in `meta`, exactly as LLVM metadata carries provenance *without affecting semantics* — the compiler's output must be identical whether or not metadata is present (determinism), while remaining fully traceable. ### 6.2 SSA → single-origin amounts and the provenance graph SSA's rule — *each value defined exactly once, every use dominated by its definition* — transposes to money: **every monetary amount in the system has exactly one defining node in an immutable provenance graph**, and any derived amount (a tax line, an FX-converted total, a settlement allocation, a write-off) must reference the node it was derived from. "Dominance" becomes: *an amount cannot be consumed by a downstream step (Payment, Settlement) before the step that defines it (Invoice, Tax) exists in the graph.* An AIR verifier — the analogue of LLVM's verification pass — rejects any compilation unit containing an amount with zero or multiple origins, a dangling reference, or a use-before-definition, with the same hard-error posture: malformed AIR never enters the pipeline. Like PHI nodes making control-flow merges explicit, merges of money (netting, batch settlement of many invoices by one payment) are explicit graph nodes, never in-place mutation. ### 6.3 Pass manager → AIC pipeline - **Stratified pass kinds**: LLVM's Module/CGSCC/Function/Loop levels map to AIR scopes — entity-wide passes (period close, reconciliation), batch passes (fusion, netting, duplicate detection), and per-event passes (validation, tax, FX, classification) — with adaptors to run event-level passes inside batch pipelines. - **Analyses vs transformations**: AIC should separate *analyses* (duplicate-hash index, FX rate table lookup, policy applicability, running trial balance) from *transformations* (adding tax lines, reclassifying Expense→Asset, generating reversals). Analyses are cached by an analysis manager and invalidated via a `PreservedAnalyses`-style declaration when a transformation touches the events they cover — this is what makes **incremental recompilation** (recompile only the delta when an invoice changes) tractable. - **Explicit, scriptable ordering**: the pipeline (OCR → Classification → Tax → FX → Fraud → Approval → Optimizations → Posting) is defined centrally by a PassBuilder equivalent and expressible as data (versioned config), with extension points instead of ad-hoc insertion. - **Verify-each invariant**: LLVM instrumentation can run the verifier after every pass; AIC makes this mandatory, not optional — **`Assets = Liabilities + Equity` (and per-document debit=credit) is checked after every pass**, and any violation aborts compilation with a precise diagnostic. No pass may break the invariant even transiently across pass boundaries. ### 6.4 Backends → ERP generators LLVM's split between target-independent algorithms and per-target descriptions maps directly onto AIR's `Backend` interface: - `capabilities()` ≈ `TargetLowering` legality declarations: which account types, tax treatments, multi-currency features, and posting granularities the target ERP supports. - **Legalization** ≈ lowering a compiled journal to what the target can express: if an ERP can't represent a compound entry, expand it into multiple simple entries; if it lacks a dedicated tax field, promote tax to explicit journal lines — the core never special-cases ERPs; each backend declares and handles its own gaps, exactly like LegalizeOps expansion/promotion/custom hooks. - `compile()/post()/reverse()` ≈ instruction selection + MC emission + the ability to undo: `post()` returns a `PostingReceipt` the way MC emission produces a concrete artifact. - Development order (generic CSV first, then QBO, Xero, Odoo, SAP) mirrors how a simple reference backend validates the target-independent core before hard targets. ### 6.5 TableGen → ALSL TableGen is the strongest single precedent for ALSL: **all target-specific facts live in declarative, versioned `.td` descriptions compiled into the engine, never hand-coded in the core**. For AIR: every tax rate, capitalization threshold, jurisdiction rule, and accounting-policy choice lives in ALSL policies (versioned, testable, diffable), and the AIC engine contains zero fiscal constants. TableGen's derived conveniences (pattern expansion, type inference, auto-derived variants) suggest ALSL should support rule composition and inheritance (e.g., a `CA-QC` policy extending a `CA` base) rather than copy-paste rules. Starting ALSL as a constrained YAML subset before a full DSL parallels how TableGen is a small language with generated artifacts, not a general-purpose one. ### 6.6 Diagnostics → clang-quality compile errors AIC diagnostics adopt Clang's triad — **location, cause, fix-it**: - **Location**: JSON-pointer/path into the offending AIR document and field (`events[3].items[0].unit_price`), the accounting analogue of line+column+caret. - **Cause with inferred facts**: state what the compiler actually computed, e.g. "entry unbalanced by 0.01 CAD: debits 1150.00, credits 1149.99 — after Tax pass (QST rounding)" — the analogue of printing the inferred operand types. - **Fix-it hints**: "jurisdiction `CA-QC` requires tax codes [GST, QST]; event declares only [GST] — add QST or change jurisdiction." - **Context chains**: like macro-expansion notes, a diagnostic on a derived amount shows its provenance chain (which pass, which ALSL policy and version, which source document and OCR/LLM confidence produced the value). --- ## 7. Sources All consulted 2026-08-05: 1. **LLVM Language Reference Manual** — LLVM Project. https://llvm.org/docs/LangRef.html — IR hierarchy, identifiers, SSA/dominance, three isomorphic forms, metadata, verification pass. 2. **Using the New Pass Manager** — LLVM Project. https://llvm.org/docs/NewPassManager.html — pass kinds, AnalysisManager caching, `PreservedAnalyses` invalidation, adaptors, PassBuilder pipelines, instrumentation. 3. **The LLVM Target-Independent Code Generator** — LLVM Project. https://llvm.org/docs/CodeGenerator.html — codegen phases, abstract target classes, SelectionDAG legalization, GlobalISel, TableGen-driven target descriptions, MC layer. 4. **Clang: Expressive Diagnostics** — LLVM Project. https://clang.llvm.org/diagnostics.html — caret diagnostics, ranges, fix-it hints, typedef preservation, template diffing, macro expansion notes. 5. **Chris Lattner, "LLVM"**, in *The Architecture of Open Source Applications*, vol. 1. https://aosabook.org/en/v1/llvm.html — three-phase design, M+N retargetability, IR as sole fully-specified interface, library-based modularity.