Chapter 6 (#38)

* #37 Create chapter 6 skeleton

* #37 Revise type system - TOP, BOTTOM, CONTROL are now directly implemented in Type, XCONTROL is a new type and that's implemented directly too.
We have a _type field that is like an enum.

* #37 Revise Type.meet() - this is now final.
Subclasses can override xmeet() which is protected but
now handles simple types in Type itself.

* #37 Basic test for peephole of CFG

* #37 Revise compute of if

* #37 Revise compute of if

* #37 WIP peephole of If

* #37 WIP peephole of If

* #37 WIP peephole of If

* #37 WIP peephole of If

* #37 WIP peephole of If

* #37 WIP fix the chars inserted by IntelliJ

* #37 WIP Fix compute type in IfNode

* #37 WIP Null check region inputs

* #37 WIP Fix where we choose great grand parent instead of grand parent
Add new test

* #37 WIP More fixes and tests

* #37 WIP Some minor adjustments

* Cleanup folding dead IF tests

Remove isDeadCtrl & just test for the constant.
Remove DEAD_CTRL, doesn't properly reset between tests.
Move keep/unkeep to Node.
PhiNode has a proper compute() call.
ProjNode ideal is a lot simpler.
Region doesn't ever get a null.
Move the mergeScopes Region peep till after all Phis are added.
Type TOP and XCONTROL count as constants.
TypeTuple gets a toString

* #37 WIP Upate README

* #37 WIP Region node should check if one of its inputs is a region that needs to be peepholed

* #37 WIP If node should check if its ctrl input is a Region that has only 1 live input so can be peepholed

* #37 WIP Further update to README to make the peephole logic clearer. Also discuss the relationship between Region and Phi nodes

* Region removes dead input paths

Remove region-folding in Return, If.
Add a Makefile.
Reformat triple-quote lines to be emacs-friendly.

* StopNode idealize

Return type sharpens to include control input.

* Remove !=, >=, >; use Not and <, <=, ==

Fix bug mixing rotating different ops.
Generalize Add fold constants; apply to Mul, EQ.
Fix Div.copy

* Fix bug rotating e.g. < or <=

Peep is only valid for associative ops

* #37 WIP Doc updates

* Work over the Ch6 Readme

Major issue: Region inputs align 1-to-1 with Phi inputs, but a Region can have zero to many Phis.  When we lose a Region input (dead path), we need to lose the same inputs to each Phi - but we don't lose the Phis themselves, unless we're folding away down to the last live input.

* Update chapter06/README.md

Co-authored-by: Yichen Yan <oraluben@outlook.com>

* Update chapter06/README.md

Co-authored-by: Yichen Yan <oraluben@outlook.com>

* #37 Backport type system changes to chapter 2

* #37 Backport type system changes to chapter 3

* #37 Backport type system changes to chapter 4

* #37 Backport type system changes to chapter 5

* #37 Merge chapter 5 updates from main.
Remove language grammar module as we describe the grammar incrementally in each chapter.

* #37 Chapter 6 doc updates - added visuals to show effects of CFG peephole

* #37 Sync some updates to chapter 2

* #37 Sync some updates to chapter 3

* #37 Sync some updates to chapter 4

---------

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Yichen Yan <oraluben@outlook.com>

21 files changed, 58 insertions, 69 deletions

diff --git a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
index a132fce0..0461dc69 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/Parser.java
@@ -182,6 +182,7 @@ public class Parser {
         // Merge results
         _scope = tScope;
         _allScopes.pop();       // Discard pushed from graph display
+
         return ctrl(tScope.mergeScopes(fScope));
     }
 
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 f2b93b2e..f6c49abf 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -25,7 +25,7 @@ public class AddNode extends Node {
                 return TypeInteger.constant(i0.value()+i1.value());
             return i0.meet(i1);
         }
-        return TypeBot.BOTTOM;
+        return Type.BOTTOM;
     }
 
     @Override
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java
index c1471c58..0ba5e7b0 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/BoolNode.java
@@ -1,7 +1,6 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeBot;
 import com.seaofnodes.simple.type.TypeInteger;
 
 abstract public class BoolNode extends Node {
@@ -33,7 +32,7 @@ abstract public class BoolNode extends Node {
                 return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0);
             return i0.meet(i1);
         }
-        return TypeBot.BOTTOM;
+        return Type.BOTTOM;
     }
 
     abstract boolean doOp(long lhs, long rhs);
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java
index 489e7275..01314c74 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/DivNode.java
@@ -1,7 +1,6 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeBot;
 import com.seaofnodes.simple.type.TypeInteger;
 
 public class DivNode extends Node {
@@ -28,11 +27,11 @@ public class DivNode extends Node {
                     : TypeInteger.constant(i0.value()/i1.value());
             return i0.meet(i1);
         }
-        return TypeBot.BOTTOM;
+        return Type.BOTTOM;
     }
 
     @Override
     public Node idealize() { return null; }
   
