Core IR and Code IR

Warning

This page describes the target architecture. The code may still differ from it.

Core IR and Code IR are the two internal representations between a checked grammar and what a backend runs or emits. This page explains why there are two, what each one is for, how Code IR is divided into the Flow, Action and Exec dialects, and how optimization works on them. It omits field tables, node inventories and call sites: the code, starting with the package comments of the IR packages, is their source of truth. The representations are internal; they are not a public API.

The whole system is in Architecture. The exact definitions are in the Core IR Specification, including the text form, which prints a module in full, the Code IR specification, which defines the module, the statements and expressions of functions, the operation kinds, dialects and stages, the Flow dialect specification, which defines the operations that say how a parser runs a rule, and the Exec dialect specification, which defines the abstract machine, every operation with its contract, the compositions and the conversion from the Flow stage, passes and printing. The reasons behind the levels are in record 062, the abstract machine in record 065, the decision to make one Code IR with dialects in record 072, and how the dialects and the conversion between the stages are defined in record 073.

Two Representations, Three Dialects

flowchart TD
  sem["Semantic model"] -->|elaborate| core["Core IR"]
  core --> p["Core passes: rewrite and analyze"]
  p --> core
  core -->|flowlower| flow["Code IR at the Flow stage"]
  flow --> fp["Flow passes: control-level decisions"]
  fp --> flow
  flow -->|vmlower| bc["Bytecode"]
  flow -->|execlower| exec["Code IR at the Exec stage"]
  comp["Compositions of the abstract machine"] --> exec
  exec --> xp["Passes: specialize, canonicalize, legalize per language"]
  xp --> exec
  exec --> out["Printers: host-language source"]
Core IR Code IR at the Flow stage Code IR at the Exec stage
Question it answers What does this rule mean? How does a parser control it? What must the abstract machine do, and how is that composed?
Operations A tree of grammar-level expressions, each carrying facts Flow and Action dialects: matching, mark and restore, expectations, captures, calls under a policy, charges, recovery, action evaluation Exec and Action dialects: operations of the abstract machine and the compositions over them
Optimized by Rewrites that are valid for any backend Control-level decisions with stated obligations Behavior-preserving passes: specializing a function for the features of a build, removing what cannot run, legalizing for a language
Knows about Input consumed, expectations, captures, failure Parser state, control flow, the features of a build (budget, Document, tracing) The abstract state of the parser (memo table, budget, ...) and the contract of each operation

Core IR is independent of the mode, of the target and of the layout of parser state. Code IR at the Flow stage is independent of how a target stores state or implements an operation, and so is the Exec stage.

The split keeps two kinds of reasoning apart. Whether a rewrite preserves what the grammar means is a question about grammars and is answered once, on Core IR, where it is easy to state. How to turn the result into fast code is a question about control and about a particular runtime, and is answered on Code IR, whose rewrites rely on the meaning that Core IR has already fixed. A new target that reuses Core IR inherits the rewrites; a change to how loops are written does not touch them.

Code IR is one representation: one structure of modules, functions, statements and expressions, one verifier, one printer and one reference interpreter. What differs between the Flow stage and the Exec stage is which dialects, the tables of operations, are allowed. Writing the base once means that action evaluation, the call protocol and the structure of functions are defined once, and that one verifier can check the relation between the stages. A set of operations is a dialect; a state of a program is a stage. "The abstract machine" is what the Exec dialect defines; "the VM" is only the bytecode interpreter.

Core IR

Core IR is a module of rules whose bodies are trees of expressions: sequences, choices, repetitions, lookaheads, literals and classes, calls to other rules, captures, and the action expressions that build values. It is elaborated once from the semantic model of the front end, and the decisions about each rule, such as which rules are memoized or value-free, are facts computed on it.

Origins

Each node and each action expression has an ID in its module, and a module built with its origin maps each ID back to the grammar expression or the action expression of the grammar that it was built from. The passes keep the IDs, so the map holds for every module of the pipeline. An analysis of a grammar, such as the complexity classifier, reasons on Core IR, which is what runs, and reads the grammar only through the origin, to quote it and to place its messages.

Effects Are Explicit

Every node carries attributes computed from its subtree: whether it can match empty input, which input can start it, and which effects it can have. The effects are what a parse can do besides returning a boolean: consume input, fail, record an expectation, write a capture, cut, recover from an error, call another rule, or raise an error that ends the parse.

Making effects explicit is what makes optimization safe to state. "This alternative can only start with a comma" is a checked fact, so a choice may skip alternatives without trying them. "This repetition has no capture and no call" lets a loop be a tight scan. A rewrite is allowed exactly when it does not change an effect that anything can observe: the input consumed, the expectations recorded at the farthest failure, the order of captures and errors.

