From e31c37890a86aedfb209cf543baf05b1b60a27d2 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Mon, 29 Apr 2024 00:11:36 +0100 Subject: Ch10update (#75) * Store-after-Store peep * Load-after-Store peephole * Fix graph viz mem edge color bug * Scalar replace loop carried dependence * #67 Dead Not node hanging around - if we add a Not in the upcast then add it to the IterPeeps worklist to ensure it gets cleaned up. We don't see the Not node in the parser hence we cannot do a peep on it there. * #67 Update visuals. Add description of Store-Store and Store-Load peeps. Add examples. * #67 Undo the change that wasn't supposed to be committed! * #67 Update description of the Store-Store and Store-Load peepholes --------- Co-authored-by: Cliff Click --- .../java/com/seaofnodes/simple/node/LoadNode.java | 22 +++++++++++++++ .../java/com/seaofnodes/simple/node/MemOpNode.java | 1 - .../main/java/com/seaofnodes/simple/node/Node.java | 13 ++++++--- .../java/com/seaofnodes/simple/node/PhiNode.java | 3 ++ .../java/com/seaofnodes/simple/node/ScopeNode.java | 2 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 26 +++++++++++++++++ .../java/com/seaofnodes/simple/Chapter10Test.java | 33 +++++++++++++++++++--- 7 files changed, 90 insertions(+), 10 deletions(-) (limited to 'chapter10/src') diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 26e57727..d37c6296 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.Field; @@ -38,6 +39,27 @@ public class LoadNode extends MemOpNode { @Override public Node idealize() { + + // Simple Load-after-Store on same address. + if( mem() instanceof StoreNode st && + ptr() == st.ptr() ) { // Must check same object + assert _field==st._field; // Equiv class aliasing is perfect + return st.val(); + } + + // Push a Load up through a Phi, as long as it collapses on at least one arm. + // BEFORE (2 Sts, 1 Ld): AFTER (1 St): + // if( pred ) ptr.x = e0; val = pred ? e0 + // else ptr.x = e1; : e1; + // val = ptr.x; ptr.x = val; + if( mem() instanceof PhiNode phi && phi.nIns()== 3 && + ((phi.in(1) instanceof StoreNode st1 && ptr()==st1.ptr()) || + (phi.in(2) instanceof StoreNode st2 && ptr()==st2.ptr()) ) ) { + Node ld1 = new LoadNode(_field,phi.in(1),ptr()).peephole(); + Node ld2 = new LoadNode(_field,phi.in(2),ptr()).peephole(); + return new PhiNode(_field._fname,_type,phi.region(),ld1,ld2); + } + return null; } } diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 4376bb0f..dd68120c 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -18,7 +18,6 @@ abstract class MemOpNode extends Node { public Node mem() { return in(1); } public Node ptr() { return in(2); } - public Node val() { return nIns() > 3 ? in(3) : null; } @Override boolean eq(Node n) { diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java index f96b88bd..6a32c092 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/Node.java @@ -178,6 +178,7 @@ public abstract class Node { old_def.kill(); // Kill old def // Set the new_def over the old (killed) edge _inputs.set(idx,new_def); + moveDepsToWorklist(); // Return self for easy flow-coding return new_def; } @@ -264,7 +265,11 @@ public abstract class Node { // Add bogus null use to keep node alive public N keep() { return addUse(null); } // Remove bogus null. - public N unkeep() { delUse(null); return (N)this; } + public N unkeep() { + assert Utils.find(_outputs, null) != -1; + delUse(null); + return (N)this; + } // Replace self with nnn in the graph, making 'this' go dead @@ -459,9 +464,9 @@ public abstract class Node { ArrayList _deps; /** - * Add a node to the list o dependencies. Only add it if its not - * an input or output of this node, that is, it is at least one step - * away. The node being added must benefit from this node being peepholed. + * Add a node to the list of dependencies. Only add it if its not an input + * or output of this node, that is, it is at least one step away. The node + * being added must benefit from this node being peepholed. */ Node addDep( Node dep ) { // Running peepholes during the big assert cannot have side effects diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 6261c446..08fe047c 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.Utils; import java.util.BitSet; @@ -36,6 +37,8 @@ public class PhiNode extends Node { Node region() { return in(0); } @Override public boolean isMultiTail() { return true; } + @Override + public boolean isMem() { return _declaredType instanceof TypeMem; } @Override public Type compute() { diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 44c1bab7..8a50eb56 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -255,7 +255,7 @@ public class ScopeNode extends Node { if( ctrl._type==Type.XCONTROL ) return null; // Invert the If conditional if( invert ) - pred = pred instanceof NotNode not ? not.in(1) : new NotNode(pred).peephole(); + pred = pred instanceof NotNode not ? not.in(1) : IterPeeps.add(new NotNode(pred).peephole()); // Direct use of a value as predicate. This is a zero/null test. if( Utils.find(_inputs, pred) != -1 ) { diff --git a/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 07e4e3f7..8faf6d4b 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -28,6 +28,7 @@ public class StoreNode extends MemOpNode { public String glabel() { return "."+_field._fname+" ="; } @Override public boolean isMem() { return true; } + public Node val() { return in(3); } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { @@ -41,6 +42,31 @@ public class StoreNode extends MemOpNode { @Override public Node idealize() { + + // Simple store-after-store on same address. Should pick up the + // required init-store being stomped by a first user store. + if( mem() instanceof StoreNode st && + ptr()==st.ptr() && // Must check same object + // Must have exactly one use of "this" or you get weird + // non-serializable memory effects in the worse case. + st.checkNoUseBeyond(this) ) { + assert _field==st._field; // Equiv class aliasing is perfect + setDef(1,st.mem()); + return this; + } + return null; } + + // Check that `this` has no uses beyond `that` + private boolean checkNoUseBeyond(Node that) { + if( nOuts()==1 ) return true; + // Add deps on the other uses (can be e.g. ScopeNode mid-parse) so that + // when the other uses go away we can retry. + for( Node use : _outputs ) + if( use != that ) + use.addDep(that); + return false; + } + } diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 6bafe72a..36ad19ae 100644 --- a/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -30,9 +30,9 @@ bar.a = 1; bar.a = 2; return bar.a; """); - StopNode stop = parser.parse(true).iterate(true); + StopNode stop = parser.parse(false).iterate(true); System.out.println(IRPrinter.prettyPrint(stop, 99, true)); - assertEquals("return .a;", stop.toString()); + assertEquals("return 2;", stop.toString()); } @Test @@ -86,8 +86,8 @@ while (arg) { } return bar.a; """); - StopNode stop = parser.parse(true).iterate(true); - assertEquals("return .a;", stop.toString()); + StopNode stop = parser.parse(false).iterate(true); + assertEquals("return Phi(Loop10,0,(Phi_a+2));", stop.toString()); } @Test @@ -189,6 +189,31 @@ v1=new s0; catch( Exception e ) { assertEquals("Redefining name 'v1'", e.getMessage()); } } + @Test + public void testIter() { + // Build and use an iterator + Parser parser = new Parser( +""" +struct Iter { + int x; + int len; +} +Iter i = new Iter; +i.len = arg; +int sum=0; +while( i.x < i.len ) { + sum = sum + i.x; + i.x = i.x + 1; +} +return sum; +"""); + StopNode stop = parser.parse().iterate(true); + assertEquals("return Phi(Loop14,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); + } + + + + @Test public void test1() { Parser parser = new Parser(""" -- cgit v1.2.3