summaryrefslogtreecommitdiff
path: root/chapter19
diff options
context:
space:
mode:
Diffstat (limited to 'chapter19')
-rw-r--r--chapter19/src/main/java/com/seaofnodes/simple/node/PhiNode.java36
-rw-r--r--chapter19/src/test/java/com/seaofnodes/simple/Chapter05Test.java24
-rw-r--r--chapter19/src/test/java/com/seaofnodes/simple/Chapter09Test.java2
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));
}