Target-Aware Implementation of Real Expressions

Paper: Target-Aware Implementation of Real Expressions
Reviewer: The Guardian

---

Summary

The authors present Chassis, a numerical compiler designed to generate target-specific implementations of real-valued expressions, optimizing for both performance and numerical accuracy. The core contribution is a novel compilation strategy that combines accuracy-aware term rewriting (similar to tools like Herbie) with target-aware instruction selection. This is achieved through a new algorithm, "instruction selection modulo equivalence," which operates on an e-graph of mixed real- and floating-point expressions. The system is guided by a target description language that specifies available operators, their real-number semantics (desugarings), and their costs. The authors evaluate Chassis across 9 distinct targets (ISAs, languages, libraries) on 547 benchmarks, claiming superior Pareto frontiers for accuracy and performance compared to both the traditional compiler Clang and the numerical compiler Herbie.

Strengths

1. The fundamental premise of unifying target-aware instruction selection with accuracy-driven numerical rewriting is compelling and directly addresses a significant, acknowledged gap in the compiler toolchain.
2. The "operator" abstraction, which separates a floating-point operation from its real-number denotation, is a clean and powerful conceptual model. It provides a principled foundation for applying mathematical rewrites to expressions that will eventually be lowered to diverse, target-specific machine operations.
3. The evaluation is commendably broad, covering a diverse set of 9 targets and a large suite of 547 benchmarks. This provides substantial evidence for the general applicability of the proposed framework.

Weaknesses

My primary concerns with this work center on the fragility of its foundational cost model, the methodological soundness of its comparison to prior work, and the unexamined limitations of its core optimization algorithm.

1. Critically Oversimplified Cost Model: The entire optimization process, from the cost-opportunity heuristic (Section 5.2) to the final typed extraction (Section 5.1), is predicated on a cost model that is demonstrably inadequate for modern hardware. The use of a single, static scalar cost per operator (Figure 3, page 5) ignores critical performance factors such as instruction latency vs. throughput, pipeline dependencies, port contention, and memory access patterns. The authors themselves provide evidence of this model's weakness in Figure 10 (page 11), where the correlation between estimated cost and actual run time is weak, with numerous significant outliers. Attributing these discrepancies to "denormal numbers" or "cache effects" is an insufficient defense. A system that claims to generate high-performance code must be built on a more faithful performance model; without one, any claims of producing "optimal" or even "better" code are unsubstantiated.

2. Unsound Comparison with Herbie: The evaluation against Herbie (Section 6.3) suffers from a significant methodological flaw. The authors evaluate Herbie's target-agnostic output by "desugaring" or porting it to the target platform (e.g., replacing fma with x*y+z). This does not compare Chassis against Herbie; it compares Chassis against a simplistic port of Herbie's generic output. A fair comparison would require Herbie to be aware of the target's constraints from the outset. Since Herbie is not designed for this, the comparison fundamentally pits a target-aware tool against a target-agnostic one on its home turf. The subsequent claims of performance improvement are therefore unsurprising and potentially misleading.

3. Unacknowledged Failure Modes of the Core Algorithm: The paper presents instruction selection modulo equivalence as its key technical advance. However, there is clear evidence that this heavyweight technique has significant practical limitations. In the Quadratic Formula case study (page 11), the authors admit, "Missing simplifications often indicate that resource limits were hit during equality saturation." More importantly, the evaluation against Herbie explicitly concedes that "Chassis fails to find similar programs to the highest-accuracy programs that Herbie finds in a handful of benchmarks (19 of 547, about 3.5% of the total)" (page 10). This is a critical finding. It suggests that for the most challenging numerical problems, the complexity of the mixed real-float e-graph leads to search termination before the most accurate rewrites can be found. This limitation is not adequately explored and challenges the narrative that Chassis strictly dominates previous approaches.

