diff options
Diffstat (limited to 'chapter05/src/main/java')
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}); } |