Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

References

A curated list of reference documents and resources for the tuffy project.

Compiler Optimization

  • Future Directions for Optimizing Compilers — Nuno P. Lopes, John Regehr, 2018. Discusses challenges in making optimizing compilers faster, less buggy, and more capable.
  • Cranelift: Using E-Graphs for Verified, Cooperating Middle-End Optimizations — Chris Fallin, Bytecode Alliance. Proposes acyclic e-graphs (aegraphs) as a unified middle-end optimization framework for Cranelift, replacing separate GVN/LICM/constant-folding passes. Key ideas: pure nodes float above a side-effect skeleton (the original CFG), scoped elaboration naturally subsumes GVN and LICM, and ISLE-based declarative rewrite rules enable verifiable optimizations. Directly relevant to tuffy’s declarative rewrite rules and “analysis is also a transformation” design.
  • optir — Jamey Sharp. Research prototype combining e-graph equality saturation (via egg) with RVSDG (Regionalized Value State Dependence Graph). Control flow is encoded structurally via switch/loop/func operators rather than explicit branches, enabling optimizations across complex control flow including irreducible CFGs. Relevant to tuffy’s hierarchical CFG regions and declarative rewrite approach.
  • egg: Fast and Extensible Equality Saturation — Max Willsey, Chandrakana Nandi, Yisu Remy Wang, Oliver Flatt, Zachary Tatlock, Pavel Panchekha, POPL 2021. Introduces the egg Rust library for e-graphs and equality saturation with novel techniques: rebuilding for amortized invariant maintenance, and e-class analyses for domain-specific data attached to equivalence classes. Relevant to tuffy’s declarative rewrite rules — equality saturation is a candidate execution model for applying verified rewrite rules without phase-ordering concerns.

Memory Analysis

  • MemorySSA — LLVM. Virtual SSA form for memory operations using a single memory partition. Three node types: MemoryDef (stores, calls, fences, atomics), MemoryUse (loads), MemoryPhi (CFG joins). Each MemoryDef creates a new version of “all memory”; precision is recovered via a clobber walker backed by alias analysis rather than upfront partitioning. Key design insight: precise memory partitioning is impractical and not worth the cost — a single chain with on-demand disambiguation is more efficient. Directly informs tuffy’s MemSSA design: single memory token chain encoded in IR, with progressive refinement as alias analysis improves.

IR Design and Semantics

  • RVSDG: An Intermediate Representation for Optimizing Compilers — Nico Reissmann, Jan Christian Meyer, Helge Bahmann, Magnus Själander, 2019. Formalizes the Regionalized Value State Dependence Graph, a data-flow-centric IR where nodes represent computations, edges represent dependencies, and regions capture hierarchical program structure. Demonstrates Dead Node and Common Node Elimination on the representation. Directly relevant to tuffy’s hierarchical CFG with SESE regions and the optir approach built on top of RVSDG.

  • RFC: Add a New Byte Type to LLVM IR — Juneyoung Lee, Pedro Lobo, Nuno Lopes, George Mitenkov. Proposes b<N> byte type to represent raw memory data, enabling per-byte poison tracking and paving the way for undef removal.

  • Leaving the Sea of Nodes — V8 team. Post-mortem on 10 years of Sea of Nodes in TurboFan: effect chain complexity, poor cache locality, limited floating benefits for effectful operations, compilation speed issues. Replaced with CFG-based Turboshaft, halving compile time.

  • A Simple Reply — Cliff Click. Rebuttal to V8’s SoN criticism: argues problems stem from JS’s lack of strong typing, not SoN itself. Strong typing (Java, Rust) provides ECA naturally, simplifying effect management. Worklist algorithms solve visitation order. Dead code elimination is near-free with reference counting.

  • VPlan: Vectorization Plan — LLVM. Hierarchical CFG with nested SESE regions and recipe-based transformations for vectorization. Key ideas: plan-then-execute (analysis doesn’t modify IR), multiple candidates with cost estimation, recipes naturally record transformation provenance. Relevant to tuffy’s “analysis is also a transformation” and rewrite path tracing goals.

