Phases

At a high level, a phase is a self-contained compiler transformation or analysis step. Phases are intended to do one thing at a time and compose in a straightforward sequence. See also the Rewriting Guide, since several phase families are built directly on top of Rewriter.

Overview

A Phase has a single entry point, run(), which wraps the actual implementation in start().

Phase

Phase is the minimal base class.

A phase provides:

• a name or annex,
• access to the current World,
• a run() wrapper for logging and verification,
• a todo() accessor backed by the internal todo_ flag for fixed-point iteration.

Note

A phase requests another round by calling invalidate().

• PhaseMan uses this to drive fixed-point pipelines.
• RWBase uses this to drive its optional pre-analysis to a fixed point.

Typical Shape

A custom phase usually derives from Phase and implements start():

class MyPhase : public mim::Phase {
public:
    MyPhase(World& world)
        : Phase(world, "my_phase") {}
 
private:
    void start() override {
        // do work here
    }
};

Run it with:

mim::Phase::run<MyPhase>(world);

Analysis

Analysis is the base class for phases that inspect the current world using the Rewriter traversal machinery. It inherits from both Phase and Rewriter, but unlike RWPhase, it rewrites into the same world. In practice, this means Rewriter is used as a structured, graph-aware traversal over ordinary MimIR Defs.

Note

An Analysis based on Rewriter has an abstract domain of ordinary Defs.

A central feature of Analysis is its lattice(), a Def2Def map that stores abstract information about old-world Defs.

This is often convenient because analysis information can itself be represented as ordinary MimIR Defs. As a result, existing IR machinery applies automatically, including:

• hash-consing / canonical sharing,
• built-in normalizations,
• and other simplifications already provided by the World.

So if your abstract domain fits naturally into MimIR, you can often encode it directly as Defs and store it in the analysis lattice.

An Analysis visits:

1. all registered annex roots, then
2. all external mutables.

During the first part, mim::Analysis::is_bootstrapping() is true. During the second part, it is false.

Typical usage:

• override rewrite(), rewrite_imm(), rewrite_mut(), or node-specific rewrite hooks,
• compute abstract information while traversing reachable IR,
• store that information in the lattice (see below) and/or in side tables,
• rely on lattice(concr, abstr) to request another iteration automatically, or call invalidate() manually where needed.

Lattice API

The lattice follows these conventions:

• An absent entry means ⊥ - nothing is known yet.
• An entry mapping a definition to itself (def ↦ def) means ⊤ - "no useful information, keep as-is".
• Any other entry is a discovered abstract value. Analyses may also introduce intermediate sentinels as ordinary Defs (for example, SEO's GVN-bundle and pending-⊤ proxies).

Analysis provides the following accessors and mutators:

• lattice() returns the full lattice map.
• lattice(def) returns the recorded abstract value for def, or nullptr if nothing is known.
• lattice(concr, abstr) writes concr ↦ abstr into both the lattice and the rewriter map (so future rewrites of concr short-circuit to abstr) and automatically invalidates iff this changes observable information: an existing entry was overwritten, or a fresh fact other than ⊤ was inserted. Freshly inserting ⊤ (def ↦ def) stays silent, as it is indistinguishable from an absent entry for consumers. It returns true iff it changed observable information - i.e. iff it invalidated - so the caller can still react, e.g. log. Besides recording a lattice fact, it also seeds the rewriter map, so a later rewrite() of concr immediately returns abstr. It asserts if you descend from ⊤.
• lattice_force(concr, abstr) is the non-asserting variant.
• pin(def) monotonically forces def to ⊤. Being built on lattice(concr, abstr), it invalidates iff it overwrote previous information.
• is_top(def) checks for def ↦ def.

Analysis-specific sentinels should be ordinary Defs - e.g. a dedicated Proxy tag, as SEO uses for its GVN and pending-⊤ markers - never nullptr, which is reserved for absent.

Handling of Mutables

Unlike RWPhase, an Analysis must traverse the entire reachable program without rebuilding it. For this reason, Analysis overrides rewrite_mut() to keep mutables in place and use the rewriter machinery as a graph-aware traversal over the existing world.

Immutables are still visited depth-first through the inherited Rewriter recursion, but mutables are visited breadth-first via an internal worklist. This matters because abstract values typically flow between mutables — e.g. from an App call site into the callee's binder vars. A breadth-first order tends to seed a mutable from all of its predecessors before its body is walked, so information propagates further per fixed-point round and convergence needs fewer rounds. Breadth-first traversal is safe here precisely because an Analysis never rebuilds a mutable: it maps every mutable to itself, so nothing depends on a mutable being fully rewritten before it is used (contrast the strict depth-first ordering an RWPhase needs, where a rebuilt binder's type/identity is consumed as it is constructed).

