diff options
Diffstat (limited to 'chapter06/src/main/java/com')
9 files changed, 96 insertions, 23 deletions
diff --git a/chapter06/src/main/java/com/seaofnodes/simple/Parser.java b/chapter06/src/main/java/com/seaofnodes/simple/Parser.java index b08c3c56..1bfe5b0d 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/Parser.java @@ -14,11 +14,6 @@ import java.util.*; */ public class Parser { - /** - * The control is a name that binds to the currently active control - * node in the graph - */ - public static final String CTRL = "$ctrl"; /** * A Global Static, unique to each compilation. This is a public, so we @@ -80,6 +75,9 @@ public class Parser { this(source, TypeInteger.BOT); } + @Override + public String toString() { return _lexer.toString(); } + String src() { return new String( _lexer._input ); } private Node ctrl() { return _scope.ctrl(); } @@ -91,7 +89,7 @@ public class Parser { _allScopes.push(_scope); _scope.push(); try { - _scope.define(CTRL , new ProjNode(START, 0, CTRL ).peephole()); + _scope.ctrl(new ProjNode(START, 0, ScopeNode.CTRL).peephole()); _scope.define("arg", new ProjNode(START, 1, "arg").peephole()); parseBlock(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); @@ -522,7 +520,4 @@ public class Parser { return new String(_input, start, 1); } } - - public static RuntimeException TODO() { return TODO("Not yet implemented"); } - public static RuntimeException TODO(String msg) { return new RuntimeException(msg); } } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/Utils.java b/chapter06/src/main/java/com/seaofnodes/simple/Utils.java new file mode 100644 index 00000000..c79d96f0 --- /dev/null +++ b/chapter06/src/main/java/com/seaofnodes/simple/Utils.java @@ -0,0 +1,6 @@ +package com.seaofnodes.simple; + +public class Utils { + public static RuntimeException TODO() { return TODO("Not yet implemented"); } + public static RuntimeException TODO(String msg) { return new RuntimeException(msg); } +}
\ No newline at end of file diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java index 61359d64..b29fb92c 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.*; public class AddNode extends Node { @@ -64,7 +63,8 @@ public class AddNode extends Node { // Now we might see (add add non) or (add non non) but never (add non add) nor (add add add) if( !(lhs instanceof AddNode) ) - return spline_cmp(lhs,rhs) ? swap12() : null; + // Rotate; look for (add (phi cons) con/(phi cons)) + return spline_cmp(lhs,rhs) ? swap12() : phiCon(this,true); // Now we only see (add add non) diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java index 9e88710c..1b0fdac7 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -31,9 +31,19 @@ public class IfNode extends MultiNode { // If constant is 0 then false branch is reachable // Else true branch is reachable if (pred()._type instanceof TypeInteger ti && ti.isConstant()) { - if (ti.value() == 0) return TypeTuple.IF_FALSE; - else return TypeTuple.IF_TRUE; + if (ti.value() == 0) return TypeTuple.IF_FALSE; + else return TypeTuple.IF_TRUE; } + + // Hunt up the immediate dominator tree. If we find an identical if + // test on either the true or false branch, then this test matches. + for( Node dom = idom(), prior=this; dom!=null; prior=dom, dom = dom.idom() ) + if( dom instanceof IfNode iff && iff.pred()==pred() ) + return prior instanceof ProjNode proj + // Repeated test, dominated on one side. Test result is the same. + ? (proj._idx==0 ? TypeTuple.IF_TRUE : TypeTuple.IF_FALSE) + : null; // Repeated test not dominated on one side + return TypeTuple.IF_BOTH; } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java index fe3fddf8..81c90f68 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -1,7 +1,5 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.Type; - public abstract class MultiNode extends Node { public MultiNode(Node... inputs) { super(inputs); } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java index fd1b870c..36e4896d 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import java.util.*; @@ -46,6 +46,16 @@ public abstract class Node { */ public Type _type; + + /** + * Immediate dominator tree depth, used to approximate a real IDOM during + * parsing where we do not have the whole program, and also peepholes + * change the CFG incrementally. + * <p> + * See {@link https://en.wikipedia.org/wiki/Dominator_(graph_theory)} + */ + int _idepth; + /** * A private Global Static mutable counter, for unique node id generation. * To make the compiler multithreaded, this field will have to move into a TLS. @@ -367,10 +377,18 @@ public abstract class Node { return true; } + // Return the immediate dominator of this Node and compute dom tree depth. + Node idom() { + Node idom = in(0); + if( idom._idepth==0 ) idom.idom(); // Recursively set _idepth + if( _idepth==0 ) _idepth = idom._idepth+1; + return idom; + } + // Make a shallow copy (same class) of this Node, with given inputs and // empty outputs and a new Node ID. The original inputs are ignored. // Does not need to be implemented in isCFG() nodes. - Node copy(Node lhs, Node rhs) { throw Parser.TODO("Binary ops need to implement copy"); } + Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); } /** * Used to allow repeating tests in the same JVM. This just resets the diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 1ddf520b..d3fd7745 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -1,6 +1,6 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; public class RegionNode extends Node { @@ -39,7 +39,7 @@ public class RegionNode extends Node { for( Node phi : _outputs ) if( phi instanceof PhiNode ) // Currently does not happen, because no loops - throw Parser.TODO(); + throw Utils.TODO(); return in(1); } return this; @@ -53,4 +53,23 @@ public class RegionNode extends Node { return i; return 0; // All inputs alive } + + // Immediate dominator of Region is a little more complicated. + private Node _idom; // Immediate dominator cache + @Override Node idom() { + if( _idom != null ) return _idom; // Return cached copy + if( nIns()!=3 ) return null; // Fails for anything other than 2-inputs + // Walk the LHS & RHS idom trees in parallel until they match, or either fails + Node lhs = in(1).idom(); + Node rhs = in(2).idom(); + while( lhs != rhs ) { + if( lhs==null || rhs==null ) return null; + var comp = lhs._idepth - rhs._idepth; + if( comp >= 0 ) lhs = lhs.idom(); + if( comp <= 0 ) rhs = rhs.idom(); + } + if( lhs==null ) return null; + _idepth = lhs._idepth+1; + return (_idom=lhs); + } } diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index eecab9f9..96564f3b 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import java.util.*; @@ -12,6 +11,12 @@ import java.util.*; public class ScopeNode extends Node { /** + * The control is a name that binds to the currently active control + * node in the graph + */ + public static final String CTRL = "$ctrl"; + + /** * Stack of lexical scopes, each scope is a symbol table * that binds variable names to Nodes. * The top of this stack represents current scope. @@ -76,10 +81,26 @@ public class ScopeNode extends Node { return null; } - public Node ctrl() { assert lookup(Parser.CTRL)==in(0); return in(0); } - + public Node ctrl() { assert lookup(CTRL)==in(0); return in(0); } + + /** + * The ctrl of a ScopeNode is always bound to the currently active + * control node in the graph, via a special name '$ctrl' that is not + * a valid identifier in the language grammar and hence cannot be + * referenced in Simple code. + * + * @param n The node to be bound to '$ctrl' + * + * @return Node that was bound + */ public Node ctrl(Node n) { - assert lookup(Parser.CTRL)==in(0); + if (nIns() == 0) { + // The first time a scope is created we do not have the name binding + // for '$ctrl' but after that we expect to find the name already bound + assert lookup(CTRL) == null; + define(CTRL, n); + } + else assert lookup(CTRL) == in(0); set_def(0,n); return n; } @@ -128,6 +149,7 @@ public class ScopeNode extends Node { */ public Node mergeScopes(ScopeNode that) { RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep()); + // Note that we skip i==0, which is bound to '$ctrl' for (int i = 1; i < nIns(); i++) if (in(i) != that.in(i)) // No need for redundant Phis set_def(i, new PhiNode(_rlabels.get(i), r, in(i), that.in(i)).peephole()); diff --git a/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java index 85c6cd34..8cff25bd 100644 --- a/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter06/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -34,4 +34,9 @@ public class StartNode extends MultiNode { @Override public Node idealize() { return null; } + + // No immediate dominator, and idepth==0 + @Override + Node idom() { return null; } + } |