diff options
Diffstat (limited to 'src/main/java/com/seaofnodes/simple/node')
13 files changed, 341 insertions, 34 deletions
diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 7c1968c5..5720aca4 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -23,14 +23,76 @@ public class AddNode extends Node { in(2)._type instanceof TypeInteger i1 ) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()+i1.value()); + return i0.meet(i1); } return Type.BOTTOM; } @Override public Node idealize () { - // TODO: add of 0, and many other peepholes added in Chaper04 + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Already handled by peephole constant folding + assert !(t1.isConstant() && t2.isConstant()); + + // Add of 0. We do not check for (0+x) because this will already + // canonicalize to (x+0) + if( t2 instanceof TypeInteger i && i.value()==0 ) + return lhs; + + // Add of same to a multiply by 2 + if( lhs==rhs ) + return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole()); + + // Goal: a left-spine set of adds, with constants on the rhs (which then fold). + + // Move non-adds to RHS + if( !(lhs instanceof AddNode) && rhs instanceof AddNode ) + return swap12(); + + // Now we might see (add add non) or (add non non) or (add add add) but never (add non add) + + // Do we have x + (y + z) ? + // Swap to (x + y) + z + // Rotate (add add add) to remove the add on RHS + if( rhs instanceof AddNode add ) + return new AddNode(new AddNode(lhs,add.in(1)).peephole(), add.in(2)); + + // 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 spline_cmp(lhs,rhs) ? swap12() : null; + + // Now we only see (add add non) + + // Do we have (x + con1) + con2? + // Replace with (x + (con1+con2) which then fold the constants + if( lhs.in(2)._type.isConstant() && t2.isConstant() ) + return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); + + // Now we sort along the spline via rotates, to gather similar things together. + + // Do we rotate (x + y) + z + // into (x + z) + y ? + if( spline_cmp(lhs.in(2),rhs) ) + return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2)); + return null; } + // Compare two off-spline nodes and decide what order they should be in. + // Do we rotate ((x + hi) + lo) into ((x + lo) + hi) ? + // Generally constants always go right, then others. + // Ties with in a category sort by node ID. + // TRUE if swapping hi and lo. + static boolean spline_cmp( Node hi, Node lo ) { + if( lo._type.isConstant() ) return false; + if( hi._type.isConstant() ) return true ; + + // Same category of "others" + return lo._nid > hi._nid; + } + } diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java new file mode 100644 index 00000000..05495790 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -0,0 +1,52 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + +abstract public class BoolNode extends Node { + + public BoolNode(Node lhs, Node rhs) { + super(null, lhs, rhs); + } + + abstract String op(); // String opcode name + + @Override + public String label() { return getClass().getSimpleName(); } + + @Override + public String glabel() { return op(); } + + @Override + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(")); + in(2)._print0(sb.append(op())); + return sb.append(")"); + } + + @Override + public Type compute() { + if( in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1 ) { + if (i0.isConstant() && i1.isConstant()) + return TypeInteger.constant(doOp(i0.value(), i1.value()) ? 1 : 0); + return i0.meet(i1); + } + return Type.BOTTOM; + } + + abstract boolean doOp(long lhs, long rhs); + + @Override + public Node idealize() { + // Compare of same + if( in(1)==in(2) ) + return new ConstantNode(TypeInteger.constant(doOp(3,3)?1:0)); + + return null; + } + + public static class EQ extends BoolNode { public EQ(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "=="; } boolean doOp(long lhs, long rhs) { return lhs == rhs; } } + public static class LT extends BoolNode { public LT(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<" ; } boolean doOp(long lhs, long rhs) { return lhs < rhs; } } + public static class LE extends BoolNode { public LE(Node lhs, Node rhs) { super(lhs,rhs); } String op() { return "<="; } boolean doOp(long lhs, long rhs) { return lhs <= rhs; } } +} diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index e4d7f412..1086037d 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -23,7 +23,7 @@ public class ConstantNode extends Node { } @Override - public String label() { return "#"+_con; } + public String label() { return ""+_con; } @Override public String uniqueName() { return "Con_" + _nid; } @@ -38,5 +38,4 @@ public class ConstantNode extends Node { @Override public Node idealize() { return null; } - } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index e3c3616a..3b3a4436 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -25,10 +25,16 @@ public class DivNode extends Node { return i1.value() == 0 ? TypeInteger.ZERO : TypeInteger.constant(i0.value()/i1.value()); + return i0.meet(i1); } return Type.BOTTOM; } @Override - public Node idealize() { return null; } + public Node idealize() { + // Div of 1. + if( in(2)._type.isConstant() && in(2)._type instanceof TypeInteger i && i.value()==1 ) + return in(1); + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 26c28281..36d5eb3e 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -23,10 +23,27 @@ public class MulNode extends Node { in(2)._type instanceof TypeInteger i1) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()*i1.value()); + return i0.meet(i1); } return Type.BOTTOM; } @Override - public Node idealize() { return null; } + public Node idealize() { + Node lhs = in(1); + Node rhs = in(2); + Type t1 = lhs._type; + Type t2 = rhs._type; + + // Mul of 1. We do not check for (1*x) because this will already + // canonicalize to (x*1) + if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==1 ) + return lhs; + + // Move constants to RHS: con*arg becomes arg*con + if ( t1.isConstant() && !t2.isConstant() ) + return swap12(); + + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/src/main/java/com/seaofnodes/simple/node/MultiNode.java new file mode 100644 index 00000000..7ba1aa19 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -0,0 +1,7 @@ +package com.seaofnodes.simple.node; + +public abstract class MultiNode extends Node { + + public MultiNode(Node... inputs) { super(inputs); } + +} diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 82357f9b..9fa0a95a 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -81,14 +81,7 @@ public abstract class Node { // line (because this is what a debugger typically displays by default) and // has to be robust with broken graph/nodes. @Override - public final String toString() { - // TODO: The print evolves in later chapters. For now, a simple - // recursive print does well. Later with control flow and later still - // with loops, we need some serious algorithm work to get a decent - // print. So you should consider the "print" to always be a work-in- - // progress as we march through the chapters. - return print(); - } + public final String toString() { return print(); } // This is a *deep* print. This version will fail on cycles, which we will // correct later when we can parse programs with loops. We print with a @@ -125,8 +118,6 @@ public abstract class Node { public boolean isCFG() { return false; } - - /** * Change a <em>def</em> into a Node. Keeps the edges correct, by removing * the corresponding <em>use->def</em> edge. This may make the original @@ -184,11 +175,11 @@ public abstract class Node { // Error is 'use' does not exist; ok for 'use' to be null. protected boolean delUse( Node use ) { Utils.del(_outputs, Utils.find(_outputs, use)); - return _outputs.size() == 0; + return _outputs.isEmpty(); } // Shortcut for "popping" n nodes. A "pop" is basically a - // set_def(last,null) followed by lowering the nIns() count. + // setDef(last,null) followed by lowering the nIns() count. void popN(int n) { for( int i=0; i<n; i++ ) { Node old_def = _inputs.removeLast(); @@ -212,6 +203,15 @@ public abstract class Node { // Mostly used for asserts and printing. boolean isDead() { return isUnused() && nIns()==0 && _type==null; } + + // Shortcuts to stop DCE mid-parse + // Add bogus null use to keep node alive + public <N extends Node> N keep() { return addUse(null); } + // Remove bogus null. + public <N extends Node> N unkeep() { delUse(null); return (N)this; } + // ------------------------------------------------------------------------ + // Graph-based optimizations + /** * We allow disabling peephole opt so that we can observe the * full graph, vs the optimized graph. @@ -226,7 +226,11 @@ public abstract class Node { * <li>in a future chapter we will look for a * <a href="https://en.wikipedia.org/wiki/Common_subexpression_elimination">Common Subexpression</a> * to eliminate.</li> - * <li>we ask the Node for a better replacement (again, none enabled in this chapter)</li> + * <li>we ask the Node for a better replacement. The "better replacement" + * is things like {@code (1+2)} becomes {@code 3} and {@code (1+(x+2))} becomes + * {@code (x+(1+2))}. By canonicalizing expressions we fold common addressing + * math constants, remove algebraic identities and generally simplify the + * code. </li> * </ul> */ public final Node peephole( ) { @@ -237,20 +241,37 @@ public abstract class Node { return this; // Peephole optimizations turned off // Replace constant computations from non-constants with a constant node - if (!(this instanceof ConstantNode) && type.isConstant()) { - kill(); // Kill `this` because replacing with a Constant - return new ConstantNode(type).peephole(); - } + if (!(this instanceof ConstantNode) && type.isConstant()) + return deadCodeElim(new ConstantNode(type).peephole()); // Future chapter: Global Value Numbering goes here // Ask each node for a better replacement Node n = idealize(); - if( n != null ) return n; + if( n != null ) // Something changed + // Recursively optimize + return deadCodeElim(n.peephole()); return this; // No progress } + // m is the new Node, self is the old. + // Return 'm', which may have zero uses but is alive nonetheless. + // If self has zero uses (and is not 'm'), {@link #kill} self. + private Node deadCodeElim(Node m) { + // If self is going dead and not being returned here (Nodes returned + // from peephole commonly have no uses (yet)), then kill self. + if( m != this && isUnused() ) { + // Killing self - and since self recursively kills self's inputs we + // might end up killing 'm', which we are returning as a live Node. + // So we add a bogus extra null output edge to stop kill(). + m.keep(); // Keep m alive + kill(); // Kill self because replacing with 'm' + m.unkeep(); // Okay to peephole m + } + return m; + } + /** * This function needs to be * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a> @@ -269,8 +290,65 @@ public abstract class Node { */ public abstract Type compute(); + /** + * This function rewrites the current Node into a more "idealized" form. + * This is the bulk of our peephole rewrite rules, and we use this to + * e.g. turn arbitrary collections of adds and multiplies with mixed + * constants into a normal form that's easy for hardware to implement. + * Example: An array addressing expression: + * <pre> ary[idx+1]</pre> + * might turn into Sea-of-Nodes IR: + * <pre> (ary+12)+((idx+1) * 4)</pre> + * This expression can then be idealized into: + * <pre> ary + ((idx*4) + (12 + (1*4)))</pre> + * And more folding: + * <pre> ary + ((idx<<2) + 16)</pre> + * And during code-gen: + * <pre> MOV4 Rary,Ridx,16 // or some such hardware-specific notation </pre> + * <p> + * {@link #idealize} has a very specific calling convention: + * <ul> + * <li>If NO change is made, return {@code null} + * <li>If ANY change is made, return not-null; this can be {@code this} + * <li>The returned Node does NOT call {@link #peephole} on itself; the {@link #peephole} call will recursively peephole it. + * <li>Any NEW nodes that are not directly returned DO call {@link #peephole}. + * </ul> + * <p> + * Examples: + * <table border="3"> + * <tr><th> before </th><th> after </th><th>return </th><th>comment </th></tr> + * <tr><td>{@code (x+5) }</td><td>{@code (x+5) }</td><td>{@code null }</td><td>No change</td></tr> + * <tr><td>{@code (5+x) }</td><td>{@code (x+5) }</td><td>{@code this }</td><td>Swapped arguments</td></tr> + * <tr><td>{@code ((x+1)+2)}</td><td>{@code (x+(1+2))}</td><td>{@code (x+_) }</td><td>Returns 2 new Nodes</td></tr> + * </table> + * + * The last entry deserves more discussion. The new Node {@code (1+2)} + * created in {@link #idealize} calls {@link #peephole} (which then folds + * into a constant). The other new Node {@code (x+3)} does not call + * peephole, because it is returned and peephole itself will recursively + * call peephole. + * <p> + * Since idealize calls peephole and peephole calls idealize, you must be + * careful that all idealizations are <em>monotonic</em>: all transforms remove + * some feature, so that the set of available transforms always shrinks. + * If you don't, you risk an infinite peephole loop! + * + * @return Either a new or changed node, or null for no changes. + */ public abstract Node idealize(); + + // ------------------------------------------------------------------------ + // Peephole utilities + + // Swap inputs without letting either input go dead during the swap. + Node swap12() { + Node tmp = in(1); + _inputs.set(1,in(2)); + _inputs.set(2,tmp); + return this; + } + /** * Used to allow repeating tests in the same JVM. This just resets the * Node unique id generator, and is done as part of making a new Parser. diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java new file mode 100644 index 00000000..e3683646 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -0,0 +1,28 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; + +public class NotNode extends Node { + public NotNode(Node in) { super(null, in); } + + @Override public String label() { return "Not"; } + + @Override public String glabel() { return "!"; } + + @Override + StringBuilder _print1(StringBuilder sb) { + in(1)._print0(sb.append("(!")); + return sb.append(")"); + } + + @Override + public Type compute() { + if( in(1)._type instanceof TypeInteger i0 ) + return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0; + return Type.BOTTOM; + } + + @Override + public Node idealize() { return null; } +} diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java new file mode 100644 index 00000000..2f49fe91 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -0,0 +1,40 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeTuple; + +public class ProjNode extends Node { + + // Which slice of the incoming multi-part value + public final int _idx; + + // Debugging label + public final String _label; + + public ProjNode(MultiNode ctrl, int idx, String label) { + super(ctrl); + _idx = idx; + _label = label; + } + + @Override + public String label() { return _label; } + + @Override + StringBuilder _print1(StringBuilder sb) { return sb.append(_label); } + + @Override public boolean isCFG() { return _idx==0; } + + public MultiNode ctrl() { return (MultiNode)in(0); } + + @Override + public Type compute() { + Type t = ctrl()._type; + return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; + } + + @Override + public Node idealize() { + return null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 7fa470f8..c9d6c9c8 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -32,7 +32,7 @@ public class ReturnNode extends Node { @Override public Type compute() { - return Type.BOTTOM; + return new TypeTuple(ctrl()._type,expr()._type); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 379ef033..8ffeac64 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -7,12 +7,18 @@ import java.util.*; /** * The Scope node is purely a parser helper - it tracks names to nodes with a * stack of scopes. - * @see <a href="file:../../../../../../../../chapter03/README.md">chapter03/README.md</a> */ public class ScopeNode extends Node { /** - * A Stack of symbol tables; a symbol table is a map from names to node indices. + * The control is a name that binds to the currently active control + * node in the graph + */ + public static final String CTRL = "$ctrl"; + public static final String ARG0 = "arg"; + + /** + * Names for every input edge */ public final Stack<HashMap<String, Integer>> _scopes; @@ -49,7 +55,7 @@ public class ScopeNode extends Node { * Recover the names for all variable bindings. * The result is an array of names that is aligned with the * inputs to the Node. - * <p> + * * This is an expensive operation. */ public String[] reverseNames() { @@ -78,21 +84,21 @@ public class ScopeNode extends Node { } /** * Lookup a name in all scopes starting from most deeply nested. - * <p> + * * @param name Name to be looked up * @see #update(String, Node, int) */ public Node lookup( String name ) { return update(name,null,_scopes.size()-1); } /** * If the name is present in any scope, then redefine else null - * <p> + * * @param name Name being redefined * @param n The node to bind to the name */ public Node update( String name, Node n ) { return update(name,n,_scopes.size()-1); } /** * Both recursive lookup and update. - * <p> + * * A shared implementation allows us to create lazy phis both during * lookups and updates; the lazy phi creation is part of chapter 8. * diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 99e240ad..022e276d 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeTuple; /** * The Start node represents the start of the function. For now, we do not @@ -9,10 +10,14 @@ import com.seaofnodes.simple.type.Type; * will require Projections to extract the values. We discuss this in detail * in Chapter 9: Functions and Calls. */ -public class StartNode extends Node { +public class StartNode extends MultiNode { - public StartNode(/*arguments go here*/) { + final TypeTuple _args; + + public StartNode(Type[] args) { super(); + _args = new TypeTuple(args); + _type = _args; } @Override @@ -26,7 +31,7 @@ public class StartNode extends Node { @Override public boolean isCFG() { return true; } @Override - public Type compute() { return Type.BOTTOM; } + public TypeTuple compute() { return _args; } @Override public Node idealize() { return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index d2e32c61..58d757ea 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -19,15 +19,22 @@ public class SubNode extends Node { @Override public Type compute() { + // Sub of same is 0 + if( in(1)==in(2) ) + return TypeInteger.ZERO; + if (in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1) { if (i0.isConstant() && i1.isConstant()) return TypeInteger.constant(i0.value()-i1.value()); + return i0.meet(i1); } return Type.BOTTOM; } @Override - public Node idealize() { return null; } + public Node idealize() { + return null; + } } |