rewrite_mut():

1. returns immediately if the mutable was already scheduled this round (see below),
2. records the mutable as visited via mut -> mut, and
3. enqueues it on the worklist — it does not recurse into the body itself.

Once a batch of roots has been scheduled, Analysis::drain() pops mutables from the worklist and, for each, enters it for curr_mut() tracking and rewrites its dependencies. Rewriting those dependencies schedules any further mutables it reaches, so the worklist drains in breadth-first order.

The mut -> mut entry recorded in step 2 doubles as the per-round "already scheduled" marker: it lives in the rewriter map (see lookup()), which reset() clears at the start of every round. Hence each mutable's dependencies are walked at most once per fixed-point round, which also prevents cyclic (recursive) CFGs from recursing forever.

Warning

Because rewrite_mut() enqueues instead of dispatching by node, the node-specific rewrite_mut_* hooks (e.g. rewrite_mut_Lam) are never invoked for an Analysis. Override rewrite_mut() itself (or the rewrite_imm_* hooks, which dispatch as usual) instead.

When a rewrite_imm_App override propagates abstract values from call arguments into a callee's binder vars, it should seed those lattice entries first and then rewrite() the callee. This schedules the callee (or does nothing if it is already scheduled), so its body is walked later during the drain, after the seeded facts — and any joins from sibling call sites — are in place. lattice(concr, abstr) conveniently pairs the two writes (lattice and rewriter map) that arise in this seeding pattern.

Sparse Fixed-Point Iteration

A full round traverses the whole World: start() first runs prepare(), then rewrites all annex roots, drains the worklist, does the same for the external mutables, and finally runs finalize(). Whenever lattice(concr, abstr) changes an entry it invalidates, requesting another round, and records curr_mut() as dirty.

The first round, and each certification round described below, is full. A follow-up round is sparse: it re-drains only dirty mutables — plus everything reachable from them — instead of walking the whole World. At the start of a sparse round the accumulated lattice is replayed into the rewriter map, so a dirty mutable's body sees the substitutions its (non-revisited) producers installed in earlier rounds. An analysis can taint() additional mutables when a change must re-visit more than the writer — e.g. SEO taints all call sites of a Lam whose abstract vars changed, which keeps its per-round join restart sound. A change that cannot be attributed to any mutable (during the annex walk or finalize()) forces the next round to be full.

Since dirt tracks writers — not readers — a sparse round may miss affected mutables. Hence, once sparse rounds quiesce, one final full round certifies the fixed point; if it discovers new facts, iteration continues sparsely from its dirt. Only full rounds run finalize(), so post-passes always see the complete abstract World. Use make_dense() to force whole-World rounds unconditionally.

Reset Between Iterations

If an analysis participates in a fixed-point loop, it should be ready to run multiple times. The base reset() clears the rewriter map (and hence the per-round "already scheduled" markers) and the worklist, and resets Phase::todo() for the next round, but preserves lattice() so that abstract values accumulated in earlier iterations remain available — this is what makes fixed-point convergence possible.

RWBase

RWBase is the common base of the two rewriting phases: RWPhase rebuilds the world into a new one, InplaceRWPhase stays in the current one. Both are a Phase and a Rewriter and share the skeleton described here.