-    @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); }
+    @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); }
 }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java
index feb4f245..b46d37db 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -1,6 +1,7 @@
 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 {
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java
index 533155d9..08924563 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MinusNode.java
@@ -1,7 +1,6 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeBot;
 import com.seaofnodes.simple.type.TypeInteger;
 
 public class MinusNode extends Node {
@@ -21,7 +20,7 @@ public class MinusNode extends Node {
     public Type compute() {
         if (in(1)._type instanceof TypeInteger i0)
             return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0;
-        return TypeBot.BOTTOM;
+        return Type.BOTTOM;
     }
 
     @Override
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java
index 9962c445..0f21f67a 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/MulNode.java
@@ -1,7 +1,6 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeBot;
 import com.seaofnodes.simple.type.TypeInteger;
 
 public class MulNode extends Node {
@@ -26,7 +25,7 @@ public class MulNode extends Node {
                 return TypeInteger.constant(i0.value()*i1.value());
             return i0.meet(i1);
         }
-        return TypeBot.BOTTOM;
+        return Type.BOTTOM;
     }
 
     @Override
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 2d8a14d4..65151acb 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -227,7 +227,7 @@ public abstract class Node {
     // Remove node 'use' from 'def's (i.e. our) output list, by compressing the list in-place.
     // Return true if the output list is empty afterward.
     // Error is 'use' does not exist; ok for 'use' to be null.
-    private boolean delUse( Node use ) {
+    protected boolean delUse( Node use ) {
         ArrayList<Node> outs = _outputs;
         int lidx = outs.size()-1; // Last index            
         // This 1-line hack compresses an element out of an ArrayList
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 656e6182..87c84453 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -1,7 +1,6 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeBot;
 
 public class PhiNode extends Node {
 
@@ -25,7 +24,7 @@ public class PhiNode extends Node {
 
     @Override
     public Type compute() {
-        return TypeBot.BOTTOM;
+        return Type.BOTTOM;
     }
 
     @Override
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java
index 8e223e93..86e3b144 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ProjNode.java
@@ -1,7 +1,6 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeBot;
 import com.seaofnodes.simple.type.TypeTuple;
 
 public class ProjNode extends Node {
@@ -31,7 +30,11 @@ public class ProjNode extends Node {
     @Override
     public Type compute() {
         Type t = ctrl()._type;
-        return t instanceof TypeTuple tt ? tt._types[_idx] : TypeBot.BOTTOM;
+        return getType(t);
+    }
+
+    private Type getType(Type t) {
+        return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM;
     }
 
     @Override
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java
index ae8724b9..354a8f8b 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/RegionNode.java
@@ -1,7 +1,6 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeControl;
 
 public class RegionNode extends Node {
     public RegionNode(Node... inputs) { super(inputs); }
@@ -18,7 +17,7 @@ public class RegionNode extends Node {
 
     @Override
     public Type compute() {
-        return TypeControl.CONTROL;
+        return Type.CONTROL;
     }
 
     @Override
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index e20d01e5..73594d2a 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -32,7 +32,7 @@ public class ReturnNode extends Node {
   
     @Override
     public Type compute() {
-      return new TypeTuple(TypeControl.CONTROL,expr()._type);
+      return new TypeTuple(Type.CONTROL,expr()._type);
     }
 
     @Override
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 61fac118..93ef54f6 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -1,7 +1,7 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.Parser;
-import com.seaofnodes.simple.type.TypeBot;
+import com.seaofnodes.simple.type.Type;
 
 import java.util.*;
 
@@ -43,7 +43,7 @@ public class ScopeNode extends Node {
     }
   
     @Override
-    public TypeBot compute() { return TypeBot.BOTTOM; }
+    public Type compute() { return Type.BOTTOM; }
 
     @Override public Node idealize() { return null; }
 
@@ -124,9 +124,9 @@ public class ScopeNode extends Node {
      * innermost stack level where the name is bound.
      *
      * @param that The ScopeNode to be merged into this
-     * @return A new Region node representing the merge point
+     * @return A new node representing the merge point
      */
-    public RegionNode mergeScopes(ScopeNode that) {
+    public Node mergeScopes(ScopeNode that) {
         RegionNode r = (RegionNode)ctrl(new RegionNode(null,ctrl(), that.ctrl()).peephole());
         for( int i=1; i<nIns(); i++ )
             if( in(i) != that.in(i) ) // No need for redundant Phis
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 91573de8..85c6cd34 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -1,7 +1,6 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeBot;
 import com.seaofnodes.simple.type.TypeTuple;
 
 /**
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java
index d089dbe5..9898de88 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/StopNode.java
@@ -1,7 +1,6 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeBot;
 
 public class StopNode extends Node {
     public StopNode(Node... inputs) {
@@ -32,7 +31,7 @@ public class StopNode extends Node {
     
     @Override
     public Type compute() {
-        return TypeBot.BOTTOM;
+        return Type.BOTTOM;
     }
 
     @Override
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java
index 6bfb42be..41d7d092 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/node/SubNode.java
@@ -1,7 +1,6 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.Type;
-import com.seaofnodes.simple.type.TypeBot;
 import com.seaofnodes.simple.type.TypeInteger;
 
 public class SubNode extends Node {
@@ -26,7 +25,7 @@ public class SubNode extends Node {
                 return TypeInteger.constant(i0.value()-i1.value());
             return i0.meet(i1);
         }
-        return TypeBot.BOTTOM;
+        return Type.BOTTOM;
     }
 
     @Override
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java
index d9567dc8..d8cb690b 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -17,14 +17,32 @@ package com.seaofnodes.simple.type;
  * simple constant folding e.g. 1+2 == 3 stuff.
  */    
 
-public abstract class Type {
+public class Type {
 
-    public static final TypeControl CONTROL = new TypeControl();
+    // ----------------------------------------------------------
+    // Simple types are implemented fully here.  "Simple" means: the code and
+    // type hierarchy are simple, not that the Type is conceptually simple.
+    static final byte TBOT    = 0; // Bottom (ALL)
+    static final byte TTOP    = 1; // Top    (ANY)
+    static final byte TCTRL   = 2; // Ctrl flow bottom
+    static final byte TSIMPLE = 3; // End of the Simple Types
+    static final byte TINT    = 4; // All Integers; see TypeInteger
+    static final byte TTUPLE  = 5; // Tuples; finite collections of unrelated Types, kept in parallel
 
-    public boolean isConstant() { return false; }
+    public final byte _type;
 
-    public abstract StringBuilder _print(StringBuilder sb);
+    public boolean is_simple() { return _type < TSIMPLE; }
+    private static final String[] STRS = new String[]{"BOTTOM","TOP","CONTROL"};
+    protected Type(byte type) { _type = type; }
 
-    public Type meet(Type other) { return TypeBot.BOTTOM; }
+    public static final Type BOTTOM   = new Type( TBOT   ); // ALL
+    public static final Type TOP      = new Type( TTOP   ); // ANY
+    public static final Type CONTROL  = new Type( TCTRL  ); // Ctrl
+
+    public boolean isConstant() { return _type == TTOP; }
+
+    public StringBuilder _print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;}
+
+    public Type meet(Type other) { return BOTTOM; }
 
 }
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeBot.java b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeBot.java
deleted file mode 100644
index a5709448..00000000
--- a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeBot.java
+++ /dev/null
@@ -1,19 +0,0 @@
-package com.seaofnodes.simple.type;
-
-import java.lang.StringBuilder;
-
-public class TypeBot extends Type {
-
-    public static final TypeBot BOTTOM = new TypeBot();
-  
-    @Override
-    public String toString() { return "Bottom"; }
-
-    @Override
-    public Type meet(Type other) {
-        return BOTTOM;
-    }
-
-    @Override
-    public StringBuilder _print(StringBuilder sb) { return sb.append(toString()); }
-}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeControl.java b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeControl.java
deleted file mode 100644
index 0130ffd0..00000000
--- a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeControl.java
+++ /dev/null
@@ -1,16 +0,0 @@
-package com.seaofnodes.simple.type;
-
-public class TypeControl extends Type {
-
-    public static final TypeControl CONTROL = new TypeControl();
-
-    @Override
-    public StringBuilder _print(StringBuilder sb) {
-        return sb.append(toString());
-    }
-
-    @Override
-    public String toString() {
-        return "Control";
-    }
-}
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
index 63c46035..5c8c7049 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -17,7 +17,11 @@ public class TypeInteger extends Type {
      */
     private final long _con;
 
-    public TypeInteger(boolean is_con, long con) { _is_con = is_con; _con = con; }
+    public TypeInteger(boolean is_con, long con) {
+        super(TINT);
+        _is_con = is_con;
+        _con = con;
+    }
 
     public static TypeInteger constant(long con) { return new TypeInteger(true, con); }
 
diff --git a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
index 80d09884..a991a856 100644
--- a/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
+++ b/chapter05/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
@@ -5,6 +5,7 @@ public class TypeTuple extends Type {
     public final Type[] _types;
 
     public TypeTuple(Type... _types) {
+        super(TTUPLE);
         this._types = _types;
     }
 
@@ -15,8 +16,13 @@ public class TypeTuple extends Type {
 
     @Override
     public StringBuilder _print(StringBuilder sb) {
+        sb.append("[ ");
+        for( Type t : _types )
+            t._print(sb).append(",");
+        sb.setLength(sb.length()-1);
+        sb.append("]");
         return sb;
     }
 
-    public static final TypeTuple IF = new TypeTuple(new Type[]{TypeControl.CONTROL,TypeControl.CONTROL});
+    public static final TypeTuple IF = new TypeTuple(new Type[]{Type.CONTROL,Type.CONTROL});
 }