From b50645a6b0ecdd9b41f947c172795c41d952874b Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 11 Nov 2023 23:17:22 +0000 Subject: Chapter 6: Peepholes for If MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Dibyendu Majumdar Co-authored-by: Thalia Archibald Co-authored-by: Yichen Yan Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: Claude Opus 5 Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Tamas Hadhazy Co-authored-by: RobertObkircher Co-authored-by: Robert Obkircher --- src/main/java/com/seaofnodes/simple/Parser.java | 3 +- .../java/com/seaofnodes/simple/node/AddNode.java | 67 +++-- .../java/com/seaofnodes/simple/node/BoolNode.java | 7 + .../java/com/seaofnodes/simple/node/IfNode.java | 20 +- .../java/com/seaofnodes/simple/node/MulNode.java | 6 + src/main/java/com/seaofnodes/simple/node/Node.java | 47 +++- .../java/com/seaofnodes/simple/node/PhiNode.java | 27 +- .../java/com/seaofnodes/simple/node/ProjNode.java | 2 + .../com/seaofnodes/simple/node/RegionNode.java | 49 +++- .../com/seaofnodes/simple/node/ReturnNode.java | 6 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 4 +- .../java/com/seaofnodes/simple/node/StartNode.java | 6 + .../java/com/seaofnodes/simple/node/StopNode.java | 5 + .../simple/print/SimpleGraphAdapter.java | 2 +- .../simple/print/SimpleGraphObserver.java | 2 +- src/main/java/com/seaofnodes/simple/type/Type.java | 37 ++- .../com/seaofnodes/simple/type/TypeInteger.java | 2 +- .../java/com/seaofnodes/simple/type/TypeTuple.java | 8 +- .../java/com/seaofnodes/simple/Chapter06Test.java | 294 +++++++++++++++++++++ 19 files changed, 548 insertions(+), 46 deletions(-) create mode 100644 src/test/java/com/seaofnodes/simple/Chapter06Test.java (limited to 'src') diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 359d0175..b9fbf26f 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -161,6 +161,7 @@ public class Parser { IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole(); // Setup projection nodes Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); + ifNode.unkeep(); Node ifF = new ProjNode(ifNode, 1, "False").peephole(); // In if true branch, the ifT proj node becomes the ctrl // But first clone the scope and set it as current @@ -204,7 +205,7 @@ public class Parser { private Node parseReturn() { var expr = require(parseExpression(), ";"); Node ret = STOP.addReturn(new ReturnNode(ctrl(), expr).peephole()); - ctrl(null); // Kill control + ctrl(new ConstantNode(Type.XCONTROL).peephole()); // Kill control return ret; } diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 367cb2c0..22c36746 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -57,7 +57,8 @@ public class AddNode extends Node { // 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 spine_cmp(lhs,rhs) ? swap12() : null; + // Rotate; look for (add (phi cons) con/(phi cons)) + return spine_cmp(lhs,rhs) ? swap12() : phiCon(this,true); // Now we only see (add add non) @@ -66,23 +67,12 @@ public class AddNode extends Node { if( lhs.in(2)._type.isConstant() && t2.isConstant() ) return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); - if( lhs.in(2) instanceof PhiNode phi && phi.allCons() && - // 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 an endless push- - // up push-down peephole cycle because the constants all fold first. - (t2.isConstant() || (rhs instanceof PhiNode && phi.in(0) == rhs.in(0) && rhs.allCons()) ) ) { - 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 2 ) { + // Only valid to rotate constants if both are same associative ops + if( lhs.getClass() != op.getClass() ) return null; + lphi = pcon(lhs.in(2)); // Will rotate with the Phi push + } + if( lphi==null ) return null; + + // RHS is a constant or a Phi of constants + if( !(rhs instanceof ConstantNode con) && pcon(rhs)==null ) + return null; + + // If both are Phis, must be same Region + if( rhs instanceof PhiNode && lphi.in(0) != rhs.in(0) ) + return null; + + // Note that this is the exact reverse of Phi pulling a common op down + // to reduce total op-count. We don't get in an endless push-up + // push-down peephole cycle because the constants all fold first. + Node[] ns = new Node[lphi.nIns()]; + ns[0] = lphi.in(0); + // Push constant up through the phi: x + (phi con0+con0 con1+con1...) + for( int i=1; i { */ public Type _type; + /** + * Immediate dominator tree depth, used to approximate a real IDOM during + * parsing where we do not have the whole program, and also peepholes + * change the CFG incrementally. + *

+ * See {@link ...} + */ + char _idepth; + /** * A private Global Static mutable counter, for unique node id generation. - * To make the compiler multi-threaded, this field will have to move into a TLS. + * To make the compiler multithreaded, this field will have to move into a TLS. * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values. * */ private static int UNIQUE_ID = 1; @@ -110,6 +121,17 @@ public abstract class Node extends BaseNode { return new_def; } + // Remove the numbered input, compressing the inputs in-place. This + // shuffles the order deterministically - which is suitable for Region and + // Phi, but not for every Node. + void delDef(int idx) { + Node old_def = in(idx); + if( old_def != null && // If the old def exists, remove a def->use edge + old_def.delUse(this) ) // If we removed the last use, the old def is now dead + old_def.kill(); // Kill old def + Utils.del(_inputs, idx); + } + /** * Add a new def to an existing Node. Keep the edges correct by * adding the corresponding def->use edge. @@ -317,6 +339,29 @@ public abstract class Node extends BaseNode { return true; } + // Return the immediate dominator of this Node and compute dom tree depth. + Node idom() { return in(0); } + + // Find the lowest common ancestor in the current dominator tree. + Node domLCA(Node rhs) { + if( rhs==null ) return this; + Node lhs = this; + while( lhs != rhs ) { + if( lhs==null || rhs==null ) return null; + int comp = lhs.idepth() - rhs.idepth(); + if( comp >= 0 ) lhs = lhs.idom(); + if( comp <= 0 ) rhs = rhs.idom(); + } + return lhs; + } + + int idepth() { return _idepth!=0 ? _idepth : cacheIDepth(idom().idepth()+1); } + // Zero depth means uncached. Check before narrowing so overflow cannot wrap. + final int cacheIDepth(int depth) { + assert 0 <= depth && depth <= Character.MAX_VALUE : "Dominator depth exceeds 65535"; + return _idepth = (char)depth; + } + // 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. diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index da3917c7..6acb5535 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -24,17 +24,18 @@ public class PhiNode extends Node { @Override public Type compute() { - Type t = in(1)._type; - for( int i=2; i { @Override protected String[] edgeNames(Node n) { diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index a7604165..ea9a705e 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 5's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 6's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture { private Parser _parser; private Node _ret; diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index 6b9130ba..d66fb3e7 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -25,25 +25,50 @@ public class Type { static final byte TBOT = 0; // Bottom (ALL) static final byte TTOP = 1; // Top (ANY) static final byte TCTRL = 2; // Ctrl flow bottom - static final byte TSIMPLE = 3; // End of the Simple Types - static final byte TINT = 4; // All Integers; see TypeInteger - static final byte TTUPLE = 5; // Tuples; finite collections of unrelated Types, kept in parallel + static final byte TXCTRL = 3; // Ctrl flow top (mini-lattice: any-xctrl-ctrl-all) + static final byte TSIMPLE = 4; // End of the Simple Types + static final byte TINT = 5; // All Integers; see TypeInteger + static final byte TTUPLE = 6; // Tuples; finite collections of unrelated Types, kept in parallel public final byte _type; public boolean is_simple() { return _type < TSIMPLE; } - private static final String[] STRS = new String[]{"Bot","Top","Ctrl"}; + private static final String[] STRS = new String[]{"Bot","Top","Ctrl","~Ctrl"}; protected Type(byte type) { _type = type; } public static final Type BOTTOM = new Type( TBOT ); // ALL public static final Type TOP = new Type( TTOP ); // ANY public static final Type CONTROL = new Type( TCTRL ); // Ctrl + public static final Type XCONTROL = new Type( TXCTRL ); // ~Ctrl - public boolean isConstant() { return _type == TTOP; } + public boolean isConstant() { return _type == TTOP || _type == TXCTRL; } public StringBuilder print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;} - public Type meet(Type other) { return BOTTOM; } + public final Type meet(Type t) { + // Shortcut for the self case + if( t == this ) return this; + // Same-type is always safe in the subclasses + if( _type==t._type ) return xmeet(t); + // Reverse; xmeet 2nd arg is never "is_simple" and never equal to "this". + if( is_simple() ) return this.xmeet(t ); + if( t.is_simple() ) return t .xmeet(this); + return BOTTOM; // Mixing 2 unrelated types + } + + // Compute meet right now. Overridden in subclasses. + // Handle cases where 'this.is_simple()' and unequal to 't'. + // Subclassed xmeet calls can assert that '!t.is_simple()'. + protected Type xmeet(Type t) { + assert is_simple(); // Should be overridden in subclass + // ANY meet anything is thing; thing meet ALL is ALL + if( _type==TBOT || t._type==TTOP ) return this; + if( _type==TTOP || t._type==TBOT ) return t; + // 'this' is {TCTRL,TXCTRL} + if( !t.is_simple() ) return BOTTOM; + // 't' is {TCTRL,TXCTRL} + return _type==TCTRL || t._type==TCTRL ? CONTROL : XCONTROL; + } @Override public final String toString() { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index cbaff45f..a9f6ee1c 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -41,7 +41,7 @@ public class TypeInteger extends Type { public long value() { return _con; } @Override - public Type meet(Type other) { + public Type xmeet(Type other) { if( this==other ) return this; if (!(other instanceof TypeInteger i)) return super.meet(other); // BOT wins diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index da701865..39d8f72b 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -10,7 +10,7 @@ public class TypeTuple extends Type { } @Override - public Type meet(Type other) { + public Type xmeet(Type other) { throw new UnsupportedOperationException("Meet on Tuple Type not yet implemented"); } @@ -24,5 +24,9 @@ public class TypeTuple extends Type { return sb; } - public static final TypeTuple IF = new TypeTuple(new Type[]{Type.CONTROL,Type.CONTROL}); + public static final TypeTuple IF_BOTH = new TypeTuple(new Type[]{Type.CONTROL, Type.CONTROL}); + public static final TypeTuple IF_NEITHER = new TypeTuple(new Type[]{Type.XCONTROL,Type.XCONTROL}); + public static final TypeTuple IF_TRUE = new TypeTuple(new Type[]{Type.CONTROL, Type.XCONTROL}); + public static final TypeTuple IF_FALSE = new TypeTuple(new Type[]{Type.XCONTROL,Type.CONTROL}); + } diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java new file mode 100644 index 00000000..00d725bc --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -0,0 +1,294 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Test; + +import static org.junit.Assert.*; + +public class Chapter06Test { + + @Test + public void testPeepholeReturn() { + Parser parser = new Parser( +""" +if( true ) return 2; +return 1; +"""); + StopNode stop = parser.parse(); + assertEquals("return 2;", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testPeepholeRotate() { + Parser parser = new Parser( +""" +int a = 1; +if (arg) + a = 2; +return (arg < a) < 3; +"""); + StopNode stop = parser.parse(); + assertEquals("return ((arg