Memory Model and Pointer Semantics

  • Pointers Are Complicated, or: What’s in a Byte? — Ralf Jung, 2018. Argues pointers are not integers; proposes abstract pointer model (allocation ID + offset) preserving provenance. Defines bytes as Bits(u8) | PtrFragment(Pointer, n) | Uninit. Directly relevant to tuffy’s byte type and uninitialized memory model.
  • Pointers Are Complicated II, or: We Need Better Language Specs — Ralf Jung, 2020. Shows three individually-correct LLVM optimizations that produce wrong results when combined, due to unspecified pointer provenance. Concludes: pointers have provenance, integers do not; ptr-to-int-to-ptr roundtrips are not no-ops.
  • Pointers Are Complicated III, or: Pointer-Integer Casts Exposed — Ralf Jung, 2022. Proposes “provenance exposure” model: ptr-to-int casts have side effects (exposing provenance), int-to-ptr casts are non-deterministic. Rust’s Strict Provenance API (ptr.addr(), with_addr()) offers a cleaner alternative. Relevant to tuffy’s pointer representation design.
  • Uninit — Ralf Jung, 2019. Uninitialized memory is not “random bits” but a distinct abstract state (None). Any operation on uninit values is UB. Validates tuffy’s decision to allow uninitialized memory at the memory level while keeping values as concrete-or-poison.
  • Do We Really Need Undefined Behavior? — Ralf Jung, 2021. Argues unrestricted UB is necessary for practical optimization (register allocation, constant folding). Platform-specific UB would make even basic codegen impossible. Supports tuffy’s poison-based UB model as a principled middle ground.
  • Clarifying the Semantics of ptrtoint — LLVM discussion. Proposes separating ptrtoint (full bitwise representation) from ptrtoaddr (address only). Highlights that compiler-level provenance and hardware provenance (CHERI) are distinct. Relevant to tuffy’s pointer representation: need to decide whether ptr-to-int exposes provenance or just address.
  • RFC: Replacing getelementptr with ptradd — nikic (Nikita Popov). Proposes replacing type-based GEP with offset-based ptradd instruction. Eliminates redundant encodings, makes address arithmetic explicit and visible to CSE/LICM, simplifies analysis by removing expensive GEP decomposition. Tuffy adopts ptradd directly instead of GEP.

ABI and Calling Conventions

  • RFC: An ABI Lowering Library for LLVM — nikic (Nikita Popov). Proposes a standalone LLVMABI library with its own type system dedicated to ABI lowering, extracting logic currently duplicated across frontends (Clang, Rust, etc.). Key design: independent type system capturing only ABI-relevant information, per-target calling convention implementations, ABIArgInfo results guiding IR generation. Layered to depend only on LLVM Support, with a C API for non-C++ frontends. Directly relevant to tuffy’s plan for a dedicated ABI library that maps int parameters/returns to concrete register classes and calling conventions.

Testing and Validation

  • RFC: Upstreaming LLVM UB-Aware Interpreter — dtcxzyw. Proposes upstreaming llubi, a UB-aware LLVM IR interpreter that detects undefined behavior during execution and properly propagates poison values. Key motivation: reducing miscompilation reproducers directly on LLVM IR (minutes vs hours with C-level tools). Separate implementation from legacy ExecutionEngine because GenericValue cannot represent poison or pointer provenance. Relevant to tuffy’s IR interpreter design.
  • llvm-ub-aware-interpreter (llubi) — dtcxzyw. Implementation of UB-aware LLVM IR interpreter. Detects guardable UBs at execution time, tracks poison propagation, integrates with llvm-reduce for test case minimization and Csmith/Rustlantis for fuzzing. Treats undef as zero (practical simplification). Does not model pointer aliasing or full provenance. Directly informs tuffy’s interpreter design, though tuffy’s poison-only model (no undef) and four-state bytes enable a cleaner implementation.

Rustc Backend Integration

  • Lowering MIR — rustc dev guide. MIR lowering flow: codegen_crate → codegen_mir per function, with modules for blocks, statements, operands, places, rvalues. SSA analysis runs before translation. One MIR basic block generally maps to one backend basic block.
  • Backend Agnostic Codegen — rustc dev guide. Trait-based backend interface: CodegenBackend, ExtraBackendMethods, CodegenMethods (CodegenCx), BuilderMethods (Builder). Associated types: Value, BasicBlock, Type, Function. ~10,000 lines of reusable backend-agnostic code in rustc_codegen_ssa. Custom backends implement these traits to plug in.