phase.h

Go to the documentation of this file.

#pragma once
 
#include <memory>
 
#include <fe/cast.h>
#include <fe/term.h>
 
#include "mim/def.h"
#include "mim/nest.h"
#include "mim/rewrite.h"
#include "mim/world.h"
 
namespace mim {
 
class Phase;
class PhaseMan;
 
using Phases = std::deque<std::unique_ptr<Phase>>;
 
/// A Phase performs one self-contained task over the whole World.
/// Phases are intended to run in a classical sequence, one after another.
/// @see @ref phases_phase
class Phase : public fe::RuntimeCast<Phase> {
public:
    /// @name Construction & Destruction
    ///@{
    Phase(World& world, std::string name)
        : world_(world)
        , name_(std::move(name)) {}
    Phase(World& world, flags_t annex);
 
    virtual ~Phase() = default;
 
    virtual std::unique_ptr<Phase> recreate(); ///< Creates a new instance; needed by a fixed-point PhaseMan.
    virtual void apply(const App*) {}          ///< Invoked if your Phase has additional args.
    virtual void apply(Phase&) {}              ///< Dito, but invoked by Phase::recreate.
 
    /// @name Redirection
    /// A Phase may resolve to a *different* Phase (or to nothing) after Phase::apply.
    /// This is used by the `compile.named` stage that resolves a string to another plugin's annex.
    ///@{
    virtual bool redirects() const { return false; } ///< If `true`, Phase::create uses take_resolved().
    virtual std::unique_ptr<Phase> take_resolved() {
        return {};
    } ///< The Phase to use instead; `nullptr` means *elide*.
    ///@}
 
    static std::unique_ptr<Phase> create(const Flags2Phases& phases, const Def* def);
 
    template<class A, class P>
    static void hook(Flags2Phases& phases) {
        fe::assert_emplace(phases, Annex::base<A>(), [](World& w) { return std::make_unique<P>(w, Annex::base<A>()); });
    }
    ///@}
 
    /// @name Getters
    ///@{
    World& world() { return world_; }
    Driver& driver() { return world().driver(); }
    const fe::Log& log() const { return world_.log(); }
    std::string_view name() const { return name_; }
    flags_t annex() const { return annex_; }
 
    /// Command-line arguments passed to this Phase's plugin via `-X <plugin>:<arg>`.
    /// Derived from Phase::annex; yields an empty fe::Vector for name-constructed Phase%s.
    const fe::Vector<std::string>& args();
    ///@}
 
    /// @name Fixed-Point Handling
    ///@{
    bool todo() const { return todo_; }
 
    /// Signals that another round of fixed-point iteration is required, either
    /// as part of
    /// - a pipeline managed by PhaseMan, or
    /// - the optional pre-analysis of an RWPhase.
    ///
    /// Calling `invalidate(todo)` bitwise-ORs @p todo into the internal `todo_` flag.
    void invalidate(bool todo = true) { todo_ |= todo; }
    ///@}
 
    /// @name run
    ///@{
    virtual void run();       ///< Entry point and generates some debug output; invokes Phase::start.
    virtual void start() = 0; ///< Actual entry.
 
    /// Runs a single Phase.
    template<class P, class... Args>
    static void run(Args&&... args) {
        P p(std::forward<Args>(args)...);
        p.run();
    }
 
    /// Adds @p n to the custom fe::Profiler counter @p key of the current run; no-op unless profiling is enabled.
    void profile_count(std::string_view key, uint64_t n = 1);
    ///@}
 
private:
    World& world_;
    flags_t annex_ = 0;
    bool todo_     = false;
 
protected:
    std::string name_;
 
