Brummel/Aura

Fork 0

Table of Contents

Graph Compilation and Behaviour-Preserving Optimization

Graph-as-data to flat instance: the compilation

"No recompile" is two different statements

Determinism as the licence to rewrite
Classical optimizations on a dataflow graph

Common-subexpression elimination (CSE)
Dead-code / dead-node elimination (DCE)
Loop-invariant code motion over a parameter sweep
How the optimizations stack

Why a flat, inspectable representation is the precondition
References

Compilation, IR, and lowering
Behaviour preservation as the correctness criterion
Classical optimizations

Graph Compilation and Behaviour-Preserving Optimization

Constructing a runnable computation graph from a higher-level description is profitably viewed as a compilation: a parameter-generic graph specification is lowered, in well-defined stages, into a concrete, flat, executable instance. Once a dataflow graph is treated as inspectable data rather than an opaque black box, the same family of transformations that an optimizing compiler applies to instruction streams — common-subexpression elimination, dead-code elimination, loop-invariant code motion — applies to the graph, and for the same reason. This page describes the compilation pipeline, the correctness criterion that licenses every rewrite (behaviour preservation, made decidable by determinism), the classical optimizations and how they map onto a dataflow graph, and why a flat, graph-as-data intermediate representation is the precondition for any of it.

Markers: [L] law/exact, [C] convention, [CORR] corrected.

Graph-as-data to flat instance: the compilation

A parameter-generic graph specification (a graph template) describes a topology with free numeric parameters (window lengths, thresholds, buffer depths) and free input roles (which streams feed which nodes), but is not yet runnable: buffers are unsized, the input bindings are symbolic, and nested sub-graph abstractions are still folded as named groupings. Producing something executable from it is a translation between two representations — the textbook definition of compilation, where a source representation is lowered into a target representation conducive to execution. The target here is a concrete, runnable instance.

A spec is compiled, not interpreted, into a flat instance that is then the target of behaviour-preserving optimization.

flowchart LR
  spec["parameter-generic graph spec"] -->|"bind params, data, seed"| inline["inline nested composites"]
  inline --> flat["flat index-wired graph"]
  flat --> passes
  subgraph passes["behaviour-preserving passes"]
    cse["common-subexpression elimination"]
    dce["dead-node elimination"]
    hoist["sweep-invariant hoisting"]
  end
  passes --> frozen[("frozen runnable instance")]

The lowering binds three things and fixes the rest:

Parameters — every free numeric parameter receives a concrete value, which both configures node behaviour and sizes node state. Buffer and window sizes are derived once parameters are known; this is a static, graph-level property — in synchronous dataflow, where "the number of tokens read and written by each process is known ahead of time," a static schedule can be found such that "channels have bounded FIFOs," i.e. the channel buffer sizes are fixed by analysis of the graph rather than discovered at run time [synchronous dataflow]. [C]
Data and seed — the concrete input streams are bound to the symbolic input roles, and any stochastic element is pinned by a seed so the instance is reproducible (see Determinism and Reproducibility). [C]
Topology — fixed: the set of nodes and edges no longer changes. A parameter never adds or removes a node; a change of topology is a different template, not a different parameter set. [C]

Two further lowering steps make the result analysable:

Inlining of nested sub-graphs. A composite — a named sub-graph used as a reusable building block — is an authoring-level convenience, not a runtime object. Compilation inlines it: the composite boundary is dissolved and its internal nodes are spliced directly into the enclosing graph. This mirrors inline expansion in a compiler, which "replaces a function call site with the body of the called function." Crucially, inlining is an enabling transformation: once a body is expanded in the context of its use site, "it may be able to do a variety of transformations that were not possible before" — dead-code elimination, loop-invariant code motion, constant propagation [inline expansion]. [L]
Lowering to a flat, index-wired representation. The final instance is a single flat graph wired by raw integer index rather than by name. Names survive, if at all, only as non-load-bearing debug symbols. This flat form is the intermediate representation that optimization passes operate on (see the last section). [C]

"No recompile" is two different statements

A persistent source of confusion: re-deriving an instance for a new parameter set is not a source or native rebuild.

Code recompilation rebuilds the native artifact from source text — slow, and unnecessary when only parameters change. [L]
Graph recompilation re-runs the cheap graph-lowering above to produce a fresh instance from the already-built template. This is the inner loop of a parameter sweep and costs a graph traversal, not a toolchain invocation. [C]

Stating "no recompile per parameter set" should always be read in the first sense (no native rebuild); a sweep still performs the second kind of (cheap) re-compilation per point. Conflating the two overstates the cost of exploring a parameter space. [C]

Determinism as the licence to rewrite

Every transformation in this pipeline is a program transformation: "any operation that takes a computer program and generates another program" [program transformation]. A transformation is valid — permitted — exactly when it is behaviour-preserving: "the transformed program is required to be semantically equivalent to the original, relative to a particular formal semantics" [program transformation]. [L] An optimizing compiler is constrained the same way: its transformations "produce semantically equivalent code optimized for some aspect" [optimizing compiler]. [L]

