chomsky-uir

Universal Intermediate Representation (UIR) for the Chomsky framework, powered by E-Graphs.

Overview

chomsky-uir is the core optimization engine of Project Chomsky. Unlike traditional linear IRs, UIR uses Equality Graphs (E-Graphs) to store and reason about multiple equivalent forms of a program simultaneously. This allows for exhaustive exploration of optimization opportunities without being limited by phase ordering.

Features

• Intent Capture: Provides IntentBuilder to formalize computational intents into rewriteable expressions.
• E-Graph Implementation: High-performance E-Graph structure for managing equivalence classes of program fragments.
• Constraint Analysis: Built-in analysis framework to track hardware constraints, type information, and semantic properties on the E-Graph.
• Lowering: Robust logic to reduce high-level intents into UIR primitives (IKun operators).
• Register Allocation: Includes a LinearScanAllocator for mapping UIR virtual registers to physical registers or stack slots.

Module Structure

• egraph.rs: The heart of the IR, managing e-classes and nodes.
• intent.rs: Defines the IKun operator set, the primary language of the UIR.
• builder.rs: Fluent API for constructing UIR from higher-level representations.
• analysis.rs: Framework for running monotonic analyses (like ConstraintAnalysis) over the E-Graph.
• regalloc.rs: Register allocation algorithms for backend emission.

Usage

use chomsky_uir::{EGraph, IntentBuilder, IKun};

let mut egraph = EGraph::new();
let mut builder = IntentBuilder::new(&mut egraph);

// Construct a simple addition
let a = builder.constant(1);
let b = builder.constant(2);
let result = builder.add(a, b);