Determines which allocations stay within the scope that allocates them. More...

#include <mim/plug/mem/escape_analysis.h>

Inheritance diagram for mim::plug::mem::EscapeAnalysis:

Classes
struct	Chain

Public Member Functions
	EscapeAnalysis (World &world)
Public Member Functions inherited from mim::Analysis
	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.
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.
World &	world ()
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
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_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_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)

Static Public Member Functions
static bool	allocates (const App *app)
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.

Private Member Functions
const Def *	rewrite_imm (const Def *) override
	Records what each value may carry: the allocations it aliases and the nested Lams in it.
const Def *	rewrite_imm_App (const App *) override
void	leave () override
	Called after curr_mut() has been completely dealt with.

Results
const LamMap< Chain > &	chains () const
bool	escaping (Lam *lam) const
	May `lam` run at any time, as it is used as a value or jumped to by an escaping Lam?
bool	confined (const Def *allocalloc) const
	Is the local `alloc` only mentioned on its home's own memory chain?
bool	freed (const Def *allocalloc) const
	Does a mem.free release `alloc`?
static const App *	freed_alloc (const Def *def)
	The allocation `def` releases if it is a mem.free of one; nullptr otherwise.

Additional Inherited Members
Protected Member Functions inherited from mim::Analysis
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
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.
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.
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.
Protected Attributes inherited from mim::Phase
std::string	name_
Protected Attributes inherited from mim::Rewriter
fe::Vector< Scope >	scopes_

Detailed Description

Determines which allocations stay within the scope that allocates them.

The home of an allocation is the Lam on whose memory chain it sits. An allocation escapes if it flows into the data of a tail call - returned, or handed to a callee or continuation - or if an escaping Lam mentions it. Any op but mem.load, the address of a mem.store, and a mem.free of the allocation itself may retain the pointers it is handed, so they escape there. A Lam escapes if its use is unknown - it is used as a value - or if an escaping Lam jumps to it. An axiom in control position is assumed to only pass control on to the continuations it receives.

A buffer-typed parameter of a Lam takes on the value its known call sites pass, as in SCCP. An external Lam has unknown call sites, so whatever is passed to it escapes. A value only flows into a Lam that its scope strictly encloses; otherwise it would outlive its scope and escapes.

Lattice: an escaping allocation is ⊤ - keep as is; absent means it stays local. A parameter is ⊤ if its call sites disagree; everything they pass escapes.

Definition at line 27 of file escape_analysis.h.

Class Documentation

◆ mim::plug::mem::EscapeAnalysis::Chain

struct mim::plug::mem::EscapeAnalysis::Chain

Definition at line 29 of file escape_analysis.h.

Class Members
DefMap< size_t >	last	Per allocation the ops mention: the index of the last op that does so.
Vector< const App * >	ops	The ops threading the memory from the Lam's Var to its tail, in program order.
const App *	tail
DefVec	targets	The continuations the tail transfers control to.

Constructor & Destructor Documentation

◆ EscapeAnalysis()

mim::plug::mem::EscapeAnalysis::EscapeAnalysis ( World & world )

inline

Definition at line 36 of file escape_analysis.h.

References mim::Analysis::Analysis(), and mim::Analysis::world().

Member Function Documentation

◆ allocates()

bool mim::plug::mem::EscapeAnalysis::allocates ( const App * app )

inlinestatic

Definition at line 39 of file escape_analysis.h.

References mim::Axm::isa().

Referenced by mim::plug::mem::phase::FreeLocals::analyze(), freed_alloc(), and rewrite_imm().

◆ chains()

const LamMap< Chain > & mim::plug::mem::EscapeAnalysis::chains ( ) const

inline

The Lams with an intact memory chain.

Definition at line 44 of file escape_analysis.h.

◆ confined()

bool mim::plug::mem::EscapeAnalysis::confined ( const Def * alloc ) const

inline

Is the local alloc only mentioned on its home's own memory chain?

Definition at line 48 of file escape_analysis.h.

◆ escaping()

bool mim::plug::mem::EscapeAnalysis::escaping ( Lam * lam ) const

inline

May lam run at any time, as it is used as a value or jumped to by an escaping Lam?

Definition at line 46 of file escape_analysis.h.

Referenced by leave().

◆ freed()

bool mim::plug::mem::EscapeAnalysis::freed ( const Def * alloc ) const

inline

Does a mem.free release alloc?

Definition at line 50 of file escape_analysis.h.

◆ freed_alloc()

const App * mim::plug::mem::EscapeAnalysis::freed_alloc ( const Def * def )

inlinestatic

The allocation def releases if it is a mem.free of one; nullptr otherwise.

Definition at line 52 of file escape_analysis.h.

References allocates(), and mim::Axm::isa().

Referenced by leave(), rewrite_imm_App(), and mim::plug::mem::phase::Heap2Stack::rewrite_imm_App().

◆ leave()

void mim::plug::mem::EscapeAnalysis::leave ( )

overrideprivatevirtual

Called after curr_mut() has been completely dealt with.

Reimplemented from mim::Analysis.

Definition at line 57 of file escape_analysis.cpp.

References mim::Rewriter::curr_mut(), escaping(), freed_alloc(), mim::Axm::isa(), mim::Analysis::pin(), and mim::Analysis::rewrite().

◆ rewrite_imm()

const Def * mim::plug::mem::EscapeAnalysis::rewrite_imm ( const Def * def )

overrideprivatevirtual

Records what each value may carry: the allocations it aliases and the nested Lams in it.

Reimplemented from mim::Rewriter.

Definition at line 18 of file escape_analysis.cpp.

References allocates(), mim::Pi::isa_cn(), mim::Var::isa_tproj(), mim::plug::mem::mem_def(), mim::Rewriter::rewrite_imm(), and mim::Def::type().

◆ rewrite_imm_App()

const Def * mim::plug::mem::EscapeAnalysis::rewrite_imm_App ( const App * app )

overrideprivatevirtual

Reimplemented from mim::Rewriter.

Definition at line 52 of file escape_analysis.cpp.

References freed_alloc(), and mim::Rewriter::rewrite_imm_App().

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

include/mim/plug/mem/escape_analysis.h
src/mim/plug/mem/escape_analysis.cpp

Classes

Public Member Functions

Static Public Member Functions

Private Member Functions

Results

Additional Inherited Members

Detailed Description

Class Documentation

◆ mim::plug::mem::EscapeAnalysis::Chain

Constructor & Destructor Documentation

◆ EscapeAnalysis()

Member Function Documentation

◆ allocates()

◆ chains()

◆ confined()

◆ escaping()

◆ freed()

◆ freed_alloc()

◆ leave()

◆ rewrite_imm()

◆ rewrite_imm_App()