    friend class Analysis;
};
 
/// Traverses the current World using Rewriter infrastructure while staying in the same world.
///
/// It recursively rewrites all World::externals() but treats World::Annexes::opaque() annexes as opaque.
///
/// Analysis provides a reusable lattice() mapping old Def%s to abstract values, represented as ordinary MimIR Def%s.
///
/// Fixed-point iteration is *sparse* by default:
/// whenever a lattice write changes observable information, the mutable currently being drained is recorded as *dirty*.
/// The next round then re-drains only those dirty mutables - plus everything reachable from them - instead of walking
/// the whole World. At the start of such a 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. 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.
/// That replay only *prunes* the walk; what the lattice means is applied by rewrite() through repr(), in every kind of
/// round alike - see repr() for why an analysis whose values are expressions needs that.
/// @note You can override
/// - Rewriter::rewrite(),
/// - Rewriter::rewrite_imm(),
/// - Rewriter::rewrite_mut(), etc.
/// @see @ref phases_analysis
/// @see @ref ssa-without-dominance for how an Analysis substitutes Def::nests for the classical SSA dominance check.
class Analysis : public Phase, public Rewriter {
public:
    /// @name Construction & Destruction
    ///@{
    Analysis(World& world, std::string name)
        : Phase(world, std::move(name))
        , Rewriter(world) {}
    Analysis(World& world, flags_t annex)
        : Phase(world, annex)
        , Rewriter(world) {}
 
    /// Clears the rewriter map and resets Phase::todo() for the next fixed-point iteration.
    /// lattice() is **preserved** across iterations so that abstract values accumulated in earlier
    /// rounds remain available - this is what makes fixed-point convergence possible.
    /// The dirty set survives as well; start() consumes it to decide whether the round can be sparse.
    /// @see RWPhase::analyze
    virtual void reset();
    ///@}
 
    /// @name Getters
    ///@{
    using Phase::world; ///< Disambiguates the Phase/Rewriter double base; for an Analysis both denote the same World.
    ///@}
 
    /// @name Sparse Fixed-Point Iteration
    ///@{
    void make_dense() { dense_ = true; } ///< Forces whole-World rounds unconditionally.
    /// Bumped on every observable lattice change; snapshot it around a code region to detect changes.
    size_t version() const { return version_; }
    ///@}
 
    /// @name lattice
    /// Conventions: *absent* = ⊥ (nothing known); `def ↦ def` = ⊤ (keep as is).
    /// Subclasses may store their own sentinels in between as ordinary Def%s (e.g. SEO's GVN-bundle Proxy%s).
    ///@{
    const auto& lattice() const { return lattice_; } ///< The whole map; used e.g. to diff two fixed-point runs.
 
    /// @returns the abstract value recorded for @p def, or `nullptr` if unknown.
    const Def* lattice(const Def* def) const {
        if (auto abstr = fe::lookup(lattice_, def)) return abstr;
        return is_singleton(def) ? def : nullptr;
    }
 
    /// The representative of @p def: follows `def ↦ lattice(def)` to the end of its chain.
    ///
    /// The lattice records *expressions*, so one and the same abstract value can be spelled at several depths
    /// of a chain (a var, and the value it was propagated to).
    /// repr() collapses those spellings to one def, so that comparing two of them answers whether they mean the same
    /// value - not whether they were derived by the same route. This is union-find's *find* without the path
    /// compression: the chain is what the lattice means, and its links keep changing between rounds - see
    /// Analysis::lattice_force.
    const Def* repr(const Def* def) const {
        assert(!is_cyclic(def) && "lattice chain must not loop");
        for (auto next = follow(def); next != def; def = next, next = follow(def)) {}
        return def;
    }
 
    /// @returns whether @p def is pinned to ⊤ (`def ↦ def`).
    bool is_top(const Def* def) const {
        auto i = lattice_.find(def);
        return i != lattice_.end() && i->second == def;
    }
    ///@}
 
protected:
    /// @name lattice
    ///@{
 
    /// The sole inhabitant of a singleton type is ⊤ and shared by all binders of that type, so it is never recorded.
    static bool is_singleton(const Def* def) { return def->world().inhabitant(def->type()) == def; }
 
