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 | 2 +- .../java/com/seaofnodes/simple/node/BoolNode.java | 3 +- .../java/com/seaofnodes/simple/node/DivNode.java | 3 +- .../java/com/seaofnodes/simple/node/MinusNode.java | 3 +- .../java/com/seaofnodes/simple/node/MulNode.java | 3 +- .../main/java/com/seaofnodes/simple/node/Node.java | 2 +- .../java/com/seaofnodes/simple/node/ProjNode.java | 7 +++-- .../com/seaofnodes/simple/node/ReturnNode.java | 2 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 4 +-- .../java/com/seaofnodes/simple/node/StartNode.java | 1 - .../java/com/seaofnodes/simple/node/SubNode.java | 3 +- .../main/java/com/seaofnodes/simple/type/Type.java | 32 ++++++++++++++++++---- .../java/com/seaofnodes/simple/type/TypeBot.java | 19 ------------- .../com/seaofnodes/simple/type/TypeControl.java | 16 ----------- .../com/seaofnodes/simple/type/TypeInteger.java | 11 ++++---- .../java/com/seaofnodes/simple/type/TypeTuple.java | 6 ++++ 16 files changed, 53 insertions(+), 64 deletions(-) delete mode 100644 chapter04/src/main/java/com/seaofnodes/simple/type/TypeBot.java delete mode 100644 chapter04/src/main/java/com/seaofnodes/simple/type/TypeControl.java (limited to 'chapter04/src/main/java') diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/AddNode.java index d4d15bef..d9fc6ad9 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter04/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/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 02eb7ce9..06be0b75 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter04/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/chapter04/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/DivNode.java index ae87deac..86b1e95c 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter04/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,7 +27,7 @@ public class DivNode extends Node { : TypeInteger.constant(i0.value()/i1.value()); return i0.meet(i1); } - return TypeBot.BOTTOM; + return Type.BOTTOM; } @Override diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 533155d9..08924563 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter04/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/chapter04/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/MulNode.java index 5f6c1ad8..19f2a340 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter04/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/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java index 804d30e0..b8a7bbd6 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/node/Node.java @@ -226,7 +226,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/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java index be0556ed..6f36226b 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter04/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/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index e20d01e5..73594d2a 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter04/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/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 45966791..17ea561a 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter04/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; } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java index 91573de8..85c6cd34 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter04/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/chapter04/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter04/src/main/java/com/seaofnodes/simple/node/SubNode.java index 42ddc1c1..ec2168e6 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter04/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/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java index d9567dc8..a063e28e 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/type/Type.java @@ -17,14 +17,36 @@ 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 Type.BOTTOM; } + + @Override + public final String toString() { + return _print(new StringBuilder()).toString(); + } } diff --git a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeBot.java b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeBot.java deleted file mode 100644 index a5709448..00000000 --- a/chapter04/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/chapter04/src/main/java/com/seaofnodes/simple/type/TypeControl.java b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeControl.java deleted file mode 100644 index 0130ffd0..00000000 --- a/chapter04/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/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 63c46035..3037e45f 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -17,18 +17,17 @@ 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); } public boolean isTop() { return !_is_con && _con==0; } public boolean isBot() { return !_is_con && _con==1; } - @Override - public String toString() { - return _print(new StringBuilder()).toString(); - } - @Override public StringBuilder _print(StringBuilder sb) { if (isTop()) return sb.append("IntTop"); diff --git a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 036147a2..513972aa 100644 --- a/chapter04/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/chapter04/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,6 +16,11 @@ 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; } } -- cgit v1.2.3