diff options
Diffstat (limited to 'src/main/java/com')
34 files changed, 776 insertions, 503 deletions
diff --git a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index bb109fc9..eba99128 100644 --- a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -16,43 +16,6 @@ public abstract class GlobalCodeMotion { schedLate( stop); } - // ------------------------------------------------------------------------ - // Backwards walk on the CFG only, looking for unreachable code - which has - // to be an infinite loop. Insert a bogus never-taken exit to Stop, so the - // loop becomes reachable. Also, set loop nesting depth - public static void fixLoops(StopNode stop) { - // Backwards walk from Stop, looking for unreachable code - BitSet visit = new BitSet(); - HashSet<CFGNode> unreach = new HashSet<>(); - unreach.add(Parser.START); - for( Node ret : stop._inputs ) - ((ReturnNode)ret).walkUnreach(visit,unreach); - if( unreach.isEmpty() ) return; - - // Forwards walk from unreachable, looking for loops with no exit test. - visit.clear(); - for( CFGNode cfg : unreach ) - walkInfinite(cfg,visit,stop); - // Set loop depth on remaining graph - unreach.clear(); - visit.clear(); - for( Node ret : stop._inputs ) - ((ReturnNode)ret).walkUnreach(visit,unreach); - assert unreach.isEmpty(); - } - - - // Forwards walk over previously unreachable, looking for loops with no - // exit test. - static private void walkInfinite( CFGNode n, BitSet visit, StopNode stop ) { - if( visit.get(n._nid) ) return; // Been there, done that - visit.set(n._nid); - if( n instanceof LoopNode loop ) - loop.forceExit(stop); - for( Node use : n._outputs ) - if( use instanceof CFGNode cfg ) - walkInfinite(cfg,visit,stop); - } // ------------------------------------------------------------------------ // Visit all nodes in CFG Reverse Post-Order, essentially defs before uses @@ -66,18 +29,16 @@ public abstract class GlobalCodeMotion { // Reverse Post-Order on CFG for( int j=rpo.size()-1; j>=0; j-- ) { CFGNode cfg = rpo.get(j); - cfg.loopDepth(); // Pre-compute loop depth + cfg.loopDepth(); for( Node n : cfg._inputs ) _schedEarly(n,visit); // In dead infinite loops, entire code blocks may be unreachable // from below. Reach down from the CFG to their Phis so their // inputs are scheduled too. - if( cfg instanceof RegionNode ) { - int len = cfg.nOuts(); - for( int i=0; i<len; i++ ) - if( cfg.out(i) instanceof PhiNode phi ) + if( cfg instanceof RegionNode ) + for( Node phi : cfg._outputs ) + if( phi instanceof PhiNode ) _schedEarly(phi,visit); - } } } @@ -143,7 +104,7 @@ public abstract class GlobalCodeMotion { // All uses done? for( Node use : n._outputs ) - if( use!=null && late[use._nid]==null && !(use instanceof PhiNode) ) + if( use!=null && late[use._nid]==null ) continue outer; // Nope, await all uses done // Loads need their memory inputs' uses also done @@ -262,9 +223,9 @@ public abstract class GlobalCodeMotion { private static CFGNode anti_dep( LoadNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st, int[] anti ) { // Preserve the full store range for the earlier evaluator scheduler. // It places nodes independently of GCM and may hoist this store. - for( ; stblk != defblk; stblk = stblk.idom() ) { + for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence - if( !(stblk instanceof IfNode) && anti[stblk._nid]==load._nid ) { + if( anti[stblk._nid]==load._nid ) { lca = stblk.domLCA(lca,null); // Raise Loads LCA if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java index cabc4a15..5a80698a 100644 --- a/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -2,23 +2,23 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; -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 + * The IterPeeps 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. - * + * <br> * 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. - * + * doing it. If the graph changes, put the neighbors on the worklist. + * <br> + * Lather, Rinse, Repeat until the worklist runs dry. + * <p> * The main issues we have to deal with: * * <ul> @@ -28,7 +28,7 @@ import java.util.Random; * 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 + * <li>Changing a Node also changes the graph "neighborhood". The neighbors 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> * @@ -38,7 +38,7 @@ import java.util.Random; * 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 + * The code for this is turned on in `IterPeeps.iterate` as `assert * progressOnList(stop);`</li> * </ul> */ @@ -119,9 +119,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) && (!n.iskeep() || n._nid<=5) ) { // 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/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index deb359ce..f5c371cc 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -4,7 +4,6 @@ import com.seaofnodes.graph.GraphObserver; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; -import static com.seaofnodes.simple.Utils.TODO; import java.util.*; @@ -99,12 +98,12 @@ 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 // have C-style '*ptr' references. - public final HashMap<String, Type> TYPES; + public static HashMap<String, Type> TYPES; // Mapping from a type name to the constructor for a Type. public final HashMap<String, StructNode> INITS; @@ -157,7 +156,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() { _xScopes.push(_scope); @@ -168,11 +167,11 @@ 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()); - _scope.pop(); + _scope.kill(); _xScopes.pop(); for( StructNode init : INITS.values() ) init.unkeep().kill(); @@ -191,9 +190,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 @@ -212,17 +211,17 @@ 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(); else if (matchx("continue")) return parseContinue(); else if (matchx("struct") ) return parseStruct(); else if (matchx(";") ) return null; // Empty statement - // declarations of vars with struct type are handled in parseExpressionStatement due - // to ambiguity - else return parseExpressionStatement(); + // Declaration or normal assignment/expression + else return parseDeclarationStatement(); } + /** * Parses a while statement * @@ -231,13 +230,13 @@ public class Parser { * </pre> * @return a {@link Node}, never {@code null} */ + private Node parseWhile() { + require("("); var savedContinueScope = _continueScope; var savedBreakScope = _breakScope; - require("("); - // Loop region has two control inputs, the first is the entry // point, and second is back edge that is set after loop is parsed // (see end_loop() call below). Note that the absence of back edge is @@ -257,9 +256,11 @@ public class Parser { _xScopes.push(_scope = _scope.dup(true)); // The true argument triggers creating phis // Parse predicate - var pred = require(parseExpression(), ")"); + var pred = parseAsgn(); + require(")"); + // IfNode takes current control and predicate - Node ifNode = new IfNode(ctrl(), pred).peephole(); + Node ifNode = new IfNode(ctrl(), pred.keep()).peephole(); // Setup projection nodes Node ifT = new CProjNode(ifNode. keep(), 0, "True" ).peephole().keep(); Node ifF = new CProjNode(ifNode.unkeep(), 1, "False").peephole(); @@ -270,6 +271,7 @@ public class Parser { // the loop predicate. Note that body Scope is still our current scope. ctrl(ifF); _xScopes.push(_breakScope = _scope.dup()); + _breakScope.addGuards(ifF,pred,true); // Up-cast predicate // No continues yet _continueScope = null; @@ -277,7 +279,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.addGuards(ifT,pred.unkeep(),false); // Up-cast predicate parseStatement(); // Parse loop body + _scope.removeGuards(ifT); // Merge the loop bottom into other continue statements if (_continueScope != null) { @@ -305,7 +309,8 @@ public class Parser { // the scope is the exit scope after the exit test. _xScopes.pop(); _xScopes.push(exit); - return _scope = exit; + _scope = exit; + return _scope; } private ScopeNode jumpTo(ScopeNode toScope) { @@ -322,14 +327,23 @@ 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; } 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 @@ -340,9 +354,12 @@ 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(parseAsgn(), ")"); + + pred.keep(); + // IfNode takes current control and predicate Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes @@ -357,20 +374,26 @@ 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 + _scope.addGuards(ifT,pred,false); // Up-cast predicate + parseStatement(); // Parse true-side + _scope.removeGuards(ifT); + ScopeNode tScope = _scope; // Parse the false side _scope = fScope; // Restore scope, then parse else block if any ifF.unkeep(); // fScope already owns the false control - _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.addGuards(ifF,pred,true); + boolean doRHS = matchx("else"); + if( doRHS ) parseStatement(); + _scope.removeGuards(ifF); + 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"); @@ -378,10 +401,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 = r; + r.peephole(); + return ret; } - /** * Parses a return statement; "return" already parsed. * The $ctrl edge is killed. @@ -392,7 +417,7 @@ public class Parser { * @return an expression {@link Node}, never {@code null} */ private Node parseReturn() { - var expr = require(parseExpression(), ";"); + var expr = require(parseAsgn(), ";"); Node ret = STOP.addReturn(new ReturnNode(ctrl(), expr, _scope).peephole()); ctrl(XCTRL); // Kill control return ret; @@ -400,89 +425,113 @@ public class Parser { - /** Parse: name [=expr] + /** Parse: [name '='] expr */ - private Node parseAsgn(Type t) { - boolean isDecl = t!=null; // Having a type is a declaration, missing one is updating a prior name - 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 = t instanceof TypeMemPtr tmp && !tmp._nil - // Must be initialized in the "new" constructor - ? Type.TOP - // Else takes the default - : t.makeInit(); - expr = con(init); - - } else if( !match("=") ) { // Something else - _lexer._position = old; - return null; - } else - expr = parseExpression(); - - // Defining a new variable vs updating an old one - if( !isDecl ) { // Assigning over an existing name - // Lookup - ScopeNode.Var def = _scope.lookup(name); - if( def==null ) - throw error("Undefined name '" + name + "'"); - t = def._type; // Declared field type - } + private Node parseAsgn() { + int old = pos(); + String name = _lexer.matchId(); + // Just a plain expression, no assignment. + // Distinguish `var==expr` from `var=expr` + if( name==null || KEYWORDS.contains(name) || !matchOpx('=','=') ) + { pos(old); return parseExpression(); } + + // Parse assignment expression + Node expr = parseAsgn(); + + // Final variable to update + ScopeNode.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 + // outside the constructor need to check the final bit. + if( _scope.in(def._idx)._type!=Type.TOP && def._final && !_scope.canInit(def) ) + throw error("Cannot reassign final '"+name+"'"); + + // Lift expression, based on type + Node lift = liftExpr(expr, def.type()); + // Update + _scope.update(name,lift); + // Return un-lifted expr + return expr; + } + // Apply declared access permissions; widen floats and narrow integers. + // Early error if types do not match variable. + private Node liftExpr( Node expr, Type t ) { + assert !(expr._type instanceof TypeMemPtr tmp) || !tmp.isFRef(); + // Read-only access is deep; a fixed binding alone does not remove access. + if( t instanceof TypeMemPtr tmp && tmp.isFinal() ) { + expr = peep(new ReadOnlyNode(expr)); + } // Auto-widen int to float - if( expr._type instanceof TypeInteger && t instanceof TypeFloat ) - expr = new ToFloatNode(expr).peephole(); + expr = widenInt( expr, t ); // Auto-narrow wide ints to narrow ints expr = zsMask(expr,t); - // Auto-deepen forward ref types - Type e = expr._type; - if( e instanceof TypeMemPtr tmp && tmp._obj._fields==null ) - e = TYPES.get(tmp._obj._name); // Type is sane - if( !e.isa(t) ) - throw error("Type " + e.str() + " is not of declared type " + t.str()); - - if( isDecl ) { - if( !_scope.define(name,t,false,expr) ) - throw error("Redefining name '" + name + "'"); - } else - _scope.update(name,expr); + if( !expr._type.isa(t) || !expr._type.accessISA(t) ) + throw error("Type " + expr._type.str() + " is not of declared type " + t.str()); return expr; } - /** - * Parses an expression statement or a declaration statement where type is a struct - * - * <pre> - * type decl [, decl]*; // Define many names with the same type - * asgn; // Assign or load a variable - * expr; // Something else - * name; // Bare name is an error + private Node widenInt( Node expr, Type t ) { + return expr._type instanceof TypeInteger && t instanceof TypeFloat + ? peep(new ToFloatNode(expr)) : expr; + } - * </pre> - * @return an expression {@link Node}, never {@code null} + /** + * Parse declaration or expression statement + * declStmt = type var['=' exprAsgn][, var['=' exprAsgn]]* ';' | exprAsgn ';' + * <p> + * exprAsgn = var '=' exprAsgn | expr */ - private Node parseExpressionStatement() { - Node n; + private Node parseDeclarationStatement() { Type t = type(); - if( t != null ) { - // Parse comma-separated declarations - n = parseAsgn(t); - while( match(",") ) - n = parseAsgn(t); - - // Parse "asgn;" which is just "name = expr;" - } else if( ( n = parseAsgn(null)) == null ) { - // Something else - n = parseExpression(); - } + if( t == null ) + return require(parseAsgn(),";"); + + // now parse var['=' asgnexpr] in a loop + Node n = parseDeclaration(t); + while( match(",") ) + n = parseDeclaration(t); return require(n,";"); } + // The binding modifier sits immediately before the name. It never + // changes permissions on the referenced object. + private boolean bindingFinal(Type t) { + if( match("!") ) return false; + if( match("~") ) return true; + return t instanceof TypeMemPtr; + } + + /** Parse final: [!|~]var['=' asgn] + */ + private Node parseDeclaration(Type t) { + assert t!=null; + boolean xfinal = bindingFinal(t); + String name = requireId(); + + // Optional initializing expression follows + Node expr; + if( match("=") ) { + expr = parseAsgn(); + + } else { + expr = con(xfinal && !(t instanceof TypeMemPtr) ? Type.TOP : t.makeInit()); + } + + // Lift expression, based on type + Node lift = liftExpr(expr, t); + + // Define a new name, + if( !_scope.define(name,t,xfinal,lift) ) + throw error("Redefining name '" + name + "'"); + return null; + } + + /** * Parse a struct declaration, and return the following statement. @@ -495,11 +544,12 @@ public class Parser { if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope"); String typeName = requireId(); Type t = TYPES.get(typeName); - if( t!=null && !(t instanceof TypeMemPtr tmp && tmp._obj._fields==null) ) + if( t!=null && !(t instanceof TypeMemPtr tmp && tmp.isFRef() ) ) throw errorSyntax("struct '" + typeName + "' cannot be redefined"); // A Block scope parse, and inspect the scope afterward for fields. - _scope.push(); + _scope.push(true); + _xScopes.push(_scope); require("{"); while (!peek('}') && !_lexer.isEOF()) parseStatement(); @@ -512,7 +562,7 @@ public class Parser { for( int i=lexlen; i<varlen; i++ ) { s.addDef(_scope.in(i)); ScopeNode.Var v = _scope._vars.at(i); - fs[i-lexlen] = Field.make(v._name,v._type,ALIAS++,v._final); + fs[i-lexlen] = Field.make(v._name,v.type(),ALIAS++,v._final); } TypeStruct ts = s._ts = TypeStruct.make(typeName, fs); TYPES.put(typeName, TypeMemPtr.make(ts)); @@ -520,6 +570,7 @@ public class Parser { // Done with struct/block scope require("}"); require(";"); + _xScopes.pop(); _scope.pop(); return null; } @@ -529,44 +580,58 @@ public class Parser { // 'id' which the caller must parse. This lets us distinguish forward ref // types (which ARE valid here) from local vars in an (optional) forward // ref type position. + + // t = int|i8|i16|i32|i64|u8|u16|u32|u64|byte|bool | flt|f32|f64 | struct[?] private Type type() { - int old1 = _lexer._position; + int old1 = pos(); + boolean writable = match("!"); + boolean readonly = !writable && match("~"); String tname = _lexer.matchId(); - if( tname==null ) return null; + if( tname==null ) return posT(old1); // Convert the type name to a type. Type t0 = TYPES.get(tname); - Type t1 = t0 == null ? TypeMemPtr.make(TypeStruct.make(tname)) : t0; // Null: assume a forward ref type + // No new types as keywords + if( t0 == null && KEYWORDS.contains(tname) ) + return posT(old1); + Type t1 = t0 == null ? TypeMemPtr.make(TypeStruct.makeFRef(tname)) : t0; // Null: assume a forward ref type + // A qualifier before the name applies to the struct reference, not + // to an enclosing array. Arrays have their own [] / [~] qualifier. + if( t1 instanceof TypeMemPtr tmp ) { + if( readonly || !writable ) t1 = tmp.makeRO(); + } else if( writable || readonly ) + return posT(old1); + // Nest arrays and '?' as needed + Type t2 = t1; while( true ) { - assert !(t1 instanceof TypeStruct); + assert !(t2 instanceof TypeStruct); if( match("?") ) { - if( !(t1 instanceof TypeMemPtr tmp) ) + if( !(t2 instanceof TypeMemPtr tmp) ) throw error("Type "+t0+" cannot be null"); - if( tmp._nil ) throw error("Type "+t1+" already allows null"); - t1 = TypeMemPtr.make(tmp._obj,true); - continue; - } - if( match("[]") ) { - t1 = typeAry(t1); - continue; - } - break; + if( tmp._nil ) throw error("Type "+t2+" already allows null"); + t2 = tmp.makeFrom(true); + } else if( match("[~]") ) { + TypeMemPtr ary = typeAry(t2); + t2 = ary.makeFrom(ary._obj.makeRO()).makeRO(); + } else if( match("[]") ) { + t2 = typeAry(t2); + } else + break; } // Check no forward ref - if( t0 != null ) return t1; + if( t0 != null ) return t2; // Check valid forward ref, after parsing all the type extra bits. // Cannot check earlier, because cannot find required 'id' until after "[]?" syntax - int old2 = _lexer._position; + int old2 = pos(); + if( !match("!") ) match("~"); String id = _lexer.matchId(); - _lexer._position = old2; // Reset lexer to reparse - if( id==null ) { - _lexer._position = old1; // Reset lexer to reparse - return null; // Not a type - } + pos(old2); // Reset lexer to reparse + if( id==null || _scope.lookup(id)!=null ) + return posT(old1); // Reset lexer to reparse // Yes a forward ref, so declare it - TYPES.put(tname,t1); - return t1; + TYPES.put(tname,((TypeMemPtr)t1).withAccess(false)); + return t2; } // Make an array type of t @@ -575,7 +640,15 @@ public class Parser { throw error("Arrays of reference types must always be nullable"); String tname = "["+t.str()+"]"; Type ta = TYPES.get(tname); - if( ta != null ) return (TypeMemPtr)ta; + if( ta != null ) { + TypeStruct ary = ((TypeMemPtr)ta)._obj; + // Keep the original shallow struct reference. Resolving a recursive + // struct must not expand its array element type on each lookup. + if( t instanceof TypeMemPtr ptr && (ptr._obj._fields==null || !ptr._obj.isAry()) && + ary._fields[1]._type instanceof TypeMemPtr old ) + t = old.withAccess(ptr._ro); + return TypeMemPtr.make(TypeStruct.makeAry(TypeInteger.BOT,ary._fields[0]._alias,t,ary._fields[1]._alias)); + } // Need make an array type. TypeStruct ts = TypeStruct.makeAry(TypeInteger.BOT,ALIAS++,t,ALIAS++); assert ts.str().equals(tname); @@ -584,12 +657,11 @@ public class Parser { return tary; } - /** * Parse an expression of the form: * * <pre> - * expr : compareExpr + * expr : bitwise * </pre> * @return an expression {@link Node}, never {@code null} */ @@ -612,7 +684,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; } @@ -640,9 +712,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; } @@ -664,7 +736,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; } @@ -685,7 +757,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; } @@ -706,7 +778,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; } @@ -715,13 +787,13 @@ public class Parser { * Parse a unary minus expression. * * <pre> - * unaryExpr : ('-') | '!') unaryExpr | postfixExpr | primaryExpr + * unaryExpr : ('-') unaryExpr | '!') unaryExpr | postfixExpr | primaryExpr | '--' Id | '++' Id * </pre> * @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()); } @@ -729,23 +801,33 @@ public class Parser { * Parse a primary expression: * * <pre> - * primaryExpr : integerLiteral | Identifier | true | false | null | new Type | '(' expression ')' + * primaryExpr : integerLiteral | true | false | null | new Type | '(' expression ')' | Id['++','--'] * </pre> * @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral(); - if( match("(") ) return require(parseExpression(), ")"); if( matchx("true" ) ) return con(1); if( matchx("false") ) return ZERO; if( matchx("null" ) ) return con(TypeMemPtr.NULLPTR); + if( match("(") ) return require(parseAsgn(), ")"); if( matchx("new" ) ) return alloc(); // Expect an identifier now - String name = _lexer.matchId(); - if( name == null) throw errorSyntax("an identifier or expression"); - ScopeNode.Var n = _scope.lookup(name); - if( n!=null ) return _scope.in(n); - throw error("Undefined name '" + name + "'"); + ScopeNode.Var n = requireLookupId("an identifier or expression"); + Node rvalue = _scope.in(n); + if( rvalue._type == Type.BOTTOM ) + throw error("Cannot read uninitialized field '"+n._name+"'"); + return rvalue; + } + + ScopeNode.Var requireLookupId(String msg) { + String id = _lexer.matchId(); + if( id == null || KEYWORDS.contains(id) ) + throw errorSyntax(msg); + ScopeNode.Var n = _scope.lookup(id); + if( n==null ) + throw error("Undefined name '" + id + "'"); + return n; } /** @@ -756,7 +838,7 @@ public class Parser { if( t==null ) throw error("Expected a type"); // Parse ary[ length_expr ] if( match("[") ) { - Node len = parseExpression().keep(); + Node len = parseAsgn(); if( !(len._type instanceof TypeInteger) ) throw error("Cannot allocate an array with length "+len._type); require("]"); @@ -781,15 +863,15 @@ public class Parser { // Push a scope, and pre-assign all struct fields. _scope.push(); for( int i=0; i<fs.length; i++ ) - _scope.define(fs[i]._fname, fs[i]._type, fs[i]._final, s.in(i)); + _scope.define(fs[i]._fname, fs[i]._type, fs[i]._final, s.in(i)._type==Type.TOP ? con(Type.BOTTOM) : s.in(i)); // Parse the constructor body - parseBlock(); + parseBlock(true); require("}"); init = _scope._inputs; } // Check that all fields are initialized for( int i=idx; i<init.size(); i++ ) - if( init.get(i)._type == Type.TOP ) + if( init.at(i)._type == Type.TOP || init.at(i)._type == Type.BOTTOM ) throw error("'"+tmp._obj._name+"' is not fully initialized, field '" + fs[i-idx]._fname + "' needs to be set in a constructor"); Node ptr = newStruct(tmp._obj, con(tmp._obj.offset(fs.length)), idx, init ); if( hasConstructor ) @@ -824,7 +906,7 @@ public class Parser { mem(after.peephole()); out.unkeep(); nnn.unkeep(); - if( prior.unkeep().isUnused() ) prior.kill(); + prior.unkill(); return ptr.unkeep(); } @@ -832,11 +914,9 @@ 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(); - ALTMP.clear(); ALTMP.add(len); ALTMP.add(con(ary._fields[1]._type.makeInit())); - Node ptr = newStruct(ary,size,0,ALTMP); - len.unkeep(); - return ptr; + Node size = peep(new AddNode(con(base),peep(new ShlNode(len.keep(),con(scale))))); + ALTMP.clear(); ALTMP.add(len.unkeep()); ALTMP.add(con(ary._fields[1]._type.makeInit())); + return newStruct(ary,size,0,ALTMP); } // Memory is one hidden SSA variable, including across branches and loops. @@ -844,12 +924,14 @@ public class Parser { private void mem(Node n) { _scope.mem(n); } private void store(String name, int alias, Type glb, Node ptr, Node off, Node val, boolean init, Node ctrl) { + if( !init && ptr._type instanceof TypeMemPtr view && view._ro && ctrl()._type!=Type.XCONTROL ) + throw error("Cannot modify final field '"+name+"'"); Node prior = mem().keep(); Node st = new StoreNode(name,alias,glb,prior,ptr,off,val,init); st.setDef(0,ctrl); st = st.peephole(); mem(new MemMergeNode(prior,alias,st).peephole()); - if( prior.unkeep().isUnused() ) prior.kill(); + prior.unkill(); } /** @@ -864,7 +946,7 @@ public class Parser { */ private Node parsePostfix(Node expr) { String name = null; - if( match(".") ) name = requireId().intern(); + if( match(".") ) name = requireId(); else if( match("#") ) name = "#"; else if( match("[") ) name = "[]"; else return expr; // No postfix @@ -878,40 +960,49 @@ public class Parser { // spoil the user experience with error messages. if( ctrl()._type==Type.XCONTROL ) // Exit out via parsing the trailing expression - return matchOpx('=','=') ? parseExpression() : parsePostfix(con(Type.TOP)); + return matchOpx('=','=') ? parseAsgn() : parsePostfix(con(Type.TOP)); // Sanity check field name for existing TypeMemPtr tmp = (TypeMemPtr)TYPES.get(ptr._obj._name); - if( tmp == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); - TypeStruct base = tmp._obj; + if( tmp == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr + "'"); + TypeStruct base = ptr._obj.isAry() ? ptr._obj : tmp._obj; int fidx = base.find(name); if( fidx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); // Get field type and layout offset from base type and field index fidx Field f = base._fields[fidx]; // Field from field index + Type tf = f._type; + if( tf instanceof TypeMemPtr ftmp && ftmp.isFRef() ) + tf = ftmp.makeFrom(((TypeMemPtr)(TYPES.get(ftmp._obj._name)))._obj); expr.keep(); - Node off = name.equals("[]") // If field is an array body + // Field offset; fixed for structs, computed for arrays + 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(parseAsgn(),"]"),con(base.aryScale()))))) // Struct field offsets are hardwired - : con(base.offset(fidx)); + : con(base.offset(fidx))).keep(); // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment if( matchOpx('=','=') ) { - off.keep(); - Node val = zsMask(parseExpression(),f._type).keep(); - // Array control stands in for the future bounds check. - store(name,f._alias,f._type,expr.unkeep(),off.unkeep(),val,false,base.isAry() ? ctrl() : null); - return val.unkeep(); + Node val = parseAsgn().keep(); + Node lift = liftExpr( val, tf ); + + store(name,f._alias,tf,expr.unkeep(),off.unkeep(),lift,false,base.isAry() ? ctrl() : null); + return val.unkeep(); // "obj.a = expr" returns the expression while updating memory } - Node load = new LoadNode(name, f._alias, f._type.glb(), mem(), expr.unkeep(), off); + Node load = new LoadNode(name, f._alias, (tf instanceof TypeMemPtr ? tf : tf.glb()), mem(), expr, off); // 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() ) load.setDef(0,ctrl()); - return parsePostfix(load.peephole()); + if( base.isAry() ) load.setDef(0,ctrl()); + load = peep(load); + + expr.unkill(); + off.unkill(); + + return parsePostfix(load); } @@ -922,16 +1013,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())); } @@ -946,6 +1037,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 @@ -959,14 +1054,28 @@ public class Parser { private boolean peek(char ch) { return _lexer.peek(ch); } private boolean peekIsId() { return _lexer.peekIsId(); } + private int pos(int pos) { + int old = _lexer._position; + _lexer._position = pos; + return old; + } + private Type posT(int pos) { _lexer._position = pos; return null; } + // Require and return an identifier private String requireId() { String id = _lexer.matchId(); - if (id != null && !KEYWORDS.contains(id) ) return id; + if (id != null && !KEYWORDS.contains(id) ) return id.intern(); throw error("Expected an identifier, found '"+id+"'"); } - + private String matchId() { + int old = pos(); + String id = _lexer.matchId(); + if( id==null ) return null; + if( !KEYWORDS.contains(id) ) return id; + pos(old); + return null; + } // Require an exact match private Parser require(String syntax) { require(null, syntax); return this; } @@ -1023,6 +1132,8 @@ public class Parser { return isEOF() ? Character.MAX_VALUE // Special value that causes parsing to terminate : (char) _input[_position]; } + // Just crash if misused + public byte peek(int off) { return _input[_position+off]; } private char nextChar() { char ch = peek(); @@ -1051,6 +1162,8 @@ public class Parser { } } + // Next non-white-space character, or EOF + public char nextXChar() { skipWhiteSpace(); return nextChar(); } // Return true, if we find "syntax" after skipping white space; also // then advance the cursor past syntax. @@ -1157,12 +1270,13 @@ public class Parser { // private boolean isPunctuation(char ch) { - return "=;[]<>()+-/*".indexOf(ch) != -1; + return "=;[]<>()+-/*&|^".indexOf(ch) != -1; } private String parsePunctuation() { int start = _position; return new String(_input, start, 1); } + } } diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index b08f749a..5eb0b0a3 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -29,7 +29,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 } @@ -37,6 +37,7 @@ public class AddNode extends Node { public Node idealize () { Node lhs = in(1); Node rhs = in(2); + if( rhs.err() != null ) return null; Type t2 = rhs._type; // Add of 0. We do not check for (0+x) because this will already diff --git a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 06596ce0..e85fc6ae 100644 --- a/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/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 @@ -71,24 +62,75 @@ public abstract class CFGNode extends Node { return lhs; } - // Loop nesting depth - public int _loopDepth; - public int loopDepth() { return _loopDepth==0 ? (_loopDepth = cfg(0).loopDepth()) : _loopDepth; } - // ------------------------------------------------------------------------ - // Support routines for Global Code Motion + // Loop nesting + public LoopNode loop() { return _ltree._head; } + public int loopDepth() { return _ltree==null ? 0 : _ltree.depth(); } + + LoopTree _ltree; + int _pre; // Pre-order numbers for loop tree finding + private static class LoopTree { + LoopTree _par; + final LoopNode _head; + int _depth; + LoopTree(LoopNode head) { _head = head; } + @Override public String toString() { return "LOOP"+_head._nid; } + int depth() { + return _depth==0 ? (_par==null ? 0 : (_depth = _par.depth()+1)) : _depth; + } + } - // Tik-tok recursion pattern. This method is final, and every caller does - // this work. - public final void walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { - if( visit.get(_nid) ) return; - visit.set(_nid); - _walkUnreach(visit,unreach); - unreach.remove(this); // Since we reached here... Node was not unreachable + // ------------------------------------------------------------------------ + // Tag all CFG Nodes with their containing LoopNode; LoopNodes themselves + // also refer to *their* containing LoopNode, as well as have their depth. + // Start is a LoopNode which contains all at depth 1. + public void buildLoopTree(StopNode stop) { + _ltree = stop._ltree = Parser.XCTRL._ltree = new LoopTree((StartNode)this); + _bltWalk(2,stop, new BitSet()); } + private int _bltWalk(int pre, StopNode stop, BitSet post) { + // Pre-walked? + if( _pre!=0 ) return pre; + _pre = pre++; + // Pre-walk + for( Node use : _outputs ) + if( use instanceof CFGNode usecfg ) + pre = usecfg._bltWalk(pre,stop,post); - // Tik-tok recursion pattern; not-final; callers override this. - void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { - cfg(0).walkUnreach(visit,unreach); + // Post-order work: find innermost loop + LoopTree inner = null, ltree; + for( Node use : _outputs ) { + if( !(use instanceof CFGNode usecfg) ) continue; + // Child visited but not post-visited? + if( !post.get(usecfg._nid) ) { + // Must be a backedge to a LoopNode then + ltree = usecfg._ltree = new LoopTree((LoopNode)usecfg); + } else { + // Take child's loop choice, which must exist + ltree = usecfg._ltree; + // If falling into a loop, use the target loop's parent instead + if( ltree._head == usecfg ) { + if( ltree._par == null ) + // This loop never had an If test choose to take its + // exit, i.e. it is a no-exit infinite loop. + ltree._par = ltree._head.forceExit(stop)._ltree; + ltree = ltree._par; + } + } + // Sort inner loops. The decision point is some branch far removed + // from either loop head OR either backedge so requires pre-order + // numbers to figure out innermost. + if( inner == null ) { inner = ltree; continue; } + if( inner == ltree ) continue; // No change + LoopTree outer = ltree._head._pre > inner._head._pre ? inner : ltree; + inner = ltree._head._pre > inner._head._pre ? ltree : inner; + inner._par = outer; + } + // Set selected loop + if( inner!=null ) + _ltree = inner; + // Tag as post-walked + post.set(_nid); + return pre; } } diff --git a/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/src/main/java/com/seaofnodes/simple/node/CProjNode.java index cba63db8..53348b5a 100644 --- a/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -53,10 +53,6 @@ public class CProjNode extends CFGNode { } @Override - public Node getBlockStart() { - return ctrl() instanceof IfNode ? this : ctrl().getBlockStart(); - } - @Override boolean eq( Node n ) { return _idx == ((CProjNode)n)._idx; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/DivFNode.java b/src/main/java/com/seaofnodes/simple/node/DivFNode.java index a3f4318d..c678ac3e 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivFNode.java @@ -29,7 +29,7 @@ public class DivFNode extends Node { Type t1 = lhs._type; Type t2 = rhs._type; - // Div of 1. + // Div of 1. if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==1 ) return lhs; diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index f21894dc..2b53b3a3 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -5,7 +5,6 @@ import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.type.TypeTuple; -import java.util.BitSet; import java.util.HashSet; public class IfNode extends CFGNode implements MultiNode { @@ -40,6 +39,9 @@ public class IfNode extends CFGNode implements MultiNode { // Else true branch is reachable if( t.isConstant() ) return t.makeInit()==t ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; + // Integers allow non-zero ranges: "1-65535" + if( t.makeZero().meet(t) != t ) + return TypeTuple.IF_TRUE; return TypeTuple.IF_BOTH; } @@ -57,12 +59,4 @@ public class IfNode extends CFGNode implements MultiNode { return null; } - @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { - for( Node proj : _outputs ) - if( ((CProjNode)proj)._loopDepth == 0 ) - unreach.add((CProjNode)proj); - super._walkUnreach(visit,unreach); - } - - @Override public Node getBlockStart() { return ctrl().getBlockStart(); } } diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 8d604b28..85ad243b 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -53,8 +53,11 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { Type t = MemMergeNode.contents(mem(),_alias,this); - // No constant folding if the pointer still needs a null check. - return err()==null ? _declaredType.join(t) : _declaredType; + // Update declared forward ref to the actual. + if( _declaredType.isFRef() && t instanceof TypeMemPtr tmp && !tmp.isFRef() ) + _declaredType = tmp.withAccess(((TypeMemPtr)_declaredType)._ro); + Type rez = err()==null ? _declaredType.join(t) : _declaredType; + return ptr()._type.isFinal() || _declaredType.isFinal() ? rez.makeRO() : rez; } @Override @@ -69,17 +72,19 @@ public class LoadNode extends MemOpNode { if( mem() instanceof StoreNode st && _alias==st._alias && ptr == st.ptr() && off() == st.off() ) { // Must check same object assert _name.equals(st._name); // Equiv class aliasing is perfect - return st.val(); + return castRO(st.val()); } // Simple Load-after-New on same address. if( mem() instanceof ProjNode p && p.in(0) instanceof NewNode nnn && ptr == nnn.proj(0) ) // Must check same object - return nnn.in(nnn.findAlias(_alias)); // Load from New init + return castRO(nnn.in(nnn.findAlias(_alias))); // Load from New init // Load-after-Store on same address, but bypassing provably unrelated // stores. This is a more complex superset of the above two peeps. // "Provably unrelated" is really weak. + if( ptr instanceof ReadOnlyNode ro ) + ptr = ro.in(1); Node mem = mem(); outer: while( true ) { @@ -90,7 +95,7 @@ public class LoadNode extends MemOpNode { break; case StoreNode st: if( _alias==st._alias && ptr == st.ptr() && off() == st.off() ) - return st.val(); // Proved equal + return castRO(st.val()); // Proved equal // Can we prove unequal? Offsets do not overlap? if( _alias==st._alias && !off()._type.join(st.off()._type).isHigh() && // Offsets overlap !neverAlias(ptr,st.ptr()) ) // And might alias @@ -103,7 +108,7 @@ public class LoadNode extends MemOpNode { case ProjNode mproj: if( mproj.in(0) instanceof NewNode nnn1 ) { if( ptr instanceof ProjNode pproj && pproj.in(0) == mproj.in(0) ) - return nnn1.in(nnn1.findAlias(_alias)); // Load from New init + return castRO(nnn1.in(nnn1.findAlias(_alias))); // Load from New init if( !(ptr instanceof ProjNode pproj && pproj.in(0) instanceof NewNode nnn2) ) break outer; // Cannot tell, ptr not related to New mem = nnn1.mem();// Bypass unrelated New @@ -122,7 +127,11 @@ public class LoadNode extends MemOpNode { // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; if( mem() instanceof MemPhiNode 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. @@ -135,12 +144,14 @@ public class LoadNode extends MemOpNode { return null; } + private Node ld( int idx ) { Node mem = mem(), ptr = ptr(); LoadNode ld = new LoadNode(_name,_alias,_declaredType,mem.in(idx),ptr instanceof PhiNode && ptr.in(0)==mem.in(0) ? ptr.in(idx) : ptr,off()); ld.setDef(0,in(0)); return ld.peephole(); } + private static boolean neverAlias( Node ptr1, Node ptr2 ) { return ptr1.in(0) != ptr2.in(0) && // Unrelated allocations @@ -148,6 +159,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); @@ -158,6 +188,13 @@ public class LoadNode extends MemOpNode { return false; } + // Read-Only is a deep property, and cannot be cast-away + private Node castRO(Node rez) { + if( (ptr()._type.isFinal() || _declaredType.isFinal()) && !rez._type.isFinal() ) + return new ReadOnlyNode(rez).peephole(); + return rez; + } + // Memory writers which must follow this read. A packaging node is not a // write, but can hide New's input, so follow this alias through aggregates. public ArrayList<Node> antiDeps() { diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index a0e988dd..8fb6a4ce 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -32,38 +32,18 @@ public class LoopNode extends RegionNode { // Bypass Region idom, same as the default idom() using use in(1) instead of in(0) @Override public CFGNode idom(Node dep) { return entry(); } - @Override public int loopDepth() { - if( _loopDepth!=0 ) return _loopDepth; // Was already set - _loopDepth = entry()._loopDepth+1; // Entry depth plus one - // One-time tag loop exits - for( CFGNode idom = back(); idom!=this; idom = idom.idom() ) { - // Walk idom in loop, setting depth - idom._loopDepth = _loopDepth; - // Loop exit hits the CProj before the If, instead of jumping from - // Region directly to If. - if( idom instanceof CProjNode proj ) { - assert proj.in(0) instanceof IfNode; // Loop exit test - // Find the loop exit CProj, and set loop_depth - for( Node use : proj.in(0)._outputs ) - if( use instanceof CProjNode proj2 && proj2 != idom ) - proj2._loopDepth = _loopDepth-1; - } - } - return _loopDepth; - } - // If this is an unreachable loop, it may not have an exit. If it does not // (i.e., infinite loop), force an exit to make it reachable. - public void forceExit( StopNode stop ) { + public StopNode forceExit( StopNode stop ) { // Walk the backedge, then immediate dominator tree util we hit this // Loop again. If we ever hit a CProj from an If (as opposed to // directly on the If) we found our exit. CFGNode x = back(); while( x != this ) { if( x instanceof CProjNode exit && exit.in(0) instanceof IfNode iff ) { - Node other = iff.cproj(1-exit._idx); - if( !(other.out(0) instanceof LoopNode loop) || loop.entry()==exit ) - return; // Found an exit, not an infinite loop + CFGNode other = iff.cproj(1-exit._idx); + if( other.loopDepth() < loopDepth() ) + return stop; // Found an exit, not an infinite loop } x = x.idom(); } @@ -76,5 +56,6 @@ public class LoopNode extends RegionNode { CProjNode f = new CProjNode(iff,1,"False"); setDef(2,f); stop.addDef(new ReturnNode(t,Parser.ZERO,null)); + return stop; } } diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 9c222ad2..0bf9b6ac 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.Field; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMemPtr; @@ -11,7 +10,9 @@ public abstract class MemOpNode extends Node { public final String _name; public final int _alias; - public final Type _declaredType; + // Declared type; not final because it might be a forward-reference + // which will be lazily improved when the reference is declared. + public Type _declaredType; public MemOpNode(String name, int alias, Type glb, Node mem, Node ptr, Node off) { super(null, mem, ptr, off); diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index bd8f71ad..b85af74e 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.Utils; public class MinusNode extends Node { @@ -16,7 +17,9 @@ public class MinusNode extends Node { public Type compute() { if( in(1)._type instanceof TypeInteger i0 ) { if( i0.isHigh() ) return TypeInteger.TOP; - return i0==TypeInteger.BOT ? TypeInteger.BOT : TypeInteger.make(-i0._max,-i0._min); + if( i0==TypeInteger.BOT || i0._min == Long.MIN_VALUE || i0._max == Long.MIN_VALUE ) + return TypeInteger.BOT; + return TypeInteger.make(-i0._max,-i0._min); } return in(1)._type.isHigh() ? TypeInteger.TOP : TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index fa25b58a..e70fe495 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -110,7 +110,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable * @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 @@ -221,6 +221,10 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable public <N extends Node> N unkeep() { delUse(null); return (N)this; } // 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 public void subsume( Node nnn ) { @@ -232,6 +236,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable n._inputs.set(idx,nnn); n.moveDepsToWorklist(); // Rewiring can change a dependent query without changing type. nnn.addUse(n); + IterPeeps.addAll(n._outputs); } kill(); } @@ -366,7 +371,7 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable * And more folding: * <pre> ary + ((idx<<2) + 16)</pre> * And during code-gen: - * <pre> MOV4 Rary,Ridx,16 // or some such hardware-specific notation </pre> + * <pre> MOV4 Rary,[Ridx<<2 +16] // or some such hardware-specific notation </pre> * <p> * {@link #idealize} has a very specific calling convention: * <ul> @@ -497,9 +502,6 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable /** Is this Node Memory related */ public boolean isMem() { return false; } - /** Return block start from a isCFG() */ - public Node getBlockStart() { return null; } - // Semantic change to the graph (so NOT a peephole), used by the Parser. // If any input is a float, flip to a float-flavored opcode and widen any // non-float input. @@ -585,9 +587,8 @@ public abstract class Node extends BaseNode<Node> implements OutNode, Cloneable 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; + try { return _walk(pred); } + finally { WVISIT.clear(); } } private <E> E _walk( Function<Node,E> pred ) { diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java index e388f4a3..b9cf4904 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -18,20 +18,19 @@ public class NotNode extends Node { switch( t0 ) { case TypeInteger i0: return i0._max < 0 || i0._min > 0 ? TypeInteger.FALSE : (i0==TypeInteger.ZERO ? TypeInteger.TRUE : TypeInteger.BOOL); case TypeFloat i0: - return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : TypeInteger.BOT; + return i0.isConstant() ? TypeInteger.constant(i0.value()==0 ? 1 : 0) : TypeInteger.BOOL; case TypeMemPtr p0: // 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 ? TypeInteger.TOP : TypeInteger.BOT; + return TypeInteger.BOOL; } } diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 8479b4dc..942748e7 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -43,7 +43,7 @@ public class PhiNode extends Node { // During parsing Phis have to be computed type pessimistically. if( r.inProgress() ) return _declaredType; // Set type to local top of the starting type - Type t = _declaredType.glb().dual(); + Type t = _declaredType.lub(); for (int i = 1; i < nIns(); i++) // 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. @@ -82,7 +82,7 @@ public class PhiNode extends Node { if( in(2)._type == in(2)._type.makeInit() ) nullx = 2; if( nullx != -1 ) { Node val = in(3-nullx); - if( r.idom(this) instanceof IfNode iff && iff.pred().addDep(this)==val ) { + if( r.idom(this).addDep(this) instanceof IfNode iff && iff.pred().addDep(this)==val ) { // Must walk the idom on the null side to make sure we hit False. CFGNode idom = (CFGNode)r.in(nullx); while( idom.nIns() > 0 && idom.in(0) != iff ) idom = idom.idom(); diff --git a/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java b/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java new file mode 100644 index 00000000..fa4e0242 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java @@ -0,0 +1,26 @@ +package com.seaofnodes.simple.node; + + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMemPtr; + + +/** + * Cast a pointer to read-only + */ +public class ReadOnlyNode extends Node { + public ReadOnlyNode( Node n ) { super(null,n); } + @Override public String label() { return "ReadOnly"; } + + @Override protected String format() { return "(const)%1"; } + @Override public Type compute() { + Type t = in(1)._type; + return t instanceof TypeMemPtr tmp ? tmp.makeRO() : t; + } + + @Override public Node idealize() { + if( in(1)._type instanceof TypeMemPtr tmp && tmp.isFinal() ) + return in(1); + return null; + } +} diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 08f48a08..27866139 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -8,7 +8,6 @@ import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import java.util.ArrayList; import java.util.Arrays; -import java.util.BitSet; import java.util.HashSet; public class RegionNode extends CFGNode { @@ -19,7 +18,7 @@ public class RegionNode extends CFGNode { public String label() { return "Region"; } @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { - return p.p(label()).p(_nid); + return p.p(label()); } @Override public boolean isMultiHead() { return true; } @@ -73,65 +72,9 @@ public class RegionNode extends CFGNode { p1.in(0) instanceof IfNode iff ) return iff.ctrl(); - - // Look for direct uses of a guarded expression, and replace with the guard result. - if( !(idom() instanceof StartNode) && // Dead or dying - !(this instanceof LoopNode) ) { - VISIT.clear(); - boolean progress = false; - outer: - for( int i=1; i<nIns(); i++ ) { - CFGNode idom = cfg(i); - while( !(idom instanceof CProjNode cproj) ) { - idom = idom.idom(); - if( idom==null || idom.idepth() < idom().idepth() ) - continue outer; - } - if( cproj.cfg0() instanceof IfNode iff && cproj.compute()==Type.CONTROL ) { - VISIT.set(iff.pred()._nid); - for( Node out : _outputs ) - if( out instanceof PhiNode phi ) - progress |= walk(iff,cproj,phi.in(i)); - } - } - if( progress ) - return this; - } - return null; } - // A walk that can be cutoff early - private static final BitSet VISIT = new BitSet(); - private boolean walk( IfNode iff, CProjNode cproj, Node n ) { - if( VISIT.get(n._nid) ) return false; - VISIT.set(n._nid); - if( n instanceof CFGNode ) return false; - if( n.in(0)!=null && n.cfg0().idepth() < iff.idepth() ) - return false; - boolean progress = false; - Node pred = iff.pred(); - if( pred._type.isHighOrConst() ) return false; // This will collapse the IF already - for( int i=1; i<n.nIns(); i++ ) { - // Using a tested value - if( n.in(i) == pred && !(n instanceof CastNode) ) { - // Checking pred for T/F - Type t = pred._type; - Type tcast = cproj._idx==0 ? t.nonZero() : t.makeInit(); - if( t!=tcast ) { // Progress to cast - Node cast = new CastNode( tcast, cproj, pred ).peephole(); - n.setDef( i, cast ); - IterPeeps.add(n); - progress = true; - } else pred.addDep( this ); - } - if( n.in(i)!=null ) - progress |= walk(iff,cproj,n.in(i)); - } - return progress; - } - - private int findDeadInput() { for( int i=1; i<nIns(); i++ ) if( in(i)._type==Type.XCONTROL ) @@ -164,13 +107,6 @@ public class RegionNode extends CFGNode { return lca; } - @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { - for( int i=1; i<nIns(); i++ ) - cfg(i).walkUnreach(visit,unreach); - } - - @Override public int loopDepth() { return _loopDepth==0 ? (_loopDepth = cfg(1).loopDepth()) : _loopDepth; } - // True if last input is null public final boolean inProgress() { return nIns()>1 && in(nIns()-1) == null; @@ -180,6 +116,4 @@ public class RegionNode extends CFGNode { @Override boolean eq( Node n ) { return !inProgress(); } - - @Override public Node getBlockStart() { return this; } } diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index eff33954..6c773c42 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -39,6 +39,4 @@ public class ReturnNode extends CFGNode { return ctrl(); return null; } - - @Override public Node getBlockStart() { return ctrl().getBlockStart(); } } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 84937ad7..753abe90 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -3,6 +3,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Ary; import com.seaofnodes.simple.type.*; import java.util.*; @@ -21,19 +22,32 @@ public class ScopeNode extends Node { public static final String ARG0 = "arg"; public static final String MEM0 = "$mem"; - /** The tracked fields are now complex enough to deserve an array-of-structs layout + /** The tracked fields are now complex enough to deserve a array-of-structs layout */ public static class Var { - public final int _idx; - public final String _name; - public final Type _type; - public final boolean _final; + public final int _idx; // index in containing scope + public final String _name; // Declared name + private Type _type; // Declared type + public final boolean _final; // Final field public Var(int idx, String name, Type type, boolean xfinal) { _idx = idx; _name = name; _type = type; _final = xfinal; } + public Type type() { + if( !_type.isFRef() ) return _type; + // Update self to no longer use the forward ref type + Type def = Parser.TYPES.get(((TypeMemPtr)_type)._obj._name); + return (_type=_type.meet(def)); + } + public Type lazyGLB() { + Type t = type(); + return t instanceof TypeMemPtr ? t : t.glb(); + } + @Override public String toString() { + return _type.toString()+(_final ? " ": " !")+_name; + } } public Node in(Var v) { return in(v._idx); } @@ -47,13 +61,23 @@ public class ScopeNode extends Node { // Size of each nested lexical scope public final Ary<Integer> _lexSize; + // 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() { _type = Type.BOTTOM; _vars = new Ary<>(Var.class); _lexSize = new Ary<>(Integer.class); } + public ScopeNode() { + _type = Type.BOTTOM; + _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 protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) { p.p("Scope[ "); @@ -61,7 +85,7 @@ public class ScopeNode extends Node { for( int i=0; i<nIns(); i++ ) { if( j < _lexSize._len && i == _lexSize.at(j) ) { p.p("| "); j++; } Var v = _vars.get(i); - p.p(v._type); + p.p(v.type()); p.p(" "); if( v._final ) p.p("!"); p.p(v._name); @@ -92,17 +116,33 @@ public class ScopeNode extends Node { * * @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); } + // Allocation fields live in the scope immediately outside the constructor + // block. Nested blocks retain that permission; surrounding bindings do not. + public boolean canInit(Var v) { + for( int i=_inCons._len-1; i>0; i-- ) + if( _inCons.at(i) ) + return v._idx >= _lexSize.at(i-1) && v._idx < _lexSize.at(i); + return false; + } + + 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. @@ -136,7 +176,7 @@ public class ScopeNode extends Node { public Var lookup( String name ) { int idx = find(name); // -1 is missed in all scopes, not found - return idx == -1 ? null : _update(_vars.at(idx),null); + return idx == -1 ? null : update(_vars.at(idx),null); } /** @@ -148,10 +188,10 @@ public class ScopeNode extends Node { public void update( String name, Node n ) { int idx = find(name); assert idx>=0; - _update(_vars.at(idx),n); + update(_vars.at(idx),n); } - Var _update( ScopeNode.Var v, Node st ) { + public Var update( ScopeNode.Var v, Node st ) { Node old = in(v._idx); if( old instanceof ScopeNode loop ) { // Lazy Phi! @@ -162,7 +202,7 @@ public class ScopeNode extends Node { // Set real Phi in the loop head // The phi takes its one input (no backedge yet) from a recursive // lookup, which might have insert a Phi in every loop nest. - : loop.setDef(v._idx,PhiNode.make(v._name, v._type instanceof TypeMemPtr ? v._type : v._type.glb(), loop.ctrl(), loop.in(loop._update(v,null)._idx),null).peephole()); + : loop.setDef(v._idx,PhiNode.make(v._name, v.lazyGLB(), loop.ctrl(), loop.in(loop.update(v,null)._idx),null).peephole()); setDef(v._idx,old); } if( st!=null ) setDef(v._idx,st); // Set new value @@ -189,8 +229,15 @@ public class ScopeNode extends Node { // 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 is one binding, with the same lazy loop Phi as scalar names. @@ -207,12 +254,12 @@ public class ScopeNode extends Node { * @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()); _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) { @@ -221,9 +268,9 @@ public class ScopeNode extends Node { // If we are in lazy phi mode we need to a lookup // by name as it will trigger a phi creation Var v = _vars.at(i); - Node lhs = this.in(this._update(v,null)); - Node rhs = that.in(that._update(v,null)); - setDef(i, PhiNode.make(v._name, v._type, r, lhs, rhs).peephole()); + Node lhs = this.in(this.update(v,null)); + Node rhs = that.in(that.update(v,null)); + setDef(i, PhiNode.make(v._name, v.type(), r, lhs, rhs).peephole()); } } @@ -273,50 +320,91 @@ public class ScopeNode extends Node { // 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. + public void addGuards( Node ctrl, Node pred, boolean invert ) { + assert ctrl instanceof CFGNode; + _guards.add(ctrl); // Marker between guard sets + // 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 + _addGuards(ctrl,pred,invert); + } - // 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 ) return null; + private void _addGuards( Node ctrl, Node pred, boolean invert ) { + if( pred==null || pred.isDead() ) + return; // A single negation is handled below. For !!p (including p != null), // also refine the underlying p without changing the Boolean result. if( pred instanceof NotNode not && not.in(1) instanceof NotNode ) { pred.keep(); // Recursive peepholes may rediscover this Not. - upcast(ctrl,not.in(1),!invert); + _addGuards(ctrl,not.in(1),!invert); pred.unkeep(); } // 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; + // Pop the guards up to this region's marker. + 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++ ) diff --git a/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/src/main/java/com/seaofnodes/simple/node/ShlNode.java index 4d673056..65dfe684 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -37,7 +37,7 @@ public class ShlNode extends Node { if( (shl.value()&63)==0 ) return lhs; // (x + c) << i => (x << i) + (c << i) - if( lhs instanceof AddNode add && add.in(2)._type instanceof TypeInteger c && c.isConstant() && c!=TypeInteger.ZERO ) { + if( lhs instanceof AddNode add && add.addDep(this).in(2)._type instanceof TypeInteger c && c.isConstant() && c!=TypeInteger.ZERO ) { long sum = c.value() << shl.value(); if( Integer.MIN_VALUE <= sum && sum <= Integer.MAX_VALUE ) return new AddNode( new ShlNode(add.in(1),rhs).peephole(), Parser.con(sum) ); diff --git a/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/src/main/java/com/seaofnodes/simple/node/ShrNode.java index bc6881f1..757fd69e 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -42,4 +42,9 @@ public class ShrNode extends Node { return null; } @Override Node copy(Node lhs, Node rhs) { return new ShrNode(lhs,rhs); } + @Override String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '>>>' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '>>>' " + in(2)._type; + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 23830a18..cefa2d72 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -3,16 +3,15 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; import com.seaofnodes.simple.type.*; -import java.util.BitSet; import java.util.HashSet; import static com.seaofnodes.simple.Utils.TODO; /** Start supplies control, whole memory, and the argument, in that order. */ -public class StartNode extends CFGNode implements MultiNode { +public class StartNode extends LoopNode implements MultiNode { final Type _arg; - public StartNode(Type arg) { super(); _arg = arg; _type = compute(); } + public StartNode(Type arg) { super(null); _arg = arg; _type = compute(); } @Override public String label() { return "Start"; } @@ -34,9 +33,4 @@ public class StartNode extends CFGNode implements MultiNode { @Override public int idepth() { return 0; } @Override public CFGNode idom(Node dep) { return null; } - @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { } - - @Override public int loopDepth() { return (_loopDepth=1); } - - @Override public Node getBlockStart() { return this; } } diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index 202afbd2..d0eb5750 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -2,9 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; -import com.seaofnodes.simple.Parser; - import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.GlobalCodeMotion; @@ -65,8 +64,6 @@ public class StopNode extends CFGNode { } @Override public CFGNode idom(Node dep) { return null; } - @Override public int loopDepth() { return (_loopDepth=1); } - public Node addReturn(Node node) { return addDef(node); } @@ -84,12 +81,9 @@ public class StopNode extends CFGNode { return this; } StopNode GCM() { - // Break infinite loops, forcing a Never-branch to exit - GlobalCodeMotion.fixLoops(this); + Parser.START.buildLoopTree(this); GlobalCodeMotion.buildCFG(this); return this; } - - @Override public Node getBlockStart() { return this; } } diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 8eb104a7..a5f04dd2 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -44,7 +44,10 @@ public class StoreNode extends MemOpNode { @Override public Type compute() { - Type t = val()._type.meet(MemMergeNode.contents(mem(),_alias,this)); + Type val = val()._type; + if( _declaredType.isFRef() && val instanceof TypeMemPtr tmp && !tmp.isFRef() ) + _declaredType = tmp; + Type t = val.join(_declaredType).meet(MemMergeNode.contents(mem(),_alias,this)); return TypeMem.make(_alias,t); } @@ -113,6 +116,9 @@ public class StoreNode extends MemOpNode { String err() { String err = super.err(); if( err != null ) return err; + TypeMemPtr tmp = (TypeMemPtr)ptr()._type; + if( tmp._ro || tmp._obj.field(_name)._final ) + return "Cannot modify final field '"+_name+"'"; Type t = val()._type; return _init || t.isa(_declaredType) ? null : "Cannot store "+t+" into field "+_declaredType+" "+_name; } diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index 134f7cd6..768cb2bf 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -22,6 +22,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/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index d023e1e7..7ba58e6f 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.type.TypeMem; -/** Chapter 16's view of the IR; browser, transport and layout are shared. */ +/** Chapter 17's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter<Node> { @Override protected String edgeName(Node n, int i) { diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index 0d6fce44..d774967b 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 16's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 17's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture<Node> { private Parser _parser; private Node _ret; diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java index e2c0aa59..71c2fded 100644 --- a/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/src/main/java/com/seaofnodes/simple/type/Field.java @@ -31,8 +31,10 @@ public class Field extends Type { return new Field(fname,type,alias,xfinal).intern(); } public Field makeFrom( Type type ) { - return new Field(_fname,type,_alias,_final).intern(); + return type == _type ? this : new Field(_fname,type,_alias,_final).intern(); } + @Override public Field makeRO() { return isFinal() ? this : make(_fname,_type.makeRO(),_alias,true); } + @Override public boolean isFinal() { return _final && _type.isFinal(); } public static final Field TEST = make("test",TypeInteger.ZERO,-2,false); public static void gather(ArrayList<Type> ts) { ts.add(TEST); } @@ -41,16 +43,20 @@ public class Field extends Type { Field fld = (Field)that; // Invariant assert _fname.equals(fld._fname); assert _alias==fld._alias; - assert _final==fld._final; - return make(_fname,_type.meet(fld._type),_alias,_final); + return make(_fname,_type.meet(fld._type),_alias,_final | fld._final); } @Override - public Field dual() { return make(_fname,_type.dual(),_alias,_final); } + public Field dual() { return make(_fname,_type.dual(),_alias,!_final); } - @Override - public Field glb() { - return make(_fname,_type.glb(),_alias,_final); + @Override public Field glb() { + Type glb = _type.glb(); + return glb==_type ? this : make(_fname,glb,_alias,_final); + } + + @Override public Field lub() { + Type lub = _type.lub(); + return lub==_type ? this : make(_fname,lub,_alias,_final); } // Override in subclasses @@ -64,7 +70,7 @@ public class Field extends Type { @Override public StringBuilder print( StringBuilder sb ) { - return _type.print(sb.append(_final?"!":"").append(_fname).append(":").append(_alias).append(" : ")); + return _type.print(sb.append(_final?"":"!").append(_fname).append(":").append(_alias).append(" : ")); } @Override public String str() { return _fname; } diff --git a/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index 989eff9e..60afb668 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -81,8 +81,6 @@ public class Type { */ public StringBuilder typeName( StringBuilder sb) { return print(sb); } - public Type makeInit() { return null; } - public Type nonZero() { return glb(); } // ---------------------------------------------------------- @@ -174,10 +172,32 @@ public class Type { // True if this "isa" t; e.g. 17 isa TypeInteger.BOT public boolean isa( Type t ) { return meet(t)==t; } - /** - * Compute greatest lower bound in the lattice - */ - public Type glb() { return _type==TCTRL ? XCONTROL : BOTTOM; } + /** Compute greatest lower bound in the lattice */ + public Type glb() { return _type==TCTRL ? CONTROL : BOTTOM; } + /** Compute least upper bound in the lattice */ + public Type lub() { return _type==TCTRL ? XCONTROL : TOP; } + + // Make an initial/default version of this type. Typically, 0 for integers + // and null for nullable pointers. + public Type makeInit() { return this; } + // Make a zero version of this type, 0 for integers and null for pointers. + public Type makeZero() { return null; } + // Make a non-zero version of this type, if possible. Integers attempt to + // exclude zero from their range and pointers become not-null. + public Type nonZero() { return glb(); } + + // Writable array slots are invariant in their element access permissions. + // Otherwise an alias could insert a readonly pointer into a writable slot. + public boolean accessISA(Type dst) { return true; } + + // Is forward-reference + public boolean isFRef() { return false; } + + // All reachable struct Fields are final + public boolean isFinal() { return true; } + + // Make all reachable struct Fields final + public Type makeRO() { return this; } // ---------------------------------------------------------- diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java index dc36c082..f85abbed 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -104,10 +104,10 @@ public class TypeFloat extends Type { return make((byte)-_sz,0); } - @Override - public Type glb() { return BOT; } - + @Override public Type glb() { return BOT; } + @Override public Type lub() { return TOP; } @Override public TypeFloat makeInit() { return ZERO; } + @Override public TypeFloat makeZero() { return ZERO; } @Override int hash() { return (int)(Double.hashCode(_con) ^ _sz); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index b475055d..b2979d7b 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/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(); } @@ -114,7 +115,9 @@ public class TypeInteger extends Type { @Override public TypeInteger dual() { return make(_max,_min); } @Override public TypeInteger glb() { return BOT; } + @Override public TypeInteger lub() { return TOP; } @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/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 76288d3e..6dcd401a 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -21,7 +21,7 @@ public class TypeMem extends Type { private TypeMem(int alias, Type t) { super(TMEM); _alias = alias; _t = t; } public static TypeMem make(int alias, Type t) { return new TypeMem(alias,t).intern(); } - public static final TypeMem TOP = make( 0, Type.TOP); + public static final TypeMem TOP = make(-1, Type.TOP ); public static final TypeMem BOT = make(-1, Type.BOTTOM); public static void gather(ArrayList<Type> ts) { ts.add(make(1,TypeInteger.ZERO)); ts.add(BOT); } @@ -40,13 +40,11 @@ public class TypeMem extends Type { @Override public Type dual() { - if( _alias== 0 ) return BOT; - if( _alias==-1 ) return TOP; return make(_alias,_t.dual()); } - @Override - public Type glb() { return make(_alias,_t.glb()); } + @Override public Type glb() { return make(_alias,_t.glb()); } + @Override public Type lub() { return make(_alias,_t.lub()); } @Override int hash() { return 9876543 + _alias + _t.hashCode(); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 9b628bea..8ecc8031 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -23,17 +23,41 @@ public class TypeMemPtr extends Type { // (TOP ,true ) - a nil public final TypeStruct _obj; + // Deep read-only access through this pointer; independent of slot finality. + public boolean _ro; + public final boolean _nil; private TypeMemPtr(TypeStruct obj, boolean nil) { super(TMEMPTR); assert obj!=null; _obj = obj; + _ro = obj==TypeStruct.BOT; _nil = nil; } public static TypeMemPtr make(TypeStruct obj, boolean nil) { return new TypeMemPtr(obj, nil).intern(); } public static TypeMemPtr make(TypeStruct obj) { return make(obj, false); } - public TypeMemPtr makeFrom(TypeStruct obj) { return make(obj, _nil); } + public TypeMemPtr makeFrom(TypeStruct obj) { return obj==_obj ? this : make(obj, _nil).withAccess(_ro); } + public TypeMemPtr makeFrom(boolean nil) { return nil==_nil ? this : make(_obj, nil).withAccess(_ro); } + @Override public TypeMemPtr makeRO() { return withAccess(true); } + @Override public boolean isFinal() { return _ro; } + + public TypeMemPtr withAccess(boolean ro) { + if( _ro==ro || (_obj==TypeStruct.TOP && _nil) ) return this; + TypeMemPtr ptr = new TypeMemPtr(_obj, _nil); + ptr._ro = ro; + return ptr.intern(); + } + + // Writable slots can load and store references, so their element access + // must agree in both directions. A read-only outer view can weaken access. + @Override public boolean accessISA(Type dst) { + if( !(dst instanceof TypeMemPtr ptr) ) return true; + if( _ro && !ptr._ro ) return false; + if( ptr._ro || _obj._fields==null || ptr._obj._fields==null || !_obj.isAry() || !ptr._obj.isAry() ) return true; + Type a = _obj._fields[1]._type, b = ptr._obj._fields[1]._type; + return a.accessISA(b) && b.accessISA(a); + } // An abstract pointer, pointing to either a Struct or an Array. // Can also be null or not. @@ -44,20 +68,23 @@ public class TypeMemPtr extends Type { public static final TypeMemPtr VOIDPTR = NULLPTR.dual(); // A bottom mix of not-null ptrs, like C's void* but not null public static final TypeMemPtr TEST= make(TypeStruct.TEST,false); - public static void gather(ArrayList<Type> ts) { ts.add(NULLPTR); ts.add(BOT); ts.add(TEST); } + public static void gather(ArrayList<Type> ts) { ts.add(NULLPTR); ts.add(BOT); ts.add(TEST); ts.add(TEST.makeRO()); } @Override Type xmeet(Type t) { TypeMemPtr that = (TypeMemPtr) t; - return TypeMemPtr.make((TypeStruct)_obj.meet(that._obj), _nil | that._nil); + return TypeMemPtr.make((TypeStruct)_obj.meet(that._obj), _nil | that._nil).withAccess(_ro | that._ro); } @Override - public TypeMemPtr dual() { return TypeMemPtr.make(_obj.dual(), !_nil); } - - @Override - public TypeMemPtr glb() { return make(_obj.glb(),true); } - @Override public TypeMemPtr makeInit() { return NULLPTR; } + public TypeMemPtr dual() { return TypeMemPtr.make(_obj.dual(), !_nil).withAccess(!_ro); } + + @Override public TypeMemPtr glb() { return make(_obj.glb(),true ).withAccess(true); } + @Override public TypeMemPtr lub() { return make(_obj.lub(),false); } + // Is forward-reference + @Override public boolean isFRef() { return _obj.isFRef(); } + @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; } @@ -67,12 +94,12 @@ public class TypeMemPtr extends Type { @Override public int log_size() { return 2; } // (1<<2)==4-byte pointers @Override - int hash() { return _obj.hashCode() ^ (_nil ? 1024 : 0); } + int hash() { return (_ro ? 8192 : 0) ^ _obj.hashCode() ^ (_nil ? 1024 : 0); } @Override boolean eq(Type t) { TypeMemPtr ptr = (TypeMemPtr)t; // Invariant - return _obj == ptr._obj && _nil == ptr._nil; + return _ro==ptr._ro && _obj == ptr._obj && _nil == ptr._nil; } // [void,name,MANY]*[,?] diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 75f24c03..97664e3c 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -36,21 +36,29 @@ public class TypeStruct extends Type { public static final TypeStruct BOT = make("$BOT",new Field[0]); public static final TypeStruct TEST = make("test",new Field[]{Field.TEST}); // Forward-ref version - public static TypeStruct make(String name) { return make(name, (Field[])null); } + public static TypeStruct makeFRef(String name) { return make(name, (Field[])null); } + // Make a read-only version + @Override public TypeStruct makeRO() { + if( isFinal() ) return this; + Field[] flds = new Field[_fields.length]; + for( int i=0; i<flds.length; i++ ) + flds[i] = _fields[i].makeRO(); + return make(_name,flds); + } // Array public static TypeStruct makeAry(TypeInteger len, int lenAlias, Type body, int bodyAlias) { assert !(body instanceof TypeMemPtr tmp && !tmp._nil); return make("[" + body.str() + "]", - Field.make("#" ,len , lenAlias,true), - Field.make("[]",body,bodyAlias,true)); + Field.make("#" ,len , lenAlias,true ), + Field.make("[]",body,bodyAlias,false)); } // A pair of self-cyclic types - private static final TypeStruct S1F = make("S1"); - private static final TypeStruct S2F = make("S2"); - public static final TypeStruct S1 = make("S1", new Field[]{ Field.make("a", TypeInteger.BOT, -1, false), Field.make("s2",TypeMemPtr.make(S2F,false),-2, false) }); - private static final TypeStruct S2 = make("S2", new Field[]{ Field.make("b", TypeFloat .BOT, -3, false), Field.make("s1",TypeMemPtr.make(S1F,false),-4, false) }); + private static final TypeStruct S1F = makeFRef("S1"); + private static final TypeStruct S2F = makeFRef("S2"); + public static final TypeStruct S1 = make("S1", Field.make("a", TypeInteger.BOT, -1, false), Field.make("s2",TypeMemPtr.make(S2F,false),-2, false) ); + private static final TypeStruct S2 = make("S2", Field.make("b", TypeFloat .BOT, -3, false), Field.make("s1",TypeMemPtr.make(S1F,false),-4, false) ); private static final TypeStruct ARY = makeAry(TypeInteger.BOT,-1,TypeFloat.BOT,-2); @@ -63,6 +71,10 @@ public class TypeStruct extends Type { return i; return -1; } + public Field field(String fname) { + int idx = find(fname); + return idx== -1 ? null : _fields[idx]; + } // Find field index by alias public int findAlias( int alias ) { @@ -89,8 +101,8 @@ public class TypeStruct extends Type { // And the answer is: "don't ask". if( !_name.equals(that._name) ) return BOT; // It's a struct; that's about all we know - if( this._fields==null ) return this; - if( that._fields==null ) return that; + if( this._fields==null ) return that; + if( that._fields==null ) return this; if( _fields.length != that._fields.length ) return BOT; // Just do field meets Field[] flds = new Field[_fields.length]; @@ -115,8 +127,7 @@ public class TypeStruct extends Type { } // Keeps the same struct, but lower-bounds all fields. - @Override - public TypeStruct glb() { + @Override public TypeStruct glb() { if( _glb() ) return this; // Need to glb each field Field[] flds = new Field[_fields.length]; @@ -131,6 +142,33 @@ public class TypeStruct extends Type { return false; return true; } + @Override public TypeStruct lub() { + if( _lub() ) return this; + // Need to glb each field + Field[] flds = new Field[_fields.length]; + for( int i=0; i<_fields.length; i++ ) + flds[i] = _fields[i].lub(); + return make(_name,flds); + } + private boolean _lub() { + if( _fields!=null ) + for( Field f : _fields ) + if( f.lub() != f ) + return false; + return true; + } + + + // Is forward-reference + @Override public boolean isFRef() { return _fields==null; } + // All fields are final + @Override public boolean isFinal() { + if( _fields==null ) return true; + for( Field fld : _fields ) + if( !fld.isFinal() ) + return false; + return true; + } @Override boolean eq(Type t) { @@ -163,10 +201,8 @@ public class TypeStruct extends Type { sb.append(_name); if( _fields == null ) return sb; // Forward reference struct, just print the name sb.append(" {"); - for( Field f : _fields ) { - sb.append(" ").append(f._fname).append(" :"); - f._type.print(sb).append("; "); - } + for( Field f : _fields ) + f._type.print(sb).append(f._final ? " " : " !").append(f._fname).append("; "); return sb.append("}"); } |