spb/air Public MIT

1<!--2Project : AIR — Accounting Intermediate Representation3Author : Simon-Pierre Boucher4Contact : contact@spboucher.ai5File : llvm-architecture.md6-->78# LLVM Compiler Architecture — Research Notes910**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.1112**Sources consulted on 2026-08-05** (see full list at the end):13141. LLVM Language Reference Manual — https://llvm.org/docs/LangRef.html152. LLVM New Pass Manager — https://llvm.org/docs/NewPassManager.html163. LLVM Target-Independent Code Generator — https://llvm.org/docs/CodeGenerator.html174. Clang: Expressive Diagnostics — https://clang.llvm.org/diagnostics.html185. Chris Lattner, "LLVM", *The Architecture of Open Source Applications* — https://aosabook.org/en/v1/llvm.html1920---2122## 1. The big picture: a three-phase design with the IR as the only interface2324LLVM 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:2526- **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.27- **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.28- **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.).2930> Contrast with GCC, where backends historically walked frontend ASTs — a tangling LLVM explicitly avoids. The IR being self-contained is the whole point.3132## 2. LLVM IR structure and SSA form3334Source: LangRef (consulted 2026-08-05).3536### 2.1 Containment hierarchy3738```39Module                     — one "translation unit"; linkable with other modules40 ├── global variables      — always accessed through pointers41 ├── functions (define)    — a control-flow graph of basic blocks42 │    └── basic blocks     — straight-line instruction lists43 │         └── instructions — typed operations; each block ends with exactly44 │                            one *terminator* (br, ret, switch, ...)45 └── named metadata46```4748- **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.49- **Entry block**: the first basic block of a function has no predecessors and may not contain PHI nodes.50- **Types**: every value has a static type; every instruction result is typed. There are no untyped "bags of bytes" at the IR level.51- **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."5253### 2.2 SSA — Static Single Assignment5455LLVM 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."5657Why it matters:5859- Def-use chains are explicit and immutable → dataflow analyses become cheap and local.60- A value's provenance is unambiguous: you can always walk from any use back to the single defining instruction.61- Merging control-flow paths is explicit (PHI nodes) rather than implicit mutation.6263### 2.3 The verifier6465A 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.*6667## 3. The (new) Pass Manager6869Source: NewPassManager doc (consulted 2026-08-05).7071### 3.1 Pass kinds by IR unit7273Passes 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).7475### 3.2 Analyses vs transformations7677The design splits work into two disjoint kinds:7879- **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.80- **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.8182A 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.8384### 3.3 Pipeline construction and ordering8586- A `PassBuilder` assembles standard pipelines (e.g., `buildPerModuleDefaultPipeline()`); ordering is explicit and centrally defined, not emergent.87- Extension points (`registerPipelineStartEPCallback()`, etc.) let clients inject passes at defined seams without forking the pipeline.88- 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.89- **Pass instrumentation** hooks allow logging/timing/verification around every pass execution (this is how `-verify-each` style checking is done).9091## 4. Backends: the target-independent code generator9293Source: CodeGenerator doc (consulted 2026-08-05).9495### 4.1 Separation of algorithm and target description9697The 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:9899| Class | Describes |100|---|---|101| `TargetMachine` | Entry point; virtual accessors to everything below |102| `DataLayout` | Memory layout, alignment, pointer size, endianness (the one non-extensible class) |103| `TargetLowering` | Which IR operations the target supports natively, and how to legalize the rest |104| `TargetRegisterInfo` / `TargetInstrInfo` | Register file and instruction set |105| `TargetFrameLowering` / `TargetSubtarget` | Stack conventions; chip-specific features and latencies |106107The pipeline: **instruction selection → scheduling → SSA machine optimizations → register allocation → prologue/epilogue → late peepholes → MC emission** (assembly or object file via `MCStreamer`/`MCInst`).108109### 4.2 SelectionDAG and GlobalISel (conceptual)110111- **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.112- **GlobalISel**: a newer, more modular instruction-selection framework operating across block boundaries; same philosophy, different machinery.113114### 4.3 TableGen: declarative target descriptions115116Rather 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:117118- drastically less boilerplate; the architecture spec lives in one place;119- pattern fragments are expanded automatically, type inference propagates constraints, commutative variants are derived without duplication;120- cross-cutting changes update all backends mechanically.121122The lesson: **domain rules belong in a declarative, checkable description language, not scattered through imperative engine code.**123124## 5. Diagnostics philosophy (Clang)125126Source: clang.llvm.org/diagnostics.html (consulted 2026-08-05).127128Clang treats error messages as a first-class product:129130- **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.131- **Ranges**: the operands/expressions involved are underlined, so the shape of the problem is visible without re-reading the line.132- **Cause, not ceremony**: messages state the inferred facts that matter (e.g., the actual types of both sides of an operator), skipping the obvious.133- **Fix-it hints**: where the correction is unambiguous, the compiler proposes the exact edit (e.g., insert a missing `typename`).134- **Readable types**: typedefs are preserved, with `aka` unwrapping when helpful; template type diffing prints only what differs.135- **Context chains**: errors inside macros automatically show the instantiation chain.136137The philosophy: a diagnostic must give **location + cause + suggested fix**, in the user's own vocabulary.138139---140141## 6. Transposition to AIR142143| LLVM | AIR | Notes |144|---|---|---|145| 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) |146| SSA form + dominance verifier | Provenance graph: every amount has a single traceable origin | Invoice → Tax → Payment → FX → Settlement → Write-off |147| 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` |148| Target backends behind abstract `Target*` interfaces | ERP backends behind a common `Backend` interface | CSV, QuickBooks, Xero, Odoo, SAP; `capabilities()` ≈ `TargetLowering` legality |149| TableGen `.td` target descriptions | ALSL declarative policy/tax/norm rules | No rates or thresholds in engine code |150| Clang diagnostics | AIC compilation diagnostics | Location + cause + fix-it, pointing at the offending AIR field |151152### 6.1 LLVM IR → AIR economic events153154LLVM'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:155156- **Formal schema first** (JSON Schema as the LangRef equivalent); anything that fails validation is rejected outright, like IR the verifier refuses.157- **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.158- **`air_version` in every document**, mirroring how bitcode compatibility is managed explicitly.159- **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.160161### 6.2 SSA → single-origin amounts and the provenance graph162163SSA'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.164165### 6.3 Pass manager → AIC pipeline166167- **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.168- **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.169- **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.170- **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.171172### 6.4 Backends → ERP generators173174LLVM's split between target-independent algorithms and per-target descriptions maps directly onto AIR's `Backend` interface:175176- `capabilities()` ≈ `TargetLowering` legality declarations: which account types, tax treatments, multi-currency features, and posting granularities the target ERP supports.177- **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.178- `compile()/post()/reverse()` ≈ instruction selection + MC emission + the ability to undo: `post()` returns a `PostingReceipt` the way MC emission produces a concrete artifact.179- Development order (generic CSV first, then QBO, Xero, Odoo, SAP) mirrors how a simple reference backend validates the target-independent core before hard targets.180181### 6.5 TableGen → ALSL182183TableGen 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.184185### 6.6 Diagnostics → clang-quality compile errors186187AIC diagnostics adopt Clang's triad — **location, cause, fix-it**:188189- **Location**: JSON-pointer/path into the offending AIR document and field (`events[3].items[0].unit_price`), the accounting analogue of line+column+caret.190- **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.191- **Fix-it hints**: "jurisdiction `CA-QC` requires tax codes [GST, QST]; event declares only [GST] — add QST or change jurisdiction."192- **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).193194---195196## 7. Sources197198All consulted 2026-08-05:1992001. **LLVM Language Reference Manual** — LLVM Project. https://llvm.org/docs/LangRef.html — IR hierarchy, identifiers, SSA/dominance, three isomorphic forms, metadata, verification pass.2012. **Using the New Pass Manager** — LLVM Project. https://llvm.org/docs/NewPassManager.html — pass kinds, AnalysisManager caching, `PreservedAnalyses` invalidation, adaptors, PassBuilder pipelines, instrumentation.2023. **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.2034. **Clang: Expressive Diagnostics** — LLVM Project. https://clang.llvm.org/diagnostics.html — caret diagnostics, ranges, fix-it hints, typedef preservation, template diffing, macro expansion notes.2045. **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.205