check_reuse.pl
Check reuse: a heap access check's proof covers later scalar accesses through the same pointer or a related one, in its block and along CFG edges (docs/m7.md).
Pizlonation states one check per access, right before it. This pass deletes a check when an earlier proof already establishes what it would: the same pointer operand, or one related to it (both constant offsets, by single-definition flights with the same lower donor, from one root; round 3), at least its range, shifted by their distance, and rights, and nothing in between that could free the object or redefine either temporary. The covered access then reads the earlier proof. Nothing is moved, widened or added, so every remaining check fails exactly where it failed before.
Facts
| Fact | Means |
|---|---|
availP, Q, Lo, Hi, Rights, Align | tmpQ is a proof of P that P+[Lo, Hi) allows Rights at alignment Align |
Blocks are walked once, in order. A block's entry facts are those every incoming edge carries: a plain edge from a block already walked carries its exit facts, a poll edge or an edge from a later block none. Only facts whose proof has one definition and whose pointer has at most one cross an edge, and a phi kills the facts naming its destination. A kept heap check adds its fact once its first access has run. An instruction that is transparent/1 keeps the facts that do not mention the temporary it defines; any other instruction (a call, allocation, getter, pointer access, setjmp, va_arg, ...) removes them all.
Renewal (round 4), range guards (round 5) and hoisted bounds (docs/bounds.md: a limit of a loop's invariant root, read by check_limit in the loop) build on these facts below.
The pass is selected with --checks=reuse; the reference path keeps every check. ir.pl's validator accepts the result by its own rule, and reuse_refines/2 checks that the only change is deleted checks whose access now reads a proof of the same or a related operand, at an offset changed by exactly their distance.
M is the checked module M0 with each heap check that an available proof covers deleted, and its access reading that proof. Context sites follow the instructions; aliasQ, tmpQ1, none, Os records that the access of the deleted proof Q reads Q1.
Mode plain is reuse_checks/2. Mode forward (docs/forward.md) also lets a pointer load with the heap load effects read an earlier proof, and its own check make a fact, and deletes a check that the hull of the available facts of its object covers, reading the first of them whose alignment suffices. Mode getter is forward where a repeated getter copy (repeated_getters/4) keeps the facts.
Blocks in order. Entry facts are those every incoming edge carries (exit facts on a plain edge from a block already walked; none on a poll edge or from a later block), kept only when the proof and its pointer are defined once in the function, less those a phi redefines.
Within a block the facts are st(Facts, Names, ByRoot): Facts newest first, as before; Names every name a fact mentions (perhaps more); ByRoot the facts of each root (base_of/4), newest first, each with its pointer's offset from the root, K-avail(...). The candidates for a check are exactly ByRoot's list for its pointer's root, in Facts' order, and a definition scans Facts only when Names has its name: a long block costs no more per check than its facts of one root.
Info is info(Defs, Uses, Bases): each temporary's number of definitions (parameters, phis and every instruction form) and of instructions reading it, and Bases, the assoc from each single-definition flight X to B-K when X's address is B's plus the constant K with B's capability, B defined once too (base_of/4).
Rep holds the repeated getter copies (repeated_getters/4), which keep the facts in getter mode. Old and New index the next instruction of block L before and after; Map pairs their sites, and Reused pairs each deleted proof with its replacement.
A vector's full-width check and its touch (docs/vector-access.md) stay, and make a fact that the chunk accesses after them may reuse. V1 does not reuse the full-width check itself.
M is M0 except for deleted heap checks, each of whose single access now reads an earlier proof of the same operand. This is identity, not safety: that the earlier proof still covers the access is ir.pl's rule, which valid_module/1 checks separately.
reuse_refines/2 for reuse_checks/3's Mode: with forward a deleted check's access may be a heap pointer load, and the proof it reads need not cover its range by itself (the hull, which is the validator's question too).
Proofs are Q-checked(P, Check) for the heap checks seen so far in the block, newest first; Global the same for every heap check in the function whose proof has one definition and its pointer at most one. A deleted check's proof had one definition and one reader, and the proof that replaces it checks the same operand and subsumes the deleted check. Whether it is available there is the validator's question.
the check of [Lo, Hi) with Rights at Align is exactly what Access needs (as pizlonation makes it), so the validator's accepting the rewired access shows that the deleted check would have passed: the hull (docs/forward.md) keeps trap timing only for such checks.
Access, at tmp(Q), may read another proof: a scalar access, or in forward mode a heap pointer load too.
covering(+Mode, +Cands, +K, +Lo, +Hi, +Rights, +Align, -Q1, -D): of the available facts Cands of a root, K1-avail(...) with their pointer's offset K1 from it, Q1's covers the check of [Lo, Hi) with Rights and Align of the pointer at offset K, at distance D = K - K1: the first that subsumes it, or in forward mode (docs/forward.md) the first whose alignment suffices when the facts together span the check's range (an object is one interval) and one of them has write rights if it needs them. Offsets count only within +-2^62, where the integers are the true distances.
A check of [Lo1, Hi1) with Rights1 at Align1 that succeeded implies that the check of [Lo, Hi) with Rights at Align, of the same pointer and object state, would succeed. Comparing with the deleted check, not just its access, keeps a wider or stronger check's trap.
Facts are those of Facts0 that do not mention the temporary Inst defines.
Inst cannot free, reallocate or relabel an object, and reaches no safepoint: arithmetic, comparisons, conversions, pure pointer construction, checks, scalar raw accesses and raw pointer loads (which read aux and box words, calling no helper).
M is the checked module M0 with each heap check replaced by a renew (docs/m7.md, round 4) when an earlier heap check of a pointer related to it at distance 0 dominates it and covers its bounds and alignment, rights aside, and both that check's proof and pointer have one definition. The renew reads that proof, the topmost such check on the dominator chain: no check that covers it dominates it, so it stays a check. Functions with a setjmp are unchanged. Every instruction keeps its index, so context sites are unchanged.
As renew_checks/2 when Distance is zero. When it is any (scheduled checks, docs/schedule.md), the earlier check may be of a pointer at any constant distance D from the same root, if it covers the replaced check's range shifted by D, and the earlier and replaced checks may be check_aheads, of their whole range.
renew_selection(+Fn, +Blocks0, +Blocks1, -Blocks): for measurement, NANOFIL_RENEW_SITES=Fn:From-To keeps only Fn's renews numbered From to To - 1 in block order (Fn alone keeps all of Fn's), and every other function's checks; unset or empty, Blocks is Blocks1. Any subset of renews is valid IR: a check left in place is the reference.
Sources maps Root to s(Depth, L, I, Q1, check, P1, K) for each reachable heap check (or check_ahead) of a pointer at K from Root whose proof and pointer have one definition, sorted by dominator depth and index.
Depths maps each reachable label to its number of dominators below the entry, in one walk of the dominator tree (a walk up the tree per block is quadratic in a long chain).
the single-source pass that runs first; hull's second pass is hull_blocks/5.
hull_blocks(+Blocks0, +Info-Once, +Depths, +Dom, -Blocks): after the single-source pass, each check that no renew reads and that two dominating checks of its object cover together (hull_pair/13) becomes a renew_hull reading them. Checks are taken in dominator-tree preorder, so a check's sources are decided before it, and a check made a renew_hull is no longer a source.
hull_pair(+Sources, +Removed, +I, +L, +Dom, +Once, +P, +K, +Lo, +Hi, +Align, -QL, -QH): two dominating checks of P's root whose ranges, moved to P, start at or below Lo and end at or above Hi, each within 2^62 bytes, the one or the other with alignment enough for Align (ir.pl's hull_renewable/8 is the validator's own statement). With no single covering source (renewed_insts/8 tried that first), the object is one interval, so the two together cover [Lo, Hi).
A renew's access: scalar or an ordinary pointer access; not a cas.
M is M0 except for heap checks replaced by renews of the same range, rights and alignment, each reading a single-definition heap check's proof of a single-definition pointer related to the replaced check's at distance 0. This is identity, not safety: dominance and coverage are the validator's (ir.pl), which valid_module/1 checks separately.
renew_refines/2 for renew_checks/3's Distance: with any a renew may read a check of a pointer related to its own at any distance (the coverage is the validator's question).
Range guards (docs/m7.md, round 5, slice A). M is the checked module M0 with each heap check in a natural loop, followed by a renewable access, whose pointer is a base defined outside its innermost loop plus an offset with a constant interval (ir.pl's guard_chain/3), replaced by renew_if of that pointer and a guard: one span_test per loop and base, appended to the end of the loop header's immediate dominator, spanning every byte the group's checks can reach. Nothing else moves, so existing context sites are unchanged; a guard has no site and cannot trap. Functions with a setjmp are unchanged.
C is c(IH, B, K, L, J, Lo, Hi) for a heap check at index J >= I of block L, followed by a renewable access, whose pointer is base B plus an offset whose accesses cover [Lo, Hi) of B, B defined before the loop whose header's immediate dominator is IH: the outermost of the loops around L for which B is. K is const for a constant offset, else ranged.
guard_places(+Cs, +Place, +Idom, -Places): Places maps B-K-IH to X, the block at whose end the guard of base B and offset kind K for the loops whose headers' immediate dominators are IH goes. The IHs of one base and kind that lie in the same loop (or in none) share one place: their nearest common dominator, or B's definition block (the entry for a parameter) when that is deeper. So one guard serves several loops (bzip2's BZ2_decompress has dozens of bit-reading loops, each run once or twice, on one state pointer), yet runs only where every path to those loops runs: at mainGtU's entry it would run on each call, though its loop is reached by few. A place in another loop than its IHs (a definition inside an inner loop) falls back to each IH.
D is the deepest block that dominates both A and B.
A guard of [Lo, Hi) may pass. A span test fails as a whole, and then each access it guards pays its full check plus the test of G. A ranged span over 256 KiB is a type's bound times a stride (a byte or short index into a row of a table), which objects rarely hold: bzip2's s->len[t][v], for a byte t, spans 1 MB of a 55 KB state. A table that large (bzip2's ftab, 256 KiB) still fits. A span_test's ends are signed 64-bit (ir.pl's valid_op); a span past them is no guard at all, and merged clusters stay within each part's.
BlockLoops maps each block in some natural loop whose header has an immediate dominator to its loops' H-Body-IH, outermost first (nested loops' bodies are nested). Built by walking the loops outermost first and each body once, so the cost is the bodies' total size, not blocks times loops.
span_clusters(+Kind, +Spans, -Clusters): the Lo-Hi Spans of one base in one loop, in clusters, each one span test. A span test passes or fails as a whole, so a span the object cannot hold must not take others down with it. An offset that varies is bounded by its type and masks, not by the array it indexes (a byte index into a six-row table), so each distinct ranged span gets its own test; constant offsets, fields, merge where they overlap or lie within 64 bytes.
B is the farthest base on the chain whose single definition is outside the loop Body and dominates its header's immediate dominator IH, so a guard at IH's end may read it.
A name no instruction or phi defines per group, g(Name, H, B, K, Lo, Hi).
M is M0 except for span_test lets of fresh names appended at block ends, and heap checks replaced in place by renew_if of the same pointer, range, rights and alignment, reading one of those guards. This is identity, not safety: that the guard covers the access is the validator's rule (ir.pl).
Each renew_if that replaced a check reads one of the fresh guards.
Hoisted bounds (docs/bounds.md). M is the checked module M0 with each heap check in a natural loop, at offset 0 and followed by a renewable access, whose pointer has the lower of a base defined outside the loop (lower_chain/3, any address), replaced by check_limit of that pointer and a limit of the base for the check's size: one limit/1 per base, size and place, appended where guard_places/4 would put a guard, so it runs once before the loops it serves. Nothing else moves, so context sites are unchanged; a limit has no site and cannot trap. Functions with a setjmp are unchanged.
C is c(IH, B, Size, L, J, 0, 0) for a heap check of [0, Size) at index J >= I of block L, followed by a renewable access, whose pointer has the lower of base B, defined before the loop whose header's immediate dominator is IH: the outermost of the loops around L for which some base on the chain is.
P-i(0, 0) and each lower donor after it through single-definition flights, as guard_base/8 reads a chain.
A name no instruction or phi defines per X-B-Size key, u(Name, X, B, Size).
M is M0 except for limit lets of fresh names appended at block ends, and heap checks replaced in place by check_limit of the same pointer, range, rights and alignment, reading one of those limits. This is identity, not safety: that the limit is of the pointer's lower and size is the validator's rule (ir.pl).