You never derive from RWBase directly — pick one of the two.

Execution Model

1. optionally perform a fixed-point analysis with analyze(),
2. rewrite the world roots:
   1. the annexes — if rewrite_annexes() says so,
   2. the external mutables;
3. run finalize();
4. an RWPhase additionally swaps the old and the new world.

Optional Pre-Analysis

An RWBase may be given an associated Analysis. If so, analyze() runs that analysis to a fixed point before rewriting begins.

This is a common pattern:

• the analysis computes facts on the world the phase reads from,
• those facts are stored in Analysis::lattice() and/or auxiliary side tables,
• the rewrite queries them through RWBase::lattice().

If no analysis is needed, analyze() can simply return false.

Analysis Results

Once analyze() has run, the rewrite can query the analysis result through RWBase::lattice().

RWBase::lattice() provides access to the analysis lattice for the Defs that the analysis visited — the old ones in the case of an RWPhase. It returns the abstract value computed by the associated Analysis, or nullptr if no value is available.

This is the standard way to communicate fixed-point analysis results into the subsequent rewrite.

Bootstrapping

Like Analysis, an RWBase processes annex roots before externals.

While annexes are being rewritten, mim::RWBase::is_bootstrapping() is true.

This matters because annexes may depend on one another. During bootstrapping, a rewrite that refers to another annex may need to defer or skip that work because the referenced annex might not yet exist in the new world.

Roots

rewrite_annexes() decides whether the annex roots are walked at all. An RWPhase has to walk them in order to populate the new world's annex table, so it returns true; an InplaceRWPhase finds that table already correct and defaults to false.

rewrite_root() is the hook for rewrites that must exempt roots. An annex or an external is the program's interface to the outside, so a phase that reshapes definitions usually has to leave the roots themselves alone; EtaConv uses it so that an annex or external keeps its η-shape.

Deferred Rewrites

A rewrite hook may not be able to finish its work immediately. For example, a closure-converting phase must create a function stub eagerly so callers can refer to it, but can rewrite its body only after completing the enclosing scope. Push such work onto your own worklist and drain it in finalize(), which runs after all roots have been walked but — for an RWPhase — still before the two worlds are swapped (see clos::phase::ClosConv).

RWPhase

RWPhase is the base class for phases that rebuild the current world into a new one, thereby removing garbage. This is the standard base class for optimization phases that structurally transform IR.

Here the RWBase's two worlds differ:

• Phase::world is the old world,
• Rewriter::world is the new world.

Note

To avoid confusion, direct world() access is deleted. Use:

• old_world() to inspect existing IR,
• new_world() to build rewritten IR.

After the final swap, the rewritten world becomes the current one.

Cleanup

Cleanup is simply an RWPhase with no custom rewrites. Because an RWPhase reconstructs only what is reachable from the world roots, rebuilding automatically eliminates dead and unreachable code.

Typical Shape

class MyRWPhase : public mim::RWPhase {
public:
    MyRWPhase(World& world)
        : RWPhase(world, "my_rw_phase") {}
 
private:
    const Def* rewrite_imm_App(const App* app) override {
        // customize rebuilding here
        return RWPhase::rewrite_imm_App(app);
    }
};

Run it with:

mim::Phase::run<MyRWPhase>(world);

InplaceRWPhase

InplaceRWPhase rewrites the current world in place instead of rebuilding it into a fresh one.

A mutable keeps its identity: its ops() are reset with Def::set only when rewriting changes them. So hash-consing makes every unaffected Def free instead of a per-run rebuild tax. A mutable whose type changes is the one exception — identity is tied to the type — and falls back to an RWPhase-style stub rebuild in this same world. This matters most for the annex graph: it is proportional to the loaded plugins — not to the program — and a local rewrite never touches it, yet an RWPhase re-creates all of it on every run.

Unlike an RWPhase, the RWBase's two worlds are the same one here, so plain world() is what you want.

Restrictions

An InplaceRWPhase

