diff options
Diffstat (limited to 'src/main/java/com/seaofnodes')
38 files changed, 761 insertions, 395 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 |