Chapter6 Part 2 - Add further peephole based on dominator calc (#42)

* #37 Add a Utils class to hold some useful functions. (#39)

Move the name '$ctrl' to the ScopeNode

* Fix maven pom

Missing an explicit compiler target, so IntelliJ/Maven defaulted to version 5 ???
Remove explict ver 17 from Makefile.

* Add immediate dominator peephole

* A little more robust & simpler idom search

* #40 Revise chapter 6 writeup to include a description of dominators

* #40 Revise chapter 6 writeup to include a description of dominators

---------

Co-authored-by: Cliff Click <cliffc@acm.org>

9 files changed, 96 insertions, 23 deletions

diff --git a/chapter06/src/main/java/com/seaofnodes/simple/Parser.java b/chapter06/src/main/java/com/seaofnodes/simple/Parser.java
index b08c3c56..1bfe5b0d 100644
--- a/chapter06/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter06/src/main/java/com/seaofnodes/simple/Parser.java
@@ -14,11 +14,6 @@ import java.util.*;
  */
 public class Parser {
 
-    /**
-     * The control is a name that binds to the currently active control
-     * node in the graph
-     */
-    public static final String CTRL = "$ctrl";
   
     /**
      * A Global Static, unique to each compilation.  This is a public, so we
@@ -80,6 +75,9 @@ public class Parser {
         this(source, TypeInteger.BOT);
     }
 
+    @Override
+    public String toString() { return _lexer.toString(); }
+  
     String src() { return new String( _lexer._input ); }
 
     private Node ctrl() { return _scope.ctrl(); }
@@ -91,7 +89,7 @@ public class Parser {
         _allScopes.push(_scope);
         _scope.push();
         try {
-            _scope.define(CTRL , new ProjNode(START, 0, CTRL ).peephole());
+            _scope.ctrl(new ProjNode(START, 0, ScopeNode.CTRL).peephole());
             _scope.define("arg", new ProjNode(START, 1, "arg").peephole());
             parseBlock();
             if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken());
@@ -522,7 +520,4 @@ public class Parser {
             return new String(_input, start, 1);
         }
     }
-
-    public static RuntimeException TODO() { return TODO("Not yet implemented"); }
-    public static RuntimeException TODO(String msg) { return new RuntimeException(msg); }
 }
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/Utils.java b/chapter06/src/main/java/com/seaofnodes/simple/Utils.java
new file mode 100644
index 00000000..c79d96f0
--- /dev/null
+++ b/chapter06/src/main/java/com/seaofnodes/simple/Utils.java
@@ -0,0 +1,6 @@
+package com.seaofnodes.simple;
+
+public class Utils {
+    public static RuntimeException TODO() { return TODO("Not yet implemented"); }
+    public static RuntimeException TODO(String msg) { return new RuntimeException(msg); }
+}
\ No newline at end of file
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 61359d64..b29fb92c 100644
--- a/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -1,6 +1,5 @@
 package com.seaofnodes.simple.node;
 
-import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.type.*;
 
 public class AddNode extends Node {
@@ -64,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)
         
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java
index 9e88710c..1b0fdac7 100644
--- a/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -31,9 +31,19 @@ public class IfNode extends MultiNode {
         // 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;
+            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;
     }
 
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java
index fe3fddf8..81c90f68 100644
--- a/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java
@@ -1,7 +1,5 @@
 package com.seaofnodes.simple.node;
 
-import com.seaofnodes.simple.type.Type;
-
 public abstract class MultiNode extends Node {
     
     public MultiNode(Node... inputs) { super(inputs); }
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java
index fd1b870c..36e4896d 100644
--- a/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -1,6 +1,6 @@
 package com.seaofnodes.simple.node;
 
-import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
 
 import java.util.*;
@@ -46,6 +46,16 @@ 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 https://en.wikipedia.org/wiki/Dominator_(graph_theory)}
+     */
+    int _idepth;
+    
     /**
      * A private Global Static mutable counter, for unique node id generation.
      * To make the compiler multithreaded, this field will have to move into a TLS.
@@ -367,10 +377,18 @@ 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.
-    Node copy(Node lhs, Node rhs) { throw Parser.TODO("Binary ops need to implement copy"); }
+    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
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index 1ddf520b..d3fd7745 100644
--- a/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -1,6 +1,6 @@
 package com.seaofnodes.simple.node;
 
-import com.seaofnodes.simple.Parser;
+import com.seaofnodes.simple.Utils;
 import com.seaofnodes.simple.type.Type;
 
 public class RegionNode extends Node {
@@ -39,7 +39,7 @@ public class RegionNode extends Node {
                 for( Node phi : _outputs )
                     if( phi instanceof PhiNode )
                         // Currently does not happen, because no loops
-                        throw Parser.TODO();
+                        throw Utils.TODO();
                 return in(1);
             }
             return this;
@@ -53,4 +53,23 @@ public class RegionNode extends Node {
                 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/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index eecab9f9..96564f3b 100644
--- a/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -1,6 +1,5 @@
 package com.seaofnodes.simple.node;
 
-import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.type.Type;
 
 import java.util.*;
@@ -12,6 +11,12 @@ import java.util.*;
 public class ScopeNode extends Node {
 
     /**
+     * The control is a name that binds to the currently active control
+     * node in the graph
+     */
+    public static final String CTRL = "$ctrl";
+
+    /**
      * Stack of lexical scopes, each scope is a symbol table
      * that binds variable names to Nodes.
      * The top of this stack represents current scope.
@@ -76,10 +81,26 @@ public class ScopeNode extends Node {
         return null;
     }
 
-    public Node ctrl() { assert lookup(Parser.CTRL)==in(0); return in(0); }
-    
+    public Node ctrl() { assert lookup(CTRL)==in(0); return in(0); }
+
+    /**
+     * The ctrl of a ScopeNode is always bound to the currently active
+     * control node in the graph, via a special name '$ctrl' that is not
+     * a valid identifier in the language grammar and hence cannot be
+     * referenced in Simple code.
+     *
+     * @param n The node to be bound to '$ctrl'
+     *
+     * @return Node that was bound
+     */
     public Node ctrl(Node n) {
-        assert lookup(Parser.CTRL)==in(0);
+        if (nIns() == 0) {
+            // The first time a scope is created we do not have the name binding
+            // for '$ctrl' but after that we expect to find the name already bound
+            assert lookup(CTRL) == null;
+            define(CTRL, n);
+        }
+        else assert lookup(CTRL) == in(0);
         set_def(0,n);
         return n;
     }
@@ -128,6 +149,7 @@ public class ScopeNode extends Node {
      */
     public Node mergeScopes(ScopeNode that) {
         RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep());
+        // 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
                 set_def(i, new PhiNode(_rlabels.get(i), r, in(i), that.in(i)).peephole());
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 85c6cd34..8cff25bd 100644
--- a/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -34,4 +34,9 @@ public class StartNode extends MultiNode {
 
     @Override
     public Node idealize() { return null; }
+
+    // No immediate dominator, and idepth==0
+    @Override
+    Node idom() { return null; }
+
 }