Chapter 6: Peepholes for Iflinear-chapter06

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Yichen Yan <oraluben@outlook.com>
Co-authored-by: Tamas Hadhazy <helsgithub15@gmail.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

12 files changed, 197 insertions, 33 deletions

diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 081c9276..b37785f6 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -63,7 +63,8 @@ public class AddNode extends Node {
 
         // Now we might see (add add non) or (add non non) but never (add non add) nor (add add add)
         if( !(lhs instanceof AddNode) )
-            return spline_cmp(lhs,rhs) ? swap12() : null;
+            // Rotate; look for (add (phi cons) con/(phi cons))
+            return spline_cmp(lhs,rhs) ? swap12() : phiCon(this,true);
 
         // Now we only see (add add non)
 
@@ -72,23 +73,12 @@ public class AddNode extends Node {
         if( lhs.in(2)._type.isConstant() && t2.isConstant() )
             return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole());
 
-        if( lhs.in(2) instanceof PhiNode phi && phi.allCons() &&
-            // Do we have ((x + (phi cons)) + con) ?
-            // Do we have ((x + (phi cons)) + (phi cons)) ?
-            // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
-
-            // Note that this is the exact reverse of Phi pulling a common op
-            // down to reduce total op-count.  We don't get in an endless push-
-            // up push-down peephole cycle because the constants all fold first.
-            (t2.isConstant() || (rhs instanceof PhiNode && phi.in(0) == rhs.in(0) && rhs.allCons()) ) ) {
-            Node[] ns = new Node[phi.nIns()];
-            ns[0] = phi.in(0);
-            // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
-            for( int i=1; i<ns.length; i++ )
-                ns[i] = new AddNode(phi.in(i),t2.isConstant() ? rhs : rhs.in(i)).peephole();
-            String label = phi._label + (rhs instanceof PhiNode rphi ? rphi._label : "");
-            return new AddNode(lhs.in(1),new PhiNode(label,ns).peephole());
-        }
+
+        // Do we have ((x + (phi cons)) + con) ?
+        // Do we have ((x + (phi cons)) + (phi cons)) ?
+        // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
+        Node phicon = phiCon(this,true);
+        if( phicon!=null ) return phicon;
 
         // Now we sort along the spline via rotates, to gather similar things together.
 
@@ -100,6 +90,47 @@ public class AddNode extends Node {
         return null;
     }
 
+    // Rotation is only valid for associative ops, e.g. Add, Mul, And, Or.
+    // Do we have ((phi cons)|(x + (phi cons)) + con|(phi cons)) ?
+    // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
+    static Node phiCon(Node op, boolean rotate) {
+        Node lhs = op.in(1);
+        Node rhs = op.in(2);
+        // LHS is either a Phi of constants, or another op with Phi of constants
+        PhiNode lphi = pcon(lhs);
+        if( rotate && lphi==null && lhs.nIns() > 2 ) {
+            // Only valid to rotate constants if both are same associative ops
+            if( lhs.getClass() != op.getClass() ) return null;
+            lphi = pcon(lhs.in(2)); // Will rotate with the Phi push
+        }
+        if( lphi==null ) return null;
+
+        // RHS is a constant or a Phi of constants
+        if( !(rhs instanceof ConstantNode con) && pcon(rhs)==null )
+            return null;
+
+        // If both are Phis, must be same Region
+        if( rhs instanceof PhiNode && lphi.in(0) != rhs.in(0) )
+            return null;
+
+        // Note that this is the exact reverse of Phi pulling a common op down
+        // to reduce total op-count.  We don't get in an endless push-up
+        // push-down peephole cycle because the constants all fold first.
+        Node[] ns = new Node[lphi.nIns()];
+        ns[0] = lphi.in(0);
+        // Push constant up through the phi: x + (phi con0+con0 con1+con1...)
+        for( int i=1; i<ns.length; i++ )
+            ns[i] = op.copy(lphi.in(i), rhs instanceof PhiNode ? rhs.in(i) : rhs).peephole();
+        String label = lphi._label + (rhs instanceof PhiNode rphi ? rphi._label : "");
+        Node phi = new PhiNode(label,ns).peephole();
+        // Rotate needs another op, otherwise just the phi
+        return lhs==lphi ? phi : op.copy(lhs.in(1),phi);
+    }
+
+    static PhiNode pcon(Node op) {
+        return op instanceof PhiNode phi && phi.allCons() ? phi : null;
+    }
+
     // Compare two off-spline nodes and decide what order they should be in.
     // Do we rotate ((x + hi) + lo) into ((x + lo) + hi) ?
     // Generally constants always go right, then Phi-of-constants, then muls, then others.
diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
index 7a4a087e..a9ec6838 100644
--- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -43,6 +43,12 @@ abstract public class BoolNode extends Node {
         if( in(1)==in(2) )
             return new ConstantNode(TypeInteger.constant(doOp(3,3)?1:0));
 
+        // Do we have ((x * (phi cons)) * con) ?
+        // Do we have ((x * (phi cons)) * (phi cons)) ?
+        // Push constant up through the phi: x * (phi con0*con0 con1*con1...)
+        Node phicon = AddNode.phiCon(this,false);
+        if( phicon!=null ) return phicon;
+
         return null;
     }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java
index 6124b893..34846e99 100644
--- a/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -26,7 +26,25 @@ public class IfNode extends MultiNode {
 
     @Override
     public Type compute() {
-        return TypeTuple.IF;
+        // If the If node is not reachable then neither is any following Proj
+        if (ctrl()._type != Type.CONTROL) return TypeTuple.IF_NEITHER;
+        // If constant is 0 then false branch is reachable
+        // Else true branch is reachable
+        if (pred()._type instanceof TypeInteger ti && ti.isConstant()) {
+            if (ti.value() == 0)   return TypeTuple.IF_FALSE;
+            else                   return TypeTuple.IF_TRUE;
+        }
+
+        // Hunt up the immediate dominator tree.  If we find an identical if
+        // test on either the true or false branch, then this test matches.
+        for( Node dom = idom(), prior=this; dom!=null;  prior=dom, dom = dom.idom() )
+          if( dom instanceof IfNode iff && iff.pred()==pred() )
+            return prior instanceof ProjNode proj
+              // Repeated test, dominated on one side.  Test result is the same.
+              ? (proj._idx==0 ? TypeTuple.IF_TRUE : TypeTuple.IF_FALSE)
+              : null;           // Repeated test not dominated on one side
+
+        return TypeTuple.IF_BOTH;
     }
 
     @Override
diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java
index 2dbdd695..0380c079 100644
--- a/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -44,6 +44,12 @@ public class MulNode extends Node {
         if ( t1.isConstant() && !t2.isConstant() )
             return swap12();
 
+        // Do we have ((x * (phi cons)) * con) ?
+        // Do we have ((x * (phi cons)) * (phi cons)) ?
+        // Push constant up through the phi: x * (phi con0*con0 con1*con1...)
+        Node phicon = AddNode.phiCon(this,true);
+        if( phicon!=null ) return phicon;
+
         return null;
     }
     @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); }
diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java
index 5412108b..97ba68ab 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -46,9 +46,19 @@ public abstract class Node {
      */
     public Type _type;
 
+
+    /**
+     * Immediate dominator tree depth, used to approximate a real IDOM during
+     * parsing where we do not have the whole program, and also peepholes
+     * change the CFG incrementally.
+     * <p>
+     * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>}
+     */
+    int _idepth;
+
     /**
      * A private Global Static mutable counter, for unique node id generation.
-     * To make the compiler multi-threaded, this field will have to move into a TLS.
+     * To make the compiler multithreaded, this field will have to move into a TLS.
      * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values.
      * */
     private static int UNIQUE_ID = 1;
@@ -151,6 +161,17 @@ public abstract class Node {
         return new_def;
     }
 
+    // Remove the numbered input, compressing the inputs in-place.  This
+    // shuffles the order deterministically - which is suitable for Region and
+    // Phi, but not for every Node.
+    void delDef(int idx) {
+        Node old_def = in(idx);
+        if( old_def != null &&  // If the old def exists, remove a def->use edge
+            old_def.delUse(this) ) // If we removed the last use, the old def is now dead
+            old_def.kill();     // Kill old def
+        Utils.del(_inputs, idx);
+    }
+
     /**
      * Add a new def to an existing Node.  Keep the edges correct by
      * adding the corresponding <em>def->use</em> edge.
@@ -358,6 +379,14 @@ public abstract class Node {
         return true;
     }
 
+    // Return the immediate dominator of this Node and compute dom tree depth.
+    Node idom() {
+        Node idom = in(0);
+        if( idom._idepth==0 ) idom.idom(); // Recursively set _idepth
+        if( _idepth==0 ) _idepth = idom._idepth+1;
+        return idom;
+    }
+
     // Make a shallow copy (same class) of this Node, with given inputs and
     // empty outputs and a new Node ID.  The original inputs are ignored.
     // Does not need to be implemented in isCFG() nodes.
diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 374e1183..15088e08 100644
--- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -26,14 +26,18 @@ public class PhiNode extends Node {
 
     @Override
     public Type compute() {
-        return Type.BOTTOM;
+        Type t = Type.TOP;
+        for (int i = 1; i < nIns(); i++)
+            t = t.meet(in(i)._type);
+        return t;
     }
 
     @Override
     public Node idealize() {
-        // Remove a "junk" Phi: Phi(x,x) is just x
-        if( same_inputs() )
-            return in(1);
+        // If we have only a single unique input, become it.
+        Node live = singleUniqueInput();
+        if (live != null)
+            return live;
 
         // Pull "down" a common data op.  One less op in the world.  One more
         // Phi, but Phis do not make code.
@@ -63,11 +67,17 @@ public class PhiNode extends Node {
         return true;
     }
 
-    private boolean same_inputs() {
-        for( int i=2; i<nIns(); i++ )
-            if( in(1) != in(i) )
-                return false;
-        return true;
+    /**
+     * If only single unique input, return it
+     */
+    private Node singleUniqueInput() {
+        Node live = null;
+        for( int i=1; i<nIns(); i++ )
+            if( region().in(i)._type != Type.XCONTROL && in(i) != this )
+                if( live == null || live == in(i) ) live = in(i);
+                else return null;
+        return live;
     }
 
+
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index 2826d192..85f28037 100644
--- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -35,6 +35,8 @@ public class ProjNode extends Node {
 
     @Override
     public Node idealize() {
+        if( ctrl()._type instanceof TypeTuple tt && tt._types[1-_idx]==Type.XCONTROL ) // Only true for IfNodes
+            return ctrl().in(0); // We become our input control
         return null;
     }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index 5d520d65..bb7998a3 100644
--- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple.node;
 
+import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
 
 public class RegionNode extends Node {
@@ -17,11 +18,58 @@ public class RegionNode extends Node {
 
     @Override
     public Type compute() {
-        return Type.CONTROL;
+        Type t = Type.XCONTROL;
+        for (int i = 1; i < nIns(); i++)
+            t = t.meet(in(i)._type);
+        return t;
     }
 
     @Override
     public Node idealize() {
+        int path = findDeadInput();
+        if( path != 0 ) {
+            for( Node phi : _outputs )
+                if( phi instanceof PhiNode )
+                    phi.delDef(path);
+            delDef(path);
+
+            // If down to a single input, become that input - but also make all
+            // Phis an identity on *their* single input.
+            if( nIns()==2 ) {
+                for( Node phi : _outputs )
+                    if( phi instanceof PhiNode )
+                        // Currently does not happen, because no loops
+                        throw Utils.TODO();
+                return in(1);
+            }
+            return this;
+        }
         return null;
     }
+
+    private int findDeadInput() {
+        for( int i=1; i<nIns(); i++ )
+            if( in(i)._type==Type.XCONTROL )
+                return i;
+        return 0;               // All inputs alive
+    }
+
+    // Immediate dominator of Region is a little more complicated.
+    private Node _idom;         // Immediate dominator cache
+    @Override Node idom() {
+        if( _idom != null ) return _idom; // Return cached copy
+        if( nIns()!=3 ) return null;      // Fails for anything other than 2-inputs
+        // Walk the LHS & RHS idom trees in parallel until they match, or either fails
+        Node lhs = in(1).idom();
+        Node rhs = in(2).idom();
+        while( lhs != rhs ) {
+          if( lhs==null || rhs==null ) return null;
+          var comp = lhs._idepth - rhs._idepth;
+          if( comp >= 0 ) lhs = lhs.idom();
+          if( comp <= 0 ) rhs = rhs.idom();
+        }
+        if( lhs==null ) return null;
+        _idepth = lhs._idepth+1;
+        return (_idom=lhs);
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index c9d6c9c8..6130d050 100644
--- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -36,5 +36,9 @@ public class ReturnNode extends Node {
     }
 
     @Override
-    public Node idealize() { return null; }
+    public Node idealize() {
+        if( ctrl()._type==Type.XCONTROL )
+            return ctrl();
+        return null;
+    }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 32045fbc..a7a04a42 100644
--- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -162,14 +162,14 @@ public class ScopeNode extends Node {
      * @return A new node representing the merge point
      */
     public Node mergeScopes(ScopeNode that) {
-        RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).peephole());
+        RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep());
         String[] ns = reverseNames();
         // Note that we skip i==0, which is bound to '$ctrl'
         for (int i = 1; i < nIns(); i++)
             if( in(i) != that.in(i) ) // No need for redundant Phis
                 setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole());
         that.kill();            // Kill merged scope
-        return r;
+        return r.unkeep().peephole();
     }
 
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 022e276d..c5a45876 100644
--- a/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -35,4 +35,9 @@ public class StartNode extends MultiNode {
 
     @Override
     public Node idealize() { return null; }
+
+    // No immediate dominator, and idepth==0
+    @Override
+    Node idom() { return null; }
+
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java
index a30256f9..01574dc7 100644
--- a/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -36,6 +36,11 @@ public class StopNode extends Node {
 
     @Override
     public Node idealize() {
+        int len = nIns();
+        for( int i=0; i<nIns(); i++ )
+            if( in(i)._type==Type.XCONTROL )
+                delDef(i--);
+        if( len != nIns() ) return this;
         return null;
     }