    /// **Non-monotone** write of `concr ↦ abstr` into lattice() and map().
    /// This is the escape hatch for analyses that must overwrite an earlier round's value (descending from ⊤ is fine).
    /// invalidate()s iff the stored value changed; an *absent* entry counts as changed - even for ⊤ -
    /// since a non-monotone lattice's consumers may well distinguish ⊥ from ⊤.
    /// Every change also touch()es curr_mut() - the seed set of the next sparse round.
    /// @returns `true` iff this changed the entry - i.e. iff it invalidate()d.
    bool lattice_force(const Def* concr, const Def* abstr);
 
    /// **Non-monotone** removal of @p concr from lattice(), so no later sparse round replays it.
    /// Like lattice_force, a removal invalidate()s and touch()es curr_mut().
    /// @returns `true` iff @p concr had an entry.
    bool lattice_erase(const Def* concr) {
        if (!lattice_.erase(concr)) return false;
        return touch(), true;
    }
 
    /// Writes `concr ↦ abstr` into lattice() and map().
    /// invalidate()s - and thereby triggers another fixed-point round - iff this changes observable information:
    /// an existing entry was overwritten, or a fresh fact other than ⊤ was inserted.
    /// Freshly inserting ⊤ (`concr ↦ concr`) stays silent, as it is indistinguishable from *absent* for consumers.
    /// Every change also touch()es curr_mut() - the seed set of the next sparse round.
    /// @returns `true` iff this changed observable information - i.e. iff it invalidate()d.
    bool lattice(const Def* concr, const Def* abstr);
 
    /// Monotonically forces @p def to ⊤ (keep as is).
    /// @returns `true` iff this changed observable information - i.e. iff it invalidate()d.
    bool pin(const Def* def) { return lattice(def, def); }
 
    /// pin%s every def in @p def%'s immutable subgraph for which @p pinnable holds.
    /// Mutables are visited but not descended into; defs already in @p visited are skipped.
    void pin_imm(DefSet& visited, const Def* def, DefPred auto pinnable) {
        if (!visited.emplace(def).second) return;
        if (pinnable(def)) pin(def);
        if (def->isa_mut()) return;
        for (auto d : def->deps())
            pin_imm(visited, d, pinnable);
    }
 
    void pin_imm(const Def* def, DefPred auto pinnable) {
        auto visited = DefSet();
        pin_imm(visited, def, pinnable);
    }
 
    /// Additionally schedules @p mut for the next sparse round.
    /// Use this when a lattice change must re-visit *other* mutables than curr_mut() -
    /// e.g. all call sites of a Lam whose var's abstract value changed.
    void taint(Def* mut) { dirty_.emplace(mut); }
 
    /// Observable analysis information changed: records curr_mut() as *dirty* - the seed set of the next sparse
    /// round - and invalidate()s. Outside of any mutable (e.g. in finalize()) the change cannot be
    /// attributed to a mutable; then the next round falls back to a full one.
    /// The lattice writes above do this for you; call it directly when a subclass keeps facts of its own.
    void touch() {
        ++version_;
        if (auto mut = curr_mut())
            dirty_.emplace(mut);
        else
            nonlocal_ = true;
        invalidate();
    }
    ///@}
 
    /// @name Rewrite
    ///@{
    void start() override;
    virtual void prepare() {} ///< Run **before** the main analysis.
    /// Run **after** the main analysis - only in **full** rounds, so it always sees the complete abstract World.
    virtual void finalize() {}
    virtual void rewrite_external(Def*);
    const Def* lookup(const Def*) override;
    const Def* rewrite_imm_Proxy(const Proxy* proxy) override { return proxy; } ///< By default: ignore Proxy%s.
 
    /// Rewrites @p def and then maps the result to its repr().
    ///
    /// This is how the lattice is applied: at the *point of use*, and only after the structural rewrite - so an
    /// Analysis's hooks always see the program itself. Pre-installing the substitutions into map() instead
    /// would skip those hooks, and only a sparse round would do so - putting the two kinds of round in
    /// different regimes, where they spell one and the same abstract value differently.
    const Def* rewrite(const Def*) override;
 
