escape.pl
Escape classification of allocs: alloc_classes/2 tells, for each alloc of a function, whether its address is only used for loads and stores at known offsets. Prior art: QBE's ALoc/AEsc.
The module also exports the relations alloc_classes/2 is built from: address_temps/2, load_width/2 and def_counts/2.
The analysis rests on one fact: a local alloc can only be reached through its own address, so no other pointer or integer can name it.
Offsets are exact integers. An IR add wraps modulo 2^64, but here a huge constant gives a huge offset, which promote's bounds check refuses.
as load_width/2, and a float load reads a slot of its own width, s or d. local_storage.pl keeps float loads out of named locals through load_width/2; promotion takes them.
Classes is [A-Class] for every alloc temp A of Func, in order, with Class one of:
- local(Size, Accesses): every use of A's address is the address of a load or store at a fixed offset, possibly through add/sub of constants or copy. Accesses is an ordset of acc(Off, Width), Width in b h w l p s d. Size is the alloc's operand. - escapes(Why): the address is used any other way (stored, passed, returned, compared, converted, merged in a phi, offset by a variable, loaded with an unsupported type), or it or a temp derived from it is defined more than once, so offsets are unknown.
As alloc_classes/2, given Func's address_temps/2 and def_counts/2.
Class is the class of the alloc A, of operand Size, given the assoc Events of each alloc's events in order: escapes for the first escape, or else local.
Event is what Ins does with the address of alloc Root: an access at a known offset, or an escape of every alloc whose address it reads. A constant offset (a derived address, seen by address_temps) is neither.
Atomic accesses are not slot accesses: their objects escape, so they stay heap objects, which Fil-C's atomic helpers require (atomic boxes live in a heap object's aux).
A cas, of an integer as of a pointer, lets every address it reads escape: its object stays on the heap, which lock cmpxchg on a shared object and Fil-C's pointer helper both need, and promotion never deletes the object of a cas it would leave behind.
A full-width vector check (docs/vector-access.md) keeps its object on the heap: promoting it would need the static bounds to discharge it.
A fixed-register asm reads its inputs' values: in plain mode a w input can be a derived address, whose object then stays (docs/asm-fixed.md).
as inst_event/3, for the instruction Ins of an Op of Kind. A load accesses its address only when its slot width is supported; otherwise it escapes, so promotion cannot mistake an unknown access for no use. Every other op lets the addresses it reads escape.
Addrs is the assoc Temp -> A-Off for each alloc temp A (Off 0) and each temp derived from one by constant offsets, whatever the class.
Addrs is Addrs0 with the temps derived, directly or not, from the X-(Root-Off) pairs of Layer and not yet in Addrs0. A dependency is followed only when its source is first resolved, a whole layer at a time: as in the old fixed point, a redefined temp takes its earliest-resolved definition, then instruction order breaks ties. Cycles without an allocation seed remain unresolved.
Counts is the assoc Temp -> number of definitions of Temp in Func (parameters, phis, instructions and call results).
Pairs is X-N for each run of N equal elements X of Sorted.