Kinds of Node

Nodes fall into a few families: matching, combining, structure (calls, captures, scopes), control (cut, recovery, left recursion, Operators Rules), action expressions, and the optimized forms that passes introduce. The exact kinds and what each one means are defined in the Core IR Specification; a new node should fit one of the families.

What the Verifier Guarantees

The Core IR verifier checks, by default once after the last pass, that the module is well formed and that the facts on it are true. With verification after each pass requested, it also runs after every pass and names the pass that broke an invariant; see Verification Between Passes. It recomputes the attributes to compare them with the module, which is why it lives with the attribute computation in the Core IR package. It guarantees four things.

  • Referential integrity. Every call, capture and slot reference points at something that exists in the scope it names, and the call graph equals the one computed from the bodies.
  • Facts match structure. Guards, first terminals and similar attributes equal what the structure implies, so a pass cannot leave a stale fact behind.
  • Forms stay in their place. Constructs that the runtime supports only in certain positions (an Operators Rule as a whole body, a stream at the top of a start rule) appear only there, and optimized forms contain only what they can represent.
  • Types are complete in a typed module: every action expression, slot and rule value has a checked type.

The individual invariants are listed in Invariants.

Optimization

An optimization is a pass: a function from a module to a module. There are two kinds.

  • Analyses compute facts. The attributes of each node (nullability, first terminals and effects) are invariants stored on the nodes; derived results such as the call graph, rule facts and site numbers are cached by the analysis manager and shared by the passes, the linter, the complexity classifier and the generators. Analyses never change meaning.
  • Rewrites replace an expression with a cheaper one that does the same thing. Each rewrite has a precondition, the facts it needs, and an obligation, what it promises to preserve.

A rewrite is safe when its precondition is established and the replacement is indistinguishable from the original on every input: same input consumed, same value, same error, same expectations at the same positions. Preconditions are satisfied by asking the analysis manager, and a rewrite declares which analyses it preserves; every other analysis is computed again when it is next asked for. How each rewrite proves itself is written beside it, as a comment, and tested by differential runs against the reference backend, which is the oracle.

For example, replacing a choice's blind tries with guarded ones is safe because the guard equals the alternative's first terminal, the literal or class that analysis proves every match of that alternative starts with: when the guard rejects the next character, the alternative would have failed there anyway, with the same expectation. Turning a value-free repetition of a character class into a scan is safe because it consumes the same characters, writes nothing and records the same expectation when it stops.

The order passes run in, which are enabled, and how they are configured are declarations of the pipeline that the driver runs; the pass pipeline explains declared passes, the analysis manager, profiles and a flag per optimization.

Examples of Rewrites

Take a rule that reads an item and then an optional separator, where the separator is a choice between two literals. Analysis computes the first terminal of each literal, and each alternative of the choice gains a guard that is that terminal: when the guard rejects the next character, the alternative would have failed there anyway, with the same expectation. In a rule that reads a name made of letters under the atomic marker, the value-free repetition of the letter class becomes a scan. A value-free rule that matches optional whitespace is called in its value-free twin, and the twin's repetition becomes a scan over the whitespace class; the value-building sibling of the twin is unchanged.

Before analysis a node carries only whether its value is wanted and its shape; nullability, first terminals and effects are attributes that the printed module shows once analysis has run. None of these rewrites changes what any input consumes or expects.

The Flow Stage

Code IR at the Flow stage holds the body of each rule variant as operations of grammar control with structured control: variables for positions and results, labeled blocks and loops, and the operations of the Flow dialect (matching, mark and restore for backtracking, expectations, captures, rule calls under a policy, charging for budgets, recovery), with action expressions as operations of the Action dialect. It holds no host-language text. Its control is structured and nested: labeled blocks and loops are regions inside the operation that owns them, and the form that is printed and verified keeps that nesting. A pass that needs a graph view asks the analysis manager for one.

flowlower, the pass that lowers Core IR to Code IR, produces the Flow stage in one uniform shape and fails loudly on a construct it does not support rather than guess. The shape is then chosen by the Flow passes, which hold every control-level decision: call specialization, inlining, dispatch, the form of a match, removal of saves that no failure path reads, merging and threading of failure paths, canonicalization, where to charge, sharing slots between locals, and outlining. Each pass declares an obligation, the property it preserves, and the features under which it applies, and the Flow verifier checks the result, right after flowlower, again where the pipeline leaves the Flow stage, and after every pass with -verify-each: structure, variables, one runtime per function, the budget invariants, recorded reads under a Document and no in-place reads in a traced parse. The passes, their order and their obligations are listed in the pass pipeline.