• cannot immutabilize a mutable that the rewrite made vacuous (unless it takes the type-change fallback),
• must not hand out a fresh identity for something that already is in its target shape — since Phase::todo() is exact, that would never converge, and
• leaves what it replaced behind as garbage until the next Cleanup.

Use an RWPhase for anything else.

Pruning

Since nothing is rebuilt, an InplaceRWPhase only pays for the nodes it actually looks at. So prune whatever provably cannot change with a cheap O(1) test at the top of your rewrite(); this is what turns the traversal from "hash-cons every node" into "touch only what matters".

Def::is_ground is the ready-made test for phases that only rewrite mutables and/or substitute Vars: a subtree with neither local_muts() nor local_vars() contains neither. Both BetaRed and EtaConv use it.

Warning

Testing only local_muts() is not enough: a substitution installed via Rewriter::map() would silently be dropped in a mut-free subtree that still mentions the substituted Var.

Roots

By default, an InplaceRWPhase walks only the external roots: whatever the program actually uses is reached through the externals anyway. Override rewrite_annexes() with true if your rewrite must also see unused annexes.

Fixed Points

Since a change is only ever committed if it really is one, Phase::todo() is exact: a quiet run costs a pruned traversal and nothing else. This is what makes an InplaceRWPhase cheap to re-run inside a PhaseMan fixed-point loop.

Typical Shape

class MyInplaceRWPhase : public mim::InplaceRWPhase {
public:
    MyInplaceRWPhase(World& world)
        : InplaceRWPhase(world, "my_inplace_phase") {}
 
private:
    const Def* rewrite(const Def* def) final { return def->is_ground() ? def : Rewriter::rewrite(def); }
 
    const Def* rewrite_imm_App(const App* app) final {
        // customize rewriting here
        return Rewriter::rewrite_imm_App(app);
    }
};

PhaseMan

PhaseMan organizes several phases into a pipeline.

It can run them:

• once, in sequence, or
• repeatedly to a fixed point.

A fixed-point PhaseMan reruns the pipeline as long as at least one phase invalidates. Because a phase's run is a deterministic function of the World's content, PhaseMan skips a phase when its last run was quiet and no later phase has changed the world. Consequently, tail iterations rerun only phases that may still make progress; the pipeline terminates without a final round that reruns every phase.

Before a rerun, the phase is recreated from its original configuration. This prevents phase-local state from leaking across rounds unless the phase explicitly reconstructs it.

Note

PhaseMan is the orchestration layer for classical phase pipelines.

Typical Shape

auto phases = mim::Phases();
phases.emplace_back(std::make_unique<PhaseA>(world));
phases.emplace_back(std::make_unique<PhaseB>(world));
 
mim::PhaseMan man(world, mim::Annex::base<mim::plug::compile::phases>());
man.apply(/*fixed_point=*/true, std::move(phases));
man.run();

Use a fixed-point pipeline when phases expose new optimization opportunities for one another.

ClosedMutPhase

ClosedMutPhase is a traversal helper for phases that visit all reachable, closed mutables in the world.

A mutable is relevant here if it is:

• reachable,
• closed, i.e. it has no free variables,
• optionally non-empty, depending on elide_empty.

This is useful for local analyses or transformations naturally phrased as:

Note

For every reachable closed mutable, inspect or process it.

You override visit(M*), where M defaults to Def but may be restricted to a particular mutable subtype.

Typical Shape

class MyClosedPhase : public mim::ClosedMutPhase<Lam> {
public:
    MyClosedPhase(World& world)
        : ClosedMutPhase(world, "my_closed_phase", /*elide_empty=*/true) {}
 
private:
    void visit(Lam* lam) override {
        // process each reachable closed Lam
    }
};

NestPhase

NestPhase builds on ClosedMutPhase and computes a Nest for each visited mutable.

Use it when your phase needs a structured view of nested control or binding structure rather than just the raw mutable.

Instead of overriding visit(M*), override:

visit(const Nest&)

This is convenient for analyses that reason about nesting, dominance-like structure, or hierarchical regions.

