From 1a9cac97df063af82516ca35bde34fde62d24c56 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Sat, 11 Nov 2023 23:17:22 +0000 Subject: 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 * Update chapter06/README.md Co-authored-by: Yichen Yan * #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 Co-authored-by: Yichen Yan --- .../java/com/seaofnodes/simple/node/AddNode.java | 5 +++-- .../java/com/seaofnodes/simple/node/DivNode.java | 10 +++++----- .../java/com/seaofnodes/simple/node/MinusNode.java | 5 ++--- .../java/com/seaofnodes/simple/node/MulNode.java | 6 +++--- .../main/java/com/seaofnodes/simple/node/Node.java | 4 ++-- .../java/com/seaofnodes/simple/node/ReturnNode.java | 4 ++-- .../java/com/seaofnodes/simple/node/ScopeNode.java | 5 ++--- .../java/com/seaofnodes/simple/node/StartNode.java | 6 ++---- .../java/com/seaofnodes/simple/node/SubNode.java | 6 +++--- .../main/java/com/seaofnodes/simple/type/Type.java | 21 ++++++++++++++++++--- .../java/com/seaofnodes/simple/type/TypeBot.java | 14 -------------- .../com/seaofnodes/simple/type/TypeInteger.java | 7 +++++-- 12 files changed, 47 insertions(+), 46 deletions(-) delete mode 100644 chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java (limited to 'chapter03/src') diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java index 6784ad60..a0376dd4 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java index ca7df79c..4f502e5f 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 834f4c11..08924563 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java index 0fa54966..c6718d27 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java index a778687d..43dc6fa5 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/Node.java @@ -47,7 +47,7 @@ public abstract class Node { /** * A private Global Static mutable counter, for unique node id generation. - * To make the compiler multi-threaded, this field will have to move into a TLS. + * To make the compiler multithreaded, this field will have to move into a TLS. * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values. * */ private static int UNIQUE_ID = 1; @@ -197,7 +197,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 outs = _outputs; int lidx = outs.size()-1; // Last index // This 1-line hack compresses an element out of an ArrayList diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 18f5eed9..a0f2e931 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 5f5d66a0..49857533 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter03/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,7 +1,6 @@ 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 +42,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; } diff --git a/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java index 08b8333a..99e240ad 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java index 71d70fa6..6eda4f11 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java index 872e453d..172cc632 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeBot.java deleted file mode 100644 index bc191241..00000000 --- a/chapter03/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/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index ff6e865b..69fb811c 100644 --- a/chapter03/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter03/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); } -- cgit v1.2.3