diff options
Diffstat (limited to 'chapter21')
12 files changed, 150 insertions, 99 deletions
diff --git a/chapter21/README.md b/chapter21/README.md index b8d065ff..63b02ae9 100644 --- a/chapter21/README.md +++ b/chapter21/README.md @@ -135,109 +135,34 @@ excluded from the spill totals. A split inserts a copy between two live ranges. If both can safely become one range, the copy can disappear before coloring. [Coalesce.java](src/main/java/com/seaofnodes/simple/codegen/Coalesce.java) -checks that the ranges do not interfere, intersects their allowed-register masks, -and combines their neighbors. It merges only when the resulting neighbor count -is smaller than the number of available registers. This simple conservative rule -preserves a color choice even if every neighbor takes a different register. - -Merging also updates neighboring adjacency lists and removes sample references -to the deleted copy. A rejected merge restores the original adjacency list. -Mask compatibility alone is insufficient: two values that are simultaneously -live cannot share a register merely because both permit it. +checks that the ranges do not interfere, intersects their allowed-register +masks, and combines their neighbors. It merges only when the resulting +neighbor count is smaller than the number of available registers - meaning it +can always color. After coloring, a copy with one use in the immediately following instruction can also disappear when that operand accepts the source register and is not its two-address operand. For example, `mov rpc=s8; st1 [rpc+4],s1` becomes -`st1 [s8+4],s1`. Adjacency proves that nothing overwrites the source in between. -Phi and control-flow users are excluded. This local cleanup leaves spill +`st1 [s8+4],s1`. Adjacency proves that nothing overwrites the source in between. +Phi and control-flow users are excluded. This local cleanup leaves spill selection unchanged; it complements coalescing without another CFG analysis. -Chapter 20's legality and progress fixes carry forward, including compatible -rematerialization and clobber-aware copy reuse. Chapter 21 retains its native -frame and ABI support. Stronger color bias and cheap-spill ranking are reserved -for Chapter 22, popular-use grouping for 23, cold-first loop splitting for 24, -and area/cost ranking for 25. +For looking at allocator progress, we will keep a table of weighted spill costs +a chapters' tests - and use the later chapter compiler and register allocator +on them. The later chapters also modify the graph (sometimes adding boiler +plate graph) so its not really a 100% fair comparison of how well this +*heuristic* does, but it does give us some idea that we're not losing ground. -These are measured sums with **this chapter's compiler**, default optimizer seed -123, on Windows x86-64. A split is a retained `SplitNode`, including register -moves; it is not necessarily a memory spill. Weighted counts multiply each split -by `8^loopDepth`. +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. -| Program cohort | Compilations | Retained moves | Loop-weighted moves | +<!-- spill-matrix:start --> +| Test cohort | # tests | Ch 20 | Ch 21 | |---|---:|---:|---:| -| Chapter 20 | 39 | 380 | 576 | -| Chapter 21 | 52 | 467 | 1,076 | -| **Total** | **91** | **847** | **1,652** | - -The Chapter 20 row freezes all 13 original inputs, including BrainFuck and -MergeSort, on three SystemV targets. They live in `Chapter20Test`. The revised -sources/ABI cases previously in that file are retained in `Chapter21AllocTest`; -together with `Chapter21Test` and the native BrainFuck/MergeSort tests they form -the Chapter 21 row. That row includes 17 ARM/SystemV, 17 RISC-V/SystemV, eight -x86/SystemV, and ten x86/Win64 compilations. Native host ABI changes affect this -row; compare the same host and targets. - -Before adjacent-copy forwarding, the memory port changed the previous total of 840 / 1,456 to 845 / 1,559, -with identical cohort membership and allocator heuristics. These are all changed -rows; each entry is retained / loop-weighted splits: - -| Cohort / program | Target / ABI | Before | Lazy memory | -|---|---|---:|---:| -| 20 / MergeSort | ARM / SystemV | 44 / 44 | 41 / 41 | -| 20 / BrainFuck | RISC-V / SystemV | 35 / 42 | 37 / 58 | -| 20 / Alloc2 | x86 / SystemV | 3 / 3 | 4 / 4 | -| 20 / Alloc2 | ARM / SystemV | 10 / 10 | 9 / 9 | -| 20 / String | x86 / SystemV | 7 / 14 | 8 / 15 | -| 20 / String | RISC-V / SystemV | 14 / 14 | 10 / 10 | -| 20 / String | ARM / SystemV | 13 / 13 | 10 / 10 | -| 21 / Sieve | x86 / Win64 | 24 / 178 | 24 / 185 | -| 21 / Sieve | RISC-V / SystemV | 19 / 89 | 22 / 92 | -| 21 / Sieve | ARM / SystemV | 23 / 93 | 21 / 91 | -| 21 / BrainFuck | RISC-V / SystemV | 35 / 42 | 46 / 130 | - -RISC-V BrainFuck accounts for most of the weighted increase. A diagnostic run -omitting only read-before-New ordering changes its two rows to 35 / 42 and -37 / 58. That explains most of the cost; the compiler retains the ordering -constraint. No heuristic tuning is included in the memory port. - -The subsequent Load-search improvement folds BrainFuck's fixed program length -through the loop's N-way memory merge. Every backedge arm must fold or return -to unchanged memory for the same pointer. It removes 907 executed heap loads -in the RISC-V Hello World run and reduces stack traffic from 1,006 loads / 572 -stores to 15 / 15. Before copy forwarding, that row had 144 / 165 moves / weighted moves, -and the complete 91-entry total was 943 / 1,594. Adjacent-copy forwarding -reduces these to 35 / 42 and 821 / 1,444 respectively. The RISC-V Hello World -run executes 21,787 instructions instead of 21,920, with unchanged heap and -stack traffic. These are emulator instruction counts, not hardware timings. -The current native BrainFuck test and all runtime assertions are enabled. - -Restoring GCM's anti-dependence dominator walk subsequently changes each -RISC-V BrainFuck row from 35 / 42 to 48 / 146, giving the current table above. -A conditional writer need not dominate a later Load placement, so checking -only the writer's exact block misses required ordering. The restored walk -fixes a read-before-conditional-store program that returned 140 instead of 120. -Both BrainFuck execution checks and the complete 91-entry spill audit pass; -the increased move count is recorded without changing allocator heuristics. - -The following coalescing comparison predates lazy memory. Both sides use the -same compiler from that audit; it is not a fresh ablation of the current graph: - -| Earlier controlled comparison, same 91 compilations | Splits | Loop-weighted splits | -|---|---:|---:| -| Audit compiler with coalescing disabled | 1,070 | 1,889 | -| Audit compiler with coalescing | 840 | 1,456 | - -The controlled run disables only `Coalesce.coalesce` in `graphColor`. Allocation, -register constraints, and runtime checks pass in both runs. The disabled run -reports nine changed spill goldens and exits unsuccessfully, as intended. -Coalescing saves 230 moves (21.5%) and 433 weighted moves (22.9%). Local increases -can still occur; the aggregate, rather than one example, judges the tradeoff. - -The final audit backported narrow x86/RISC-V store masks and corrected ARM -register-bank selection and floating-point memory operations. Restricting byte -stores to legal registers lowers RISC-V BrainFuck from 211 to 42 weighted moves -in each of its two cohorts, reducing the previous table by 44 raw / 338 weighted -moves. These correctness fixes are included on both sides of the comparison. -Earlier measurements made with the broader masks are historical, not the current -baseline. Chapter 20's 357 weighted moves are not a coalescing baseline either: -Chapter 21 changes machine lowering and implements native ABI obligations. +| Ch 20 | 39 | 360 | 576 | +| Ch 21 | 52 | | 1,072 | +<!-- spill-matrix:end --> + diff --git a/chapter21/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter21/src/main/java/com/seaofnodes/simple/IterPeeps.java index ded3da7e..7c2f1b0c 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter21/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); + } @SuppressWarnings("unchecked") public <N extends Node> N add( N n ) { return (N)_work.push(n); } @@ -57,12 +62,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/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 81992327..47e80ca9 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -99,6 +99,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/chapter21/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter12Test.java index ec7b3cb3..0b4ad8ec 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter21/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/chapter21/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java index 23d0ef37..6377bc14 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java +++ b/chapter21/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/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java index 3a514763..f0fe7dcd 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/chapter21/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/chapter21/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 94187d1c..cb92277f 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -4,11 +4,13 @@ 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.*; public class Chapter15Test { + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java index 884597cf..362388d6 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/chapter21/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/chapter21/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index e7f5849d..e8f6e0bd 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/chapter21/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/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 173fb653..7c0af028 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -115,6 +115,7 @@ public class Chapter18Test { } + @Ignore @Test public void testJig() { CodeGen code = new CodeGen( @@ -453,7 +454,7 @@ if (i2i) return i2i(arg); return f2f(o)(1); """); code.driver(Phase.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/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java index 0a92dc20..c53a8e11 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter21/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/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java index be945a0b..e63fb32e 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -89,6 +89,7 @@ return f(s); } + @Ignore @Test public void testJig() { CodeGen code = new CodeGen("return 0;"); |