THE FOLD / BOSS / THE GATEKEEPER / THE PEEPHOLE
THE PEEPHOLE
the limit is why it is trustworthy
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Slide a window a few instructions wide along the emitted code and rewrite whatever matches a pattern. No analysis, no graph, no proof — just a list of local truths applied everywhere.
LIT verified live. 12 instructions, 5 rules, none looking at more than one instruction at a time. 8 are removed — 66.7% — leaving 4. And 1 adjacent pair survives that a wider window would take: a push immediately followed by the matching pop. The window size is the entire limit of the technique.
LIT verified live. 12 instructions, 5 rules, none looking at more than one instruction at a time. 8 are removed — 66.7% — leaving 4. And 1 adjacent pair survives that a wider window would take: a push immediately followed by the matching pop. The window size is the entire limit of the technique.
2 HOW IT WAS WEAVED · AI + HUMAN
Peephole optimisation is McKeeman’s (1965) and it is still where a surprising fraction of the final instruction count goes.
AVAN (AI) left the push/pop pair in deliberately and counted it as a miss. A pass that removes 66.7% of the instructions looks complete until you notice what it walked past — and what it walked past is not a bug in the rules but the shape of the window they are allowed to see through.
AVAN (AI) left the push/pop pair in deliberately and counted it as a miss. A pass that removes 66.7% of the instructions looks complete until you notice what it walked past — and what it walked past is not a bug in the rules but the shape of the window they are allowed to see through.
3 ONE DIMENSION
Twelve instructions, five rules, one thing missed.
4 TWO DIMENSIONS · INTERACTIVE
Widen the window and pick up the pair.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a small window, moved everywhere.
AVAN’s addition (the inverse-companion): the forward reading is that a peephole pass is limited by its window. The inverse is that the limit is why it is trustworthy. A rule that looks at one instruction cannot be wrong about control flow, aliasing or lifetimes, because it never consults them; the narrowness that costs it the push/pop pair is the same narrowness that makes it impossible to break. Read backwards, every optimisation is a trade of reach against certainty, and this one sits at the end of the pipeline precisely because it is the one nobody has to check.
LIT 12 instructions against 5 rules, none looking at more than one instruction at a time, remove 8 - 66.7% - and leave 4, while 1 adjacent pair survives that a wider window would take: a push immediately followed by the matching pop, so the window size is the entire limit of the technique
FIG Peephole optimisation is McKeeman's (1965) and it is still where a surprising fraction of the final instruction count goes. AVAN left the push/pop pair in deliberately and counted it as a miss. A pass that removes 66.7% of the instructions looks complete until you notice what it walked past - and what it walked past is not a bug in the rules but the shape of the window they are allowed to see through.
FIG Peephole optimisation is McKeeman's (1965) and it is still where a surprising fraction of the final instruction count goes. AVAN left the push/pop pair in deliberately and counted it as a miss. A pass that removes 66.7% of the instructions looks complete until you notice what it walked past - and what it walked past is not a bug in the rules but the shape of the window they are allowed to see through.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE GATEKEEPER · David Lee Wise (ROOT0), with AVAN