diff options
Diffstat (limited to 'chapter17/src/main/java/com')
12 files changed, 125 insertions, 69 deletions
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter17/src/main/java/com/seaofnodes/simple/IterPeeps.java index 96ae350e..81b89513 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; import java.util.ArrayList; import java.util.Arrays; @@ -113,9 +114,12 @@ public abstract class IterPeeps { 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; + Node m = n; + if( n.compute().isa(n._type) ) { // Types must be forwards, even if on worklist + if( WORK.on(n) ) return null; + m = n.peepholeOpt(); + if( m==null ) return null; + } System.err.println("BREAK HERE FOR BUG"); return m; }); diff --git a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java index fac012a4..371bddf1 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java @@ -150,7 +150,7 @@ public class Parser { public static Node find(int nid) { return START.find(nid); } private Node ctrl() { return _scope.ctrl(); } - private Node ctrl(Node n) { return _scope.ctrl(n); } + private <N extends Node> N ctrl(N n) { return _scope.ctrl(n); } public StopNode parse() { return parse(false); } public StopNode parse(boolean show) { @@ -165,7 +165,7 @@ public class Parser { _scope.define(ScopeNode.ARG0, TypeInteger.BOT, false, new ProjNode(START, 2, ScopeNode.ARG0).peephole()); // Parse whole program - parseBlock(); + parseBlock(false); if( ctrl()._type==Type.CONTROL ) STOP.addReturn(new ReturnNode(ctrl(), ZERO, _scope).peephole()); @@ -189,9 +189,9 @@ public class Parser { * Does not parse the opening or closing '{}' * @return a {@link Node} or {@code null} */ - private Node parseBlock() { + private Node parseBlock(boolean inCon) { // Enter a new scope - _scope.push(); + _scope.push(inCon); while (!peek('}') && !_lexer.isEOF()) parseStatement(); // Exit scope @@ -210,7 +210,7 @@ public class Parser { private Node parseStatement() { if( false ) return null; else if (matchx("return") ) return parseReturn(); - else if (match ("{") ) return require(parseBlock(),"}"); + else if (match ("{") ) return require(parseBlock(false),"}"); else if (matchx("if") ) return parseIf(); else if (matchx("while") ) return parseWhile(); else if (matchx("break") ) return parseBreak(); @@ -324,7 +324,7 @@ public class Parser { return cur; // toScope is either the break scope, or a scope that was created here assert toScope._lexSize.size() <= _breakScope._lexSize.size(); - toScope.ctrl(toScope.mergeScopes(cur)); + toScope.ctrl(toScope.mergeScopes(cur).peephole()); return toScope; } @@ -342,9 +342,16 @@ public class Parser { * @return a {@link Node}, never {@code null} */ private Node parseIf() { - require("("); // Parse predicate - var pred = require(parseExpression(), ")").keep(); + require("("); + var pred = require(parseExpression(), ")"); + return parseTrinary(pred,true,"else"); + } + + // Parse a conditional expression, merging results. + private Node parseTrinary( Node pred, boolean stmt, String fside ) { + pred.keep(); + // IfNode takes current control and predicate Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes @@ -359,19 +366,24 @@ public class Parser { // Parse the true side ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection _scope.upcast(ifT,pred,false); // Up-cast predicate - parseStatement(); // Parse true-side + Node lhs = stmt ? parseStatement() : parseExpression().keep(); // Parse true-side ScopeNode tScope = _scope; // Parse the false side _scope = fScope; // Restore scope, then parse else block if any ctrl(ifF.unkeep()); // Ctrl token is now set to ifFalse projection - _scope.upcast(ifF,pred,true); // Up-cast predicate - if (matchx("else")) { - parseStatement(); + // 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); + boolean doRHS = match(fside); + Node rhs = doRHS + ? (stmt ? parseStatement() : parseExpression()) + : (stmt ? null : con(lhs._type.makeZero())); + if( doRHS ) fScope = _scope; - } pred.unkeep(); + // Check for `if(pred) int x=17;` if( tScope.nIns() != ndefs || fScope.nIns() != ndefs ) throw error("Cannot define a new name on one arm of an if"); @@ -379,10 +391,12 @@ public class Parser { _scope = tScope; _xScopes.pop(); // Discard pushed from graph display - return ctrl(tScope.mergeScopes(fScope)); + RegionNode r = ctrl(tScope.mergeScopes(fScope)); + Node ret = stmt ? r : new PhiNode("",lhs._type.meet(rhs._type),r,lhs,rhs).peephole(); + r.peephole(); + return ret; } - /** * Parses a return statement; "return" already parsed. * The $ctrl edge is killed. @@ -410,42 +424,39 @@ public class Parser { /** Parse: name [=expr] */ - private Node parseAsgn(Type t, boolean xfinal) { - boolean isDecl = t!=null; // Having a type is a declaration, missing one is updating a prior name + // t==null ==>> re-assign: !final, expr=parse(), t:=def ._type + // t==TOP ==>> value : final, expr=parse(), t:=expr._type + // t==BOT ==>> variable : !final, expr=parse(), t:=expr._type + // t==type && !expr ==>> declaratn: !final, expr=makeInit; t:=type; + // t==type && expr ==>> declaratn: final=inCon && noBang, expr=parse() ; t:=type; + private Node parseAsgn(Type t, boolean hasBang) { + boolean isDecl = t!=null; int old = _lexer._position; String name = requireId(); - Node expr; - if( peek(';') || peek(',') ) { - // Bare "name" is not allowed - if( t==null ) throw errorSyntax("expression"); - // Does this declaration need an initializer and not getting one? - Type init = xfinal || t instanceof TypeMemPtr tmp && !tmp._nil - // Must be initialized in the "new" constructor - ? Type.TOP - // Else takes the default - : t.makeInit(); - // "var" and "val" require an expression to infer - if( init == null ) throw errorSyntax("expression"); - expr = con(init); - - } else if( !match("=") ) { // Something else - _lexer._position = old; - return null; - } else - expr = parseExpression(); + + boolean hasType = t!=null && t!=Type.TOP && t!=Type.BOTTOM; // User written type + boolean hasExpr = !(peek(';') || peek(',')); // Expression follows + if( hasExpr && !match("=") ) // Something else + { _lexer._position = old; return null; } + if( !hasExpr && t==Type.BOTTOM ) throw errorSyntax("expression"); + Node expr = hasExpr ? parseExpression() : con(t.makeInit()); + boolean xfinal = t==Type.TOP || (hasType && hasExpr && !hasBang && _scope.inCon()); // Defining a new variable vs updating an old one - if( !isDecl ) { // Assigning over an existing name - // Lookup + if( t==null ) { + // Lookup old variable ScopeMinNode.Var def = _scope.lookup(name); if( def==null ) throw error("Undefined name '" + name + "'"); // TOP fields are for late-initialized fields; these have never // been written to, and this must be the final write. Other writes - // need to check the final bit. - if( _scope.in(def._idx)._type!=Type.TOP && def._final ) + // outside the constructor need to check the final bit. + if( _scope.in(def._idx)._type!=Type.TOP && def._final && !_scope.inCon() ) throw error("Cannot reassign final '"+name+"'"); t = def.type(); // Declared field type + } else if( !hasType && hasExpr ) { + // Discovered type from expression + t = expr._type.glb(); } // Auto-widen int to float @@ -475,10 +486,7 @@ public class Parser { /** Parse final: [!]asgn */ private Node parseFinal(Type t) { - // TOP is a "val" marker - uses type inference for a "value", i.e. a final. - // BOT is a "var" marker - uses type inference for a "variable", i.e. not final - boolean xfinal = t==Type.TOP || (t!=null && match("!")); - return parseAsgn(t,xfinal); + return parseAsgn(t,match("!")); } /** @@ -526,7 +534,7 @@ public class Parser { throw errorSyntax("struct '" + typeName + "' cannot be redefined"); // A Block scope parse, and inspect the scope afterward for fields. - _scope.push(); + _scope.push(true); require("{"); while (!peek('}') && !_lexer.isEOF()) parseStatement(); @@ -562,6 +570,9 @@ public class Parser { if( tname==null ) return null; // Convert the type name to a type. Type t0 = TYPES.get(tname); + // No new types as keywords + if( t0 == null && KEYWORDS.contains(tname) ) + { _lexer._position = old1; return null; } Type t1 = t0 == null ? TypeMemPtr.make(TypeStruct.makeFRef(tname)) : t0; // Null: assume a forward ref type // Nest arrays and '?' as needed while( true ) { @@ -616,11 +627,14 @@ public class Parser { * Parse an expression of the form: * * <pre> - * expr : compareExpr + * expr : bitwise [? expr [: expr]] * </pre> * @return an expression {@link Node}, never {@code null} */ - private Node parseExpression() { return parseBitwise(); } + private Node parseExpression() { + Node expr = parseBitwise(); + return match("?") ? parseTrinary(expr,false,":") : expr; + } /** * Parse an bitwise expression @@ -823,7 +837,7 @@ public class Parser { for( int i=0; i<fs.length; i++ ) _scope.define(fs[i]._fname, fs[i]._type, fs[i]._final, s.in(i)); // Parse the constructor body - parseBlock(); + parseBlock(true); require("}"); init = _scope._inputs; } @@ -948,6 +962,8 @@ public class Parser { // 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 val = zsMask(inc,f._type); Node st = new StoreNode(name, f._alias, f._type, memAlias(f._alias), expr, off, val, false); diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/AddNode.java index f3b213fb..0834a381 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -36,7 +36,7 @@ public class AddNode extends Node { return TypeInteger.BOT; } - private static boolean overflow( long x, long y ) { + static boolean overflow( long x, long y ) { if( (x ^ y ) < 0 ) return false; // unequal signs, never overflow return (x ^ (x + y)) < 0; // sum has unequal signs, so overflow } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 9e9d6970..3513f265 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -28,15 +28,6 @@ public abstract class CFGNode extends Node { // Block head is Start, Region, CProj, but not e.g. If, Return, Stop public boolean blockHead() { return false; } - // Should be exactly 1 tail from a block head - public CFGNode blockTail() { - assert blockHead(); - for( Node n : _outputs ) - if( n instanceof CFGNode cfg ) - return cfg; - return null; - } - // ------------------------------------------------------------------------ /** * Immediate dominator tree depth, used to approximate a real IDOM during diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 2c0afda2..555b9ae4 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -87,6 +87,8 @@ public class LoadNode extends MemOpNode { break outer; // Cannot tell, ptr not related to New mem = nnn1.in(_alias);// Bypass unrelated New break; + } else if( mproj.in(0) instanceof StartNode ) { + break outer; } else throw Utils.TODO(); default: throw Utils.TODO(); @@ -101,7 +103,11 @@ public class LoadNode extends MemOpNode { // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; if( mem() instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 && - off() instanceof ConstantNode ) { + // Offset can be hoisted + off() instanceof ConstantNode && + // Pointer can be hoisted + hoistPtr(ptr,memphi) ) { + // Profit on RHS/Loop backedge if( profit(memphi,2) || // Else must not be a loop to count profit on LHS. @@ -125,6 +131,25 @@ public class LoadNode extends MemOpNode { ptr2 instanceof ProjNode && ptr2.in(0) instanceof NewNode; } + private static boolean hoistPtr(Node ptr, PhiNode memphi ) { + // Can I hoist ptr above the Region? + if( !(memphi.region() instanceof RegionNode r) ) + return false; // Dead or dying Region/Phi + // If ptr from same Region, then yes, just use hoisted split pointers + if( ptr instanceof PhiNode pphi && pphi.region() == r ) + return true; + + // No, so can we lift this ptr? + CFGNode cptr = ptr.cfg0(); + if( cptr != null ) + // Pointer is controlled high + // TODO: Really needs to be the LCA of all inputs is high + return cptr.idepth() <= r.idepth(); + + // Dunno without a longer walk + return false; + } + // Profitable if we find a matching Store on this Phi arm. private boolean profit(PhiNode phi, int idx) { Node px = phi.in(idx); 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 c67fb910..35dbc19e 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java @@ -153,7 +153,7 @@ public abstract class Node implements OutNode { * @param new_def the new definition * @return new_def for flow coding */ - public Node setDef(int idx, Node new_def ) { + public <N extends Node> N setDef(int idx, N new_def ) { unlock(); Node old_def = in(idx); if( old_def == new_def ) return new_def; // No change 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 f7446c51..2fc495c5 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -29,9 +29,11 @@ public class ScopeNode extends ScopeMinNode { // Since of each nested lexical scope public final Ary<Integer> _lexSize; + // True if parsing inside of a constructor + public final Ary<Boolean> _inCons; // A new ScopeNode - public ScopeNode() { _vars = new Ary<>(Var.class); _lexSize = new Ary<>(Integer.class); } + public ScopeNode() { _vars = new Ary<>(Var.class); _lexSize = new Ary<>(Integer.class); _inCons = new Ary<>(Boolean.class); } @Override public String label() { return "Scope"; } @@ -75,17 +77,24 @@ public class ScopeNode extends ScopeMinNode { * * @return Node that was bound */ - public Node ctrl(Node n) { return setDef(0,n); } + public <N extends Node> N ctrl(N n) { return setDef(0,n); } - public void push() { + public void push() { push(false); } + public void push(boolean inCon) { + assert _lexSize._len==_inCons._len; _lexSize.push(_vars.size()); + _inCons.push(inCon); } public void pop() { + assert _lexSize._len==_inCons._len; int n = _lexSize.pop(); + _inCons.pop(); popUntil(n); _vars.setLen(n); } + public boolean inCon() { return _inCons.last(); } + // Find name in reverse, return an index into _vars or -1. Linear scan // instead of hashtable, but probably doesn't matter until the scan // typically hits many dozens of variables. @@ -180,6 +189,7 @@ public class ScopeNode extends ScopeMinNode { // 3) Ensure that the order of defs is the same to allow easy merging dup._vars.addAll(_vars); dup._lexSize.addAll(_lexSize); + dup._inCons .addAll(_inCons ); dup.addDef(ctrl()); // Control input is just copied // Memory input is a shallow copy @@ -208,13 +218,13 @@ public class ScopeNode extends ScopeMinNode { * @param that The ScopeNode to be merged into this * @return A new node representing the merge point */ - public Node mergeScopes(ScopeNode that) { + public RegionNode mergeScopes(ScopeNode that) { RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep()); mem()._merge(that.mem(),r); this ._merge(that ,r); that.kill(); // Kill merged scope IterPeeps.add(r); - return r.unkeep().peephole(); + return r.unkeep(); } private void _merge(ScopeNode that, RegionNode r) { diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/SubNode.java index 009fb30e..5d6c2643 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -29,6 +29,11 @@ public class SubNode extends Node { t2 instanceof TypeInteger i2 ) { if (i1.isConstant() && i2.isConstant()) return TypeInteger.constant(i1.value()-i2.value()); + // Fold ranges like {2-3} - {0-1} into {1-3}. + if( !AddNode.overflow(i1._min,-i2._max) && + !AddNode.overflow(i1._max,-i2._min) && + i2._min != Long.MIN_VALUE ) + return TypeInteger.make(i1._min-i2._max,i1._max-i2._min); } // Sub of same is 0 if( in(1)==in(2) ) diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java index 7467be79..e454f48f 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java @@ -82,6 +82,7 @@ public class Type { public StringBuilder typeName( StringBuilder sb) { return print(sb); } public Type makeInit() { return null; } + public Type makeZero() { return null; } public Type nonZero() { return glb(); } // ---------------------------------------------------------- diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeFloat.java index dc36c082..37f6ce71 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -108,6 +108,7 @@ public class TypeFloat extends Type { public Type glb() { return BOT; } @Override public TypeFloat makeInit() { return ZERO; } + @Override public TypeFloat makeZero() { return ZERO; } @Override int hash() { return (int)(Double.hashCode(_con) ^ _sz); } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index b475055d..06848dc7 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -81,6 +81,7 @@ public class TypeInteger extends Type { if( this==I16 || this==U16 ) return 1; // 1<<1 == 2 bytes if( this==I32 || this==U32 ) return 2; // 1<<2 == 4 bytes if( this==BOT ) return 3; // 1<<3 == 8 bytes + if( isHighOrConst() ) return 0; throw Utils.TODO(); } @@ -115,6 +116,7 @@ public class TypeInteger extends Type { @Override public TypeInteger dual() { return make(_max,_min); } @Override public TypeInteger glb() { return BOT; } @Override public TypeInteger makeInit() { return ZERO; } + @Override public TypeInteger makeZero() { return ZERO; } @Override public TypeInteger nonZero() { if( isHigh() ) return this; if( _min==0 ) return make(1,Math.max(_max,1)); // specifically good on BOOL diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 449bf89e..cc4b9fcd 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -59,7 +59,8 @@ public class TypeMemPtr extends Type { public TypeMemPtr glb() { return make(_obj.glb(),true); } // Is forward-reference @Override public boolean isFRef() { return _obj.isFRef(); } - @Override public TypeMemPtr makeInit() { return NULLPTR; } + @Override public Type makeInit() { return _nil ? NULLPTR : Type.TOP; } + @Override public Type makeZero() { return NULLPTR; } @Override public Type nonZero() { return VOIDPTR; } @Override public boolean isHigh() { return this==TOP; } |