diff options
Diffstat (limited to 'chapter17/src/main/java')
5 files changed, 129 insertions, 63 deletions
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java index 371bddf1..799e0629 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java @@ -2,7 +2,6 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; -import static com.seaofnodes.simple.Utils.TODO; import java.util.*; @@ -91,7 +90,7 @@ public class Parser { public final Stack<ScopeNode> _xScopes = new Stack<>(); ScopeNode _continueScope; - ScopeNode _breakScope; + ScopeNode _breakScope; // Merge all the while-breaks here // Mapping from a type name to a Type. The string name matches // `type.str()` call. No TypeMemPtrs are in here, because Simple does not @@ -169,7 +168,7 @@ public class Parser { if( ctrl()._type==Type.CONTROL ) STOP.addReturn(new ReturnNode(ctrl(), ZERO, _scope).peephole()); - _scope.pop(); + _scope.kill(); _xScopes.pop(); for( StructNode init : INITS.values() ) init.unkeep().kill(); @@ -269,7 +268,7 @@ public class Parser { // the loop predicate. Note that body Scope is still our current scope. ctrl(ifF); _xScopes.push(_breakScope = _scope.dup()); - _breakScope.upcast(ifF,pred,true); // Up-cast predicate + _breakScope.addGuards(ifF,pred,true); // Up-cast predicate // No continues yet _continueScope = null; @@ -277,8 +276,9 @@ public class Parser { // Parse the true side, which corresponds to loop body // Our current scope is the body Scope ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection - _scope.upcast(ifT,pred,false); // Up-cast predicate + _scope.addGuards(ifT,pred,false); // Up-cast predicate parseStatement(); // Parse loop body + _scope.removeGuards(ifT); // Merge the loop bottom into other continue statements if (_continueScope != null) { @@ -330,8 +330,17 @@ public class Parser { private void checkLoopActive() { if (_breakScope == null) throw Parser.error("No active loop for a break or continue"); } - private Node parseBreak () { checkLoopActive(); return ( _breakScope = require(jumpTo( _breakScope ),";")); } private Node parseContinue() { checkLoopActive(); return (_continueScope = require(jumpTo( _continueScope ),";")); } + private Node parseBreak () { + checkLoopActive(); + // At the time of the break, and loop-exit conditions are only valid if + // they are ALSO valid at the break. It is the intersection of + // conditions here, not the union. + _breakScope.removeGuards(_breakScope.ctrl()); + _breakScope = require(jumpTo(_breakScope ),";"); + _breakScope.addGuards(_breakScope.ctrl(), null, false); + return _breakScope; + } /** * Parses a statement @@ -365,8 +374,10 @@ public class Parser { // Parse the true side ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection - _scope.upcast(ifT,pred,false); // Up-cast predicate + _scope.addGuards(ifT,pred,false); // Up-cast predicate Node lhs = stmt ? parseStatement() : parseExpression().keep(); // Parse true-side + _scope.removeGuards(ifT); + ScopeNode tScope = _scope; // Parse the false side @@ -374,11 +385,12 @@ public class Parser { ctrl(ifF.unkeep()); // Ctrl token is now set to ifFalse projection // Up-cast predicate, even if not else clause, because predicate can // remain true if the true clause exits: `if( !ptr ) return 0; return ptr.fld;` - _scope.upcast(ifF,pred,true); + _scope.addGuards(ifF,pred,true); boolean doRHS = match(fside); Node rhs = doRHS ? (stmt ? parseStatement() : parseExpression()) : (stmt ? null : con(lhs._type.makeZero())); + _scope.removeGuards(ifF); if( doRHS ) fScope = _scope; pred.unkeep(); @@ -392,7 +404,7 @@ public class Parser { _xScopes.pop(); // Discard pushed from graph display RegionNode r = ctrl(tScope.mergeScopes(fScope)); - Node ret = stmt ? r : new PhiNode("",lhs._type.meet(rhs._type),r,lhs,rhs).peephole(); + Node ret = stmt ? r : peep(new PhiNode("",lhs._type.meet(rhs._type),r,lhs,rhs)); r.peephole(); return ret; } @@ -461,7 +473,7 @@ public class Parser { // Auto-widen int to float if( expr._type instanceof TypeInteger && t instanceof TypeFloat ) - expr = new ToFloatNode(expr).peephole(); + expr = peep(new ToFloatNode(expr)); // Auto-narrow wide ints to narrow ints expr = zsMask(expr,t); // Auto-deepen forward ref types @@ -653,7 +665,7 @@ public class Parser { else if( match("^") ) lhs = new XorNode(lhs,null); else break; lhs.setDef(2,parseComparison()); - lhs = lhs.peephole(); + lhs = peep(lhs); } return lhs; } @@ -681,9 +693,9 @@ public class Parser { else break; // Peepholes can fire, but lhs is already "hooked", kept alive lhs.setDef(idx,parseShift()); - lhs = lhs.widen().peephole(); + lhs = peep(lhs.widen()); if( negate ) // Extra negate for != - lhs = new NotNode(lhs).peephole(); + lhs = peep(new NotNode(lhs)); } return lhs; } @@ -705,7 +717,7 @@ public class Parser { else if( match(">>") ) lhs = new SarNode(lhs,null); else break; lhs.setDef(2,parseAddition()); - lhs = lhs.widen().peephole(); + lhs = peep(lhs.widen()); } return lhs; } @@ -726,7 +738,7 @@ public class Parser { else if( match("-") ) lhs = new SubNode(lhs,null); else break; lhs.setDef(2,parseMultiplication()); - lhs = lhs.widen().peephole(); + lhs = peep(lhs.widen()); } return lhs; } @@ -747,7 +759,7 @@ public class Parser { else if( match("/") ) lhs = new DivNode(lhs,null); else break; lhs.setDef(2,parseUnary()); - lhs = lhs.widen().peephole(); + lhs = peep(lhs.widen()); } return lhs; } @@ -761,8 +773,8 @@ public class Parser { * @return a unary expression {@link Node}, never {@code null} */ private Node parseUnary() { - if (match("-")) return new MinusNode(parseUnary()).widen().peephole(); - if (match("!")) return new NotNode(parseUnary()).peephole(); + if (match("-")) return peep(new MinusNode(parseUnary()).widen()); + if (match("!")) return peep(new NotNode(parseUnary())); return parsePostfix(parsePrimary()); } @@ -787,7 +799,7 @@ public class Parser { if( matchx("++") || matchx("--") ) { if( n._final ) throw error("Cannot reassign final '"+n._name+"'"); - _scope.update(n,new AddNode(rvalue,con( _lexer.peek(-1)=='+' ? 1 : -1)).peephole()); + _scope.update(n,peep(new AddNode(rvalue,con( _lexer.peek(-1)=='+' ? 1 : -1)))); } return rvalue.unkeep(); } @@ -882,7 +894,7 @@ public class Parser { private Node newArray(TypeStruct ary, Node len) { int base = ary.aryBase (); int scale= ary.aryScale(); - Node size = new AddNode(con(base),new ShlNode(len,con(scale)).peephole()).peephole(); + Node size = peep(new AddNode(con(base),peep(new ShlNode(len,con(scale))))); ALTMP.clear(); ALTMP.add(len); ALTMP.add(con(ary._fields[1]._type.makeInit())); return newStruct(ary,size,0,ALTMP); } @@ -935,7 +947,7 @@ public class Parser { Node off = (name.equals("[]") // If field is an array body // Array index math - ? new AddNode(con(base.aryBase()),new ShlNode(require(parseExpression(),"]"),con(base.aryScale())).peephole()).peephole() + ? peep(new AddNode(con(base.aryBase()),peep(new ShlNode(require(parseExpression(),"]"),con(base.aryScale()))))) // Struct field offsets are hardwired : con(base.offset(fidx))).keep(); @@ -958,20 +970,20 @@ public class Parser { // Structs don't need this; they only need a NPE check which is // done via the type system. if( base.isAry() ) load.setDef(0,ctrl()); - load = load.peephole(); + load = peep(load); // ary[idx]++ if( matchx("++") || matchx("--") ) { if( f._final && !f._fname.equals("[]") ) throw error("Cannot reassign final '"+f._fname+"'"); - Node inc = new AddNode(load,con( _lexer.peek(-1)=='+' ? 1 : -1)).peephole(); + Node inc = peep(new AddNode(load,con( _lexer.peek(-1)=='+' ? 1 : -1))); Node val = zsMask(inc,f._type); Node st = new StoreNode(name, f._alias, f._type, memAlias(f._alias), expr, off, val, false); // Arrays include control, as a proxy for a safety range check. // Structs don't need this; they only need a NPE check which is // done via the type system. if( base.isAry() ) st.setDef(0,ctrl()); - memAlias(f._alias, st.peephole()); + memAlias(f._alias, peep(st)); // And use the original loaded value as the result } if( off.unkeep().isDead() ) off.kill(); @@ -987,16 +999,16 @@ public class Parser { if( !(val._type instanceof TypeFloat tval && t instanceof TypeFloat t0 && !tval.isa(t0)) ) return val; // Float rounding - return new RoundF32Node(val).peephole(); + return peep(new RoundF32Node(val)); } if( t0._min==0 ) // Unsigned - return new AndNode(val,con(t0._max)).peephole(); + return peep(new AndNode(val,con(t0._max))); // Signed extension int shift = Long.numberOfLeadingZeros(t0._max)-1; Node shf = con(shift); if( shf._type==TypeInteger.ZERO ) return val; - return new SarNode(new ShlNode(val,shf.keep()).peephole(),shf.unkeep()).peephole(); + return peep(new SarNode(peep(new ShlNode(val,shf.keep())),shf.unkeep())); } @@ -1011,6 +1023,10 @@ public class Parser { private ConstantNode parseLiteral() { return con(_lexer.parseNumber()); } public static Node con( long con ) { return con(TypeInteger.constant(con)); } public static ConstantNode con( Type t ) { return (ConstantNode)new ConstantNode(t).peephole(); } + public Node peep( Node n ) { + // Peephole, then improve with lexically scoped guards + return _scope.upcastGuard(n.peephole()); + } ////////////////////////////////// // Utilities for lexical analysis diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java index 35dbc19e..3827fdac 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java @@ -267,6 +267,10 @@ public abstract class Node implements OutNode { } // Test "keep" status public boolean iskeep() { return _outputs.find(null) != -1; } + public void unkill() { + if( unkeep().isUnused() ) + kill(); + } // Replace self with nnn in the graph, making 'this' go dead diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/NotNode.java index ffd3e01e..664d7c7b 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -28,15 +28,14 @@ public class NotNode extends Node { // top->top, bot->bot, null->1, *void->0, not-null ptr->0, ptr/nil->bot // If input in null then true // If input is not null ptr then false - if( p0 == TypeMemPtr.TOP ) return TypeInteger.TOP; - if( p0 == TypeMemPtr.NULLPTR ) return TypeInteger.constant(1); - if( !p0._nil ) return TypeInteger.constant(0); - return TypeInteger.BOT; + if( p0 == TypeMemPtr.NULLPTR ) return TypeInteger.TRUE; + if( !p0._nil ) return TypeInteger.FALSE; + return TypeInteger.BOOL; case Type t: if( t0.getClass() != Type.class ) // Only doing NOT on ints and ptrs throw Utils.TODO(); - return t0==Type.TOP ? Type.TOP : Type.BOTTOM; + return TypeInteger.BOOL; } } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java index a55bb479..9e0f46cb 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -18,7 +18,7 @@ public class RegionNode extends CFGNode { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { - return sb.append(label()).append(_nid); + return sb.append(label()); } @Override public boolean isMultiHead() { return true; } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 2fc495c5..5a735515 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -32,12 +32,19 @@ public class ScopeNode extends ScopeMinNode { // True if parsing inside of a constructor public final Ary<Boolean> _inCons; + // Extra guards; tested predicates and casted results + private final Ary<Node> _guards; + // A new ScopeNode - public ScopeNode() { _vars = new Ary<>(Var.class); _lexSize = new Ary<>(Integer.class); _inCons = new Ary<>(Boolean.class); } + public ScopeNode() { + _vars = new Ary<>(Var .class); + _lexSize= new Ary<>(Integer.class); + _inCons = new Ary<>(Boolean.class); + _guards = new Ary<>(Node .class); + } @Override public String label() { return "Scope"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { sb.append("Scope[ "); @@ -187,9 +194,15 @@ public class ScopeNode extends ScopeMinNode { // 1) duplicate the name bindings of the ScopeNode across all stack levels // 2) Make the new ScopeNode a user of all the nodes bound // 3) Ensure that the order of defs is the same to allow easy merging - dup._vars.addAll(_vars); + dup._vars .addAll(_vars ); dup._lexSize.addAll(_lexSize); dup._inCons .addAll(_inCons ); + dup._guards .addAll(_guards ); + // The dup'd guards all need dup'd keepers, to keep proper accounting + // when later removing all guards + for( Node n : _guards ) + if( !(n instanceof CFGNode) ) + n.keep(); dup.addDef(ctrl()); // Control input is just copied // Memory input is a shallow copy @@ -274,44 +287,78 @@ public class ScopeNode extends ScopeMinNode { // Up-casting: using the results of an If to improve a value. // E.g. "if( ptr ) ptr.field;" is legal because ptr is known not-null. - - // This Scope looks for direct variable uses, or certain simple - // combinations, and replaces the variable with the upcast variant. - public Node upcast( Node ctrl, Node pred, boolean invert ) { - if( ctrl._type == Type.XCONTROL || pred.isDead() ) - return null; // Dead, do not do anything + public void addGuards( Node ctrl, Node pred, boolean invert ) { + assert ctrl instanceof CFGNode; + _guards.add(ctrl); // Marker to distinguish 0,1,2 guards + // add pred & its cast to the normal input list, with special Vars + if( ctrl._type == Type.XCONTROL || pred==null || pred.isDead() ) + return; // Dead, do not add any guards // Invert the If conditional if( invert ) pred = pred instanceof NotNode not ? not.in(1) : IterPeeps.add(new NotNode(pred).peephole()); - - // Direct use of a value as predicate. This is a zero/null test. - if( _inputs.find(pred) != -1 ) { - if( !(pred._type instanceof TypeMemPtr tmp) ) - // Must be an `int`, since int and ptr are the only two value types - // being tested. No representation for a generic not-null int, so no upcast. - return null; - if( tmp.isa(TypeMemPtr.VOIDPTR) ) - return null; // Already not-null, no reason to upcast - // Upcast the ptr to not-null ptr, and replace in scope - return replace(pred,new CastNode(TypeMemPtr.VOIDPTR,ctrl,pred).peephole()); + // This is a zero/null test. + // Compute the positive test type. + Type tnz = pred._type.nonZero(); + Type tcast = tnz.join(pred._type); + if( tcast != pred._type ) { + Node cast = new CastNode(tnz,ctrl,pred.keep()).peephole().keep(); + _guards.add(pred); + _guards.add(cast); + replace(pred,cast); } + // Compute the negative test type. if( pred instanceof NotNode not ) { - // Direct use of a !value as predicate. This is a zero/null test. - if( _inputs.find(not.in(1)) != -1 ) { - Type tinit = not.in(1)._type.makeInit(); - if( not.in(1)._type.isa(tinit) ) return null; // Already zero/null, no reason to upcast - return replace(not.in(1), new ConstantNode(tinit).peephole()); + Node npred = not.in(1); + Type tzero = npred._type.makeZero(); + Type tzcast= tzero.join(npred._type); + if( tzcast != npred._type ) { + Node cast = new CastNode(tzero,ctrl,npred.keep()).peephole().keep(); + _guards.add(npred); + _guards.add( cast); + replace(npred,cast); } } - // Apr/9/2024: Attempted to replace X with Y if guarded by a test of - // X==Y. This didn't seem to help very much, or at least in the test - // cases seen so far was a very minor help. + } - // No upcast - return null; + // Remove matching pred/cast pairs from this guarded region. + public void removeGuards( Node ctrl ) { + assert ctrl instanceof CFGNode; + // 0,1 or 2 guards + while( true ) { + Node g = _guards.pop(); + if( g == ctrl ) break; + if( g instanceof CFGNode ) continue; + g .unkill(); // Pop/kill cast + _guards.pop().unkill(); // Pop/kill pred + } } + // If we find a guarded instance of pred, replace with the upcasted version + public Node upcastGuard( Node pred ) { + // If finding an instanceof pred, replace with cast. + // Otherwise, just pred itself. + int i = _guards._len; + while( i > 0 ) { + Node cast = _guards.at(--i); + if( cast instanceof CFGNode ) continue; // Marker between guard sets + Node xpred = _guards.at(--i); + if( xpred == pred ) + return cast; + } + return pred; + } + + // Kill guards also + @Override public void kill() { + for( Node n : _guards ) + if( !(n instanceof CFGNode) ) + n.unkill(); + _guards.clear(); + super.kill(); + } + + private Node replace( Node old, Node cast ) { assert old!=null && old!=cast; for( int i=0; i<nIns(); i++ ) |