diff options
| author | Cliff Click <cliffc@acm.org> | 2026-10-07 19:10:51 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-07 19:10:51 -0700 |
| commit | 2eba63966bdc3d9cfdf41ee085f35cbb6d529bbc (patch) | |
| tree | c297b19a448bc3e0780437122646183240437a30 /chapter24 | |
| parent | aaec6f8136df6f7020bfc05f79ff5273adf73de1 (diff) | |
| download | Simple-2eba63966bdc3d9cfdf41ee085f35cbb6d529bbc.tar.gz Simple-2eba63966bdc3d9cfdf41ee085f35cbb6d529bbc.zip | |
Towrds getting RA spill counts comparable
Ignore JIGs. Get test suites more conical, so reg alloc spill counts are comparable
Diffstat (limited to 'chapter24')
17 files changed, 161 insertions, 63 deletions
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. + +<!-- spill-matrix:start --> +| 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 | +<!-- spill-matrix:end --> + 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<Node> _work; - public IterPeeps( long seed ) { _work = new WorkList<>(seed); } + private final WorkList<CallEndNode> _workInline; + + public IterPeeps( long seed ) { + _work = new WorkList<>(seed); + _workInline = new WorkList<>(seed); + } @SuppressWarnings("unchecked") public <N extends Node> 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; i<len; i++ ) { + Node n = TINYBODY[i]; + copy[i] = n==fun ? call.ctrl() : + n instanceof ParmNode parm ? (parm._idx==0 ? null : call.arg(parm._idx)) : + n==ret ? null : n.copyEmpty(); + } + for( int i=0; i<len; i++ ) { + Node n = TINYBODY[i]; + if( n instanceof StoreNode || n instanceof MemMergeNode ) { + for( Node in : n._inputs ) copy[i].addDef(mapped(in,copy)); + CodeGen.CODE.add(copy[i]); + } + } + Node[] result = new Node[3]; + for( int i=0; i<3; i++ ) result[i] = mapped(ret.in(i),copy).keep(); + keep(); + call.unlink_all(); + CodeGen.CODE.add(fun); + CodeGen.CODE.addAll(fun._outputs); + // subsume kills each projection; retain CallEnd until all are replaced. + while( nOuts()>1 ) { + 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; i<copy.length; i++ ) + if( TINYBODY[i]==n ) return copy[i]; + return n; // Constants outside the body are shared. + } + + // Bounded recognition of initializer boilerplate. Walk uses from the entry + // and stop at Return, never following callers or constant inputs. This also + // avoids scanning sparse MemMerge input arrays while a large body shrinks. + // Watch this small prefix, including an unsupported node that may fold. + private static final Node[] TINYBODY = new Node[15]; // Tiny worklist + private int smallBody(FunNode fun) { + ReturnNode ret = fun.ret(); + for( Node in : ret._inputs ) + if( in!=null ) addDep(in); + if( ret.ctrl()!=fun ) return 0; + TINYBODY[0] = fun; + int len=1; + for( int i=0; i<len; i++ ) { + Node n = TINYBODY[i]; + addDep(n); + if( n==ret ) continue; + if( n instanceof ParmNode parm && parm.region()!=fun ) return 0; + if( n!=fun && !(n instanceof ParmNode) && + !(n instanceof StoreNode) && !(n instanceof MemMergeNode) ) + return 0; + if( n.nOuts()>TINYBODY.length ) return 0; + for( Node use : n._outputs ) { + if( use==null ) continue; + int j=0; + while( j<len && TINYBODY[j]!=use ) j++; + if( j<len ) continue; + if( len==TINYBODY.length ) { addDep(use); return 0; } + TINYBODY[len++] = use; + } + } + return len; + } + @Override public Node pcopy(int idx) { return _folding ? in(1).in(idx) : null; } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 041e0d06..ac3b81ec 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -1,11 +1,13 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter12Test { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java index 23d0ef37..6377bc14 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.StopNode; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -47,6 +48,7 @@ public class Chapter14FloatTest { } + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter14Test.java index da7e50bc..c342eeed 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -2,12 +2,14 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.StopNode; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter14Test { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 66a50d0f..d0a42ccf 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -10,6 +10,7 @@ import static org.junit.Assert.*; public class Chapter15Test { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter16Test.java index 692ac8d5..f73cbf57 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -1,12 +1,14 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter16Test { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index 59bd3b0c..24dc0229 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -1,12 +1,14 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter17bTest { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 1941f516..44c365dd 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -115,6 +115,7 @@ public class Chapter18Test { } + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( @@ -454,7 +455,7 @@ if (i2i) return i2i(arg); return f2f(o)(1); """); code.driver(Phase.LocalSched); - assertEquals("Stop[ return Phi(Region,#2,#2); return Parm_i(i2i.o,i64); ]", code._stop.toString()); + assertEquals("Stop[ return Phi(Region,#2,1); return Parm_i(i2i.o,i64); ]", code._stop.toString()); assertEquals("1", Eval2.eval(code, 2)); } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java index 26bf35d2..8a840787 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -8,6 +8,7 @@ import com.seaofnodes.simple.codegen.CodeGen; import java.io.IOException; import java.nio.file.Files; import java.nio.file.Path; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.*; @@ -32,6 +33,7 @@ public class Chapter19Test { } + @Ignore @Test public void testJig() { CodeGen code = new CodeGen(""" diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java index fdcc0817..4ca1dbda 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -92,6 +92,7 @@ return f(s); } + @Ignore @Test public void testJig() { CodeGen code = new CodeGen("return 0;"); diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23AllocTest.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23AllocTest.java index 7f4b86d5..f3cc7512 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23AllocTest.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23AllocTest.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple; import java.io.IOException; import java.nio.file.*; +import org.junit.Ignore; import org.junit.Test; // Revised or newly enabled allocation examples in Chapter 23. @@ -14,6 +15,7 @@ public class Chapter23AllocTest { Chapter23Test.testCPU(src,"arm" , "SystemV", 1,null); } + @Ignore @Test public void testJig21() throws IOException { String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp")); @@ -22,6 +24,7 @@ public class Chapter23AllocTest { Chapter23Test.testCPU(src,"arm" , "SystemV",-1,null); } + @Ignore @Test public void testJig22() throws IOException { String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp")); diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 7ad340c2..884e77e5 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -88,6 +88,7 @@ public class Chapter23Test { } } + @Ignore @Test public void testJig() throws IOException { String src = diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24AllocTest.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24AllocTest.java index a56c823a..7fae2c27 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24AllocTest.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24AllocTest.java @@ -8,6 +8,7 @@ import java.io.IOException; import java.nio.file.*; import com.seaofnodes.simple.node.cpus.arm.arm; import com.seaofnodes.simple.node.cpus.riscv.riscv; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.*; @@ -34,6 +35,7 @@ return sqrt(arg) + sqrt(cast_int); Chapter24Test.testCPU(src,"arm" , "SystemV",19,null); } + @Ignore @Test public void testJig21() throws IOException { String src = @@ -131,6 +133,7 @@ val addAll = { int i0, flt f1, int i2, flt f3, int i4, flt f5, int i6, flt f7, i assertEquals(22.8, result1, 0.00001); } + @Ignore @Test public void testJig22() throws IOException { String src = diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java index 58c0d7f8..bb89aa16 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java @@ -12,6 +12,7 @@ import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.cpus.riscv.riscv; import java.io.IOException; +import org.junit.Ignore; import org.junit.Test; import static org.junit.Assert.*; @@ -36,6 +37,7 @@ public class Chapter24Test { } + @Ignore @Test public void testJig() throws IOException { String src = "int v0=0; v0 = arg && 0== 0 !=0;"; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/progs/jig.smp b/chapter24/src/test/java/com/seaofnodes/simple/progs/jig.smp index f7a5d202..29987d8e 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/progs/jig.smp +++ b/chapter24/src/test/java/com/seaofnodes/simple/progs/jig.smp @@ -1,5 +1,5 @@ // -*- mode: java; -*- -val fib = {int n -> +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); |