    /// Schedules @p mut for a breadth-first visit of its dependencies and records `mut -> mut`.
    /// Mutables are enqueued instead of recursed into; Analysis::drain then walks them in BFS order.
    /// The `mut -> mut` entry doubles as the per-round "already scheduled" marker (Rewriter::scopes_ are
    /// cleared by reset()), so each mutable's deps are visited at most once per fixed-point round.
    /// Then dispatches to the rewrite_mut_* hook, which merely observes @p mut.
    const Def* rewrite_mut(Def*) final;
 
#define CODE_MUT(N) \
    const Def* rewrite_mut_##N(N* mut) override { return mut; }
    MIM_MUT_NODE(CODE_MUT)
#undef CODE_MUT
    virtual void leave() {} ///< Called after curr_mut() has been completely dealt with.
    ///@}
 
private:
    /// The next def on @p def's chain, or @p def itself if it ends it (⊥ or ⊤).
    const Def* follow(const Def* def) const {
        auto i = lattice_.find(def);
        return i == lattice_.end() ? def : i->second;
    }
 
    bool is_cyclic(const Def* def) const;
 
    /// Walks all enqueued mutables' dependencies - in BFS order - under each mutable's curr_mut() scope.
    void drain();
 
    Def2Def lattice_;
    std::deque<Def*> worklist_;
    MutSet dirty_;               ///< Muts whose drain changed the lattice this round; seeds the next sparse round.
    size_t version_     = 0;     ///< @see version()
    bool nonlocal_      = false; ///< The lattice changed outside of any mut; the next round must be a full one.
    bool curr_sparse_   = false; ///< Is the current round sparse?
    bool dense_         = false; ///< @see make_dense()
    size_t num_drained_ = 0;     ///< muts drained this round; flushed into the fe::Profiler
};
 
/// Rebuilds old_world() into new_world() and then swaps them.
///
/// It is a Phase *and* a Rewriter that runs an optional analyze() to a fixed point.
/// Then, it rewrites all old World::externals().
/// An World::Annexes::opaque() annex is not rewritten but resolved to the annex of the same flags in new_world().
///
/// If an associated Analysis is provided, the rewrite can query its abstract results through lattice().
///
/// @note You can override
/// - Rewriter::rewrite(),
/// - Rewriter::rewrite_imm(),
/// - Rewriter::rewrite_mut(), etc.
/// @see @ref phases_rwphase
class RWPhase : public Phase, public Rewriter {
public:
    /// @name Construction
    ///@{
    RWPhase(World& world, std::string name, Analysis* analysis = nullptr)
        : RWPhase(world, std::move(name), analysis, world.inherit()) {}
    RWPhase(World& world, flags_t annex, Analysis* analysis = nullptr)
        : RWPhase(world, annex, analysis, world.inherit()) {}
    ///@}
 
    /// @name Analysis
    ///@{
    Analysis* analysis() { return analysis_; }
    const Analysis* analysis() const { return analysis_; }
 
    /// Returns the abstract value computed by the associated Analysis for the given old-world Def, or `nullptr` if no
    /// value is available.
    const Def* lattice(const Def* old_def) const { return analysis_ ? analysis_->lattice(old_def) : nullptr; }
 
    /// Returns lattice(@p old_def) if it differs from @p old_def (i.e. we learned something), otherwise `nullptr`.
    const Def* abstracted(const Def* old_def) const {
        auto l = lattice(old_def);
        return l && l != old_def ? l : nullptr;
    }
 
    bool is_top(const Def* old_def) const { return analysis_->is_top(old_def); }
 
    /// Runs the optional pre-analysis on old_world(), typically to a fixed point, before rewriting begins.
    ///
    /// If analysis() is set, this is the natural place to iterate until Phase::todo() becomes `false`.
    /// If no Analysis is needed, simply return `false`.
    virtual bool analyze();
    ///@}
 
