diff options
Diffstat (limited to 'src')
22 files changed, 559 insertions, 82 deletions
diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index c35a4e32..b30dd450 100644 --- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -17,7 +17,7 @@ public class GraphVisualizer { // nodes in the graph. Collection<Node> all = findAll(parser); StringBuilder sb = new StringBuilder(); - sb.append("digraph chapter05 {\n"); + sb.append("digraph chapter06 {\n"); sb.append("/*\n"); sb.append(parser.src()); sb.append("\n*/\n"); @@ -207,29 +207,24 @@ public class GraphVisualizer { * Finds all nodes in the graph. */ private Collection<Node> findAll(Parser parser) { - final StartNode start = Parser.START; final HashMap<Integer, Node> all = new HashMap<>(); - for( Node n : start._outputs ) + for( Node n : Parser.START._outputs ) + walk(all, n); + for( Node n : parser._scope._inputs ) walk(all, n); - // Scan symbol tables - for( HashMap<String,Integer> scope : parser._scope._scopes ) - for (Integer i : scope.values()) - walk(all, parser._scope.in(i)); return all.values(); } /** * Walk a subgraph and populate distinct nodes in the all list. */ - private void walk(HashMap<Integer, Node> all, Node n) { + private void walk(HashMap<Integer,Node> all, Node n) { if(n == null ) return; if (all.get(n._nid) != null) return; // Been there, done that all.put(n._nid, n); for (Node c : n._inputs) - if (c != null) - walk(all, c); - for (Node c : n._outputs) - if (c != null) - walk(all, c); + walk(all, c); + for( Node c : n._outputs ) + walk(all, c); } } diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 80674d59..1a15efa3 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -155,6 +155,7 @@ public class Parser { IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).<IfNode>keep().peephole(); // Setup projection nodes Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); + ifNode.unkeep(); Node ifF = new ProjNode(ifNode, 1, "False").peephole(); // In if true branch, the ifT proj node becomes the ctrl // But first clone the scope and set it as current @@ -198,7 +199,7 @@ public class Parser { private Node parseReturn() { var expr = require(parseExpression(), ";"); Node ret = STOP.addReturn(new ReturnNode(ctrl(), expr).peephole()); - ctrl(null); // Kill control + ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill control return ret; } diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 081c9276..b37785f6 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -63,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) @@ -72,23 +73,12 @@ public class AddNode extends Node { if( lhs.in(2)._type.isConstant() && t2.isConstant() ) return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); - if( lhs.in(2) instanceof PhiNode phi && phi.allCons() && - // Do we have ((x + (phi cons)) + con) ? - // Do we have ((x + (phi cons)) + (phi cons)) ? - // Push constant up through the phi: x + (phi con0+con0 con1+con1...) - - // Note that this is the exact reverse of Phi pulling a common op - // down to reduce total op-count. We don't get in an endless push- - // up push-down peephole cycle because the constants all fold first. - (t2.isConstant() || (rhs instanceof PhiNode && phi.in(0) == rhs.in(0) && rhs.allCons()) ) ) { - Node[] ns = new Node[phi.nIns()]; - ns[0] = phi.in(0); - // Push constant up through the phi: x + (phi con0+con0 con1+con1...) - for( int i=1; i<ns.length; i++ ) - ns[i] = new AddNode(phi.in(i),t2.isConstant() ? rhs : rhs.in(i)).peephole(); - String label = phi._label + (rhs instanceof PhiNode rphi ? rphi._label : ""); - return new AddNode(lhs.in(1),new PhiNode(label,ns).peephole()); - } + + // Do we have ((x + (phi cons)) + con) ? + // Do we have ((x + (phi cons)) + (phi cons)) ? + // Push constant up through the phi: x + (phi con0+con0 con1+con1...) + Node phicon = phiCon(this,true); + if( phicon!=null ) return phicon; // Now we sort along the spline via rotates, to gather similar things together. @@ -100,6 +90,47 @@ public class AddNode extends Node { return null; } + // Rotation is only valid for associative ops, e.g. Add, Mul, And, Or. + // Do we have ((phi cons)|(x + (phi cons)) + con|(phi cons)) ? + // Push constant up through the phi: x + (phi con0+con0 con1+con1...) + static Node phiCon(Node op, boolean rotate) { + Node lhs = op.in(1); + Node rhs = op.in(2); + // LHS is either a Phi of constants, or another op with Phi of constants + PhiNode lphi = pcon(lhs); + if( rotate && lphi==null && lhs.nIns() > 2 ) { + // Only valid to rotate constants if both are same associative ops + if( lhs.getClass() != op.getClass() ) return null; + lphi = pcon(lhs.in(2)); // Will rotate with the Phi push + } + if( lphi==null ) return null; + + // RHS is a constant or a Phi of constants + if( !(rhs instanceof ConstantNode con) && pcon(rhs)==null ) + return null; + + // If both are Phis, must be same Region + if( rhs instanceof PhiNode && lphi.in(0) != rhs.in(0) ) + return null; + + // Note that this is the exact reverse of Phi pulling a common op down + // to reduce total op-count. We don't get in an endless push-up + // push-down peephole cycle because the constants all fold first. + Node[] ns = new Node[lphi.nIns()]; + ns[0] = lphi.in(0); + // Push constant up through the phi: x + (phi con0+con0 con1+con1...) + for( int i=1; i<ns.length; i++ ) + ns[i] = op.copy(lphi.in(i), rhs instanceof PhiNode ? rhs.in(i) : rhs).peephole(); + String label = lphi._label + (rhs instanceof PhiNode rphi ? rphi._label : ""); + Node phi = new PhiNode(label,ns).peephole(); + // Rotate needs another op, otherwise just the phi + return lhs==lphi ? phi : op.copy(lhs.in(1),phi); + } + + static PhiNode pcon(Node op) { + return op instanceof PhiNode phi && phi.allCons() ? phi : null; + } + // Compare two off-spline nodes and decide what order they should be in. // Do we rotate ((x + hi) + lo) into ((x + lo) + hi) ? // Generally constants always go right, then Phi-of-constants, then muls, then others. diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 7a4a087e..a9ec6838 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -43,6 +43,12 @@ abstract public class BoolNode extends Node { if( in(1)==in(2) ) return new ConstantNode(TypeInteger.constant(doOp(3,3)?1:0)); + // Do we have ((x * (phi cons)) * con) ? + // Do we have ((x * (phi cons)) * (phi cons)) ? + // Push constant up through the phi: x * (phi con0*con0 con1*con1...) + Node phicon = AddNode.phiCon(this,false); + if( phicon!=null ) return phicon; + return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 6124b893..34846e99 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -26,7 +26,25 @@ public class IfNode extends MultiNode { @Override public Type compute() { - return TypeTuple.IF; + // If the If node is not reachable then neither is any following Proj + if (ctrl()._type != Type.CONTROL) return TypeTuple.IF_NEITHER; + // 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; + } + + // 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; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 2dbdd695..0380c079 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -44,6 +44,12 @@ public class MulNode extends Node { if ( t1.isConstant() && !t2.isConstant() ) return swap12(); + // Do we have ((x * (phi cons)) * con) ? + // Do we have ((x * (phi cons)) * (phi cons)) ? + // Push constant up through the phi: x * (phi con0*con0 con1*con1...) + Node phicon = AddNode.phiCon(this,true); + if( phicon!=null ) return phicon; + return null; } @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 8681ac5a..39e8ff8d 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -46,9 +46,19 @@ 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 <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} + */ + int _idepth; + /** * 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; @@ -151,6 +161,17 @@ public abstract class Node { return new_def; } + // Remove the numbered input, compressing the inputs in-place. This + // shuffles the order deterministically - which is suitable for Region and + // Phi, but not for every Node. + void delDef(int idx) { + Node old_def = in(idx); + if( old_def != null && // If the old def exists, remove a def->use edge + old_def.delUse(this) ) // If we removed the last use, the old def is now dead + old_def.kill(); // Kill old def + Utils.del(_inputs, idx); + } + /** * Add a new def to an existing Node. Keep the edges correct by * adding the corresponding <em>def->use</em> edge. @@ -358,6 +379,14 @@ 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. diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 374e1183..15088e08 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -26,14 +26,18 @@ public class PhiNode extends Node { @Override public Type compute() { - return Type.BOTTOM; + Type t = Type.TOP; + for (int i = 1; i < nIns(); i++) + t = t.meet(in(i)._type); + return t; } @Override public Node idealize() { - // Remove a "junk" Phi: Phi(x,x) is just x - if( same_inputs() ) - return in(1); + // If we have only a single unique input, become it. + Node live = singleUniqueInput(); + if (live != null) + return live; // Pull "down" a common data op. One less op in the world. One more // Phi, but Phis do not make code. @@ -63,11 +67,17 @@ public class PhiNode extends Node { return true; } - private boolean same_inputs() { - for( int i=2; i<nIns(); i++ ) - if( in(1) != in(i) ) - return false; - return true; + /** + * If only single unique input, return it + */ + private Node singleUniqueInput() { + Node live = null; + for( int i=1; i<nIns(); i++ ) + if( region().in(i)._type != Type.XCONTROL && in(i) != this ) + if( live == null || live == in(i) ) live = in(i); + else return null; + return live; } + } diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 2826d192..85f28037 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -35,6 +35,8 @@ public class ProjNode extends Node { @Override public Node idealize() { + if( ctrl()._type instanceof TypeTuple tt && tt._types[1-_idx]==Type.XCONTROL ) // Only true for IfNodes + return ctrl().in(0); // We become our input control return null; } } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 5d520d65..bb7998a3 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; public class RegionNode extends Node { @@ -17,11 +18,58 @@ public class RegionNode extends Node { @Override public Type compute() { - return Type.CONTROL; + Type t = Type.XCONTROL; + for (int i = 1; i < nIns(); i++) + t = t.meet(in(i)._type); + return t; } @Override public Node idealize() { + int path = findDeadInput(); + if( path != 0 ) { + for( Node phi : _outputs ) + if( phi instanceof PhiNode ) + phi.delDef(path); + delDef(path); + + // If down to a single input, become that input - but also make all + // Phis an identity on *their* single input. + if( nIns()==2 ) { + for( Node phi : _outputs ) + if( phi instanceof PhiNode ) + // Currently does not happen, because no loops + throw Utils.TODO(); + return in(1); + } + return this; + } return null; } + + private int findDeadInput() { + for( int i=1; i<nIns(); i++ ) + if( in(i)._type==Type.XCONTROL ) + 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/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index c9d6c9c8..6130d050 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -36,5 +36,9 @@ public class ReturnNode extends Node { } @Override - public Node idealize() { return null; } + public Node idealize() { + if( ctrl()._type==Type.XCONTROL ) + return ctrl(); + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 32045fbc..a7a04a42 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -162,14 +162,14 @@ public class ScopeNode extends Node { * @return A new node representing the merge point */ public Node mergeScopes(ScopeNode that) { - RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).peephole()); + RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep()); String[] ns = reverseNames(); // 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 setDef(i, new PhiNode(ns[i], r, in(i), that.in(i)).peephole()); that.kill(); // Kill merged scope - return r; + return r.unkeep().peephole(); } } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 022e276d..c5a45876 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -35,4 +35,9 @@ public class StartNode extends MultiNode { @Override public Node idealize() { return null; } + + // No immediate dominator, and idepth==0 + @Override + Node idom() { return null; } + } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index a30256f9..01574dc7 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -36,6 +36,11 @@ public class StopNode extends Node { @Override public Node idealize() { + int len = nIns(); + for( int i=0; i<nIns(); i++ ) + if( in(i)._type==Type.XCONTROL ) + delDef(i--); + if( len != nIns() ) return this; return null; } diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index 6b9130ba..d66fb3e7 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -25,25 +25,50 @@ public class Type { 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 + static final byte TXCTRL = 3; // Ctrl flow top (mini-lattice: any-xctrl-ctrl-all) + static final byte TSIMPLE = 4; // End of the Simple Types + static final byte TINT = 5; // All Integers; see TypeInteger + static final byte TTUPLE = 6; // Tuples; finite collections of unrelated Types, kept in parallel public final byte _type; public boolean is_simple() { return _type < TSIMPLE; } - private static final String[] STRS = new String[]{"Bot","Top","Ctrl"}; + private static final String[] STRS = new String[]{"Bot","Top","Ctrl","~Ctrl"}; protected Type(byte type) { _type = type; } 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 static final Type XCONTROL = new Type( TXCTRL ); // ~Ctrl - public boolean isConstant() { return _type == TTOP; } + public boolean isConstant() { return _type == TTOP || _type == TXCTRL; } public StringBuilder print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;} - public Type meet(Type other) { return BOTTOM; } + public final Type meet(Type t) { + // Shortcut for the self case + if( t == this ) return this; + // Same-type is always safe in the subclasses + if( _type==t._type ) return xmeet(t); + // Reverse; xmeet 2nd arg is never "is_simple" and never equal to "this". + if( is_simple() ) return this.xmeet(t ); + if( t.is_simple() ) return t .xmeet(this); + return BOTTOM; // Mixing 2 unrelated types + } + + // Compute meet right now. Overridden in subclasses. + // Handle cases where 'this.is_simple()' and unequal to 't'. + // Subclassed xmeet calls can assert that '!t.is_simple()'. + protected Type xmeet(Type t) { + assert is_simple(); // Should be overridden in subclass + // ANY meet anything is thing; thing meet ALL is ALL + if( _type==TBOT || t._type==TTOP ) return this; + if( _type==TTOP || t._type==TBOT ) return t; + // 'this' is {TCTRL,TXCTRL} + if( !t.is_simple() ) return BOTTOM; + // 't' is {TCTRL,TXCTRL} + return _type==TCTRL || t._type==TCTRL ? CONTROL : XCONTROL; + } @Override public final String toString() { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index cbaff45f..a9f6ee1c 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -41,7 +41,7 @@ public class TypeInteger extends Type { public long value() { return _con; } @Override - public Type meet(Type other) { + public Type xmeet(Type other) { if( this==other ) return this; if (!(other instanceof TypeInteger i)) return super.meet(other); // BOT wins diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index da701865..39d8f72b 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -10,7 +10,7 @@ public class TypeTuple extends Type { } @Override - public Type meet(Type other) { + public Type xmeet(Type other) { throw new UnsupportedOperationException("Meet on Tuple Type not yet implemented"); } @@ -24,5 +24,9 @@ public class TypeTuple extends Type { return sb; } - public static final TypeTuple IF = new TypeTuple(new Type[]{Type.CONTROL,Type.CONTROL}); + public static final TypeTuple IF_BOTH = new TypeTuple(new Type[]{Type.CONTROL, Type.CONTROL}); + public static final TypeTuple IF_NEITHER = new TypeTuple(new Type[]{Type.XCONTROL,Type.XCONTROL}); + public static final TypeTuple IF_TRUE = new TypeTuple(new Type[]{Type.CONTROL, Type.XCONTROL}); + public static final TypeTuple IF_FALSE = new TypeTuple(new Type[]{Type.XCONTROL,Type.CONTROL}); + } diff --git a/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 4085ed7e..47cee096 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -14,8 +14,6 @@ public class Chapter02Test { Node._disablePeephole = true; // disable peephole so we can observe full graph StopNode ret = parser.parse(); assertEquals("return (1+((2*3)+(-5)));", ret.print()); - GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(parser)); Node._disablePeephole = false; } @@ -59,8 +57,6 @@ public class Chapter02Test { Parser parser = new Parser("return 1+2*3+-5;"); StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); - GraphVisualizer gv = new GraphVisualizer(); - System.out.println(gv.generateDotOutput(parser)); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java index adbfba84..10b67f5f 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -31,7 +31,7 @@ public class Chapter03Test { @Test public void testVarScopeNoPeephole() { - Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); Node._disablePeephole = true; StopNode ret = parser.parse(); Node._disablePeephole = false; @@ -40,7 +40,7 @@ public class Chapter03Test { @Test public void testVarDist() { - Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;"); + Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1);"); StopNode ret = parser.parse(); assertEquals("return 8;", ret.print()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/src/test/java/com/seaofnodes/simple/Chapter04Test.java index 55c0b15f..98878ca6 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -10,7 +10,7 @@ public class Chapter04Test { @Test public void testPeephole() { - Parser parser = new Parser("return 1+arg+2; #showGraph;"); + Parser parser = new Parser("return 1+arg+2;"); StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @@ -38,7 +38,7 @@ public class Chapter04Test { @Test public void testPeephole3() { - Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;"); + Parser parser = new Parser("return 1+arg+2+arg+3;"); StopNode ret = parser.parse(); assertEquals("return ((arg*2)+6);", ret.print()); } @@ -52,7 +52,7 @@ public class Chapter04Test { @Test public void testVarArg() { - Parser parser = new Parser("return arg; #showGraph;"); + Parser parser = new Parser("return arg;"); StopNode stop = parser.parse(); ReturnNode ret = stop.ret(); assertTrue(ret.in(0) instanceof ProjNode); @@ -61,49 +61,49 @@ public class Chapter04Test { @Test public void testConstantArg() { - Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2)); + Parser parser = new Parser("return arg;", TypeInteger.constant(2)); StopNode ret = parser.parse(); assertEquals("return 2;", ret.print()); } @Test public void testCompEq() { - Parser parser = new Parser("return 3==3; #showGraph;"); + Parser parser = new Parser("return 3==3;"); StopNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testCompEq2() { - Parser parser = new Parser("return 3==4; #showGraph;"); + Parser parser = new Parser("return 3==4;"); StopNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test public void testCompNEq() { - Parser parser = new Parser("return 3!=3; #showGraph;"); + Parser parser = new Parser("return 3!=3;"); StopNode ret = parser.parse(); assertEquals("return 0;", ret.print()); } @Test public void testCompNEq2() { - Parser parser = new Parser("return 3!=4; #showGraph;"); + Parser parser = new Parser("return 3!=4;"); StopNode ret = parser.parse(); assertEquals("return 1;", ret.print()); } @Test public void testBug1() { - Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;"); + Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2;"); StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test public void testBug2() { - Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;"); + Parser parser = new Parser("int a=arg+1; a=a; return a;"); StopNode ret = parser.parse(); assertEquals("return (arg+1);", ret.print()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java index b5fcbeaf..134a8be2 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -17,11 +17,9 @@ if (arg == 1) a = arg+2; else { a = arg-3; - #showGraph; } -#showGraph; return a;"""); - StopNode ret = parser.parse(true); + StopNode ret = parser.parse(false); assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); } @@ -36,7 +34,7 @@ if (arg == 1) { c = 4; } return c;""", TypeInteger.BOT); - StopNode ret = parser.parse(true); + StopNode ret = parser.parse(false); assertEquals("return Phi(Region16,4,3);", ret.toString()); } @@ -48,7 +46,7 @@ if( arg==1 ) return 3; else return 4; -#showGraph;""", TypeInteger.BOT); +""", TypeInteger.BOT); StopNode stop = parser.parse(); assertEquals("Stop[ return 3; return 4; ]", stop.toString()); } @@ -64,7 +62,7 @@ if( arg==1 ) else b=a+1; return a+b;"""); - StopNode ret = parser.parse(true); + StopNode ret = parser.parse(false); assertEquals("return ((arg*2)+Phi(Region20,2,3));", ret.toString()); } @@ -79,7 +77,7 @@ if( arg==1 ) else a=b+1; return a+b;"""); - StopNode ret = parser.parse(true); + StopNode ret = parser.parse(false); assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region31,4,5));", ret.toString()); } @@ -98,7 +96,7 @@ else if( arg==3 ) else a=5; return a; -#showGraph;""", TypeInteger.BOT); +""", TypeInteger.BOT); StopNode stop = parser.parse(); assertEquals("return Phi(Region33,Phi(Region21,2,3),Phi(Region31,4,5));", stop.toString()); } @@ -114,7 +112,7 @@ if( arg ) if( arg==0 ) b=2; return arg+a+b; -#showGraph;""", TypeInteger.BOT); +""", TypeInteger.BOT); StopNode stop = parser.parse(); assertEquals("return ((arg+Phi(Region13,1,0))+Phi(Region22,2,0));", stop.toString()); } @@ -129,7 +127,7 @@ if( arg==1 ) a=arg==3; } return a;"""); - StopNode ret = parser.parse(true); + StopNode ret = parser.parse(false); assertEquals("return (arg==Phi(Region16,3,2));", ret.toString()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java new file mode 100644 index 00000000..44b49d73 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -0,0 +1,294 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter06Test { + + @Test + public void testPeepholeReturn() { + Parser parser = new Parser( +""" +if( true ) return 2; +return 1; +"""); + StopNode stop = parser.parse(false); + assertEquals("return 2;", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testPeepholeRotate() { + Parser parser = new Parser( +""" +int a = 1; +if (arg) + a = 2; +return (arg < a) < 3; +"""); + StopNode stop = parser.parse(false); + assertEquals("return ((arg<Phi(Region12,2,1))<3);", stop.toString()); + } + + @Test + public void testPeepholeCFG() { + Parser parser = new Parser( +""" +int a=1; +if( true ) + a=2; +else + a=3; +return a; +"""); + StopNode stop = parser.parse(false); + assertEquals("return 2;", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testIfIf() { + Parser parser = new Parser( +""" +int a=1; +if( arg!=1 ) + a=2; +else + a=3; +int b=4; +if( a==2 ) + b=42; +else + b=5; +return b;""", TypeInteger.BOT); + StopNode stop = parser.parse(false); + assertEquals("return Phi(Region32,42,5);", stop.toString()); + } + + @Test + public void testIfArgIf() { + Parser parser = new Parser( +""" +int a=1; +if( 1==1 ) + a=2; +else + a=3; +int b=4; +if( arg==2 ) + b=a; +else + b=5; +return b;""", TypeInteger.BOT); + StopNode stop = parser.parse(false); + assertEquals("return Phi(Region28,2,5);", stop.toString()); + } + + @Test + public void testMerge3With2() { + Parser parser = new Parser( +""" +int a=1; +if( arg==1 ) + if( arg==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +""", TypeInteger.constant(2)); + StopNode stop = parser.parse(); + assertEquals("return 5;", stop.toString()); + } + + @Test + public void testMerge3With1() { + Parser parser = new Parser( +""" +int a=1; +if( arg==1 ) + if( arg==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +""", TypeInteger.constant(1)); + StopNode stop = parser.parse(false); + assertEquals("return 3;", stop.toString()); + } + + @Test + public void testMerge3Peephole() { + Parser parser = new Parser( +""" +int a=1; +if( arg==1 ) + if( 1==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +""", TypeInteger.BOT); + StopNode stop = parser.parse(false); + assertEquals("return Phi(Region36,3,Phi(Region34,4,5));", stop.toString()); + } + + @Test + public void testMerge3Peephole1() { + Parser parser = new Parser( +""" +int a=1; +if( arg==1 ) + if( 1==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +""", TypeInteger.constant(1)); + StopNode stop = parser.parse(false); + assertEquals("return 3;", stop.toString()); + } + + @Test + public void testMerge3Peephole3() { + Parser parser = new Parser( +""" +int a=1; +if( arg==1 ) + if( 1==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +""", TypeInteger.constant(3)); + StopNode stop = parser.parse(false); + assertEquals("return 4;", stop.toString()); + } + + @Test + public void testDemo1NonConst() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; +"""); + StopNode ret = parser.parse(false); + assertEquals("return Phi(Region22,4,1);", ret.toString()); + } + + + @Test + public void testDemo1True() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; +""", TypeInteger.constant(1)); + StopNode ret = parser.parse(false); + assertEquals("return 4;", ret.toString()); + } + + @Test + public void testDemo1False() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +if( arg ) { + a = 2; + if( arg ) { b = 2; } + else b = 3; +} +return a+b; +""", TypeInteger.constant(0)); + StopNode ret = parser.parse(false); + assertEquals("return 1;", ret.toString()); + } + + @Test + public void testDemo2NonConst() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; +"""); + StopNode ret = parser.parse(false); + assertEquals("return (Phi(Region33,Phi(Region22,2,3),0)+Phi(Region33,3,1));", ret.toString()); + } + + + @Test + public void testDemo2True() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; +""", TypeInteger.constant(1)); + StopNode ret = parser.parse(false); + assertEquals("return 6;", ret.toString()); + } + + @Test + public void testDemo2arg2() { + Parser parser = new Parser(""" +int a = 0; +int b = 1; +int c = 0; +if( arg ) { + a = 1; + if( arg==2 ) { c=2; } else { c=3; } + if( arg ) { b = 2; } + else b = 3; +} +return a+b+c; +""", TypeInteger.constant(2)); + StopNode ret = parser.parse(false); + assertEquals("return 5;", ret.toString()); + } + +} |