diff options
Diffstat (limited to 'chapter25/src')
3 files changed, 54 insertions, 10 deletions
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 064852e4..9f800e2f 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -107,7 +107,8 @@ public class PhiNode extends Node { // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). Node down; - if( same_op() && (down=drop_same_op())!=null ) return down; + Node op = factoringOp(); + if( same_op(op) && (down=drop_same_op(op))!=null ) return down; if( nIns()==3 ) { Node merge = matchingGuardMerge(r,1); @@ -165,10 +166,28 @@ public class PhiNode extends Node { return tested!=null && ScopeNode.availableAt(n,r,new java.util.BitSet()) ? n : null; } + // View x<<1 as x+x only while matching mixed Phi arms. Do not + // expand the graph into Adds that would immediately strength-reduce again. + private Node factoringOp() { + Node op = in(1); + if( doubled(op) ) + for( int i=2; i<nIns(); i++ ) + if( in(i) instanceof AddNode add && add._mode==1 ) return in(i); + return op; + } + + private boolean doubled(Node n) { + return n instanceof ShlNode && + addDep(n.in(2))._type instanceof TypeInteger con && con.isConstant() && con.value()==1; + } + + private static Node factoringInput(Node op, Node n, int j) { + return op instanceof AddNode && !(n instanceof AddNode) ? n.in(1) : n.in(j); + } + // Same op on all Phi paths; all ops have only the Phi as a use. // None have a control input. - private boolean same_op() { - Node op = in(1); + private boolean same_op(Node op) { if( op instanceof CFGNode || op instanceof ConstantNode || op instanceof PhiNode || op instanceof ProjNode || op instanceof NewNode || op instanceof ScopeNode || op instanceof MemMergeNode ) return false; // A bulk Phi must split its aliases before factoring precise Stores. @@ -186,7 +205,8 @@ public class PhiNode extends Node { for( int i=1; i<nIns(); i++ ) { Node n = in(i); if( addDep(region().in(i))._type==Type.XCONTROL || - op.getClass()!=n.getClass() || n.nIns()!=op.nIns() || n.in(0)!=null || !op.eq(n) ) return false; + !((op.getClass()==n.getClass() && op.eq(n)) || (op instanceof AddNode add && add._mode==1 && doubled(n))) || + n.nIns()!=op.nIns() || n.in(0)!=null ) return false; if( n instanceof MemOpNode mem && !mem.canDrop((MemOpNode)op,this) ) return false; // Moving a Store must remove the old effect, not duplicate it. // Allow one shared arm: the other arms disappear into the single @@ -204,21 +224,21 @@ public class PhiNode extends Node { return true; } - private Node drop_same_op() { - Node op = in(1), cp = op.copyEmpty(); + private Node drop_same_op(Node op) { + Node cp = op.copyEmpty(); cp._type = null; cp.addDef(null); for( int j=1; j<op.nIns(); j++ ) { - Node x = op.in(j); + Node x = factoringInput(op,in(1),j); boolean different = false; for( int i=2; i<nIns(); i++ ) - if( in(i).in(j)!=x ) different=true; + if( factoringInput(op,in(i),j)!=x ) different=true; if( different ) { Node[] ins = new Node[nIns()]; ins[0] = region(); Type t = Type.TOP; for( int i=1; i<nIns(); i++ ) { - ins[i] = in(i).in(j); + ins[i] = factoringInput(op,in(i),j); t = t.meet(ins[i]._type); } // Not accepts both pointers and integers, but a Phi cannot mix them. diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter05Test.java index b234209f..460db1b1 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; import org.junit.Test; import static org.junit.Assert.*; @@ -198,4 +199,27 @@ return a; catch( RuntimeException e ) { assertEquals("Undefined name 'ififif'",e.getMessage()); } } + private static <N extends Node> N init(N n) { n._type=n.compute(); return n; } + + @Test public void testDoublingBeforeAndAfterStrengthReduction() { + for( boolean reduced : new boolean[]{false,true} ) + for( boolean reverse : new boolean[]{false,true} ) { + CodeGen code = new CodeGen(""); + Node ctrl = init(new CProjNode(code._start,0,"Ctrl")); + RegionNode region = init(new RegionNode(null,null,ctrl,ctrl)); + Node p = init(new ConstantNode(TypeInteger.BOT)); + Node i = init(new MinusNode(p)); + Node twice = reduced ? init(new ShlNode(null,p,init(new ConstantNode(TypeInteger.constant(1))))) : init(new AddNode(p,p,(byte)1)); + Node sum = init(new AddNode(i,p,(byte)1)); + PhiNode phi = init(new PhiNode("sum",region,reverse ? sum : twice,reverse ? twice : sum)); + phi.keep(); + Node factored = phi.idealize(); + assertTrue(factored instanceof AddNode); + assertSame(p,factored.in(2)); + assertTrue(factored.in(1) instanceof PhiNode); + assertSame(reverse ? i : p,factored.in(1).in(1)); + assertSame(reverse ? p : i,factored.in(1).in(2)); + phi.unkeep(); + } + } } diff --git a/chapter25/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter25/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 50410618..6e167d9e 100644 --- a/chapter25/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter25/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -41,7 +41,7 @@ else { return x; """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("return Phi(Region,(arg<<1),(Shl+1));", code.print()); + assertEquals("return (Phi(Region,arg,1)+Phi(Region,arg,(arg<<1)));", code.print()); Assert.assertEquals( "2", Eval2.eval(code, 1)); Assert.assertEquals("23", Eval2.eval(code, 11)); } |
