promote.pl
Promotion of memory slots to SSA temporaries, by promote_module/2 and promote_func/3. Prior art: QBE's promote and ssa passes, LLVM's mem2reg.
Which allocs
A slot is one fixed offset and width, accOff, Width, of an alloc that escape.pl calls local. An alloc is promoted, all its slots at once, when:
- it is in any block, its every execution a fresh zeroed object: the alloc itself sets each slot to 0, and its block is a definition block for phi placement. Strict SSA makes every access go through the latest execution's address (an inlined callee's local, perf.md item 4, in a caller's loop is an alloc in a middle block);
- its size is a constant and every slot lies inside it, so no access could trap or be undefined; in filc mode the size is at most 2^48 - 1, so the alloc itself could not trap too_big (interp:
alloc_res/6), which removing it would hide; - its slots do not overlap and each offset has one width, so every load reads exactly the bytes one earlier store wrote, except for punned reads: a
borhload, at an access never stored, inside a slot of widthhorw(a union read through a narrower member, lz4'sLZ4_isLittleEndian). It reads the slot's value shifted right by 8 times its byte offset (little-endian), then extended as any narrow load.landpslots are never punned; - in filc mode, its
pslots are 8-aligned (allocs are 16-aligned), so noloadporstorep, V, Acould trap as misaligned; - its float (
sord) slots are read only after a store to them on every path from the alloc (float_roots_stored/4): a slot read where the CFG, not the program, allows its initial zero would carry phis round a loop (Lua's luaV_execute).
An l access that another access overlaps (a struct of words copied as a long, read as words) is first split into two w accesses, the low word at its offset (split_words/8), when the alloc then promotes. The memory read and written is the same either way.
The function must also be in strict SSA form: each temp defined once, every definition dominating its uses. Otherwise a stored temp could be redefined before the load that promote would turn into its copy. A function that is not, or that calls setjmp, is left alone.
The rewrite
Loads become copies or extensions of the slot's current value, and stores disappear. Phis are placed on the iterated dominance frontier of the entry and the reachable blocks that store to the slot or hold its alloc, where the slot is live (pruned SSA, Cytron et al.); their temps are named pr.N. After its alloc and before any store a slot holds 0: Fil-C allocations are zeroed, and in plain mode the bytes are unknown, so 0 is one of the values they could have. Unreachable blocks read 0 too.
Values keep the class of the store: a storeb, V, A of a w value keeps the whole value, and each load narrows or extends it again, exactly as the bytes would.
| A load of | Becomes, on the slot's value |
|---|---|
l, p, s or d | copy |
sw or uw, at class w | copy |
sw or uw, at class l | extsw or extuw |
sh, uh, sb or ub | the extension of that type, such as extsb |
A slot's phi has class w for widths b, h and w, and the slot's width, l, p, s or d, otherwise. A float slot's 0 is the bit pattern of +0.0, which is what a zeroed object reads.
M is the module M0 with the promotable allocs of each function promoted.
Item is the module item Item0, promoted if it is a function. The cuts: the item's clause is not indexed (Mode comes first), and a choicepoint per function or data item would pin the module's trail until the pass ends (SQLite's 2,376 data items overflowed 1 GB).
N is the number of alloc instructions in the functions of module M.
F is the function F0 with its promotable allocs promoted, or F0 if it has none or is not in strict SSA form. Mode is module_mode/2 of the module being promoted.
As promote_func/3, carrying F0's context Records0 along (provenance.pl): the removed loads and stores' values become aliases of the slot's value, each slot's phis get generated origins citing its declaration and stores, and instruction sites are re-indexed. A setjmp function is left alone.
split_words/8).Word splitting
Splits is A-Offs for each local alloc A that Roots lacks and that would promote if each of its l accesses at an offset of Offs, which another access overlaps, were two w accesses, at the offset and 4 past it (a struct of words copied as a long and read as words: lz4's LZ4HC_match_t).
Bad lists the allocs that an l store of a value other than a temp or a constant writes (in plain mode a global(G) is read only at l, so its low word cannot be stored at w).
F is F0 with each l access of Splits split, little-endian: a store of V stores V's low word (a w store reads V at w) and then V shifted right by 32 at 4 past it; a load reads both words unsigned and joins them. The memory written and read is the same, so F is F0 whether or not promotion follows. New temps are sw.N, fresh against Counts.
Names are sw.K for the next K from N0 that Counts does not define.
A single shared summary per slot avoids repeating all stores for every phi. These are conservative contributors, not reaching-definition facts.
Roots is [A-Slots] for the allocs A of F that can be promoted, in order, Slots an ordset of acc(Off, Width).
As promotable/3, with An = an(Classes, Addrs, Counts): F's alloc_classes/2, address_temps/2 and def_counts/2, computed once for escape analysis and the rewrite, or an([], none, none) when F has no alloc or calls setjmp.
Without an alloc, skip escape analysis.
Roots is Roots0 less the allocs with a float (s or d) slot that a load may read before any store to it, along some path from its alloc. Promotion reads such a slot's initial zero through phis, and a path the program never takes (a load guarded by the test that a store happened, as in Lua's op_arithf) would carry the slot round a loop: luaV_execute took 166 d phis at its dispatch and doubled in size. Integer slots are promoted as before.
every load of a float slot of A, in a reachable block, follows a store to that slot on every path from the entry: a forward must analysis whose state is the ordset of A's float offsets stored, emptied by A's alloc.
the offsets stored on every path into L, over the predecessors analysed so far (an unanalysed one is optimistic: it constrains nothing until it is).
Stored maps each alloc to the accesses that store to it.
Slots are the accesses of Accs that no other one contains. Each other access is a punned read: a load of b or h, never stored, inside a slot of width h or w (a union read through a narrower member; its bytes are a shift and an extension of the slot's value, little-endian). Fails otherwise.
an alloc of Size bytes does not trap too_big: Fil-C's limit is 2^48 - 1 bytes (FILC_MAX_ALLOCATION_SIZE, interp:alloc_res/6). A negative constant is a size of 2^64 or more, read at l. Plain mode has none.
a slot of Width at Off is aligned enough in Mode: only p slots in filc mode need 8.
no two of Accs overlap. Accs is sorted by offset, so it is enough to compare neighbours. Two widths at one offset overlap too.
F is in strict SSA form: every temp has one definition, and in the blocks reachable from the entry each definition dominates each use (a phi argument is used at the end of its predecessor). Cfg and Idom are those of F.
As strict_ssa/3, given F's def_counts/2.
Block, given as L-Phis-Insts-Jump, reads a temp as Use = use(T, L, At): T is read in block L at At, which is at(Pos) for position Pos, or end for the end of the block; a phi argument is read at the end of its predecessor.
the temp of Use = use(T, L, At) is defined before At in block L, or in a block that dominates L.
Rewriting
Blocks are the blocks of F0 with every slot of Roots promoted; Addrs and Counts are F0's address_temps/2 and def_counts/2.
phis_temps//3 is the last fresh temp number.Labels is the ordset of the labels where Var needs a phi: the iterated dominance frontier of the entry and the blocks that store to Var, keeping only blocks where Var is live on entry. Each placed phi counts as a store for the iteration. Unreachable stores are not in Stores: they never run.
Placed is Placed0 with the frontier labels where Var is live, of the labels in Work and, in turn, of each new one. Invariant: Placed0 is the ordset of those labels found so far, and each of them has had its frontier scanned or is still in Work.
if Var is live on entry to Y and Y is not in Placed0, Y is in Placed and in front of Work0.
the phis L-Var for each Var of Vars, in order, and each L of its ordset of labels in Labelss.
Placed is Phis with each L-Var as L-(Var-T), T a fresh temp. The semicontext is the number of the last fresh temp.
T is pr.N, the first such name after N0 that is not in Used.
the renamed blocks of the dominator subtree at L, Cur0 being the slots' values on entry to L. Env is env(Addrs, PhiAt, ByLabel, Kids, Succs).
the renamed blocks Ls, each with the slots' values Cur0 on entry.
Renamed is renamed(L-Blk, Args): Blk is block L with its slot accesses rewritten, given the slots' values Cur0 on entry (Cur on exit), and Args the (Succ-Var)-(L-Value) arguments it gives its successors' slot phis.
the instructions Insts0 with their slot accesses rewritten, Cur0 and Cur being the slots' values before and after them.
the alloc and the derived addresses are no instructions, a load of a slot is an operation on its current value, a store to a slot is none and sets its value, and any other instruction is itself.
punned_slots/3).What a load at class K of type T computes from the value last stored at its width (see the header).
Block is the renamed Block0, with the slots' phis appended to its own.