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 the entry block, so it runs exactly once per call (the validator forbids jumps to the entry block) and its fresh contents are the only initial state;
- its size is a constant and every slot lies inside it, so no access could trap or be undefined;
- its slots do not overlap and each offset has one width, so every load reads exactly the bytes one earlier store wrote;
- in filc mode, its
pslots are 8-aligned (allocs are 16-aligned), so noloadporstorep, V, Acould trap as misaligned.
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, where the slot is live (pruned SSA, Cytron et al.); their temps are named pr.N. 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 or p | 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 or p, otherwise.
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.
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.
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).
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.
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.
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.
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.