From c2813a97078c88726ecbc78ba985e9e4fefe2504 Mon Sep 17 00:00:00 2001 From: Thalia Archibald Date: Sun, 3 Mar 2024 17:55:47 +0000 Subject: Chapter 9: Global Value Numbering and Iterative Peepholes Co-authored-by: Cliff Click Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Tamas Hadhazy Co-authored-by: Robert Obkircher Co-authored-by: Dibyendu Majumdar Co-authored-by: Darrick Wiebe --- .../java/com/seaofnodes/simple/GraphEvaluator.java | 2 +- .../com/seaofnodes/simple/GraphVisualizer.java | 30 ++- src/main/java/com/seaofnodes/simple/IRPrinter.java | 7 +- src/main/java/com/seaofnodes/simple/IterPeeps.java | 204 ++++++++++++++++ src/main/java/com/seaofnodes/simple/Parser.java | 75 +++--- .../java/com/seaofnodes/simple/node/AddNode.java | 51 ++-- .../java/com/seaofnodes/simple/node/BoolNode.java | 3 +- .../com/seaofnodes/simple/node/ConstantNode.java | 17 +- .../java/com/seaofnodes/simple/node/DivNode.java | 3 +- .../java/com/seaofnodes/simple/node/IfNode.java | 29 ++- .../java/com/seaofnodes/simple/node/MinusNode.java | 2 +- .../java/com/seaofnodes/simple/node/MulNode.java | 3 +- .../java/com/seaofnodes/simple/node/MultiNode.java | 7 + src/main/java/com/seaofnodes/simple/node/Node.java | 261 +++++++++++++++++---- .../java/com/seaofnodes/simple/node/NotNode.java | 2 +- .../java/com/seaofnodes/simple/node/PhiNode.java | 49 ++-- .../java/com/seaofnodes/simple/node/ProjNode.java | 10 +- .../com/seaofnodes/simple/node/RegionNode.java | 68 ++++-- .../com/seaofnodes/simple/node/ReturnNode.java | 2 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 3 + .../java/com/seaofnodes/simple/node/StartNode.java | 2 +- .../java/com/seaofnodes/simple/node/StopNode.java | 11 +- .../java/com/seaofnodes/simple/node/SubNode.java | 3 +- src/main/java/com/seaofnodes/simple/type/Type.java | 76 +++++- .../com/seaofnodes/simple/type/TypeInteger.java | 59 +++-- .../java/com/seaofnodes/simple/type/TypeTuple.java | 46 +++- 26 files changed, 812 insertions(+), 213 deletions(-) create mode 100644 src/main/java/com/seaofnodes/simple/IterPeeps.java (limited to 'src/main/java/com/seaofnodes') diff --git a/src/main/java/com/seaofnodes/simple/GraphEvaluator.java b/src/main/java/com/seaofnodes/simple/GraphEvaluator.java index f5694a78..9fc51c8e 100644 --- a/src/main/java/com/seaofnodes/simple/GraphEvaluator.java +++ b/src/main/java/com/seaofnodes/simple/GraphEvaluator.java @@ -167,7 +167,7 @@ public class GraphEvaluator { public static long evaluate(Node graph, long parameter, int loops) { var res = evaluateWithResult(graph, parameter, loops); - if (res.type==ResultType.TIMEOUT) throw new RuntimeException("Timeout"); + if (res.type== ResultType.TIMEOUT) throw new RuntimeException("Timeout"); return res.value; } diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index d75e5bea..b4d64d4c 100644 --- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -20,15 +20,16 @@ public class GraphVisualizer { public GraphVisualizer(boolean separateControlCluster) { this._separateControlCluster = separateControlCluster; } public GraphVisualizer() { this(false); } - public String generateDotOutput(Parser parser) { + public String generateDotOutput(Parser parse) { return generateDotOutput(parse.STOP,parse._scope,parse._xScopes); } + public String generateDotOutput(StopNode stop, Node scope, Stack xScopes) { // Since the graph has cycles, we need to create a flat list of all the // nodes in the graph. - Collection all = findAll(parser); + Collection all = findAll(stop, scope); StringBuilder sb = new StringBuilder(); - sb.append("digraph chapter08 {\n"); + sb.append("digraph chapter09 {\n"); sb.append("/*\n"); - sb.append(parser.src()); + sb.append(stop._src); sb.append("\n*/\n"); // To keep the Scopes below the graph and pointing up into the graph we @@ -52,15 +53,19 @@ public class GraphVisualizer { nodes(sb, all); // Now the scopes, in a cluster no edges - for( ScopeNode scope : parser._xScopes ) - scope( sb, scope ); + if( xScopes != null ) + for( ScopeNode xscope : xScopes ) + if( !xscope.isDead() ) + scope( sb, xscope ); // Walk the Node edges nodeEdges(sb, all); // Walk the active Scope edges - for( ScopeNode scope : parser._xScopes ) - scopeEdges( sb, scope ); + if( xScopes != null ) + for( ScopeNode xscope : xScopes ) + if( !xscope.isDead() ) + scopeEdges( sb, xscope ); sb.append("}\n"); return sb.toString(); @@ -232,12 +237,13 @@ public class GraphVisualizer { /** * Finds all nodes in the graph. */ - private Collection findAll(Parser parser) { + private Collection findAll(Node stop, Node scope) { final HashMap all = new HashMap<>(); - for( Node n : Parser.START._outputs ) - walk(all, n); - for( Node n : parser._scope._inputs ) + for( Node n : stop._inputs ) walk(all, n); + if( scope != null ) + for( Node n : scope._inputs ) + walk(all, n); return all.values(); } diff --git a/src/main/java/com/seaofnodes/simple/IRPrinter.java b/src/main/java/com/seaofnodes/simple/IRPrinter.java index 2a6dbefd..c06ac9d0 100644 --- a/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -48,14 +48,15 @@ public class IRPrinter { // First walk the CFG, then everything if( n.isCFG() ) { for( Node use : n._outputs ) - if( use.isCFG() && use.nOuts()>=1 && !(use._outputs.get(0) instanceof LoopNode) ) + if( use!=null && use.isCFG() && use.nOuts()>=1 && !(use._outputs.get(0) instanceof LoopNode) ) postOrd(use, rpos,visit,bfs); for( Node use : n._outputs ) - if( use.isCFG() ) + if( use!=null && use.isCFG() ) postOrd(use,rpos,visit,bfs); } for( Node use : n._outputs ) - postOrd(use, rpos,visit,bfs); + if( use != null ) + postOrd(use, rpos,visit,bfs); // Post-order rpos.add(n); } diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java new file mode 100644 index 00000000..6dafd95f --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -0,0 +1,204 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.ConstantNode; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.StopNode; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.BitSet; +import java.util.Random; + +/** + * The IterOptim runs after parsing. It iterates the peepholes to a fixed point + * so that no more peepholes apply. This should be linear because peepholes rarely + * (never?) increase code size. The graph should monotonically reduce in some + * dimension, which is usually size. It might also reduce in e.g. number of + * MulNodes or Load/Store nodes, swapping out more "expensive" Nodes for cheaper + * ones. + * + * The theoretical overall worklist is mindless just grabbing the next thing and + * doing it. If the graph changes, put the neighbors on the worklist. Lather, + * Rinse, Repeat until the worklist runs dry. + * + * The main issues we have to deal with: + * + *
    + *
  • Nodes have uses; replacing some set of Nodes with another requires more graph + * reworking. Not rocket science, but it can be fiddly. Its helpful to have a + * small set of graph munging utilities, and the strong invariant that the graph + * is stable and correct between peepholes. In our case `Node.subsume` does + * most of the munging, building on our prior stable Node utilities.
    • + * + *
  • Changing a Node also changes the graph "neighborhood". The neigbors need to + * be checked to see if THEY can also peephole, and so on. After any peephole + * or graph update we put a Nodes uses and defs on the worklist.
    • + * + *
  • Our strong invariant is that for all Nodes, either they are on the worklist + * OR no peephole applies. This invariant is easy to check, although expensive. + * Basically the normal "iterate peepholes to a fixed point" is linear, and this + * check is linear at each peephole step... so quadratic overall. Its a useful + * assert, but one we can disable once the overall algorithm is stable - and + * then turn it back on again when some new set of peepholes is misbehaving. + * The code for this is turned on in `IterOptim.iterate` as `assert + * progressOnList(stop);`
    • + *
+ */ +public abstract class IterPeeps { + + private static final WorkList WORK = new WorkList<>(); + + public static N add( N n ) { + return (N)WORK.push(n); + } + + public static void addAll( ArrayList ary ) { + WORK.addAll(ary); + } + + /** + * Iterate peepholes to a fixed point + */ + public static StopNode iterate(StopNode stop, boolean show) { + assert progressOnList(stop); + int cnt=0; + + Node n; + while( (n=WORK.pop()) != null ) { + if( n.isDead() ) continue; + cnt++; // Useful for debugging, searching which peephole broke things + Node x = n.peepholeOpt(); + if( x != null ) { + if( x.isDead() ) continue; + // peepholeOpt can return brand-new nodes, needing an initial type set + if( x._type==null ) x.setType(x.compute()); + // Changes require neighbors onto the worklist + if( x != n || !(x instanceof ConstantNode) ) { + // All outputs of n (changing node) not x (prior existing node). + for( Node z : n._outputs ) WORK.push(z); + // Everybody gets a free "go again" in case they didn't get + // made in their final form. + WORK.push(x); + // If the result is not self, revisit all inputs (because + // there's a new user), and replace in the graph. + if( x != n ) { + for( Node z : n. _inputs ) WORK.push(z); + n.subsume(x); + } + } + // If there are distant neighbors, move to worklist + n.moveDepsToWorklist(); + assert progressOnList(stop); // Very expensive assert + } + } + + if( show ) + System.out.println(new GraphVisualizer().generateDotOutput(stop,null,null)); + return stop; + } + + // Visit ALL nodes and confirm the invariant: + // Either you are on the WORK worklist OR running `iter()` makes no progress. + + // This invariant ensures that no progress is missed, i.e., when the + // worklist is empty we have indeed done all that can be done. To help + // with debugging, the {@code assert} is broken out in a place where it is easy to + // stop if a change is found. + + // Also, the normal usage of `iter()` may attempt peepholes with distance + // neighbors and these should fail, but will then try to add dependencies + // {@link #Node.addDep} which is a side effect in an assert. The {@link + // #midAssert} is used to stop this side effect. + private static boolean MID_ASSERT; + public static boolean midAssert() { return MID_ASSERT; } + private static boolean progressOnList(Node stop) { + MID_ASSERT = true; + int old_cnt = Node.ITER_CNT, old_nop = Node.ITER_NOP_CNT; + Node changed = stop.walk( n -> { + if( WORK.on(n) ) return null; + Node m = n.peepholeOpt(); + if( m==null ) return null; + System.err.println("BREAK HERE FOR BUG"); + return m; + }); + Node.ITER_CNT = old_cnt; Node.ITER_NOP_CNT = old_nop; + MID_ASSERT = false; + return changed==null; + } + + public static void reset() { + WORK.clear(); + } + + /** + * Classic WorkList, with a fast add/remove, dup removal, random pull. + * The Node's nid is used to check membership in the worklist. + */ + public static class WorkList { + + private Node[] _es; + private int _len; + private final BitSet _on; // Bit set if Node._nid is on WorkList + private final Random _R; // For randomizing pull from the WorkList + private final long _seed; + + /* Useful stat - how many nodes are processed in the post parse iterative opt */ + private long _totalWork = 0; + + WorkList() { this(123); } + WorkList(long seed) { + _es = new Node[1]; + _len=0; + _on = new BitSet(); + _seed = seed; + _R = new Random(); + _R.setSeed(_seed); + } + + /** + * Pushes a Node on the WorkList, ensuring no duplicates + * If Node is null it will not be added. + */ + public E push( E x ) { + if( x==null ) return null; + int idx = x._nid; + if( !_on.get(idx) ) { + _on.set(idx); + if( _len==_es.length ) + _es = Arrays.copyOf(_es,_len<<1); + _es[_len++] = x; + _totalWork++; + } + return x; + } + + public void addAll( ArrayList ary ) { + for( E n : ary ) + push(n); + } + + /** + * True if Node is on the WorkList + */ + boolean on( E x ) { return _on.get(x._nid); } + + /** + * Removes a random Node from the WorkList; null if WorkList is empty + */ + E pop() { + if( _len == 0 ) return null; + int idx = _R.nextInt(_len); + E x = (E)_es[idx]; + _es[idx] = _es[--_len]; // Compress array + _on.clear(x._nid); + return x; + } + + public void clear() { + _len = 0; + _on.clear(); + _R.setSeed(_seed); + _totalWork = 0; + } + } +} diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 69796828..aabdf63a 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -69,11 +69,12 @@ public class Parser { public Parser(String source, TypeInteger arg) { Node.reset(); + IterPeeps.reset(); _lexer = new Lexer(source); _scope = new ScopeNode(); _continueScope = _breakScope = null; START = new StartNode(new Type[]{ Type.CONTROL, arg }); - STOP = new StopNode(); + STOP = new StopNode(source); } public Parser(String source) { @@ -108,7 +109,6 @@ public class Parser { return STOP; } - /** * Parses a block * @@ -185,11 +185,10 @@ public class Parser { // Parse predicate var pred = require(parseExpression(), ")"); // IfNode takes current control and predicate - IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole(); + Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes - Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); - ifNode.unkeep(); - Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + Node ifT = new ProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole(); // Clone the body Scope to create the break/exit Scope which accounts for any // side effects in the predicate. The break/exit Scope will be the final @@ -203,7 +202,7 @@ public class Parser { // Parse the true side, which corresponds to loop body // Our current scope is the body Scope - ctrl(ifT); // set ctrl token to ifTrue projection + ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection parseStatement(); // Parse loop body // Merge the loop bottom into other continue statements @@ -247,7 +246,7 @@ public class Parser { return cur; // toScope is either the break scope, or a scope that was created here assert toScope._scopes.size() <= _breakScope._scopes.size(); - toScope.mergeScopes(cur); + toScope.ctrl(toScope.mergeScopes(cur)); return toScope; } @@ -269,11 +268,10 @@ public class Parser { // Parse predicate var pred = require(parseExpression(), ")"); // IfNode takes current control and predicate - IfNode ifNode = (IfNode)new IfNode(ctrl(), pred).keep().peephole(); + Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes - Node ifT = new ProjNode(ifNode, 0, "True" ).peephole(); - ifNode.unkeep(); - Node ifF = new ProjNode(ifNode, 1, "False").peephole(); + Node ifT = new ProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); + Node ifF = new ProjNode(ifNode.unkeep(), 1, "False").peephole().keep(); // In if true branch, the ifT proj node becomes the ctrl // But first clone the scope and set it as current int ndefs = _scope.nIns(); @@ -281,13 +279,13 @@ public class Parser { _xScopes.push(fScope); // For graph visualization we need all scopes // Parse the true side - ctrl(ifT); // set ctrl token to ifTrue projection + ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection parseStatement(); // Parse true-side ScopeNode tScope = _scope; // Parse the false side _scope = fScope; // Restore scope, then parse else block if any - ctrl(ifF); // Ctrl token is now set to ifFalse projection + ctrl(ifF.unkeep()); // Ctrl token is now set to ifFalse projection if (matchx("else")) { parseStatement(); fScope = _scope; @@ -324,8 +322,8 @@ public class Parser { * Dumps out the node graph * @return {@code null} */ - private Node showGraph() { - System.out.println(new GraphVisualizer().generateDotOutput(this)); + Node showGraph() { + System.out.println(new GraphVisualizer().generateDotOutput(STOP,_scope,_xScopes)); return null; } @@ -384,12 +382,23 @@ public class Parser { */ private Node parseComparison() { var lhs = parseAddition(); - if (match("==")) return new BoolNode.EQ(lhs, parseComparison()).peephole(); - if (match("!=")) return new NotNode(new BoolNode.EQ(lhs, parseComparison()).peephole()).peephole(); - if (match("<=")) return new BoolNode.LE(lhs, parseComparison()).peephole(); - if (match("<" )) return new BoolNode.LT(lhs, parseComparison()).peephole(); - if (match(">=")) return new BoolNode.LE(parseComparison(), lhs).peephole(); - if (match(">" )) return new BoolNode.LT(parseComparison(), lhs).peephole(); + while( true ) { + int idx=0; boolean negate=false; + // Test for any local nodes made, and "keep" lhs during peepholes + if( false ) ; + else if( match("==") ) { idx=2; lhs = new BoolNode.EQ(lhs, null); } + else if( match("!=") ) { idx=2; lhs = new BoolNode.EQ(lhs, null); negate=true; } + else if( match("<=") ) { idx=2; lhs = new BoolNode.LE(lhs, null); } + else if( match("<" ) ) { idx=2; lhs = new BoolNode.LT(lhs, null); } + else if( match(">=") ) { idx=1; lhs = new BoolNode.LE(null, lhs); } + else if( match(">" ) ) { idx=1; lhs = new BoolNode.LT(null, lhs); } + else break; + // Peepholes can fire, but lhs is already "hooked", kept alive + lhs.setDef(idx,parseAddition()); + lhs = lhs.peephole(); + if( negate ) // Extra negate for != + lhs = new NotNode(lhs).peephole(); + } return lhs; } @@ -402,9 +411,15 @@ public class Parser { * @return an add expression {@link Node}, never {@code null} */ private Node parseAddition() { - var lhs = parseMultiplication(); - if (match("+")) return new AddNode(lhs, parseAddition()).peephole(); - if (match("-")) return new SubNode(lhs, parseAddition()).peephole(); + Node lhs = parseMultiplication(); + while( true ) { + if( false ) ; + else if( match("+") ) lhs = new AddNode(lhs,null); + else if( match("-") ) lhs = new SubNode(lhs,null); + else break; + lhs.setDef(2,parseMultiplication()); + lhs = lhs.peephole(); + } return lhs; } @@ -418,8 +433,14 @@ public class Parser { */ private Node parseMultiplication() { var lhs = parseUnary(); - if (match("*")) return new MulNode(lhs, parseMultiplication()).peephole(); - if (match("/")) return new DivNode(lhs, parseMultiplication()).peephole(); + while( true ) { + if( false ) ; + else if( match("*") ) lhs = new MulNode(lhs,null); + else if( match("/") ) lhs = new DivNode(lhs,null); + else break; + lhs.setDef(2,parseUnary()); + lhs = lhs.peephole(); + } return lhs; } diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 84a368fd..4e30bb55 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -25,21 +25,16 @@ 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; + return in(1)._type.meet(in(2)._type); } @Override public Node idealize () { 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 ) @@ -55,6 +50,10 @@ public class AddNode extends Node { if( !(lhs instanceof AddNode) && rhs instanceof AddNode ) return swap12(); + // x+(-y) becomes x-y + if( rhs instanceof MinusNode minus ) + return new SubNode(lhs,minus.in(1)); + // 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) ? @@ -66,7 +65,7 @@ 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) ) // Rotate; look for (add (phi cons) con/(phi cons)) - return spline_cmp(lhs,rhs) ? swap12() : phiCon(this,true); + return spine_cmp(lhs,rhs,this) ? swap12() : phiCon(this,true); // Now we only see (add add non) @@ -77,7 +76,11 @@ public class AddNode extends Node { // Do we have (x + con1) + con2? // Replace with (x + (con1+con2) which then fold the constants - if( lhs.in(2)._type.isConstant() && t2.isConstant() ) + // lhs.in(2) is con1 here + // If lhs.in(2) is not a constant, we add ourselves as a dependency + // because if it later became a constant then we could make this + // transformation. + if( lhs.in(2).addDep(this)._type.isConstant() && rhs._type.isConstant() ) return new AddNode(lhs.in(1),new AddNode(lhs.in(2),rhs).peephole()); @@ -87,11 +90,11 @@ public class AddNode extends Node { Node phicon = phiCon(this,true); if( phicon!=null ) return phicon; - // Now we sort along the spline via rotates, to gather similar things together. + // Now we sort along the spine via rotates, to gather similar things together. // Do we rotate (x + y) + z // into (x + z) + y ? - if( spline_cmp(lhs.in(2),rhs) ) + if( spine_cmp(lhs.in(2),rhs,this) ) return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2)); return null; @@ -104,16 +107,16 @@ public class AddNode extends Node { Node lhs = op.in(1); Node rhs = op.in(2); // LHS is either a Phi of constants, or another op with Phi of constants - PhiNode lphi = pcon(lhs); + PhiNode lphi = pcon(lhs,op); if( rotate && lphi==null && lhs.nIns() > 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 + lphi = pcon(lhs.in(2),op); // 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 ) + if( !(rhs instanceof ConstantNode) && pcon(rhs,op)==null ) return null; // If both are Phis, must be same Region @@ -134,21 +137,31 @@ public class AddNode extends Node { return lhs==lphi ? phi : op.copy(lhs.in(1),phi); } - static PhiNode pcon(Node op) { - return op instanceof PhiNode phi && phi.allCons() ? phi : null; + /** + * Tests if the op is a phi and has all constant inputs. + * If not, returns null. + * If op is a phi, but its inputs are not all constants, then dep is added as + * a dependency to the phi's non-const input, because if later the input turn into a constant + * dep can make progress. + */ + static PhiNode pcon(Node op, Node dep) { + return op instanceof PhiNode phi && phi.allCons(dep) ? phi : null; } - // Compare two off-spline nodes and decide what order they should be in. + // Compare two off-spine 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 Phi-of-constants, then muls, 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 ) { + static boolean spine_cmp( Node hi, Node lo, Node dep ) { if( lo._type.isConstant() ) return false; if( hi._type.isConstant() ) return true ; - if( lo instanceof PhiNode && lo.allCons() ) return false; - if( hi instanceof PhiNode && hi.allCons() ) return true ; + if( lo instanceof PhiNode lphi && lphi.region()._type==Type.XCONTROL ) return false; + if( hi instanceof PhiNode hphi && hphi.region()._type==Type.XCONTROL ) return false; + + if( lo instanceof PhiNode && lo.allCons(dep) ) return false; + if( hi instanceof PhiNode && hi.allCons(dep) ) return true ; if( lo instanceof PhiNode && !(hi instanceof PhiNode) ) return true; if( hi instanceof PhiNode && !(lo instanceof PhiNode) ) return false; diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index 0c32d50d..d3fcec95 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -32,9 +32,8 @@ abstract public class BoolNode extends Node { 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; + return in(1)._type.meet(in(2)._type); } abstract boolean doOp(long lhs, long rhs); diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 13006bfb..9e45198c 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -8,7 +8,7 @@ import java.util.BitSet; /** * A Constant node represents a constant value. At present, the only constants * that we allow are integer literals; therefore Constants contain an integer - * value. As we add other types of constants, we will refactor how we represent + * value. As we add other types of constants, we will refactor how we represent * Constants. *

* Constants have no semantic inputs. However, we set Start as an input to @@ -25,7 +25,7 @@ public class ConstantNode extends Node { } @Override - public String label() { return ""+_con; } + public String label() { return "#"+_con; } @Override public String uniqueName() { return "Con_" + _nid; } @@ -42,4 +42,17 @@ public class ConstantNode extends Node { @Override public Node idealize() { return null; } + + @Override + boolean eq(Node n) { + ConstantNode con = (ConstantNode)n; // Contract + return _con==con._con; + } + + @Override + int hash() { return _con.hashCode(); } + + // Dead control is its own idom root + Node idom() { 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 7207fd48..08ce70b8 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -27,9 +27,8 @@ public class DivNode extends Node { return i1.value() == 0 ? TypeInteger.ZERO : TypeInteger.constant(i0.value()/i1.value()); - return i0.meet(i1); } - return Type.BOTTOM; + return in(1)._type.meet(in(2)._type); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 23a8fafc..460dce51 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -32,27 +32,30 @@ public class IfNode extends MultiNode { // If the If node is not reachable then neither is any following Proj if (ctrl()._type != Type.CONTROL && ctrl()._type != Type.BOTTOM ) return TypeTuple.IF_NEITHER; + Node pred = pred(); + Type t = pred._type; + // High types mean NEITHER side is reachable. + // Wait until the type falls to decide which way to go. + if( t == Type.TOP || t == TypeInteger.TOP ) + return TypeTuple.IF_NEITHER; // If constant is 0 then false branch is reachable // Else true branch is reachable - if (pred()._type instanceof TypeInteger ti && ti.isConstant()) { - if (ti.value() == 0) return TypeTuple.IF_FALSE; - else return TypeTuple.IF_TRUE; - } - - // Hunt up the immediate dominator tree. If we find an identical if - // test on either the true or false branch, then this test matches. - for( Node dom = idom(), prior=this; dom!=null; prior=dom, dom = dom.idom() ) - if( dom instanceof IfNode iff && iff.pred()==pred() ) - return prior instanceof ProjNode proj - // Repeated test, dominated on one side. Test result is the same. - ? (proj._idx==0 ? TypeTuple.IF_TRUE : TypeTuple.IF_FALSE) - : dom._type; // Repeated test not dominated on one side + if (t instanceof TypeInteger ti && ti.isConstant()) + return ti==TypeInteger.ZERO ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; return TypeTuple.IF_BOTH; } @Override public Node idealize() { + // Hunt up the immediate dominator tree. If we find an identical if + // test on either the true or false branch, that side wins. + if( !pred()._type.isHighOrConst() ) + for( Node dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() ) + if( dom.addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==pred() && prior instanceof ProjNode prj ) { + setDef(1,new ConstantNode(TypeInteger.make(true,prj._idx==0?1:0)).peephole()); + return this; + } return null; } } diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 3d944fd4..dd092c9e 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -22,7 +22,7 @@ public class MinusNode extends Node { public Type compute() { if (in(1)._type instanceof TypeInteger i0) return i0.isConstant() ? TypeInteger.constant(-i0.value()) : i0; - return Type.BOTTOM; + return TypeInteger.TOP.meet(in(1)._type); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 2e701a4e..7e9f88a2 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -25,9 +25,8 @@ 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; + return in(1)._type.meet(in(2)._type); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/src/main/java/com/seaofnodes/simple/node/MultiNode.java index 7ba1aa19..2743bd19 100644 --- a/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -4,4 +4,11 @@ public abstract class MultiNode extends Node { public MultiNode(Node... inputs) { super(inputs); } + // Find a projection by index + ProjNode proj( int idx ) { + for( Node out : _outputs ) + if( out instanceof ProjNode prj && prj._idx==idx ) + return prj; + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 2d6d5ad5..5eb9c076 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,10 +1,12 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IRPrinter; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import java.util.*; +import java.util.function.Function; /** * All Nodes in the Sea of Nodes IR inherit from the Node class. @@ -63,6 +65,7 @@ public abstract class Node { * Starting with value 1, to avoid bugs confusing node ID 0 with uninitialized values. * */ private static int UNIQUE_ID = 1; + public static int UID() { return UNIQUE_ID; } protected Node(Node... inputs) { _nid = UNIQUE_ID++; // allocate unique dense ID @@ -105,7 +108,7 @@ public abstract class Node { // This is the common print: check for repeats, check for DEAD and print // "DEAD" else call the per-Node print1. final StringBuilder _print0(StringBuilder sb, BitSet visited) { - if (visited.get(_nid)) + if (visited.get(_nid) && !(this instanceof ConstantNode) ) return sb.append(label()); visited.set(_nid); return isDead() @@ -131,7 +134,7 @@ public abstract class Node { sb.append(" "); sb.append(" [[ "); for( Node use : _outputs ) - sb.append("%4d ".formatted(use._nid)); + sb.append(use==null ? "____ " : "%4d ".formatted(use._nid)); int lim = 5 - Math.max(_inputs.size(),3); for( int i = _outputs.size(); iuse edge // This needs to happen before removing the old node's def->use edge as // the new_def might get killed if the old node kills it recursively. @@ -198,13 +203,17 @@ public abstract class Node { // 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) { + // Phi, but not for every Node. If the def goes dead, it is recursively + // killed, which may include 'this' Node. + Node delDef(int idx) { + unlock(); 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 + old_def.moveDepsToWorklist(); Utils.del(_inputs, idx); + return this; } /** @@ -215,6 +224,7 @@ public abstract class Node { * @return new_def for flow coding */ Node addDef(Node new_def) { + unlock(); // Add use->def edge _inputs.add(new_def); // If new def is not null, add the corresponding def->use edge @@ -237,6 +247,7 @@ public abstract class Node { // Shortcut for "popping" n nodes. A "pop" is basically a // setDef(last,null) followed by lowering the nIns() count. void popN(int n) { + unlock(); for( int i=0; iuses, by setting all of its defs - * to null. This may recursively kill more Nodes and is basically dead - * code elimination. This function is co-recursive with {@link #popN}. + * to null. This may recursively kill more Nodes, and is basically dead + * code elimination. */ public void kill( ) { + unlock(); assert isUnused(); // Has no uses, so it is dead - popN(nIns()); // Set all inputs to null, recursively killing unused Nodes _type=null; // Flag as dead + while( nIns()>0 ) { // Set all inputs to null, recursively killing unused Nodes + Node old_def = _inputs.removeLast(); + if( old_def != null ) { + IterPeeps.add(old_def);// Revisit neighbor because removed use + if( old_def.delUse(this) ) // If we removed the last use, the old def is now dead + old_def.kill(); // Kill old def + } + } assert isDead(); // Really dead now } // Mostly used for asserts and printing. - boolean isDead() { return isUnused() && nIns()==0 && _type==null; } + public boolean isDead() { return isUnused() && nIns()==0 && _type==null; } // Shortcuts to stop DCE mid-parse // Add bogus null use to keep node alive @@ -268,10 +287,11 @@ public abstract class Node { // Replace self with nnn in the graph, making 'this' go dead - void subsume( Node nnn ) { + public void subsume( Node nnn ) { assert nnn!=this; while( nOuts() > 0 ) { Node n = _outputs.removeLast(); + n.unlock(); int idx = Utils.find(n._inputs, this); n._inputs.set(idx,nnn); nnn.addUse(n); @@ -288,6 +308,19 @@ public abstract class Node { */ public static boolean _disablePeephole = false; + /** + * Try to peephole at this node and return a better replacement Node. + * Always returns some not-null Node (often this). + */ + public final Node peephole( ) { + if (_disablePeephole) { + _type = compute(); + return this; // Peephole optimizations turned off + } + Node n = peepholeOpt(); + return n==null ? this : deadCodeElim(n.peephole()); // Cannot return null for no-progress + } + /** * Try to peephole at this node and return a better replacement Node if * possible. We compute a {@link Type} and then check and replace: @@ -301,29 +334,45 @@ public abstract class Node { * {@code (x+(1+2))}. By canonicalizing expressions we fold common addressing * math constants, remove algebraic identities and generally simplify the * code. + * + * Unlike peephole above, this explicitly returns null for no-change, or not-null + * for a better replacement (which can be this). * */ - public final Node peephole( ) { + public final Node peepholeOpt( ) { + ITER_CNT++; // Compute initial or improved Type - Type type = _type = compute(); - - if (_disablePeephole) - return this; // Peephole optimizations turned off + Type old = setType(compute()); // Replace constant computations from non-constants with a constant node - if (!(this instanceof ConstantNode) && type.isConstant()) - return deadCodeElim(new ConstantNode(type).peephole()); - - // Future chapter: Global Value Numbering goes here + if (!(this instanceof ConstantNode) && _type.isHighOrConst() ) + return new ConstantNode(_type).peepholeOpt(); + + // Global Value Numbering + if( _hash==0 ) { + Node n = GVN.get(this); // Will set _hash as a side effect + if( n==null ) + GVN.put(this,this); // Put in table now + else { + // Because of random worklist ordering, the two equal nodes + // might have different types. Because of monotonicity, both + // types are valid. To preserve monotonicity, the resulting + // shared Node has to have the best of both types. + n.setType(n._type.join(_type)); + _hash = 0; // Clear, since it never went in the table + return deadCodeElim(n);// Return previous; does Common Subexpression Elimination + } + } // Ask each node for a better replacement Node n = idealize(); if( n != null ) // Something changed - // Recursively optimize - return deadCodeElim(n.peephole()); + return n; // Report progress - return this; // No progress + if( old==_type ) ITER_NOP_CNT++; + return old==_type ? null : this; // Report progress } + public static int ITER_CNT, ITER_NOP_CNT; // m is the new Node, self is the old. // Return 'm', which may have zero uses but is alive nonetheless. @@ -353,13 +402,26 @@ public abstract class Node { * theory. Much later on, this will become important and allow us to do * many fancy complex optimizations trivially... because theory. *

- * compute() needs to be stand-alone, and cannot recursively call compute - * on its inputs programs are cyclic (have loops!) and this will just + * {@link #compute()} needs to be stand-alone, and cannot recursively call compute + * on its inputs, because programs are cyclic (have loops!) and this will just * infinitely recurse until stack overflow. Instead, compute typically * computes a new type from the {@link #_type} field of its inputs. */ public abstract Type compute(); + // Set the type. Assert monotonic progress. + // If changing, add users to worklist. + public Type setType(Type type) { + Type old = _type; + assert old==null || type.isa(old); // Since _type not set, can just re-run this in assert in the debugger + if( old == type ) return old; + _type = type; // Set _type late for easier assert debugging + IterPeeps.addAll(_outputs); + moveDepsToWorklist(); + return old; + } + + /** * 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 @@ -399,32 +461,127 @@ public abstract class Node { * call peephole. *

* Since idealize calls peephole and peephole calls idealize, you must be - * careful that all idealizations are monotonic: all transforms remove - * some feature, so that the set of available transforms always shrinks. - * If you don't, you risk an infinite peephole loop! + * careful that all idealizations are monotonic: 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(); + // Some of the peephole rules get complex, and search further afield than + // just the nearest neighbor. These peepholes can fail the pattern match + // on a node some distance away, and if that node ever changes we should + // retry the peephole. Track a set of Nodes dependent on `this`, and + // revisit them if `this` changes. + 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. + */ + Node addDep( Node dep ) { + // Running peepholes during the big assert cannot have side effects + // like adding dependencies. + if( IterPeeps.midAssert() ) return this; + if( _deps==null ) _deps = new ArrayList<>(); + if( Utils.find(_deps ,dep) != -1 ) return this; // Already on list + if( Utils.find(_inputs,dep) != -1 ) return this; // No need for deps on immediate neighbors + if( Utils.find(_outputs,dep)!= -1 ) return this; + _deps.add(dep); + return this; + } + + // Move the dependents onto a worklist, and clear for future dependents. + public void moveDepsToWorklist( ) { + if( _deps==null ) return; + IterPeeps.addAll(_deps); + _deps.clear(); + } + + + // Global Value Numbering. Hash over opcode and inputs; hits in this table + // are structurally equal. + public static final HashMap GVN = new HashMap<>(); + + // Two nodes are equal if they have the same inputs and the same "opcode" + // which means the same Java class, plus same internal parts. + @Override public final boolean equals( Object o ) { + if( o==this ) return true; + if( o.getClass() != getClass() ) return false; + Node n = (Node)o; + int len = _inputs.size(); + if( len != n._inputs.size() ) return false; + for( int i=0; i>13) ^ n._nid; + if( hash==0 ) hash = 0xDEADBEEF; // Bad hash, so use some junky thing + return (_hash=hash); + } + // Subclasses add extra hash info (such as ConstantNodes constant) + int hash() { return 0; } + + // ------------------------------------------------------------------------ // Peephole utilities // Swap inputs without letting either input go dead during the swap. Node swap12() { + unlock(); // Hash is order dependent Node tmp = in(1); _inputs.set(1,in(2)); _inputs.set(2,tmp); return this; } - // does this node contain all constants? - // Ignores in(0), as is usually control. - boolean allCons() { + /** + * Does this node contain all constants? + * Ignores in(0), as is usually control. + * In an input is not a constant, we add dep as + * a dependency to it, because dep can make progress + * if the input becomes a constant later. + * It is sufficient for one of the non-const + * inputs to have the dependency so we don't bother + * checking the rest. + */ + boolean allCons(Node dep) { for( int i=1; i E walk( Function pred ) { + assert WVISIT.isEmpty(); + E rez = _walk(pred); + WVISIT.clear(); + return rez; + } + + private E _walk( Function pred ) { + if( WVISIT.get(_nid) ) return null; // Been there, done that + WVISIT.set(_nid); + E x = pred.apply(this); + if( x != null ) return x; + for( Node def : _inputs ) if( def != null && (x = def._walk(pred)) != null ) return x; + for( Node use : _outputs ) if( use != null && (x = use._walk(pred)) != null ) return x; + return null; } /** * Debugging utility to find a Node by index */ - public Node find(int nid) { return _find(new BitSet(),nid); } - private Node _find(BitSet visit, int nid) { - if( _nid==nid ) return this; - if( visit.get(_nid) ) return null; - visit.set(_nid); - for( Node def : _inputs ) - if( def!=null ) { - Node rez = def._find(visit,nid); - if( rez != null ) return rez; - } - for( Node use : _outputs ) { - Node rez = use._find(visit,nid); - if( rez != null ) return rez; - } - return null; + public Node find(int nid) { + return walk( n -> n._nid==nid ? n : null ); } } diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java index 39df410d..7a520fec 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -22,7 +22,7 @@ public class NotNode extends Node { public Type compute() { if( in(1)._type instanceof TypeInteger i0 ) return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : i0; - return Type.BOTTOM; + return TypeInteger.TOP.meet(in(1)._type); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index c7b5b357..ec4c6ad3 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -16,7 +16,7 @@ public class PhiNode extends Node { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { - if( region().inProgress() ) + if( !(region() instanceof RegionNode r) || r.inProgress() ) sb.append("Z"); sb.append("Phi("); for( Node in : _inputs ) { @@ -29,23 +29,29 @@ public class PhiNode extends Node { return sb; } - RegionNode region() { return (RegionNode)in(0); } + Node region() { return in(0); } @Override public boolean isMultiTail() { return true; } @Override public Type compute() { - if( !(region() instanceof RegionNode r) || r.inProgress() ) - return Type.BOTTOM; + if( !(region() instanceof RegionNode r) ) + return region()._type==Type.XCONTROL ? Type.TOP : _type; + if( r.inProgress() ) return Type.BOTTOM; Type t = Type.TOP; for (int i = 1; i < nIns(); i++) - t = t.meet(in(i)._type); + // If the region's control input is live, add this as a dependency + // to the control because we can be peeped should it become dead. + if( r.in(i).addDep(this)._type != Type.XCONTROL && in(i) != this ) + t = t.meet(in(i)._type); return t; } @Override public Node idealize() { - if( !(region() instanceof RegionNode r ) || r.inProgress() ) - return null; + if( !(region() instanceof RegionNode r ) ) + return in(1); // Input has collapse to e.g. starting control. + if( r.inProgress() || r.nIns()<=1 ) + return null; // Input is in-progress // If we have only a single unique input, become it. Node live = singleUniqueInput(); @@ -84,11 +90,13 @@ public class PhiNode extends Node { * If only single unique input, return it */ private Node singleUniqueInput() { + if( region() instanceof LoopNode loop && loop.entry()._type == Type.XCONTROL ) + return null; // Dead entry loops just ignore and let the loop collapse Node live = null; for( int i=1; i1 && in(nIns()-1) == null; + } + + // Never equal if inProgress + @Override boolean eq( Node n ) { + return !inProgress(); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 312058b9..922a3649 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -34,7 +34,7 @@ public class ReturnNode extends Node { @Override public Type compute() { - return new TypeTuple(ctrl()._type,expr()._type); + return TypeTuple.make(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 e5d03d93..3abea54d 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; import java.util.*; @@ -212,6 +213,8 @@ public class ScopeNode extends Node { if( in(i) instanceof PhiNode phi ) { // Do an eager useless-phi removal Node in = phi.peephole(); + IterPeeps.addAll(phi._outputs); + phi.moveDepsToWorklist(); if( in != phi ) { phi.subsume(in); setDef(i,in); // Set the update back into Scope diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 01f1485a..e399138b 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -18,7 +18,7 @@ public class StartNode extends MultiNode { public StartNode(Type[] args) { super(); - _args = new TypeTuple(args); + _args = TypeTuple.make(args); _type = _args; } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index 417790d9..602feffc 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -1,12 +1,17 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.IterPeeps; import java.util.BitSet; public class StopNode extends Node { - public StopNode(Node... inputs) { - super(inputs); + + public final String _src; + + public StopNode(String src) { + super(); + _src = src; } @Override @@ -50,4 +55,6 @@ public class StopNode extends Node { return addDef(node); } + public StopNode iterate( ) { return IterPeeps.iterate(this,false); } + public StopNode iterate(boolean show) { return IterPeeps.iterate(this,show ); } } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index af66b950..f661be14 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -29,9 +29,8 @@ public class SubNode 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; + return in(1)._type.meet(in(2)._type); } @Override diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index 2f0e6171..d0265e83 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -1,5 +1,8 @@ package com.seaofnodes.simple.type; +import com.seaofnodes.simple.Utils; + +import java.util.HashMap; /** * These types are part of a Monotone Analysis Framework, @@ -18,6 +21,7 @@ package com.seaofnodes.simple.type; */ public class Type { + static final HashMap INTERN = new HashMap<>(); // ---------------------------------------------------------- // Simple types are implemented fully here. "Simple" means: the code and @@ -36,15 +40,53 @@ public class Type { 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 static final Type BOTTOM = new Type( TBOT ).intern(); // ALL + public static final Type TOP = new Type( TTOP ).intern(); // ANY + public static final Type CONTROL = new Type( TCTRL ).intern(); // Ctrl + public static final Type XCONTROL = new Type( TXCTRL ).intern(); // ~Ctrl + + // Is high or on the lattice centerline. + public boolean isHighOrConst() { return _type==TTOP || _type==TXCTRL; } - public boolean isConstant() { return _type == TTOP || _type == TXCTRL; } + // Strict constant values, things on the lattice centerline. + // Excludes both high and low values + public boolean isConstant() { return false; } public StringBuilder _print(StringBuilder sb) {return is_simple() ? sb.append(STRS[_type]) : sb;} + // ---------------------------------------------------------- + + // Factory method which interns "this" + protected T intern() { + T nnn = (T)INTERN.get(this); + if( nnn==null ) + INTERN.put(nnn=(T)this,this); + return nnn; + } + + private int _hash; // Hash cache; not-zero when set. + @Override + public final int hashCode() { + if( _hash!=0 ) return _hash; + _hash = hash(); + if( _hash==0 ) _hash = 0xDEADBEEF; // Bad hash from subclass; use some junk thing + return _hash; + } + // Override in subclasses + int hash() { return _type; } + + @Override + public final boolean equals( Object o ) { + if( o==this ) return true; + if( !(o instanceof Type t)) return false; + if( _type != t._type ) return false; + return eq(t); + } + // Overridden in subclasses; subclass can assume "this!=t" and java classes are same + boolean eq(Type t) { return true; } + + + // ---------------------------------------------------------- public final Type meet(Type t) { // Shortcut for the self case if( t == this ) return this; @@ -53,7 +95,7 @@ public class Type { // 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 + return xmeet(t); // Mixing 2 unrelated types } // Compute meet right now. Overridden in subclasses. @@ -70,6 +112,28 @@ public class Type { return _type==TCTRL || t._type==TCTRL ? CONTROL : XCONTROL; } + // True if this "isa" t; e.g. 17 isa TypeInteger.BOT + public boolean isa( Type t ) { return meet(t)==t; } + + // ---------------------------------------------------------- + // Our lattice is defined with a MEET and a DUAL. + // JOIN is dual of meet of both duals. + public final Type join(Type t) { + if( this==t ) return this; + return dual().meet(t.dual()).dual(); + } + + public Type dual() { + return switch( _type ) { + case TBOT -> TOP; + case TTOP -> BOTTOM; + case TCTRL -> XCONTROL; + case TXCTRL -> CONTROL; + default -> throw Utils.TODO(); // Should not reach here + }; + } + + // ---------------------------------------------------------- @Override public final String toString() { return _print(new StringBuilder()).toString(); diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index b30e21d8..ba045603 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -5,36 +5,39 @@ package com.seaofnodes.simple.type; */ public class TypeInteger extends Type { - public final static TypeInteger TOP = new TypeInteger(false, 0); - public final static TypeInteger BOT = new TypeInteger(false, 1); - public final static TypeInteger ZERO= new TypeInteger(true, 0); + public final static TypeInteger TOP = make(false, 0); + public final static TypeInteger BOT = make(false, 1); + public final static TypeInteger ZERO= make(true , 0); - private final boolean _is_con; + public final boolean _is_con; /** * The constant value or - * if not constant then 0=bottom, 1=top. + * if not constant then 1=bottom, 0=top. */ - private final long _con; + public final long _con; - public TypeInteger(boolean is_con, long con) { + private TypeInteger(boolean is_con, long con) { super(TINT); _is_con = is_con; _con = con; } + public static TypeInteger make(boolean is_con, long con) { + return new TypeInteger(is_con,con).intern(); + } - public static TypeInteger constant(long con) { return new TypeInteger(true, con); } - - public boolean isTop() { return !_is_con && _con==0; } - public boolean isBot() { return !_is_con && _con==1; } + public static TypeInteger constant(long con) { return make(true, con); } @Override public StringBuilder _print(StringBuilder sb) { - if (isTop()) return sb.append("IntTop"); - if (isBot()) return sb.append("IntBot"); + if( this==TOP ) return sb.append("IntTop"); + if( this==BOT ) return sb.append("IntBot"); return sb.append(_con); } + @Override + public boolean isHighOrConst() { return _is_con || _con==0; } + @Override public boolean isConstant() { return _is_con; } @@ -42,22 +45,30 @@ public class TypeInteger extends Type { @Override public Type xmeet(Type other) { - if( this==other ) return this; - if (!(other instanceof TypeInteger i)) return super.meet(other); + // Invariant from caller: 'this' != 'other' and same class (TypeInteger) + TypeInteger i = (TypeInteger)other; // Contract // BOT wins - if ( isBot() ) return this; - if ( i.isBot() ) return i ; + if ( this==BOT ) return this; + if ( i ==BOT ) return i ; // TOP loses - if ( i.isTop() ) return this; - if ( isTop() ) return i ; - assert isConstant() && i.isConstant(); - return _con==i._con ? this : TypeInteger.BOT; + if ( i ==TOP ) return this; + if ( this==TOP ) return i ; + // Since both are constants, and are never equals (contract) unequals + // constants fall to bottom + return BOT; } @Override - public boolean equals( Object o ) { - if( o==this ) return true; - if( !(o instanceof TypeInteger i) ) return false; + public Type dual() { + if( isConstant() ) return this; // Constants are a self-dual + return _con==0 ? BOT : TOP; + } + + @Override + int hash() { return (int)(_con ^ (_is_con ? 0 : 0x4000)); } + @Override + public boolean eq( Type t ) { + TypeInteger i = (TypeInteger)t; // Contract return _con==i._con && _is_con==i._is_con; } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 0f8b95bd..e82ea00b 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -4,14 +4,24 @@ public class TypeTuple extends Type { public final Type[] _types; - public TypeTuple(Type... _types) { - super(TTUPLE); - this._types = _types; - } + private TypeTuple(Type[] types) { super(TTUPLE); _types = types; } + public static TypeTuple make(Type... types) { return new TypeTuple(types).intern(); } @Override public Type xmeet(Type other) { - throw new UnsupportedOperationException("Meet on Tuple Type not yet implemented"); + TypeTuple tt = (TypeTuple)other; // contract from xmeet + assert _types.length == tt._types.length; + Type[] ts = new Type[_types.length]; + for( int i=0; i<_types.length; i++ ) + ts[i] = _types[i].meet(tt._types[i]); + return make(ts); + } + + @Override public Type dual() { + Type[] ts = new Type[_types.length]; + for( int i=0; i<_types.length; i++ ) + ts[i] = _types[i].dual(); + return make(ts); } @Override @@ -24,9 +34,27 @@ public class TypeTuple extends Type { return sb; } - 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}); + public static final TypeTuple IF_BOTH = make(new Type[]{Type. CONTROL,Type. CONTROL}); + public static final TypeTuple IF_NEITHER = make(new Type[]{Type.XCONTROL,Type.XCONTROL}); + public static final TypeTuple IF_TRUE = make(new Type[]{Type. CONTROL,Type.XCONTROL}); + public static final TypeTuple IF_FALSE = make(new Type[]{Type.XCONTROL,Type. CONTROL}); + + @Override + int hash() { + int sum = 0; + for( Type type : _types ) sum ^= type.hashCode(); + return sum; + } + + @Override + boolean eq( Type t ) { + TypeTuple tt = (TypeTuple)t; // Contract + if( _types.length != tt._types.length ) return false; + for( int i=0; i<_types.length; i++ ) + if( _types[i]!=tt._types[i] ) + return false; + return true; + } + } -- cgit v1.2.3