Example: SCCP

#pragma once
 
#include <mim/phase.h>
 
namespace mim {
 
/// SCCP - Sparse Conditional Constant Propagation - but propagates **arbitrary expressions**.
/// @see [Constant propagation with conditional branches](https://dl.acm.org/doi/pdf/10.1145/103135.103136)
///
/// Lattice per Lam::var:
/// ```
///  ⊤      ← Keep as is
///  |
/// Expr    ← Whole expression is propagated (vertically) through var
///  |
///  ⊥
/// ```
class SCCP : public RWPhase {
private:
    class Analysis : public mim::Analysis {
    public:
        Analysis(World& world)
            : mim::Analysis(world, "SCCP::Analyzer") {}
 
    private:
        const Def* propagate(const Def* var, const Def* def);
        const Def* rewrite_imm_App(const App* app) final;
    };
 
public:
    SCCP(World& world)
        : RWPhase(world, "SCCP", &analysis_)
        , analysis_(world) {}
 
private:
    const Def* rewrite_imm_App(const App* old_app) final;
 
    Analysis analysis_;
    Lam2Lam lam2lam_;
};
 
} // namespace mim

The provided Sparse Conditional Constant Propagation (SCCP) implementation is a good example of the intended phase structure. Its architecture is:

• an inner Analysis computes propagation facts on the old world,
• an outer RWPhase uses those facts to rebuild a simplified new world.

Note

The implementation propagates not only constants but also arbitrary expressions.

Analysis

#include "sccp.h"
 
namespace mim {
 
/// The Lam the abstract @p var belongs to; @p var is a Var or a Var projection.
static Lam* lam_of(const Def* var) {
    if (auto ex = var->isa<Extract>()) return ex->tuple()->as<Var>()->binder()->as_mut<Lam>();
    return var->as<Var>()->binder()->as_mut<Lam>();
}
 
const Def* SCCP::Analysis::propagate(const Def* var, const Def* def) {
    // `⊥ ⊔ x` is `x`, but unusable if lam nests it.
    if (lam_of(var)->nests(def)) return pin(var), var;
 
    auto cur = lattice(var);
    if (!cur) { // ⊥ ⊔ def = def; lattice(var, def) invalidates, as it inserts a fresh non-⊤ fact
        lattice(var, def);
        log().d("propagate {} → {}", var, def);
        return def;
    }
 
    if (def->isa<Bot>() || cur == def || cur == var) return cur; // cur ⊔ ⊥ = cur ⊔ cur = cur; ⊤ stays ⊤
 
    if (cur->isa<Bot>()) { // ⊥ ⊔ def = def; lattice(var, def) invalidates, as it overwrites cur
        lattice(var, def);
        return def;
    }
 
    return pin(var), var; // two different values join to ⊤; lattice(var, var) therein invalidates, as it overwrites cur
}
 
const Def* SCCP::Analysis::rewrite_imm_App(const App* app) {
    if (auto lam = app->callee()->isa_mut<Lam>(); isa_optimizable(lam)) {
        auto n          = app->num_targs();
        auto abstr_args = absl::FixedArray<const Def*>(n);
        auto abstr_vars = absl::FixedArray<const Def*>(n);
 
        // propagate
        for (size_t i = 0; i != n; ++i) {
            auto abstr    = rewrite(app->targ(i));
            abstr_vars[i] = propagate(lam->tvar(i), abstr);
            abstr_args[i] = abstr;
        }
 
        lattice(lam->var(), world().tuple(abstr_vars)); // set new abstract var
        return world().app(rewrite(lam), abstr_args);
    }
 
    return mim::Analysis::rewrite_imm_App(app);
}
 
} // namespace mim

The SCCP analysis associates each lambda variable with a lattice value:

• bottom: no useful information yet (an absent entry),
• a concrete expression: this value can be propagated,
• top: keep the variable as-is (a Def maps to itself).

