High-Level Synthesis turns C into hardware, but it does so by running a FIXED sequence of optimization passes — and the order is a trap — one pass blocks another, a greedy rewrite can't be undone, so the tool reaches just one point in a vast space of equivalent circuits, usually a mediocre one, and it can't even tell which rewrite helps the hardware without slowly re-running the synthesizer; this paper (Intel) builds SEER, which sidesteps the ordering problem entirely by using an "e-graph" — a data structure that holds ALL the equivalent versions of a program at once — and "equality saturation" to keep applying every rewrite rule until nothing new appears, THEN picks the best design by a hardware cost model, so it never has to commit to a pass order; it scales this to real programs by reusing existing compiler passes as rewrites, estimating hardware cost analytically instead of re-synthesizing, and cleverly keeping multiple forms of the same code so an analysis that only works on one form can unlock a transformation while the hardware-efficient form is what gets built — reaching up to 38x the performance within 1.4x the area, and even beating designs hand-optimized by Intel hardware experts.
The argument in one glance
-
Problem
HLS optimizes by a fixed pass order — and the order is a trap
High-Level Synthesis (HLS) compiles a high-level program in C or C++ into a hardware design (RTL) for an FPGA or ASIC, so a software engineer can produce hardware without writing Verilog. To make the hardware good, HLS applies a series of OPTIMIZATION PASSES — loop transformations, arithmetic simplifications, memory optimizations. But it applies them in a FIXED, predetermined order, and that order is a trap. Optimization passes interfere: one pass can block or enable another, so the sequence you pick determines which transformations become possible. And each pass is applied GREEDILY — it commits to one rewrite and cannot undo it. So a fixed pass order walks a single path through an enormous space of equivalent hardware designs, and usually lands on a mediocre one.
-
What people did
Run a commercial HLS tool with its built-in pass pipeline
The standard approach is to run a commercial HLS tool (Stratus, Vitis, Catapult), which applies its predetermined sequence of source transformations to every input program, possibly steered by programmer pragmas, and produces RTL. It is the mature, supported path, and for programs whose ideal transformation matches the built-in order, it works well.
-
Why it fell short
One fixed order explores one path, and cannot see the hardware cost
A fixed pass order can only reach one point in the space. In the paper's motivating example, a program has two valid loop-fusion choices — fuse loops one and two, or fuse loops two and three — that are mutually exclusive: commit to one and you can never reach the other. Which is better depends on the specifics (the latencies of the functions involved), so no single fixed order is right for all programs. Worse, an HLS optimizer working at the source level cannot even TELL whether a given transformation improves the resulting hardware without slowly re-running the downstream synthesis tool to measure area and latency. So the search space is both combinatorially huge and expensive to evaluate, and current HLS tools handle it poorly — missing designs that a human expert would find, or failing to find good ones at all. The result is that the quality of an HLS design is often limited not by the algorithm but by the tool's inability to explore.
-
This paper's idea
Keep all equivalent designs at once with an e-graph, then extract the best
This paper (Intel — Cheng, Coward, Chelini, Barbalho, Drane) builds SEER, which sidesteps pass-ordering entirely using an E-GRAPH and EQUALITY SATURATION. An e-graph is a data structure that compactly represents MANY functionally-equivalent versions of a program at once, sharing structure; equality saturation grows it by applying ALL rewrite rules repeatedly until no new equivalent forms appear, and only THEN extracts the single best design by a cost model — so SEER never has to choose a pass order, it keeps every rewrite simultaneously and picks the winner at the end. The hard part is making this work at scale for real HLS: SEER reuses existing MLIR compiler passes and a data-path optimizer (ROVER) as rewrites INSIDE the e-graph (rather than reimplementing 106-plus optimizations), bridged by a small language, SeerLang; it estimates hardware cost analytically to avoid re-synthesizing every candidate; and — its deepest trick — it keeps MULTIPLE representations of the same code in one equivalence class, so an analysis that only works on one form (an affine loop index a compiler pass can analyze) can unlock a transformation while a hardware-efficient form (a cheaper shift-and-add) is what actually gets built. A hardware-aware cost model extracts the best design, verified by per-step equivalence checking. SEER reaches up to 38x the performance within 1.4x the area, and even beats designs hand-optimized by Intel hardware experts.
Why this problem is worth solving
Custom hardware is how performance keeps scaling, and HLS is what lets
software engineers produce it — but only if the tool can actually find good
designs, and today its search is crippled by how it applies
optimizations. Understanding that limitation comes first. A
HIGH-LEVEL
SYNTHESIS (HLS) compiles a high-level program (C or C++) into a
register-transfer-level hardware design for an FPGA or ASIC, applying
optimization PASSES to improve the result. The PHASE-ORDERING problem is
that these passes interfere: the order in which you apply them changes
which transformations are possible, because one pass can block or enable
another (fusing two loops may open or foreclose a later optimization). A
fixed, predetermined order — what every HLS tool uses — therefore reaches
only ONE point in the space of equivalent designs, and a pass applied
greedily commits to a rewrite it cannot undo, so there is no backtracking.
This is worse in hardware than in software for two reasons: transformations
exist at many granularities (control-flow, data-path, bit-level) that
interact, and you cannot tell whether a transformation actually helped the
HARDWARE without slowly re-running synthesis to measure area and
latency
The technique SEER brings to this is one that was designed precisely to
beat phase-ordering. An
an E-GRAPH (equivalence graph)
is a data structure that stores MANY functionally-equivalent versions of a
program compactly, by grouping equivalent expressions into equivalence
classes and sharing common sub-expressions — so the forms x-times-2 plus x,
x-shifted-left plus x, and x-times-3 can all coexist as one equivalence
class rather than three separate programs. EQUALITY SATURATION uses it to
avoid phase-ordering: instead of picking an order and greedily applying
rewrites, you apply ALL rewrite rules repeatedly, each one ADDING the new
equivalent form to the e-graph without deleting the old, growing the graph
until no new equivalences appear (saturation) or a limit is hit. At that
point the e-graph holds a huge space of equivalent programs, and a single
EXTRACTION step reads out the best one according to a cost model. The key
property is that you never commit to a transformation order: every rewrite
is kept simultaneously, and the ordering decision is replaced by choosing
the cheapest form at the very end
What people did before, and where it broke
- Commercial HLS with a fixed pass pipeline (Stratus, Vitis, Catapult). Apply a predetermined sequence of transformations, steered by pragmas. Mature and supported, but the single fixed order explores one path and cannot adapt to what a particular program’s hardware needs.
- Manual pragma tuning by experts. A hardware engineer inserts directives to guide the transformations. Can reach good designs, but is slow, specialist, and per-design, and still bounded by which transformations the tool exposes.
- Data-path-only optimizers (ROVER). Use e-graphs to optimize arithmetic data-paths for area. Effective for that slice, but they do not touch control flow (loops, conditionals), so they miss most of the performance opportunity.
- E-graph rewriting in small settings. Equality saturation had been applied to small expression-level problems, but not to large software compiler frameworks like MLIR or to whole HLS programs, because e-graphs blow up and reimplementing every optimization as a rewrite is infeasible.
- The gap. No approach explored the full space of equivalent HLS designs — across control-flow, data-path, and bit-level — at scale, with a hardware-aware cost model, without committing to a pass order. That is the gap SEER fills.
How SEER escapes the pass-ordering trap
Keep all equivalent designs in an e-graph, reuse existing passes, and extract the cheapest hardware
-
The phase-ordering trap
HLS applies optimization passes in a fixed order, and each greedy pass commits to a rewrite it cannot undo, so the tool reaches one point in a huge space of equivalent designs — and it cannot tell whether a transformation helped the hardware without slowly re-running synthesis.
-
Represent all equivalent programs in an e-graph new
SEER translates the program (from MLIR, via a bridge language SeerLang that adds a seq operator to preserve memory ordering) into an e-graph, then grows it by equality saturation — applying every rewrite rule repeatedly and adding each new equivalent form without deleting the old — so no pass order is ever chosen.
-
Reuse existing compiler passes as rewrites new
Rather than reimplement optimizations, SEER runs 106 internal data-path and gate-level rewrites directly, and orchestrates existing MLIR passes (loop fusion, unrolling, if-conversion, memory forwarding) and the ROVER data-path optimizer as DYNAMIC rewrites: match a pattern, call the external pass, validate the result, and union it back into the e-graph.
-
Keep multiple representations to resolve analysis-vs-efficiency new
A loop-fusion pass needs an affine index it can analyze, but the hardware-efficient form of that index (a shift-and-add) is not affine and would block the analysis. SEER keeps BOTH forms in the same equivalence class, so the analyzable affine form unlocks the loop transformation while the cheaper shift-and-add form remains available to extract.
-
Estimate hardware cost analytically and extract the best new
To avoid re-synthesizing every candidate, SEER approximates the scheduling of newly-generated loops from the original loops' constraints. Extraction is two-phase: first minimize the sum of pipelined-loop latencies (control path), then, for the fixed control flow, minimize circuit area via an integer-linear-programming solver (data path from ROVER).
-
Verify by per-step equivalence checking new
Because the reused passes may be unverified, SEER adds translation validation: it traces the extracted design back to the original through single rewrites, generates SystemC for each step, and formally equivalence-checks each one — building a sound chain that the optimized hardware is functionally identical to the input.
The idea
Replace the ordering decision with keeping every option and choosing at the end. The whole trouble with a fixed pass pipeline is that it commits: apply loop fusion here, and you foreclose the design where you fused differently. SEER refuses to commit. An e-graph holds every equivalent form at once, equality saturation grows that set by applying all rewrites without deleting anything, and a single extraction picks the best design according to a hardware cost model — so the question “what order of passes?” is replaced by “keep them all, then extract the cheapest.” Exploring a space of equivalent forms and selecting by cost, rather than greedily committing to one path, is the same search-over-equivalences discipline the site’s companion high-level-synthesis page uses to explore dataflow designs and the in-memory-fusion page uses when it rewrites its dataflow graph with equality-graph rules and picks the least-traffic form — and it is the same keep-options-open, decide-with-full-information instinct the autotuning and scheduling pages share. The e-graph is what makes “explore everything” cheap enough to be practical.
Reuse the existing ecosystem as composable rewrites — do not reinvent. A pure e-graph approach would require reimplementing every loop transformation and arithmetic optimization as a rewrite rule, which is infeasible for a real compiler. SEER’s scaling move is to run EXISTING tools inside the e-graph: it orchestrates MLIR’s compiler passes and the ROVER data-path optimizer as dynamic rewrites, matching a pattern, invoking the mature external pass, validating, and unioning the result back. So SEER inherits decades of compiler and hardware-optimizer engineering rather than rebuilding it. Composing existing, trusted components as building blocks instead of reinventing them is a move the site rewards throughout — the serverless-transfer and GPU-persistence pages repurpose existing hardware primitives, the FPGA-compilation page reuses the vendor synthesizer as a backend, and the companion HLS page builds on the same MLIR infrastructure. The bridge language, SeerLang, exists precisely to let two frameworks that share no representation cooperate without rewriting either.
Keep multiple representations so analysis and efficiency stop fighting. The paper’s subtlest idea exploits what an e-graph uniquely allows. Often the form a compiler ANALYSIS can reason about is not the form that makes efficient HARDWARE: a loop-fusion pass needs an affine index like three-times-i to check dependencies, but the hardware-cheap version of that index is a shift-and-add, which is not affine and defeats the analysis. In a normal compiler you must choose one form and lose the other. In an e-graph, SEER keeps BOTH in the same equivalence class, so the analyzable form unlocks the loop fusion while the efficient form remains available to extract — the fusion succeeds AND the cheap circuit gets built. Keeping two representations so you get the best of each, instead of choosing between an analysis-friendly and an efficient one, is the same refuse-the-false-choice, have-both discipline the FHE-accelerator page uses when it decouples a precision knob from the storage unit and the accelerator-companion page uses when it pairs a general ALU with specialized memory logic. The representation is not a constraint here; it is a resource you can hold several of at once.
Optimizing hardware without choosing a pass order
From a committed pass order to a searched design
Super-optimizing an HLS design with e-graph rewriting. Numbers from the paper's ASIC evaluation.
Step 1 of 5
Why a fixed order loses
A fixed pass pipeline can fuse loops one and two OR loops two and three, but not both — commit to one and the other is unreachable — and which is better depends on the hardware, which the source-level optimizer cannot see without slowly re-running synthesis. A greedy order also cannot backtrack from a bad rewrite.
the best transformation differs by program (it depends on the latencies of the functions involved), so no single order fits all current HLS tools handle this combinatorial, expensive-to-evaluate space poorly, missing designs an expert would find
Why it works
- A fixed pass order commits greedily and cannot reach mutually-exclusive transformations → an e-graph keeps every equivalent form at once and equality saturation adds rewrites without deleting → the ordering decision is deferred to a single cost-based extraction at the end.
- Reimplementing every optimization as a rewrite is infeasible → SEER runs existing MLIR passes and the ROVER optimizer as dynamic rewrites inside the e-graph → it inherits mature control-flow and data-path optimizations without rebuilding them.
- Analysis-friendly and hardware-efficient forms of an expression often conflict → keeping both in one equivalence class lets the analyzable form enable a transform while the efficient form is extracted → SEER gets the transformation AND the cheap circuit, which a single-form compiler cannot.
- Measuring each candidate’s hardware quality by re-running synthesis would be far too slow → SEER approximates loop scheduling analytically and extracts with a two-phase latency-then-area cost model → the search stays tractable while remaining hardware-aware.
- The reused passes may be unverified → SEER traces each single rewrite back and formally equivalence-checks it → the optimized hardware is provably equivalent to the input, decomposed into simple per-step checks.
What it costs (trade-offs and scope)
- E-graphs blow up, so SEER bounds the exploration. It disables exploring different loop-unroll factors by default, restricts gate-minimization rules, and approximates new loops’ scheduling from the originals rather than re-scheduling exactly — so the search is bounded and the cost estimates are approximate, and a design outside those bounds is missed.
- It optimizes what it models — power is not modeled. The cost model targets performance and area but not power, so aggressive pipelining can regress power (about 2.54x on average across benchmarks); the unmodeled dimension suffers, a direct instance of “you do not improve what you do not measure.”
- It is heavy integration machinery. SEER depends on MLIR passes, the ROVER optimizer, the egg library, and the SeerLang bridge, and targets ASICs through a commercial HLS backend — a lot of moving parts tied to that specific ecosystem and its dialects, so the numbers ride those tools.
- Verification is required and adds cost. Because the reused passes are not trusted, SEER runs a commercial formal equivalence checker on each rewrite step; the per-step decomposition keeps it tractable, but it is extra work on top of the search.
- The benefit is proportional to what the fixed order was leaving on the table. The evaluation targets programs current HLS handles poorly (8 of 19 MachSuite benchmarks plus an Intel kernel); the 38x figure is a maximum on one benchmark, the average is closer to 3x fewer cycles, and on programs HLS already optimizes well there is far less for SEER to add.
The evaluation
SEER built on MLIR, the egg library, and ROVER, targeting ASICs with a commercial HLS tool at 45nm, evaluated against vanilla commercial HLS and against ROVER (data-path only), on an Intel production resource-combining kernel plus a subset of MachSuite (matrix multiply, string matching, molecular dynamics, sorting), measuring cycles, critical path, area, and power from post-place-and-route reports and HLS co-simulation, with per-step formal equivalence checking.
Optimizing an HLS design
| Property | Fixed-pass HLS (commercial) | Data-path optimizer (ROVER) | SEER (this work) |
|---|---|---|---|
| What it explores | |||
| Phase-ordering | |||
| Reuses existing passes | |||
| Hardware awareness | |||
| Result |
Check yourself
Check your understanding
1. HLS tools apply optimization passes in a fixed order, which SEER argues is the core limitation. Predict what goes wrong, and how an e-graph fixes it.
2. A pure e-graph approach would need every loop and arithmetic optimization reimplemented as a rewrite rule — infeasible for a real compiler. Predict how SEER scales to real HLS anyway.
3. SEER keeps TWO forms of the same expression — an affine index and a hardware-efficient shift-and-add — in one equivalence class. Predict why holding both matters.
4. SEER's cost model optimizes performance and area but not power, and its results sometimes show power regressing. Predict what general lesson this illustrates.
Sources
- SEER: Super-Optimization Explorer for HLS using E-graph Rewriting with MLIR (arXiv:2308.07654) — ASPLOS 2024 (full text read via ar5iv and the author PDF).
- Author PDF — full paper with evaluation.
- ACM DL: SEER (DOI 10.1145/3620665.3640392) — published version.