From 369268fe6f3bd1dcd59117c8f831f04f4e3b0560 Mon Sep 17 00:00:00 2001
From: Dibyendu Majumdar <mobile@majumdar.org.uk>
Date: Fri, 27 Oct 2023 20:35:04 +0100
Subject: Chapter 5: If Statement, Phi, and Region

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Yichen Yan <oraluben@outlook.com>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Tamas Hadhazy <helsgithub15@gmail.com>
Co-authored-by: David Rubin <87927264+Rexicon226@users.noreply.github.com>
---
 .../java/com/seaofnodes/simple/node/AddNode.java   | 27 +++++++-
 .../java/com/seaofnodes/simple/node/BoolNode.java  |  6 +-
 .../java/com/seaofnodes/simple/node/DivNode.java   |  2 +
 .../java/com/seaofnodes/simple/node/IfNode.java    | 36 +++++++++++
 .../java/com/seaofnodes/simple/node/MulNode.java   |  1 +
 src/main/java/com/seaofnodes/simple/node/Node.java | 14 +++++
 .../java/com/seaofnodes/simple/node/PhiNode.java   | 73 ++++++++++++++++++++++
 .../java/com/seaofnodes/simple/node/ProjNode.java  |  2 +-
 .../com/seaofnodes/simple/node/RegionNode.java     | 27 ++++++++
 .../java/com/seaofnodes/simple/node/ScopeNode.java | 41 ++++++++++++
 .../java/com/seaofnodes/simple/node/StopNode.java  | 46 ++++++++++++++
 .../java/com/seaofnodes/simple/node/SubNode.java   |  1 +
 12 files changed, 271 insertions(+), 5 deletions(-)
 create mode 100644 src/main/java/com/seaofnodes/simple/node/IfNode.java
 create mode 100644 src/main/java/com/seaofnodes/simple/node/PhiNode.java
 create mode 100644 src/main/java/com/seaofnodes/simple/node/RegionNode.java
 create mode 100644 src/main/java/com/seaofnodes/simple/node/StopNode.java

(limited to 'src/main/java/com/seaofnodes/simple/node')

diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 5720aca4..081c9276 100644
--- a/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -72,6 +72,24 @@ 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());
+        }
+
         // Now we sort along the spline via rotates, to gather similar things together.
 
         // Do we rotate (x + y) + z
@@ -84,15 +102,22 @@ public class AddNode extends Node {
 
     // 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 others.
+    // 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.allCons() ) return false;
+        if( hi instanceof PhiNode && hi.allCons() ) return true ;
+
+        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/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
index 05495790..7a4a087e 100644
--- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -46,7 +46,7 @@ abstract public class BoolNode extends Node {
         return null;
     }
 
-    public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } }
-    public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs <  rhs; } }
-    public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } }
+    public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); } }
+    public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs <  rhs; } Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); } }
+    public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); } }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java
index 3b3a4436..519a8c8a 100644
--- a/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -37,4 +37,6 @@ public class DivNode extends Node {
             return in(1);
         return null;
     }