    /// @name Rewrite
    ///@{
    virtual void rewrite_external(Def*);
    const Def* lookup(const Def*) override;
    ///@}
 
    /// @name World
    /// * Phase::world is the **old** one.
    /// * Rewriter::world is the **new** one.
    /// * RWPhase::world is deleted to not confuse this.
    ///@{
    using Phase::world;
    using Rewriter::world;
    World& world() = delete;                         ///< Hides both and forbids direct access.
    World& old_world() { return Phase::world(); }    ///< Get **old** Def%s from here.
    World& new_world() { return Rewriter::world(); } ///< Create **new** Def%s into this.
    ///@}
 
protected:
    void start() override;
 
    /// @name Coercion
    /// Every checking position - an App's argument, a Tuple's ops, a Lam's body - coerce()s its value.
    /// This reconciles a representation the phase changed with one it did not, e.g. an Axm's signature.
    ///@{
    const Def* rewrite_imm_App(const App*) override;
    const Def* rewrite_imm_Tuple(const Tuple*) override;
    const Def* rewrite_stub(Def*, Def*) override;
    using Rewriter::rewrite_stub;
 
    /// Converts the *new* @p new_val into a value of the *new* @p new_type, where a checking position demands it.
    /// Both are matched leaf by leaf: tuples are exploded and reassembled, Pi%s are η-wrapped, and
    /// information-free components are dropped or filled in with their sole inhabitant.
    const Def* coerce(const Def* new_type, const Def* new_val);
    /// Does coerce() explode and reassemble values of @p type?
    static bool splittable(const Def* type) {
        return (type->isa<Sigma>() || type->isa_imm<Arr>()) && type->num_tprojs() != 1;
    }
    ///@}
 
    /// Run **after** all roots have been walked but still **before** the two worlds are swapped.
    /// This is where you drain a worklist of rewrites your hooks deferred (see e.g. clos::phase::ClosConv).
    virtual void finalize() {}
 
private:
    RWPhase(World& world, std::string name, Analysis* analysis, std::unique_ptr<World>&& new_world)
        : Phase(world, std::move(name))
        , Rewriter(*new_world)
        , analysis_(analysis)
        , new_world_(std::move(new_world)) {}
    RWPhase(World& world, flags_t annex, Analysis* analysis, std::unique_ptr<World>&& new_world)
        : Phase(world, annex)
        , Rewriter(*new_world)
        , analysis_(analysis)
        , new_world_(std::move(new_world)) {}
 
    /// η-wraps @p val into a Lam of @p type, coerce()ing its Var to @p val%'s domain and its result to the codomain.
    /// @returns `nullptr` unless both @p val%'s type and @p type are Pi%s.
    const Def* eta_coerce(const Def* type, const Def* val);
    /// Builds a value of @p type from the top of the stack @p todo.
    /// Greedy matching is sound as assignable types share their leaves.
    const Def* reshape(DefVec& todo, const Def* type);
 
    DefMap<Def2Def> etas_; ///< type ↦ val ↦ eta_coerce(type, val)
 
    Analysis* analysis_;
    std::unique_ptr<World> new_world_; ///< Owns Rewriter::world.
};
 
/// An RWPhase that searches for a pattern and replaces it.
/// Implement the replace() hook - or use the MIM_REPL macro for an inline definition.
class Repl : public RWPhase {
public:
    using RWPhase::RWPhase;
 
    /// replace() inspects and builds Def%s of the **old** world; the RWPhase machinery carries the result over.
    World& world() { return old_world(); }
 
