Traverses the current World using Rewriter infrastructure while staying in the same world. More...

#include <mim/phase.h>

Inheritance diagram for mim::Analysis:

Public Member Functions
Construction & Destruction
	Analysis (World &world, std::string name)
	Analysis (World &world, flags_t annex)
virtual void	reset ()
	Clears the rewriter map and resets Phase::todo() for the next fixed-point iteration.
Sparse Fixed-Point Iteration
< Disambiguates the Phase/Rewriter double base; for an Analysis both denote the same World.
void	make_dense ()
	Forces whole-World rounds unconditionally.
size_t	version () const
	Bumped on every observable lattice change; snapshot it around a code region to detect changes.
Getters
World &	world ()
Public Member Functions inherited from mim::Phase
	Phase (World &world, std::string 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.
virtual bool	redirects () const
	If true, Phase::create uses take_resolved().
virtual std::unique_ptr< Phase >	take_resolved ()
	The Phase to use instead; nullptr means elide.
World &	world ()
Driver &	driver ()
const fe::Log &	log () const
std::string_view	name () const
flags_t	annex () const
const fe::Vector< std::string > &	args ()
	Command-line arguments passed to this Phase's plugin via -X <plugin>:<arg>.
bool	todo () const
void	invalidate (bool todo=true)
	Signals that another round of fixed-point iteration is required, either as part of.
virtual void	run ()
	Entry point and generates some debug output; invokes Phase::start.
void	profile_count (std::string_view key, uint64_t n=1)
	Adds `n` to the custom fe::Profiler counter `key` of the current run; no-op unless profiling is enabled.
Public Member Functions inherited from mim::Rewriter
template<class D = Def>
D *	curr_mut () const
	Rewriter (World &world)
virtual	~Rewriter ()
void	reset ()
World &	world ()
void	push (Vars old_vars={}, Vars new_vars={})
void	pop ()
void	bind_old (const Var *var)
	Adds the old `var` - if any - to the innermost scope.
void	bind_new (const Var *var)
	Adds the new `var` - if any - to the innermost scope.
void	bind (const Var old_var, const Var new_var)
const Def *	map (const Def old_def, const Def new_def)
const Def *	map (const Def *old_def, Defs new_defs)
const Def *	map (Defs old_defs, const Def *new_def)
const Def *	map (Defs old_defs, Defs new_defs)
virtual const Def *	rewrite_imm (const Def *)
virtual const Def *	rewrite_stub (Def , Def )
const Def *	rewrite_stub (Def old_mut, Def new_mut, fe::View< size_t > new2old)
	Like above, but `new_mut` may have a different number of ops than `old_mut:` new_mut->op(i) is rewritten from old_mut->op(new2old[i]).
virtual DefVec	rewrite (Defs)
virtual const Def *	rewrite_imm_Lit (const Lit *)
virtual const Def *	rewrite_imm_Axm (const Axm *)
virtual const Def *	rewrite_imm_Var (const Var *)
virtual const Def *	rewrite_imm_Type (const Type *)
virtual const Def *	rewrite_imm_Level (const Level *)
virtual const Def *	rewrite_imm_LMax (const LMax *)
virtual const Def *	rewrite_imm_LSucc (const LSucc *)
virtual const Def *	rewrite_imm_Pi (const Pi *)
virtual const Def *	rewrite_imm_Lam (const Lam *)
virtual const Def *	rewrite_imm_App (const App *)
virtual const Def *	rewrite_imm_Sigma (const Sigma *)
virtual const Def *	rewrite_imm_Tuple (const Tuple *)
virtual const Def *	rewrite_imm_Extract (const Extract *)
virtual const Def *	rewrite_imm_Insert (const Insert *)
virtual const Def *	rewrite_imm_Arr (const Arr *)
virtual const Def *	rewrite_imm_Pack (const Pack *)
virtual const Def *	rewrite_imm_Join (const Join *)
virtual const Def *	rewrite_imm_Inj (const Inj *)
virtual const Def *	rewrite_imm_Match (const Match *)
virtual const Def *	rewrite_imm_Variant (const Variant *)
virtual const Def *	rewrite_imm_Top (const Top *)
virtual const Def *	rewrite_imm_Bot (const Bot *)
virtual const Def *	rewrite_imm_Reform (const Reform *)
virtual const Def *	rewrite_imm_Rule (const Rule *)
virtual const Def *	rewrite_imm_Single (const Single *)
virtual const Def *	rewrite_imm_Wrap (const Wrap *)
virtual const Def *	rewrite_imm_Nat (const Nat *)
virtual const Def *	rewrite_imm_Idx (const Idx *)
virtual const Def *	rewrite_imm_Nom (const Nom *)
virtual const Def *	rewrite_imm_Name (const Name *)
virtual const Def *	rewrite_imm_Struc (const Struc *)
virtual const Def *	rewrite_imm_Seq (const Seq *seq)
virtual const Def *	rewrite_mut_Seq (Seq *seq)

Protected Member Functions
Rewrite
void	start () override
	Actual entry.
virtual void	prepare ()
	Run before the main analysis.
virtual void	finalize ()
	Run after the main analysis - only in full rounds, so it always sees the complete abstract World.
virtual void	rewrite_external (Def *)
const Def *	lookup (const Def *) override
	Lookup old_def by searching in reverse through the stack of maps.
const Def *	rewrite_imm_Proxy (const Proxy *proxy) override
	By default: ignore Proxys.
const Def *	rewrite (const Def *) override
	Rewrites `def` and then maps the result to its repr().
const Def *	rewrite_mut (Def *) final
	Schedules `mut` for a breadth-first visit of its dependencies and records mut -> mut.
const Def *	rewrite_mut_Hole (Hole *mut) override
const Def *	rewrite_mut_Pi (Pi *mut) override
const Def *	rewrite_mut_Lam (Lam *mut) override
const Def *	rewrite_mut_Sigma (Sigma *mut) override
const Def *	rewrite_mut_Arr (Arr *mut) override
const Def *	rewrite_mut_Pack (Pack *mut) override
const Def *	rewrite_mut_Variant (Variant *mut) override
const Def *	rewrite_mut_Rule (Rule *mut) override
virtual void	leave ()
	Called after curr_mut() has been completely dealt with.
Protected Member Functions inherited from mim::Rewriter
Def2Def &	old2new ()
	The map of the innermost push() scope.
bool	has_intersection (const Def *old_def)
	Does `old_def` depend on the old Vars of any scope?
auto	enter (Def *new_mut)
	Updates curr_mut() to `new_mut` and restores it at the end of the scope.
const Def *	seal (Def old_mut, Def new_mut)
	The tail of rewrite_stub: immutabilizes `new_mut` in hindsight, as rewriting may have made it vacuous.

lattice
const auto &	lattice () const
	The whole map; used e.g. to diff two fixed-point runs.
const Def *	lattice (const Def *def) const
const Def *	repr (const Def *def) const
	The representative of `def:` follows def ↦ lattice(def) to the end of its chain.
bool	is_top (const Def *def) const
static bool	is_singleton (const Def *def)
	The sole inhabitant of a singleton type is ⊤ and shared by all binders of that type, so it is never recorded.
bool	lattice_force (const Def concr, const Def abstr)
	Non-monotone write of concr ↦ abstr into lattice() and map().
bool	lattice_erase (const Def *concr)
	Non-monotone removal of `concr` from lattice(), so no later sparse round replays it.
bool	lattice (const Def concr, const Def abstr)
	Writes concr ↦ abstr into lattice() and map().
bool	pin (const Def *def)
	Monotonically forces `def` to ⊤ (keep as is).
void	pin_imm (DefSet &visited, const Def *def, DefPred auto pinnable)
	pins every def in `def's` immutable subgraph for which `pinnable` holds.
void	pin_imm (const Def *def, DefPred auto pinnable)
void	taint (Def *mut)
	Additionally schedules `mut` for the next sparse round.
void	touch ()
	Observable analysis information changed: records curr_mut() as dirty - the seed set of the next sparse round - and invalidate()s.

Additional Inherited Members
Static Public Member Functions inherited from mim::Phase
static std::unique_ptr< Phase >	create (const Flags2Phases &phases, const Def *def)
template<class A, class P>
static void	hook (Flags2Phases &phases)
template<class P, class... Args>
static void	run (Args &&... args)
	Runs a single Phase.
Protected Attributes inherited from mim::Phase
std::string	name_
Protected Attributes inherited from mim::Rewriter
fe::Vector< Scope >	scopes_

Detailed Description

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 Defs to abstract values, represented as ordinary MimIR Defs.

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

See also: Analysis; SSA without Dominance for how an Analysis substitutes Def::nests for the classical SSA dominance check.

Definition at line 130 of file phase.h.

Constructor & Destructor Documentation

◆ Analysis() [1/2]

mim::Analysis::Analysis	(	World &	world,
		std::string	name )

inline

Definition at line 134 of file phase.h.

References mim::Phase::name(), mim::Phase::Phase(), mim::Rewriter::Rewriter(), and world().

Referenced by mim::plug::mem::EscapeAnalysis::EscapeAnalysis().

◆ Analysis() [2/2]

mim::Analysis::Analysis	(	World &	world,
		flags_t	annex )

inline

Definition at line 137 of file phase.h.

References mim::Phase::annex(), mim::Phase::Phase(), mim::Rewriter::Rewriter(), and world().

Member Function Documentation

◆ finalize()

virtual void mim::Analysis::finalize ( )

inlineprotectedvirtual

Run after the main analysis - only in full rounds, so it always sees the complete abstract World.

Definition at line 268 of file phase.h.

Referenced by start().

◆ is_singleton()

bool mim::Analysis::is_singleton ( const Def * def )

inlinestaticprotected

The sole inhabitant of a singleton type is ⊤ and shared by all binders of that type, so it is never recorded.

Definition at line 199 of file phase.h.

References mim::World::inhabitant(), mim::Def::type(), and mim::Def::world().

Referenced by lattice(), lattice(), and lattice_force().

◆ is_top()

bool mim::Analysis::is_top ( const Def * def ) const

inline

Returns: whether def is pinned to ⊤ (def ↦ def).

Definition at line 188 of file phase.h.

◆ lattice() [1/3]

const auto & mim::Analysis::lattice ( ) const

inline

The whole map; used e.g. to diff two fixed-point runs.

Definition at line 165 of file phase.h.

Referenced by pin().

◆ lattice() [2/3]

bool mim::Analysis::lattice	(	const Def *	concr,
		const Def *	abstr )

protected

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.

Definition at line 134 of file phase.cpp.

References is_singleton(), mim::Rewriter::map(), and touch().

◆ lattice() [3/3]

const Def * mim::Analysis::lattice ( const Def * def ) const

inline

Returns: the abstract value recorded for def, or nullptr if unknown.

Definition at line 168 of file phase.h.

References is_singleton().

◆ lattice_erase()

bool mim::Analysis::lattice_erase ( const Def * concr )

inlineprotected

Non-monotone removal of 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 concr had an entry.

Definition at line 212 of file phase.h.

References touch().

◆ lattice_force()

bool mim::Analysis::lattice_force	(	const Def *	concr,
		const Def *	abstr )

protected

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.

Definition at line 123 of file phase.cpp.

References is_singleton(), mim::Rewriter::map(), and touch().

◆ leave()

virtual void mim::Analysis::leave ( )

inlineprotectedvirtual

Called after curr_mut() has been completely dealt with.

Reimplemented in mim::plug::mem::EscapeAnalysis.

Definition at line 292 of file phase.h.

◆ lookup()

const Def * mim::Analysis::lookup ( const Def * old_def )

overrideprotectedvirtual

Lookup old_def by searching in reverse through the stack of maps.

Returns: nullptr if nothing was found.

Reimplemented from mim::Rewriter.

Definition at line 118 of file phase.cpp.

References mim::World::annexes(), mim::Rewriter::lookup(), mim::World::Annexes::opaque(), and world().

Referenced by rewrite_mut().

◆ make_dense()

void mim::Analysis::make_dense ( )

inline

Forces whole-World rounds unconditionally.

Definition at line 156 of file phase.h.

◆ pin()

bool mim::Analysis::pin ( const Def * def )

inlineprotected

Monotonically forces def to ⊤ (keep as is).

Returns: true iff this changed observable information - i.e. iff it invalidate()d.

Definition at line 227 of file phase.h.

References lattice().

Referenced by mim::plug::mem::EscapeAnalysis::leave(), and pin_imm().

◆ pin_imm() [1/2]

void mim::Analysis::pin_imm	(	const Def *	def,
		DefPred auto	pinnable )

inlineprotected

Definition at line 239 of file phase.h.

References pin_imm().

◆ pin_imm() [2/2]

void mim::Analysis::pin_imm	(	DefSet &	visited,
		const Def *	def,
		DefPred auto	pinnable )

inlineprotected

pins every def in def's immutable subgraph for which pinnable holds.

Mutables are visited but not descended into; defs already in visited are skipped.

Definition at line 231 of file phase.h.

References mim::Def::deps(), mim::Def::isa_mut(), pin(), and pin_imm().

Referenced by pin_imm(), and pin_imm().

◆ prepare()

virtual void mim::Analysis::prepare ( )

inlineprotectedvirtual

Run before the main analysis.

Definition at line 266 of file phase.h.

Referenced by start().

◆ repr()

const Def * mim::Analysis::repr ( const Def * def ) const

inline

The representative of 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.

Definition at line 181 of file phase.h.

Referenced by rewrite().

◆ reset()

void mim::Analysis::reset ( )

virtual

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 also: RWPhase::analyze

Definition at line 68 of file phase.cpp.

References mim::Rewriter::push(), and mim::Rewriter::scopes_.

◆ rewrite()

const Def * mim::Analysis::rewrite ( const Def * def )

overrideprotectedvirtual

Rewrites 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.

Reimplemented from mim::Rewriter.

Definition at line 154 of file phase.cpp.

References mim::Def::isa_mut(), repr(), and mim::Rewriter::rewrite().

Referenced by mim::plug::mem::EscapeAnalysis::leave(), rewrite_external(), and start().

◆ rewrite_external()

void mim::Analysis::rewrite_external ( Def * mut )

protectedvirtual

Reimplemented in mim::plug::gpu::phase::MemChecks.

Definition at line 116 of file phase.cpp.

References rewrite().

Referenced by mim::plug::gpu::phase::MemChecks::rewrite_external(), and start().

◆ rewrite_imm_Proxy()

const Def * mim::Analysis::rewrite_imm_Proxy ( const Proxy * proxy )

inlineoverrideprotectedvirtual

By default: ignore Proxys.

Reimplemented from mim::Rewriter.

Definition at line 271 of file phase.h.

◆ rewrite_mut()

const Def * mim::Analysis::rewrite_mut ( Def * mut )

finalprotectedvirtual

Schedules 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 mut.

Reimplemented from mim::Rewriter.

Definition at line 159 of file phase.cpp.

References lookup(), mim::Rewriter::map(), and mim::Rewriter::rewrite_mut().

◆ rewrite_mut_Arr()

const Def * mim::Analysis::rewrite_mut_Arr ( Arr * mut )

inlineoverrideprotectedvirtual

Reimplemented from mim::Rewriter.

Definition at line 290 of file phase.h.

References CODE_MUT, and MIM_MUT_NODE.

◆ rewrite_mut_Hole()

const Def * mim::Analysis::rewrite_mut_Hole ( Hole * mut )

inlineoverrideprotectedvirtual

Reimplemented from mim::Rewriter.

Definition at line 290 of file phase.h.

◆ rewrite_mut_Lam()

const Def * mim::Analysis::rewrite_mut_Lam ( Lam * mut )

inlineoverrideprotectedvirtual

Reimplemented from mim::Rewriter.

Definition at line 290 of file phase.h.

◆ rewrite_mut_Pack()

const Def * mim::Analysis::rewrite_mut_Pack ( Pack * mut )

inlineoverrideprotectedvirtual

Reimplemented from mim::Rewriter.

Definition at line 290 of file phase.h.

◆ rewrite_mut_Pi()

const Def * mim::Analysis::rewrite_mut_Pi ( Pi * mut )

inlineoverrideprotectedvirtual

Reimplemented from mim::Rewriter.

Definition at line 290 of file phase.h.

◆ rewrite_mut_Rule()

const Def * mim::Analysis::rewrite_mut_Rule ( Rule * mut )

inlineoverrideprotectedvirtual

Reimplemented from mim::Rewriter.

Definition at line 290 of file phase.h.

◆ rewrite_mut_Sigma()

const Def * mim::Analysis::rewrite_mut_Sigma ( Sigma * mut )

inlineoverrideprotectedvirtual

Reimplemented from mim::Rewriter.

Definition at line 290 of file phase.h.

◆ rewrite_mut_Variant()

const Def * mim::Analysis::rewrite_mut_Variant ( Variant * mut )

inlineoverrideprotectedvirtual

Reimplemented from mim::Rewriter.

Definition at line 290 of file phase.h.

◆ start()

void mim::Analysis::start ( )

overrideprotectedvirtual

Actual entry.

Implements mim::Phase.

Definition at line 75 of file phase.cpp.

References finalize(), mim::Phase::invalidate(), mim::World::lenient(), mim::Phase::log(), mim::Rewriter::map(), mim::Rewriter::old2new(), prepare(), mim::Phase::profile_count(), rewrite(), rewrite_external(), mim::Phase::todo(), and world().

◆ taint()

void mim::Analysis::taint ( Def * mut )

inlineprotected

Additionally schedules 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.

Definition at line 247 of file phase.h.

◆ touch()

void mim::Analysis::touch ( )

inlineprotected

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.

Definition at line 253 of file phase.h.

References mim::Rewriter::curr_mut(), and mim::Phase::invalidate().

Referenced by lattice(), lattice_erase(), and lattice_force().

◆ version()

size_t mim::Analysis::version ( ) const

inline

Bumped on every observable lattice change; snapshot it around a code region to detect changes.

Definition at line 158 of file phase.h.

◆ world()

World & mim::Phase::world ( )

inline

Definition at line 58 of file phase.h.

Referenced by Analysis(), Analysis(), mim::plug::mem::EscapeAnalysis::EscapeAnalysis(), lookup(), and start().

The documentation for this class was generated from the following files:

include/mim/phase.h
src/mim/phase.cpp

Public Member Functions

Protected Member Functions

lattice

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ Analysis() [1/2]

◆ Analysis() [2/2]

Member Function Documentation

◆ finalize()

◆ is_singleton()

◆ is_top()

◆ lattice() [1/3]

◆ lattice() [2/3]

◆ lattice() [3/3]

◆ lattice_erase()

◆ lattice_force()

◆ leave()

◆ lookup()

◆ make_dense()

◆ pin()

◆ pin_imm() [1/2]

◆ pin_imm() [2/2]

◆ prepare()

◆ repr()

◆ reset()

◆ rewrite()

◆ rewrite_external()

◆ rewrite_imm_Proxy()

◆ rewrite_mut()

◆ rewrite_mut_Arr()

◆ rewrite_mut_Hole()

◆ rewrite_mut_Lam()

◆ rewrite_mut_Pack()

◆ rewrite_mut_Pi()

◆ rewrite_mut_Rule()

◆ rewrite_mut_Sigma()

◆ rewrite_mut_Variant()

◆ start()

◆ taint()

◆ touch()

◆ version()

◆ world()