The sharp formal version is observational equivalence: two program phrases are observationally equivalent if, in any context, they give rise to the same observations — one cannot distinguish them no matter what context they are placed in. Semantic preservation is "the standard semantic preservation property required in source-to-source program rewriting, optimizing compilation, equivalence verification" [semantics-preserving transformations]. [L]

The catch is that "same observable output" must be decidable for a rewrite to be applied safely, and this is where determinism earns its keep:

Referential transparency is the property that "replacing a subexpression with another one that denotes the same value does not change the value of the expression" [referential transparency]. [L] It "allow[s] the programmer and the compiler to reason about program behavior as a rewrite system" and is precisely what enables "memoization, common subexpression elimination, lazy evaluation, constant folding, parallelization" [referential transparency]. [L]
A deterministic node is referentially transparent by construction: same inputs and same bound parameters produce the same output, every time. Therefore "is the result the same?" reduces to "are the operator, parameters, and inputs the same?" — a structural check on the graph, not a semantic theorem to prove per case. [L]
Two computations with no shared mutable state are independent and may be reordered or run in parallel without changing the result — the same property that makes disjoint simulations concurrently executable underlies the safety of these rewrites. See Determinism and Reproducibility. [L]

Without determinism, "same result" is undecidable in general, and the rewrites below would be unsound. Determinism is therefore not merely a reproducibility nicety; it is the enabling precondition for behaviour-preserving optimization of the graph. [C]

Classical optimizations on a dataflow graph

The three workhorse optimizations of classical compilers transfer directly to a dataflow graph. Each is defined below from compiler theory, then mapped onto graph nodes and edges.

Common-subexpression elimination (CSE)

Definition. CSE "searches for instances of identical expressions (i.e., they all evaluate to the same value), and analyzes whether it is worthwhile replacing them with a single variable holding the computed value" [CSE]. [L] An expression is available at a point if every path to that point already evaluates it with no intervening change to its operands [CSE]. [L] CSE comes in local (within a single basic block) and global (whole-procedure) variants [CSE]. [L]

On the graph. Two sub-computations are identical when they have the same operator, the same bound parameters, and the same input edges. Such duplicate sub-graphs are merged into one node whose single output fans out to all former consumers. The redundant computation is performed once and shared, so reusing a building block (a moving average, a normalization) many times costs no redundant compute. [C] Because dataflow nodes are deterministic, syntactic identity (same operator + params + inputs) already implies value identity — the availability condition is satisfied structurally. [L]

Value-equivalence beyond syntax. Lexical CSE matches only textually identical expressions; global value numbering (GVN) instead "tries to determine an underlying equivalence" by assigning the same value number to expressions that compute the same value, and so "sometimes helps eliminate redundant code that common subexpression elimination (CSE) does not" [value numbering]. [L] In production compilers GVN "eliminate[s] fully and partially redundant instructions" and also performs redundant load elimination [LLVM passes]. [L] On a graph, GVN-style reasoning can unify nodes that are not byte-identical but provably compute the same stream (e.g. two differently-ordered but commutative reductions). [C]

Dead-code / dead-node elimination (DCE)

Definition. DCE removes "code that does not affect the program results" [DCE]. [L] It covers two distinct categories: unreachable code (can never execute) and dead stores — "code that only affects dead variables (written to, but never read again)" [DCE]. [L] The two are found by different analyses: unreachable code by control-flow reachability, dead computations by live-variable / data-flow analysis [DCE]. [L] Iterative variants re-check the inputs of just-removed instructions to see if they have become newly dead [LLVM passes]. [L]

On the graph. A node is dead if its output reaches no observable output — that is, no sink. Liveness propagates backward from sinks: mark every sink live, then mark live any node feeding a live node; everything left unmarked is dead and is dropped. This is exactly backward live-variable propagation over the DAG. [C] The reduction can cascade: removing one dead node may render its sole upstream producer dead in turn — the iterative re-check above. [L]

The side-effect caveat — never eliminate a sink. DCE is sound only because it removes code whose results are unused; code with observable side effects must be preserved. Eliminating a binding is safe only when the compiler can establish it has no side effect; the conservative rule is to preserve any "code with observable behavior" — code that "[m]ust [be] preserve[d] despite no apparent data usage," including I/O and other externally visible operations — so semantics are not changed by the removal [DCE side effects]. [C] A sink is the observable effect — it records output into the result registry — so a sink is never dead, even if nothing downstream reads it, and is never eliminated. Liveness is defined relative to the sinks; the sinks are the roots of the live set, not candidates for removal. [C] Eliminating a sink because "nothing consumes its output" is the classic DCE bug: confusing a value-producing node with an effect-producing one.

Loop-invariant code motion over a parameter sweep

