Restore missing anti-dependence walk

2 files changed, 33 insertions, 10 deletions

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,