diff options
4 files changed, 135 insertions, 30 deletions
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 a726a22d..7cb0f822 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -36,42 +36,92 @@ public class AddNode extends Node { Type t1 = lhs._type; Type t2 = rhs._type; + // Already handled by peephole constant folding + assert !(t1.isConstant() && t2.isConstant()); + // Add of 0. We do not check for (0+x) because this will already // canonicalize to (x+0) - if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==0 ) + if( t2 instanceof TypeInteger i && i.value()==0 ) return lhs; - - // Move constants to RHS: con+arg becomes arg+con - if ( t1.isConstant() && !t2.isConstant() ) { - Node tmp = in(1); // Swap inputs without letting either input go dead during the swap - _inputs.set(1,in(2)); - _inputs.set(2,tmp); - return this; - } - + + // Add of same to a multiply by 2 + if( lhs==rhs ) + return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole()); + // Goal: a left-spine set of adds, with constants on the rhs (which then fold). - // Do we have (x + con1) + con2 ? - // Rotate to x +(con1 + con2) - // The constants will fold on the next peephole. - if (t2.isConstant() && lhs instanceof AddNode && lhs.in(2)._type.isConstant() ) + // Move non-adds to RHS + if( !(lhs instanceof AddNode) && rhs instanceof AddNode ) + return swap12(); + + // Now we might see (add add non) or (add non non) or (add add add) but never (add non add) + + // Do we have x + (y + z) ? + // Swap to (x + y) + z + // Rotate (add add add) to remove the add on RHS + if( rhs instanceof AddNode add ) + return new AddNode(new AddNode(lhs,add.in(1)).peephole(), add.in(2)); + + // 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; + + // Now we only see (add add non) + + // Do we have (x + con1) + con2? + // Replace with (x + (con1+con2) which then fold the constants + if( lhs.in(2)._type.isConstant() && t2.isConstant() ) return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); - // Do we have x + (y + non_add) ? - // Swap to (x + y) + non_add - if (rhs instanceof AddNode add && !(add.in(2) instanceof AddNode) ) - return new AddNode(new AddNode(lhs,add.in(1)).peephole(), add.in(2)); + if( lhs.in(2) instanceof PhiNode phi && phi.all_cons() && + // 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 a endless push- + // up push-down peephole cycle because the constants all fold first. + (t2.isConstant() || (rhs instanceof PhiNode && rhs.all_cons()) ) ) { + 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(); + return new AddNode(lhs.in(1),new PhiNode(ns).peephole()); + } - // Do we have (x + y) + x - // Swap to (x + x) + y - if (lhs instanceof AddNode add && add.in(1)==rhs ) - return new AddNode(new AddNode(rhs,rhs).peephole(), add.in(2)); + // Now we sort along the spline via rotates, to gather similar things together. - // Add of same to a multiply by 2 - if( lhs==rhs ) - return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole()); + // Do we rotate (x + y) + z + // into (x + z) + y ? + if( spline_cmp(lhs.in(2),rhs) ) + return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2)); return 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. + // 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.all_cons() ) return false; + if( hi instanceof PhiNode && hi.all_cons() ) return true ; + + if( lo instanceof MulNode ) throw new RuntimeException("TODO"); + if( hi instanceof MulNode ) throw new RuntimeException("TODO"); + + 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/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java index 49426c26..dc4d7a33 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/Node.java @@ -215,7 +215,6 @@ public abstract class Node { return new_def; } - // Breaks the edge invariants, used temporarily private void addUse(Node n) { _outputs.add(n); } @@ -258,7 +257,7 @@ public abstract class Node { // Mostly used for asserts and printing. boolean isDead() { return isUnused() && nIns()==0 && _type==null; } - + /** * This function needs to be * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a> @@ -324,6 +323,32 @@ public abstract class Node { */ public abstract Node idealize(); + + // ----------------------- + // Peephole utilities + + // Swap inputs without letting either input go dead during the swap. + Node swap12() { + Node tmp = in(1); + _inputs.set(1,in(2)); + _inputs.set(2,tmp); + return this; + } + + // does this node contain all constants? + // Ignores in(0), as is usually control. + boolean all_cons() { + 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 new RuntimeException("TODO"); } + /** * 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/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 6fef99f3..4334ac10 100644 --- a/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter05/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -34,7 +34,37 @@ public class PhiNode extends Node { // Remove a "junk" Phi: Phi(x,x) is just x if( in(1)==in(2) ) 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(lhss).peephole(); + Node phi_rhs = new PhiNode(rhss).peephole(); + //if( phi_lhs instanceof PhiNode && phi_rhs instanceof PhiNode ) { + // phi_lhs.kill(); + // phi_rhs.kill(); + // return null; // No progress, no profit + //} + 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; + } } diff --git a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java index ea65900f..7089e000 100644 --- a/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter05/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -53,14 +53,14 @@ return c; public void testChapter5IfMergeB() { Parser parser = new Parser("int a=arg+1; int b=0; if( arg==1 ) b=a; else b=a+1; return a+b; #showGraph;"); StopNode ret = parser.parse(); - assertEquals("return ((arg+1)+Phi(Region20,(arg+1),(arg+2)));", ret.toString()); + assertEquals("return ((arg*2)+Phi(Region20,2,3));", ret.toString()); } @Test public void testChapter5IfMerge2() { Parser parser = new Parser("int a=arg+1; int b=arg+2; if( arg==1 ) b=b+a; else a=b+1; return a+b; #showGraph;"); StopNode ret = parser.parse(); - assertEquals("return (Phi(Region31,(arg+1),(arg+3))+Phi(Region31,((arg*2)+3),(arg+2)));", ret.toString()); + assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region31,4,5));", ret.toString()); } @Test |