In the implementation, this lattice is stored in Analysis::lattice() as a Def2Def map. A nice aspect here is that the propagated value is itself a regular Def. This illustrates the benefit of building analysis on top of Rewriter: the abstract domain can live directly inside MimIR, so canonicalization and normalization come for free.

The join in propagate() is expressed entirely through the lattice API: lattice(var) reads the current abstract value, lattice(concr, abstr) overwrites it, and pin() resolves conflicting values to ⊤. No manual invalidate() bookkeeping is needed: every join step that gains information - including the ⊥ → value insert - triggers the next fixed-point round automatically via lattice(concr, abstr).

The analysis traverses the old world and updates the lattice when it sees applications of optimizable lambdas. Whenever this changes the lattice, the analysis reruns until stable - sparsely, re-draining only the dirty mutables in between full rounds. This is a textbook use of Analysis:

• walk the old IR,
• collect facts,
• store them in Analysis::lattice(),
• iterate to a fixed point.

SSA without Dominance

The very first line of propagate() is a guard that has no counterpart in the lattice algebra:

if (lam_of(var)->nests(def)) return pin(var);

It is the MimIR analogue of the dominance side condition that a classical SSA-based SCCP has to enforce, so it is worth spelling out what it replaces.

Why the guard exists at all

Textbook SCCP only ever propagates constants. A constant is a literal: it has no operands and is available at every program point by construction. This is what makes classical SCCP so comfortable — specializing a call site to a constant is always valid, and there is simply no availability question to ask.

MimIR's SCCP is more ambitious: it propagates arbitrary expressions, not just constants (this is essentially copy/expression propagation folded into the same fixed point). The moment you propagate a whole expression, you inherit an obligation constants let you ignore: the expression you substitute must actually be available at the point where it lands. The guard is exactly that availability check.

The classical picture

Textbook SCCP runs on a CFG in SSA form. Every value has exactly one definition, control flow is made explicit by basic blocks and edges, and φ-nodes reconcile the values that arrive along the different predecessor edges of a join block. SCCP assigns each SSA value a lattice cell (⊥ / a constant / ⊤) and, once the fixed point is reached, substitutes the discovered constant at every use of that value.

That substitution is only sound because SSA comes with a dominator tree:

• a definition dominates all of its uses, and
• a φ-operand must be available along its associated predecessor edge, i.e. its definition dominates the end of that predecessor block.

Dominance is exactly the structural guarantee "the value already exists at the program point where I want to use it". Without it, folding a value into a use could move a computation to a place where its operands are not yet defined.

The MimIR picture

MimIR has no CFG, no basic blocks, and no separate φ instructions. Control flow is expressed in CPS: a Lam is a basic block, its parameters are the φ-nodes, and every App of that Lam is one predecessor edge supplying the corresponding operands. So the SCCP analysis joins, per parameter, all the arguments flowing in from the call sites — precisely the φ-semantics — and stores the result in the lattice().

What is missing is the dominator tree. Its role — deciding whether a candidate value is available at the point where it would be substituted — is taken over by the scope/nesting relation Def::nests, computed structurally from free variables rather than from a precomputed CFG analysis. L->nests(def) holds iff def lives strictly inside L, i.e. it transitively depends on binders introduced below L; a def that only mentions things visible at L's level or further out is not nested.

Now the guard reads directly:

• var is a parameter of L = lam_of(var); its call sites live outside L.
• If L->nests(def), the joined value refers to binders that only come into existence within L's own body. Such a value simply does not exist at L's call sites, so propagating it into var — and thus substituting it at var's uses — would hoist a computation out of the region where its operands are defined. This is the exact situation dominance forbids, so the analysis pins var to ⊤ (pin) instead.
• If L does not nest def, the value is in scope at every call site — the analogue of "the definition dominates all uses" — and propagation is sound.

In other words, where classical SCCP walks a dominator tree to certify availability, MimIR asks a single scope question: is this value visible at the binder it would replace? Def::nests is that availability oracle, and it falls straight out of the free-variable structure that MimIR maintains anyway — no auxiliary dominance computation required.

Why this is hard elsewhere

