diff options
Diffstat (limited to 'chapter22')
6 files changed, 57 insertions, 13 deletions
diff --git a/chapter22/README.md b/chapter22/README.md index 229c78d9..96c02ef1 100644 --- a/chapter22/README.md +++ b/chapter22/README.md @@ -189,17 +189,23 @@ are cheap to split. Register order breaks ties between callee saves. These are small preferences, not a general cost model. Grouping popular values by register class is left for Chapter 23, cold loop splits for 24, and area/cost ranking for 25. +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. 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` in this directory. Each row below uses **this chapter's compiler**, default worklist seed 123, and the same source/target combinations as the earlier cohort. The Windows run combines x86 SystemV/Win64 and RISC-V/ARM SystemV. Diagnostic graphs and mask regressions do not contribute to the totals. -| Program cohort | Compilations | Split/move count | Loop-weighted count | +| Program cohort | Compilations | Retained moves | Loop-weighted moves | |---|---:|---:|---:| -| Chapter 20 | 39 | 324 | 443 | -| Chapter 21 | 52 | 447 | 986 | -| Chapter 22 | 24 | 67 | 67 | -| **Total** | **115** | **838** | **1,496** | +| Chapter 20 | 39 | 321 | 433 | +| Chapter 21 | 52 | 438 | 970 | +| Chapter 22 | 26 | 67 | 67 | +| **Total** | **117** | **826** | **1,470** | `_spills` counts retained SplitNodes, including register moves; `_spillScaled` weights each by `8^loopDepth`. These are compiler estimates, not measured runtime @@ -207,7 +213,7 @@ memory traffic. The reporter also prints individual allocations and CPU/ABI sums Chapter 21's original `int age` person example is preserved as `person21`; this chapter's `i32 age` version and revised infinite-loop example belong to cohort 22. -For a controlled comparison, the same compiler and correctness fixes with +Before adjacent-copy forwarding, a controlled comparison of the same compiler and correctness fixes with Chapter 21's color preferences and spill ordering produce 885 moves and 1,543 weighted moves. This chapter saves **47 weighted moves (3.0%)**. RISC-V BrainFuck improves from 42 to 28 and ARM from 34 to 28 in each of its two cohorts. Some diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index c0be96f1..ea911007 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -536,8 +536,8 @@ public class RegAlloc { if( defreg != usereg && splitBypass(bb,j,n,defreg) ) usereg = lrg(n.in(1))._reg; - // Split has same reg? Useless! Can remove it! - if( defreg == usereg ) { + // Same register, or the next instruction can use the source directly. + if( defreg == usereg || splitForward(bb,j,n,usereg) ) { n.removeSplit(); j--; continue; @@ -550,6 +550,18 @@ public class RegAlloc { } } + // A sole, adjacent use can read the source register directly. Nothing can + // clobber it in between; only the operand mask and two-address tie remain. + private boolean splitForward( CFGNode bb, int j, Node split, int reg ) { + if( split.nOuts()!=1 || j+1==bb.nOuts() ) return false; + Node use = split.out(0); + if( use!=bb.out(j+1) || use instanceof PhiNode || use instanceof CFGNode || + !(use instanceof MachNode mach) ) return false; + int i = use._inputs.find(split); + RegMask mask = mach.regmap(i); + return mask!=null && mask.test(reg) && mach.twoAddress()!=i; + } + private boolean splitBypass( CFGNode bb, int j, Node lo, int defreg ) { // Attempt to bypass split Node hi = lo.in(1); diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 1f4a3d27..828a2824 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -115,7 +115,7 @@ val sqrt = { int x -> }; return sqrt(arg) + sqrt(arg+2); """; - testTarget(src,"x86_64_v2", "SystemV",48,null); + testTarget(src,"x86_64_v2", "SystemV",40,null); testTarget(src,"riscv" , "SystemV",17,null); testTarget(src,"arm" , "SystemV",18,null); } @@ -162,7 +162,7 @@ for( int i=0; i<ary#-1; i++ ) ary[i+1] += ary[i]; return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 """; - testTarget(src,"x86_64_v2", "SystemV",9,"return .[];"); + testTarget(src,"x86_64_v2", "SystemV",7,"return .[];"); testTarget(src,"riscv" , "SystemV",7,"return (add,.[],(mul,.[],1000));"); testTarget(src,"arm" , "SystemV",5,"return (add,.[],(mul,.[],1000));"); } diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java index 4fddbb4b..b81483d8 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java @@ -21,7 +21,7 @@ val sqrt = { int x -> }; return sqrt(arg) + sqrt(arg+2); """; - Chapter21Test.testCPU(src,"x86_64_v2", "Win64" ,48,null); + Chapter21Test.testCPU(src,"x86_64_v2", "Win64" ,40,null); Chapter21Test.testCPU(src,"riscv" , "SystemV",19,null); Chapter21Test.testCPU(src,"arm" , "SystemV",19,null); } @@ -49,7 +49,7 @@ return sqrt(arg) + sqrt(arg+2); String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash.smp")); Chapter21Test.testCPU(src,"x86_64_v2", "SystemV", 9,null); Chapter21Test.testCPU(src,"riscv" , "SystemV", 3,null); - Chapter21Test.testCPU(src,"arm" , "SystemV", 3,null); + Chapter21Test.testCPU(src,"arm" , "SystemV", 1,null); } } diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 28804cfd..4e1aadd9 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -231,6 +231,7 @@ public class Chapter21Test { } @Test public void testCoalescing() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coalescing(); } + @Test public void testCopyForward() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.copyForward(); } @Test public void testRisc64BitStore() { byte[] mem = new byte[24]; EvalRisc5 cpu = new EvalRisc5(mem,mem.length); @@ -312,7 +313,7 @@ public class Chapter21Test { String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash.smp")); testCPU(src,"x86_64_v2", "SystemV", 9,null); testCPU(src,"riscv" , "SystemV", 3,null); - testCPU(src,"arm" , "SystemV", 3,null); + testCPU(src,"arm" , "SystemV", 1,null); } @Test public void testStringExport() throws IOException { diff --git a/chapter22/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter22/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index e4643ee6..0c5edaa1 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -176,6 +176,31 @@ public class RegAllocTestSupport { assertFalse("A fixed definition clobbers even before coloring",uncolored.sameBlockNoClobber(copy)); } + public static void copyForward() throws Exception { + // Forwarding, fixed operand, two-address tie, intervening clobber, + // another user, and a scheduling-only edge. + for( int kind=0; kind<6; kind++ ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(A,null,null,false,code._start); + alloc.newLRG(def)._reg=0; + SplitNode copy = code._mach.split("test",(byte)0,null); + copy.setDef(0,code._start); copy.setDef(1,def); + alloc.newLRG(copy)._reg=1; + if( kind==3 ) new Op(null,null,A,false,code._start); + int twoAddress = kind==2 ? 1 : 0; + RegMask mask = kind==1 ? B : kind==5 ? null : new RegMask(3L); + Op use = new Op(null,mask,null,false,code._start,copy) { + @Override public int twoAddress() { return twoAddress; } + }; + if( kind==4 ) new Op(null,B,null,false,code._start,copy); + var post = RegAlloc.class.getDeclaredMethod("postColor"); + post.setAccessible(true); post.invoke(alloc); + assertSame("copy case "+kind,kind==0 ? def : copy,use.in(1)); + assertEquals(kind==0 ? 0 : 1,alloc._spills); + } + } + public static void coalescing() { // Merge, incompatible masks, interference, capacity, and adjacency remapping. for( int kind=0; kind<5; kind++ ) { |