diff options
Diffstat (limited to 'src')
50 files changed, 1454 insertions, 635 deletions
diff --git a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 8a96e69c..2eac6ccc 100644 --- a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -69,17 +69,6 @@ public abstract class GlobalCodeMotion { cfg.loopDepth(); for( Node n : cfg._inputs ) _schedEarly(n,visit); - // Strictly for dead infinite loops, we can have entire code blocks - // not reachable from below - so we reach down, from above, one - // step. Since _schedEarly modifies the output arrays, the normal - // region._outputs ArrayList iterator throws CME. The extra edges - // are always *added* after any Phis, so just walk the Phi prefix. - if( cfg instanceof RegionNode region ) { - int len = region.nOuts(); - for( int i=0; i<len; i++ ) - if( region.out(i) instanceof PhiNode phi ) - _schedEarly(phi,visit); - } } } @@ -95,18 +84,20 @@ public abstract class GlobalCodeMotion { private static void _schedEarly(Node n, BitSet visit) { if( n==null || visit.get(n._nid) ) return; // Been there, done that + assert !(n instanceof CFGNode); visit.set(n._nid); // Schedule not-pinned not-CFG inputs before self. Since skipping // Pinned, this never walks the backedge of Phis (and thus spins around // a data-only loop, eventually attempting relying on some pre-visited- // not-post-visited data op with no scheduled control. for( Node def : n._inputs ) - if( def!=null && !def.isPinned() ) + if( def!=null ) _schedEarly(def,visit); // If not-pinned (e.g. constants, projections, phi) and not-CFG if( !n.isPinned() ) { // Schedule at deepest input CFGNode early = Parser.START; // Maximally early, lowest idepth + if( n.in(0) instanceof CFGNode cfg ) early = cfg; for( int i=1; i<n.nIns(); i++ ) if( n.in(i).cfg0().idepth() > early.idepth() ) early = n.in(i).cfg0(); // Latest/deepest input @@ -123,7 +114,7 @@ public abstract class GlobalCodeMotion { // Copy the best placement choice into the control slot for( int i=0; i<late.length; i++ ) - if( ns[i] != null ) + if( ns[i] != null && !(ns[i] instanceof ProjNode) ) ns[i].setDef(0,late[i]); } @@ -138,18 +129,22 @@ public abstract class GlobalCodeMotion { // These I know the late schedule of, and need to set early for loops if( n instanceof CFGNode cfg ) late[n._nid] = cfg.blockHead() ? cfg : cfg.cfg(0); else if( n instanceof PhiNode phi ) late[n._nid] = phi.region(); - else if( n.isPinned() ) late[n._nid] = n.cfg0(); + else if( n instanceof ProjNode && n.in(0) instanceof CFGNode cfg ) late[n._nid] = cfg; else { // All uses done? for( Node use : n._outputs ) - if( late[use._nid]==null ) + 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._type instanceof TypeMem && late[memuse._nid]==null ) + if( late[memuse._nid]==null && + // Load-use directly defines memory + (memuse._type instanceof TypeMem || + // Load-use indirectly defines memory + (memuse._type instanceof TypeTuple tt && tt._types[ld._alias] instanceof TypeMem)) ) continue outer; // All uses done, schedule @@ -170,11 +165,12 @@ public abstract class GlobalCodeMotion { private static void _doSchedLate(Node n, Node[] ns, CFGNode[] late) { // Walk uses, gathering the LCA (Least Common Ancestor) of uses - CFGNode early = (CFGNode)n.in(0); + CFGNode early = n.in(0) instanceof CFGNode cfg ? cfg : n.in(0).cfg0(); assert early != null; CFGNode lca = null; for( Node use : n._outputs ) - lca = use_block(n,use, late)._idom(lca,null); + if( use != null ) + lca = use_block(n,use, late)._idom(lca,null); // Loads may need anti-dependencies, raising their LCA if( n instanceof LoadNode load ) @@ -226,6 +222,10 @@ public abstract class GlobalCodeMotion { assert late[st._nid]!=null; lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st); break; + case NewNode st: + assert late[st._nid]!=null; + lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st); + break; case PhiNode phi: // Repeat anti-dep for matching Phi inputs. // No anti-dep edges but may raise the LCA. diff --git a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index 604770a4..f5fa1350 100644 --- a/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -82,8 +82,8 @@ public class GraphVisualizer { for (Node n : all) { if (n instanceof ProjNode || n instanceof CProjNode || n instanceof ScopeNode || n==Parser.XCTRL) continue; // Do not emit, rolled into MultiNode or Scope cluster already - if (_separateControlCluster && doCtrl && !n.isCFG()) continue; - if (_separateControlCluster && !doCtrl && n.isCFG()) continue; + if( _separateControlCluster && doCtrl && !(n instanceof CFGNode) ) continue; + if( _separateControlCluster && !doCtrl && (n instanceof CFGNode) ) continue; sb.append("\t\t").append(n.uniqueName()).append(" [ "); String lab = n.glabel(); if (n instanceof MultiNode) { @@ -93,6 +93,7 @@ public class GraphVisualizer { sb.append("\t\t\t<TR><TD BGCOLOR=\"yellow\">").append(lab).append("</TD></TR>\n"); sb.append("\t\t\t<TR>"); boolean doProjTable = false; + n._outputs.sort((x,y) -> x instanceof ProjNode xp && y instanceof ProjNode yp ? (xp._idx - yp._idx) : (x._nid - y._nid)); for (Node use : n._outputs) { if (use instanceof ProjNode proj) { if (!doProjTable) { @@ -124,7 +125,7 @@ public class GraphVisualizer { } else { // control nodes have box shape // other nodes are ellipses, i.e. default shape - if (n.isCFG()) sb.append("shape=box style=filled fillcolor=yellow "); + if( n instanceof CFGNode ) sb.append("shape=box style=filled fillcolor=yellow "); else if (n instanceof PhiNode) sb.append("style=filled fillcolor=lightyellow "); sb.append("label=\"").append(lab).append("\" "); } @@ -154,14 +155,14 @@ public class GraphVisualizer { private void scope( StringBuilder sb, ScopeNode scope ) { sb.append("\tnode [shape=plaintext];\n"); int level=1; - for( int idx = scope._scopes.size()-1; idx>=0; idx-- ) { - var syms = scope._scopes.get(idx); + for( int idx = scope._idxs.size()-1; idx>=0; idx-- ) { + var syms = scope._idxs.get(idx); String scopeName = makeScopeName(scope, level); sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name sb.append("\t\t").append(scopeName).append(" [label=<\n"); sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n"); // Add the scope level - int scopeLevel = scope._scopes.size()-level; + int scopeLevel = scope._idxs.size()-level; sb.append("\t\t\t<TR><TD BGCOLOR=\"cyan\">").append(scopeLevel).append("</TD>"); for(String name: syms.keySet()) sb.append("<TD PORT=\"").append(makePortName(scopeName, name)).append("\">").append(name).append("</TD>"); @@ -212,7 +213,7 @@ public class GraphVisualizer { if ( n instanceof NewNode ) sb.append(" color=green"); // control edges are colored red - else if( def.isCFG() ) + else if( def instanceof CFGNode ) sb.append(" color=red"); else if( def.isMem() ) sb.append(" color=blue"); @@ -229,8 +230,8 @@ public class GraphVisualizer { private void scopeEdges( StringBuilder sb, ScopeNode scope ) { sb.append("\tedge [style=dashed color=cornflowerblue];\n"); int level=1; - for( int i = scope._scopes.size()-1; i>=0; i-- ) { - var syms = scope._scopes.get(i); + for( int i = scope._idxs.size()-1; i>=0; i-- ) { + var syms = scope._idxs.get(i); String scopeName = makeScopeName(scope, level); for( String name : syms.keySet() ) { int idx = syms.get(name); diff --git a/src/main/java/com/seaofnodes/simple/IRPrinter.java b/src/main/java/com/seaofnodes/simple/IRPrinter.java index 43c6c9f7..418cda29 100644 --- a/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -86,7 +86,7 @@ public class IRPrinter { boolean gap=false; for( int i=rpos.size()-1; i>=0; i-- ) { Node n = rpos.get(i); - if( n.isCFG() || n.isMultiHead() ) { + if( n instanceof CFGNode || n.isMultiHead() ) { if( !gap ) sb.append("\n"); // Blank before multihead printLine( n, sb, llvmFormat ); // Print head while( --i >= 0 ) { @@ -110,12 +110,12 @@ public class IRPrinter { if( visit.get(n._nid) ) return; // Already post-order walked visit.set(n._nid); // First walk the CFG, then everything - if( n.isCFG() ) { + if( n instanceof CFGNode ) { for( Node use : n._outputs ) - if( use!=null && use.isCFG() && use.nOuts()>=1 && !(use._outputs.get(0) instanceof LoopNode) ) + if( use instanceof CFGNode && use.nOuts() >= 1 && !(use._outputs.get( 0 ) instanceof LoopNode) ) postOrd(use, rpos,visit,bfs); for( Node use : n._outputs ) - if( use!=null && use.isCFG() ) + if( use instanceof CFGNode ) postOrd(use,rpos,visit,bfs); } for( Node use : n._outputs ) @@ -176,8 +176,8 @@ public class IRPrinter { _bs.set(n._nid); } void del(int idx) { - Node n = Utils.del(_bfs, idx); - _bs.clear(n._nid); + _bs.clear(_bfs.get(idx)._nid); + Utils.del(_bfs, idx); } boolean any_visited( Node n ) { for( Node def : n._inputs ) @@ -190,19 +190,28 @@ public class IRPrinter { // Bulk pretty printer, knowing scheduling information is available public static String prettyPrintScheduled( Node node, int depth, boolean llvmFormat ) { // Backwards DFS walk to depth. - HashMap<Node,Integer> ds = new HashMap<>(); - _walk(ds,node,depth); + HashMap<Integer,Integer> ds = new HashMap<>(); + ArrayList<Node> ns = new ArrayList<>(); + _walk(ds,ns,node,depth); + // Remove data projections, these are force-printed behind their multinode head + for( int i=0; i<ns.size(); i++ ) { + if( ns.get(i) instanceof ProjNode proj && !(proj.in(0) instanceof CFGNode) ) { + Utils.del(ns,i--); + ds.remove(proj._nid); + } + } // Print by block with least idepth StringBuilder sb = new StringBuilder(); ArrayList<Node> bns = new ArrayList<>(); while( !ds.isEmpty() ) { CFGNode blk = null; - for( Node n : ds.keySet() ) { - CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : (CFGNode)n.in(0); + for( Node n : ns ) { + CFGNode cfg = n instanceof CFGNode cfg0 && cfg0.blockHead() ? cfg0 : n.cfg0(); if( blk==null || cfg.idepth() < blk.idepth() ) blk = cfg; } - ds.remove(blk); + ds.remove(blk._nid); + ns.remove(blk); // Print block header sb.append("%-13.13s".formatted(label(blk)+":")); @@ -218,7 +227,7 @@ public class IRPrinter { bns.clear(); int xd = Integer.MAX_VALUE; for( Node use : blk._outputs ) { - Integer i = ds.get(use); + Integer i = ds.get(use._nid); if( i!=null && !(use instanceof CFGNode cfg && cfg.blockHead()) ) { bns.add(use); xd = Math.min(xd,i); @@ -227,26 +236,35 @@ public class IRPrinter { // Print Phis up front, if any for( int i=0; i<bns.size(); i++ ) if( bns.get(i) instanceof PhiNode phi ) - printLine( phi, sb, llvmFormat,bns,i--,ds); + printLine( phi, sb, llvmFormat,bns,i--,ds,ns); // Print block contents in depth order, bumping depth until whole block printed for( ; !bns.isEmpty(); xd++ ) - for( int i=0; i<bns.size(); i++ ) - if( ds.get(bns.get(i))==xd ) - printLine( bns.get(i), sb, llvmFormat, bns, i--, ds ); + for( int i=0; i<bns.size(); i++ ) { + Node n = bns.get(i); + if( ds.get(n._nid)==xd ) { + printLine( n, sb, llvmFormat, bns, i--, ds,ns ); + if( n instanceof MultiNode && !(n instanceof CFGNode) ) { + for( Node use : n._outputs ) { + printLine(use,sb,llvmFormat,bns,bns.indexOf(use),ds,ns); + } + } + } + } sb.append("\n"); } return sb.toString(); } - private static void _walk( HashMap<Node,Integer> ds, Node node, int d ) { - Integer nd = ds.get(node); + private static void _walk( HashMap<Integer,Integer> ds, ArrayList<Node> ns, Node node, int d ) { + Integer nd = ds.get(node._nid); if( nd!=null && d <= nd ) return; // Been there, done that - ds.put(node,d); + if( ds.put(node._nid,d) == null ) + ns.add(node); if( d == 0 ) return; // Depth cutoff for( Node def : node._inputs ) if( def != null ) - _walk(ds,def,d-1); + _walk(ds,ns,def,d-1); } static String label( CFGNode blk ) { @@ -257,10 +275,11 @@ public class IRPrinter { if( !blk.blockHead() ) blk = blk.cfg(0); sb.append( "%-9.9s ".formatted( label( blk ) ) ); } - static void printLine( Node n, StringBuilder sb, boolean llvmFormat, ArrayList<Node> bns, int i, HashMap<Node,Integer> ds ) { + static void printLine( Node n, StringBuilder sb, boolean llvmFormat, ArrayList<Node> bns, int i, HashMap<Integer,Integer> ds, ArrayList<Node> ns ) { printLine( n, sb, llvmFormat ); - Utils.del(bns,i); - ds.remove(n); + if( i != -1 ) Utils.del(bns,i); + ds.remove(n._nid); + ns.remove(n); } } diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 9e4b9eb6..4bb18d6b 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -23,8 +23,11 @@ public class Parser { */ public static StartNode START; - public static ConstantNode ZERO; - public static XCtrlNode XCTRL; + public static ConstantNode ZERO; // Very common node, cached here + public static XCtrlNode XCTRL; // Very common node, cached here + + // Next available memory alias number + static int ALIAS; public StopNode STOP; @@ -89,7 +92,9 @@ public class Parser { ScopeNode _continueScope; ScopeNode _breakScope; - // Mapping from a type name to a Type. + // 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 static HashMap<String, Type> TYPES = new HashMap<>(); public Parser(String source, TypeInteger arg) { @@ -116,8 +121,9 @@ public class Parser { _continueScope = _breakScope = null; START = new StartNode(new Type[]{ Type.CONTROL, arg }); STOP = new StopNode(source); - ZERO = new ConstantNode(TypeInteger.constant(0)).peephole().keep(); + ZERO = con(0).keep(); XCTRL= new XCtrlNode().peephole().keep(); + ALIAS = 2; // alias 0 for the control, 1 for memory } public Parser(String source) { @@ -143,9 +149,12 @@ public class Parser { _scope.push(); _scope.define(ScopeNode.CTRL, Type.CONTROL , new CProjNode(START, 0, ScopeNode.CTRL).peephole()); _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 1, ScopeNode.ARG0).peephole()); + + // Parse whole program parseBlock(); + if( ctrl()._type==Type.CONTROL ) - STOP.addReturn(new ReturnNode(ctrl(), new ConstantNode(TypeInteger.constant(0)).peephole(), _scope).peephole()); + STOP.addReturn(new ReturnNode(ctrl(), ZERO, _scope).peephole()); _scope.pop(); _xScopes.pop(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); @@ -207,7 +216,7 @@ public class Parser { Type t = type(); if( t==null ) throw errorSyntax("Requires a field type, found '"+_lexer.getAnyNextToken()+"'"); - return require(Field.make(requireId().intern(),t),";"); + return require(Field.make(requireId().intern(),ALIAS++,t),";"); } /** @@ -221,7 +230,9 @@ 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 TypeStruct ts && ts._fields==null) ) throw errorSyntax("struct '" + typeName + "' cannot be redefined"); + if( t!=null && !(t instanceof TypeMemPtr tmp && tmp._obj._fields==null) ) + throw errorSyntax("struct '" + typeName + "' cannot be redefined"); + // Parse a collection of fields ArrayList<Field> fields = new ArrayList<>(); require("{"); while (!peek('}') && !_lexer.isEOF()) { @@ -231,8 +242,8 @@ public class Parser { } require("}"); // Build and install the TypeStruct - TypeStruct ts = TypeStruct.make(typeName, fields); - TYPES.put(typeName, ts); + TypeStruct ts = TypeStruct.make(typeName, fields.toArray(new Field[fields.size()])); + TYPES.put(typeName, TypeMemPtr.make(ts)); START.addMemProj(ts, _scope); // Insert memory edges return parseStatement(); } @@ -325,7 +336,7 @@ public class Parser { ctrl(XCTRL); // Kill current scope // Prune nested lexical scopes that have depth > than the loop head // We use _breakScope as a proxy for the loop head scope to obtain the depth - while( cur._scopes.size() > _breakScope._scopes.size() ) + while( cur._idxs.size() > _breakScope._idxs.size() ) cur.pop(); // If this is a continue then first time the target is null // So we just use the pruned current scope as the base for the @@ -333,7 +344,7 @@ public class Parser { if (toScope == null) return cur; // toScope is either the break scope, or a scope that was created here - assert toScope._scopes.size() <= _breakScope._scopes.size(); + assert toScope._idxs.size() <= _breakScope._idxs.size(); toScope.ctrl(toScope.mergeScopes(cur)); return toScope; } @@ -463,33 +474,70 @@ public class Parser { // Auto-deepen forward ref types Type e = expr._type; if( e instanceof TypeMemPtr tmp && tmp._obj._fields==null ) - e = tmp.make_from((TypeStruct)TYPES.get(tmp._obj._name)); + 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()); return _scope.update(name,expr); } - // Parse a "type id" and return "type" (and re-parse "id" in caller) or - // return null. + // Parse and return a type or null. Valid types always are followed by an + // '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. private Type type() { - int old = _lexer._position; + int old1 = _lexer._position; String tname = _lexer.matchId(); if( tname==null ) return null; - boolean nullable = match("?"); - Type t = TYPES.get(tname); - // Assume a forward-reference type - if( t == null ) { - int old2 = _lexer._position; - String id = _lexer.matchId(); - if( id==null ) { - _lexer._position = old; - 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 + // Nest arrays and '?' as needed + while( true ) { + assert !(t1 instanceof TypeStruct); + if( match("?") ) { + if( !(t1 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; } - TYPES.put(tname,t = TypeStruct.make(tname)); - _lexer._position = old2; // Reparse ID in caller + break; } - return t instanceof TypeStruct obj ? TypeMemPtr.make(obj,nullable) : t; + + // Check no forward ref + if( t0 != null ) return t1; + // 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; + 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 + } + // Yes a forward ref, so declare it + TYPES.put(tname,t1); + return t1; + } + + // Make an array type of t + private TypeMemPtr typeAry( Type t ) { + if( t instanceof TypeMemPtr tmp && !tmp._nil ) + throw error("Arrays of reference types must always be nullable"); + String tname = t.str()+"[]"; + Type ta = TYPES.get(tname); + if( ta != null ) return (TypeMemPtr)ta; + // Need make an array type. + TypeStruct ts = TypeStruct.makeAry(TypeInteger.BOT,ALIAS++,t,ALIAS++); + TypeMemPtr tary = TypeMemPtr.make(ts); + TYPES.put(tname,tary); + START.addMemProj(ts, _scope); // Insert memory alias edges + return tary; } @@ -637,22 +685,36 @@ public class Parser { * Parse a primary expression: * * <pre> - * primaryExpr : integerLiteral | Identifier | true | false | null | new Identifier | '(' expression ')' + * primaryExpr : integerLiteral | Identifier | true | false | null | new Type | '(' expression ')' * </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 new ConstantNode(TypeInteger.constant(1)).peephole(); + if( matchx("true" ) ) return con(1); if( matchx("false") ) return ZERO; if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole(); if( matchx("new") ) { - String structName = requireId(); - Type t = TYPES.get(structName); - if( !(t instanceof TypeStruct obj) || obj._fields==null ) - throw error("Unknown struct type '" + structName + "'"); - return newStruct(obj); + Type t = type(); + if( t==null ) throw error("Expected a type"); + if( match("[") ) { + Node len = parseExpression().keep(); + if( !(len._type instanceof TypeInteger) ) + throw error("Cannot allocate an array with length "+len._type); + require("]"); + TypeMemPtr tmp = typeAry(t); + return newArray(tmp._obj,len); + } + if( t instanceof TypeMemPtr tmp ) { + TypeStruct obj = tmp._obj; + if( obj._fields==null ) + throw error("Unknown struct type '" + obj._name + "'"); + if( obj.isAry() ) + throw Utils.TODO(); // Missing array length + return newStruct(obj,con(obj.offset(obj._fields.length))); + } + throw error("Cannot allocate a "+t.str()); } String name = _lexer.matchId(); if( name == null) throw errorSyntax("an identifier or expression"); @@ -662,16 +724,29 @@ public class Parser { } /** - * Return a NewNode but also generate instructions to initialize it. + * Return a NewNode with pre-zeroed memory */ - private Node newStruct(TypeStruct obj) { - Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep(); - int alias = START._aliasStarts.get(obj._name); - for( Field field : obj._fields ) { - memAlias(alias, new StoreNode(field._fname, alias, field._type, ctrl(), memAlias(alias), n, new ConstantNode(field._type.makeInit()).peephole(),true).peephole()); - alias++; - } - return n.unkeep(); + private Node newStruct(TypeStruct obj, Node size) { + Field[] fs = obj._fields; + Node[] ns = new Node[2+fs.length]; + ns[0] = ctrl(); + ns[1] = size; + for( int i = 0; i < fs.length; i++ ) + ns[i+2] = memAlias(fs[i]._alias); + Node nnn = new NewNode(TypeMemPtr.make(obj), ns).peephole(); + for( int i = 0; i < fs.length; i++ ) + memAlias(fs[i]._alias, new ProjNode(nnn,i+2,memName(fs[i]._alias)).peephole()); + return new ProjNode(nnn,1,obj._name).peephole(); + } + + private Node newArray(TypeStruct ary, Node len) { + int base = ary.aryBase (); + int scale= ary.aryScale(); + Node size = new AddNode(con(base),new ShlNode(len,con(scale)).peephole()).peephole(); + Node ptr = newStruct(ary,size); + int alias = ary._fields[0]._alias; // Length alias + memAlias(alias,new StoreNode("#",alias,TypeInteger.BOT,memAlias(alias),ptr,con( ary.offset(0) ), len.unkeep(), true ).peephole()); + return ptr; } // We set up memory aliases by inserting special vars in the scope these @@ -688,39 +763,70 @@ public class Parser { * * <pre> * expr ('.' IDENTIFIER)* [ = expr ] + * expr # + * expr ('[' expr ']')* = [ = expr ] * </pre> */ private Node parsePostfix(Node expr) { - if( !match(".") ) return expr; + String name = null; + if( match(".") ) name = requireId().intern(); + else if( match("#") ) name = "#"; + else if( match("[") ) name = "[]"; + else return expr; // No postfix + // Sanity check expr for being a reference if( !(expr._type instanceof TypeMemPtr ptr) ) - throw error("Expected struct reference but got " + expr._type.str()); - - String name = requireId().intern(); - if( expr._type == TypeMemPtr.TOP ) throw error("Accessing field '" + name + "' from null"); + throw error("Expected reference but got " + expr._type.str()); + if( ptr == TypeMemPtr.TOP ) throw error("Accessing field '" + name + "' from null"); if( ptr._obj == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); - TypeStruct base = (TypeStruct)TYPES.get(ptr._obj._name); - int idx = base==null ? -1 : base.find(name); - if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); - int alias = START._aliasStarts.get(ptr._obj._name)+idx; + // Sanity check field name for existing + TypeMemPtr tmp = (TypeMemPtr)TYPES.get(ptr._obj._name); + if( tmp == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); + TypeStruct base = tmp._obj; + int fidx = base.find(name); + if( fidx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); + expr.keep(); + + // Get field type and layout offset from base type and field index fidx + Field f = base._fields[fidx]; // Field from field index + Node off; + if( name.equals("[]") ) { // If field is an array body + // Array index math + Node idx = require(parseExpression(),"]"); + Node shl = new ShlNode(idx,con(base.aryScale())).peephole(); + off = new AddNode(con(base.aryBase()),shl).peephole(); + } else { // Else normal struct field + // Hardwired field offset + off = con(base.offset(fidx)); + } if( match("=") ) { // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment if( peek('=') ) _lexer._position--; else { + off.keep(); Node val = parseExpression(); - Type glb = base._fields[idx]._type; // Auto-truncate when storing to narrow fields - val = zsMask(val,glb); - memAlias(alias, new StoreNode(name, alias,glb, ctrl(), memAlias(alias), expr, val, false).peephole()); - return expr; // "obj.a = expr" returns the expression while updating memory + val = zsMask(val,f._type).keep(); + Node st = new StoreNode(name, f._alias, f._type, memAlias(f._alias), expr.unkeep(), off.unkeep(), val, false); + // Arrays include control, as a proxy for a safety range check. + // Structs don't need this; they only need a NPE check which is + // done via the type system. + if( base.isAry() ) st.setDef(0,ctrl()); + memAlias(f._alias, st.peephole()); + return val.unkeep(); // "obj.a = expr" returns the expression while updating memory } } - Type declaredType = base._fields[idx]._type; - return parsePostfix(new LoadNode(name, alias, declaredType.glb(), memAlias(alias), expr).peephole()); + Node load = new LoadNode(name, f._alias, f._type.glb(), memAlias(f._alias), expr.unkeep(), 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()); } + // zero/sign extend. "i" is limited to either classic unsigned (min==0) or // classic signed (min=minus-power-of-2); max=power-of-2-minus-1. private Node zsMask(Node val, Type t ) { @@ -731,10 +837,10 @@ public class Parser { return new RoundF32Node(val).peephole(); } if( t0._min==0 ) // Unsigned - return new AndNode(val,new ConstantNode(TypeInteger.constant(t0._max)).peephole()).peephole(); + return new AndNode(val,con(t0._max)).peephole(); // Signed extension int shift = Long.numberOfLeadingZeros(t0._max)-1; - Node shf = new ConstantNode(TypeInteger.constant(shift)).peephole(); + Node shf = con(shift); if( shf._type==TypeInteger.ZERO ) return val; return new SarNode(new ShlNode(val,shf.keep()).peephole(),shf.unkeep()).peephole(); @@ -753,6 +859,10 @@ public class Parser { return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole(); } + public static Node con( long con ) { + return new ConstantNode(TypeInteger.constant(con)).peephole(); + } + ////////////////////////////////// // Utilities for lexical analysis diff --git a/src/main/java/com/seaofnodes/simple/Utils.java b/src/main/java/com/seaofnodes/simple/Utils.java index f3ac25b1..1346c3ea 100644 --- a/src/main/java/com/seaofnodes/simple/Utils.java +++ b/src/main/java/com/seaofnodes/simple/Utils.java @@ -13,14 +13,9 @@ public class Utils { * @param i element to be removed * @return element removed */ - public static <E> E del(ArrayList<E> array, int i) { - if ( i >= 0 && i < array.size() ) { - E tmp = array.get(i); - E last = array.removeLast(); - if (i < array.size()) array.set(i, last); - return tmp; - } - return null; + public static <E> void del(ArrayList<E> array, int i) { + E last = array.removeLast(); + if (i < array.size()) array.set(i, last); } /** diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 9d425f7a..f3b213fb 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -22,7 +22,8 @@ public class AddNode extends Node { @Override public Type compute() { Type t1 = in(1)._type, t2 = in(2)._type; - if( t1.isHigh() || t2.isHigh() ) return TypeInteger.TOP; + if( t1.isHigh() || t2.isHigh() ) + return TypeInteger.TOP; if( t1 instanceof TypeInteger i1 && t2 instanceof TypeInteger i2 ) { if (i1.isConstant() && i2.isConstant()) @@ -36,7 +37,7 @@ public class AddNode extends Node { } private static boolean overflow( long x, long y ) { - if( (x ^ y ) < 0 ) return false; // unequal signs, never overflow + if( (x ^ y ) < 0 ) return false; // unequal signs, never overflow return (x ^ (x + y)) < 0; // sum has unequal signs, so overflow } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/AndNode.java b/src/main/java/com/seaofnodes/simple/node/AndNode.java index 350859db..7e4b898b 100644 --- a/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -21,7 +21,6 @@ public class AndNode extends Node { @Override public Type compute() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; if( in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) diff --git a/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/src/main/java/com/seaofnodes/simple/node/BoolNode.java index f0cca1e2..238be00e 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -37,9 +37,6 @@ abstract public class BoolNode extends Node { Type t2 = in(2)._type; if( t1.isHigh() || t2.isHigh() ) return BOOL.dual(); - // Compare of same - if( in(1)==in(2) ) - return doOp(ZERO,ZERO); if( t1 instanceof TypeInteger i1 && t2 instanceof TypeInteger i2 ) return doOp(i1,i2); @@ -56,6 +53,10 @@ abstract public class BoolNode extends Node { @Override public Node idealize() { + // Compare of same + if( in(1)==in(2) ) + return new ConstantNode(doOp(ZERO,ZERO)); + // Equals pushes constant to the right; 5==X becomes X==5. if( this instanceof EQ ) { if( !(in(2) instanceof ConstantNode) ) { @@ -67,11 +68,14 @@ abstract public class BoolNode extends Node { // Equals X==0 becomes a !X if( (in(2)._type == ZERO || in(2)._type == TypeMemPtr.NULLPTR) ) return new NotNode(in(1)); - // Equals bool == 1 becomes bool - if( in(2)._type == TRUE && in(1)._type == BOOL ) - return in(1); } + // Do we have ((x * (phi cons)) * con) ? + // Do we have ((x * (phi cons)) * (phi cons)) ? + // Push constant up through the phi: x * (phi con0*con0 con1*con1...) + Node phicon = AddNode.phiCon(this,this instanceof EQ); + if( phicon!=null ) return phicon; + return null; } @@ -109,8 +113,8 @@ abstract public class BoolNode extends Node { Node copyF() { return new LEF(null,null); } } - public static class EQF extends EQ { public EQF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs == rhs; } Node copy(Node lhs, Node rhs) { return new EQF(lhs,rhs); } } - public static class LTF extends LT { public LTF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs < rhs; } Node copy(Node lhs, Node rhs) { return new LTF(lhs,rhs); } } - public static class LEF extends LE { public LEF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs <= rhs; } Node copy(Node lhs, Node rhs) { return new LEF(lhs,rhs); } } + public static class EQF extends EQ { public EQF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs == rhs; } } + public static class LTF extends LT { public LTF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs < rhs; } } + public static class LEF extends LE { public LEF(Node lhs, Node rhs) { super(lhs,rhs); } boolean doOp(double lhs, double rhs) { return lhs <= rhs; } } } diff --git a/src/main/java/com/seaofnodes/simple/node/CFGNode.java b/src/main/java/com/seaofnodes/simple/node/CFGNode.java index 07ba0fa4..9e9d6970 100644 --- a/src/main/java/com/seaofnodes/simple/node/CFGNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CFGNode.java @@ -23,9 +23,6 @@ public abstract class CFGNode extends Node { public CFGNode(Node... nodes) { super(nodes); } - @Override public boolean isCFG() { return true; } - @Override public boolean isPinned() { return true; } - public CFGNode cfg(int idx) { return (CFGNode)in(idx); } // Block head is Start, Region, CProj, but not e.g. If, Return, Stop diff --git a/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/src/main/java/com/seaofnodes/simple/node/CProjNode.java index fb0ff879..3d6fd1fa 100644 --- a/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -37,14 +37,17 @@ public class CProjNode extends CFGNode { @Override public Node idealize() { - if ( ctrl() instanceof IfNode iff ) { - if ( iff._type instanceof TypeTuple tt && tt._types[1 - _idx] == Type.XCONTROL ) - return iff.in(0); // We become our input control - - // Flip a negating if-test, to remove the not - if( iff.pred().addDep(this) instanceof NotNode not ) - return new CProjNode(new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True"); + if( ctrl()._type instanceof TypeTuple tt ) { + if( tt._types[_idx]==Type.XCONTROL ) + return Parser.XCTRL; // We are dead + if( ctrl() instanceof IfNode && tt._types[1-_idx]==Type.XCONTROL ) // Only true for IfNodes + return ctrl().in(0); // We become our input control } + + // Flip a negating if-test, to remove the not + if( ctrl() instanceof IfNode iff && iff.pred().addDep(this) instanceof NotNode not ) + return new CProjNode(new IfNode(iff.ctrl(),not.in(1)).peephole(),1-_idx,_idx==0 ? "False" : "True"); + return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 016b0b9b..845b9d08 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -36,8 +36,6 @@ public class ConstantNode extends Node { } @Override public boolean isMultiTail() { return true; } - // The special forever-zero is pinned, all others can sink - @Override public boolean isPinned() { return this==Parser.ZERO; } @Override public Type compute() { return _con; } diff --git a/src/main/java/com/seaofnodes/simple/node/DivNode.java b/src/main/java/com/seaofnodes/simple/node/DivNode.java index da9571db..76e98678 100644 --- a/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -37,7 +37,7 @@ public class DivNode extends Node { @Override public Node idealize() { // Div of 1. - if( in(2)._type.isConstant() && in(2)._type instanceof TypeInteger i && i.value()==1 ) + if( in(2)._type == TypeInteger.TRUE ) return in(1); return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 78ccc8a9..0bdf86f0 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -1,8 +1,10 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; - +import com.seaofnodes.simple.type.TypeMem; +import com.seaofnodes.simple.type.TypeStruct; import java.util.BitSet; /** @@ -15,34 +17,82 @@ public class LoadNode extends MemOpNode { * Load a value from a ptr.field. * * @param name The field we are loading - * @param memSlice The memory alias node - this is updated after a Store - * @param memPtr The ptr to the struct from where we load a field + * @param mem The memory alias node - this is updated after a Store + * @param ptr The ptr to the struct base from where we load a field + * @param off The offset inside the struct base */ - public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) { - super(name, alias, glb, null, memSlice, memPtr); + public LoadNode(String name, int alias, Type glb, Node mem, Node ptr, Node off) { + super(name, alias, glb, mem, ptr, off); } - @Override public String label() { return _name; } - @Override public String glabel() { return "."+_name; } + // GraphVis DOT code (must be valid Java identifiers) and debugger labels + @Override public String label() { return "ld_"+mlabel(); } + // GraphVis node-internal labels + @Override public String glabel() { return "." +_name; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(".").append(_name); } @Override public Type compute() { + if( mem()._type instanceof TypeMem mem && + // No constant folding if ptr might null-check + _declaredType != mem._t && err()==null ) { + assert mem._alias == _alias; + return _declaredType.join(mem._t); + } return _declaredType; } @Override public Node idealize() { + Node ptr = ptr(); // Simple Load-after-Store on same address. if( mem() instanceof StoreNode st && - ptr() == st.ptr() ) { // Must check same object + ptr == st.ptr() && off() == st.off() ) { // Must check same object assert _name.equals(st._name); // Equiv class aliasing is perfect return st.val(); } + // Simple Load-after-New on same address. + if( mem() instanceof ProjNode p && p.in(0) instanceof NewNode nnn && + ptr == nnn.proj(1) ) // Must check same object + return new ConstantNode(_declaredType.makeInit()); + + // 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. + Node mem = mem(); + outer: + while( true ) { + switch( mem ) { + case StoreNode st: + if( ptr == st.ptr() && off() == st.off() ) + return 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 + break outer; // Cannot tell, stop trying + // Pointers cannot overlap + mem = st.mem(); // Proved never equal + break; + case PhiNode phi: + break outer; // Assume related + case ProjNode mproj: + if( mproj.in(0) instanceof NewNode nnn1 ) { + if( ptr instanceof ProjNode pproj && pproj.in(0) == mproj.in(0) ) + return new ConstantNode(_declaredType.makeInit()); // Load from a New + 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 throw Utils.TODO(); + default: + throw Utils.TODO(); + } + } + // Push a Load up through a Phi, as long as it collapses on at least // one arm. If at a Loop, the backedge MUST collapse - else we risk // spinning the same transform around the loop indefinitely. @@ -50,31 +100,38 @@ public class LoadNode extends MemOpNode { // if( pred ) ptr.x = e0; val = pred ? e0 // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; - if( mem() instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 ) { + if( mem() instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 && + off() instanceof ConstantNode ) { // Profit on RHS/Loop backedge if( profit(memphi,2) || // Else must not be a loop to count profit on LHS. (!(memphi.region() instanceof LoopNode) && profit(memphi,1)) ) { - if( ptr() instanceof NewNode || !(ptr() instanceof CastNode) ) { - if( !(ptr() instanceof NewNode) ) throw Utils.TODO(); // Validate - - Node ld1 = new LoadNode(_name,_alias,_declaredType,memphi.in(1),ptr()).peephole(); - Node ld2 = new LoadNode(_name,_alias,_declaredType,memphi.in(2),ptr()).peephole(); - return new PhiNode(_name,_type,memphi.region(),ld1,ld2); - } + Node ld1 = ld(1); + Node ld2 = ld(2); + return new PhiNode(_name,_declaredType,memphi.region(),ld1,ld2); } } 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 + ptr1 instanceof ProjNode && ptr1.in(0) instanceof NewNode && + ptr2 instanceof ProjNode && ptr2.in(0) instanceof NewNode; + } + // Profitable if we find a matching Store on this Phi arm. private boolean profit(PhiNode phi, int idx) { Node px = phi.in(idx); - return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr(); - } - - Node copy(Node mem, Node ptr) { - return new LoadNode(_name,_alias,_declaredType,mem,ptr); + if( px==null ) return false; + if( px._type instanceof TypeMem mem && mem._t.isHighOrConst() ) { px.addDep(this); return true; } + if( px instanceof StoreNode st1 && ptr()==st1.ptr() && off()==st1.off() ) { px.addDep(this); return true; } + return false; } } diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 76564db0..c7a1efec 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -13,16 +13,24 @@ public abstract class MemOpNode extends Node { public final int _alias; public final Type _declaredType; - - public MemOpNode(String name, int alias, Type glb, Node... nodes) { - super(nodes); + public MemOpNode(String name, int alias, Type glb, Node mem, Node ptr, Node off) { + super(null, mem, ptr, off); _name = name; _alias = alias; _declaredType = glb; } + public MemOpNode(String name, int alias, Type glb, Node mem, Node ptr, Node off, Node value) { + this(name, alias, glb, mem, ptr, off); + addDef(value); + } + + // + static String mlabel(String name) { return name.equals("[]") ? "ary" : (name.equals("#") ? "len" : name); } + String mlabel() { return mlabel(_name); } public Node mem() { return in(1); } public Node ptr() { return in(2); } + public Node off() { return in(3); } @Override boolean eq(Node n) { @@ -36,8 +44,11 @@ public abstract class MemOpNode extends Node { @Override String err() { Type ptr = ptr()._type; - return (ptr==Type.BOTTOM || (ptr instanceof TypeMemPtr tmp && tmp._nil) ) - ? "Might be null accessing '" + _name + "'" - : null; + // Already an error, but better error messages come from elsewhere + if( ptr == Type.BOTTOM ) return null; + // Better be a not-nil TMP + if( ptr instanceof TypeMemPtr tmp && !tmp._nil ) + return null; + return "Might be null accessing '" + _name + "'"; } } diff --git a/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 8ba45d26..8a2c9406 100644 --- a/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -22,9 +22,7 @@ public class MinusNode extends Node { public Type compute() { if( in(1)._type instanceof TypeInteger i0 ) { if( i0.isHigh() ) return TypeInteger.TOP; - // Catch overflow wrapping on `-Long.MIN_VALUE` - if( i0 == TypeInteger.BOT || i0._min == Long.MIN_VALUE ) return TypeInteger.BOT; - return TypeInteger.make(-i0._max,-i0._min); + return i0==TypeInteger.BOT ? TypeInteger.BOT : TypeInteger.make(-i0._max,-i0._min); } return TypeInteger.TOP.meet(in(1)._type); } diff --git a/src/main/java/com/seaofnodes/simple/node/NewNode.java b/src/main/java/com/seaofnodes/simple/node/NewNode.java index 0724ec56..f06564cd 100644 --- a/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -1,24 +1,34 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.TypeMemPtr; - +import com.seaofnodes.simple.type.*; import java.util.BitSet; -public class NewNode extends Node { - - TypeMemPtr _ptr; - - public NewNode(TypeMemPtr ptr, Node ctrl) { - super(ctrl); - this._ptr = ptr; +/** + * Allocation! Allocate a chunk of memory, and pre-zero it. + * The inputs include control and size, and ALL aliases being set. + * The output is large tuple, one for every alias plus the created pointer. + * New is expected to be followed by projections for every alias. + */ +public class NewNode extends Node implements MultiNode { + + public TypeMemPtr _ptr; + + public NewNode(TypeMemPtr ptr, Node... nodes) { + super(nodes); + // Control in slot 0 + assert nodes[0]._type==Type.CONTROL || nodes[0]._type == Type.XCONTROL; + // Malloc-length in slot 1 + assert nodes[1]._type instanceof TypeInteger; + // Memory slices in remaining slots + for( int i=2; i<nodes.length; i++ ) + assert nodes[i]._type instanceof TypeMem; + + _ptr = ptr; } - @Override - public String label() { return "new"; } - - @Override - public String glabel() { return "new " + _ptr._obj._name; } + @Override public String label() { + return "new_" + (_ptr._obj.isAry() ? "ary_"+_ptr._obj._fields[1]._type.str() : _ptr._obj.str()); + } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { @@ -26,10 +36,16 @@ public class NewNode extends Node { return sb.append(_ptr._obj.str()); } - @Override public boolean isPinned() { return true; } - @Override - public Type compute() { return _ptr; } + public TypeTuple compute() { + Field[] fs = _ptr._obj._fields; + Type[] ts = new Type[fs.length+2]; + ts[0] = Type.CONTROL; + ts[1] = _ptr; + for( int i=0; i<fs.length; i++ ) + ts[i+2] = TypeMem.make(fs[i]._alias,fs[i]._type.makeInit()).meet( in(i+2)._type ); + return TypeTuple.make(ts); + } @Override public Node idealize() { return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 96b569b5..461f153d 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -135,7 +135,7 @@ public abstract class Node implements OutNode { public boolean isUnused() { return nOuts() == 0; } - public CFGNode cfg0() { return (CFGNode)in(0); } + public CFGNode cfg0() { return (CFGNode)in(0); } /** * Change a <em>def</em> into a Node. Keeps the edges correct, by removing @@ -179,11 +179,10 @@ public abstract class Node implements OutNode { Node delDef(int idx) { unlock(); Node old_def = in(idx); - if( old_def != null && // If the old def exists, remove a def->use edge - old_def.delUse(this) ) // If we removed the last use, the old def is now dead + Utils.del(_inputs, idx); + if( old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def old_def.moveDepsToWorklist(); - Utils.del(_inputs, idx); return this; } @@ -295,7 +294,7 @@ public abstract class Node implements OutNode { return this; // Peephole optimizations turned off } Node n = peepholeOpt(); - return n==null ? this : deadCodeElim(n.peephole()); // Cannot return null for no-progress + return n==null ? this : deadCodeElim(n.peephole().keep()).unkeep(); // Cannot return null for no-progress } /** @@ -533,16 +532,13 @@ public abstract class Node implements OutNode { // ------------------------------------------------------------------------ // - /** Is this Node control-flow-graph related */ - public boolean isCFG() { return false; } - /** 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 */ + /** Pinned in the schedule; these are data nodes whose input#0 is not allowed to change */ public boolean isPinned() { return false; } // Semantic change to the graph (so NOT a peephole), used by the Parser. @@ -631,12 +627,7 @@ public abstract class Node implements OutNode { E x = pred.apply(this); if( x != null ) return x; for( Node def : _inputs ) if( def != null && (x = def._walk(pred)) != null ) return x; - // Unroll iterator to survive junk CME - for( int i=0; i<_outputs.size(); i++ ) { - Node use = _outputs.get(i); - if( use != null && (x = use._walk(pred)) != null ) - return x; - } + for( Node use : _outputs ) if( use != null && (x = use._walk(pred)) != null ) return x; return null; } diff --git a/src/main/java/com/seaofnodes/simple/node/OrNode.java b/src/main/java/com/seaofnodes/simple/node/OrNode.java index e18996b7..1b32d4fb 100644 --- a/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -21,7 +21,6 @@ public class OrNode extends Node { @Override public Type compute() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; if( in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) diff --git a/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 05584423..139e80a3 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -11,12 +11,12 @@ public class PhiNode extends Node { final String _label; // The Phi type we compute must stay within the domain of the Phi. - // Example Int stays Int, Ptr stays Ptr, Mem stays Mem. + // Example Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. final Type _declaredType; public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label; assert declaredType!=null; _declaredType = declaredType; } - @Override public String label() { return "Phi_"+_label; } + @Override public String label() { return "Phi_"+MemOpNode.mlabel(_label); } @Override public String glabel() { return "φ_"+_label; } @@ -73,7 +73,8 @@ public class PhiNode extends Node { // Phi(op(A,B),op(Q,R),op(X,Y)) becomes // op(Phi(A,Q,X), Phi(B,R,Y)). Node op = in(1); - if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) { + if( op.nIns()==3 && op.in(0)==null && same_op() ) { + assert !(op instanceof CFGNode); Node[] lhss = new Node[nIns()]; Node[] rhss = new Node[nIns()]; lhss[0] = rhss[0] = in(0); // Set Region @@ -81,16 +82,9 @@ public class PhiNode extends Node { lhss[i] = in(i).in(1); rhss[i] = in(i).in(2); } - Node phi_lhs = new PhiNode(_label, in(1).in(1)._type.glb(),lhss).peephole(); - Node phi_rhs = new PhiNode(_label, in(1).in(2)._type.glb(),rhss).peephole(); - Node phi_op = op.copy(phi_lhs,phi_rhs); - phi_op.setType(phi_op.compute()); - // If losing precision, don't do it - if( !phi_op._type.isa(_type) ) { - phi_op.kill(); - return null; - } - return phi_op; + Node phi_lhs = new PhiNode(_label, _declaredType,lhss).peephole(); + Node phi_rhs = new PhiNode(_label, _declaredType,rhss).peephole(); + return op.copy(phi_lhs,phi_rhs); } // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. @@ -107,9 +101,9 @@ public class PhiNode extends Node { if( in(2)._type == in(2)._type.makeInit() ) nullx = 2; if( nullx != -1 ) { Node val = in(3-nullx); - if( region().idom(this) instanceof IfNode iff && iff.pred().addDep(this)==val ) { + if( r.idom(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)region().in(nullx); + CFGNode idom = (CFGNode)r.in(nullx); while( idom.nIns() > 0 && idom.in(0) != iff ) idom = idom.idom(); if( idom instanceof CProjNode proj && proj._idx==1 ) return val; @@ -121,13 +115,9 @@ public class PhiNode extends Node { } private boolean same_op() { - for( int i=2; i<nIns(); i++ ) { - if( in(1).getClass() != in(i).getClass() ) return false; - if( in(1).in(1)._type.glb() != in(i).in(1)._type.glb() ) return false; - if( in(1).in(2)._type.glb() != in(i).in(2)._type.glb() ) return false; - } - // Load merging needs an anti-dep check. - if( in(1) instanceof MemOpNode ) return false; + for( int i=2; i<nIns(); i++ ) + if( in(1).getClass() != in(i).getClass() ) + return false; return true; } diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index f94e98a7..73c1fa15 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -20,12 +20,13 @@ public class ProjNode extends Node { _label = label; } - @Override - public String label() { return _label; } + @Override public String label() { return _label; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(_label); } + @Override public CFGNode cfg0() { return in(0).cfg0(); } + @Override public boolean isMultiTail() { return in(0).isMultiHead(); } @Override public boolean isMem() { return _type instanceof TypeMem; } @Override public boolean isPinned() { return true; } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index d5105614..bd05ce01 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -66,15 +66,70 @@ public class RegionNode extends CFGNode { // If a CFG diamond with no merging, delete: "if( pred ) {} else {};" if( !hasPhi() && // No Phi users, just a control user - in(1) instanceof ProjNode p1 && - in(2) instanceof ProjNode p2 && + in(1) instanceof CProjNode p1 && + in(2) instanceof CProjNode p2 && p1.in(0)==p2.in(0) && 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 static 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(); + 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; + } + } + 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 ) diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 444b76a8..e12f1fef 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -17,7 +17,8 @@ public class ReturnNode extends CFGNode { public ReturnNode(Node ctrl, Node data, ScopeNode scope) { super(ctrl, data); - // We lookup memory slices by the naming convention that they start with $ + // Add memory slices to Return, so all memory updates are live-on-exit. + // We look up memory slices by the naming convention that they start with $. // We could also use implicit knowledge that all memory projects are at offset >= 2 if( scope != null ) { String[] names = scope.reverseNames(); diff --git a/src/main/java/com/seaofnodes/simple/node/SarNode.java b/src/main/java/com/seaofnodes/simple/node/SarNode.java index 881a3812..ba99fde8 100644 --- a/src/main/java/com/seaofnodes/simple/node/SarNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SarNode.java @@ -21,14 +21,14 @@ public class SarNode extends Node { @Override public Type compute() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; - if (in(1)._type instanceof TypeInteger i1 && - in(2)._type instanceof TypeInteger i2) { - if( i1.isConstant() && i2.isConstant() ) - return TypeInteger.constant(i1.value()>>i2.value()); - if( i2._min < 0 || i2._max >= 64 ) - return TypeInteger.BOT; - return TypeInteger.make(i1._min>>i2._min,i1._max>>i2._min); + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if( i0.isConstant() && i1.isConstant() ) + return TypeInteger.constant(i0.value()>>i1.value()); + if( i1.isConstant() ) { + int log = (int)i1.value(); + return TypeInteger.make(-1L<<(63-log),(1L<<(63-log))-1); + } } return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 843ce733..877ae4a4 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,10 +1,9 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IterPeeps; -import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Utils; -import com.seaofnodes.simple.type.TypeMemPtr; - +import com.seaofnodes.simple.type.*; import java.util.*; /** @@ -21,24 +20,22 @@ public class ScopeNode extends Node { public static final String ARG0 = "arg"; /** - * Names for every input edge + * Map variable names to Scope input edge */ - public final Stack<HashMap<String, Integer>> _scopes; + public final Stack<HashMap<String, Integer>> _idxs; /** - * Tracks declared types for every name + * Map variable names to declared Type */ - public Stack<HashMap<String, Type>> _types; - + final Stack<HashMap<String, Type>> _decls; // A new ScopeNode public ScopeNode() { - _scopes = new Stack<>(); - _types = new Stack<>(); + _idxs = new Stack<>(); + _decls= new Stack<>(); _type = Type.BOTTOM; } - @Override public String label() { return "Scope"; } @Override @@ -58,6 +55,20 @@ public class ScopeNode extends Node { return sb.append("]"); } + public Node ctrl() { return in(0); } + + /** + * The ctrl of a ScopeNode is always bound to the currently active + * control node in the graph, via a special name '$ctrl' that is not + * a valid identifier in the language grammar and hence cannot be + * referenced in Simple code. + * + * @param n The node to be bound to '$ctrl' + * + * @return Node that was bound + */ + public Node ctrl(Node n) { return setDef(0,n); } + /** * Recover the names for all variable bindings. * The result is an array of names that is aligned with the @@ -67,7 +78,7 @@ public class ScopeNode extends Node { */ public String[] reverseNames() { String[] names = new String[nIns()]; - for( HashMap<String,Integer> syms : _scopes ) + for( HashMap<String,Integer> syms : _idxs ) for( String name : syms.keySet() ) names[syms.get(name)] = name; return names; @@ -77,33 +88,34 @@ public class ScopeNode extends Node { @Override public Node idealize() { return null; } - public void push() { _scopes.push(new HashMap<>()); _types.push(new HashMap<>()); } - public void pop() { popN(_scopes.pop().size()); _types.pop(); } + public void push() { _idxs.push(new HashMap<>()); _decls.push(new HashMap<>()); } + public void pop() { popN(_idxs.pop().size()); _decls.pop(); } /** - * Create a new name in the current scope + * Create a new variable name in the current scope */ public Node define( String name, Type declaredType, Node n ) { - HashMap<String,Integer> syms = _scopes.lastElement(); - _types.lastElement().put(name,declaredType); + HashMap<String,Integer> syms = _idxs.lastElement(); + _decls.lastElement().put(name,declaredType); if( syms.put(name,nIns()) != null ) return null; // Double define return addDef(n); } + /** * Lookup a name in all scopes starting from most deeply nested. * * @param name Name to be looked up * @see #update(String, Node, int) */ - public Node lookup( String name ) { return update(name,null,_scopes.size()-1); } + public Node lookup( String name ) { return update(name,null,_idxs.size()-1); } /** * If the name is present in any scope, then redefine else null * * @param name Name being redefined * @param n The node to bind to the name */ - public Node update( String name, Node n ) { return update(name,n,_scopes.size()-1); } + public Node update( String name, Node n ) { return update(name,n,_idxs.size()-1); } /** * Both recursive lookup and update. * <p> @@ -117,7 +129,7 @@ public class ScopeNode extends Node { */ private Node update( String name, Node n, int nestingLevel ) { if( nestingLevel<0 ) return null; // Missed in all scopes, not found - var syms = _scopes.get(nestingLevel); // Get the symbol table for nesting level + var syms = _idxs.get(nestingLevel); // Get the symbol table for nesting level var idx = syms.get(name); if( idx == null ) return update(name,n,nestingLevel-1); // Not found in this scope, recursively look in parent scope Node old = in(idx); @@ -135,29 +147,15 @@ public class ScopeNode extends Node { return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer } - // Return declared type + // Return declared type for a variable public Type lookupDeclaredType( String name ) { - for( int i=_types.size(); i>0; i-- ) { - Type t = _types.get(i-1).get(name); + for( int i=_decls.size(); i>0; i-- ) { + Type t = _decls.get(i-1).get(name); if( t != null ) return t; } return null; } - public Node ctrl() { return in(0); } - - /** - * The ctrl of a ScopeNode is always bound to the currently active - * control node in the graph, via a special name '$ctrl' that is not - * a valid identifier in the language grammar and hence cannot be - * referenced in Simple code. - * - * @param n The node to be bound to '$ctrl' - * - * @return Node that was bound - */ - public Node ctrl(Node n) { return setDef(0,n); } - /** * Duplicate a ScopeNode; including all levels, up to Nodes. So this is * neither shallow (would dup the Scope but not the internal HashMap @@ -165,7 +163,7 @@ public class ScopeNode extends Node { * also the program Nodes). * <p> * If the {@code loop} flag is set, the edges are filled in as the original - * Scope, as a indication of Lazy Phis at loop heads. The goal here is to + * Scope, as an indication of Lazy Phis at loop heads. The goal here is to * not make Phis at loop heads for variables which are never touched in the * loop body. * <p> @@ -178,10 +176,10 @@ public class ScopeNode extends Node { // 1) duplicate the name bindings of the ScopeNode across all stack levels // 2) Make the new ScopeNode a user of all the nodes bound // 3) Ensure that the order of defs is the same to allow easy merging - for( HashMap<String,Integer> syms : _scopes ) - dup._scopes.push(new HashMap<>(syms)); - for( HashMap<String,Type> ts : _types ) - dup._types.push(ts); // Types don't change, just keep stacks aligned + for( HashMap<String,Integer> syms : _idxs ) + dup._idxs.push(new HashMap<>(syms)); + for( HashMap<String,Type> ts : _decls ) + dup._decls.push(ts); // Types don't change, just keep stacks aligned dup.addDef(ctrl()); // Control input is just copied for( int i=1; 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 605c5d86..28e6dd14 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -1,8 +1,8 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; - import java.util.BitSet; public class ShlNode extends Node { @@ -21,7 +21,6 @@ public class ShlNode extends Node { @Override public Type compute() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; if (in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1) { if( i0.isConstant() && i1.isConstant() ) @@ -34,11 +33,18 @@ public class ShlNode extends Node { public Node idealize() { Node lhs = in(1); Node rhs = in(2); - Type t2 = rhs._type; - // Shl of 0. - if( t2.isConstant() && t2 instanceof TypeInteger i && (i.value()&63)==0 ) - return lhs; + if( rhs._type instanceof TypeInteger shl && shl.isConstant() ) { + // Shl of 0. + 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() ) { + 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) ); + } + } // TODO: x << 3 << (y ? 1 : 2) ==> x << (y ? 4 : 5) diff --git a/src/main/java/com/seaofnodes/simple/node/ShrNode.java b/src/main/java/com/seaofnodes/simple/node/ShrNode.java index bed18d2b..16d78ebf 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -21,19 +21,10 @@ public class ShrNode extends Node { @Override public Type compute() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; - if (in(1)._type instanceof TypeInteger i1 && - in(2)._type instanceof TypeInteger i2) { - if( i1.isConstant() && i2.isConstant() ) - return TypeInteger.constant(i1.value()>>>i2.value()); - if( i2._min < 0 || i2._max >= 64 ) - return TypeInteger.BOT; - // Zero shifting a negative makes a larger positive - // so get the endpoints correct. - long s1 = i1._min>>>i2._min; - long s2 = i1._max>>>i2._min; - boolean wrap = i1._min < 0 && i1._max >=0; - return TypeInteger.make(wrap ? 0 : Math.min(s1,s2),Math.max(s1,s2)); + if (in(1)._type instanceof TypeInteger i0 && + in(2)._type instanceof TypeInteger i1) { + if( i0.isConstant() && i1.isConstant() ) + return TypeInteger.constant(i0.value()>>>i1.value()); } return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/StartNode.java b/src/main/java/com/seaofnodes/simple/node/StartNode.java index 5f205ffd..5964e19f 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -4,7 +4,6 @@ import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.*; import java.util.Arrays; import java.util.BitSet; -import java.util.HashMap; import java.util.HashSet; /** @@ -19,16 +18,10 @@ public class StartNode extends CFGNode implements MultiNode { // This field is NOT final, because the tuple expands as we add memory aliases TypeTuple _args; - // The alias number of the first field in the struct. - // - public final HashMap<String,Integer> _aliasStarts; - - public StartNode(Type[] args) { super(); _args = TypeTuple.make(args); _type = _args; - _aliasStarts = new HashMap<>(); } /** @@ -36,28 +29,29 @@ public class StartNode extends CFGNode implements MultiNode { * as the key. */ public void addMemProj( TypeStruct ts, ScopeNode scope) { - int len = _args._types.length; - _aliasStarts.put(ts._name,len); - - // resize the tuple's type array to include all fields of the struct - int max = len + ts._fields.length; - Type[] args = Arrays.copyOf(_args._types, max); - - // The new members of the tuple get a mem type with an alias - for( int alias = len; alias < max; alias++ ) - args[alias] = TypeMem.make(alias); - _type = _args = TypeTuple.make(args); - // For each of the fields we now add a mem projection. Note that the - // alias matches the slot of the field in the tuple - for( int alias = len; alias < max; alias++ ) { - String name = Parser.memName(alias); - Node n = new ProjNode(this, alias, name).peephole(); - scope.define(name, args[alias], n); + if( ts._fields.length==0 ) return; + // Expand args type for more memory projections + Type[] args = _args._types; + int max = args.length; + for( Field f : ts._fields ) + max = Math.max(max,f._alias); + args = Arrays.copyOf(args, max+1); + // For each of the fields we now add a mem projection. + for( Field f : ts._fields ) { + TypeMem tm_decl = TypeMem.make(f._alias,f._type.glb()); + args[f._alias] = tm_decl.dual(); + String name = Parser.memName(f._alias); + Node n = new ProjNode(this, f._alias, name); // No 'compute' until ScopeNode gets typed + n._type = args[f._alias]; + scope.define(name, tm_decl, n); } + for (int i = 0; i < args.length; i++) + if (args[i] == null) + args[i] = Type.TOP; // We parsed a nested struct/array. Avoid nulls until a caller replaces this alias. + _type = _args = TypeTuple.make(args); } - @Override - public String label() { return "Start"; } + @Override public String label() { return "Start"; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { @@ -66,6 +60,7 @@ public class StartNode extends CFGNode implements MultiNode { @Override public boolean isMultiHead() { return true; } @Override public boolean blockHead() { return true; } + @Override public CFGNode cfg0() { return this; } @Override public TypeTuple compute() { return _args; } diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 57e8b3ad..b1c74b94 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -14,21 +14,24 @@ public class StoreNode extends MemOpNode { private final boolean _init; // Initializing writes are allowed to write null /** - * @param name The struct field we are assigning to - * @param memSlice The memory alias node - this is updated after a Store - * @param memPtr The ptr to the struct where we will store a value + * @param name The struct field we are assigning to + * @param mem The memory alias node - this is updated after a Store + * @param ptr The ptr to the struct base where we will store a value + * @param off The offset inside the struct base * @param value Value to be stored */ - public StoreNode(String name, int alias, Type glb, Node ctrl, Node memSlice, Node memPtr, Node value, boolean init) { - super(name, alias, glb, ctrl, memSlice, memPtr, value); + public StoreNode(String name, int alias, Type glb, Node mem, Node ptr, Node off, Node value, boolean init) { + super(name, alias, glb, mem, ptr, off, value); _init = init; } - @Override public String label() { return "." +_name+"="; } + // GraphVis DOT code and debugger labels + @Override public String label() { return "st_"+mlabel(); } + // GraphVis node-internal labels @Override public String glabel() { return "." +_name+"="; } @Override public boolean isMem() { return true; } - public Node val() { return in(3); } + public Node val() { return in(4); } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { @@ -36,7 +39,14 @@ public class StoreNode extends MemOpNode { } @Override - public Type compute() { return TypeMem.make(_alias); } + 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; + return TypeMem.make(_alias,t); + } @Override public Node idealize() { @@ -45,6 +55,7 @@ public class StoreNode extends MemOpNode { // required init-store being stomped by a first user store. if( mem() instanceof StoreNode st && ptr()==st.ptr() && // Must check same object + off()==st.off() && // And same offset ptr()._type instanceof TypeMemPtr && // No bother if weird dead pointers // Must have exactly one use of "this" or you get weird // non-serializable memory effects in the worse case. @@ -72,7 +83,7 @@ public class StoreNode extends MemOpNode { String err() { String err = super.err(); if( err != null ) return err; - Type ptr = val()._type; - return _init || ptr.isa(_declaredType) ? null : "Cannot store "+ptr+" into field "+_declaredType+" "+_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 6d2f1711..009fb30e 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -22,10 +22,6 @@ public class SubNode extends Node { @Override public Type compute() { - // Sub of same is 0 - if( in(1)==in(2) ) - return TypeInteger.ZERO; - Type t1 = in(1)._type, t2 = in(2)._type; if( t1.isHigh() || t2.isHigh() ) return TypeInteger.TOP; @@ -34,6 +30,9 @@ public class SubNode extends Node { if (i1.isConstant() && i2.isConstant()) return TypeInteger.constant(i1.value()-i2.value()); } + // Sub of same is 0 + if( in(1)==in(2) ) + return TypeInteger.ZERO; return TypeInteger.BOT; } diff --git a/src/main/java/com/seaofnodes/simple/node/XorNode.java b/src/main/java/com/seaofnodes/simple/node/XorNode.java index 3978f048..30a88dca 100644 --- a/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -21,7 +21,6 @@ public class XorNode extends Node { @Override public Type compute() { - if( in(1)._type.isHigh() || in(2)._type.isHigh() ) return TypeInteger.TOP; if( in(1)._type instanceof TypeInteger i0 && in(2)._type instanceof TypeInteger i1 ) { if( i0.isConstant() && i1.isConstant() ) diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java index b2c006dd..5e674132 100644 --- a/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/src/main/java/com/seaofnodes/simple/type/Field.java @@ -12,48 +12,52 @@ public class Field extends Type { // Field name public final String _fname; + // Unique memory alias + public final int _alias; // Type of the field public final Type _type; - private Field(String fname, Type type ) { + private Field(String fname, int alias, Type type ) { super(TFLD); _fname = fname; + _alias = alias; _type = type; } // Make with existing alias - public static Field make( String fname, Type type ) { - return new Field(fname,type).intern(); + public static Field make( String fname, int alias, Type type ) { + return new Field(fname,alias,type).intern(); } - public static final Field TEST = make("test",TypeInteger.ZERO); + public static final Field TEST = make("test",-2,TypeInteger.ZERO); public static void gather(ArrayList<Type> ts) { ts.add(TEST); } @Override Field xmeet( Type that ) { Field fld = (Field)that; // Invariant assert _fname.equals(fld._fname); - return make(_fname,_type.meet(fld._type)); + assert _alias==fld._alias; + return make(_fname,_alias,_type.meet(fld._type)); } @Override - public Field dual() { return make(_fname,_type.dual()); } + public Field dual() { return make(_fname,_alias,_type.dual()); } @Override public Field glb() { - return make(_fname,_type.glb()); + return make(_fname,_alias,_type.glb()); } // Override in subclasses - int hash() { return _fname.hashCode() ^ _type.hashCode(); } + int hash() { return _fname.hashCode() ^ _type.hashCode() ^ _alias; } boolean eq(Type t) { Field f = (Field)t; - return _fname.equals(f._fname) && _type==f._type; + return _fname.equals(f._fname) && _alias==f._alias && _type==f._type; } @Override public StringBuilder print( StringBuilder sb ) { - return _type.print(sb.append(_fname).append(" :")); + return _type.print(sb.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 49dc090a..989eff9e 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/src/main/java/com/seaofnodes/simple/type/Type.java @@ -39,6 +39,7 @@ public class Type { static final byte TMEMPTR = 9; // Memory pointer type static final byte TSTRUCT =10; // Structs; tuples with named fields static final byte TFLD =11; // Fields into struct + static final byte TARRAY =12; // Array public final byte _type; @@ -81,6 +82,7 @@ public class Type { public StringBuilder typeName( StringBuilder sb) { return print(sb); } public Type makeInit() { return null; } + public Type nonZero() { return glb(); } // ---------------------------------------------------------- @@ -178,6 +180,14 @@ public class Type { public Type glb() { return _type==TCTRL ? XCONTROL : BOTTOM; } // ---------------------------------------------------------- + + // Size in bits to hold an instance of this type. + // Sizes are expected to be between 1 and 64 bits. + // Size 0 means this either takes no space (such as a known-zero field) + // or isn't a scalar to be stored in memory. + public int log_size() { throw Utils.TODO(); } + + // ---------------------------------------------------------- // Useful in the debugger, which calls toString everywhere. // This is a more verbose dev-friendly print. @Override diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java index 975c1a9e..dc36c082 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -70,6 +70,11 @@ public class TypeFloat extends Type { @Override public boolean isHighOrConst() { return _sz<=0; } @Override public boolean isConstant() { return _sz==0; } + @Override public int log_size() { + int sz = _sz==0 ? (isF32() ? 32 : 64) : Math.abs(_sz); + return _sz==32 ? 2 : 3; + } + public double value() { return _con; } @Override @@ -111,4 +116,5 @@ public class TypeFloat extends Type { TypeFloat i = (TypeFloat)t; // Contract return _con==i._con && _sz==i._sz; } + } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index aca3e06b..042b4ba8 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.type; +import com.seaofnodes.simple.Utils; import java.util.ArrayList; /** @@ -75,6 +76,14 @@ public class TypeInteger extends Type { @Override public boolean isHighOrConst() { return _min >= _max; } @Override public boolean isConstant () { return _min == _max; } + @Override public int log_size() { + if( this==I8 || this==U8 || this==BOOL ) return 0; // 1<<0 == 1 bytes + 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 + throw Utils.TODO(); + } + public long value() { assert isConstant(); return _min; } // AND-mask of forced zeros. e.g. unsigned types will return their mask; @@ -104,8 +113,14 @@ public class TypeInteger extends Type { } @Override public TypeInteger dual() { return make(_max,_min); } - @Override public Type glb() { return BOT; } + @Override public TypeInteger glb() { return BOT; } @Override public TypeInteger makeInit() { return ZERO; } + @Override public TypeInteger nonZero() { + if( isHigh() ) return this; + if( _min==0 ) return make(1,_max); // specifically good on BOOL + if( _max==0 ) return make(_min,-1); + return this; + } @Override int hash() { return (int)((_min ^ (_min>>32)) *(_max ^ (_max>>32))); } @Override public boolean eq( Type t ) { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index b2d081f4..32491a11 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -16,47 +16,53 @@ public class TypeMem extends Type { // -1 means BOT, all memory. // N means slice#N. public final int _alias; + public final Type _t; // Memory contents, some scalar type - private TypeMem(int alias) { super(TMEM); _alias = alias; } + private TypeMem(int alias, Type t) { super(TMEM); _alias = alias; _t = t; } - public static TypeMem make(int alias) { return new TypeMem(alias).intern(); } - public static final TypeMem TOP = make( 0); - public static final TypeMem BOT = make(-1); + 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 BOT = make(-1, Type.BOTTOM); - public static void gather(ArrayList<Type> ts) { ts.add(make(1)); ts.add(BOT); } + public static void gather(ArrayList<Type> ts) { ts.add(make(1,TypeInteger.ZERO)); ts.add(BOT); } @Override TypeMem xmeet(Type t) { TypeMem that = (TypeMem) t; // Invariant: TypeMem and unequal - return _alias==0 ? that : (that._alias==0 ? this : BOT); + if( this==TOP ) return that; + if( that==TOP ) return this; + if( this==BOT ) return BOT; + if( that==BOT ) return BOT; + int alias = _alias==that._alias ? _alias : -1; + Type mt = _t.meet(that._t); + return make(alias,mt); } @Override public Type dual() { if( _alias== 0 ) return BOT; if( _alias==-1 ) return TOP; - return this; + return make(_alias,_t.dual()); } @Override - public Type glb() { return make(_alias); } + public Type glb() { return make(_alias,_t.glb()); } @Override - int hash() { return 9876543 + _alias; } + int hash() { return 9876543 + _alias + _t.hashCode(); } @Override boolean eq(Type t) { TypeMem that = (TypeMem) t; // Invariant - return _alias == that._alias; + return _alias == that._alias && _t == that._t; } @Override public StringBuilder print(StringBuilder sb) { - return sb.append("MEM#").append( switch(_alias) { - case 0 -> "TOP"; - case -1 -> "BOT"; - default -> ""+_alias; - }); + sb.append("MEM#"); + if( _alias== 0 ) return sb.append("TOP"); + if( _alias==-1 ) return sb.append("BOT"); + return _t.print(sb.append(_alias).append(":")); } @Override public String str() { return toString(); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 06fe2963..8b484235 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -6,8 +6,8 @@ import java.util.ArrayList; * Represents a Pointer to memory. * * Null is generic pointer to non-existent memory. - * *void is a non-Null pointer to all possible structs. - * Pointers can be to specific struct types, or a union with Null. + * *void is a non-Null pointer to all possible refs, both structs and arrays. + * Pointers can be to specific struct and array types, or a union with Null. * The distinguished *$BOT ptr represents union of *void and Null. * The distinguished *$TOP ptr represents the dual of *$BOT. */ @@ -33,12 +33,16 @@ 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 make_from(TypeStruct obj) { return make(obj, _nil); } + public TypeMemPtr makeFrom(TypeStruct obj) { return make(obj, _nil); } + // An abstract pointer, pointing to either a Struct or an Array. + // Can also be null or not. public static TypeMemPtr BOT = make(TypeStruct.BOT,true); public static TypeMemPtr TOP = BOT.dual(); + // An abstract null (can be Struct or Array) or not-null C void* public static TypeMemPtr NULLPTR = make(TypeStruct.TOP,true); public static TypeMemPtr VOIDPTR = NULLPTR.dual(); // A bottom mix of not-null ptrs, like C's void* but not null + public static TypeMemPtr TEST= make(TypeStruct.TEST,false); public static void gather(ArrayList<Type> ts) { ts.add(NULLPTR); ts.add(BOT); ts.add(TEST); } @@ -52,11 +56,14 @@ public class TypeMemPtr extends Type { public TypeMemPtr dual() { return TypeMemPtr.make(_obj.dual(), !_nil); } @Override - public Type glb() { return make(_obj.glb(),true); } + public TypeMemPtr glb() { return make(_obj.glb(),true); } @Override public TypeMemPtr makeInit() { return NULLPTR; } + @Override public Type nonZero() { return VOIDPTR; } @Override public boolean isHigh() { return this==TOP; } + @Override public int log_size() { return 2; } // (1<<2)==4-byte pointers + @Override int hash() { return _obj.hashCode() ^ (_nil ? 1024 : 0); } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index e2489d6f..abfb8a67 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -9,39 +9,52 @@ import java.util.ArrayList; public class TypeStruct extends Type { // A Struct has a name and a set of fields; the fields themselves have - // names and types. Briefly during parsing its allowed to have a - // forward-ref to a Struct; in this case the _fields array is null. + // names, types and aliases. The name has no semantic meaning, but is + // useful for debugging. Briefly during parsing a Struct can be a + // forward-ref; in this case the _fields array is null. + // Its illegal to attempt to load a field from a forward-ref struct. + + // Example: "int rez = new S.x; struct S { int x; } return rez;" // Error, S not defined + // Rewrite: "struct S { int x; } int rez = new S.x; return rez;" // Ok, no forward ref // // During the normal optimization run, struct types "bottom out" at further - // struct references, so we don't have to handle e.g. cyclic types. The + // struct references, so we don't have to handle e.g. cyclic types. The // "bottom out" is again the forward-ref struct. public final String _name; public final Field[] _fields; - private TypeStruct(String name, Field[] fields) { - super(Type.TSTRUCT); + TypeStruct(String name, Field[] fields) { + super(TSTRUCT); _name = name; _fields = fields; } - // Forward-ref version - public static TypeStruct make(String name) { return new TypeStruct(name, null).intern(); } // All fields directly listed - public static TypeStruct make(String name, Field[] fields) { return new TypeStruct(name, fields).intern(); } - // Parser uses an ArrayList to gather the fields - public static TypeStruct make(String name, ArrayList<Field> fields) { return make(name,fields.toArray(new Field[fields.size()])); } - - public static final TypeStruct TOP = make("$TOP",new Field [0]); - public static final TypeStruct BOT = make("$BOT",new Field [0]); + public static TypeStruct make(String name, Field... fields) { return new TypeStruct(name, fields).intern(); } + public static final TypeStruct TOP = make("$TOP",new Field[0]); + 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); } + + // 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("#" , lenAlias,len ), + Field.make("[]",bodyAlias,body)); + } // 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), Field.make("s2",TypeMemPtr.make(S2F,false)) }); - private static final TypeStruct S2 = make("S2", new Field[]{ Field.make("b", TypeFloat .BOT), Field.make("s1",TypeMemPtr.make(S1F,false)) }); - public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); } + public static final TypeStruct S1 = make("S1", new Field[]{ Field.make("a", -1, TypeInteger.BOT), Field.make("s2",-2,TypeMemPtr.make(S2F,false)) }); + private static final TypeStruct S2 = make("S2", new Field[]{ Field.make("b", -3, TypeFloat .BOT), Field.make("s1",-4,TypeMemPtr.make(S1F,false)) }); + + private static final TypeStruct ARY = makeAry(TypeInteger.BOT,-1,TypeFloat.BOT,-2); + + public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); ts.add(ARY); } public int find(String fname) { for( int i=0; i<_fields.length; i++ ) @@ -68,11 +81,15 @@ public class TypeStruct extends Type { return BOT; // It's a struct; that's about all we know if( this._fields==null ) return this; if( that._fields==null ) return that; - // Now all fields should be the same, so just do field meets - assert _fields.length == that._fields.length; + if( _fields.length != that._fields.length ) return BOT; + // Just do field meets Field[] flds = new Field[_fields.length]; - for( int i=0; i<_fields.length; i++ ) - flds[i] = (Field)_fields[i].meet(that._fields[i]); + for( int i=0; i<_fields.length; i++ ) { + Field f0 = _fields[i], f1 = that._fields[i]; + if( !f0._fname.equals(f1._fname) || f0._alias != f1._alias ) + return BOT; + flds[i] = (Field)f0.meet(f1); + } return make(_name,flds); } @@ -111,6 +128,7 @@ public class TypeStruct extends Type { if( !_name.equals(ts._name) ) return false; if( _fields == ts._fields ) return true; + if( _fields==null || ts._fields==null ) return false; if( _fields.length!=ts._fields.length ) return false; for( int i = 0; i < _fields.length; i++ ) @@ -141,4 +159,52 @@ public class TypeStruct extends Type { } @Override public String str() { return _name; } + + + public boolean isAry() { return _fields.length==2 && _fields[1]._fname.equals("[]"); } + + public int aryBase() { + assert isAry(); + if( _offs==null ) _offs = offsets(); + return _offs[1]; + } + public int aryScale() { + assert isAry(); + return _fields[1]._type.log_size(); + } + + + // Field offsets as packed byte offsets + private int[] _offs; // Lazily computed and not part of the type semantics + public int offset(int idx) { + if( _offs==null ) _offs = offsets(); + return _offs[idx]; + } + private int[] offsets() { // Field byte offsets + // Compute a layout for a collection of fields + assert _fields != null; // No forward refs + // Compute a layout + int[] cnts = new int[4]; // Count of fields at log field size + for( Field f : _fields ) + cnts[f._type.log_size()]++; // Log size is 0(byte), 1(i16/u16), 2(i32/f32), 3(i64/dbl) + int off = 0, idx = 0; // Base common struct fields go here, e.g. Mark/Klass + // Compute offsets to the start of each power-of-2 aligned fields. + int[] offs = new int[4]; + for( int i=3; i>=0; i-- ) { + offs[i] = off; + off += cnts[i]<<i; + } + // Assign offsets to all fields. + // Really a hidden radix sort. + _offs = new int[_fields.length+1]; + for( Field f : _fields ) { + int log = f._type.log_size(); + _offs[idx++] = offs[log]; // Field offset + offs[log] += 1<<log; // Next field offset at same alignment + cnts[log]--; // Count down, should be all zero at end + } + _offs[_fields.length] = (off+7)& ~7; // Round out to max alignment + return _offs; + } + } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 783f3f60..59ddf34b 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -46,7 +46,14 @@ public class TypeTuple extends Type { return sb; } - @Override public String str() { return print(new StringBuilder()).toString(); } + @Override public String str() { + StringBuilder sb = new StringBuilder(); + sb.append("[ "); + for( Type t : _types ) + sb.append(t.str()).append(", "); + sb.setLength(sb.length()-2); + return sb.append("]").toString(); + } /** * Display Type name in a format that's good for IR printer diff --git a/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/src/test/java/com/seaofnodes/simple/BrainFuckTest.java new file mode 100644 index 00000000..f7c66bda --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/BrainFuckTest.java @@ -0,0 +1,81 @@ +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 java.nio.charset.StandardCharsets; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class BrainFuckTest { + + @Ignore + @Test + public void testBrainfuck() { + var program = "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.".getBytes(StandardCharsets.UTF_8); + 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(";"); + } + + Parser parser = new Parser( + encoded + """ +int pc = 0; +int d = 0; +u8[] data = new u8[100]; +u8[] output = new u8[0]; + +while (pc < program#) { + int command = program[pc]; + if (command == 62) { + d = d + 1; + } else if (command == 60) { + d = d - 1; + } else if (command == 43) { + data[d] = data[d] + 1; + } else if (command == 45) { + data[d] = data[d] - 1; + } else if (command == 46) { + u8[] old = output; + output = new u8[output# + 1]; + int i = 0; + while (i < old#) { + output[i] = old[i]; + i = i + 1; + } + output[i] = data[d]; + } 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; + } + } + } 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; + } + } + } + pc = pc + 1; +} +return output; + """); + StopNode stop = parser.parse(false).iterate(false); + assertEquals("Hello World!\n", Evaluator.evaluate(stop, 0, 10000).toString()); + } +} diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 99ce8fa5..ae37a867 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(Region34,42,5);", stop.toString()); + assertEquals("return Phi(Region39,42,5);", stop.toString()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java index fb324fd9..def9aaa6 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -64,8 +64,8 @@ else v.y = 3; return v; """); - StopNode stop = parser.parse().iterate(); - assertEquals("return new Vector2D;", stop.toString()); + StopNode stop = parser.parse(false).iterate(); + assertEquals("return Vector2D;", stop.toString()); } @Test @@ -103,7 +103,7 @@ while (arg) { return bar.a; """); StopNode stop = parser.parse(false).iterate(); - assertEquals("return Phi(Loop12,0,(Phi_a+2));", stop.toString()); + assertEquals("return Phi(Loop13,0,(Phi_a+2));", stop.toString()); } @Test @@ -155,7 +155,7 @@ if( bar ) bar.a = 1; return bar; """); StopNode stop = parser.parse(false).iterate(); - assertEquals("return Phi(Region31,(*void)Phi(Region19,null,new Bar),null);", stop.toString()); + assertEquals("return Phi(Region33,(*void)Phi(Region20,null,Bar),null);", stop.toString()); } @Test @@ -171,7 +171,7 @@ else bar.a = 1; return rez; """); StopNode stop = parser.parse(false).iterate(); - assertEquals("return Phi(Region37,4,3);", stop.toString()); + assertEquals("return Phi(Region39,4,3);", stop.toString()); } @Test @@ -225,7 +225,7 @@ while( i.x < i.len ) { return sum; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop17,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); + assertEquals("return Phi(Loop18,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); } @@ -246,7 +246,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,new s0,Phi(Region34,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop13,s0,Phi(Region37,s0,Phi_ret));", stop.toString()); } @Test @@ -264,7 +264,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop15,new s0,Phi(Region35,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop17,s0,Phi(Region38,s0,Phi_ret));", stop.toString()); } @@ -281,7 +281,7 @@ while(arg < 10) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,new s0,Phi(Region33,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop13,s0,Phi(Region35,s0,Phi_ret));", stop.toString()); } @Test @@ -325,7 +325,7 @@ else return new s0; if(new s0.f0) return 0; """); StopNode stop = parser.parse().iterate(); - assertEquals("return new s0;", stop.toString()); + assertEquals("return s0;", stop.toString()); } @Test @@ -353,7 +353,7 @@ s0 v1 = v0; return v1; """); StopNode stop = parser.parse().iterate(); - assertEquals("return new s0;", stop.toString()); + assertEquals("return s0;", stop.toString()); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 63cd511a..5f9f9cac 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -291,7 +291,7 @@ else { } } """); - StopNode stop = parser.parse().iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("Stop[ return 9; return 0; return 0; return 0; ]", stop.toString()); } @@ -346,7 +346,9 @@ if (arg) v.f=1; return i; """); StopNode stop = parser.parse().iterate(); - assertEquals("return .f;", stop.toString()); + assertEquals("return 2;", stop.toString()); + assertEquals(2L, Evaluator.evaluate(stop, 0)); + assertEquals(2L, Evaluator.evaluate(stop, 1)); } @Test @@ -355,6 +357,7 @@ return i; """ struct S { int f; } S v = new S; +v.f = arg; S t = new S; int i = 0; if (arg) { @@ -366,7 +369,7 @@ if (arg) { return i; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region34,.f,0);", stop.toString()); + assertEquals("return Phi(Region40,.f,0);", stop.toString()); } @Test @@ -385,7 +388,7 @@ if (v1) { return v0; """); StopNode stop = parser.parse().iterate(); - assertEquals("return new S;", stop.toString()); + assertEquals("return S;", stop.toString()); } @@ -395,6 +398,7 @@ return v0; """ struct S { int f; } S v = new S; +v.f = arg; S t = new S; int i = v.f; if (arg+1) arg= 0; @@ -402,7 +406,7 @@ while (arg) v.f = 2; return i; """); StopNode stop = parser.parse().iterate(); - assertEquals("return .f;", stop.toString()); + assertEquals("return arg;", stop.toString()); } @Test @@ -419,7 +423,7 @@ while(1) { return v; """); StopNode stop = parser.parse().iterate(); - assertEquals("return new S;", stop.toString()); + assertEquals("return S;", stop.toString()); } @Test @@ -451,8 +455,8 @@ while (arg) { } return i; """); - StopNode stop = parser.parse().iterate(false); - assertEquals("return .f;", stop.toString()); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); } @Test @@ -471,8 +475,8 @@ while(arg) { } return arg; """); - StopNode stop = parser.parse().iterate(false); - assertEquals("return Phi(Loop15,arg,Phi(Region37,.f,0));", stop.toString()); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Loop17,arg,Phi(Region42,.f,0));", stop.toString()); } @Test @@ -489,8 +493,8 @@ if (arg) { } return v; """); - StopNode stop = parser.parse().iterate(false); - assertEquals("return new S;", stop.toString()); + StopNode stop = parser.parse().iterate(); + assertEquals("return S;", stop.toString()); } @Test @@ -511,21 +515,4 @@ return v; StopNode stop = parser.parse().iterate(); //assertEquals("return new S;", stop.toString()); } - - @Test - public void testSplit() { - Parser parser = new Parser( - """ -struct S { int f; } -S s = new S; -if( arg==0 ) s.f = 1; -else if (arg == 1) s.f = 1; -return s.f; -"""); - StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region37,1,Phi(Region35,1,0));", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); - assertEquals(1L, Evaluator.evaluate(stop, 1)); - assertEquals(0L, Evaluator.evaluate(stop, 2)); - } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java index 972118be..2a637ce6 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -14,7 +14,7 @@ public class Chapter12Test { """ return 3.14; """); - StopNode stop = parser.parse().iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return 3.14;", stop.toString()); assertEquals(3.14, Evaluator.evaluate(stop, 0)); } @@ -25,7 +25,7 @@ return 3.14; """ return 3.14; """); - StopNode stop = parser.parse().iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return 3.14;", stop.toString()); assertEquals(3.14, Evaluator.evaluate(stop, 0)); } @@ -42,7 +42,7 @@ while( 1 ) { } return guess; """); - StopNode stop = parser.parse().iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop9,(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)); @@ -55,7 +55,7 @@ return guess; flt x = arg; return x+1==x; """); - StopNode stop = parser.parse().iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return ((flt)arg==(ToFloat+1.0));", stop.toString()); assertEquals(0L, Evaluator.evaluate(stop, 1)); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 0edb2d51..416aba31 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -14,7 +14,7 @@ public class Chapter13Test { """ return 3.14; """); - StopNode stop = parser.parse().iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return 3.14;", stop.toString()); assertEquals(3.14, Evaluator.evaluate(stop, 0)); } @@ -56,7 +56,7 @@ LLI? next = head.next; if( next==null ) return 1; return next.i; """); - StopNode stop = parser.parse().iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("Stop[ return 0; return 1; return .i; ]", stop.toString()); assertEquals(2L, Evaluator.evaluate(stop, 3)); } @@ -75,7 +75,7 @@ i0.f = f0; f0.i = i0; return f0.i.f.i.i; """); - StopNode stop = parser.parse().iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return 17;", stop.toString()); } @@ -87,7 +87,7 @@ struct N { N next; int i; } N n = new N; return n.next; """); - StopNode stop = parser.parse().iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return null;", stop.toString()); } @@ -100,8 +100,8 @@ N n = new N; n.next = new N; return n.next; """); - StopNode stop = parser.parse().iterate(false); - assertEquals("return new N;", stop.toString()); + StopNode stop = parser.parse().iterate(); + assertEquals("return N;", stop.toString()); } @Test @@ -136,7 +136,7 @@ return n.i; """ struct S{}; """); - StopNode stop = parser.parse().iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return 0;", stop.toString()); assertEquals(0L, Evaluator.evaluate(stop, 0)); } @@ -160,8 +160,8 @@ struct S1 { S2? s; } struct S2 { int x; } return new S1.s=new S2; """); - StopNode stop = parser.parse().iterate(false); - assertEquals("return new S1;", stop.toString()); + StopNode stop = parser.parse().iterate(); + assertEquals("return S2;", stop.toString()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/src/test/java/com/seaofnodes/simple/Chapter14Test.java index fcb7fa24..048cb93a 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -15,7 +15,7 @@ public class Chapter14Test { """ return 3.14; """); - StopNode stop = parser.parse(false).iterate(); + StopNode stop = parser.parse().iterate(); assertEquals("return 3.14;", stop.toString()); assertEquals(3.14, Evaluator.evaluate(stop, 0)); } @@ -31,7 +31,7 @@ if( b < 0 ) c = -1; if( b > 2 ) c = 1; return c; """); - StopNode stop = parser.parse(false).iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return 99;", stop.toString()); assertEquals(99L, Evaluator.evaluate(stop, 0)); } @@ -44,7 +44,7 @@ u8 b = 123; b = b + 456;// Truncate return b; """); - StopNode stop = parser.parse(false).iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return 67;", stop.toString()); assertEquals(67L, Evaluator.evaluate(stop, 0)); } @@ -58,7 +58,7 @@ u8 b = 123; while( b ) b = b + 456;// Truncate return b; """); - StopNode stop = parser.parse(false).iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return Phi(Loop9,123,((Phi_b+456)&255));", stop.toString()); } @@ -71,7 +71,7 @@ b = b + 456;// Truncate u1 c = b; // No more truncate needed return c; """); - StopNode stop = parser.parse(false).iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return 1;", stop.toString()); assertEquals(1L, Evaluator.evaluate(stop, 0)); } @@ -84,7 +84,7 @@ int b = 123; b = b+456 & 31; // Precedence return b; """); - StopNode stop = parser.parse(false).iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return 3;", stop.toString()); assertEquals(3L, Evaluator.evaluate(stop, 0)); } @@ -98,7 +98,7 @@ Foo f = new Foo; f.b = 123; return f.b; """); - StopNode stop = parser.parse(false).iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return 1;", stop.toString()); assertEquals(1L, Evaluator.evaluate(stop, 0)); } @@ -110,7 +110,7 @@ return f.b; i8 b = 255; // Chopped return b; // Sign extend """); - StopNode stop = parser.parse(false).iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return -1;", stop.toString()); assertEquals(-1L, Evaluator.evaluate(stop, 0)); } @@ -123,9 +123,10 @@ i8 b = arg; b = b + 1;// Truncate return b; """); - StopNode stop = parser.parse(false).iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return (((((arg<<56)>>56)+1)<<56)>>56);", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); + assertEquals(1L, Evaluator.evaluate(stop, 0)); + assertEquals(-128L, Evaluator.evaluate(stop, 127)); } @Test @@ -136,47 +137,18 @@ u16 mask = (1<<16)-1; // AND mask int c = 123456789 & mask; return c; // """); - StopNode stop = parser.parse(false).iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return 52501;", stop.toString()); assertEquals(52501L, Evaluator.evaluate(stop, 0)); } @Test - public void testWrapMinus() { - Parser parser = new Parser( -""" -int MAX = 9223372036854775807; //0x7FFFFFFFFFFFFFFF; -int i = (arg&MAX) + -MAX + -1; // Basically (e0) + Long.MIN_VALUE -int j = -i; // Negating Long.MIN_VALUE wraps, cannot constant fold -if (arg) j = 1; -return j; -"""); - StopNode stop = parser.parse(false).iterate(); - assertEquals("return Phi(Region28,1,(-((arg&9223372036854775807)+-9223372036854775808)));", stop.toString()); - assertEquals(-9223372036854775808L, Evaluator.evaluate(stop, 0)); - assertEquals(1L, Evaluator.evaluate(stop, 1)); - } - - @Test - public void testWrapShr() { - Parser parser = new Parser( -""" -return (arg >>> 1)==0; -"""); - StopNode stop = parser.parse(false).iterate(); - assertEquals("return (!(arg>>>1));", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); - assertEquals(1L, Evaluator.evaluate(stop, 1)); - assertEquals(0L, Evaluator.evaluate(stop, 2)); - } - - @Test public void testOr() { Parser parser = new Parser( """ return (arg | 123 ^ 456) >>> 1; """); - StopNode stop = parser.parse(false).iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return (((arg|123)^456)>>>1);", stop.toString()); assertEquals(217L, Evaluator.evaluate(stop, 0)); } @@ -194,101 +166,6 @@ return arg; } @Test - public void testLoadBug() { - Parser parser = new Parser( -""" -struct A { int i; } -struct B { int i; } -A a = new A; -A t1 = new A; -B b = new B; -B t2 = new B; -int i; -if (arg) i = a.i; -else i = b.i; -return i; -"""); - StopNode stop = parser.parse(false).iterate(false); - assertEquals("return Phi(Region31,.i,.i);", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 0)); - } - - @Test - public void testBug2() { - Parser parser = new Parser( -""" -int z = 0; -while (1) { - int j; - if (arg&3) { - j = arg >> 2; - } else { - j = (arg >> 3)+z; - } - return j+1; -} -"""); - StopNode stop = parser.parse(false).iterate(false); - assertEquals("return ((arg>>Phi(Region32,2,3))+1);", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 0)); - assertEquals(1L, Evaluator.evaluate(stop, 1)); - assertEquals(2L, Evaluator.evaluate(stop, 7)); - assertEquals(2L, Evaluator.evaluate(stop, 8)); - } - - @Test - public void testBug3() { - Parser parser = new Parser( -""" -flt f = arg; -bool b; -if (arg&3) b = f == 1.0; -else b = f == 2.0; -if (arg&5) b = arg == 1; -return b; -"""); - StopNode stop = parser.parse(false).iterate(false); - assertEquals("return Phi(Region37,(arg==1),((flt)arg==Phi(Region23,1.0,2.0)));", stop.toString()); - assertEquals(1L, Evaluator.evaluate(stop, 1)); - assertEquals(0L, Evaluator.evaluate(stop, 2)); - assertEquals(0L, Evaluator.evaluate(stop, 3)); - } - - @Test - public void testBug4() { - Parser parser = new Parser( -""" -int i; -if (arg&7) i=3; -else i=2; -return (arg == i) == 1; -"""); - StopNode stop = parser.parse(false).iterate(); - assertEquals("return (arg==Phi(Region18,3,2));", stop.toString()); - assertEquals(0L, Evaluator.evaluate(stop, 0)); - assertEquals(0L, Evaluator.evaluate(stop, 1)); - assertEquals(0L, Evaluator.evaluate(stop, 2)); - assertEquals(1L, Evaluator.evaluate(stop, 3)); - } - - @Test - public void testBug5() { - Parser parser = new Parser( -""" -int d = -1; -while (1) { - int i = (arg & 7) + (9223372036854775807 - 7); - if (arg & 1) i = ((arg&3) + (9223372036854775807 - 3)) & d; - return i + -1; -} -"""); - StopNode stop = parser.parse(false).iterate(); - assertEquals("return (Phi(Region43,((arg&3)+9223372036854775804),((arg&7)+9223372036854775800))+-1);", stop.toString()); - assertEquals(0x7FFFFFFFFFFFFFF7L, Evaluator.evaluate(stop, 0)); - assertEquals(0x7FFFFFFFFFFFFFFCL, Evaluator.evaluate(stop, 1)); - } - - @Test public void testTypes() { Parser parser = new Parser( """ @@ -309,7 +186,7 @@ f32 ff32 = 3.141592653589793; if( ff32 != 3.1415927410125732) return 5; return 0; """); - StopNode stop = parser.parse().iterate(false); + StopNode stop = parser.parse().iterate(); assertEquals("return 0;", stop.toString()); assertEquals(0L, Evaluator.evaluate(stop, 0)); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/src/test/java/com/seaofnodes/simple/Chapter15Test.java new file mode 100644 index 00000000..6ec7cc1a --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -0,0 +1,351 @@ +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 java.nio.charset.StandardCharsets; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter15Test { + + @Test + public void testJig() { + Parser parser = new Parser(""" +return 3.14; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 3.14;", stop.toString()); + assertEquals(3.14, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testLifetime() { + Parser parser = new Parser(""" +u8[] b = new u8[5]; +if (arg) { + b[0] = b[0] + 1; +} else { + b[1] = b[1] * 2; +} +return b[0] + b[1]; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Region69,1,0);", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + assertEquals(1L, Evaluator.evaluate(stop, 1)); + } + + @Test + public void testCyclic() { + Parser parser = new Parser( +""" +struct C { + C? l; +} +C c = new C; +c.l = c; +return c; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return C;", stop.toString()); + assertEquals("Obj<C>@1{l=obj@1}", Evaluator.evaluate(stop, 0).toString()); + } + + @Test + public void testSafetyCheck() { + Parser parser = new Parser( +""" +u8[] old = new u8[0]; +u8[] output = new u8[1]; +int i = 0; +while (i < old#) { + output[i] = old[i]; + i = i + 1; +} +output[i] = 1; +return output; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return u8[];", stop.toString()); + assertEquals("\u0001", Evaluator.evaluate(stop, 0).toString()); + } + + @Test + public void testBasic1() { + Parser parser = new Parser( +""" +int[] is = new int[2]; +return is[1]; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testBasic2() { + Parser parser = new Parser( +""" +int[] is = new int[2]; +int[] is2 = new int[2]; +return is[1]; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testBasic3() { + Parser parser = new Parser( +""" +int[] a = new int[2]; +a[0] = 1; +a[1] = 2; +return a[0]; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 1;", stop.toString()); + assertEquals(1L, Evaluator.evaluate(stop, 0)); + } + + @Test + public void testBasic4() { + Parser parser = new Parser( +""" +struct A { int i; } +A?[] a = new A?[2]; +return a; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return *A?[];", stop.toString()); + assertEquals("Obj<*A?[]>{#=2,[]=[null,null]}", Evaluator.evaluate(stop, 0).toString()); + } + + @Test + public void testBasic5() { + Parser parser = new Parser( +""" +struct S { int x; flt y; } +// A new S +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]; +iss[0] = new S?[7]; +iss[0][2] = s; + +// Now pull out the filled-in value, with null checks +flt rez; +S?[]? is = iss[arg]; +if( !is ) rez = 1.2; +else { + S? i = is[2]; + if( !i ) rez = 2.3; + else rez = i.y; +} +return rez; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Region118,1.2,Phi(Region115,2.3,.y));", stop.toString()); + assertEquals(3.14, Evaluator.evaluate(stop, 0)); + } + + @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; + +// Double-d array of Ss. Fill in one row. +S?[]?[] iss = new S?[]?[2]; +iss[0] = new S?[7]; +iss[0][2] = s; + +// Now pull out the filled-in value, with null checks +flt rez = 1.2; +if( iss[arg] ) + if( iss[arg][2] ) + 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)); + } + + @Test + public void testTree() { + Parser parser = new Parser( +""" +// Can we define a forward-reference array? +struct Tree { Tree?[] _kids; } +Tree root = new Tree; +root._kids = new Tree?[2]; +root._kids[0] = new Tree; +return root; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return Tree;", stop.toString()); + assertEquals("Obj<Tree>{_kids=Obj<*Tree?[]>{#=2,[]=[Obj<Tree>{_kids=null},null]}}", Evaluator.evaluate(stop, 0).toString()); + } + + @Test + public void testNestedStructAddMemProj() { + Parser parser = new Parser( +""" +struct S { + int a; + int[] b; +} +return 0; +"""); + StopNode stop = parser.parse(); + assertEquals("return 0;", stop.toString()); + } + + @Test + public void testRollingSum() { + Parser parser = new Parser( +""" +int[] ary = new int[arg]; +// Fill [0,1,2,3,4,...] +int i=0; +while( i < ary# ) { + ary[i] = i; + i = i+1; +} +// Fill [0,1,3,6,10,...] +i=0; +while( i < ary# - 1 ) { + ary[i+1] = ary[i+1] + ary[i]; + i = i+1; +} +return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return (.[]+(.[]*1000));", stop.toString()); + assertEquals(1006L, Evaluator.evaluate(stop, 4)); + } + + @Test + 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; + // Mark out the rest non-primes + int i = j + j; + while( i < ary# ) { + ary[i] = 1; + i = i + j; + } + j = j + 1; +} +// Now just collect the remaining primes +while( j < arg ) { + if( ary[j] == 0 ) { + primes[nprimes] = j; nprimes = nprimes + 1; + } + j = j + 1; +} +// Shrink the result array to size +int[] rez = new int[nprimes]; +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[] {\n # :int;\n [] :int;\n}",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]); + } + + @Test + public void testNewNodeInit() { + Parser parser = new Parser( +""" +struct S {int i; flt f;} +S s1 = new S; +S s2 = new S; +s2.i = 3; +s2.f = 2.0; +if (arg) s1 = new S; +return s1.i + s1.f; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return ((flt).i+.f);", stop.toString()); + assertEquals(0.0, Evaluator.evaluate(stop, 0)); + } + + + @Test + public void testBad0() { + Parser parser = new Parser( +""" +return new flt; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot allocate a flt",e.getMessage()); } + } + + @Test + public void testBad1() { + Parser parser = new Parser( +""" +int is = new int[2]; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Type *int[] is not of declared type int",e.getMessage()); } + } + + @Test + public void testBad2() { + Parser parser = new Parser( +""" +int[] is = new int[3.14]; +return is[1]; +"""); + try { parser.parse().iterate(); fail(); } + catch( Exception e ) { assertEquals("Cannot allocate an array with length 3.14",e.getMessage()); } + } + + @Test + public void testBad3() { + Parser parser = new Parser( +""" +int[] is = new int[arg]; +return is[1]; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 0;", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 4)); + try { Evaluator.evaluate(stop,0); } + catch( ArrayIndexOutOfBoundsException e ) { assertEquals("Array index 1 out of bounds for array length 0",e.getMessage()); } + try { Evaluator.evaluate(stop,-1); } + catch( NegativeArraySizeException e ) { assertEquals("-1",e.getMessage()); } + } + +} diff --git a/src/test/java/com/seaofnodes/simple/TypeTest.java b/src/test/java/com/seaofnodes/simple/TypeTest.java index 9e8a1418..cb45a0d7 100644 --- a/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -13,32 +13,32 @@ public class TypeTest { @Test public void testTypeAdHoc() { TypeStruct s1 = TypeStruct.make("s1", new Field[]{ - Field.make("a", TypeInteger.BOT), - Field.make("b", TypeInteger.BOT) }); + Field.make("a",-1, TypeInteger.BOT), + Field.make("b",-2, TypeInteger.BOT) }); TypeStruct s2 = TypeStruct.make("s2", new Field[]{ - Field.make("a", TypeInteger.BOT), - Field.make("b", TypeInteger.BOT) }); + Field.make("a",-3, TypeInteger.BOT), + Field.make("b",-4, TypeInteger.BOT) }); Assert.assertEquals(s1, s1.glb()); Assert.assertNotEquals(s1, s1.dual()); Assert.assertEquals(s1, s1.dual().glb()); - TypeMem m1 = TypeMem.make(1); - TypeMem m2 = TypeMem.make(2); - TypeMem m3 = TypeMem.make(3); - TypeMem m4 = TypeMem.make(4); + TypeMem m1 = TypeMem.make(1,TypeInteger.ZERO); + TypeMem m2 = TypeMem.make(2,TypeInteger.U16); + TypeMem m3 = TypeMem.make(3,TypeFloat.BOT); + TypeMem m4 = TypeMem.make(4,TypeInteger.BOT); Assert.assertNotEquals(m1, m2); Assert.assertNotEquals(m2, m3); Assert.assertNotEquals(m3, m4); Assert.assertEquals(TypeStruct.BOT, s1.meet(s2)); - Assert.assertEquals(TypeMem .BOT, m1.meet(m2)); + Assert.assertEquals(TypeMem.make(-1,TypeInteger.U16), m1.meet(m2)); Assert.assertEquals(TypeMem .BOT, m2.meet(m3)); Assert.assertEquals(TypeMem .BOT, m3.meet(m4)); - Assert.assertEquals(m1, m1.glb()); - Assert.assertEquals(TypeMem.make(1), m1.dual()); - Assert.assertEquals(m1.dual(), m1.glb().dual()); + Assert.assertEquals(TypeMem.make(1,TypeInteger.BOT), m1.glb()); + Assert.assertEquals(TypeMem.make(1,TypeInteger.ZERO), m1.dual()); + Assert.assertEquals(m4.dual(), m4.glb().dual()); TypeMemPtr ptr1 = TypeMemPtr.make(s1); Assert.assertEquals(s1, ptr1._obj); @@ -58,12 +58,12 @@ public class TypeTest { Assert.assertEquals(ptr1, ptr1.dual().dual()); Assert.assertEquals(ptr1.glb(), ptr1.dual().glb()); - Assert.assertEquals(TypeMemPtr.BOT, ptr1.meet(ptr2nil)); + Assert.assertEquals(TypeMemPtr.make(TypeStruct.BOT,true), ptr1.meet(ptr2nil)); Assert.assertEquals(ptr1.glb(), ptr1.meet(TypeMemPtr.NULLPTR)); TypeMemPtr TOP = TypeMemPtr.TOP; - TypeMemPtr BOT = TypeMemPtr.BOT; - TypeMemPtr PTR = TypeMemPtr.VOIDPTR; + TypeMemPtr BOT = TypeMemPtr.make(TypeStruct.BOT,true ); + TypeMemPtr PTR = TypeMemPtr.make(TypeStruct.BOT,false); TypeMemPtr NULL = TypeMemPtr.NULLPTR; Type PTR_meet_NULL = NULL.meet(PTR); Assert.assertEquals(BOT, PTR_meet_NULL); diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 31a14c05..34921b94 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -6,27 +6,119 @@ import com.seaofnodes.simple.type.*; import java.lang.invoke.MethodHandle; import java.lang.invoke.MethodHandles; -import java.util.ArrayList; -import java.util.BitSet; -import java.util.Objects; +import java.util.*; public class Evaluator { private static final Object MEMORY = new Object(); public record Obj(TypeStruct struct, Object[] fields) { + private void init(IdentityHashMap<Obj, Integer> objs) { + var oid = objs.get(this); + if (oid != null) { + if (oid != 0) objs.put(this, 0); + return; + } + objs.put(this, -1); + for (var obj : fields) { + if (obj instanceof Obj o) o.init(objs); + } + } + private static int p(StringBuilder sb, IdentityHashMap<Obj, Integer> objs, int id, String indentation, String step, String sep, Object obj) { + if (obj instanceof Obj o) return o.p(sb, objs, id, indentation, step, sep); + sb.append(obj); + return id; + } + private int p(StringBuilder sb, IdentityHashMap<Obj, Integer> objs, int id, String indentation, String step, String sep) { + var cid = objs.get(this); + assert cid != null; + if (cid > 0) { + sb.append("obj@").append(cid); + return id; + } + if (struct._name.equals("u8[]")) { + sb.append('"'); + for (int i=struct._fields.length-1; i<fields.length; i++) { + var v = fields[i]; + if (v == null) v = 0; + assert v instanceof Number; + var n = ((Number)v).byteValue() & 0xFF; + if (n >= 0x20 && n < 0x80) { + if (n == 0x22 || n == 0x5C) sb.append("\\"); + sb.append((char)n); + } else { + sb.append("\\x").append("0123456789abcdef".charAt(n >> 4)).append("0123456789abcdef".charAt(n & 0xF)); + } + } + sb.append('"'); + return id; + } + sb.append("Obj<").append(struct._name).append(">"); + if (cid == 0) { + cid = id++; + objs.put(this, cid); + sb.append("@").append(cid); + } + sb.append("{"); + if (struct._fields.length == 0) { + assert !struct.isAry(); + sb.append("}"); + return id; + } + String nextIndent = indentation + step; + int e = struct._fields.length - 1; + for(int i=0; i<e; i++) { + sb.append(nextIndent).append(struct._fields[i]._fname).append("="); + id = p(sb, objs, id, nextIndent, step, sep, fields[i]); + sb.append(sep); + } + sb.append(nextIndent).append(struct._fields[e]._fname).append("="); + if (struct.isAry()) { + sb.append("["); + if (fields.length > e) { + String innerIndent = nextIndent + step; + sb.append(innerIndent); + id = p(sb, objs, id, nextIndent, step, sep, fields[e]); + for (int i = e+1; i < fields.length; i++) { + sb.append(sep).append(innerIndent); + id = p(sb, objs, id, nextIndent, step, sep, fields[i]); + } + sb.append(nextIndent); + } + sb.append("]"); + } else { + id = p(sb, objs, id, nextIndent, step, sep, fields[e]); + } + sb.append(indentation).append("}"); + return id; + } + private StringBuilder p(StringBuilder sb, String indentation, String step, String sep) { + var objs = new IdentityHashMap<Obj, Integer>(); + init(objs); + p(sb, objs, 1, indentation, step, sep); + return sb; + } @Override public String toString() { - var sb = new StringBuilder(); - sb.append("Obj<").append(struct._name).append("> {"); - for(int i=0; i<struct._fields.length; i++) { - sb.append("\n ").append(struct._fields[i]._fname).append("=").append(fields[i]); + if (struct._name.equals("u8[]")) { + var sb = new StringBuilder(); + for (int i=struct._fields.length-1; i<fields.length; i++) { + var v = fields[i]; + if (v == null) v = 0; + assert v instanceof Number; + var n = ((Number)v).byteValue() & 0xFF; + sb.append((char)n); + } + return sb.toString(); } - return sb.append("\n}").toString(); + return p(new StringBuilder(), "", "", ",").toString(); + } + public String pretty() { + return p(new StringBuilder(), "\n", " ", "").toString(); } } - private static int getFieldIndex(TypeStruct struct, MemOpNode memop) { + private static int getFieldIndex(TypeStruct struct, MemOpNode memop, long off) { int idx = struct.find(memop._name); if( idx >= 0 ) return idx; throw new AssertionError("Field "+memop._name+" not found in struct " + struct._name); @@ -82,22 +174,82 @@ public class Evaluator { return in2 == 0 ? 0 : vald(div.in(1)) / in2; } + private static long offToIdx(long off, TypeStruct t) { + off -= t.aryBase(); + int scale = t.aryScale(); + long mask = (1L << scale)-1; + assert (off & mask) == 0; + return off>>scale; + } + private Object alloc(NewNode alloc) { - var type = ((TypeMemPtr)alloc.compute())._obj; - return new Obj(type, new Object[type._fields.length]); + TypeStruct type = alloc._ptr._obj; + Object[] body=null; + int num; + if( type.isAry() ) { + long sz = (Long)val(alloc.in(1)); + long n = offToIdx(sz, type); + if( n < 0 ) + throw new NegativeArraySizeException(""+n); + body = new Object[(int)n+1]; // Array body + var c = type._fields[type._fields.length-1]._type; + if (c instanceof TypeInteger) { + for (int i=0; i<n; i++) body[i+type._fields.length-1] = 0L; + } else if (c instanceof TypeFloat) { + for (int i = 0; i < n; i++) body[i+type._fields.length-1] = 0D; + } else { + assert c instanceof TypeMemPtr; + } + num = type._fields.length-1; + } else { + body = new Object[type._fields.length]; + num = type._fields.length; + } + for (int i=0; i<num; i++) { + var c = type._fields[i]._type; + if (c instanceof TypeInteger) { + body[i] = 0L; + } else if (c instanceof TypeFloat) { + body[i] = 0D; + } else { + assert c instanceof TypeMemPtr; + } + } + Object[] mems = new Object[type._fields.length+2]; + // mems[0] is control + mems[1] = new Obj(type,body); // the ref + // mems[2+...] are memory aliases + return mems; } private Object load(LoadNode load) { - var from = (Obj)val(load.in(2)); - var idx = getFieldIndex(from.struct, load); - return from.fields[idx]; + var from = (Obj)val(load.ptr()); + var off = vall(load.off()); + var idx = getFieldIndex(from.struct, load, (Long)off); + if( idx==from.struct._fields.length-1 && from.struct.isAry() ) { + long len = from.fields.length - from.struct._fields.length + 1; + long i = offToIdx(off, from.struct); + if( i < 0 || i >= len ) + throw new ArrayIndexOutOfBoundsException("Array index out of bounds " + i + " < " + len); + return from.fields[(int)i+from.struct._fields.length-1]; + + } else + return from.fields[idx]; } private Object store(StoreNode store) { - var to = (Obj)val(store.in(2)); - var val = val(store.in(3)); - var idx = getFieldIndex(to.struct, store); - to.fields[idx] = val; + var to = (Obj)val(store.ptr()); + var off = vall(store.off()); + var val = val(store.val()); + var idx = getFieldIndex(to.struct, store, (Long)off); + if( idx==to.struct._fields.length-1 && to.struct.isAry() ) { + long len = to.fields.length - to.struct._fields.length + 1; + long i = offToIdx(off, to.struct); + if( i < 0 || i >= len ) + throw new RuntimeException("Array index out of bounds " + off + " <= " + len); + to.fields[(int)i+to.struct._fields.length-1] = val; + } else + to.fields[idx] = val; return null; } diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index 8b86d67a..59c15d3f 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -155,7 +155,10 @@ public class Scheduler { * @return true if all placed inputs are before this node. */ private boolean isValid(NodeData data) { - return data.node._inputs.stream().map(i->i==null?null:d(i)).map(d->d==null||d.users>0?null:d.block).allMatch(d->d==null||dom(d, data.block)==d); + return data.node._inputs.stream() + .map(i->i==null?null:d(i)) + .map(d->d==null||d.users>0?null:d.block) + .allMatch(d->d==null||dom(d, data.block)==d); } /** @@ -204,7 +207,7 @@ public class Scheduler { * @return true if node is placed during the control flow graph build. */ private static boolean isPinnedNode(NodeData data) { - return data.node.isCFG() || data.node instanceof PhiNode; + return data.node instanceof CFGNode || data.node instanceof PhiNode; } /** @@ -359,7 +362,7 @@ public class Scheduler { while (!queue.isEmpty()) { var data = queue.pop(); var node = data.node; - assert node.isCFG(); + assert node instanceof CFGNode; BasicBlock block; switch (node) { case StartNode s: @@ -399,7 +402,9 @@ public class Scheduler { } } if (!(node instanceof ReturnNode)) - for (Node n:node._outputs) if (n!=null && n.isCFG() && isCFGNodeReady(n) && d(n).block == null) queue.push(d(n)); + for (Node n : node._outputs) + if(n instanceof CFGNode && isCFGNodeReady(n) && d(n).block == null) + queue.push(d(n)); var b = block; for(var in:data.node._inputs) od(in).ifPresent(d->update(d, b)); } @@ -421,7 +426,7 @@ public class Scheduler { if (nd.users>0) nd.users++; return; } - assert node.isCFG() == cfg; + assert node instanceof CFGNode == cfg; assert isNotXCtrl(node); nd = new NodeData(node); if (cfg) nd.users=0; @@ -443,24 +448,24 @@ public class Scheduler { while (!cfgQueue.isEmpty()) { var data = cfgQueue.pop(); node = data.node; - assert node.isCFG(); + assert node instanceof CFGNode; if (!(node instanceof ReturnNode)) { - for (var out : node._outputs) if (out!=null && out.isCFG() && isNotXCtrl(out)) markAlive(cfgQueue, out, true); + for (var out : node._outputs) if (out!=null && out instanceof CFGNode && isNotXCtrl(out)) markAlive(cfgQueue, out, true); } - for (var in : node._inputs) if(in!=null && !in.isCFG() && isNotXCtrl(in)) markAlive(dataQueue, in, false); + for (var in : node._inputs) if(in!=null && !(in instanceof CFGNode) && isNotXCtrl(in)) markAlive(dataQueue, in, false); } // Mark all other nodes. while (!dataQueue.isEmpty()) { var data = dataQueue.pop(); node = data.node; - assert !node.isCFG(); + assert !(node instanceof CFGNode); if (node instanceof PhiNode phi) { var r = phi.in(0); for (int i=1; i<phi.nIns(); i++) { if (od(r.in(i)).isPresent()) markAlive(dataQueue, phi.in(i), false); } } else { - for (var in : node._inputs) if (in != null && !in.isCFG()) markAlive(dataQueue, in, false); + for (var in : node._inputs) if (in != null && !(in instanceof CFGNode)) markAlive(dataQueue, in, false); } if (node instanceof StoreNode) mem.push(data); } @@ -501,8 +506,8 @@ public class Scheduler { for(var n:node._outputs) if (n instanceof CProjNode p && p._idx==0) return p; return null; } - assert node._outputs.stream().filter(Node::isCFG).limit(2).count()<=1; - for(var n:node._outputs) if(n.isCFG()) return n; + assert node._outputs.stream().filter(x -> x instanceof CFGNode).limit(2).count()<=1; + for(var n:node._outputs) if(n instanceof CFGNode) return n; return null; } @@ -546,7 +551,7 @@ public class Scheduler { } if (last instanceof ReturnNode) break; if (last instanceof IfNode if_) { - for(var out:if_._outputs) if (out.isCFG() && blocks.get(out) == null) queue.push(d(out)); + for(var out:if_._outputs) if (out instanceof CFGNode && blocks.get(out) == null) queue.push(d(out)); break; } data = d(last); diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index ec6e7816..7cd854bf 100644 --- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -25,7 +25,7 @@ public class ScriptGenerator { private static final int MAX_BLOCK_DEPTH = 4; private static final int MAX_EXPRESSION_DEPTH = 10; private static final int MAX_SUFFIX_RECURSIVE_DEPTH = 10; - + /** * Number of spaces per indentation */ @@ -109,8 +109,8 @@ public class ScriptGenerator { static { new Parser("", TypeInteger.BOT); - for(var e:Parser.TYPES.entrySet()) { - if (e.getValue() instanceof TypeInteger) { + for( var e : Parser.TYPES.entrySet() ) { + if( e.getValue() instanceof TypeInteger ) { INTTYPES.add(new TypeInt(e.getKey())); } } |