From 2eba63966bdc3d9cfdf41ee085f35cbb6d529bbc Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Wed, 7 Oct 2026 19:10:51 -0700 Subject: Towrds getting RA spill counts comparable Ignore JIGs. Get test suites more conical, so reg alloc spill counts are comparable --- chapter24/README.md | 82 ++++++------------- .../main/java/com/seaofnodes/simple/IterPeeps.java | 19 ++++- .../com/seaofnodes/simple/node/CallEndNode.java | 93 ++++++++++++++++++++++ .../java/com/seaofnodes/simple/Chapter12Test.java | 2 + .../com/seaofnodes/simple/Chapter14FloatTest.java | 2 + .../java/com/seaofnodes/simple/Chapter14Test.java | 2 + .../java/com/seaofnodes/simple/Chapter15Test.java | 1 + .../java/com/seaofnodes/simple/Chapter16Test.java | 2 + .../java/com/seaofnodes/simple/Chapter17bTest.java | 2 + .../java/com/seaofnodes/simple/Chapter18Test.java | 3 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 2 + .../java/com/seaofnodes/simple/Chapter20Test.java | 1 + .../com/seaofnodes/simple/Chapter23AllocTest.java | 3 + .../java/com/seaofnodes/simple/Chapter23Test.java | 1 + .../com/seaofnodes/simple/Chapter24AllocTest.java | 3 + .../java/com/seaofnodes/simple/Chapter24Test.java | 2 + .../test/java/com/seaofnodes/simple/progs/jig.smp | 4 +- 17 files changed, 161 insertions(+), 63 deletions(-) (limited to 'chapter24') diff --git a/chapter24/README.md b/chapter24/README.md index 00d4c58c..07c63ee3 100644 --- a/chapter24/README.md +++ b/chapter24/README.md @@ -282,7 +282,7 @@ Similarly, `CallEnd`s merge results from all called functions, computing the *meet* over all the `Return`s. This *link* step adds a few checks to our algorithm's inner loop, and also -builds a precise Call Graph, and allows our SCCP to run interprocedurally. +builds a precise Call Graph which allows our SCCP to run interprocedurally. Other than discovering a few new edges as the algorithm proceeds, the core algorithm is unchanged. We are guaranteed to terminate with a fixed point solution, and may discover e.g. certain call parameters are constants (or @@ -292,68 +292,32 @@ e.g. not-null) on all calling paths. ## RegAlloc improvements: try cold loop splits first A loop Phi and its backedge can belong to one live range even though their -values must coexist at some instruction. This self-conflict requires splitting -the range. Chapter 23 split the Phi's definition and incoming values right away. +values must coexist at some instruction. This self-conflict requires splitting +the range. Chapter 23 split the Phi's definition and incoming values right away. This chapter first leaves the hot definition/backedge alone and tries the -outside-loop copies. If coloring succeeds, it avoids moves on every iteration. +outside-loop copies. If coloring succeeds, it avoids moves on every iteration. Other conflicts, including two-address operations, keep their existing handling. -The allocator remembers which Phis have had this chance. If the same Phi +The allocator remembers which Phis have had this chance. If the same Phi self-conflicts again, the next attempt uses the ordinary aggressive splitting. -The record uses Phi identity because live ranges are rebuilt each round. It +The record uses Phi identity because live ranges are rebuilt each round. It also covers a backedge-only conflict where the first attempt inserts no copy: -that attempt must still consume the one permitted delay. A regression checks +that attempt must still consume the one permitted delay. A regression checks both the cheaper first attempt and the mandatory fallback. -Chapter 21's adjacent-copy forwarding also carries forward: after coloring, -a sole use in the next instruction can read the source register when its -operand mask permits it and no two-address tie is broken. The table below -includes this cleanup and the lazy memory forward port. Cohort 22 now also includes the two zero-move C return -ABI checks added since the earlier audit (26 entries instead of 24). - -Run `make spill-stats`. All rows use **Chapter 24's compiler**, optimizer seed -123, and the same source/target combinations as the earlier cohort tables. -These Windows results combine x86 SystemV/Win64 and RISC-V/ARM SystemV, -remeasured after the lazy memory forward port. - -| Program cohort | Compilations | Retained moves | Loop-weighted moves | -|---|---:|---:|---:| -| Chapter 20 | 39 | 320 | 439 | -| Chapter 21 | 52 | 420 | 952 | -| Chapter 22 | 26 | 67 | 67 | -| Chapter 23 | 30 | 78 | 225 | -| Chapter 24 | 67 | 422 | 1,325 | -| **Total** | **214** | **1,307** | **3,008** | - -`_spills` counts retained SplitNodes, including register moves. `_spillScaled` -weights those moves by `8^loopDepth`; it is a cost estimate, not measured memory -traffic. Diagnostic machine graphs contribute no allocations to this table. -The reporter checks allocation legality and native/emulated results even when -spill expectations differ, and exits unsuccessfully for either kind of failure. - -In the original 2026-09-20 allocator audit, before subsequent compiler fixes, -the table totaled 1,332 / 2,956. With only the cold-first rule disabled, that -compiler and the same programs produced -**1,338 moves / 2,962 weighted moves**. The rule saves six of each. A RISC-V -MergeSort case adds one move, offset by improvements in other MergeSort cases, -Sieve, and an ARM loop case. Aggregate measurements justify accepting that -local regression; the improvement here is modest, not universal. - -On cohorts 20-23 alone in that audit, Chapter 23 produced 933 / 1,745; Chapter 24 produced -900 / 1,614. Only six of each reduction comes from this allocator change. The -rest comes from other compiler changes, including SCCP; comparing chapters -alone would overstate the heuristic's benefit. - -The older cohorts retain the 64-bit Person, guarded String, and smaller emulator -argument list. Revised Jig, BubbleSort, Newton, and stack-argument inputs belong -to cohort 24 alongside this chapter's existing tests. The frozen String workload -also exposed a missing null check in the inlining dominator walk; that correctness -fix is included on both sides of the heuristic comparison. Area/cost spill -ranking remains for Chapter 25. - -The current function-pointer rule keeps unknown callers whenever an address is -used as a value rather than only as a direct call target. This preserves callable -bodies without escape analysis, but Phi-selected functions retain general -parameter types. The no-return String case now drops its unused hash bodies and -needs no splits. Source/target membership remains unchanged; these graph changes -are separate from the cold-first allocator comparison above. +Rows are fixed test cohorts; columns are the compiler/allocator chapters. Each +cell is the sum of `_spillScaled`: retained split moves, including register +copies, weighted by loopDepth. Lower is better. **# tests counts +compilations** (program/CPU/ABI cases), including zero-spill cases, rather than +JUnit methods. The count and membership of each row stay fixed across columns. + + +| Test cohort | # tests | Ch 20 | Ch 21 | Ch 22 | Ch 23 | Ch 24 | +|---|---:|---:|---:|---:|---:|---:| +| Ch 20 | 39 | 360 | 576 | 430 | 442 | 441 | +| Ch 21 | 52 | | 1,072 | 960 | 961 | 948 | +| Ch 22 | 26 | | | 63 | 63 | 63 | +| Ch 23 | 24 | | | | 103 | 103 | +| Ch 24 | 58 | | | | | 1,387 | + + diff --git a/chapter24/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter24/src/main/java/com/seaofnodes/simple/IterPeeps.java index c924ccea..a3b66e09 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -49,7 +49,12 @@ public class IterPeeps { public final WorkList _work; - public IterPeeps( long seed ) { _work = new WorkList<>(seed); } + private final WorkList _workInline; + + public IterPeeps( long seed ) { + _work = new WorkList<>(seed); + _workInline = new WorkList<>(seed); + } @SuppressWarnings("unchecked") public N add( N n ) { return (N)_work.push(n); } @@ -60,12 +65,24 @@ public class IterPeeps { * Iterate peepholes to a fixed point */ public void iterate( CodeGen code ) { + while( true ) { + iteratePeeps(code); + CallEndNode cend; + while( (cend=_workInline.pop())!=null ) + if( cend.inlineSmall() ) break; + if( cend==null ) return; + } + } + + // Only try growing inlines once the shrinking peepholes reach a fixed point. + private void iteratePeeps( CodeGen code ) { assert progressOnList(code, _work, true); int cnt=0; Node n; while( (n=_work.pop()) != null ) { if( n.isDead() ) continue; + if( n instanceof CallEndNode cend ) _workInline.push(cend); cnt++; // Useful for debugging, searching which peephole broke things var obs = CodeGen.CODE._obs; if( obs != null ) obs.before(n); diff --git a/chapter24/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter24/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index fb57a090..115f70c6 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -123,6 +123,99 @@ public class CallEndNode extends CFGNode implements MultiNode { return null; } + // Clone only tiny, straight-line boilerplate, after ordinary peeps settle. + // Larger bodies still use the existing single-caller, non-cloning inline. + public boolean inlineSmall() { + if( isDead() || _folding || nIns()!=2 || !(in(0) instanceof CallNode call) ) return false; + Node fptr = call.fptr(); + if( !(fptr instanceof ConstantNode) || + !(fptr._type instanceof TypeFunPtr tfp && tfp.notNull() && tfp.isConstant()) ) + { addDep(fptr); return false; } + if( call.err()!=null ) return false; + ReturnNode ret = (ReturnNode)in(1); + FunNode fun = ret.fun(); + if( fun._folding ) return false; + int len = smallBody(fun); + if( len==0 ) return false; + // All callers consume the three normal return projections. + for( Node use : _outputs ) + if( !((use instanceof ProjNode p && p._idx>=0 && p._idx<3) || + (use instanceof CProjNode cp && cp._idx==0)) ) return false; + + // Substitute control and arguments directly; no new function identity, + // parameter Phis, or return address is needed for this straight line. + Node[] copy = new Node[len]; + for( int i=0; i1 ) { + Node use = out(0)==null ? out(1) : out(0); + int idx = use instanceof ProjNode p ? p._idx : ((CProjNode)use)._idx; + CodeGen.CODE.addAll(use._outputs); + use.subsume(result[idx]); + } + unkill(); + for( Node n : result ) n.unkill(); + CodeGen.CODE.invalidateIDepthCaches(); + return true; + } + + private static Node mapped(Node n, Node[] copy) { + for( int i=0; iTINYBODY.length ) return 0; + for( Node use : n._outputs ) { + if( use==null ) continue; + int j=0; + while( j +val _fib = {int n -> int temp=0; int f1=1; int f2=1; @@ -13,4 +13,4 @@ val fib = {int n -> return f2; }; -fib(10); +_fib(10); -- cgit v1.2.3