A charge of one step is one reservation of one unit, so a printer that charges several steps, or the code points of a literal, with one call keeps them separate reservations: the runtime reserves a run that fits at once and, when the run does not fit, fails at the unit that does not, as the separate charges would, and reports that unit as the reservation that failed. The charge pass keeps the total charge, charges every loop iteration, charges input before examining it and never moves or merges a charge across a write to the observation or to the stream window, a callback of the caller, or a commit. An interruption therefore leaves exactly the trace events, stream deliveries, callbacks and commits that come before the reservation that failed, as the parse without the pass would.

Marks are typed locals of the Flow and Exec stages, not values that can be used once: a choice restores the same mark before each of its next alternatives, and a loop restores the mark of its iteration. Both verifiers check how marks nest: every use of a mark is dominated by its definition, and the marks of one component are used last in, first out. The preconditions of the operations that take marks (truncating the recovered errors, resetting the record of missing input, ending the innermost isolation of expectations and the like) are checks of the verifier.

Every Flow operation states its contract, its cost, the features it needs and its laws, and an immediate operand of a declared type that holds its static data (a literal, a class, a rule), while its dynamic operands are arguments. At the Exec stage each Flow operation is a primitive that each target prints in place. The conformance of a target is checked for each Flow operation: probes around every printed primitive call check that the position moves as the contract says, that the cost stays within its bound and, for reads of the input, that the result agrees with a model of the input. A backend that implements a Flow operation natively, as the VM does, is held to the same contract.

The Exec Stage

The Exec dialect has two parts. The first is the specification of the abstract machine: a set of components and registers that make up the abstract state of a parse (the memo table, the budget, the position, ...) and a set of operations, each a transition of that state with a signature, a behavior contract, a precondition, the components it reads and writes, a bound on what it charges the budget, and the features it belongs to. An operation says what happens and not how. The second part is compositions: functions in structured code over the operations, written once for every runtime: the call protocol of a rule with memoization, left-recursion growth, Operators Rules, the observation of a call, Documents and streams.

execlower, a pass of Code IR, converts the Flow stage to the Exec stage completely: each call of a Flow operation becomes a call of the primitive that stands for it, with the same arguments and immediate operand, the Flow attributes of each function become its Exec-stage attributes, and the verifier at the Exec stage checks the postcondition that no Flow operation and no Flow attribute remains. Operations of the Action dialect are legal at both stages and are kept. The rules of a grammar enter the Exec stage only this way; the compositions are written in the Exec dialect directly.

The properties that passes ask of an operation are derived from its declaration, not declared beside it, so they cannot disagree with it. An operation is pure, that is, a call of it can be removed, when it writes nothing, cannot end the parse and, while the budget is on, has no cost: a call that charges the budget is not pure in a budget-controlled build, because removing it changes where a limit interrupts. It is zero-width when it does not write the position, and infallible when it neither fails nor ends the parse. Dead-store removal, save-elide and the charge pass read these properties.

Every law of an operation is typed: it has a kind that passes read, such as equal results (equal arguments give equal results), a stable read (two reads with no write of the component between them give the same result) or the merge of two charges, and a conformance property that tests it. A pass relies only on laws of a kind it names. A law is a declared fact about results, which the conformance properties test; it never permits removing a call, which only the derived purity above does.

Two kinds of checking keep the freedom of the targets safe. A conformance suite runs sequences of operations on a reference model, written for clarity and never printed, and on an implementation, and fails on the first difference in results or in the cost charged beyond the bound, or on a change to state that the operation does not declare that it writes. Passes on the Exec stage keep a function's behavior: specializing a function for the set of features of one build turns each feature into a constant, and canonicalization removes what then cannot run, so the ordinary, budget-controlled, observed and Document variants of a mechanism are specializations of one composition. These passes depend only on the reads and writes that each operation declares, so they are shared across dialects.

How Targets Use the Result

  • The closure backend builds one closure for each node of Core IR, after the Core passes of the pipeline, and evaluates action expressions directly. It is built independently of the lowering to Code IR, so that a bug in that lowering shows up as a difference between backends.
  • The VM takes Code IR at the Flow stage: vmlower selects instructions almost one for one from Flow operations, with superinstructions for calls of compositions and for common match patterns. The compositions are native in the VM and checked by the conformance suite.
  • Generated parsers in each host language take Code IR at the Exec stage, after the dialect-independent passes and the passes of that host language that legalize and optimize it, and print it as structured source. The printers print the compositions of the runtimes too, so the rules of a generated parser and the shared mechanisms they call come from the same representation.
  • A future native-code backend would lower the Exec stage to LLVM IR.

The VM, every host language and a future native-code backend therefore take grammar code from one Code IR, so charging and the propagation of options cannot drift between two lowerings of grammar code.