    /// @returns the replacement or `nullptr` if the pattern does not match.
    virtual const Def* replace(const Def* def) = 0;
 
private:
    const Def* rewrite(const Def* def) final {
        while (auto subst = replace(def))
            def = subst;
 
        return Rewriter::rewrite(def);
    }
};
 
#define MIM_CONCAT_INNER(a, b) a##b
#define MIM_CONCAT(a, b)       MIM_CONCAT_INNER(a, b)
 
#define MIM_REPL(__phases, __annex, ...) MIM_REPL_IMPL(__phases, __annex, __LINE__, __VA_ARGS__)
 
// clang-format off
#define MIM_REPL_IMPL(__phases, __annex, __id, ...)                         \
    struct MIM_CONCAT(Repl_, __id) : ::mim::Repl {                          \
        using Repl::Repl;                                                   \
                                                                            \
        const ::mim::Def* replace(const ::mim::Def* def) final __VA_ARGS__  \
    };                                                                      \
    ::mim::Phase::hook<__annex, MIM_CONCAT(Repl_, __id)>(__phases)
// clang-format on
 
/// Removes unreachable and dead code by rebuilding the whole World into a new one and `swap`ping them afterwards.
/// @see @ref phases_rwphase
class Cleanup : public RWPhase {
public:
    using RWPhase::RWPhase;
};
 
/// Organizes several Phase%s into a pipeline.
/// If fixed_point() is `true`, rerun the whole pipeline until all Phase::todo()%s flags remain `false`.
/// @see @ref phases_phase_man
class PhaseMan : public Phase {
public:
    /// @name Construction
    ///@{
    PhaseMan(World& world, flags_t annex)
        : Phase(world, annex) {}
 
    void apply(bool, Phases&&);
    void apply(const App*) final;
    void apply(Phase&) final;
    ///@}
 
    /// @name Getters
    ///@{
    bool fixed_point() const { return fixed_point_; }
    auto& phases() { return phases_; }
    const auto& phases() const { return phases_; }
    ///@}
 
private:
    void start() final;
 
    Phases phases_;
    bool fixed_point_;
};
 
/// Transitively visits all *reachable*, [*closed*](@ref Def::is_closed) mutables in the World.
/// * Select with `elide_empty` whether you want to visit trivial mutables without body.
/// * Set `schedule` if the mutables should be scheduled to ensure a correct order of dependencies.
/// * If you are only interested in specific mutables, you can pass this to @p M.
/// @see @ref phases_closed_mut_phase
template<class M = Def>
class ClosedMutPhase : public Phase {
public:
    ClosedMutPhase(World& world, std::string name, bool elide_empty, bool schedule = false)
        : Phase(world, std::move(name))
        , elide_empty_(elide_empty)
        , schedule_(schedule) {}
    ClosedMutPhase(World& world, flags_t annex, bool elide_empty, bool schedule = false)
        : Phase(world, annex)
        , elide_empty_(elide_empty)
        , schedule_(schedule) {}
 
    bool elide_empty() const { return elide_empty_; }
    bool schedule() const { return schedule_; }
 
protected:
    void start() override {
        world().template for_each<M>(elide_empty(), [this](M* mut) { root_ = mut, visit(mut); }, schedule());
    }
    virtual void visit(M*) = 0;
    M* root() const { return root_; }
 
private:
    const bool elide_empty_;
    const bool schedule_;
    M* root_;
};
 
/// Like ClosedMutPhase but computes a Nest for each NestPhase::visit.
/// @see @ref phases_nest_phase
template<class M = Def>
class NestPhase : public ClosedMutPhase<M> {
public:
    NestPhase(World& world, std::string name, bool elide_empty, bool schedule = false)
        : ClosedMutPhase<M>(world, std::move(name), elide_empty, schedule) {}
    NestPhase(World& world, flags_t annex, bool elide_empty, bool schedule = false)
        : ClosedMutPhase<M>(world, annex, elide_empty, schedule) {}
 
    const Nest& nest() const { return *nest_; }
    virtual void visit(const Nest&) = 0;
 
private:
    void visit(M* mut) final {
        Nest nest(mut);
        nest_ = &nest;
        visit(nest);
    }
 
    const Nest* nest_;
};
 
} // namespace mim