diff options
Diffstat (limited to 'src')
38 files changed, 1310 insertions, 295 deletions
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<ScopeNode> xScopes) { // Since the graph has cycles, we need to create a flat list of all the // nodes in the graph. - Collection<Node> all = findAll(parser); + Collection<Node> 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<Node> findAll(Parser parser) { + private Collection<Node> findAll(Node stop, Node scope) { final HashMap<Integer, Node> 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: + * + * <ul> + * <li>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.</li> + * + * <li>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.</li> + * + * <li>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);`</li> + * </ul> + */ +public abstract class IterPeeps { + + private static final WorkList<Node> WORK = new WorkList<>(); + + public static <N extends Node> N add( N n ) { + return (N)WORK.push(n); + } + + public static void addAll( ArrayList<Node> 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<E extends Node> { + + 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<E> 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).<IfNode>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 49bb30ea..2012a30a 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. * <p> * 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(); i<lim; i++ ) sb.append(" "); @@ -154,6 +157,7 @@ public abstract class Node { * @return Input node or null */ public Node in(int i) { return _inputs.get(i); } + public Node out(int i) { return _outputs.get(i); } public int nIns() { return _inputs.size(); } @@ -179,9 +183,10 @@ public abstract class Node { * @param new_def the new definition * @return new_def for flow coding */ - Node setDef(int idx, Node new_def ) { + public Node setDef(int idx, Node new_def ) { + unlock(); Node old_def = in(idx); - if( old_def == new_def ) return this; // No change + if( old_def == new_def ) return new_def; // No change // If new def is not null, add the corresponding def->use 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; i<n; i++ ) { Node old_def = _inputs.removeLast(); if( old_def != null && // If it exists and @@ -247,18 +258,26 @@ public abstract class Node { /** * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em> - * 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); @@ -289,6 +309,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: * <ul> @@ -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. </li> + * + * Unlike peephole above, this explicitly returns null for no-change, or not-null + * for a better replacement (which can be this). * </ul> */ - 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. * <p> - * 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. * <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! + * 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(); + // 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<Node> _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<Node,Node> 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<len; i++ ) + if( in(i) != n.in(i) ) + return false; + return eq(n); + } + // Subclasses add extra checks (such as ConstantNodes have same constant), + // and can assume "this!=n" and has the same Java class. + boolean eq( Node n ) { return true; } + + + // Cached hash. If zero, then not computed AND this Node is NOT in the GVN + // table - and can have its edges hacked (which will change his hash + // anyway). If Non-Zero then this Node is IN the GVN table, or is being + // probed to see if it can be inserted. His edges are "locked", because + // hacking his edges will change his hash. + int _hash; + + // If the _hash is set, then the Node is in the GVN table; remove it. + void unlock() { + if( _hash==0 ) return; + Node old = GVN.remove(this); // Pull from table + assert old==this; + _hash=0; // Out of table now + } + + + // Hash of opcode and inputs + @Override public final int hashCode() { + if( _hash != 0 ) return _hash; + int hash = hash(); + for( Node n : _inputs ) + if( n != null ) + hash = hash ^ (hash<<17) ^ (hash>>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<nIns(); i++ ) - if( !(in(i)._type.isConstant()) ) + if( !(in(i)._type.isConstant()) ) { + in(i).addDep(dep); // If in(i) becomes a constant later, will trigger some peephole return false; + } return true; } @@ -448,25 +605,35 @@ public abstract class Node { public static void reset() { UNIQUE_ID = 1; _disablePeephole=false; + GVN.clear(); + ITER_CNT = ITER_NOP_CNT = 0; + } + + + // Utility to walk the entire graph applying a function; return the first + // not-null result. + private static final BitSet WVISIT = new BitSet(); + final public <E> E walk( Function<Node,E> pred ) { + assert WVISIT.isEmpty(); + E rez = _walk(pred); + WVISIT.clear(); + return rez; + } + + private <E> E _walk( Function<Node,E> 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; i<nIns(); i++ ) { - if( region() instanceof LoopNode loop && loop.entry()._type == Type.XCONTROL ) - return null; // Dead entry loops just ignore and let the loop collapse - if( region().in(i)._type != Type.XCONTROL && in(i) != this ) + // 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( region().in(i).addDep(this)._type != Type.XCONTROL && in(i) != this ) if( live == null || live == in(i) ) live = in(i); else return null; } @@ -96,9 +104,22 @@ public class PhiNode extends Node { } @Override - boolean allCons() { - if( !(region() instanceof RegionNode r) || r.inProgress() ) - return false; - return super.allCons(); + boolean allCons(Node dep) { + if( !(region() instanceof RegionNode r) ) return false; + // When the region completes (is no longer in progress) the Phi can + // become a "all constants" Phi, and the "dep" might make progress. + addDep(dep); + if( r.inProgress() ) return false; + return super.allCons(dep); + } + + // True if last input is null + public final boolean inProgress() { + return 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/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 3c3f73b8..0ed9441d 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -7,7 +7,7 @@ import java.util.BitSet; public class ProjNode extends Node { - // Which slice of the incoming multi-part value + // Which slice of the incoming multipart value public final int _idx; // Debugging label @@ -32,7 +32,7 @@ public class ProjNode extends Node { @Override public Type compute() { - Type t = ctrl()._type; + Type t = in(0)._type; return t instanceof TypeTuple tt ? tt._types[_idx] : Type.BOTTOM; } @@ -42,4 +42,10 @@ public class ProjNode extends Node { return ctrl().in(0); // We become our input control return null; } + + @Override + boolean eq( Node n ) { return _idx == ((ProjNode)n)._idx; } + + @Override + int hash() { return _idx; } } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 453d028f..c949c2b2 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -1,9 +1,11 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; -import java.util.Collection; +import java.util.ArrayList; +import java.util.Arrays; import java.util.BitSet; public class RegionNode extends Node { @@ -34,22 +36,31 @@ public class RegionNode extends Node { public Node idealize() { if( inProgress() ) return null; int path = findDeadInput(); - if( path != 0 ) { - for( Node phi : _outputs ) - if( phi instanceof PhiNode ) - phi.delDef(path); - delDef(path); - - // If down to a single input, become that input - but also make all - // Phis an identity on *their* single input. - if( nIns()==2 ) { - for( Node phi : _outputs ) - if( phi instanceof PhiNode ) - // Currently does not happen, because no loops - throw Utils.TODO(); - return in(1); + if( path != 0 && + // Do not delete the entry path of a loop (ok to remove the back + // edge and make the loop a single-entry Region which folds away + // the Loop). Folding the entry path confused the loop structure, + // moving the backedge to the entry point. + !(this instanceof LoopNode loop && loop.entry()==in(path)) ) { + // Cannot use the obvious output iterator here, because a Phi + // deleting an input might recursively delete *itself*. This + // shuffles the output array, and we might miss iterating an + // unrelated Phi. So on rare occasions we repeat the loop to get + // all the Phis. + int nouts = 0; + while( nouts != nOuts() ) { + nouts = nOuts(); + for( int i=0; i<nOuts(); i++ ) + if( out(i) instanceof PhiNode phi && phi.nIns()==nIns() ) + phi.delDef(path); } - return this; + _idom = null; // Clear idom cache + return isDead() ? new ConstantNode(Type.XCONTROL) : delDef(path); + } + // If down to a single input, become that input + if( nIns()==2 && !hasPhi() ) { + _idom = null; // Clear idom cache + return in(1); // Collapse if no Phis; 1-input Phis will collapse on their own } return null; } @@ -61,11 +72,22 @@ public class RegionNode extends Node { return 0; // All inputs alive } + private boolean hasPhi() { + for( Node phi : _outputs ) + if( phi instanceof PhiNode ) + return true; + return false; + } + // Immediate dominator of Region is a little more complicated. private Node _idom; // Immediate dominator cache @Override Node idom() { - if( _idom != null ) return _idom; // Return cached copy - if( nIns()!=3 ) return null; // Fails for anything other than 2-inputs + if( _idom != null ) { + if( _idom.isDead() ) _idom=null; + else return _idom; // Return cached copy + } + if( nIns()==2 ) return in(1); // 1-input is that one input + if( nIns()!=3 ) return null; // Fails for anything other than 2-inputs // Walk the LHS & RHS idom trees in parallel until they match, or either fails Node lhs = in(1).idom(); Node rhs = in(2).idom(); @@ -77,11 +99,17 @@ public class RegionNode extends Node { } if( lhs==null ) return null; _idepth = lhs._idepth+1; - return (_idom=lhs); + if( !IterPeeps.midAssert() ) _idom=lhs; + return lhs; } // True if last input is null public final boolean inProgress() { - return in(nIns()-1) == null; + return nIns()>1 && 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<Type,Type> 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 extends Type> 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,59 +5,70 @@ 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; } public long value() { return _con; } @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; + } + } diff --git a/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 47cee096..75ee0b70 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -13,7 +13,7 @@ public class Chapter02Test { Parser parser = new Parser("return 1+2*3+-5;"); Node._disablePeephole = true; // disable peephole so we can observe full graph StopNode ret = parser.parse(); - assertEquals("return (1+((2*3)+(-5)));", ret.print()); + assertEquals("return ((1+(2*3))+(-5));", ret.print()); Node._disablePeephole = false; } diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 64ff153e..2246b927 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -40,7 +40,7 @@ public class Chapter03Test { @Test public void testVarDist() { - Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); "); + Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1);"); StopNode ret = parser.parse(); assertEquals("return 8;", ret.print()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 68d379a1..6ad3af15 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -21,7 +21,7 @@ else { } return a;"""); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); } @@ -36,7 +36,7 @@ if (arg == 1) { c = 4; } return c;""", TypeInteger.BOT); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return Phi(Region16,4,3);", ret.toString()); } @@ -64,7 +64,7 @@ if( arg==1 ) else b=a+1; return a+b;"""); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return ((arg*2)+Phi(Region20,2,3));", ret.toString()); } @@ -79,7 +79,7 @@ if( arg==1 ) else a=b+1; return a+b;"""); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return ((Phi(Region31,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); } @@ -99,7 +99,7 @@ else a=5; return a; """, TypeInteger.BOT); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region33,Phi(Region21,2,3),Phi(Region31,4,5));", stop.toString()); } @@ -129,7 +129,7 @@ if( arg==1 ) a=arg==3; } return a;"""); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return (arg==Phi(Region16,3,2));", ret.toString()); } @@ -169,6 +169,7 @@ return a;"""); } } + @Test public void testBadNum() { try { diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java index b858b83e..054e96e8 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -15,7 +15,7 @@ public class Chapter06Test { if( true ) return 2; return 1; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return 2;", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -29,7 +29,7 @@ if (arg) a = 2; return (arg < a) < 3; """); - StopNode stop = parser.parse(false); + StopNode stop = parser.parse().iterate(); assertEquals("return ((arg<Phi(Region12,2,1))<3);", stop.toString()); } @@ -44,7 +44,7 @@ else a=3; return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return 2;", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -64,7 +64,7 @@ if( a==2 ) else b=5; return b;""", TypeInteger.BOT); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region32,42,5);", stop.toString()); } @@ -83,8 +83,8 @@ if( arg==2 ) else b=5; return b;""", TypeInteger.BOT); - StopNode stop = parser.parse(); - assertEquals("return Phi(Region28,2,5);", stop.toString()); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Region29,2,5);", stop.toString()); } @Test @@ -123,7 +123,7 @@ else a=5; return a; """, TypeInteger.constant(1)); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return 3;", stop.toString()); } @@ -143,8 +143,8 @@ else a=5; return a; """, TypeInteger.BOT); - StopNode stop = parser.parse(); - assertEquals("return Phi(Region36,3,Phi(Region34,4,5));", stop.toString()); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Region37,3,Phi(Region35,4,5));", stop.toString()); } @Test @@ -163,7 +163,7 @@ else a=5; return a; """, TypeInteger.constant(1)); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return 3;", stop.toString()); } @@ -183,7 +183,7 @@ else a=5; return a; """, TypeInteger.constant(3)); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return 4;", stop.toString()); } @@ -199,8 +199,8 @@ if( arg ) { } return a+b; """); - StopNode ret = parser.parse(); - assertEquals("return Phi(Region22,4,1);", ret.toString()); + StopNode ret = parser.parse().iterate(); + assertEquals("return Phi(Region24,4,1);", ret.toString()); } @@ -216,7 +216,7 @@ if( arg ) { } return a+b; """, TypeInteger.constant(1)); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return 4;", ret.toString()); } @@ -232,7 +232,7 @@ if( arg ) { } return a+b; """, TypeInteger.constant(0)); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return 1;", ret.toString()); } @@ -250,8 +250,8 @@ if( arg ) { } return a+b+c; """); - StopNode ret = parser.parse(); - assertEquals("return (Phi(Region33,Phi(Region22,2,3),0)+Phi(Region,3,1));", ret.toString()); + StopNode ret = parser.parse().iterate(); + assertEquals("return (Phi(Region35,Phi(Region22,2,3),0)+Phi(Region,3,1));", ret.toString()); } @@ -269,7 +269,7 @@ if( arg ) { } return a+b+c; """, TypeInteger.constant(1)); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return 6;", ret.toString()); } @@ -287,7 +287,7 @@ if( arg ) { } return a+b+c; """, TypeInteger.constant(2)); - StopNode ret = parser.parse(); + StopNode ret = parser.parse().iterate(); assertEquals("return 5;", ret.toString()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/src/test/java/com/seaofnodes/simple/Chapter07Test.java index d691672e..adf10471 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -36,7 +36,7 @@ if(arg){}else{ } return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region22,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); } @@ -56,7 +56,7 @@ while(i < arg) { } return sum; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop8,0,Phi(Loop20,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); } @@ -93,7 +93,7 @@ while(a < 10) { } return b; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop8,2,(Phi(Region26,Phi_b,4)+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -128,7 +128,7 @@ while(a < 10) { } return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -156,7 +156,7 @@ int a = 1; while(arg) a = 2; return a; """); - StopNode stop = parser.parse(false); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop7,1,2);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -190,7 +190,7 @@ while(a < 10) { } return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop7,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -226,7 +226,7 @@ while(a < 10) { } return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop8,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 5d9d1545..cea6dd0f 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -4,22 +4,12 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.TypeInteger; import org.junit.Assert; import org.junit.Test; -import org.junit.Ignore; import static org.junit.Assert.*; public class Chapter08Test { @Test - @Ignore - public void testJig() { - Parser parser = new Parser(""" -// Insert test case here -"""); - StopNode stop = parser.parse(); - } - - @Test public void testEx6() { Parser parser = new Parser( """ @@ -32,7 +22,7 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region36,Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); Assert.assertEquals(5, GraphEvaluator.evaluate(stop, 1)); @@ -55,7 +45,7 @@ while(arg < 10) { } return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop7,1,Phi(Region42,Phi_a,(Phi_a+1)));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -74,7 +64,7 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region34,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -90,7 +80,7 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region25,Phi(Loop6,arg,(Phi_arg+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -109,7 +99,7 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -126,7 +116,7 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop6,arg,(Phi_arg+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof ProjNode); } @@ -142,15 +132,15 @@ while( arg < 10 ) { } return arg; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return arg;", stop.toString()); } @Test public void testRegress2() { Parser parser = new Parser("if(1) return 0; else while(arg>--arg) arg=arg+1; return 0;"); - StopNode stop = parser.parse(); - assertEquals("Stop[ return 0; return 0; ]", stop.toString()); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); } @Test @@ -177,7 +167,7 @@ while(arg < 10) { } return arg; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return arg;", stop.toString()); } @@ -194,7 +184,7 @@ while(arg < 10) { } return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Region28,Phi(Loop7,1,(Phi_a+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -210,9 +200,9 @@ while(1) { } return a; """); - StopNode stop = parser.parse(); + StopNode stop = parser.parse().iterate(); assertEquals("return (Phi(Loop7,1,Add)+1);", stop.toString()); - assertTrue(stop.ret().ctrl() instanceof RegionNode); + assertTrue(stop.ret().ctrl() instanceof ProjNode prj && prj._idx==1 ); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/src/test/java/com/seaofnodes/simple/Chapter09Test.java new file mode 100644 index 00000000..5567299a --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -0,0 +1,300 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Assert; +import org.junit.BeforeClass; +import org.junit.Test; +import org.junit.Ignore; + +import static org.junit.Assert.*; + +public class Chapter09Test { + + @Test + @Ignore + public void testJig() { + Parser parser = new Parser(""" +int v0=0; +arg=0; +while(v0) { + while(1) if(arg*arg*0==0) {} + while(0) {} + arg=1; +} +return 0; + """); + StopNode stop = parser.parse().iterate(); + } + + @Test + public void testGVN1() { + Parser parser = new Parser( + """ +int x = arg + arg; +if(arg < 10) { + return arg + arg; +} +else { + x = x + 1; +} +return x; + """); + StopNode stop = parser.parse(); + assertEquals("Stop[ return (arg*2); return (Mul+1); ]", stop.toString()); + Assert.assertEquals(2, GraphEvaluator.evaluate(stop, 1)); + Assert.assertEquals(23, GraphEvaluator.evaluate(stop, 11)); + } + + @Test + public void testGVN2() { + Parser parser = new Parser( + """ +return arg*arg-arg*arg; + """); + StopNode stop = parser.parse(); + assertEquals("return 0;", stop.toString()); + Assert.assertEquals(0, GraphEvaluator.evaluate(stop, 1)); + } + + @Test + public void testWorklist1() { + Parser parser = new Parser( + """ +int step = 1; +while (arg < 10) { + arg = arg + step + 1; +} +return arg; + """); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop7,arg,(Phi_arg+2));", stop.toString()); + Assert.assertEquals(11, GraphEvaluator.evaluate(stop, 1)); + } + + @Test + public void testWorklist2() { + Parser parser = new Parser( + """ +int cond = 0; +int one = 1; +while (arg < 10) { + if (cond) one = 2; + arg = arg + one*3 + 1; +} +return arg; + """); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop8,arg,(Phi_arg+4));", stop.toString()); + Assert.assertEquals(13, GraphEvaluator.evaluate(stop, 1)); + } + + @Test + public void testWorklist3() { + Parser parser = new Parser( + """ +int v1 = 0; +int v2 = 0; +int v3 = 0; +int v4 = 0; +int v5 = 0; +int v6 = 0; +int v7 = 0; +int v8 = 0; +while (arg) { + if (v1) v2 = 1; + if (v2) v3 = 1; + if (v3) v4 = 1; + if (v4) v5 = 1; + if (v5) v6 = 1; + if (v6) v7 = 1; + if (v7) v8 = 1; + arg = arg + v8 + 1; +} +return arg; + """); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop14,arg,(Phi_arg+1));", stop.toString()); + } + + @Test + public void testRegionPeepBug() { + Parser parser = new Parser( + """ +int v0=0; +int v1=0; +while(v1+arg) { + arg=0; + int v2=v0; + while(arg+1) {} + v0=1; + v1=v2; +} + """); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testWhile0() { + Parser parser = new Parser("while(0) continue; if(0) arg=0;"); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testWhile1() { + Parser parser = new Parser(""" +if(0) while(0) { + int arg=arg; + while(0) {} +} +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + + @Test + public void testPrecedence() { + Parser parser = new Parser("return 3-1+2;"); + StopNode stop = parser.parse().iterate(); + assertEquals("return 4;", stop.toString()); + } + + @Test + public void testSwap2() { + Parser parser = new Parser("return 1+(1+1);"); + StopNode stop = parser.parse().iterate(); + assertEquals("return 3;", stop.toString()); + } + + + @Test + public void testFuzz0() { + Parser parser = new Parser(""" +int one = 1; +int a = 0; +int zero = 0; +while(arg) { + a = -(one + a + 2); + arg = arg + 1; + one = one + zero; +} +return a; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop9,0,(-(Phi_a+3)));", stop.toString()); + } + + @Test + public void testFuzz1() { + Parser parser = new Parser(""" +while(1) {} +while(arg) break; +while(arg) arg=0; +arg=0; +int v0=0!=0<-0; +return -0+0+0; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + + @Test + public void testFuzz2() { + Parser parser = new Parser("return 0+-0;"); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + } + + @Test + public void testFuzz3() { + Parser parser = new Parser("int v0=0; while(0==69) while(v0) return 0;"); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz4() { + Parser parser = new Parser(""" +while(1) { + arg=0<=0; + if(1<0) while(arg==-0) arg=arg-arg; +} +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz5() { + Parser parser = new Parser(""" +{ + int v0=0; + while(1) + int v1=0--0; + while(v0) + break; + while(-v0) { + while(0+0+v0) continue; + break; + } + if(-0!=-0+0+v0) while(0+0+0+0) + break; +} +return 0!=0; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz6() { + Parser parser = new Parser(""" +int v0=0; +while(0==1) while(v0) + v0=1+v0; + """); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz7() { + Parser parser = new Parser(""" +while(1) {} +int v0=0; +while(v0) + {} +int v1=0; +while(1) + v1=1; +return v1+v0; + """); + StopNode stop = parser.parse().iterate(); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz8() { + Parser parser = new Parser("while(arg) arg = arg - 1; return arg;"); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop6,arg,(Phi_arg-1));", stop.toString()); + } + + @Test + public void testMeet() { + Type t1 = Type.TOP; + Type t2 = TypeInteger.TOP; + Assert.assertEquals(TypeInteger.TOP, t1.meet(t2)); + Assert.assertEquals(TypeInteger.TOP, t2.meet(t1)); + t1 = Type.BOTTOM; + t2 = TypeInteger.BOT; + Assert.assertEquals(Type.BOTTOM, t1.meet(t2)); + Assert.assertEquals(Type.BOTTOM, t2.meet(t1)); + } + +} diff --git a/src/test/java/com/seaofnodes/simple/FuzzerWrap.java b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java index 82a6a472..bb3bec1c 100644 --- a/src/test/java/com/seaofnodes/simple/FuzzerWrap.java +++ b/src/test/java/com/seaofnodes/simple/FuzzerWrap.java @@ -1,8 +1,8 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.fuzzer.Fuzzer; -import org.junit.Ignore; import org.junit.Test; +import org.junit.Ignore; import static org.junit.Assert.assertTrue; @@ -18,9 +18,18 @@ public class FuzzerWrap { @Ignore public void fuzzPeeps() { var fuzzer = new Fuzzer(); - for (int i=0; i<100000; i++) + for (int i=0; i<1000000; i++) fuzzer.fuzzPeeps(i); assertTrue(fuzzer.noExceptions()); } + + @Test + @Ignore + public void fuzzPeepTiming() { + var fuzzer = new Fuzzer(); + int max_nid=0; + for (int i=0; i<1000000; i++) + max_nid = fuzzer.fuzzPeepTiming(i, max_nid); + } } diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java index 5fcd8764..936fb41e 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java @@ -1,6 +1,8 @@ package com.seaofnodes.simple.fuzzer; import com.seaofnodes.simple.GraphEvaluator; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; import java.util.ArrayList; @@ -108,6 +110,45 @@ public class Fuzzer { } /** + * Run one test with the given seed, and check for peephole counts. + * @param seed The seed to use for generating this test case + */ + public int fuzzPeepTiming(long seed, int max_nids) { + var rand = new Random(seed); + var sb = new StringBuilder(); + new ScriptGenerator(rand, sb, true).genProgram(); + try { + var parser = new Parser(sb.toString()); + + var stop = parser.parse(); + int parse_peeps= Node.ITER_CNT; + int parse_nops = Node.ITER_NOP_CNT; + double parse_nop_ratio = (double)parse_nops/parse_peeps; + int nids = Node.UID(); + if( nids <= max_nids ) return max_nids; + + double parse_peeps_per_node = (double)parse_peeps/nids; + + stop.iterate(); + int iter_peeps= Node.ITER_CNT; + int iter_nops = Node.ITER_NOP_CNT; + double iter_nop_ratio = (double)iter_nops/iter_peeps; + double iter_peeps_per_node = (double)iter_peeps/nids; + + System.out.printf("%6d | Parsing: peeps: %5d, nops: %5d, ratio: %5.3f, last UID: %5d ps/node: %5.3f | Iter: peeps: %6d, nops: %6d, ratio: %5.3f, ps/node: %5.3f\n", + seed, + parse_peeps,parse_nops,parse_nop_ratio,nids,parse_peeps_per_node, + iter_peeps , iter_nops, iter_nop_ratio, iter_peeps_per_node); + return nids; + } catch (Throwable e) { + // ignore exceptions, let the normal fullPeeps catch and reduce, + // we're interested in valid program optimizations + } + return max_nids; + } + + + /** * Run one test with the given seed. * @param seed The seed to use for generating this test case */ @@ -118,6 +159,7 @@ public class Fuzzer { check(sb.toString(), valid); } + /** * Check that no exceptions happened. * @return true if no exception happened diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java index 37a57e11..f13a51e1 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java @@ -1,15 +1,79 @@ package com.seaofnodes.simple.fuzzer; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.node.StopNode; +import java.io.OutputStream; +import java.io.PrintStream; +import java.lang.invoke.MethodHandle; +import java.lang.invoke.MethodHandles; +import java.lang.reflect.Field; +import java.util.BitSet; + /** * Some utilities for the fuzzer. */ class FuzzerUtils { /** + * Get the value of a private field + */ + @SuppressWarnings("unchecked") + public static <T> T getFieldValue(Object obj, String name) throws NoSuchFieldException, IllegalAccessException { + return (T) (obj instanceof Class<?> clz ? getField(clz, name).get(null) : getField(obj.getClass(), name).get(obj)); + } + + /** + * Get access to a private field + */ + public static Field getField(Class<?> clz, String name) throws NoSuchFieldException { + var field = clz.getDeclaredField(name); + try { + field.setAccessible(true); + } catch (Throwable e) { + // Intentionally left empty + } + return field; + } + + /** + * Try to rethrow an exception or create a runtime exception and throw it. + */ + public static RuntimeException rethrow(Throwable e) { + if (e instanceof RuntimeException re) return re; + if (e instanceof Error er) throw er; + return new RuntimeException(e); + } + + /** + * Copy of Node.WVISIST + * Used to clear as exceptions might happen in the walk and left this bitset not cleared + */ + private static final BitSet NodeWalkVisit; + + /** + * Write access to Iterate.MID_ASSERT + * Exception could happen mid assert and left this at true. Used to reset to false prior to parsing. + */ + private static final MethodHandle set_MID_ASSERT; + + /** + * Some problems might trigger debug output. Suppress this output with a null print stream during fuzzing. + */ + public static final PrintStream NULL_PRINT_STREAM = new PrintStream(OutputStream.nullOutputStream()); + + static { + try { + NodeWalkVisit = getFieldValue(Node.class, "WVISIT"); + set_MID_ASSERT = MethodHandles.lookup().unreflectSetter(getField( IterPeeps.class, "MID_ASSERT")); + } catch (Exception e) { + throw new ExceptionInInitializerError(e); + } + } + + /** * Check that eiter one of the objects is null or that both are equal. */ private static boolean equalOrNull(Object a, Object b) { @@ -50,9 +114,25 @@ class FuzzerUtils { * Parse script with peepholes enabled or disabled */ public static StopNode parse(String script, boolean runPeeps) { - var parser = new Parser(script); - Node._disablePeephole = !runPeeps; - return parser.parse(); + var err = System.err; + var out = System.out; + try { + System.setErr(NULL_PRINT_STREAM); + System.setOut(NULL_PRINT_STREAM); + try { + set_MID_ASSERT.invokeExact(false); + } catch (Throwable e) { + throw rethrow(e); + } + var parser = new Parser(script); + Node._disablePeephole = !runPeeps; + var stop = parser.parse(); + return runPeeps ? stop.iterate() : stop; + } finally { + NodeWalkVisit.clear(); + System.setErr(err); + System.setOut(out); + } } } diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java index b7fc18ec..2ef0a3fd 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java @@ -32,8 +32,8 @@ public class Reducer { new Replace(Pattern.compile("\\{(?:[^{}]|\\{})+}"), "{}"), new Replace(Pattern.compile("\\{((?:[^{}]|\\{})+)}"), "$1"), new Replace(Pattern.compile("\\(([^()]+)\\)"), "$1"), - new Replace(Pattern.compile("\\b\\w+\\b"), "1"), new Replace(Pattern.compile("\\b\\w+\\b"), "0"), + new Replace(Pattern.compile("\\b(?:[^\\W0]|\\w\\w+)\\b"), "1"), new Replace(Pattern.compile("\\d+\\+"), ""), new Replace(Pattern.compile("\\+\\d+"), ""), new Replace(Pattern.compile("(?<=\\n|^)[^\\n]*(?=\\n|$)"), "\n"), diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index 148c2319..ad98f7e2 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -16,20 +16,6 @@ import java.util.Random; public class ScriptGenerator { /** - * Get the list of keywords from the parser. - */ - @SuppressWarnings("unchecked") - private static HashSet<String> getKeywords() { - try { - var field = Parser.class.getDeclaredField("KEYWORDS"); - field.setAccessible(true); - return (HashSet<String>) field.get(new Parser("")); - } catch (Throwable e) { - throw new ExceptionInInitializerError(e); - } - } - - /** * Number of spaces per indentation */ private static final int INDENTATION = 4; @@ -40,7 +26,15 @@ public class ScriptGenerator { /** * List of keywords not valid for identifiers. */ - private static final HashSet<String> KEYWORDS = getKeywords(); + private static final HashSet<String> KEYWORDS; + + static { + try { + KEYWORDS = FuzzerUtils.getFieldValue(new Parser(""), "KEYWORDS"); + } catch (Throwable e) { + throw new ExceptionInInitializerError(e); + } + } /** * Flag for a statement that it does not pass on control flow to the next statement. @@ -83,11 +77,11 @@ public class ScriptGenerator { /** * The depth of blocks allowed. */ - private int depth = 7; + private int depth = 20; /** * The depth of expressions allowed. */ - private int exprDepth = 3; + private int exprDepth = 30; /** * Current variables in scope. */ @@ -141,7 +135,7 @@ public class ScriptGenerator { * @return The random name generated */ private StringBuilder getRandomName() { - int len = random.nextInt(10) + 1; + int len = random.nextInt(30) + 1; StringBuilder sb = new StringBuilder(len); sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()-10))); for (int i=1; i<len; i++) @@ -203,7 +197,7 @@ public class ScriptGenerator { * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the last statement generated */ public int genStatements() { - var num = random.nextInt(10); + var num = random.nextInt(10); // (30); for (int i=0; i<num; i++) { printIndentation(); var stop = genStatement(); |