From b59828ac09a88310640d8b8d3d95a8be0cee1187 Mon Sep 17 00:00:00 2001
From: Cliff Click <cliffc@acm.org>
Date: Sun, 29 Oct 2023 13:09:14 -0700
Subject: Rethink & cleanup Add peeps

More rigorously head for a left-spline sum-of-products format.
---
 .../java/com/seaofnodes/simple/node/AddNode.java   | 100 +++++++++++++++------
 .../main/java/com/seaofnodes/simple/node/Node.java |  29 +++++-
 .../java/com/seaofnodes/simple/node/PhiNode.java   |  32 ++++++-
 3 files changed, 133 insertions(+), 28 deletions(-)

(limited to 'chapter05/src/main')

diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java
index a726a22d..7cb0f822 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -36,42 +36,92 @@ public class AddNode extends Node {
         Type t1 = lhs._type;
         Type t2 = rhs._type;
 
+        // Already handled by peephole constant folding
+        assert !(t1.isConstant() && t2.isConstant());
+
         // Add of 0.  We do not check for (0+x) because this will already
         // canonicalize to (x+0)
-        if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 )
+        if( t2 instanceof TypeInteger i && i.value()==0 )
             return lhs;
-        
-        // Move constants to RHS: con+arg becomes arg+con
-        if ( t1.isConstant() && !t2.isConstant() ) {
-            Node tmp = in(1);   // Swap inputs without letting either input go dead during the swap
-            _inputs.set(1,in(2));
-            _inputs.set(2,tmp);
-            return this;
-        }
-        
+              
+        // Add of same to a multiply by 2
+        if( lhs==rhs )
+            return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole());
+
         // Goal: a left-spine set of adds, with constants on the rhs (which then fold).
         
-        // Do we have (x + con1) + con2 ?
-        // Rotate to   x +(con1  + con2)
-        // The constants will fold on the next peephole.
-        if (t2.isConstant() && lhs instanceof AddNode && lhs.in(2)._type.isConstant() )
+        // Move non-adds to RHS
+        if( !(lhs instanceof AddNode) && rhs instanceof AddNode )
+            return swap12();
+
+        // Now we might see (add add non) or (add non non) or (add add add) but never (add non add)
+
+        // Do we have  x + (y + z) ?
+        // Swap to    (x + y) + z
+        // Rotate (add add add) to remove the add on RHS
+        if( rhs instanceof AddNode add )
+            return new AddNode(new AddNode(lhs,add.in(1)).peephole(), add.in(2));
+
+        // 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;
+
+        // Now we only see (add add non)
+        
+        // Do we have (x + con1) + con2?
+        // Replace with (x + (con1+con2) which then fold the constants
+        if( lhs.in(2)._type.isConstant() && t2.isConstant() )
             return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole());
 
-        // Do we have  x + (y + non_add) ?
-        // Swap to    (x + y) + non_add
-        if (rhs instanceof AddNode add && !(add.in(2) instanceof AddNode) )
-          return new AddNode(new AddNode(lhs,add.in(1)).peephole(), add.in(2));
+        if( lhs.in(2) instanceof PhiNode phi && phi.all_cons() &&
+            // 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 a endless push-
+            // up push-down peephole cycle because the constants all fold first.
+            (t2.isConstant() || (rhs instanceof PhiNode && rhs.all_cons()) ) ) {
+            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();
+            return new AddNode(lhs.in(1),new PhiNode(ns).peephole());
+        }
 
-        // Do we have (x + y) + x
-        // Swap to    (x + x) + y
-        if (lhs instanceof AddNode add && add.in(1)==rhs )
-          return new AddNode(new AddNode(rhs,rhs).peephole(), add.in(2));
+        // Now we sort along the spline via rotates, to gather similar things together.
         
-        // Add of same to a multiply by 2
-        if( lhs==rhs )
-            return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole());
+        // Do we rotate (x + y) + z
+        // into         (x + z) + y ?
+        if( spline_cmp(lhs.in(2),rhs) )
+            return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2));
         
         return 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.