4. Heuristic-Driven Search without Sensitivity Analysis: The system relies on a "cost opportunity heuristic" to guide its iterative search (Section 5.2). The design of this heuristic appears reasonable, but its behavior is not analyzed. How sensitive is the final output quality to the specific rewrite rules used in this heuristic's lightweight pass? What happens when this heuristic makes a locally optimal but globally suboptimal choice early in the search? Without an ablation study or sensitivity analysis, this core component remains a black box, making it difficult to assess the robustness of the overall system.

Questions to Address In Rebuttal

The authors should address the following points in their rebuttal:

1. Regarding the cost model: How can you justify that the optimization process yields meaningful results when it is based on a cost model that Figure 10 shows to be a poor predictor of actual performance? How would your system's decisions change if it used a more sophisticated model that accounted for instruction throughput and pipeline dependencies?
2. Regarding the Herbie comparison: Please defend the claim that your evaluation methodology is fair. How can you be certain that the performance gap you report is not simply an artifact of your process for porting Herbie's output, rather than a genuine advantage of Chassis's synthesis capability?
3. Regarding algorithmic limits: What are the specific resource limits (e.g., e-node count, timeout) being hit during equality saturation? Can you provide a more detailed analysis of the 19 benchmarks where Herbie produces a more accurate result? Is the failure to match Herbie a fundamental limitation of the mixed real-float e-graph approach, or simply a matter of providing more time and memory?
4. Regarding the guiding heuristic: Can you provide evidence that your cost-opportunity heuristic is robust? For instance, what is the impact on the final Pareto curve if a subset of the "simplifying" rewrite rules used by the heuristic is removed?

Review Form: The Synthesizer

---

Summary

This paper presents Chassis, a novel compiler framework designed to bridge the gap between traditional, target-aware compilers (like Clang) and target-agnostic numerical compilers (like Herbie). The central problem it addresses is the increasingly difficult task of generating code for real-number expressions that is both highly performant and numerically accurate on heterogeneous hardware.

The core contribution is a unified approach that performs accuracy-improving rewrites and target-specific instruction selection within a single optimization framework. This is enabled by two key ideas: (1) a target description language that defines available hardware/library operators in terms of the real-number expressions they approximate, along with their costs and accuracies; and (2) a novel "instruction selection modulo equivalence" algorithm. This algorithm uses equality saturation on a mixed representation of real-number and floating-point expressions within an e-graph, allowing it to simultaneously explore mathematical transformations and target-specific lowering choices.

The authors evaluate Chassis on a diverse set of 9 targets and show that it consistently finds better Pareto-optimal trade-offs between performance and accuracy than both Clang (with and without fast-math) and Herbie, demonstrating the value of this synthesized approach.

Strengths

1. Insightful and Powerful Synthesis of Fields: The paper's primary strength is its conceptual contribution. For years, the compiler community and the numerical analysis/synthesis community have largely worked in parallel on the problem of floating-point code. Traditional compilers know the machine but are naive about numerical semantics (offering only the blunt instruments of strict preservation or "fast-math"). Numerical tools know the mathematics but are naive about the target machine. Chassis provides an elegant and effective unification of these two worlds. This reframing of the problem is a significant intellectual contribution.

2. A Compelling Core Abstraction: The "operator" abstraction, which links a concrete, target-specific floating-point operation to its real-number denotation (its "desugaring"), is the technical key that unlocks the entire system. Building the optimization pass (Section 5.1, page 6) around an e-graph that can represent both the real-number semantics and the target-specific floating-point implementations is a powerful idea. It allows the system to reason about correctness at the level of mathematics while reasoning about cost at the level of the machine.

3. Strong and Broad Empirical Evidence: The evaluation is thorough and well-designed. By testing on 9 distinct targets—ranging from low-level ISAs (AVX) to high-level languages (Julia, Python) and specialized libraries (fdlibm, vdt) as shown in Figure 6 (page 8)—the authors convincingly demonstrate the generality and adaptability of their framework. Comparing against both a state-of-the-art traditional compiler (Clang) and a state-of-the-art numerical compiler (Herbie) provides a clear and persuasive case for the superiority of the unified approach. The results in Figure 8 (page 9) are particularly compelling.

