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>

10 files changed, 43 insertions, 41 deletions

diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java
index 6784ad60..a0376dd4 100644
--- a/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java
+++ b/chapter02/src/main/java/com/seaofnodes/simple/node/AddNode.java
@@ -21,9 +21,10 @@ public class AddNode extends Node {
     public Type compute() {
         if( in(1)._type instanceof TypeInteger i0 &&
             in(2)._type instanceof TypeInteger i1 ) {
-            return TypeInteger.constant(i0.value()+i1.value());
+            if (i0.isConstant() && i1.isConstant())
+                return TypeInteger.constant(i0.value()+i1.value());
         }
-        return TypeBot.BOTTOM;
+        return Type.BOTTOM;
     }
 
     @Override
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/DivNode.java
index ca7df79c..4f502e5f 100644
--- a/chapter02/src/main/java/com/seaofnodes/simple/node/DivNode.java
+++ b/chapter02/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 {
@@ -22,11 +21,12 @@ public class DivNode extends Node {
     public Type compute() {
         if (in(1)._type instanceof TypeInteger i0 &&
             in(2)._type instanceof TypeInteger i1) {
-            return i1.value() == 0
-                ? TypeInteger.ZERO
-                : TypeInteger.constant(i0.value()/i1.value());
+            if (i0.isConstant() && i1.isConstant())
+                return i1.value() == 0
+                    ? TypeInteger.ZERO
+                    : TypeInteger.constant(i0.value()/i1.value());
         }
-        return TypeBot.BOTTOM;
+        return Type.BOTTOM;
     }
 
     @Override
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/MinusNode.java
index 834f4c11..08924563 100644
--- a/chapter02/src/main/java/com/seaofnodes/simple/node/MinusNode.java
+++ b/chapter02/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 {
@@ -20,8 +19,8 @@ public class MinusNode extends Node {
     @Override
     public Type compute() {
         if (in(1)._type instanceof TypeInteger i0)
-            return TypeInteger.constant(-i0.value());
-        return TypeBot.BOTTOM;
+            return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0;
+        return Type.BOTTOM;
     }
 
     @Override
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/MulNode.java
index 0fa54966..c6718d27 100644
--- a/chapter02/src/main/java/com/seaofnodes/simple/node/MulNode.java
+++ b/chapter02/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 {
@@ -22,9 +21,10 @@ public class MulNode extends Node {
     public Type compute() {
         if (in(1)._type instanceof TypeInteger i0 &&
             in(2)._type instanceof TypeInteger i1) {
-            return TypeInteger.constant(i0.value()*i1.value());
+            if (i0.isConstant() && i1.isConstant())
+                return TypeInteger.constant(i0.value()*i1.value());
         }
-        return TypeBot.BOTTOM;
+        return Type.BOTTOM;
     }
 
     @Override
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
index 18f5eed9..a0f2e931 100644
--- a/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
+++ b/chapter02/src/main/java/com/seaofnodes/simple/node/ReturnNode.java
@@ -31,8 +31,8 @@ public class ReturnNode extends Node {
     @Override public boolean isCFG() { return true; }
   
     @Override
-    public TypeBot compute() {
-        return TypeBot.BOTTOM;
+    public Type compute() {
+        return Type.BOTTOM;
     }
 
     @Override
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java
index 08b8333a..99e240ad 100644
--- a/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java
+++ b/chapter02/src/main/java/com/seaofnodes/simple/node/StartNode.java
@@ -1,6 +1,6 @@
 package com.seaofnodes.simple.node;
 
-import com.seaofnodes.simple.type.TypeBot;
+import com.seaofnodes.simple.type.Type;
 
 /**
  * The Start node represents the start of the function.  For now, we do not
@@ -26,9 +26,7 @@ public class StartNode extends Node {
     @Override public boolean isCFG() { return true; }
 
     @Override
-    public TypeBot compute() {
-        return TypeBot.BOTTOM;
-    }
+    public Type compute() { return Type.BOTTOM; }
 
     @Override
     public Node idealize() { return null; }
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter02/src/main/java/com/seaofnodes/simple/node/SubNode.java
index 71d70fa6..6eda4f11 100644
--- a/chapter02/src/main/java/com/seaofnodes/simple/node/SubNode.java
+++ b/chapter02/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 {
@@ -22,9 +21,10 @@ public class SubNode extends Node {
     public Type compute() {
         if (in(1)._type instanceof TypeInteger i0 &&
             in(2)._type instanceof TypeInteger i1) {
-            return TypeInteger.constant(i0.value()-i1.value());
+            if (i0.isConstant() && i1.isConstant())
+                return TypeInteger.constant(i0.value()-i1.value());
         }
-        return TypeBot.BOTTOM;
+        return Type.BOTTOM;
     }
 
     @Override
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java
index 872e453d..172cc632 100644
--- a/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/chapter02/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -17,9 +17,24 @@ package com.seaofnodes.simple.type;
  * simple constant folding e.g. 1+2 == 3 stuff.
  */    
 
-public abstract class Type {
+public class Type {
 
-    public boolean isConstant() { return false; }
+    // ----------------------------------------------------------
+    // 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 TSIMPLE = 2; // End of the Simple Types
+    static final byte TINT    = 3; // All Integers; see TypeInteger
+    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"};
+    protected Type(byte type) { _type = type; }
+
+    public static final Type BOTTOM   = new Type( TBOT ); // ALL
+
+    public boolean isConstant() { return _type == TTOP; }
+
+    public StringBuilder _print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;}
 }
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/type/TypeBot.java b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeBot.java
deleted file mode 100644
index bc191241..00000000
--- a/chapter02/src/main/java/com/seaofnodes/simple/type/TypeBot.java
+++ /dev/null
@@ -1,14 +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 StringBuilder _print(StringBuilder sb) { return sb.append(toString()); }
-}
diff --git a/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
index ff6e865b..69fb811c 100644
--- a/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
+++ b/chapter02/src/main/java/com/seaofnodes/simple/type/TypeInteger.java
@@ -10,9 +10,12 @@ public class TypeInteger extends Type {
     /**
      * The constant value observed for this type
      */
-    public final long _con;
+    private final long _con;
 
-    public TypeInteger(long con) { _con = con; }
+    public TypeInteger(long con) { 
+		super(TINT);
+		_con = con; 
+	}
 
     public static TypeInteger constant(long con) { return new TypeInteger(con); }