diff options
Diffstat (limited to 'src/main/java/com/seaofnodes/simple/node')
12 files changed, 271 insertions, 5 deletions
diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 5720aca4..081c9276 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -72,6 +72,24 @@ 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()); + } + // Now we sort along the spline via rotates, to gather similar things together. // Do we rotate (x + y) + z @@ -84,15 +102,22 @@ public class AddNode extends Node { // 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 others. + // Generally constants always go right, then Phi-of-constants, then muls, then others. // Ties with in a category sort by node ID. // TRUE if swapping hi and lo. static boolean spline_cmp( Node hi, Node lo ) { if( lo._type.isConstant() ) return false; if( hi._type.isConstant() ) return true ; + if( lo instanceof PhiNode && lo.allCons() ) return false; + if( hi instanceof PhiNode && hi.allCons() ) return true ; + + if( lo instanceof PhiNode && !(hi instanceof PhiNode) ) return true; + if( hi instanceof PhiNode && !(lo instanceof PhiNode) ) return false; + // Same category of "others" return lo._nid > hi._nid; } + @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 05495790..7a4a087e 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -46,7 +46,7 @@ abstract public class BoolNode extends Node { return null; } - public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } } - public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } } - public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } } + public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQ(lhs,rhs); } } + public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } Node copy(Node lhs, Node rhs) { return new LT(lhs,rhs); } } + public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LE(lhs,rhs); } } } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index 3b3a4436..519a8c8a 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -37,4 +37,6 @@ public class DivNode extends Node { return in(1); return null; } + + @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); } } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java new file mode 100644 index 00000000..6124b893 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -0,0 +1,36 @@ +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 { + + public IfNode(Node ctrl, Node pred) { + super(ctrl, pred); + } + + @Override + public String label() { return "If"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + sb.append("if( "); + return in(1)._print0(sb).append(" )"); + } + + @Override public boolean isCFG() { return true; } + + public Node ctrl() { return in(0); } + public Node pred() { return in(1); } + + @Override + public Type compute() { + return TypeTuple.IF; + } + + @Override + public Node idealize() { + return null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 36d5eb3e..2dbdd695 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -46,4 +46,5 @@ public class MulNode extends Node { 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 9fa0a95a..5412108b 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -349,6 +349,20 @@ public abstract class Node { return this; } + // does this node contain all constants? + // Ignores in(0), as is usually control. + boolean allCons() { + for( int i=1; i<nIns(); i++ ) + if( !(in(i)._type.isConstant()) ) + return false; + return true; + } + + // 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 Utils.TODO("Binary ops need to implement copy"); } + /** * Used to allow repeating tests in the same JVM. This just resets the * Node unique id generator, and is done as part of making a new Parser. diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java new file mode 100644 index 00000000..374e1183 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -0,0 +1,73 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; + +public class PhiNode extends Node { + + final String _label; + + public PhiNode(String label, Node... inputs) { super(inputs); _label = label; } + + @Override public String label() { return "Phi_"+_label; } + + @Override public String glabel() { return "φ_"+_label; } + + @Override + StringBuilder _print1(StringBuilder sb) { + sb.append("Phi("); + for( Node in : _inputs ) + in._print0(sb).append(","); + sb.setLength(sb.length()-1); + sb.append(")"); + return sb; + } + + Node region() { return in(0); } + + @Override + public Type compute() { + return Type.BOTTOM; + } + + @Override + public Node idealize() { + // Remove a "junk" Phi: Phi(x,x) is just x + if( same_inputs() ) + return in(1); + + // Pull "down" a common data op. One less op in the world. One more + // Phi, but Phis do not make code. + // Phi(op(A,B),op(Q,R),op(X,Y)) becomes + // op(Phi(A,Q,X), Phi(B,R,Y)). + Node op = in(1); + if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) { + Node[] lhss = new Node[nIns()]; + Node[] rhss = new Node[nIns()]; + lhss[0] = rhss[0] = in(0); // Set Region + for( int i=1; i<nIns(); i++ ) { + lhss[i] = in(i).in(1); + rhss[i] = in(i).in(2); + } + Node phi_lhs = new PhiNode(_label,lhss).peephole(); + Node phi_rhs = new PhiNode(_label,rhss).peephole(); + return op.copy(phi_lhs,phi_rhs); + } + + return null; + } + + private boolean same_op() { + for( int i=2; i<nIns(); i++ ) + if( in(1).getClass() != in(i).getClass() ) + return false; + return true; + } + + private boolean same_inputs() { + for( int i=2; i<nIns(); i++ ) + if( in(1) != in(i) ) + return false; + return true; + } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 2f49fe91..2826d192 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -23,7 +23,7 @@ public class ProjNode extends Node { @Override StringBuilder _print1(StringBuilder sb) { return sb.append(_label); } - @Override public boolean isCFG() { return _idx==0; } + @Override public boolean isCFG() { return _idx==0 || ctrl() instanceof IfNode; } public MultiNode ctrl() { return (MultiNode)in(0); } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java new file mode 100644 index 00000000..5d520d65 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -0,0 +1,27 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; + +public class RegionNode extends Node { + public RegionNode(Node... inputs) { super(inputs); } + + @Override + public String label() { return "Region"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + return sb.append(label()).append(_nid); + } + + @Override public boolean isCFG() { return true; } + + @Override + public Type compute() { + return Type.CONTROL; + } + + @Override + public Node idealize() { + 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 8ffeac64..32045fbc 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -131,4 +131,45 @@ public class ScopeNode extends Node { */ public Node ctrl(Node n) { return setDef(0,n); } + /** + * Duplicate a ScopeNode; including all levels, up to Nodes. So this is + * neither shallow (would dup the Scope but not the internal HashMap + * tables), nor deep (would dup the Scope, the HashMap tables, but then + * also the program Nodes). + * <p> + * The new Scope is a full-fledged Node with proper use<->def edges. + */ + public ScopeNode dup() { + ScopeNode dup = new ScopeNode(); + // Our goals are: + // 1) duplicate the name bindings of the ScopeNode across all stack levels + // 2) Make the new ScopeNode a user of all the nodes bound + // 3) Ensure that the order of defs is the same to allow easy merging + for( HashMap<String,Integer> syms : _scopes ) + dup._scopes.push(new HashMap<>(syms)); + dup.addDef(ctrl()); // Control input is just copied + for( int i=1; i<nIns(); i++ ) + dup.addDef(in(i)); + return dup; + } + + /** + * Merges the names whose node bindings differ, by creating Phi node for such names + * The names could occur at all stack levels, but a given name can only differ in the + * innermost stack level where the name is bound. + * + * @param that The ScopeNode to be merged into this + * @return A new node representing the merge point + */ + public Node mergeScopes(ScopeNode that) { + RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).peephole()); + 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; + } + } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java new file mode 100644 index 00000000..a30256f9 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -0,0 +1,46 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; + +public class StopNode extends Node { + public StopNode(Node... inputs) { + super(inputs); + } + + @Override + public String label() { + return "Stop"; + } + + @Override + StringBuilder _print1(StringBuilder sb) { + if( ret()!=null ) return ret()._print0(sb); + sb.append("Stop[ "); + for( Node ret : _inputs ) + ret._print0(sb).append(" "); + return sb.append("]"); + } + + @Override public boolean isCFG() { return true; } + + // If a single Return, return it. + // Otherwise, null because ambiguous. + public ReturnNode ret() { + return nIns()==1 ? (ReturnNode)in(0) : null; + } + + @Override + public Type compute() { + return Type.BOTTOM; + } + + @Override + public Node idealize() { + return null; + } + + public Node addReturn(Node node) { + return addDef(node); + } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index 58d757ea..475b3790 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -37,4 +37,5 @@ public class SubNode extends Node { return null; } + @Override Node copy(Node lhs, Node rhs) { return new SubNode(lhs,rhs); } } |