4. High Potential for Impact: This work is incredibly timely. With the proliferation of specialized accelerators, low-precision numeric types in machine learning, and complex math libraries, the need for automated tools that can navigate the accuracy/performance landscape is acute. Chassis provides a principled and extensible framework for tackling this challenge, potentially influencing the design of future compilers for scientific computing, HPC, and AI/ML domains.

Weaknesses

While this is an excellent paper, there are areas where the approach's limitations and future challenges could be explored further. My comments are not intended to diminish the contribution but to contextualize it and point toward future avenues.

1. Simplicity of the Performance Model: The paper rightly acknowledges in Section 7 (page 11) that the cost models are relatively simple. They are based on summing the scalar costs of operators and handling conditionals in one of two fixed styles. Modern high-performance architectures, however, have deeply complex performance characteristics governed by instruction-level parallelism, memory latency/throughput, cache effects, and pipeline hazards. The moderate correlation and visible outliers in Figure 10 (page 11) suggest that this simple model is a first-order approximation. While sufficient to prove the paper's point, it is also the component most likely to need significant enhancement for generating truly optimal code on complex targets.

2. The Target Description Bottleneck: The power of Chassis is predicated on the existence of a high-quality target description. While the authors discuss auto-generation of costs and linking to emulated implementations (Section 4.2, page 5), the process of accurately characterizing a novel piece of hardware—especially one with esoteric, approximate instructions—remains a non-trivial expert task. The success of the approach in the wider world will depend on the community's ability and willingness to create and maintain these descriptions, which represents a potential adoption hurdle.

3. Scalability of the Search: The combined search space of mathematical rewrites and instruction choices is enormous. The paper notes that Chassis sometimes fails to match Herbie's best accuracy (Figure 9, page 10), attributing this to resource limits in the more complex, mixed e-graph saturation. This hints at potential scalability challenges. While the heuristics for guiding the search are clever, the fundamental complexity may limit the applicability of this heavyweight optimization to very large or complex functions without further innovations in search-space pruning or guidance.

Questions to Address In Rebuttal

1. Regarding the performance model, could you elaborate on the system's sensitivity to cost inaccuracies? For example, how robust is the Pareto frontier generation if the relative costs of division vs. reciprocal approximation are significantly mis-estimated? Does the framework offer hooks for plugging in more sophisticated, non-linear performance models in the future?

2. The case studies in Section 6.4 (page 10) are illustrative. In the Quadratic Formula example, Chassis produces an AVX implementation that includes a redundant multiplication. The paper notes this is likely due to resource limits during saturation. This seems to be a key trade-off: the unified search is powerful but may be too expensive to run to completion. Could you comment on this trade-off and whether there are plans for more aggressive heuristic pruning to allow the search to proceed further on the most promising paths?

3. Looking at the broader context, how do you envision this technology being integrated into a mainstream compiler like LLVM? Does the mixed real/float representation necessitate a new IR, or could this be implemented as a pass that operates on a high-level IR (like MLIR) before the standard lowering and instruction selection phases?

Review Form: Innovator (Novelty Specialist)

Summary

The paper presents Chassis, a numerical compiler that aims to unify two distinct lines of work: target-aware optimization from traditional compilers and accuracy-aware term rewriting from numerical compilers. The central thesis is that by co-designing these two aspects, one can generate code that is superior on the accuracy-performance Pareto frontier compared to systems that handle them separately.

The claimed novelty rests on a core algorithm the authors term "instruction selection modulo equivalence." This is realized by performing equality saturation on a mixed-representation e-graph that simultaneously represents expressions in both real-number arithmetic and target-specific floating-point operations. This unified representation is the primary technical contribution, which in turn necessitates a novel "typed extraction" algorithm to pull valid, well-typed programs from the e-graph.

Strengths

