diff options
| author | Cliff Click <cliffc@acm.org> | 2024-10-21 09:25:15 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2025-02-07 09:12:14 -0800 |
| commit | 3407c35a22158835d1a0e0ff29bc0b825cdb1adc (patch) | |
| tree | 013987f86eccae0dec204cd9e001c843ccb498a7 /src | |
| parent | cd4ff0919b2d4489a1b6ceda0581c49bd87ba0de (diff) | |
| download | Simple-3407c35a22158835d1a0e0ff29bc0b825cdb1adc.tar.gz Simple-3407c35a22158835d1a0e0ff29bc0b825cdb1adc.zip | |
Chapter 17: Syntax Sugar
Co-authored-by: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Diffstat (limited to 'src')
52 files changed, 1628 insertions, 695 deletions
diff --git a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 29841266..9698abd9 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,7 +29,7 @@ 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); if( cfg instanceof RegionNode ) @@ -138,14 +101,13 @@ 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 if( n instanceof LoadNode ld ) for( Node memuse : ld.mem()._outputs ) - if( !(memuse instanceof PhiNode) && - late[memuse._nid]==null && + if( late[memuse._nid]==null && // Load-use directly defines memory (memuse._type instanceof TypeMem || // Load-use indirectly defines memory @@ -211,7 +173,7 @@ public abstract class GlobalCodeMotion { // Least loop depth first, then largest idepth private static boolean better( CFGNode lca, CFGNode best ) { - return lca._loopDepth < best._loopDepth || + return lca.loopDepth() < best.loopDepth() || (lca.idepth() > best.idepth() || best instanceof IfNode); } @@ -251,9 +213,9 @@ public abstract class GlobalCodeMotion { // private static CFGNode anti_dep( LoadNode load, CFGNode stblk, CFGNode defblk, CFGNode lca, Node st ) { // Walk store blocks "reach" from its scheduled location to its earliest - for( ; stblk != defblk; stblk = stblk.idom() ) { + for( ; stblk != defblk.idom(); stblk = stblk.idom() ) { // Store and Load overlap, need anti-dependence - if( !(stblk instanceof IfNode) && stblk._anti==load._nid ) { + if( stblk._anti==load._nid ) { lca = stblk._idom(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/IRPrinter.java b/src/main/java/com/seaofnodes/simple/IRPrinter.java index 418cda29..7ef55a3f 100644 --- a/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -216,10 +216,11 @@ public class IRPrinter { // Print block header sb.append("%-13.13s".formatted(label(blk)+":")); sb.append( " ".repeat(4) ).append(" [[ "); - if( blk instanceof RegionNode || blk instanceof StopNode ) + if( blk instanceof StartNode ) ; + else if( blk instanceof RegionNode || blk instanceof StopNode ) for( int i=(blk instanceof StopNode ? 0 : 1); i<blk.nIns(); i++ ) label(sb,blk.cfg(i)); - else if( !(blk instanceof StartNode) ) + else label(sb,blk.cfg(0)); sb.append(" ]] \n"); diff --git a/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java index 96ae350e..36f053f9 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> */ @@ -113,9 +113,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 a8064e17..5a44b63e 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -2,7 +2,6 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; -import static com.seaofnodes.simple.Utils.TODO; import java.util.*; @@ -91,12 +90,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; @@ -141,6 +140,8 @@ public class Parser { put("u16" ,TypeInteger.U16); put("u32" ,TypeInteger.U32); put("u8" ,TypeInteger.U8 ); + put("val" ,Type.TOP); // Marker type, indicates type inference + put("var" ,Type.BOTTOM); // Marker type, indicates type inference }}; } @@ -148,7 +149,7 @@ public class Parser { public static Node find(int nid) { return START.find(nid); } private Node ctrl() { return _scope.ctrl(); } - private Node ctrl(Node n) { return _scope.ctrl(n); } + private <N extends Node> N ctrl(N n) { return _scope.ctrl(n); } public StopNode parse() { return parse(false); } public StopNode parse(boolean show) { @@ -163,11 +164,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(); @@ -187,9 +188,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 @@ -208,18 +209,19 @@ 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("for") ) return parseFor(); else if (matchx("break") ) return parseBreak(); else if (matchx("continue")) return parseContinue(); else if (matchx("struct") ) return parseStruct(); else if (matchx("#showGraph")) return require(showGraph(),";"); 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 * @@ -229,11 +231,40 @@ public class Parser { * @return a {@link Node}, never {@code null} */ private Node parseWhile() { + require("("); + return parseLooping(false); + } - var savedContinueScope = _continueScope; - var savedBreakScope = _breakScope; + /** + * Parses a for statement + * + * <pre> + * for( var x=init; test; incr ) body + * </pre> + * @return a {@link Node}, never {@code null} + */ + private Node parseFor() { + // { var x=init,y=init,...; + // while( pred ) { + // body; + // next; + // } + // } require("("); + _scope.push(); // Scope for the index variables + if( !match(";") ) // Can be empty init "for(;test;next) body" + parseDeclarationStatement(); // Non-empty init + Node rez = parseLooping(true); + _scope.pop(); // Exit index variable scope + return rez; + } + + // Shared by `for` and `while` + private Node parseLooping( boolean doFor ) { + + var savedContinueScope = _continueScope; + var savedBreakScope = _breakScope; // Loop region has two control inputs, the first is the entry // point, and second is back edge that is set after loop is parsed @@ -254,19 +285,32 @@ public class Parser { _xScopes.push(_scope = _scope.dup(true)); // The true argument triggers creating phis // Parse predicate - var pred = require(parseExpression(), ")"); + var pred = peek(';') ? con(1) : parseAsgn(); + require( doFor ? ";" : ")" ); + // 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(); + // for( ;;next ) body + int nextPos = -1, nextEnd = -1; + if( doFor ) { + // Skip the next expression and parse it later + nextPos = pos(); + skipAsgn(); + nextEnd = pos(); + require(")"); + } + // Clone the body Scope to create the break/exit Scope which accounts for any // side effects in the predicate. The break/exit Scope will be the final // scope after the loop, and its control input is the False branch of // 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; @@ -274,7 +318,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) { @@ -283,6 +329,16 @@ public class Parser { _scope = _continueScope; } + // Now append the next code onto the body code + if( doFor ) { + int old = pos(nextPos); + if( !peek(')') ) + parseAsgn(); + if( pos() != nextEnd ) + throw errorSyntax( "Unexpected code after expression" ); + pos(old); + } + // The true branch loops back, so whatever is current _scope.ctrl gets // added to head loop as input. endLoop() updates the head scope, and // goes through all the phis that were created earlier. For each phi, @@ -302,7 +358,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) { @@ -319,14 +376,41 @@ 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; + } + + // Look for an unbalanced `)`, skipping balanced + private Type skipAsgn() { + int paren=0; + while( true ) + // Next X char handles skipping complex comments + switch( _lexer.nextXChar() ) { + case Character.MAX_VALUE: + throw Utils.TODO(); + case ')': + if( --paren<0 ) + return posT(pos()-1); // Leave the `)` behind + break; + case '(': paren ++; break; + default: break; + } + } + /** * Parses a statement @@ -337,9 +421,16 @@ public class Parser { * @return a {@link Node}, never {@code null} */ private Node parseIf() { - require("("); // Parse predicate - var pred = require(parseExpression(), ")").keep(); + require("("); + var pred = require(parseAsgn(), ")"); + return parseTrinary(pred,true,"else"); + } + + // Parse a conditional expression, merging results. + private Node parseTrinary( Node pred, boolean stmt, String fside ) { + pred.keep(); + // IfNode takes current control and predicate Node ifNode = new IfNode(ctrl(), pred).peephole(); // Setup projection nodes @@ -353,31 +444,48 @@ 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 + Node lhs = stmt ? parseStatement() : parseAsgn().keep(); // Parse true-side + _scope.removeGuards(ifT); + ScopeNode tScope = _scope; // Parse the false side _scope = fScope; // Restore scope, then parse else block if any ctrl(ifF.unkeep()); // Ctrl token is now set to ifFalse projection - _scope.upcast(ifF,pred,true); // Up-cast predicate - if (matchx("else")) { - parseStatement(); + // Up-cast predicate, even if not else clause, because predicate can + // remain true if the true clause exits: `if( !ptr ) return 0; return ptr.fld;` + _scope.addGuards(ifF,pred,true); + boolean doRHS = match(fside); + Node rhs = doRHS + ? (stmt ? parseStatement() : parseAsgn()) + : (stmt ? null : con(lhs._type.makeZero())); + _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"); + // Check the trinary widening int/flt + if( !stmt ) { + rhs = widenInt( rhs, lhs._type ).keep(); + lhs = widenInt( lhs.unkeep(), rhs._type ).keep(); + rhs.unkeep(); + } + // Merge results _scope = tScope; _xScopes.pop(); // Discard pushed from graph display - return ctrl(tScope.mergeScopes(fScope)); + RegionNode r = ctrl(tScope.mergeScopes(fScope)); + Node ret = stmt ? r : peep(new PhiNode("",lhs._type.meet(rhs._type),r,lhs.unkeep(),rhs)); + r.peephole(); + return ret; } - /** * Parses a return statement; "return" already parsed. * The $ctrl edge is killed. @@ -388,7 +496,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; @@ -403,101 +511,120 @@ public class Parser { return null; } - /** Parse: name [=expr] + /** Parse: [name '='] expr */ - private Node parseAsgn(Type t, boolean xfinal) { - boolean isDecl = t!=null; // Having a type is a declaration, missing one is updating a prior name - int old = _lexer._position; - String name = requireId(); - Node expr; - if( peek(';') || peek(',') ) { - // Bare "name" is not allowed - if( t==null ) throw errorSyntax("expression"); - // Does this declaration need an initializer and not getting one? - Type init = xfinal || t instanceof TypeMemPtr tmp && !tmp._nil - // Must be initialized in the "new" constructor - ? Type.TOP - // Else takes the default - : t.makeInit(); - 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 - ScopeMinNode.Var def = _scope.lookup(name); - if( def==null ) - throw error("Undefined name '" + name + "'"); - // TOP fields are for late-initialized fields; these have never - // been written to, and this must be the final write. Other writes - // need to check the final bit. - if( _scope.in(def._idx)._type!=Type.TOP && def._final ) - throw error("Cannot reassign final '"+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 + ScopeMinNode.Var def = _scope.lookup(name); + if( def==null ) + throw error("Undefined name '" + name + "'"); + + // TOP fields are for late-initialized fields; these have never + // been written to, and this must be the final write. Other writes + // outside the constructor need to check the final bit. + if( _scope.in(def._idx)._type!=Type.TOP && def._final && !_scope.inCon() ) + throw error("Cannot reassign final '"+name+"'"); + + // Lift expression, based on type + Node lift = liftExpr(expr, def.type(), def._final); + // Update + _scope.update(name,lift); + // Return un-lifted expr + return expr; + } + // Make finals deep; widen ints to floats; narrow wide int types. + // Early error if types do not match variable. + private Node liftExpr( Node expr, Type t, boolean xfinal ) { + assert !(expr._type instanceof TypeMemPtr tmp) || !tmp.isFRef(); + // Final is deep on ptrs + if( xfinal && t instanceof TypeMemPtr tmp ) { + t = tmp.makeRO(); + 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,xfinal,expr) ) - throw error("Redefining name '" + name + "'"); - } else - _scope.update(name,expr); + if( !expr._type.isa(t) ) + throw error("Type " + expr._type.str() + " is not of declared type " + t.str()); return expr; } - /** Parse final: [!]asgn - */ - private Node parseFinal(Type t) { - boolean xfinal = t!=null && match("!"); - return parseAsgn(t,xfinal); + private Node widenInt( Node expr, Type t ) { + return expr._type instanceof TypeInteger && t instanceof TypeFloat + ? peep(new ToFloatNode(expr)) : 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 - - * </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 ) { - // now parse final [, final]* - n = parseFinal(t); - while( match(",") ) - n = parseFinal(t); - - // Parse "asgn;" which is just "name = expr;" - } else if( ( n = parseAsgn(null,false)) == 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,";"); } + /** Parse final: [!]var['=' asgn] + */ + private Node parseDeclaration(Type t) { + assert t!=null; + // Has var/val instead of a user-declared type + boolean inferType = t==Type.TOP || t==Type.BOTTOM; + boolean hasBang = match("!"); + String name = requireId(); + + // Optional initializing expression follows + boolean xfinal = false; + Node expr; + if( match("=") ) { + expr = parseAsgn(); + // `val` is always final + xfinal = (t==Type.TOP) || + // var is always not-final, final if no Bang AND TMP since primitives are not-final by default + (t!=Type.BOTTOM && !hasBang && (t instanceof TypeMemPtr)); + // var/val, then type comes from expression + if( inferType ) + t = expr._type.glb(); + + } else { + if( inferType && !_scope.inCon() ) + throw errorSyntax("=expression"); + expr = con(t.makeInit()); + } + + // Lift expression, based on type + Node lift = liftExpr(expr, t, xfinal); + if( xfinal && t instanceof TypeMemPtr tmp ) + t = tmp.makeRO(); + + // 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. @@ -510,11 +637,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(); @@ -527,7 +655,7 @@ public class Parser { for( int i=lexlen; i<varlen; i++ ) { s.addDef(_scope.in(i)); ScopeMinNode.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)); @@ -535,6 +663,7 @@ public class Parser { // Done with struct/block scope require("}"); require(";"); + _xScopes.pop(); _scope.pop(); return null; } @@ -544,44 +673,45 @@ 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 | val | var | struct[?] private Type type() { - int old1 = _lexer._position; + int old1 = pos(); String tname = _lexer.matchId(); if( tname==null ) return null; // 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 // 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 = TypeMemPtr.make(tmp._obj,true); + } 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(); 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; + return t2; } // Make an array type of t @@ -599,16 +729,28 @@ public class Parser { return tary; } + // Fixup forward refs lazily. Basically a Union-Find flavored read + // barrier. + Type lazyFRef(Type t) { + //if( !t.isFRef() ) return t; + //Type def = Parser.TYPES.get(((TypeMemPtr)t)._obj._name); + throw Utils.TODO(); + + } + /** * Parse an expression of the form: * * <pre> - * expr : compareExpr + * expr : bitwise [? expr [: expr]] * </pre> * @return an expression {@link Node}, never {@code null} */ - private Node parseExpression() { return parseBitwise(); } + private Node parseExpression() { + Node expr = parseBitwise(); + return match("?") ? parseTrinary(expr,false,":") : expr; + } /** * Parse an bitwise expression @@ -627,7 +769,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; } @@ -655,9 +797,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; } @@ -679,7 +821,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; } @@ -700,7 +842,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; } @@ -721,7 +863,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; } @@ -730,13 +872,31 @@ 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(); + // Pre-dec/pre-inc + int old = pos(); + if( match("--") || match("++") ) { + int delta = _lexer.peek(-1)=='+' ? 1 : -1; // Pre vs post + String name = _lexer.matchId(); + if( name!=null ) { + ScopeMinNode.Var n = _scope.lookup(name); + if( n != null ) { + if( n._final ) + throw error("Cannot reassign final '"+n._name+"'"); + Node expr = zsMask(peep(new AddNode(_scope.in(n),con(delta))),n.type()); + _scope.update(n,expr); + return expr; + } + } + // Reset, try again + pos(old); + } + if (match("-")) return peep(new MinusNode(parseUnary()).widen()); + if (match("!")) return peep(new NotNode(parseUnary())); return parsePostfix(parsePrimary()); } @@ -744,23 +904,55 @@ 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"); - ScopeMinNode.Var n = _scope.lookup(name); - if( n!=null ) return _scope.in(n); - throw error("Undefined name '" + name + "'"); + ScopeMinNode.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+"'"); + // Check for assign-update, x += e0; + char ch = _lexer.matchOperAssign(); + if( ch==0 ) return rvalue; + if( n._final ) + throw error("Cannot reassign final '"+n._name+"'"); + Node op = switch(ch) { + case '+' -> new AddNode(rvalue,null); + case '-' -> new SubNode(rvalue,null); + case '*' -> new MulNode(rvalue,null); + case '/' -> new DivNode(rvalue,null); + case 1 -> new AddNode(rvalue,con( 1)); + case (char)-1 -> new AddNode(rvalue,con(-1)); + default -> throw Utils.TODO(); + }; + // Return pre-value (x+=1) or post-value (x++) + boolean pre = op.in(2)==null; + // Parse RHS argument as needed + if( pre ) + { op.keep().setDef(2,parseAsgn()); op.unkeep(); } + else rvalue.keep(); // Keep post-value across peeps + op = zsMask(peep(op),n.type()); + _scope.update(n,op); + return pre ? op : rvalue.unkeep(); + } + + ScopeMinNode.Var requireLookupId(String msg) { + String id = _lexer.matchId(); + if( id == null || KEYWORDS.contains(id) ) + throw errorSyntax(msg); + ScopeMinNode.Var n = _scope.lookup(id); + if( n==null ) + throw error("Undefined name '" + id + "'"); + return n; } /** @@ -771,7 +963,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("]"); @@ -796,15 +988,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 ) @@ -843,8 +1035,8 @@ 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 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); } @@ -868,7 +1060,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 @@ -882,44 +1074,66 @@ 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() + "'"); + if( tmp == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr + "'"); TypeStruct base = 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); - 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('=','=') ) { - Node val = parseExpression(); - // Auto-truncate when storing to narrow fields - val = zsMask(val,f._type); - Node st = new StoreNode(name, f._alias, f._type, memAlias(f._alias), expr, off, val, false); + Node val = parseAsgn().keep(); + Node lift = liftExpr( val, tf, f._final ); + + Node st = new StoreNode(name, f._alias, tf, memAlias(f._alias), expr, off.unkeep(), lift, false); // Arrays include control, as a proxy for a safety range check. // Structs don't need this; they only need a NPE check which is // done via the type system. if( base.isAry() ) st.setDef(0,ctrl()); memAlias(f._alias, st.peephole()); - return val; // "obj.a = expr" returns the expression while updating memory + return val.unkeep(); // "obj.a = expr" returns the expression while updating memory } - Node load = new LoadNode(name, f._alias, f._type.glb(), memAlias(f._alias), expr, off); + Node load = new LoadNode(name, f._alias, tf.glb(), memAlias(f._alias), expr.keep(), 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); + + // ary[idx]++ or ptr.fld++ + if( matchx("++") || matchx("--") ) { + if( f._final && !f._fname.equals("[]") ) + throw error("Cannot reassign final '"+f._fname+"'"); + Node inc = peep(new AddNode(load,con( _lexer.peek(-1)=='+' ? 1 : -1))); + Node val = zsMask(inc,tf); + Node st = new StoreNode(name, f._alias, tf, memAlias(f._alias), expr.unkeep(), off, val, false); + // Arrays include control, as a proxy for a safety range check. + // Structs don't need this; they only need a NPE check which is + // done via the type system. + if( base.isAry() ) st.setDef(0,ctrl()); + memAlias(f._alias, peep(st)); + // And use the original loaded value as the result + } else expr.unkill(); + off.unkill(); + + return parsePostfix(load); } @@ -930,16 +1144,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())); } @@ -954,6 +1168,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 @@ -967,14 +1185,29 @@ public class Parser { private boolean peek(char ch) { return _lexer.peek(ch); } private boolean peekIsId() { return _lexer.peekIsId(); } + private int pos() { return _lexer._position; } + 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; } @@ -1031,6 +1264,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(); @@ -1059,6 +1294,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. @@ -1165,12 +1402,28 @@ 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); } + + // Next oper= character, or 0. + // As a convenience, mark "++" as a char 1 and "--" as char -1 (65535) + // Disallow e.g. "arg--1" which should parse as "arg - -1" + public char matchOperAssign() { + skipWhiteSpace(); + if( _position+2 >= _input.length ) return 0; + char ch0 = (char)_input[_position]; + if( "+-/*&|^".indexOf(ch0) == -1 ) return 0; + char ch1 = (char)_input[_position+1]; + if( ch1 == '=' ) { _position += 2; return ch0; } + if( isIdLetter((char)_input[_position+2]) ) return 0; + if( ch0 == '+' && ch1 == '+' ) { _position += 2; return (char) 1; } + if( ch0 == '-' && ch1 == '-' ) { _position += 2; return (char)-1; } + return 0; + } } } diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index f3b213fb..0834a381 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -36,7 +36,7 @@ public class AddNode extends Node { return TypeInteger.BOT; } - private static boolean overflow( long x, long y ) { + static boolean overflow( long x, long y ) { if( (x ^ y ) < 0 ) return false; // unequal signs, never overflow return (x ^ (x + y)) < 0; // sum has unequal signs, so overflow } diff --git a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 9e9d6970..052ad8fc 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 @@ -64,27 +55,78 @@ 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; } - // Anti-dependence field support public int _anti; // Per-CFG field to help find anti-deps // ------------------------------------------------------------------------ - // 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 3d6fd1fa..d2f1bbe1 100644 --- a/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -52,10 +52,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/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 3cce89ab..513b4721 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -43,6 +43,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; } @@ -60,12 +63,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 d15d4f83..1528f2e9 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -33,10 +33,13 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { - if( mem()._type instanceof TypeMem mem && - // No constant folding if ptr might null-check - _declaredType != mem._t && err()==null ) { - return _declaredType.join(mem._t); + if( mem()._type instanceof TypeMem mem ) { + // Update declared forward ref to the actual + if( _declaredType.isFRef() && mem._t instanceof TypeMemPtr tmp && !tmp.isFRef() ) + _declaredType = tmp; + // No lifting if ptr might null-check + if( err()==null ) + return _declaredType.join(mem._t); } return _declaredType; } @@ -60,13 +63,15 @@ public class LoadNode extends MemOpNode { // 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 ) { switch( mem ) { case StoreNode st: if( 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( !off()._type.join(st.off()._type).isHigh() && // Offsets overlap !neverAlias(ptr,st.ptr()) ) // And might alias @@ -79,11 +84,13 @@ 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.in(_alias);// Bypass unrelated New break; + } else if( mproj.in(0) instanceof StartNode ) { + break outer; } else throw Utils.TODO(); default: throw Utils.TODO(); @@ -98,7 +105,11 @@ public class LoadNode extends MemOpNode { // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; if( mem() instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 && - off() instanceof ConstantNode ) { + // Offset can be hoisted + off() instanceof ConstantNode && + // Pointer can be hoisted + hoistPtr(ptr,memphi) ) { + // Profit on RHS/Loop backedge if( profit(memphi,2) || // Else must not be a loop to count profit on LHS. @@ -111,10 +122,12 @@ public class LoadNode extends MemOpNode { return null; } + private Node ld( int idx ) { Node mem = mem(), ptr = ptr(); return new LoadNode(_name,_alias,_declaredType,mem.in(idx),ptr instanceof PhiNode && ptr.in(0)==mem.in(0) ? ptr.in(idx) : ptr, off()).peephole(); } + private static boolean neverAlias( Node ptr1, Node ptr2 ) { return ptr1.in(0) != ptr2.in(0) && // Unrelated allocations @@ -122,6 +135,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); @@ -130,4 +162,11 @@ public class LoadNode extends MemOpNode { if( px instanceof StoreNode st1 && ptr()==st1.ptr() && off()==st1.off() ) { px.addDep(this); return true; } return false; } + + // Read-Only is a deep property, and cannot be cast-away + private Node castRO(Node rez) { + if( ptr()._type.isFinal() && !rez._type.isFinal() ) + return new ReadOnlyNode(rez).peephole(); + return rez; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 22862cb9..ecda9c63 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 c7a1efec..82aab8ac 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 8a2c9406..760a4274 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; +import com.seaofnodes.simple.Utils; import java.util.BitSet; @@ -22,7 +23,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 TypeInteger.TOP.meet(in(1)._type); } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 462a403c..3827fdac 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -153,7 +153,7 @@ public abstract class Node implements OutNode { * @param new_def the new definition * @return new_def for flow coding */ - public Node setDef(int idx, Node new_def ) { + public <N extends Node> N setDef(int idx, N new_def ) { unlock(); Node old_def = in(idx); if( old_def == new_def ) return new_def; // No change @@ -267,6 +267,10 @@ public abstract class Node implements OutNode { } // Test "keep" status public boolean iskeep() { return _outputs.find(null) != -1; } + public void unkill() { + if( unkeep().isUnused() ) + kill(); + } // Replace self with nnn in the graph, making 'this' go dead @@ -278,6 +282,7 @@ public abstract class Node implements OutNode { int idx = n._inputs.find(this); n._inputs.set(idx,nnn); nnn.addUse(n); + IterPeeps.addAll(n._outputs); } kill(); } @@ -419,7 +424,7 @@ public abstract class Node implements OutNode { * 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> @@ -542,9 +547,6 @@ public abstract class Node implements OutNode { /** Is this Node Memory related */ public boolean isMem() { return false; } - /** Return block start from a isCFG() */ - public Node getBlockStart() { return null; } - /** Pinned in the schedule; these are data nodes whose input#0 is not allowed to change */ public boolean isPinned() { return false; } diff --git a/src/main/java/com/seaofnodes/simple/node/NotNode.java b/src/main/java/com/seaofnodes/simple/node/NotNode.java index ffd3e01e..664d7c7b 100644 --- a/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -28,15 +28,14 @@ public class NotNode extends Node { // top->top, bot->bot, null->1, *void->0, not-null ptr->0, ptr/nil->bot // If input in null then true // If input is not null ptr then false - if( p0 == TypeMemPtr.TOP ) return TypeInteger.TOP; - if( p0 == TypeMemPtr.NULLPTR ) return TypeInteger.constant(1); - if( !p0._nil ) return TypeInteger.constant(0); - return TypeInteger.BOT; + if( p0 == TypeMemPtr.NULLPTR ) return TypeInteger.TRUE; + if( !p0._nil ) return TypeInteger.FALSE; + return TypeInteger.BOOL; case Type t: if( t0.getClass() != Type.class ) // Only doing NOT on ints and ptrs throw Utils.TODO(); - return t0==Type.TOP ? Type.TOP : Type.BOTTOM; + return TypeInteger.BOOL; } } diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index f0140ce6..cb266ca3 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -47,7 +47,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. @@ -101,7 +101,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..fddcaa67 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/ReadOnlyNode.java @@ -0,0 +1,29 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMemPtr; + +import java.util.BitSet; + +/** + * 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 + StringBuilder _print1(StringBuilder sb, BitSet visited) { + return in(1)._print0(sb.append("(const)"),visited); + } + @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 941de76b..fb39af17 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -18,7 +18,7 @@ public class RegionNode extends CFGNode { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { - return sb.append(label()).append(_nid); + return sb.append(label()); } @Override public boolean isMultiHead() { return true; } @@ -72,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 +108,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 +117,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 de4eba52..b586a44f 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -47,6 +47,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/ScopeMinNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java index e4874e15..9134f9c3 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java @@ -14,16 +14,29 @@ public class ScopeMinNode extends Node { /** 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 ScopeMinNode() { _type = TypeMem.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 11e54d82..86aa7665 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,8 +1,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.Ary; import com.seaofnodes.simple.type.*; import java.util.*; @@ -29,13 +27,22 @@ public class ScopeNode extends ScopeMinNode { // Since of each nested lexical scope public final Ary<Integer> _lexSize; + // True if parsing inside of a constructor + public final Ary<Boolean> _inCons; + + // Extra guards; tested predicates and casted results + private final Ary<Node> _guards; // A new ScopeNode - public ScopeNode() { _vars = new Ary<>(Var.class); _lexSize = new Ary<>(Integer.class); } + public ScopeNode() { + _vars = new Ary<>(Var .class); + _lexSize= new Ary<>(Integer.class); + _inCons = new Ary<>(Boolean.class); + _guards = new Ary<>(Node .class); + } @Override public String label() { return "Scope"; } - @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { sb.append("Scope[ "); @@ -43,7 +50,7 @@ public class ScopeNode extends ScopeMinNode { for( int i=0; i<nIns(); i++ ) { if( j < _lexSize._len && i == _lexSize.at(j) ) { sb.append("| "); j++; } Var v = _vars.get(i); - v._type.print(sb); + v.type().print(sb); sb.append(" "); if( v._final ) sb.append("!"); sb.append(v._name); @@ -75,17 +82,24 @@ public class ScopeNode extends ScopeMinNode { * * @return Node that was bound */ - public Node ctrl(Node n) { return setDef(0,n); } + public <N extends Node> N ctrl(N n) { return setDef(0,n); } - public void push() { + public void push() { push(false); } + public void push(boolean inCon) { + assert _lexSize._len==_inCons._len; _lexSize.push(_vars.size()); + _inCons.push(inCon); } public void pop() { + assert _lexSize._len==_inCons._len; int n = _lexSize.pop(); + _inCons.pop(); popUntil(n); _vars.setLen(n); } + public boolean inCon() { return _inCons.last(); } + // Find name in reverse, return an index into _vars or -1. Linear scan // instead of hashtable, but probably doesn't matter until the scan // typically hits many dozens of variables. @@ -125,7 +139,7 @@ public class ScopeNode extends ScopeMinNode { 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); } /** @@ -137,10 +151,10 @@ public class ScopeNode extends ScopeMinNode { 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! @@ -151,7 +165,7 @@ public class ScopeNode extends ScopeMinNode { // 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,new PhiNode(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,new PhiNode(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 @@ -178,8 +192,15 @@ public class ScopeNode extends ScopeMinNode { // 1) duplicate the name bindings of the ScopeNode across all stack levels // 2) Make the new ScopeNode a user of all the nodes bound // 3) Ensure that the order of defs is the same to allow easy merging - dup._vars.addAll(_vars); + dup._vars .addAll(_vars ); dup._lexSize.addAll(_lexSize); + dup._inCons .addAll(_inCons ); + dup._guards .addAll(_guards ); + // The dup'd guards all need dup'd keepers, to keep proper accounting + // when later removing all guards + for( Node n : _guards ) + if( !(n instanceof CFGNode) ) + n.keep(); dup.addDef(ctrl()); // Control input is just copied // Memory input is a shallow copy @@ -208,13 +229,13 @@ public class ScopeNode extends ScopeMinNode { * @param that The ScopeNode to be merged into this * @return A new node representing the merge point */ - public Node mergeScopes(ScopeNode that) { + public RegionNode mergeScopes(ScopeNode that) { RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep()); mem()._merge(that.mem(),r); this ._merge(that ,r); that.kill(); // Kill merged scope IterPeeps.add(r); - return r.unkeep().peephole(); + return r.unkeep(); } private void _merge(ScopeNode that, RegionNode r) { @@ -223,9 +244,9 @@ public class ScopeNode extends ScopeMinNode { // 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, new PhiNode(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, new PhiNode(v._name, v.type(), r, lhs, rhs).peephole()); } } @@ -264,42 +285,78 @@ public class ScopeNode extends ScopeMinNode { // Up-casting: using the results of an If to improve a value. // E.g. "if( ptr ) ptr.field;" is legal because ptr is known not-null. - - // This Scope looks for direct variable uses, or certain simple - // combinations, and replaces the variable with the upcast variant. - public Node upcast( Node ctrl, Node pred, boolean invert ) { + public void addGuards( Node ctrl, Node pred, boolean invert ) { + assert ctrl instanceof CFGNode; + _guards.add(ctrl); // Marker to distinguish 0,1,2 guards + // add pred & its cast to the normal input list, with special Vars + if( ctrl._type == Type.XCONTROL || pred==null || pred.isDead() ) + return; // Dead, do not add any guards // Invert the If conditional if( invert ) pred = pred instanceof NotNode not ? not.in(1) : IterPeeps.add(new NotNode(pred).peephole()); - - // Direct use of a value as predicate. This is a zero/null test. - if( _inputs.find(pred) != -1 ) { - if( !(pred._type instanceof TypeMemPtr tmp) ) - // Must be an `int`, since int and ptr are the only two value types - // being tested. No representation for a generic not-null int, so no upcast. - return null; - if( tmp.isa(TypeMemPtr.VOIDPTR) ) - return null; // Already not-null, no reason to upcast - // Upcast the ptr to not-null ptr, and replace in scope - return replace(pred,new CastNode(TypeMemPtr.VOIDPTR,ctrl,pred).peephole()); + // This is a zero/null test. + // Compute the positive test type. + Type tnz = pred._type.nonZero(); + Type tcast = tnz.join(pred._type); + if( tcast != pred._type ) { + Node cast = new CastNode(tnz,ctrl,pred.keep()).peephole().keep(); + _guards.add(pred); + _guards.add(cast); + replace(pred,cast); } + // Compute the negative test type. if( pred instanceof NotNode not ) { - // Direct use of a !value as predicate. This is a zero/null test. - if( _inputs.find(not.in(1)) != -1 ) { - Type tinit = not.in(1)._type.makeInit(); - if( not.in(1)._type.isa(tinit) ) return null; // Already zero/null, no reason to upcast - return replace(not.in(1), new ConstantNode(tinit).peephole()); + Node npred = not.in(1); + Type tzero = npred._type.makeZero(); + Type tzcast= tzero.join(npred._type); + if( tzcast != npred._type ) { + Node cast = new CastNode(tzero,ctrl,npred.keep()).peephole().keep(); + _guards.add(npred); + _guards.add( cast); + replace(npred,cast); } } - // Apr/9/2024: Attempted to replace X with Y if guarded by a test of - // X==Y. This didn't seem to help very much, or at least in the test - // cases seen so far was a very minor help. + } + + // Remove matching pred/cast pairs from this guarded region. + public void removeGuards( Node ctrl ) { + assert ctrl instanceof CFGNode; + // 0,1 or 2 guards + while( true ) { + Node g = _guards.pop(); + if( g == ctrl ) break; + if( g instanceof CFGNode ) continue; + g .unkill(); // Pop/kill cast + _guards.pop().unkill(); // Pop/kill pred + } + } - // No upcast - return null; + // 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 b67d985a..6fd951e4 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -44,7 +44,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/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index c03a4b06..ab6e4931 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -14,11 +14,11 @@ import static com.seaofnodes.simple.Utils.TODO; * In ch10 we also add mem aliases as structs get defined; each field in struct * adds a distinct alias to Start's tuple. */ -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"; } @@ -41,9 +41,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 0eacc1f4..867225cb 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.GlobalCodeMotion; import com.seaofnodes.simple.GraphVisualizer; @@ -63,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); } @@ -77,13 +76,10 @@ public class StopNode extends CFGNode { return this; } StopNode GCM(boolean show) { - // Break infinite loops, forcing a Never-branch to exit - GlobalCodeMotion.fixLoops(this); + Parser.START.buildLoopTree(this); if( show ) System.out.println(new GraphVisualizer().generateDotOutput(this,null,null)); 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 7b1bddd5..62b49a1a 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -42,9 +42,15 @@ public class StoreNode extends MemOpNode { public Type compute() { Type val = val()._type; TypeMem mem = (TypeMem)mem()._type; // Invariant - Type t = mem._alias==_alias - ? val.meet(mem._t) // Meet into existing memory - : Type.BOTTOM; + Type t = Type.BOTTOM; // No idea on field contents + // Same alias, lift val to the declared type and then meet into other fields + if( mem._alias == _alias ) { + // Update declared forward ref to the actual + if( _declaredType.isFRef() && val instanceof TypeMemPtr tmp && !tmp.isFRef() ) + _declaredType = tmp; + val = val.join(_declaredType); + t = val.meet(mem._t); + } return TypeMem.make(_alias,t); } @@ -108,6 +114,9 @@ public class StoreNode extends MemOpNode { String err() { String err = super.err(); if( err != null ) return err; + TypeMemPtr tmp = (TypeMemPtr)ptr()._type; + if( 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 009fb30e..5d6c2643 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -29,6 +29,11 @@ public class SubNode extends Node { t2 instanceof TypeInteger i2 ) { if (i1.isConstant() && i2.isConstant()) return TypeInteger.constant(i1.value()-i2.value()); + // Fold ranges like {2-3} - {0-1} into {1-3}. + if( !AddNode.overflow(i1._min,-i2._max) && + !AddNode.overflow(i1._max,-i2._min) && + i2._min != Long.MIN_VALUE ) + return TypeInteger.make(i1._min-i2._max,i1._max-i2._min); } // Sub of same is 0 if( in(1)==in(2) ) diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java index e2c0aa59..349c1fb0 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 _final ? 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..4ebb2b6d 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,28 @@ 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(); } + + // 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 32491a11..33c6a8ce 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 ec059b8f..786a7be5 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -33,7 +33,10 @@ public class TypeMemPtr extends Type { } 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); } + public TypeMemPtr makeFrom(boolean nil) { return nil==_nil ? this : make(_obj, nil); } + @Override public TypeMemPtr makeRO() { return makeFrom(_obj.makeRO()); } + @Override public boolean isFinal() { return _obj.isFinal(); } // An abstract pointer, pointing to either a Struct or an Array. // Can also be null or not. @@ -55,9 +58,12 @@ public class TypeMemPtr extends Type { @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; } + @Override public TypeMemPtr glb() { return make(_obj.glb(),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; } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 4e4d1305..b3dbcad0 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) { @@ -161,10 +199,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("}"); } diff --git a/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/src/test/java/com/seaofnodes/simple/BrainFuckTest.java index d5ffe835..88d79215 100644 --- a/src/test/java/com/seaofnodes/simple/BrainFuckTest.java +++ b/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -15,7 +15,7 @@ public class BrainFuckTest { @Test public void testBrainfuck() { var program = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.".getBytes(StandardCharsets.UTF_8); - var encoded = new StringBuilder("u8[] program = new u8[").append(program.length).append("];"); + var encoded = new StringBuilder("u8[] !program = new u8[").append(program.length).append("];"); for (int i = 0; i < program.length; i++) { int value = program[i] & 0xFF; encoded.append("program[").append(i).append("] = ").append(value).append(";"); @@ -23,54 +23,46 @@ public class BrainFuckTest { Parser parser = new Parser( encoded + """ -int pc = 0; -int d = 0; -u8[] data = new u8[100]; -u8[] output = new u8[0]; +var d = 0; +u8[] !output = new u8[0]; +u8[] !data = new u8[100]; -while (pc < program#) { - int command = program[pc]; +for( int pc = 0; pc < program#; pc++ ) { + var command = program[pc]; if (command == 62) { - d = d + 1; + d++; } else if (command == 60) { - d = d - 1; + d--; } else if (command == 43) { - data[d] = data[d] + 1; + data[d]++; } else if (command == 45) { - data[d] = data[d] - 1; + data[d]--; } else if (command == 46) { - u8[] old = output; + // Output a byte; increase the output array size + var old = output; output = new u8[output# + 1]; - int i = 0; - while (i < old#) { + for( var i = 0; i < old#; i++ ) output[i] = old[i]; - i = i + 1; - } - output[i] = data[d]; + output[old#] = data[d]; // Add the extra byte on the end } else if (command == 44) { data[d] = 42; } else if (command == 91) { if (data[d] == 0) { - int d = 1; - while (d > 0) { - pc = pc + 1; - command = program[pc]; - if (command == 91) d = d + 1; - if (command == 93) d = d - 1; + for( var d = 1; d > 0; ) { + command = program[++pc]; + if (command == 91) d++; + if (command == 93) d--; } } } else if (command == 93) { - if (data[d] != 0) { - int d = 1; - while (d > 0) { - pc = pc - 1; - command = program[pc]; - if (command == 93) d = d + 1; - if (command == 91) d = d - 1; + if (data[d]) { + for( var d = 1; d > 0; ) { + command = program[--pc]; + if (command == 93) d++; + if (command == 91) d--; } } } - pc = pc + 1; } return output; """); diff --git a/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/src/test/java/com/seaofnodes/simple/Chapter01Test.java index c10dc510..f7524c17 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -58,7 +58,7 @@ public class Chapter01Test { @Test public void testNotBad3() { // this test used to fail in chapter 1 - assertEquals("return 12;", new Parser("return --12;").parse().print()); + assertEquals("return 12;", new Parser("return - -12;").parse().print()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 64ff153e..2de0b46e 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -31,7 +31,7 @@ public class Chapter03Test { @Test public void testVarScopeNoPeephole() { - Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c; "); + Parser parser = new Parser("int a=1; int b=2; int !c=0; { int b=3; c=a+b; } return c; "); Node._disablePeephole = true; StopNode ret = parser.parse(); Node._disablePeephole = false; @@ -68,7 +68,7 @@ public class Chapter03Test { @Test public void testBad1() { try { - new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); + new Parser("int a=1; int b=2; int !c=0; { int b=3; c=a+b;").parse(); fail(); } catch( RuntimeException e ) { assertEquals("Syntax error, expected }: ",e.getMessage()); diff --git a/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/src/test/java/com/seaofnodes/simple/Chapter04Test.java index 80cdb3f2..0db3afde 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -96,14 +96,14 @@ public class Chapter04Test { @Test public void testBug1() { - Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; "); + Parser parser = new Parser("int a=arg+1; int !b=a; b=1; return a+2; "); StopNode ret = parser.parse(); assertEquals("return (arg+3);", ret.print()); } @Test public void testBug2() { - Parser parser = new Parser("int a=arg+1; a=a; return a; "); + Parser parser = new Parser("int !a=arg+1; a=a; return a; "); StopNode ret = parser.parse(); assertEquals("return (arg+1);", ret.print()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java index b5920125..9afb8f28 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -17,12 +17,11 @@ if (arg == 1) a = arg+2; else { a = arg-3; - } - -return a;"""); +return a; +"""); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region23,(arg+2),(arg-3));", ret.toString()); + assertEquals("return Phi(Region,(arg+2),(arg-3));", ret.toString()); } @Test @@ -37,7 +36,7 @@ if (arg == 1) { } return c;""", TypeInteger.BOT); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region22,4,3);", ret.toString()); + assertEquals("return Phi(Region,4,3);", ret.toString()); } @Test @@ -65,7 +64,7 @@ else b=a+1; return a+b;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return ((arg*2)+Phi(Region26,2,3));", ret.toString()); + assertEquals("return ((arg*2)+Phi(Region,2,3));", ret.toString()); } @Test @@ -80,7 +79,7 @@ else a=b+1; return a+b;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return ((Phi(Region37,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); + assertEquals("return ((Phi(Region,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); } @Test @@ -100,7 +99,7 @@ else return a; """, TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region43,Phi(Region28,2,3),Phi(Region41,4,5));", stop.toString()); + assertEquals("return Phi(Region,Phi(Region,2,3),Phi(Region,4,5));", stop.toString()); } @Test @@ -116,7 +115,7 @@ if( arg==0 ) return arg+a+b; """, TypeInteger.BOT); StopNode stop = parser.parse(); - assertEquals("return ((arg+Phi(Region20,1,0))+Phi(Region37,2,0));", stop.toString()); + assertEquals("return ((arg+Phi(Region,1,0))+Phi(Region,2,0));", stop.toString()); } @Test @@ -130,7 +129,7 @@ if( arg==1 ) } return a;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return (arg==Phi(Region22,3,2));", ret.toString()); + assertEquals("return (arg==Phi(Region,3,2));", ret.toString()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java index ff1f3251..50c0580d 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -65,7 +65,7 @@ else b=5; return b;""", TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region43,42,5);", stop.toString()); + assertEquals("return Phi(Region,42,5);", stop.toString()); } @Test @@ -84,7 +84,7 @@ else b=5; return b;""", TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region38,2,5);", stop.toString()); + assertEquals("return Phi(Region,2,5);", stop.toString()); } @Test @@ -144,7 +144,7 @@ else return a; """, TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region48,3,Phi(Region46,4,5));", stop.toString()); + assertEquals("return Phi(Region,3,Phi(Region,4,5));", stop.toString()); } @Test @@ -200,7 +200,7 @@ if( arg ) { return a+b; """); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region35,4,1);", ret.toString()); + assertEquals("return Phi(Region,4,1);", ret.toString()); } @@ -251,7 +251,7 @@ if( arg ) { return a+b+c; """); StopNode ret = parser.parse().iterate(); - assertEquals("return (Phi(Region48,Phi(Region29,2,3),0)+Phi(Region,3,1));", ret.toString()); + assertEquals("return (Phi(Region,Phi(Region,2,3),0)+Phi(Region,3,1));", ret.toString()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/src/test/java/com/seaofnodes/simple/Chapter07Test.java index b54c24a3..355bbba4 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -10,15 +10,15 @@ public class Chapter07Test { @Test public void testExample() { Parser parser = new Parser( - """ - while(arg < 10) { - arg = arg + 1; - } - return arg; - """); +""" +while(arg < 10) { + arg = arg + 1; +} +return arg; +"""); Node._disablePeephole = true; StopNode stop = parser.parse(); - assertEquals("return Phi(Loop10,arg,(Phi_arg+1));", stop.toString()); + assertEquals("return Phi(Loop,arg,(Phi_arg+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -36,7 +36,7 @@ if(arg){}else{ return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region31,1,Phi(Loop18,1,(Phi_a+1)));", stop.toString()); + assertEquals("return Phi(Region,1,Phi(Loop,1,(Phi_a+1)));", stop.toString()); } @Test @@ -56,7 +56,7 @@ while(i < arg) { return sum; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,0,Phi(Loop26,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); + assertEquals("return Phi(Loop,0,Phi(Loop,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); } @Test @@ -73,7 +73,7 @@ return b; """); Node._disablePeephole = true; StopNode stop = parser.parse(); - assertEquals("return Phi(Loop12,2,Phi(Region34,Phi_b,4));", stop.toString()); + assertEquals("return Phi(Loop,2,Phi(Region,Phi_b,4));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -93,7 +93,7 @@ while(a < 10) { return b; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,2,(Phi(Region34,Phi_b,4)+1));", stop.toString()); + assertEquals("return Phi(Loop,2,(Phi(Region,Phi_b,4)+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -111,7 +111,7 @@ return a; """); Node._disablePeephole = true; StopNode stop = parser.parse(); - assertEquals("return Phi(Loop11,1,((Phi_a+1)+2));", stop.toString()); + assertEquals("return Phi(Loop,1,((Phi_a+1)+2));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -128,7 +128,7 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString()); + assertEquals("return Phi(Loop,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -142,7 +142,7 @@ return a; """); Node._disablePeephole = true; StopNode stop = parser.parse(); - assertEquals("return Phi(Loop11,1,2);", stop.toString()); + assertEquals("return Phi(Loop,1,2);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -156,7 +156,7 @@ while(arg) a = 2; return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,1,2);", stop.toString()); + assertEquals("return Phi(Loop,1,2);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -173,7 +173,7 @@ return a; """); Node._disablePeephole = true; StopNode stop = parser.parse(); - assertEquals("return Phi(Loop11,1,((Phi_a+1)+2));", stop.toString()); + assertEquals("return Phi(Loop,1,((Phi_a+1)+2));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -190,7 +190,7 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString()); + assertEquals("return Phi(Loop,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -208,7 +208,7 @@ return a; """); Node._disablePeephole = true; StopNode stop = parser.parse(); - assertEquals("return Phi(Loop12,1,((Phi_a+1)+2));", stop.toString()); + assertEquals("return Phi(Loop,1,((Phi_a+1)+2));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); Node._disablePeephole = false; } @@ -226,7 +226,7 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,1,(Phi_a+3));", stop.toString()); + assertEquals("return Phi(Loop,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/src/test/java/com/seaofnodes/simple/Chapter08Test.java index c199b78c..bb3bd674 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -23,7 +23,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region45,Phi(Region32,Phi(Loop10,arg,(Phi_arg+1)),Add),Add);", stop.toString()); + assertEquals("return Phi(Region,Phi(Region,Phi(Loop,arg,(Phi_arg+1)),Add),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); Assert.assertEquals(5L, Evaluator.evaluate(stop, 1)); Assert.assertEquals(10L, Evaluator.evaluate(stop, 6)); @@ -46,7 +46,7 @@ while(arg < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,1,Phi(Region52,Phi_a,(Phi_a+1)));", stop.toString()); + assertEquals("return Phi(Loop,1,Phi(Region,Phi_a,(Phi_a+1)));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -65,7 +65,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region43,Phi(Loop10,arg,(Phi_arg+1)),Add);", stop.toString()); + assertEquals("return Phi(Region,Phi(Loop,arg,(Phi_arg+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -81,7 +81,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region32,Phi(Loop10,arg,(Phi_arg+1)),Add);", stop.toString()); + assertEquals("return Phi(Region,Phi(Loop,arg,(Phi_arg+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -100,7 +100,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,arg,(Phi_arg+1));", stop.toString()); + assertEquals("return Phi(Loop,arg,(Phi_arg+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -117,7 +117,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,arg,(Phi_arg+1));", stop.toString()); + assertEquals("return Phi(Loop,arg,(Phi_arg+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -138,7 +138,7 @@ return arg; @Test public void testRegress2() { - Parser parser = new Parser("if(1) return 0; else while(arg>--arg) arg=arg+1; return 0;"); + Parser parser = new Parser("if(1) return 0; else while(arg>- -arg) arg=arg+1; return 0;"); StopNode stop = parser.parse().iterate(); assertEquals("return 0;", stop.toString()); } @@ -185,7 +185,7 @@ while(arg < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region35,Phi(Loop11,1,(Phi_a+1)),Add);", stop.toString()); + assertEquals("return Phi(Region,Phi(Loop,1,(Phi_a+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -201,7 +201,7 @@ while(1) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return (Phi(Loop11,1,Add)+1);", stop.toString()); + assertEquals("return (Phi(Loop,1,Add)+1);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode prj && prj._idx==1 ); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/src/test/java/com/seaofnodes/simple/Chapter09Test.java index b1d9d6e5..c31afcd6 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -69,7 +69,7 @@ while (arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,arg,(Phi_arg+2));", stop.toString()); + assertEquals("return Phi(Loop,arg,(Phi_arg+2));", stop.toString()); Assert.assertEquals(11L, Evaluator.evaluate(stop, 1)); } @@ -86,7 +86,7 @@ while (arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,arg,(Phi_arg+4));", stop.toString()); + assertEquals("return Phi(Loop,arg,(Phi_arg+4));", stop.toString()); Assert.assertEquals(13L, Evaluator.evaluate(stop, 1)); } @@ -115,7 +115,7 @@ while (arg) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop18,arg,(Phi_arg+1));", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test @@ -185,7 +185,7 @@ while(arg) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop13,0,(-(Phi_a+3)));", stop.toString()); + assertEquals("return Phi(Loop,0,(-(Phi_a+3)));", stop.toString()); } @Test @@ -283,7 +283,7 @@ return v1+v0; public void testFuzz8() { Parser parser = new Parser("while(arg) arg = arg - 1; return arg;"); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,arg,(Phi_arg-1));", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 2a33031d..d41c83d8 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -44,7 +44,7 @@ struct Foo { int x; }; Foo? foo = null; -Bar bar = new Bar; +Bar !bar = new Bar; bar.a = 1; bar.a = 2; return bar.a; @@ -57,7 +57,7 @@ return bar.a; public void testExample() { Parser parser = new Parser(""" struct Vector2D { int x; int y; }; -Vector2D v = new Vector2D; +Vector2D !v = new Vector2D; v.x = 1; if (arg) v.y = 2; @@ -96,7 +96,7 @@ arg=0+new s0.0; public void testLoop() { Parser parser = new Parser(""" struct Bar { int a; }; -Bar bar = new Bar; +Bar !bar = new Bar; while (arg) { bar.a = bar.a + 2; arg = arg + 1; @@ -104,14 +104,14 @@ while (arg) { return bar.a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop16,0,(Phi_a+2));", stop.toString()); + assertEquals("return Phi(Loop,0,(Phi_a+2));", stop.toString()); } @Test public void testIf() { Parser parser = new Parser(""" struct Bar { int a; }; -Bar bar = new Bar; +Bar !bar = new Bar; if (arg) bar = null; bar.a = 1; return bar.a; @@ -124,7 +124,7 @@ return bar.a; public void testIf2() { Parser parser = new Parser(""" struct Bar { int a; }; -Bar? bar = null; +Bar? !bar = null; if (arg) bar = new Bar; bar.a = 1; return bar.a; @@ -150,13 +150,13 @@ return bar.a; public void testIfOrNull() { Parser parser = new Parser(""" struct Bar { int a; }; -Bar? bar = new Bar; +Bar? !bar = new Bar; if (arg) bar = null; if( bar ) bar.a = 1; return bar; """); StopNode stop = parser.parse(false).iterate(); - assertEquals("return Phi(Region38,(*void)Phi(Region24,null,Bar),null);", stop.toString()); + assertEquals("return Phi(Region,(*void)Phi(Region,null,Bar),null);", stop.toString()); } @Test @@ -164,7 +164,7 @@ return bar; Parser parser = new Parser( """ struct Bar { int a; }; -Bar? bar = new Bar; +Bar? !bar = new Bar; if (arg) bar = null; int rez = 3; if( !bar ) rez=4; @@ -172,14 +172,14 @@ else bar.a = 1; return rez; """); StopNode stop = parser.parse(false).iterate(); - assertEquals("return Phi(Region44,4,3);", stop.toString()); + assertEquals("return Phi(Region,4,3);", stop.toString()); } @Test public void testWhileWithNullInside() { Parser parser = new Parser(""" struct s0 {int v0;}; -s0? v0 = new s0; +s0? !v0 = new s0; int ret = 0; while(arg) { ret = v0.v0; @@ -216,7 +216,7 @@ struct Iter { int x; int len; }; -Iter i = new Iter; +Iter !i = new Iter; i.len = arg; int sum=0; while( i.x < i.len ) { @@ -226,7 +226,7 @@ while( i.x < i.len ) { return sum; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop21,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); + assertEquals("return Phi(Loop,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); } @@ -234,9 +234,9 @@ return sum; public void test1() { Parser parser = new Parser(""" struct s0 {int v0;}; -s0 ret = new s0; +s0 !ret = new s0; while(arg) { - s0 v0 = new s0; + s0 !v0 = new s0; v0.v0 = arg; arg = arg-1; if (arg==5) ret=v0; @@ -245,15 +245,15 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop16,s0,Phi(Region43,s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", stop.toString()); } @Test public void test2() { Parser parser = new Parser(""" struct s0 {int v0;}; -s0 ret = new s0; -s0 v0 = new s0; +s0 !ret = new s0; +s0 !v0 = new s0; while(arg) { v0.v0 = arg; arg = arg-1; @@ -263,7 +263,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop20,s0,Phi(Region44,s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", stop.toString()); } @@ -271,16 +271,16 @@ return ret; public void test3() { Parser parser = new Parser(""" struct s0 {int v0;}; -s0 ret = new s0; +s0 !ret = new s0; while(arg < 10) { - s0 v0 = new s0; + s0 !v0 = new s0; if (arg == 5) ret=v0; arg = arg + 1; } return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop16,s0,Phi(Region41,s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop,s0,Phi(Region,s0,Phi_ret));", stop.toString()); } @Test @@ -350,7 +350,7 @@ s0 v1 = v0; return v1; """); StopNode stop = parser.parse().iterate(); - assertEquals("return s0;", stop.toString()); + assertEquals("return (const)s0;", stop.toString()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/src/test/java/com/seaofnodes/simple/Chapter11Test.java index d6b7bb00..613b979b 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -14,7 +14,7 @@ public class Chapter11Test { public void testFuzzer() { Parser parser = new Parser( """ -while(-----arg) { +while(---- -arg) { while(-arg) { while(-----arg*---0) { int N=--false==false<--arg; @@ -103,7 +103,7 @@ while(-----arg) { int UX=arg; while(UX<-3*arg) { UX=UX+arg/-1; - arg=-3--(-UX--47<arg==--arg==arg)/arg--UX>=-arg; + arg=-3--(-UX- -47<arg==--arg==arg)/arg- -UX>=-arg; if(---12) while(-UX) break; break; } @@ -224,9 +224,9 @@ if(arg!=62==arg) { } } arg=-arg+arg; - arg=--47+-arg<1>arg*(-arg==-arg--0>3); + arg=--47+-arg<1>arg*(-arg==-arg- -0>3); arg=(----arg)!=arg+--59; - arg=--4+arg==-(arg)-arg; + arg=- -4+arg==-(arg)-arg; } else { while(--true-----true*-25+-18>arg>=-----(-arg)---13) { @@ -292,7 +292,7 @@ else { } """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 9; return 0; return 0; ]", stop.toString()); + assertEquals("Stop[ return 9; return 0; return 0; return 0; return 0; ]", stop.toString()); } @@ -324,7 +324,7 @@ while( prime <= arg ) { return primeCount; """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 0; return Phi(Loop23,1,Phi(Region100,Phi_primeCount,Phi(Region93,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString()); + assertEquals("Stop[ return 0; return Phi(Loop,1,Phi(Region,Phi_primeCount,Phi(Region,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString()); assertEquals(0L, Evaluator.evaluate(stop, 1)); // No primes 1 or below assertEquals(1L, Evaluator.evaluate(stop, 2)); // 2 assertEquals(2L, Evaluator.evaluate(stop, 3)); // 2, 3 @@ -338,7 +338,7 @@ return primeCount; Parser parser = new Parser( """ struct S { int f; }; -S v=new S; +S !v=new S; v.f = 2; int i=new S.f; i=v.f; @@ -356,9 +356,9 @@ return i; Parser parser = new Parser( """ struct S { int f; }; -S v = new S; +S !v = new S; v.f = arg; -S t = new S; +S !t = new S; int i = 0; if (arg) { if (arg+1) v = t; @@ -369,7 +369,7 @@ if (arg) { return i; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region45,.f,0);", stop.toString()); + assertEquals("return Phi(Region,.f,0);", stop.toString()); } @Test @@ -377,7 +377,7 @@ return i; Parser parser = new Parser( """ struct S { int f; }; -S v0 = new S; +S !v0 = new S; S? v1; if (arg) v1 = new S; if (v1) { @@ -397,7 +397,7 @@ return v0; Parser parser = new Parser( """ struct S { int f; }; -S v = new S; +S !v = new S; v.f = arg; S t = new S; int i = v.f; @@ -414,7 +414,7 @@ return i; Parser parser = new Parser( """ struct S { int f; }; -S v = new S; +S !v = new S; while(1) { while(arg+1) { arg=arg-1; } if (arg) break; @@ -431,14 +431,14 @@ return v; Parser parser = new Parser( """ struct s { int v; }; -s ptr=new s; +s !ptr=new s; while( -arg ) ptr = new s; while(1) arg = arg+ptr.v; """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 0; return 0; ]", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test @@ -446,7 +446,7 @@ while(1) Parser parser = new Parser( """ struct S { int f; }; -S v = new S; +S !v = new S; S t = new S; int i = v.f; while (arg) { @@ -464,7 +464,7 @@ return i; Parser parser = new Parser( """ struct S { int f; }; -S v = new S; +S !v = new S; S t = new S; while(arg) { arg=arg-1; @@ -476,7 +476,7 @@ while(arg) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop20,arg,Phi(Region48,.f,0));", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test @@ -484,7 +484,7 @@ return arg; Parser parser = new Parser( """ struct S { int f; }; -S v = new S; +S !v = new S; S t = new S; if (arg) { v.f=2; @@ -502,7 +502,7 @@ return v; Parser parser = new Parser( """ struct S { int f; }; -S v = new S; +S !v = new S; int i = arg; while (arg > 0) { int j = i/3; diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java index c0f6266a..a70a5f33 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -43,7 +43,7 @@ while( 1 ) { return guess; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0));", stop.toString()); + assertEquals("return Phi(Loop,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0));", stop.toString()); assertEquals(3.0, Evaluator.evaluate(stop, 9)); assertEquals(1.414213562373095, Evaluator.evaluate(stop, 2)); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 165d23e5..30d9b147 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -23,9 +23,9 @@ return 3.14; Parser parser = new Parser( """ struct LLI { LLI? next; int i; }; -LLI? head = null; +LLI? !head = null; while( arg ) { - LLI x = new LLI; + LLI !x = new LLI; x.next = head; x.i = arg; head = x; @@ -42,9 +42,9 @@ return head.next.i; Parser parser = new Parser( """ struct LLI { LLI? next; int i; }; -LLI? head = null; +LLI? !head = null; while( arg ) { - LLI x = new LLI; + LLI !x = new LLI; x.next = head; x.i = arg; head = x; @@ -66,9 +66,9 @@ return next.i; """ struct int0 { int i; flt0? f; }; struct flt0 { flt f; int0? i; }; -int0 i0 = new int0; +int0 !i0 = new int0; i0.i = 17; -flt0 f0 = new flt0; +flt0 !f0 = new flt0; f0.f = 3.14; i0.f = f0; f0.i = i0; @@ -100,7 +100,7 @@ N n = new N { next = new M; }; return n.next; """); StopNode stop = parser.parse().iterate(); - assertEquals("return M;", stop.toString()); + assertEquals("return (const)M;", stop.toString()); } @Test @@ -121,12 +121,12 @@ return n.next; Parser parser = new Parser( """ struct N { N? next; int i; }; -N n = new N; +N !n = new N; n.i = 3.14; return n.i; """); try { parser.parse().iterate(); fail(); } - catch( Exception e ) { assertEquals("Cannot store 3.14 into field int i",e.getMessage()); } + catch( Exception e ) { assertEquals("Type 3.14 is not of declared type int",e.getMessage()); } } @Test @@ -144,7 +144,7 @@ struct S{}; public void testForwardRef0() { Parser parser = new Parser( """ -struct S1 { S2 s; }; +struct S1 { S2? s; }; return new S2; """); try { parser.parse().iterate(); fail(); } @@ -169,7 +169,7 @@ return new S1.s=new S2; """ struct I {int i;}; struct P { I? pi; }; -P p1 = new P; +P !p1 = new P; P p2 = new P; p2.pi = new I; p2.pi.i = 2; diff --git a/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/src/test/java/com/seaofnodes/simple/Chapter14Test.java index 7d7bb25a..23c82358 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -59,7 +59,7 @@ while( b ) b = b + 456;// Truncate return b; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,123,((Phi_b+456)&255));", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test @@ -94,7 +94,7 @@ return b; Parser parser = new Parser( """ struct Foo { u1 b; }; -Foo f = new Foo; +Foo !f = new Foo; f.b = 123; return f.b; """); @@ -175,7 +175,7 @@ while(v1) break; return v1; """); StopNode stop = parser.parse().iterate(); - assertEquals("return (Phi(Loop18,((1<<arg)&1),0)&Phi(Loop,Shl,4294967295));", stop.toString()); + assertEquals("return (Phi(Loop,((1<<arg)&1),0)&Phi(Loop,Shl,4294967295));", stop.toString()); assertEquals(1L, Evaluator.evaluate(stop, 0)); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 8161862f..4e2682dc 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -25,7 +25,7 @@ return 3.14; Parser parser = new Parser( """ struct C { C? l; }; -C c = new C; +C !c = new C; c.l = c; return c; """); @@ -39,7 +39,7 @@ return c; Parser parser = new Parser( """ u8[] old = new u8[0]; -u8[] output = new u8[1]; +u8[] !output = new u8[1]; int i = 0; while (i < old#) { output[i] = old[i]; @@ -82,7 +82,7 @@ return is[1]; public void testBasic3() { Parser parser = new Parser( """ -int[] a = new int[2]; +int[] !a = new int[2]; a[0] = 1; a[1] = 2; return a[0]; @@ -97,7 +97,7 @@ return a[0]; Parser parser = new Parser( """ struct A { int i; }; -A?[] a = new A?[2]; +A?[] !a = new A?[2]; return a; """); StopNode stop = parser.parse().iterate(); @@ -111,10 +111,10 @@ return a; """ struct S { int x; flt y; }; // A new S -S s = new S; s.x=99; s.y = 3.14; +S !s = new S; s.x=99; s.y = 3.14; // Double-d array of Ss. Fill in one row. -S?[]?[] iss = new S?[]?[2]; +S?[]?[] !iss = new S?[]?[2]; iss[0] = new S?[7]; iss[0][2] = s; @@ -130,19 +130,18 @@ else { return rez; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region117,1.2,Phi(Region114,2.3,3.14));", stop.toString()); + assertEquals("return Phi(Region,1.2,Phi(Region,2.3,3.14));", stop.toString()); assertEquals(3.14, Evaluator.evaluate(stop, 0)); assertEquals(1.2 , Evaluator.evaluate(stop, 1)); } - @Ignore @Test public void testBasic6() { Parser parser = new Parser( """ struct S { int x; flt y; }; // A new S -S s = new S; s.x=99; s.y = 3.14; +S !s = new S; s.x=99; s.y = 3.14; // Double-d array of Ss. Fill in one row. S?[]?[] iss = new S?[]?[2]; @@ -156,9 +155,8 @@ if( iss[arg] ) rez = iss[arg][2].y; return rez; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region122,Phi(Region118,.y,1.2),1.2);", stop.toString()); - assertEquals(3.14, Evaluator.evaluate(stop, 0)); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Might be null accessing 'y'",e.getMessage()); } } @Test @@ -167,8 +165,8 @@ return rez; """ // Can we define a forward-reference array? struct Tree { Tree?[]? _kids; }; -Tree root = new Tree; -root._kids = new Tree?[2]; +Tree !root = new Tree; +root._kids = new Tree?[2]; // NO BANG SO ARRAY IS OF IMMUTABLE TREES???? root._kids[0] = new Tree; return root; """); @@ -192,7 +190,7 @@ return 0; public void testRollingSum() { Parser parser = new Parser( """ -int[] ary = new int[arg]; +int[] !ary = new int[arg]; // Fill [0,1,2,3,4,...] int i=0; while( i < ary# ) { @@ -216,44 +214,42 @@ return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 public void sieveOEratosthenes() { Parser parser = new Parser( """ -int[] ary = new int[arg]; -int[] primes = new int[arg]; -int nprimes = 0; -// Find primes -int j=2; -while( j*j < arg ) { - while( ary[j]==1 ) j = j + 1; - // j is now a prime - primes[nprimes] = j; nprimes = nprimes + 1; +int[] !ary = new int[arg], !primes = new int[arg]; +int nprimes = 0, p=2; +// Find primes while p^2 < arg +while( p*p < arg ) { + // skip marked non-primes + while( ary[p]==1 ) p = p + 1; + // p is now a prime + primes[nprimes] = p; nprimes = nprimes + 1; // Mark out the rest non-primes - int i = j + j; + int i = p + p; while( i < ary# ) { ary[i] = 1; - i = i + j; + i = i + p; } - j = j + 1; + p = p + 1; } -// Now just collect the remaining primes -while( j < arg ) { - if( ary[j] == 0 ) { - primes[nprimes] = j; nprimes = nprimes + 1; +// Now just collect the remaining primes, no more marking +while( p < arg ) { + if( ary[p] == 0 ) { + primes[nprimes] = p; nprimes = nprimes + 1; } - j = j + 1; + p = p + 1; } -// Shrink the result array to size -int[] rez = new int[nprimes]; -j = 0; +// Copy/shrink the result array +int[] !rez = new int[nprimes]; +int j = 0; while( j < nprimes ) { rez[j] = primes[j]; j = j + 1; } - return rez; """); StopNode stop = parser.parse().iterate(); assertEquals("return [int];", stop.toString()); Evaluator.Obj obj = (Evaluator.Obj)Evaluator.evaluate(stop, 20); - assertEquals("[int] { # :int; [] :int; }",obj.struct().toString()); + assertEquals("[int] {int #; int ![]; }",obj.struct().toString()); long nprimes = (Long)obj.fields()[0]; long[] primes = new long[]{2,3,5,7,11,13,17,19}; for( int i=0; i<nprimes; i++ ) @@ -265,8 +261,8 @@ return rez; Parser parser = new Parser( """ struct S {int i; flt f;}; -S s1 = new S; -S s2 = new S; +S !s1 = new S; +S !s2 = new S; s2.i = 3; s2.f = 2.0; if (arg) s1 = new S; diff --git a/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/src/test/java/com/seaofnodes/simple/Chapter16Test.java index ad287e82..5450824a 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -43,28 +43,28 @@ return x+y; assertEquals(5L, Evaluator.evaluate(stop, 0)); } - @Test - public void testFinal0() { - Parser parser = new Parser( -""" -int !x=2; -x=3; -return x; -"""); - try { parser.parse().iterate(); fail(); } - catch( Exception e ) { assertEquals("Cannot reassign final 'x'",e.getMessage()); } - } +// @Test +// public void testFinal0() { +// Parser parser = new Parser( +//""" +//int !x=2; +//x=3; +//return x; +//"""); +// try { parser.parse().iterate(); fail(); } +// catch( Exception e ) { assertEquals("Cannot reassign final 'x'",e.getMessage()); } +// } @Test public void testFinal1() { Parser parser = new Parser( """ -int !x=2, y=3; +int x=2, y=3; if( arg ) { int x = y; x = x*x; y=x; } // Shadow final x return y; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region21,9,3);", stop.toString()); + assertEquals("return Phi(Region,9,3);", stop.toString()); assertEquals(3L, Evaluator.evaluate(stop, 0)); assertEquals(9L, Evaluator.evaluate(stop, 1)); } @@ -107,17 +107,78 @@ return z.x; @Test - public void testStructFinal() { + public void testStructFinal0() { Parser parser = new Parser(""" struct Point { int !x, !y; }; Point p = new Point { x=3; y=4; }; return p; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Point;", stop.toString()); + assertEquals("return (const)Point;", stop.toString()); assertEquals("Obj<Point>{x=3,y=4}", Evaluator.evaluate(stop, 0).toString()); } + @Test + public void testStructFinal1() { + Parser parser = new Parser(""" +struct Point { int x=3, y=4; }; +Point p = new Point { x=5; y=6; }; +p.x++; +return p; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } + } + + @Test + public void testStructFinal2() { + Parser parser = new Parser(""" +struct Point { int x=3, y=4; }; +Point p = new Point; +p.x++; +return p; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } + } + + @Test + public void testStructFinal3() { + Parser parser = new Parser(""" +struct Point { var x; var y; }; +Point p = new Point; +p.x++; +return p; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("'Point' is not fully initialized, field 'x' needs to be set in a constructor",e.getMessage()); } + } + + @Test + public void testStructFinal4() { + Parser parser = new Parser(""" +struct Point { val x=3; val y=4; }; +Point p = new Point; +p.x++; +return p; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot reassign final 'x'",e.getMessage()); } + } + + @Test + public void testStructFinal5() { + Parser parser = new Parser(""" +struct Point { var x=3; var y=4; }; +Point !p = new Point; +p.x++; +return p; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Point;", stop.toString()); + assertEquals("Obj<Point>{x=4,y=4}", Evaluator.evaluate(stop, 0).toString()); + } + // Same as the Chapter13 test with the same name, but using the new // constructor syntax @Test @@ -125,7 +186,7 @@ return p; Parser parser = new Parser( """ struct LLI { LLI? next; int i; }; -LLI? head = null; +LLI? !head = null; while( arg ) { head = new LLI { next=head; i=arg; }; arg = arg-1; @@ -147,12 +208,12 @@ return next.i; Parser parser = new Parser( """ struct LLI { LLI? next; int i; }; -LLI? head = null; +LLI? !head = null; while( arg ) { head = new LLI { next=head; // Any old code in the constructor - int tmp=arg; + int !tmp=arg; while( arg > 10 ) { tmp = tmp + arg; arg = arg - 1; @@ -182,7 +243,7 @@ struct Square { // Newtons approximation to the square root, computed in a constructor. // The actual allocation will copy in this result as the initial // value for 'diag'. - flt diag = arg*arg/2; + flt !diag = arg*arg/2; while( 1 ) { flt next = (side/diag + diag)/2; if( next == diag ) break; diff --git a/src/test/java/com/seaofnodes/simple/Chapter17Test.java b/src/test/java/com/seaofnodes/simple/Chapter17Test.java new file mode 100644 index 00000000..4a7e959a --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter17Test.java @@ -0,0 +1,505 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; +import org.junit.Ignore; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter17Test { + + @Test + public void testJig() { + Parser parser = new Parser(""" +int i = 0; +i=i=1; +return i; + //return 3.14; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 1;", stop.toString()); + assertEquals(1L, Evaluator.evaluate(stop, 0)); + } + + + // --------------------------------------------------------------- + @Test + public void testInc0() { + Parser parser = new Parser(""" +return arg++; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return arg;", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testInc1() { + Parser parser = new Parser(""" +return arg+++arg++; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return ((arg*2)+1);", stop.toString()); + assertEquals(1L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testInc2() { + Parser parser = new Parser(""" +// -(arg--)-(arg--) +return -arg---arg--; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return (-((arg*2)+-1));", stop.toString()); + assertEquals(1L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testInc3() { + Parser parser = new Parser(""" +int[] !xs = new int[arg]; +xs[0]++; +xs[1]++; +return xs[0]; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 1;", stop.toString()); + assertEquals(1L, Evaluator.evaluate(stop, 2)); + } + + @Test + public void testInc4() { + Parser parser = new Parser(""" +u8[] !xs = new u8[1]; +xs[0]--; +return xs[0]; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 255;", stop.toString()); + assertEquals(255L, Evaluator.evaluate(stop, 2)); + } + + @Test + public void testInc5() { + Parser parser = new Parser(""" +struct S { u16 x; }; +S !s = new S; +s.x--; +return s.x; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 65535;", stop.toString()); + assertEquals(65535L, Evaluator.evaluate(stop, 2)); + } + + @Test + public void testInc6() { + Parser parser = new Parser("return --arg;"); + StopNode stop = parser.parse().iterate(); + assertEquals("return (arg+-1);", stop.toString()); + assertEquals(-1L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testInc7() { + Parser parser = new Parser("u8 x=0; return --x;"); + StopNode stop = parser.parse().iterate(); + assertEquals("return 255;", stop.toString()); + assertEquals(255L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testInc8() { + Parser parser = new Parser("int x; x+=2; return x+=3;"); + StopNode stop = parser.parse().iterate(); + assertEquals("return 5;", stop.toString()); + assertEquals(5L, Evaluator.evaluate(stop, 0)); + } + + // --------------------------------------------------------------- + @Test public void testVar0() { + Parser parser = new Parser("var d; return d;"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Syntax error, expected =expression: ;",e.getMessage()); } + } + + @Test public void testVar1() { + Parser parser = new Parser("val d; return d;"); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Syntax error, expected =expression: ;",e.getMessage()); } + } + + @Test public void testVar2() { + Parser parser = new Parser("int x; x=3; x++; return x; // Ok, no initializer so x is mutable "); + StopNode stop = parser.parse().iterate(); + assertEquals("return 4;", stop.toString()); + assertEquals(4L, Evaluator.evaluate(stop, 0)); + } + + @Test public void testVar3() { + Parser parser = new Parser("int x=3; x++; return x; // Ok, primitive so x is mutable despite initializer "); + StopNode stop = parser.parse().iterate(); + assertEquals("return 4;", stop.toString()); + assertEquals(4L, Evaluator.evaluate(stop, 0)); + } + + @Test public void testVar4() { + Parser parser = new Parser("struct S{int x;}; S s; s=new S; s.x++; return s.x; // Ok, no initializer so x is mutable "); + StopNode stop = parser.parse().iterate(); + assertEquals("return 1;", stop.toString()); + assertEquals(1L, Evaluator.evaluate(stop, 0)); + } + + @Test public void testVar5() { + Parser parser = new Parser("struct S{int x;}; S s; s=new S{x=3;}; s.x++; return s.x; // Ok, no initializer so x is mutable "); + StopNode stop = parser.parse().iterate(); + assertEquals("return 4;", stop.toString()); + assertEquals(4L, Evaluator.evaluate(stop, 0)); + } + + @Test public void testVar6() { + Parser parser = new Parser("struct S{int x;}; S s=new S; s.x++; return s.x; // Error initializer so x is immutable "); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } + } + + @Test public void testVar7() { + Parser parser = new Parser("struct S{int x;}; S s=new S{x=3;}; s.x++; return s.x; // Error initializer so x is immutable "); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } + } + + @Test public void testVar8() { + Parser parser = new Parser("struct S{int x;}; S !s=new S; s.x++; return s.x; // Ok, has '!' so s.x is mutable "); + StopNode stop = parser.parse().iterate(); + assertEquals("return 1;", stop.toString()); + assertEquals(1L, Evaluator.evaluate(stop, 0)); + } + + @Test public void testVar9() { + Parser parser = new Parser("struct S{int x;}; var s=new S; s.x++; return s.x; // Ok, has var so s.x is mutable "); + StopNode stop = parser.parse().iterate(); + assertEquals("return 1;", stop.toString()); + assertEquals(1L, Evaluator.evaluate(stop, 0)); + } + + @Test public void testVar10() { + Parser parser = new Parser("struct S{int x;}; val s=new S; s.x++; return s.x; // Error, has val so x is immutable "); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } + } + + @Test public void testVar11() { + Parser parser = new Parser(""" +struct Bar { int x; }; +Bar !bar = new Bar; +bar.x = 3; // Ok, bar is mutable + +struct Foo { Bar? !bar; int y; }; +Foo !foo = new Foo { bar = bar; }; +foo.bar = bar; // Ok foo is mutable +foo.bar.x++; // Ok foo and foo.bar and foo.bar.x are all mutable + +val xfoo = foo; // Throw away mutability +xfoo.bar.x++; // Error, cannot mutate through xfoo + """); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } + } + + @Test public void testVar12() { + Parser parser = new Parser(""" +struct Bar { int x; }; +Bar !bar = new Bar; +bar.x = 3; // Ok, bar is mutable + +struct Foo { Bar? !bar; int y; }; +Foo !foo = new Foo; +foo.bar = bar; // Ok bar is mutable +foo.bar.x++; // Ok foo and foo.bar and foo.bar.x are all mutable + +val xfoo = foo; // Throw away mutability +int x4 = xfoo.bar.x; // Ok to read through xfoo, gets 4 +foo.bar.x++; // Bumps to 5 +int x5 = xfoo.bar.x; // Ok to read through xfoo, gets 5 +return x4*10+x5; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 45;", stop.toString()); + assertEquals(45L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testVar13() { + Parser parser = new Parser(""" +int i,i++; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Redefining name 'i'",e.getMessage()); } + } + + + @Test + public void testVar14() { + Parser parser = new Parser(""" +struct B {}; +struct A { B b; }; +A x = new A { + return b; // read before init + b = new B; +}; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot read uninitialized field 'b'",e.getMessage()); } + } + + @Test + public void testVar15() { + Parser parser = new Parser(""" +struct B {}; +struct A { B b; }; +return new A { + if (arg) b = new B; // Constructor ends with partial init of b +}.b; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("'A' is not fully initialized, field 'b' needs to be set in a constructor",e.getMessage()); } + } + + // --------------------------------------------------------------- + @Test + public void testTrinary0() { + Parser parser = new Parser(""" +return arg ? 1 : 2; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Region,1,2);", stop.toString()); + assertEquals(2L, Evaluator.evaluate(stop, 0)); + assertEquals(1L, Evaluator.evaluate(stop, 1)); + } + + @Test + public void testTrinary1() { + Parser parser = new Parser(""" +return arg ? 0 : arg; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testTrinary2() { + Parser parser = new Parser(""" +struct Bar { int x; }; +var b = arg ? new Bar : null; +return b ? b.x++ + b.x++ : -1; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Region,1,-1);", stop.toString()); + assertEquals(-1L, Evaluator.evaluate(stop, 0)); + assertEquals( 1L, Evaluator.evaluate(stop, 1)); + } + + @Test + public void testTrinary3() { + Parser parser = new Parser(""" +struct Bar { int x; }; +var b = arg ? new Bar; +return b ? b.x++ + b.x++ : -1; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Region,1,-1);", stop.toString()); + assertEquals(-1L, Evaluator.evaluate(stop, 0)); + assertEquals( 1L, Evaluator.evaluate(stop, 1)); + } + + @Test + public void testTrinary4() { + // This test case will benefit from an unzipping transformation + Parser parser = new Parser(""" +struct Bar { Bar? next; int x; }; +var b = arg ? new Bar { next = (arg==2) ? new Bar{x=2;}; x=1; }; +return b ? b.next ? b.next.x : b.x; // parses "b ? (b.next ? b.next.x : b.x) : 0" +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Region,Phi(Region,.x,.x),0);", stop.toString()); + assertEquals( 0L, Evaluator.evaluate(stop, 0)); + assertEquals( 1L, Evaluator.evaluate(stop, 1)); + assertEquals( 2L, Evaluator.evaluate(stop, 2)); + } + + @Test + public void testTrinary5() { + Parser parser = new Parser(""" +flt f=arg?1:1.2; +return f; // missing widening +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Region,1.0,1.2);", stop.toString()); + assertEquals(1.2, Evaluator.evaluate(stop, 0)); + } + + // --------------------------------------------------------------- + @Test + public void testFor0() { + Parser parser = new Parser(""" +int sum=0; +for( int i=0; i<arg; i++ ) + sum += i; +return sum; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", stop.toString()); + assertEquals(3L, Evaluator.evaluate(stop, 3)); + assertEquals(45L, Evaluator.evaluate(stop, 10)); + } + @Test + public void testFor1() { + Parser parser = new Parser(""" +int sum=0, i=0; +for( ; i<arg; i++ ) + sum += i; +return sum; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", stop.toString()); + assertEquals(3L, Evaluator.evaluate(stop, 3)); + assertEquals(45L, Evaluator.evaluate(stop, 10)); + } + @Test + public void testFor2() { + Parser parser = new Parser(""" +int sum=0; +for( int i=0; ; i++ ) { + if( i>=arg ) break; + sum += i; +} +return sum; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", stop.toString()); + assertEquals(3L, Evaluator.evaluate(stop, 3)); + assertEquals(45L, Evaluator.evaluate(stop, 10)); + } + @Test + public void testFor3() { + Parser parser = new Parser(""" +int sum=0; +for( int i=0; i<arg; ) + sum += i++; +return sum; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", stop.toString()); + assertEquals(3L, Evaluator.evaluate(stop, 3)); + assertEquals(45L, Evaluator.evaluate(stop, 10)); + } + @Test + public void testFor4() { + Parser parser = new Parser(""" +int sum=0; +for( int i=0; i<arg; i++ ) + sum += i; +return i; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Undefined name 'i'",e.getMessage()); } + } + @Test + public void testFor5() { + Parser parser = new Parser(""" +for(;;arg++;) {} +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Syntax error, expected Unexpected code after expression: ;",e.getMessage()); } + } + + + + // --------------------------------------------------------------- + @Test + public void testForward0() { + Parser parser = new Parser(""" +struct A{ + B? f1; + B? f2; +}; +return new A; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return A;", stop.toString()); + assertEquals("Obj<A>{f1=null,f2=null}", Evaluator.evaluate(stop).toString()); + } + + @Test + public void testForward1() { + Parser parser = new Parser(""" +struct A{ + B?[]? nil_array_of_b; + B?[] not_array_of_b = new B?[0]; +}; +return new A.not_array_of_b; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return (const)[*B?];", stop.toString()); + assertEquals("Obj<[*B?]>{#=0,[]=[]}", Evaluator.evaluate(stop).toString()); + } + + // --------------------------------------------------------------- + @Test + public void testLinkedList2() { + Parser parser = new Parser(""" +struct LLI { LLI? next; int i; }; +LLI? !head = null; +while( arg-- ) + head = new LLI { next=head; i=arg; }; +int sum=0; +var ptr = head; // A read-only ptr, to be assigned from read-only next fields +for( ; ptr; ptr = ptr.next ) + sum += ptr.i; +return sum; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop,0,(Phi_sum+.i));", stop.toString()); + assertEquals(45L, Evaluator.evaluate(stop, 10)); + } + + @Test + public void sieveOfEratosthenes() { + Parser parser = new Parser( +""" +var ary = new bool[arg], primes = new int[arg]; +var nprimes=0, p=0; +// Find primes while p^2 < arg +for( p=2; p*p < arg; p++ ) { + // skip marked non-primes + while( ary[p] ) p++; + // p is now a prime + primes[nprimes++] = p; + // Mark out the rest non-primes + for( int i = p + p; i < ary#; i += p ) + ary[i] = true; +} +// Now just collect the remaining primes, no more marking +for( ; p < arg; p++ ) + if( !ary[p] ) + primes[nprimes++] = p; +// Copy/shrink the result array +var !rez = new int[nprimes]; +for( int j=0; j<nprimes; j++ ) + rez[j] = primes[j]; +return rez; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return [int];", stop.toString()); + Evaluator.Obj obj = (Evaluator.Obj)Evaluator.evaluate(stop, 20); + assertEquals("[int] {int #; int ![]; }",obj.struct().toString()); + long nprimes = (Long)obj.fields()[0]; + long[] primes = new long[]{2,3,5,7,11,13,17,19}; + for( int i=0; i<nprimes; i++ ) + assertEquals(primes[i],(long)(Long)obj.fields()[i+1]); + } + +} diff --git a/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/src/test/java/com/seaofnodes/simple/SchedulerTest.java index 168e0ed7..c67217af 100644 --- a/src/test/java/com/seaofnodes/simple/SchedulerTest.java +++ b/src/test/java/com/seaofnodes/simple/SchedulerTest.java @@ -24,7 +24,7 @@ public class SchedulerTest { struct S { int f; } -S v=new S; +S !v=new S; v.f = 2; int i=v.f; if (arg) v.f=1; @@ -42,7 +42,7 @@ return i; struct S { int f; }; -S v0=new S; +S !v0=new S; if(arg) v0.f=1; return v0; """); @@ -58,7 +58,7 @@ return v0; struct S { int f; }; -S v=new S; +S !v=new S; v.f = 2; int i=new S.f; i=v.f; diff --git a/src/test/java/com/seaofnodes/simple/TypeTest.java b/src/test/java/com/seaofnodes/simple/TypeTest.java index 6f7409cd..1cb97cf6 100644 --- a/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -20,7 +20,7 @@ public class TypeTest { Field.make("b", TypeInteger.BOT,-4, false) }); Assert.assertEquals(s1, s1.glb()); Assert.assertNotEquals(s1, s1.dual()); - Assert.assertEquals(s1, s1.dual().glb()); + Assert.assertEquals(s1.makeRO(), s1.dual().glb()); TypeMem m1 = TypeMem.make(1,TypeInteger.ZERO); TypeMem m2 = TypeMem.make(2,TypeInteger.U16); @@ -57,7 +57,7 @@ public class TypeTest { Assert.assertEquals(ptr1nil, ptr1.glb()); Assert.assertEquals(ptr1, ptr1.dual().dual()); - Assert.assertEquals(ptr1.glb(), ptr1.dual().glb()); + Assert.assertEquals(ptr1.glb().makeRO(), ptr1.dual().glb()); Assert.assertEquals(TypeMemPtr.make(TypeStruct.BOT,true), ptr1.meet(ptr2nil)); Assert.assertEquals(ptr1.glb(), ptr1.meet(TypeMemPtr.NULLPTR)); @@ -79,7 +79,7 @@ public class TypeTest { // Test theoretical properties. // This is a symmetric complete bounded (ranked) lattice. - // Also the meet is commutative and associative. + // Also, the meet is commutative and associative. // The lattice has a dual (symmetric), and join is ~(~x meet ~y). // See https://en.wikipedia.org/wiki/Lattice_(order). @Test diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index c215de00..72f84fa2 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -36,7 +36,7 @@ public class Evaluator { sb.append("obj@").append(cid); return id; } - if (struct._name.equals("u8[]")) { + if (struct._name.equals("[u8]")) { sb.append('"'); for (int i=struct._fields.length-1; i<fields.length; i++) { var v = fields[i]; @@ -308,6 +308,7 @@ public class Evaluator { case CProjNode cproj -> ((Object[])val(cproj.ctrl()))[cproj._idx]; case ProjNode proj -> ((Object[])val( proj.in(0) ))[ proj._idx]; case ScopeMinNode mem -> null; + case ReadOnlyNode ro -> val(ro.in(1)); default -> throw new AssertionError("Unexpected node " + node); }; } |
