diff options
Diffstat (limited to 'chapter20')
12 files changed, 149 insertions, 58 deletions
diff --git a/chapter20/README.md b/chapter20/README.md index e11dcff2..9f7cb1c5 100644 --- a/chapter20/README.md +++ b/chapter20/README.md @@ -503,59 +503,25 @@ two-address operands, and Phi register agreement; tiny machine graphs exercise hard conflicts independently of optimizer choices. Native execution comes with encoding in Chapter 21. -### Spill-count summed across tests - -Run `make spill-stats` to execute the tests and print each compilation's counts, -CPU/ABI subtotals, and the total below. Assertions remain enabled, and a failing -test makes the command fail. The optimizer's default seed is 123. - -The Chapter 20 program cohort is all 11 source examples in `Chapter20Test`, plus -`BrainFuckTest.testBrainfuck` and `MergeSortTest.testMergeSort`, on x86-64, -RISC-V, and ARM using SystemV: 13 programs and 39 compilations, including the -zero-spill cases. The synthetic allocator regression graphs are correctness -checks, not additional program benchmarks. - -| Program-test cohort | Allocator chapter | Compilations | Split moves | Loop-weighted moves | -|---|---:|---:|---:|---:| -| Chapter 20 | 20 | 39 | 234 | 360 | - -`_spills` counts surviving split moves, including register-to-register copies; -it does not count only stack stores. `_spillScaled` weights each move by -`8^loopDepth`, a rough cost estimate rather than measured execution frequency. -The weighted subtotals are 161 for x86-64, 100 for RISC-V, and 99 for ARM. - -### Comments on the measurements - -Before the correctness fixes, this cohort had 235 moves / 354 weighted moves. -The corrected baseline before lazy memory cost three more of each. The final narrow x86 -store-mask backport accounts for two of those moves: an integer byte/short store -cannot consume an XMM register. This is a correctness cost, not a quality gain. -The fixed-neighbor color-bias correction changes no counts in this cohort. - -With lazy memory and selected-read ordering, the same 39 compilations have -234 moves / 360 weighted moves, versus 238 / 357 before the port. Register -legality passes on every target; allocator heuristics are unchanged. The changed -programs are: - -| Program | Target | Moves before / after | Weighted before / after | -|---|---|---:|---:| -| Array access (`testAlloc2`) | x86-64 | 1 / 2 | 1 / 2 | -| Array prefix sum (`testArray1`) | x86-64 | 5 / 6 | 5 / 13 | -| String hash | x86-64 | 7 / 5 | 21 / 19 | -| String hash | RISC-V | 4 / 3 | 4 / 3 | -| String hash | ARM | 5 / 3 | 5 / 3 | -| Merge sort | ARM | 37 / 36 | 37 / 36 | - -The prefix sum's extra loop move follows from scheduling selected reads before -clobbering writes. A diagnostic build omitting that ordering returns to 5 / 5; -it is not a valid alternative schedule. These are changed frontend and scheduling -graphs, not a comparison of allocator heuristics. The new memory-allocation -regressions check legality but do not add entries to this measured cohort. - -Later chapters will add one quality technique at a time and end with this kind -of table: Chapter 21 will measure both the Chapter 20 and Chapter 21 program -cohorts using its allocator, and Chapter 25 will have rows for cohorts 20-25. -Keep the program/target membership and seeds fixed when comparing a row between -chapters, and separate changes in the optimizer or instruction selection from -changes in allocation. A local regression may be worthwhile when the total -improves; an allocation failure or illegal register assignment never is. +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 `8^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 20 | 39 | 360 | +<!-- spill-matrix:end --> + +These Windows measurements use optimizer seed 123 for cohorts 20-24 and include +x86-64 SystemV/Win64 and ARM/RISC-V SystemV as applicable. Run `make spill-stats` +here for this compiler, or at the repository root to rebuild the full matrix +and check cohort membership. See the [complete comparison](../docs/regalloc-spills.md) +for measurement details and reproduction commands. + +Cohort 20 contains 11 Chapter20Test programs plus BrainFuck and MergeSort, +each on three SystemV targets: 39 compilations. Synthetic allocator graphs +check correctness separately. This is the baseline; later chapters extend the +columns while keeping these programs and targets fixed. diff --git a/chapter20/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter20/src/main/java/com/seaofnodes/simple/IterPeeps.java index 42cfedba..a21fb517 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -46,7 +46,12 @@ public class IterPeeps { private 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); + } public <N extends Node> N add( N n ) { return (N)_work.push(n); } @@ -56,12 +61,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); 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/chapter20/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index ba04922b..0ee3d418 100644 --- a/chapter20/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter20/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -96,6 +96,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()) ) + { fptr.addDep(this); 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 ) in.addDep(this); + if( ret.ctrl()!=fun ) return 0; + TINYBODY[0] = fun; + int len=1; + for( int i=0; i<len; i++ ) { + Node n = TINYBODY[i]; + n.addDep(this); + 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 ) { use.addDep(this); return 0; } + TINYBODY[len++] = use; + } + } + return len; + } + @Override public Node pcopy(int idx) { return _folding ? in(1).in(idx) : null; } diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 6b7b5d85..4abc9117 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter20/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/chapter20/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java index 23d0ef37..6377bc14 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java +++ b/chapter20/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/chapter20/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter14Test.java index 3a514763..f0fe7dcd 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/chapter20/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/chapter20/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 73014399..6a22ff97 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter15Test.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.*; public class Chapter15Test { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter16Test.java index 884597cf..362388d6 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -3,12 +3,14 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.evaluator.Evaluator; 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 Chapter16Test { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index ff35f904..da619ed3 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/chapter20/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/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java index b5cc0682..dafd2f3a 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -123,6 +123,7 @@ public class Chapter18Test { } + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( @@ -462,7 +463,7 @@ if (i2i) return i2i(arg); return f2f(o)(1); """); code.parse().opto().typeCheck().GCM().localSched(); - assertEquals("Stop[ return Phi(Region,#2,#2); return Parm_i(o,int); ]", code._stop.toString()); + assertEquals("Stop[ return Phi(Region,#2,1); return Parm_i(o,int); ]", code._stop.toString()); assertEquals("1", Eval2.eval(code, 2)); } diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter19Test.java index 3cc7d5ab..9bd75207 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -31,6 +31,7 @@ public class Chapter19Test { } + @Ignore @Test public void testJig() { CodeGen code = new CodeGen(""" diff --git a/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 5a7375f5..104be01e 100644 --- a/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter20/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -60,6 +60,7 @@ return f(s); } + @Ignore @Test public void testJig() { CodeGen code = new CodeGen("return 0;"); |