+    // Ties with in a category sort by node ID.
+    // TRUE if swapping hi and lo.
+    static boolean spline_cmp( Node hi, Node lo ) {
+        if( lo._type.isConstant() ) return false;
+        if( hi._type.isConstant() ) return true ;
+            
+        if( lo instanceof PhiNode && lo.all_cons() ) return false;
+        if( hi instanceof PhiNode && hi.all_cons() ) return true ;
+
+        if( lo instanceof MulNode ) throw new RuntimeException("TODO");        
+        if( hi instanceof MulNode ) throw new RuntimeException("TODO");
+
+        if( lo instanceof PhiNode && !(hi instanceof PhiNode) ) return true;
+        if( hi instanceof PhiNode && !(lo instanceof PhiNode) ) return false;
         
+        // Same category of "others"
+        return lo._nid > hi._nid;
+    }
+    
+    @Override
+    Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); }
 }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
index 49426c26..dc4d7a33 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -215,7 +215,6 @@ public abstract class Node {
         return new_def;
     }
 
-    
     // Breaks the edge invariants, used temporarily
     private void addUse(Node n) { _outputs.add(n); }
 
@@ -258,7 +257,7 @@ public abstract class Node {
 
     // Mostly used for asserts and printing.
     boolean isDead() { return isUnused() && nIns()==0 && _type==null; }
-    
+  
     /**
      * This function needs to be
      * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a>
@@ -324,6 +323,32 @@ public abstract class Node {
      */
     public abstract Node idealize();
 
+
+    // -----------------------
+    // Peephole utilities
+    
+    // Swap inputs without letting either input go dead during the swap.
+    Node swap12() {
+        Node tmp = in(1);
+        _inputs.set(1,in(2));
+        _inputs.set(2,tmp);
+        return this;
+    }
+    
+    // does this node contain all constants?
+    // Ignores in(0), as is usually control.
+    boolean all_cons() {
+        for( int i=1; i<nIns(); i++ )
+            if( !(in(i)._type.isConstant()) )
+                return false;
+        return true;
+    }
+
+    // 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.
+    Node copy(Node lhs, Node rhs) { throw new RuntimeException("TODO"); }
+
     /**
      * Used to allow repeating tests in the same JVM.  This just resets the
      * Node unique id generator, and is done as part of making a new Parser.
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index 6fef99f3..4334ac10 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -34,7 +34,37 @@ public class PhiNode extends Node {
         // Remove a "junk" Phi: Phi(x,x) is just x
         if( in(1)==in(2) )
             return in(1);
-        
+
+        // Pull "down" a common data op.  One less op in the world.  One more
+        // Phi, but Phis do not make code.        
+        //   Phi(op(A,B),op(Q,R),op(X,Y)) becomes
+        //     op(Phi(A,Q,X), Phi(B,R,Y)).
+        Node op = in(1);
+        if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) {
+            Node[] lhss = new Node[nIns()];
+            Node[] rhss = new Node[nIns()];
+            lhss[0] = rhss[0] = in(0); // Set Region
+            for( int i=1; i<nIns(); i++ ) {
+                lhss[i] = in(i).in(1);
+                rhss[i] = in(i).in(2);
+            }
+            Node phi_lhs = new PhiNode(lhss).peephole();
+            Node phi_rhs = new PhiNode(rhss).peephole();
+            //if( phi_lhs instanceof PhiNode && phi_rhs instanceof PhiNode ) {
+            //    phi_lhs.kill();
+            //    phi_rhs.kill();
+            //    return null;    // No progress, no profit
+            //}
+            return op.copy(phi_lhs,phi_rhs);
+        }
+
         return null;
     }
+
+    private boolean same_op() {
+        for( int i=2; i<nIns(); i++ )
+            if( in(1).getClass() != in(i).getClass() )
+                return false;
+        return true;
+    }
 }
-- 
cgit v1.2.3