From c0b6e387d7c40aec9e8d626976f4cfac27c54f90 Mon Sep 17 00:00:00 2001
From: Cliff Click <cliffc@acm.org>
Date: Sun, 20 Apr 2025 12:14:22 -0700
Subject: Fix bugs

One more encoding invert-branch test version, with extensive comments and symmetry pointed out.  Fixes missing back branch at loop end.

Switch the arguments to `dep.addDep(this)` to become `this.addDep(dep)` shortened to `addDep(dep)`.

One more missing dep in Region fusing.
---
 .../com/seaofnodes/simple/codegen/Encoding.java    | 34 ++++++++++++++++------
 .../java/com/seaofnodes/simple/node/AddNode.java   |  2 +-
 .../java/com/seaofnodes/simple/node/CFGNode.java   |  4 +--
 .../java/com/seaofnodes/simple/node/CProjNode.java |  2 +-
 .../com/seaofnodes/simple/node/CallEndNode.java    |  6 ++--
 .../com/seaofnodes/simple/node/ConstantNode.java   |  2 +-
 .../java/com/seaofnodes/simple/node/IfNode.java    |  2 +-
 .../java/com/seaofnodes/simple/node/LoadNode.java  |  6 ++--
 .../main/java/com/seaofnodes/simple/node/Node.java | 19 ++++++------
 .../java/com/seaofnodes/simple/node/PhiNode.java   | 14 ++++-----
 .../com/seaofnodes/simple/node/RegionNode.java     | 14 ++++-----
 .../java/com/seaofnodes/simple/node/ShlNode.java   |  2 +-
 .../java/com/seaofnodes/simple/node/StoreNode.java |  2 +-
 .../java/com/seaofnodes/simple/Chapter21Test.java  |  4 +--
 14 files changed, 64 insertions(+), 49 deletions(-)

diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
index 6d6248e4..c822a73e 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Encoding.java
@@ -228,16 +228,8 @@ public class Encoding {
             // Pick out the T/F projections
             CProjNode t = iff.cproj(0);
             CProjNode f = iff.cproj(1);
-            int tld = t.loopDepth(), fld = f.loopDepth(), bld = iff.loopDepth();
             // Invert the branch or not
-            if( tld >= bld &&   // true to exit a loop
-                // false to exit a loop, invert to true
-                (fld < bld ||
-                 // Else not exiting (staying or entering deeper).
-                 // Fall/false into a full block, Jump/true to an empty block.
-                 ( f.nOuts()==1 && (t.nOuts()>1 ||
-                                    // Everything else equal, use pre-order
-                                    t._pre > f._pre) )) ) {
+            if( shouldInvert(t,f,iff.loopDepth()) ) {
                 iff.negate();
                 t.invert();
                 f.invert();
@@ -278,6 +270,30 @@ public class Encoding {
         rpo.add(bb);
     }
 
+    // Should this test be inverted?
+    private static boolean shouldInvert(CFGNode t, CFGNode f, int bld) {
+        int tld = t.loopDepth(), fld = f.loopDepth();
+        // These next two are symmetric and can happen in any order; if `tld <
+        // bld` is true, the `fld < bld` must be false, or else both directions
+        // exit the loop... and the IF test would not be in the loop.
+
+        // true to exit a loop usually, keep true if taking an empty backwards branch
+        if( tld < bld ) return  emptyBackBlock(f,bld);
+        // false to exit a loop, normally invert to true (except empty back)
+        if( fld < bld ) return !emptyBackBlock(t,bld);
+
+        // Not exiting the loop; staying at this depth (or going deeper loop).
+        // Fall/false into a full block, Jump/true to an empty block.
+        if( f.nOuts()>1 && t.nOuts()==1 ) return false;
+        if( t.nOuts()>1 && f.nOuts()==1 ) return true ;
+        // Everything else equal, use pre-order
+        return t._pre > f._pre;
+    }
+
+    private static boolean emptyBackBlock( CFGNode c, int bld ) {
+        return c.loopDepth()==bld && c.nOuts()==1 && c.uctrl() instanceof LoopNode;
+    }
+
     // Is the CFG from "next" to the end empty?  This means jumping to "next"
     // will naturally fall into the end.
     private static boolean isEmptyBackwardsScan(Ary<CFGNode> rpo, CFGNode next) {
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 01d31aa2..dd128e76 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -96,7 +96,7 @@ public class AddNode extends Node {
         // If lhs.in(2) is not a constant, we add ourselves as a dependency
         // because if it later became a constant then we could make this
         // transformation.
-        if( lhs.in(2).addDep(this)._type.isConstant() && rhs._type.isConstant() )
+        if( addDep(lhs.in(2))._type.isConstant() && rhs._type.isConstant() )
             return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole());
 
 
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java
index fd17092f..56a33a26 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CFGNode.java
@@ -84,8 +84,8 @@ public abstract class CFGNode extends Node {
         CFGNode lhs = this;
         while( lhs != rhs ) {
             var comp = lhs.idepth() - rhs.idepth();
-            if( comp >= 0 ) lhs = ((CFGNode)lhs.addDep(dep)).idom();
-            if( comp <= 0 ) rhs = ((CFGNode)rhs.addDep(dep)).idom();
+            if( comp >= 0 ) lhs = (dep==null ? lhs : dep.addDep(lhs)).idom();
+            if( comp <= 0 ) rhs = (dep==null ? rhs : dep.addDep(rhs)).idom();
         }
         return lhs;
     }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/CProjNode.java
index 4554284f..94770f16 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/CProjNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CProjNode.java
@@ -46,7 +46,7 @@ public class CProjNode extends CFGNode {
         }
 
         // Flip a negating if-test, to remove the not
-        if( ctrl() instanceof IfNode iff && iff.pred().addDep(this) instanceof NotNode not )
+        if( ctrl() instanceof IfNode iff && addDep(iff.pred()) instanceof NotNode not )
             return new CProjNode(new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True");
 
         // Copy of some other input
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 e1f64ca0..47975833 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/CallEndNode.java
@@ -38,7 +38,7 @@ public class CallEndNode extends CFGNode implements MultiNode {
             return TypeTuple.RET.dual();
         Type ret = Type.BOTTOM;
         TypeMem mem = TypeMem.BOT;
-        if( call.fptr().addDep(this)._type instanceof TypeFunPtr tfp ) {
+        if( addDep(call.fptr())._type instanceof TypeFunPtr tfp ) {
             ret = tfp.ret();
             // Here, if I can figure out I've found *all* callers, then I can meet
             // across the linked returns and join with the function return type.
@@ -84,10 +84,10 @@ public class CallEndNode extends CFGNode implements MultiNode {
                         return this;
                     }
                 } else {
-                    fun.addDep(this);
+                    addDep(fun);
                 }
             } else { // Function ptr has multiple users (so maybe multiple call sites)
-                fptr.addDep(this);
+                addDep(fptr);
             }
         }
 
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
index 2880ed61..79f301c1 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/ConstantNode.java
@@ -45,7 +45,7 @@ public class ConstantNode extends Node {
     public StringBuilder _print1(StringBuilder sb, BitSet visited) {
         if( _con instanceof TypeFunPtr tfp && tfp.isConstant() ) {
             FunNode fun = CodeGen.CODE.link(tfp);
-            if( fun._name != null )
+            if( fun!=null && fun._name != null )
                 return sb.append("{ ").append(fun._name).append("}");
         }
         return sb.append(_con==null ? "---" : _con.print(new SB()));
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/IfNode.java
index 5b26f23d..5d90449e 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -58,7 +58,7 @@ public class IfNode extends CFGNode implements MultiNode {
         // test on either the true or false branch, that side wins.
         if( !pred()._type.isHighOrConst() )
             for( CFGNode dom = idom(), prior=this; dom!=null;  prior = dom, dom = dom.idom() )
-                if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof CProjNode prj ) {
+                if( addDep(dom) instanceof IfNode iff && addDep(iff.pred())==pred() && prior instanceof CProjNode prj ) {
                     setDef(1,con( prj._idx==0 ? 1 : 0 ));
                     return this;
                 }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index b8ddeca4..6147de81 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -77,7 +77,7 @@ public class LoadNode extends MemOpNode {
         while( true ) {
             switch( mem ) {
             case StoreNode st:
-                if( ptr == st.ptr().addDep(this) && off() == st.off() )
+                if( ptr == addDep(st.ptr()) && off() == st.off() )
                     return extend(castRO(st.val())); // Proved equal
                 // Can we prove unequal?  Offsets do not overlap?
                 if( !off()._type.join(st.off()._type).isHigh() && // Offsets overlap
@@ -88,7 +88,7 @@ public class LoadNode extends MemOpNode {
                 break;
             case PhiNode phi:
                 // Assume related
-                phi.addDep(this);
+                addDep(phi);
                 break outer;
             case ConstantNode top: break outer;  // Assume shortly dead
             case ProjNode mproj: // Memory projection
@@ -182,7 +182,7 @@ public class LoadNode extends MemOpNode {
         if( px==null ) return false;
         if( px._type instanceof TypeMem mem && mem._t.isHighOrConst() ) return true;
         if( px instanceof StoreNode st1 && ptr()==st1.ptr() && off()==st1.off() ) return true;
-        px.addDep(this);
+        addDep(px);
         return false;
     }
 
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java
index c02a4924..c0c2e606 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -549,17 +549,16 @@ public abstract class Node implements Cloneable {
      * or output of this node, that is, it is at least one step away.  The node
      * being added must benefit from this node being peepholed.
      */
-    Node addDep( Node dep ) {
+    <N extends Node> N addDep( N dep ) {
         // Running peepholes during the big assert cannot have side effects
         // like adding dependencies.
-        if( CODE._midAssert ) return this;
-        if( dep == null ) return this;
-        if( _deps==null ) _deps = new Ary<>(Node.class);
-        if( _deps   .find(dep) != -1 ) return this; // Already on list
-        if( _inputs .find(dep) != -1 ) return this; // No need for deps on immediate neighbors
-        if( _outputs.find(dep) != -1 ) return this;
-        _deps.add(dep);
-        return this;
+        if( CODE._midAssert ) return dep;
+        if( dep._deps==null ) dep._deps = new Ary<>(Node.class);
+        if( dep._deps   .find(this) != -1 ) return dep; // Already on list
+        if( dep._inputs .find(this) != -1 ) return dep; // No need for deps on immediate neighbors
+        if( dep._outputs.find(this) != -1 ) return dep;
+        dep._deps.add(this);
+        return dep;
     }
 
     // Move the dependents onto a worklist, and clear for future dependents.
@@ -667,7 +666,7 @@ public abstract class Node implements Cloneable {
     boolean allCons(Node dep) {
         for( int i=1; i<nIns(); i++ )
             if( !(in(i)._type.isConstant()) ) {
-                in(i).addDep(dep); // If in(i) becomes a constant later, will trigger some peephole
+                dep.addDep(in(i)); // If in(i) becomes a constant later, will trigger some peephole
                 return false;
             }
         return true;
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 5e2e3056..ed46c8f9 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -58,7 +58,7 @@ public class PhiNode extends Node {
         for (int i = 1; i < nIns(); i++)
             // If the region's control input is live, add this as a dependency
             // to the control because we can be peeped should it become dead.
-            if( r.in(i).addDep(this)._type != Type.XCONTROL )
+            if( addDep(r.in(i))._type != Type.XCONTROL )
                 t = t.meet(in(i)._type);
         return t;
     }
@@ -87,8 +87,8 @@ public class PhiNode extends Node {
 
         // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove.
         if( nIns()==3 ) {
-            if( in(1) instanceof CastNode cast && cast.in(1).addDep(this)==in(2) ) return in(2);
-            if( in(2) instanceof CastNode cast && cast.in(1).addDep(this)==in(1) ) return in(1);
+            if( in(1) instanceof CastNode cast && addDep(cast.in(1))==in(2) ) return in(2);
+            if( in(2) instanceof CastNode cast && addDep(cast.in(1))==in(1) ) return in(1);
         }
         // If merging a null-checked null and the checked value, just use the value.
         // if( val ) ..; phi(Region,False=0/null,True=val);
@@ -101,7 +101,7 @@ public class PhiNode extends Node {
                 Node val = in(3-nullx);
                 if( val instanceof CastNode cast )
                     val = cast.in(1);
-                if( r.idom(this).addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==val ) {
+                if( addDep(r.idom(this)) instanceof IfNode iff && addDep(iff.pred())==val ) {
                     // Must walk the idom on the null side to make sure we hit False.
                     CFGNode idom = (CFGNode)r.in(nullx);
                     while( idom != null && idom.nIns() > 0 && idom.in(0) != iff ) idom = idom.idom();
@@ -122,7 +122,7 @@ public class PhiNode extends Node {
             if( in(1).getClass() != op.getClass() || op.in(0)!=null || in(1).nIns() != op.nIns() )
                 return false;      // Wrong class or CFG bound or mismatched inputs
             if( op.nOuts() > 1 ) { // Too many users, but addDep in case lose users
-                for( Node out : op._outputs ) if( out!=null ) out.addDep(this);
+                for( Node out : op._outputs ) if( out!=null ) addDep(out);
                 return false;
             }
         }
@@ -168,7 +168,7 @@ public class PhiNode extends Node {
         for( int i=1; i<nIns(); i++ ) {
             // If the region's control input is live, add this as a dependency
             // to the control because we can be peeped should it become dead.
-            if( region().in(i).addDep(this)._type != Type.XCONTROL && in(i) != this )
+            if( addDep(region().in(i))._type != Type.XCONTROL && in(i) != this )
                 if( live == null || live == in(i) ) live = in(i);
                 else return null;
         }
@@ -180,7 +180,7 @@ public class PhiNode extends Node {
         if( !(region() instanceof RegionNode r) ) return false;
         // When the region completes (is no longer in progress) the Phi can
         // become a "all constants" Phi, and the "dep" might make progress.
-        addDep(dep);
+        dep.addDep(this);
         if( r.inProgress() ) return false;
         return super.allCons(dep);
     }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index 583a4088..8c56feff 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -48,7 +48,7 @@ public class RegionNode extends CFGNode {
         if( !hasPhi() &&         // No Phi users, just a control user
             in(1) instanceof CProjNode p1 &&
             in(2) instanceof CProjNode p2 &&
-            p1.in(0).addDep(this)==p2.in(0).addDep(this) &&
+            addDep(p1.in(0))==addDep(p2.in(0)) &&
             p1.in(0) instanceof IfNode iff ) {
             // Replace with the iff.ctrl directly
             if( nIns()==3 ) return iff.ctrl();
@@ -122,18 +122,18 @@ public class RegionNode extends CFGNode {
         return false;
     }
 
+    // Is there a value in-between 2 Regions?  Difficult to correctly fuse
+    // without extensive testing, so just ignore.
     boolean hasMidUser(RegionNode r) {
         for( Node use : r._outputs ) {
             if( use==this ) continue;
             if( use instanceof PhiNode ) {
                 for( Node data : use._outputs ) {
-                    if( !(data instanceof PhiNode phi2) || phi2.region()!=this ) {
-                        use.addDep(this); return true; }
-                    assert phi2.region()==this;
+                    if( !(data instanceof PhiNode phi2) || phi2.region()!=this )
+                        { addDep(use); addDep(data); return true; }
                 }
-            } else {
-                use.addDep(this);
-                return true; } // Control user
+            } else
+                { addDep(use);  return true; } // Control user
         }
         return false;
     }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/ShlNode.java
index 21dbd503..82e01841 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/ShlNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/ShlNode.java
@@ -38,7 +38,7 @@ public class ShlNode extends LogicalNode {
             if( (shl.value()&63)==0 )
                 return lhs;
             // (x + c) << i  =>  (x << i) + (c << i)
-            if( lhs instanceof AddNode add && add.addDep(this).in(2)._type instanceof TypeInteger c && c.isConstant() ) {
+            if( lhs instanceof AddNode add && addDep(add).in(2)._type instanceof TypeInteger c && c.isConstant() ) {
                 long sum = c.value() << shl.value();
                 if( Integer.MIN_VALUE <= sum  && sum <= Integer.MAX_VALUE )
                     return new AddNode(new ShlNode(_loc,add.in(1),rhs).peephole(), Parser.con(sum) );
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java
index e8f5c4e2..b9f99f4e 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java
@@ -94,7 +94,7 @@ public class StoreNode extends MemOpNode {
         // when the other uses go away we can retry.
         for( Node use : mem._outputs )
             if( use != this )
-                use.addDep(this);
+                addDep(use);
         return false;
     }
 
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java
index 2a5082a0..ed869ed3 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java
@@ -12,10 +12,10 @@ import static org.junit.Assert.*;
 
 public class Chapter21Test {
 
-    @Test @Ignore
+    @Test
     public void testJig() throws IOException {
         String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/jig.smp"));
-        testCPU(src,"x86_64_v2", "Win64",-1,null);
+        testCPU(src,"x86_64_v2", "Win64"  ,-1,null);
         testCPU(src,"riscv"    , "SystemV",-1,null);
         testCPU(src,"arm"      , "SystemV",-1,null);
     }
-- 
cgit v1.2.3