diff options
15 files changed, 201 insertions, 68 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, diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 21a8ad76..530336d6 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -266,22 +266,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(); } @@ -290,12 +290,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/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 926acf93..a52cb80b 100644 --- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -17,6 +17,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, diff --git a/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 1d802cae..80d5d9bb 100644 --- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -266,22 +266,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(); } @@ -290,12 +290,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/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 9aa18821..7e82e37c 100644 --- a/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter23/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -18,6 +18,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, diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 1d802cae..80d5d9bb 100644 --- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -266,22 +266,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(); } @@ -290,12 +290,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/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 65b59fab..896b9317 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -18,6 +18,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, diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 484bcaa9..8eebc15b 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -266,22 +266,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 EscapeNode 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 call: assert late[call._nid]!=null; - lca = anti_dep(load,late[call._nid],lca,call,anti); + lca = anti_dep(load,late[call._nid],call.cfg0(),lca,call,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; default: throw Utils.TODO("Should not reach here"); } @@ -290,12 +290,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/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java index c3d93188..93a9e63f 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -15,6 +15,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, diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index 7332cb48..ec6a727a 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -160,9 +160,10 @@ on a rejected Phi factoring attempt. Those fixes predate this memory port. All three targets retain the memory Phi subclasses and New's pointer slot 0, memory slot 1, and size input 2. Chapter 21 caches New's register masks in the -shared node during register allocation; update that shared interface. Keep its -existing scheduler rule that writers are already placed when adding read-before- -write constraints. Calls receive no scheduling-only operands. +shared node during register allocation; update that shared interface. Writers +are placed before adding read-before-write constraints; the dominator walk +must still find conditional writers above a Load's proposed merge placement. +Calls receive no scheduling-only operands. Dependency registration reverses direction here: `consumer.addDep(producer)`. The forwarded memory queries and explicit forward dependencies follow that API. @@ -360,15 +361,6 @@ lines beyond the original extraction. suite passes, including its current String programs. -- **Chapter 21 read-before-conditional-store scheduling.** A reduced negative - test for Load search exposed an existing ordering error: summing `a.x` before - a possibly aliasing conditional store in a loop returns 140 instead of 120 - when the pointer aliases `a`. It reproduces with the saved pre-search Load - class as well. Source and before/after graph dumps are in - `build/LoadSearchProbe.java` and `build/load-search-probe-{before,after}.txt`. - The Load-search rejection tests put the Store before the read to isolate - the optimization from that separate scheduling defect. Investigate separately. - - **Chapter 21 synthetic TOP return allocation.** The original compiler at `f01ee052` and the memory port both fail in `Coalesce.coalesce`: a Split of TOP has no input live range. Reproduction: `struct S { int x; int y; }; @@ -573,6 +565,21 @@ The top-level runner accepts explicit chapter lists, e.g. ## Validation record +- **GCM conditional-writer ordering, Chapters 21-25.** Restored the `idom()` + walk from a writer's late block through its early bound, including matching + memory-Phi predecessor paths. Chapters 11-20 already retained this walk. + Exact-block checking missed a conditional Store that executes before a Load + sunk below the merge. `Chapter21Test.testReadBeforeConditionalStore`, forwarded + through 25, checks 120 for the aliasing case and 60 for the distinct-pointer + case. Generated ARM/RISC-V execution agrees in Chapter 21. The walk was + removed in `798bd959` (April 12, 2025, PR #201), before the Chapter 21 squash. + Chapter 21's two RISC-V BrainFuck rows change from 35 / 42 to 48 / 146 + retained / weighted moves; the full 91-entry audit is now 847 / 1,652. + Runtime checks pass and the two quality goldens are updated; no allocator + heuristic changed. Validation logs: `build/gcm-walk-tests.log` (22-24), + `build/gcm-walk21-final.log` (complete 21 rerun and spill audit), and + `build/gcm-walk25-final.log` (complete 25 rerun). + - **Chapter 25 memory follow-through.** Full Make validation passes **482 tests plus the 17-seed fuzzer wrapper**, and the release jar and system library build. The loop-search and read-before-write regressions fail against the original LoadNode and pass with the port. A diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index 208494e7..c409cd55 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -260,7 +260,10 @@ For shared viewer work, read [the graph viewer notes](graph-viewer-codex-notes.m - Keep anti-dependence marks in a pass-local array, not CFGNode. In 11-20 the evaluator independently reschedules nodes, so retain the full store placement range when constraining loads; using only GCM's final store block breaks - `SchedulerTest.testStoreInIf2`. From 21, the chosen store block suffices. + `SchedulerTest.testStoreInIf2`. Retain the dominator walk from 21 onward too: + a conditional Store can precede a Load's late block without dominating it. + Its exact block need not be marked, but an ancestor intersects the Load's + placement range. `Chapter21Test.testReadBeforeConditionalStore` checks this. Preserve each chapter's alias/tuple memory representation when finding stores. - Changes in node order can expose encoding bugs. Chapter 21's empty-block scan mistook entry to a nested loop for a backedge; require the same loop-tree node, |