Phases

Table of Contents

• Overview
• Phase
  • Typical Shape
• Analysis
  • Lattice API
  • Handling of Mutables
  • Sparse Fixed-Point Iteration
  • Reset Between Iterations
• RWPhase
  • Cleanup
  • Execution Model
  • Optional Pre-Analysis
  • Analysis Results
  • Bootstrapping
  • Typical Shape
• PhaseMan
  • Typical Shape
• ClosedMutPhase
  • Typical Shape
  • NestPhase
• Example: SCCP
  • Analysis
  • SSA without Dominance
    • Why the guard exists at all
    • The classical picture
    • The MimIR picture
    • Why this is hard elsewhere
  • Transformation
  • Discussion
• Choosing the Right Base Class
• Recommended Design Pattern
• Minimal Examples
  • Compilation Pipelines in M⁠im
• Summary

At a high level, a phase is an isolated compiler transformation or analysis step. Phases are intended to do one thing at a time and to 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.
• RWPhase 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 internal lattice(), which stores abstract information for old-world Defs as a Def2Def mapping.

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".
• Anything else is a discovered abstract value; analyses may also introduce their own sentinels in between as ordinary Defs (e.g. 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 seed the rewriter map, so a later rewrite() of concr immediately returns abstr. It asserts, if you go down 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 simply rewrite() the callee: this schedules the callee (or is a no-op if already scheduled) so its body is walked later during the drain, by which point the seeded facts — and any joins contributed by 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.

Only the first round (and certification rounds, see below) is full; a follow-up round is sparse: it re-drains only the 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.

RWPhase

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

It inherits from both Phase and Rewriter, but here the 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.

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.

Execution Model

An RWPhase runs in three conceptual steps:

1. optionally perform a fixed-point analysis on the old world,
2. rewrite reachable old Defs into the new world:
   1. rewrite annex roots,
   2. rewrite external mutables;
3. swap the old and new worlds.

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

Optional Pre-Analysis

An RWPhase 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 old world,
• those facts are stored in Analysis::lattice() and/or auxiliary side tables,
• the rewrite queries them through RWPhase::lattice() and produces the new world.

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

Analysis Results

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

This provides read access to the analysis lattice for old-world Defs: given an old definition, RWPhase::lattice() 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, RWPhase processes annex roots before externals.

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

This matters because annexes may depend on one another. During bootstrapping, rewrites that refer to other annexes may need to be deferred or skipped, since those annexes might not yet exist in the new world.

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);

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. Since a phase's run is a deterministic function of the World's content, PhaseMan skips any phase whose last run was quiet and after which no other phase changed the world - so tail iterations only rerun the phases that are still making progress, and the pipeline terminates without a final everybody-reruns round.

Before a rerun, the phase is recreated from its original configuration. This keeps phase-local state from leaking across rounds unless the phase explicitly recomputes 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);
        DLOG("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 ever introducing a 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 RWPhase::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 RWPhase::lattice().

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

Note

The complete SCCP example fits into 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 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 RWPhase::lattice().
• 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.