The primary strength of this paper is a genuinely novel synthesis of existing techniques into a new, more powerful framework.

1. The Mixed Real/Float E-Graph: The core idea of performing equality saturation on an e-graph containing both real-number semantics (e.g., 1/x) and concrete floating-point implementations (e.g., rcpps(x)) is, to my knowledge, new. Prior work like Herbie [29, 31] operates on an e-graph of purely floating-point expressions at a fixed precision. Traditional compilers perform instruction selection via pattern matching on a DAG or tree, not within an equality saturation framework that also considers mathematical equivalences. By unifying these into a single data structure, Chassis allows mathematical rewrites (e.g., a/b -> a * (1/b)) to directly enable target-specific instruction selection (e.g., using a fast reciprocal instruction). This is an elegant and powerful architectural innovation that cleanly bypasses the phase-ordering problems inherent in a multi-stage approach.

2. Formalizing the Compiler's Task as "Desugaring Preservation": The conceptual framing of the problem (Section 4.1) is itself a novel contribution. Viewing target-specific operators as implementations that "desugar" to a real-number denotation provides a clean, formal bridge between the abstract mathematical world and the concrete hardware world. This abstraction is what enables the mixed e-graph to function. While denotational semantics is not new, its specific application here as the core equivalence relation for a numerical optimization e-graph is a novel and insightful framing.

Weaknesses

While the central synthesis is novel, some of the constituent parts are extensions of known concepts, and the paper could be more precise in delineating the exact "delta" from prior art.

1. Overlap with Instruction Level Abstraction (ILA): The concept of modeling hardware instructions or accelerators by their mathematical function is conceptually similar to the Instruction Level Abstraction (ILA) proposed in prior work [23], which the authors cite. ILA is used for formal verification and models the state updates of a system based on its instructions. The "desugaring" in Chassis is essentially a stateless version of this for pure functions. The authors should more explicitly state that while the abstract modeling concept has precedents, their contribution is the integration of this concept into a generative, equality-saturation-based optimization framework for numerical code, which is a different domain and purpose than ILA's verification focus.

2. Incremental Novelty of "Typed Extraction": The mixed real/float e-graph necessitates an extraction algorithm that is aware of types. The paper presents "typed extraction" as a novel algorithm (Section 5.1). However, it appears to be a logical, albeit non-trivial, engineering extension of standard cost-based extraction algorithms (e.g., the one used in egg [39]). Given a mixed-type data structure, any extraction routine must handle types to produce a valid program. The novelty appears to be in the application and implementation, rather than a fundamental algorithmic breakthrough in program extraction from e-graphs. The paper would be stronger if it either claimed this as a necessary engineering contribution or detailed a more profound theoretical novelty in the algorithm itself.

3. The "Cost Opportunity" Heuristic: The heuristic for guiding the search (Section 5.2, Figure 5) is a clever technique. It uses a lightweight, restricted equality saturation pass as a lookahead mechanism. While the specific formulation is new, the general idea of using a cheaper, approximate model to guide a more expensive search is a standard meta-heuristic in optimization. Its novelty is that of a specific, effective heuristic, not a paradigm shift in search.

Questions to Address In Rebuttal

1. Please clarify the novelty of your "desugaring" abstraction (Section 4) with respect to prior work on Instruction Level Abstraction [23]. Is the core novelty simply the application of this known modeling technique to the domain of numerical compilers, or is there a more fundamental difference in the abstraction itself?

2. Could you elaborate on the novelty of the "typed extraction" algorithm (Section 5.1)? Is there a deeper algorithmic or theoretical contribution beyond adapting standard e-graph extraction to handle a multi-typed node representation, which seems like a necessary step for the proposed e-graph structure?

3. The core contribution is the unified e-graph. This seems to be a significant increase in the search space size and complexity compared to Herbie's approach. Does this novel representation introduce new scaling challenges? For example, does the e-graph grow intractably large when dealing with targets that have many operators with similar or identical desugarings (e.g., multiple approximate sine functions)?