The availability obligation is cheap to state but awkward to discharge in most IRs, and this is where MimIR's structural answer stands out.

• CFG + SSA answers it with the dominator tree, as sketched above. This works, but only because the CFG has already fixed where every value lives; the whole machinery presupposes a schedule.
• Sea-of-nodes deliberately refuses that commitment: data nodes float, and only control, φ, and memory nodes are pinned. That freedom is the entire point — it is what lets the optimizer move computations around without fighting a premature schedule. But it makes availability ill-posed: a floating expression has no location, so "is it available here?" is not even a well-formed question until the node is anchored. To answer it you must reason about where the expression's transitively control-pinned inputs would sit — that is, run (at least partial) global code motion and consult the CFG dominator relation. So copy/expression propagation drags the schedule — precisely what sea-of-nodes set out to avoid — back into the picture.

MimIR sidesteps the dilemma without introducing syntactic scope: it is a scopeless IR. There are no lexical scoping brackets that a Lam opens over its body; instead, scope is implicit, emerging from how free variables nest. Def::nests reads availability straight off that implicit nesting — L nests def iff def transitively depends on a variable bound below L — so the containment a lexical language would spell out with explicit brackets is recovered purely from the free-variable structure MimIR maintains anyway. The query is structural and commits to no schedule, so MimIR gets a compelling, schedule-free answer to the availability question that dominance-based and sea-of-nodes IRs can only reconstruct by (partially) scheduling first.

Transformation

#include "sccp.h"
 
namespace mim {
 
const Def* SCCP::rewrite_imm_App(const App* old_app) {
    if (auto old_lam = old_app->callee()->isa_mut<Lam>()) {
        if (auto l = lattice(old_lam->var()); l && l != old_lam->var()) {
            invalidate();
 
            size_t num_old = old_lam->num_tvars();
            Lam* new_lam;
            if (auto i = lam2lam_.find(old_lam); i != lam2lam_.end())
                new_lam = i->second;
            else {
                // build new dom
                auto new_doms = DefVec();
                for (size_t i = 0; i != num_old; ++i) {
                    auto old_var = old_lam->var(num_old, i);
                    auto abstr   = lattice(old_var);
                    if (old_var == abstr) new_doms.emplace_back(rewrite(old_lam->dom(num_old, i)));
                }
 
                // build new lam
                size_t num_new    = new_doms.size();
                auto new_vars     = absl::FixedArray<const Def*>(num_old);
                new_lam           = new_world().mut_lam(new_doms, rewrite(old_lam->codom()))->set(old_lam->dbg());
                lam2lam_[old_lam] = new_lam;
 
                // build new var
                for (size_t i = 0, j = 0; i != num_old; ++i) {
                    auto old_var = old_lam->var(num_old, i);
                    auto abstr   = lattice(old_var);
 
                    if (old_var == abstr) {
                        auto v      = new_lam->var(num_new, j++);
                        new_vars[i] = v;
                    } else {
                        new_vars[i] = rewrite(abstr); // SCCP propagate
                    }
                }
 
                map(old_lam->var(), new_vars);
                new_lam->set(rewrite(old_lam->filter()), rewrite(old_lam->body()));
            }
 
            // build new app
            size_t num_new = new_lam->num_vars();
            auto new_args  = absl::FixedArray<const Def*>(num_new);
            for (size_t i = 0, j = 0; i != num_old; ++i) {
                auto old_var = old_lam->var(num_old, i);
                auto abstr   = lattice(old_var);
                if (old_var == abstr) new_args[j++] = rewrite(old_app->targ(i));
            }
 
            return map(old_app, new_world().app(new_lam, new_args));
        }
    }
 
    return RWPhase::rewrite_imm_App(old_app);
}
 
} // namespace mim

Once the lattice is stable, the outer SCCP phase starts rewriting. During rewriting, it can query abstract values for old-world definitions through RWBase::lattice().

When it sees an application of a lambda whose parameters have propagated values, it rebuilds a specialized lambda:

• parameters with known propagated expressions are removed,
• remaining parameters are kept,
• the lambda body is rewritten with the propagated values substituted,
• the call site is rebuilt with only the remaining arguments.

So SCCP follows the standard RWPhase pattern:

1. analyze the old world,
2. rewrite into a new world using the computed facts,
3. swap worlds.

Discussion

Separating SCCP into analysis and rewrite keeps both parts simple:

• the analysis never mutates or partially rewrites the program,
• the rewrite does not need to discover facts on the fly,
• fixed-point logic stays in the analysis stage where it belongs,
• the handoff from analysis to rewrite is explicit through Analysis::lattice() and RWBase::lattice().

This separation is the main design pattern to follow for nontrivial optimizations.

Note

The complete SCCP example is roughly 150 lines of C++ source code. Most of the usual compiler boilerplate is absorbed by the existing Analysis, RWPhase, and Rewriter infrastructure, so the implementation can focus on the optimization itself.

Choosing the Right Base Class

A useful rule of thumb is:

• derive from Phase if you just need a custom one-off action,
• derive from Analysis if you want a graph-aware traversal that computes facts on the current world,
• derive from RWPhase if you want to rebuild the world into a transformed new one, optionally consuming facts from an associated Analysis,
• derive from InplaceRWPhase if your rewrite is type-preserving and local, so that paying for a full rebuild would be wasteful,
• derive from ClosedMutPhase if you want to visit all reachable closed mutables,
• derive from NestPhase if that visit should come with a computed Nest.

Recommended Design Pattern

For most optimization phases, the preferred structure is:

1. write an Analysis that computes facts to a fixed point,
2. store those facts in Analysis::lattice() and/or auxiliary tables,
3. write an RWPhase that consumes those facts while rebuilding the world.

This keeps analyses and transformations cleanly separated and fits naturally with MimIR's rewriting-based infrastructure.

Minimal Examples

A simple whole-world rewrite phase:

class Simplify : public mim::RWPhase {
public:
    Simplify(mim::World& world)
        : RWPhase(world, "simplify") {}
 
private:
    const mim::Def* rewrite_imm_App(const mim::App* app) override {
        // rewrite or simplify selected applications
        // fallback:
        return Rewriter::rewrite_imm_App(app);
    }
};

A simple analysis phase:

class CountMutLams : public mim::Analysis {
public:
    CountMutLams(mim::World& world)
        : Analysis(world, "count_lams") {}
 
    size_t num_lams = 0;
 
private:
    // Note: override rewrite_mut - the node-specific rewrite_mut_* hooks are not dispatched
    // for an Analysis (see "Handling of Mutables").
    mim::Def* rewrite_mut(mim::Def* mut) override {
        if (!lookup(mut) && mut->isa_mut<mim::Lam>()) ++num_lams; // count on first visit only
        return mim::Analysis::rewrite_mut(mut);
    }
};

Using both:

CountMutLams analysis(world);
analysis.run();
 
mim::Phase::run<Simplify>(world);

Compilation Pipelines in M⁠im

You can also expose your custom phases as axioms in Mim via the compile plugin and build your own compilation pipeline. Mim's default compilation pipeline is defined in the opt plugin.

Summary

Phases are MimIR's main unit of compiler work.

• Phase is the minimal base abstraction.
• Analysis is for graph-aware fact collection on the current world and provides a reusable lattice() for abstract values.
• RWPhase is for rewriting the current world into a transformed new one and can read analysis results through RWBase::lattice().
• InplaceRWPhase is for type-preserving, local rewrites of the current world that must not pay for a rebuild.
• PhaseMan sequences phases, optionally to a fixed point.
• ClosedMutPhase and NestPhase are traversal helpers for common whole-world inspections.

The key design idea is that MimIR phases are built around structured traversal and rewriting. For substantial optimizations, the usual pattern is:

• compute facts with Analysis,
• store them in Analysis::lattice(),
• consume them with RWPhase.

Previous	Next
Rewriting	Python Bindings