diff options
Diffstat (limited to 'chapter21')
5 files changed, 46 insertions, 15 deletions
diff --git a/chapter21/README.md b/chapter21/README.md index c553390a..a2222a8f 100644 --- a/chapter21/README.md +++ b/chapter21/README.md @@ -158,9 +158,9 @@ by `8^loopDepth`. | Program cohort | Compilations | Retained moves | Loop-weighted moves | |---|---:|---:|---:| -| Chapter 20 | 39 | 367 | 472 | -| Chapter 21 | 52 | 454 | 972 | -| **Total** | **91** | **821** | **1,444** | +| 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 @@ -204,6 +204,14 @@ 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: diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 9945374a..447a6df1 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -267,22 +267,22 @@ public abstract class GlobalCodeMotion { switch( mem ) { case MemOpNode st: assert late[st._nid]!=null; - lca = anti_dep(load,late[st._nid],lca,st,anti); + lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); break; case CallNode st: assert late[st._nid]!=null; - lca = anti_dep(load,late[st._nid],lca,st,anti); + lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); break; case PhiNode phi: // Repeat anti-dep for matching Phi inputs. // No anti-dep edges but may raise the LCA. for( int i=1; i<phi.nIns(); i++ ) if( phi.in(i)==load.mem() ) - lca = anti_dep(load,phi.region().cfg(i),lca,null,anti); + lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null,anti); break; case NewNode st: assert late[st._nid]!=null; - lca = anti_dep(load,late[st._nid],lca,st,anti); + lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); break; default: throw Utils.TODO(); } @@ -291,12 +291,17 @@ public abstract class GlobalCodeMotion { } // - private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode lca, Node st, int[] anti ) { - // Stores are already placed. Constrain the load at that block only. - if( anti[stblk._nid]==load._nid ) { - lca = stblk.domLCA(lca,null); - if( lca==stblk && st!=null && !(st instanceof CallNode) && st._inputs.find(load) == -1 ) - st.addDef(load); // Same-block load must precede the store. + private static CFGNode anti_dep( MemOpNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st, int[] anti ) { + // A conditional writer can precede the load without dominating its late block. + // Walk back to the first overlap with the load's placement range. + for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { + // Store and Load overlap, need anti-dependence + if( anti[stblk._nid]==load._nid ) { + lca = stblk.domLCA(lca,null); // Raise Loads LCA + if( lca == stblk && st != null && !(st instanceof CallNode) && st._inputs.find(load) == -1 ) // And if something moved, + st.addDef(load); // Add anti-dep as well; Calls already end their block. + return lca; // Cap this stores' anti-dep to here + } } return lca; } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index 97d33b70..aa6fada0 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -20,7 +20,7 @@ public class BrainFuckTest { String brain_fuck = "Hello World!\n"; TestC.run("brain_fuck", brain_fuck, 40); - EvalRisc5 R5 = TestRisc5.build("brain_fuck", 0, 42, false); + EvalRisc5 R5 = TestRisc5.build("brain_fuck", 0, 146, false); int trap = R5.step(100000); assertEquals(0,trap); int ptr = (int)R5.regs[riscv.A0]; diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 250acaa2..8112917e 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -306,7 +306,7 @@ for( int pc = 0; pc < program#; pc++ ) { return output; """; testTarget(src,"x86_64_v2", "SystemV",40,null); - testTarget(src,"riscv" , "SystemV",42,null); + testTarget(src,"riscv" , "SystemV",146,null); testTarget(src,"arm" , "SystemV",34,null); //assertEquals("Hello World!\n", Eval2.eval(code, 0, 10000)); } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 94170fcb..f431feeb 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -16,6 +16,24 @@ import static org.junit.Assert.*; public class Chapter21Test { + @Test public void testReadBeforeConditionalStore() { + var code = new CodeGen(""" + struct S { int x; }; S !a=new S; S !b=new S; + a.x=10; b.x=20; S !p=a; if(arg&1) p=b; + int sum=0; + for(int i=0; i<6; i++) { + sum+=a.x; + if(i==2) p.x=30; + else if(i==4) b.x=40; + } + return sum; + """).parse().opto(); + // The i==2 read still sees 10: three reads of 10, then three of 30. + assertEquals("120",Eval2.eval(code,0)); + assertEquals("60",Eval2.eval(code,1)); + } + + @Test public void testArmBitfieldExtracts() { // Independent SXT/UXT instruction words, plus ASR, LSR and LSL aliases. int[] ops = {0x93401c20,0xd3401c20,0x93403c20,0xd3403c20, |