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