A Cargo workspace of Rust crates providing trait-based abstractions and implementations for compiler intermediate representations: control flow graphs (CFG), static single assignment (SSA) form, and code generation backends.
The crates are designed to be composable via Rust's trait system. Most core
crates are #![no_std] compatible (requiring only alloc). The workspace
uses Cargo's resolver v2.
The workspace also contains portal-jit-host-names,
a dependency-free no_std + alloc helper for safely rendering configurable
host-property accesses in generated JavaScript. It is generic over each
consumer's Display-backed semantic key type, so it does not depend on
WSDOM, Vane, or Jade. See its crate README for the resolver and validation
contract.
The workspace Cargo.toml lists 12 crates. Four additional crates exist on
disk (ast-traits, siftify, ssa-pliron-compat, ssa-trace) but are
not included in the workspace members list.
Core CFG abstraction layer. Defines three traits that everything else builds on:
Func— a function containing an arena ofBlocks and an entry block.Block<F>— holds aTerminator.Term<F>— iteratesTargets (successors).Target<F>— a single successor edge; providesblock()/block_mut().
Either<A,B> gets a blanket Term impl so you can compose terminator
types without boilerplate. The util module adds FuncViaCfg<T,W> (a
newtype that pairs an arbitrary CFG T with an entry block) and a
func_via_cfg! macro to generate the corresponding wrapper struct.
Type aliases BlockI<F>, TermI<F>, TargetI<F> project through the
arena index to the concrete output types.
Dependencies: arena-traits, either.
Extends cfg-traits with SSA value semantics.
Func— adds aValuetype, aValuesarena, and accessors.Block<F>— addsinsts()(iterate value IDs in order) andadd_inst(func, block, value).Value<F>— marker; requiresHasValues<F>.TypedFunc/TypedBlock/TypedValue— optional layer for typed IRs;TypedFunc::add_blockparamadds a block parameter with a type.HasValues<F>/HasChainableValues<F>— iterate or mutably iterate theF::ValueIDs held by an operand.Target<F>/Term<F>— SSA-aware versions that also implementHasValues.Builder<F>/CpsBuilder<F>— helper traits for CPS-style IR construction; closuresFnOnce(&mut F, F::Block) -> Result<(R, F::Block)>automatically implementBuilder.op::OpValue<F,O>— disassembly/reassembly trait for pattern-matching specific op shapes out of a value type, with composableEither-based chaining.
Val<F> and Vec<F::Value> both implement HasValues and
HasChainableValues.
Dependencies: anyhow (no-std), arena-traits, cfg-traits, either.
Concrete algorithms over any IR that satisfies cfg-traits/ssa-traits.
cfg module — iterative DFS postorder traversal (postorder,
calculate_postorder).
dom module — Cooper/Harvey/Kennedy "Simple, Fast Dominance
Algorithm" (adapted from regalloc.rs, Apache-2.0/LLVM-exception).
Derives from a postorder walk; produces a BTreeMap<Option<Block>, Block> immediate-dominator tree. Public functions: domtree,
dominates, calculate.
maxssa module — max-SSA conversion pass (maxssa). For each block,
identifies values used but not defined there, adds block parameters via
TypedFunc::add_blockparam, and rewrites all branch targets to thread
the values through. Works in two passes: collect new args, then rewrite
uses and branch args.
reducify module — CFG reducibility pass (Reducifier::run). Uses
RPO to find back-edges and assign header sets; detects irreducible loops
(edges that enter a loop region without going through the header); when
irreducible edges exist, applies max-SSA then clones basic blocks to
separate execution contexts, rewriting value and block maps accordingly.
preds(f, k) — iterator over predecessor blocks of k.
add_phi(f, k, ty, trial) — adds a block parameter and propagates a
trial value from each predecessor.
Dependencies: arena-traits, cfg-traits, ssa-traits.
Bridges the SSA IR to the relooper crate. Given a Func whose Block
type implements RelooperLabel, calls ssa-impls::dom::domtree to build
the dominator tree, then feeds reachable blocks (those dominated by the
entry) and their successors into relooper::reloop, returning a
Box<ShapedBlock<F::Block>>.
Dependencies: arena-traits, cfg-traits, relooper, ssa-impls,
ssa-traits.
Emits Rust TokenStream from an SSA IR using ssa-reloop for structured
control flow.
Defines RsFunc (composed trait bound), Rs<F> (emit to TokenStream),
RsId<F> (emit as an Ident), RsTerm<F> (emit a terminator given a
block-to-tokens closure), and RsOp<F> (emit an operation given args and
block args).
go(params, f, entry) — top-level emitter. Declares Option<T>
variables for every SSA value and every block parameter, calls
ssa-reloop::go to get a ShapedBlock, then recurses through it via
block(). Branch control flow uses labeled loop / continue /
break following relooper's BranchMode. A cff integer variable
handles Multiple shaped blocks (the "control-flow flattening" pattern).
render_target emits the assignment sequence for a branch target's
arguments plus the goto expression.
With feature = "ssa-canon", provides Rs for ssa_canon::Value and
RsTerm for ssa_canon::Target. With feature = "id-arena", provides
RsId for id_arena::Id<T>.
Dependencies: anyhow, arena-traits, cfg-traits, either,
proc-macro2, quasiquote, quote, relooper, ssa-canon (optional),
ssa-reloop, ssa-traits, syn.
Emits C source code from an SSA IR.
CCFunc — composed trait bound requiring types/blocks/values/terminators
all implement C<F> (the fn c(&self, f: &F) -> Result<String> trait).
cc(s, entry) — generates a C function body: parameter list, variable
declarations (one per block parameter that isn't the entry, plus one per
SSA value), a goto to the entry block label, then a sequence of
labeled basic blocks (BB<n>:) each containing value assignments and a
terminator.
render_target — emits the argument-copy sequence and goto for a branch.
With feature = "id-arena": C for id_arena::Id<T> (formats as
x<index>). With feature = "ssa-canon": C for ssa_canon::Value
and ssa_canon::Target. Either<A,B> gets blanket C and COp impls.
Dependencies: anyhow, arena-traits, cfg-traits, either,
id-arena (optional), ssa-canon (optional), ssa-traits.
A concrete, generic SSA IR parameterized by <O, T, Y> (operation type,
terminator type, type annotation):
Value<O,T,Y>— eitherOp(O, args, block_args, ty)orParam(index, block, ty).Block<O,T,Y>— holdsterm: T,insts: Vec<Id<Value>>, andparams: Vec<(Y, Id<Value>)>.Target<O,T,Y>—{ args: Vec<Id<Value>>, block: Id<Block> }.Func<O,T,Y>—{ vals: Arena<Value>, blocks: Arena<Block>, entry }.
Implements cfg_traits::Func, ssa_traits::Func, ssa_traits::TypedFunc,
ssa_traits::Block, ssa_traits::TypedBlock, ssa_traits::Value,
ssa_traits::TypedValue, ssa_traits::Target, and all the corresponding
cfg_traits counterparts.
Also implements OpValue<Func<O,T,Y>, CanonOp<X>> for Value<O,T,Y>
when O: Sift<X>, enabling pattern-matching ops out of the value via
the sift-trait mechanism. Uses unsafe { mem::transmute } to reinterpret
arena IDs across the type change.
Backed by id-arena. Uses arena-traits with the id-arena feature.
Dependencies: anyhow, arena-traits (id-arena feature), cfg-traits,
id-arena, sift-trait, ssa-traits.
Generic SSA-to-SSA translation framework.
Translator<F: TypedFunc, G: Func> — the core translation trait with
associated types Meta (how a source value maps to target values) and
Instance (per-block state). Methods: add_blockparam, emit_val,
emit_term.
State<F,G,T> — memoizes already-translated (source_block, instance)
pairs in a BTreeMap; State::go drives the translation loop, calling
add_blockparam for each typed block param and emit_val for each
instruction before emit_term.
CarryTranslator<F,G> — a blanket refinement for translators where
Meta: ValSer<G::Value> and Instance: EqIter<Item=(F::Ty, Meta::Kind)>.
ai module — AI<H> wrapper that implements Translator given a
Handler<F,G> that knows how to stamp/unstamp kind-annotated values
(AnyKind from the valser crate) and emit individual values/terminators.
emit_target reconstructs a target in the output IR by gathering values,
inferring types via ty(), and calling go for the target block.
Dependencies: anyhow, arena-traits, cfg-traits, either,
ssa-traits, valser.
Single trait: Sift<T> — extracts a T from Self or returns a
Residue. Methods: sift(self) -> Result<T, Residue>, of(T) -> Self,
lift(Residue) -> Self.
Blanket impl for Either<T,U>: if A: Sift<T> and A::Residue: Sift<U>,
then A: Sift<Either<T,U>>, with Residue = <<A as Sift<T>>::Residue as Sift<U>>::Residue. This chains sifting left-first, falling through to
right.
Used by ssa-canon to pattern-match op variants and by tac-traits to
distinguish register LValues from other LValues.
Dependencies: either.
Extends cfg-traits::Func with a register file:
pub trait Func: cfg_traits::Func {
type Reg;
type Regs: IndexIter<Self::Reg>;
fn regs(&self) -> &Self::Regs;
fn regs_mut(&mut self) -> &mut Self::Regs;
}#![no_std]. No algorithms; purely a trait definition.
Dependencies: arena-traits, cfg-traits.
Three-address code layer on top of register-machine-traits.
Func — blanket impl over any register_machine_traits::Func whose
blocks arena yields Block<Self>.
Block<F> — extends cfg_traits::Block with:
type Item— the instruction payload.type LValue: Sift<F::Reg, Residue: AsRef<F::Reg> + AsMut<F::Reg>>— either exactly a register, or a residue that can borrow as a register. Also requiresAsRef<F::Reg> + AsMut<F::Reg>.values()/values_mut()— iterate(&LValue, &Item)pairs.add_value(lvalue, item)— append an instruction.
Helper type aliases: ItemI<F>, LValueI<F>, LValueNonRegI<F>.
#![no_std].
Dependencies: arena-traits, cfg-traits, register-machine-traits,
sift-trait.
Utility for merging multiple lists of items by equality, tracking index mappings.
union(iterators) — takes an iterator of iterators, deduplicates items
by == into a single vals: Vec<A>, and records for each input list
the positions (poss: Vec<Vec<usize>>) of its items in the merged
vals.
Union::create(i, default, vals) — given a per-input-list index i and
a fresh iterator of values, constructs a full-length Vec<B> by writing
defaults for items not in list i and the provided values for items that
are.
#![no_std].
Dependencies: none.
Defines a Trace<F,G> trait for abstract interpretation / symbolic
execution: run a block producing a State: ValSer<G::Value>, and
transfer across an edge producing a new Instance. The Tracer<F,G,T>
struct wraps the implementation and memoizes (block, instance) -> G::Block results.
Dependencies: anyhow, arena-traits, cfg-traits, ssa-traits,
valser.
Bridge between the pliron MLIR-style IR framework and ssa-traits.
PlironCompatOp<F: ssa_traits::Func> — implemented by pliron::op::Op
subtypes; to_ssa_traits translates the op into the target SSA IR given
value/block maps.
pliron_compat_op!(F => TraitName) — macro that generates a blanket alias
trait and registers a linkme distributed-slice entry for pliron's op
interface dependency system.
Dependencies: anyhow, arena-traits, cfg-traits, linkme, pliron,
ssa-traits.
Minimal AST abstraction. Defines Ast with associated types
Value<Sub> and Control<Sub>, and AstImpl<A> as an enum of Op or
Control. No dependencies.
A proc-macro2/quote/syn-based code generation helper (patch) that
rewrites enum definitions: adds a generic type parameter
__Pattern_<Variant> (defaulting to ()) for each variant, and injects
a corresponding field into each variant. Not registered in the workspace.
Dependencies: proc-macro2, quote, syn.
cfg-traits
└── ssa-traits
└── ssa-impls
└── ssa-reloop ──── ssa-rust
sift-trait ───── ssa-canon ─────── ssa-cc
register-machine-traits
└── tac-traits
onion (standalone)
The external crates used across the workspace are: arena-traits,
either, anyhow, id-arena, relooper, valser, proc-macro2,
quote, quasiquote, syn.
All workspace-member crates are at version 0.2.3 (current) with tags
for each crate published back to v0.1.x. Release branches visible in
remotes: v0.2, v0.4, dev/0.3. The workspace Cargo.toml declares
workspace-level id-arena = "2.2.1" used by ssa-canon and optionally
by ssa-cc and ssa-rust.