+
+    @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); }
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java
new file mode 100644
index 00000000..6124b893
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -0,0 +1,36 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+import com.seaofnodes.simple.type.TypeInteger;
+import com.seaofnodes.simple.type.TypeTuple;
+
+public class IfNode extends MultiNode {
+
+    public IfNode(Node ctrl, Node pred) {
+        super(ctrl, pred);
+    }
+
+    @Override
+    public String label() { return "If"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        sb.append("if( ");
+        return in(1)._print0(sb).append(" )");
+    }
+
+    @Override public boolean isCFG() { return true; }
+
+    public Node ctrl() { return in(0); }
+    public Node pred() { return in(1); }
+
+    @Override
+    public Type compute() {
+        return TypeTuple.IF;
+    }
+
+    @Override
+    public Node idealize() {
+        return null;
+    }
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java
index 36d5eb3e..2dbdd695 100644
--- a/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -46,4 +46,5 @@ public class MulNode extends Node {
 
         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 9fa0a95a..5412108b 100644
--- a/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -349,6 +349,20 @@ public abstract class Node {
         return this;
     }
 
+    // does this node contain all constants?
+    // Ignores in(0), as is usually control.
+    boolean allCons() {
+        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 Utils.TODO("Binary ops need to implement copy"); }
+
     /**
      * 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/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
new file mode 100644
index 00000000..374e1183
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -0,0 +1,73 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+
+public class PhiNode extends Node {
+
+    final String _label;
+
+    public PhiNode(String label, Node... inputs) { super(inputs); _label = label; }
+
+    @Override public String label() { return "Phi_"+_label; }
+
+    @Override public String glabel() { return "&phi;_"+_label; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        sb.append("Phi(");
+        for( Node in : _inputs )
+            in._print0(sb).append(",");
+        sb.setLength(sb.length()-1);
+        sb.append(")");
+        return sb;
+    }
+
+    Node region() { return in(0); }
+
+    @Override
+    public Type compute() {
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() {
+        // Remove a "junk" Phi: Phi(x,x) is just x
+        if( same_inputs() )
+            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(_label,lhss).peephole();
+            Node phi_rhs = new PhiNode(_label,rhss).peephole();
+            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;
+    }
+
+    private boolean same_inputs() {
+        for( int i=2; i<nIns(); i++ )
+            if( in(1) != in(i) )
+                return false;
+        return true;
+    }
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index 2f49fe91..2826d192 100644
--- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -23,7 +23,7 @@ public class ProjNode extends Node {
     @Override
     StringBuilder _print1(StringBuilder sb) { return sb.append(_label); }
 
-    @Override public boolean isCFG() { return _idx==0; }
+    @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; }
 
     public MultiNode ctrl() { return (MultiNode)in(0); }
 
diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
new file mode 100644
index 00000000..5d520d65
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -0,0 +1,27 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+
+public class RegionNode extends Node {
+    public RegionNode(Node... inputs) { super(inputs); }
+
+    @Override
+    public String label() { return "Region"; }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        return sb.append(label()).append(_nid);
+    }
+
+    @Override public boolean isCFG() { return true; }
+
+    @Override
+    public Type compute() {
+        return Type.CONTROL;
+    }
+
+    @Override
+    public Node idealize() {
+        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 8ffeac64..32045fbc 100644
--- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -131,4 +131,45 @@ public class ScopeNode extends Node {
      */
     public Node ctrl(Node n) { return setDef(0,n); }
 
+    /**
+     * Duplicate a ScopeNode; including all levels, up to Nodes.  So this is
+     * neither shallow (would dup the Scope but not the internal HashMap
+     * tables), nor deep (would dup the Scope, the HashMap tables, but then
+     * also the program Nodes).
+     * <p>
+     * The new Scope is a full-fledged Node with proper use<->def edges.
+     */
+    public ScopeNode dup() {
+        ScopeNode dup = new ScopeNode();
+        // Our goals are:
+        // 1) duplicate the name bindings of the ScopeNode across all stack levels
+        // 2) Make the new ScopeNode a user of all the nodes bound
+        // 3) Ensure that the order of defs is the same to allow easy merging
+        for( HashMap<String,Integer> syms : _scopes )
+            dup._scopes.push(new HashMap<>(syms));
+        dup.addDef(ctrl());      // Control input is just copied
+        for( int i=1; i<nIns(); i++ )
+            dup.addDef(in(i));
+        return dup;
+    }
+
+    /**
+     * Merges the names whose node bindings differ, by creating Phi node for such names
+     * The names could occur at all stack levels, but a given name can only differ in the
+     * innermost stack level where the name is bound.
+     *
+     * @param that The ScopeNode to be merged into this
+     * @return A new node representing the merge point
+     */
+    public Node mergeScopes(ScopeNode that) {
+        RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).peephole());
+        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;
+    }
+
 }
diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java
new file mode 100644
index 00000000..a30256f9
--- /dev/null
+++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -0,0 +1,46 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.Type;
+
+public class StopNode extends Node {
+    public StopNode(Node... inputs) {
+        super(inputs);
+    }
+
+    @Override
+    public String label() {
+        return "Stop";
+    }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb) {
+        if( ret()!=null ) return ret()._print0(sb);
+        sb.append("Stop[ ");
+        for( Node ret : _inputs )
+            ret._print0(sb).append(" ");
+        return sb.append("]");
+    }
+
+    @Override public boolean isCFG() { return true; }
+
+    // If a single Return, return it.
+    // Otherwise, null because ambiguous.
+    public ReturnNode ret() {
+        return nIns()==1 ? (ReturnNode)in(0) : null;
+    }
+
+    @Override
+    public Type compute() {
+        return Type.BOTTOM;
+    }
+
+    @Override
+    public Node idealize() {
+        return null;
+    }
+
+    public Node addReturn(Node node) {
+        return addDef(node);
+    }
+
+}
diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java
index 58d757ea..475b3790 100644
--- a/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -37,4 +37,5 @@ public class SubNode extends Node {
         return null;
     }
 
+    @Override Node copy(Node lhs, Node rhs) { return new SubNode(lhs,rhs); }
 }
-- 
cgit v1.2.3