diff options
Diffstat (limited to 'chapter19')
3 files changed, 53 insertions, 9 deletions
diff --git a/chapter19/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter19/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 6fb315b4..e8a37a4d 100644 --- a/chapter19/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter19/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -74,7 +74,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 merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -105,8 +106,26 @@ public class PhiNode extends Node { return null; } - private boolean same_op() { + // 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 ) return in(i); + return op; + } + + private boolean doubled(Node n) { + return n instanceof ShlNode && + n.in(2).addDep(this)._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); + } + + 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. @@ -124,7 +143,8 @@ public class PhiNode extends Node { for( int i=1; i<nIns(); i++ ) { Node n = in(i); if( region().in(i).addDep(this)._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 && 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 @@ -142,21 +162,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); } PhiNode phi = j==1 && op instanceof MemOpNode mem diff --git a/chapter19/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 09e7f7c7..338b26dc 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; import org.junit.Test; import static org.junit.Assert.*; @@ -197,4 +198,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)); + Node sum = init(new AddNode(i,p)); + PhiNode phi = init(new PhiNode("sum",TypeInteger.BOT,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/chapter19/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter19/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 5672d566..a5620e13 100644 --- a/chapter19/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter19/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -40,7 +40,7 @@ else { return x; """); code.parse().iter(); - 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)); } |