Definition. Loop-invariant code motion (LICM, "hoisting") moves a computation out of a loop when it "produces identical results regardless of which iteration executes it"; the condition is that "all reaching definitions for the operands ... are outside of the loop," in which case "the expression can be moved out of the loop" to before the loop entry [LICM]. [L] The payoff: hoisted code "is executed less often" [LICM]. [L] In a production compiler the LICM pass "attempt[s] to remove as much code from the body of a loop as possible ... by hoisting code into the preheader block" [LLVM passes]. [L]

The "loop" in a sweep. A parameter sweep runs the same graph template many times, once per value of a swept parameter — the loop body is one graph evaluation, the loop variable is the swept parameter. The graph then partitions in two:

The sweep-invariant frontier: every node that does not depend on the swept parameter and whose inputs are all themselves sweep-invariant. By the LICM condition (all reaching definitions outside the loop), this sub-graph computes the same streams at every sweep point. [L]
The parameter-dependent suffix: the swept node and everything transitively downstream of it.

The invariant sub-graph is computed once and its result is shared read-only across all sweep points; only the dependent suffix re-runs per point. [C] This is LICM with the sweep as the loop: the shared prefix is "hoisted" out of the per-point work. It composes with CSE across the family of instances — the invariant frontier is a common sub-expression shared by every member of the sweep, computed once and fanned out (cross-link Backtesting Engine Architecture for how a sweep family is orchestrated). [C]

A subtlety inherited from LICM: hoisting is only sound when the moved work is genuinely invariant. Mis-classifying a parameter-dependent node as invariant would share a wrong result across points — the analogue of LICM's safety conditions, where a computation must be proven invariant (and side-effect-free / safe to speculate) before it is moved [LICM]. [L]

How the optimizations stack

These passes reinforce one another, which is why compilers run them as a pipeline:

Inlining first dissolves composite boundaries so that duplicate building blocks inside different composites become visible to CSE [inline expansion]. [L]
CSE / GVN then merges the now-visible duplicates. [C]
DCE prunes whatever no longer reaches a sink (including nodes orphaned by a merge). [C]
LICM over the sweep hoists the surviving invariant frontier out of the per-point loop. [C]

SSA-style intermediate forms make this stacking cheap: "most optimizations can be adapted to preserve [SSA] form, so that one optimization can be performed after another with no additional analysis" [SSA]. [L] A dataflow DAG with single-output nodes and explicit input edges is already close to SSA in spirit — each node defines one value, used by its consumers — which is part of why these passes port over so directly. [C]

Why a flat, inspectable representation is the precondition

None of the above is possible against an opaque sub-engine. Every one of these analyses is a whole-graph query:

CSE/GVN must find identical sub-computations across former composite boundaries — it has to see inside them.
DCE must trace liveness backward from every sink through the entire graph.
LICM over a sweep must identify the invariant frontier, which requires knowing the full dependency structure and which nodes touch the swept parameter.

All three are cross-boundary analyses, and all three demand that the graph be available as inspectable data. This is the role of an intermediate representation: "the data structure or code used internally by a compiler ... designed to be conducive to further processing, such as optimization and translation," and required to represent the program "without loss of information" [IR]. [L] A graph-based IR exists precisely so that flow analysis and re-arrangement can be performed before execution [IR]. [L]

The streaming-systems analogue is the split between a logical graph and a physical graph: the logical graph "[r]epresents the high-level structure defined by the user's code or query," and an optimizer/planner compiles it into the physical graph — "[t]he detailed execution plan generated by the system's optimizer and planner" — a step that, as the source puts it, "might involve fusing operators, reordering operations, choosing optimal join strategies, or determining appropriate state backends" [dataflow graph]. [C] The parameter-generic template is the logical graph; the flat, index-wired instance is the physical graph; the optimizer in between is exactly the pass pipeline above. [C]

The design consequence is decisive:

A flat, graph-as-data instance exposes the whole topology to analysis, so CSE, DCE, and sweep-level LICM are all available. [C]
An opaque sub-engine boundary — a node implemented as a black box that the host graph cannot see into — forecloses every cross-boundary optimization: duplicates inside it cannot be merged with duplicates outside it, its internal dead nodes cannot be pruned by the host, and it cannot participate in the invariant-frontier computation. The boundary is a wall to analysis. [C]

This is why inlining composites down to a single flat representation is not cosmetic: it is the step that creates the analysable IR. The flat graph is the object the optimizer rewrites; behaviour preservation (grounded in determinism) is the correctness invariant the rewrites must respect; and the columnar data layout of the streams flowing along its edges is what makes the surviving, optimized computation fast to execute. The outputs that any of this is allowed to change are exactly the sink-recorded streams — see Metric Catalogue and Metric Verification Log for what those observable outputs are and how their invariance under optimization is checked.

References

Compilation, IR, and lowering

Behaviour preservation as the correctness criterion

Classical optimizations

Home

Backtesting Engine Architecture

Strategy Analysis & Validation