diff options
Diffstat (limited to 'chapter15')
19 files changed, 381 insertions, 227 deletions
diff --git a/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 8a96e69c..3bdfcb2d 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -95,18 +95,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 +125,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 +140,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 +176,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 +233,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/chapter15/src/main/java/com/seaofnodes/simple/Parser.java b/chapter15/src/main/java/com/seaofnodes/simple/Parser.java index bea06a19..65bc82ea 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter15/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; @@ -116,8 +119,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 +147,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 +214,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),";"); } /** @@ -222,6 +229,7 @@ public class Parser { 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"); + // Parse a collection of fields ArrayList<Field> fields = new ArrayList<>(); require("{"); while (!peek('}') && !_lexer.isEOF()) { @@ -231,7 +239,7 @@ public class Parser { } require("}"); // Build and install the TypeStruct - TypeStruct ts = TypeStruct.make(typeName, fields); + TypeStruct ts = TypeStruct.make(typeName, fields.toArray(new Field[fields.size()])); TYPES.put(typeName, ts); START.addMemProj(ts, _scope); // Insert memory edges return parseStatement(); @@ -325,7 +333,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 +341,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 +471,42 @@ 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 = tmp.makeFrom((TypeStruct)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; - } - TYPES.put(tname,t = TypeStruct.make(tname)); - _lexer._position = old2; // Reparse ID in caller - } - return t instanceof TypeStruct obj ? TypeMemPtr.make(obj,nullable) : t; + // Convert the type name to a type. + Type t0 = TYPES.get(tname); + Type t1 = t0==null ? TypeStruct.BOT : t0; // Null: assume a forward ref type + //while( match("[]") ) + // t1 = TypeArray.make(t1); + Type t2 = t1 instanceof TypeStruct obj ? TypeMemPtr.make(obj,match("?")) : t1; + + // Check no forward ref + if( t0 != null ) return t2; + // Check valid forward ref, after parsing all the type extra bits. + // Cannot check earlier, because cannot find required 'id' until after "[]?" syntax + int old2 = _lexer._position; + 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, t0 = TypeStruct.make(tname)); + return ((TypeMemPtr)t2).makeFrom((TypeStruct)t0); } @@ -644,15 +661,21 @@ public class Parser { 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); + String typeName = _lexer.matchId(); + if( typeName==null ) throw error("Expected a type"); + Type t = TYPES.get(typeName); + //if( match("[") ) + // return require(newArray(t),"]"); + if( t instanceof TypeStruct obj ) { + if( obj._fields==null ) + throw error("Unknown struct type '" + typeName + "'"); + return newStruct(obj); + } + throw error("Cannot allocate a "+t); } String name = _lexer.matchId(); if( name == null) throw errorSyntax("an identifier or expression"); @@ -662,19 +685,28 @@ 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, memAlias(alias), n, new ConstantNode(field._type.makeInit()).peephole(),true).peephole()); - alias++; - } - return n.unkeep(); + Field[] fs = obj._fields; + Node[] ns = new Node[2+fs.length]; + ns[0] = ctrl(); + ns[1] = con(obj.offsets()[fs.length]); + 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(); } - // We set up memory aliases by inserting special vars in the scope these + private Node newArray(Type t) { + Node len = parseExpression(); + //TypeArray tary = TypeArray.make(t,TypeInteger.BOT); + //return new NewArrayNode(tary,ctrl(),len).peephole(); + throw Utils.TODO(); + } + // We set up memory aliases by inserting special vars in the scope these // variables are prefixed by $ so they cannot be referenced in Simple code. // Using vars has the benefit that all the existing machinery of scoping // and phis work as expected @@ -688,39 +720,48 @@ public class Parser { * * <pre> * expr ('.' IDENTIFIER)* [ = expr ] + * expr ('[' expr ']')* = [ = expr ] * </pre> */ private Node parsePostfix(Node expr) { - if( !match(".") ) return expr; + String name = "[]"; + if( match(".") ) name = requireId().intern(); + else if( !match("[") ) 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() + "'"); + // Sanity check field name for existing TypeStruct base = (TypeStruct)TYPES.get(ptr._obj._name); - int idx = base==null ? -1 : base.find(name); + if( base == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); + int idx = base.find(name); if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); - int alias = START._aliasStarts.get(ptr._obj._name)+idx; + + // Get field type and layout offset + Field f = base._fields[idx]; + Node off = con(base.offsets()[idx]); + if( name.equals("[]") ) + throw Utils.TODO(); // Array index math if( match("=") ) { // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment if( peek('=') ) _lexer._position--; else { 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, memAlias(alias), expr, val, false).peephole()); - return expr; // "obj.a = expr" returns the expression while updating memory + val = zsMask(val,f._type); + memAlias(f._alias, new StoreNode(name, f._alias, f._type, memAlias(f._alias), expr, off, val, false).peephole()); + return val; // "obj.a = expr" returns the expression while updating memory } } - Type declaredType = base._fields[idx]._type; - return parsePostfix(new LoadNode(name, alias, declaredType, memAlias(alias), expr).peephole()); + Node load = new LoadNode(name, f._alias, f._type, memAlias(f._alias), expr, off).peephole(); + return parsePostfix(load); } + // 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 +772,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 +794,10 @@ public class Parser { return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole(); } + private Node con( long con ) { + return new ConstantNode(TypeInteger.constant(con)).peephole(); + } + ////////////////////////////////// // Utilities for lexical analysis diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 4e1421fa..0567db6e 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter15/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,11 +17,12 @@ 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, 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; } @@ -30,6 +33,12 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { + if( mem()._type instanceof TypeMem mem && + // No constant folding if ptr might null-check + _declaredType != mem._t && err()==null ) { + assert mem._alias == _alias; + return _declaredType.join(mem._t); + } return _declaredType; } @@ -43,6 +52,11 @@ public class LoadNode extends MemOpNode { 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()); + // 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. @@ -55,13 +69,9 @@ public class LoadNode extends MemOpNode { 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 = new LoadNode(_name,_alias,_declaredType,memphi.in(1),ptr(), off()).peephole(); + Node ld2 = new LoadNode(_name,_alias,_declaredType,memphi.in(2),ptr(), off()).peephole(); + return new PhiNode(_name,_declaredType,memphi.region(),ld1,ld2); } } @@ -71,6 +81,9 @@ public class LoadNode extends MemOpNode { // 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(); + 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() ) { px.addDep(this); return true; } + return false; } } diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index bc8e46d3..7a25d498 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -13,21 +13,21 @@ public abstract class MemOpNode extends Node { public final int _alias; public final Type _declaredType; - - public MemOpNode(String name, int alias, Type glb, Node memSlice, Node memPtr) { - super(null, memSlice, memPtr); + 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 memSlice, Node memPtr, Node value) { - this(name, alias, glb, memSlice, memPtr); + 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); } public Node mem() { return in(1); } public Node ptr() { return in(2); } + public Node off() { return in(3); } @Override boolean eq(Node n) { @@ -41,8 +41,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/chapter15/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/NewNode.java index 0724ec56..f1e6e84b 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -1,24 +1,32 @@ 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 { +/** + * 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 { TypeMemPtr _ptr; - public NewNode(TypeMemPtr ptr, Node ctrl) { - super(ctrl); - this._ptr = 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.str(); } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { @@ -26,10 +34,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() { + Type[] ts = new Type[nIns()]; + ts[0] = Type.CONTROL; + ts[1] = _ptr; + Field[] fs = _ptr._obj._fields; + 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/chapter15/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/ProjNode.java index f94e98a7..73c1fa15 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter15/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/chapter15/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/StartNode.java index 5f205ffd..14bf37f5 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter15/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,26 @@ 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); } + _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 +57,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/chapter15/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter15/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 44a14be1..a27aee2b 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -14,21 +14,22 @@ 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 memSlice, Node memPtr, Node value, boolean init) { - super(name, alias, glb, 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 "ST"+_name; } + @Override public String label() { return "." +_name+"="; } @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 +37,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() { @@ -72,7 +80,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/chapter15/src/main/java/com/seaofnodes/simple/type/Field.java b/chapter15/src/main/java/com/seaofnodes/simple/type/Field.java index b2c006dd..5e674132 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/chapter15/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/chapter15/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/chapter15/src/main/java/com/seaofnodes/simple/type/TypeMem.java index b2d081f4..32491a11 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/chapter15/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/chapter15/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter15/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index b77f1dc2..e7794e14 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -9,40 +9,40 @@ 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(byte t, String name, Field[] fields) { + super(t); _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(TSTRUCT, 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, null); } // 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 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)) }); public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); } public int find(String fname) { @@ -70,11 +70,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); } @@ -113,6 +117,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++ ) @@ -143,4 +148,37 @@ public class TypeStruct extends Type { } @Override public String str() { return _name; } + + + // Field offsets as packed byte offsets + private int[] _offs; // Lazily computed and not part of the type semantics + public int[] offsets() { // Field byte offsets + if( _offs != null ) return _offs; + + // 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+3); + } + // 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+3); // Next field offset at same alignment + cnts[log]--; // Count down, should be all zero at end + } + _offs[_fields.length] = (off+63)& ~63; // Round out to max alignment + return _offs; + } + } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 65bd1170..f1b791fb 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -65,9 +65,9 @@ else v.y = 3; return v; """); - StopNode stop = parser.parse(true).iterate(true); + StopNode stop = parser.parse(false).iterate(true); System.out.println(IRPrinter.prettyPrint(stop, 99, true)); - assertEquals("return new Vector2D;", stop.toString()); + assertEquals("return Vector2D;", stop.toString()); } @Test @@ -105,7 +105,7 @@ while (arg) { return bar.a; """); StopNode stop = parser.parse(false).iterate(true); - assertEquals("return Phi(Loop12,0,(Phi_a+2));", stop.toString()); + assertEquals("return Phi(Loop13,0,(Phi_a+2));", stop.toString()); } @Test @@ -157,7 +157,7 @@ if( bar ) bar.a = 1; return bar; """); StopNode stop = parser.parse(false).iterate(true); - assertEquals("return Phi(Region31,(*void)Phi(Region19,null,new Bar),null);", stop.toString()); + assertEquals("return Phi(Region33,(*void)Phi(Region20,null,Bar),null);", stop.toString()); } @Test @@ -173,7 +173,7 @@ else bar.a = 1; return rez; """); StopNode stop = parser.parse(false).iterate(true); - assertEquals("return Phi(Region37,4,3);", stop.toString()); + assertEquals("return Phi(Region39,4,3);", stop.toString()); } @Test @@ -227,7 +227,7 @@ while( i.x < i.len ) { return sum; """); StopNode stop = parser.parse().iterate(true); - assertEquals("return Phi(Loop17,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); + assertEquals("return Phi(Loop18,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); } @@ -249,7 +249,7 @@ return ret; """); StopNode stop = parser.parse(true).iterate(true); System.out.println(IRPrinter.prettyPrint(stop, 99, true)); - assertEquals("return Phi(Loop12,new s0,Phi(Region34,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop13,s0,Phi(Region37,s0,Phi_ret));", stop.toString()); } @Test @@ -268,7 +268,7 @@ return ret; """); StopNode stop = parser.parse(true).iterate(true); System.out.println(IRPrinter.prettyPrint(stop, 99, true)); - assertEquals("return Phi(Loop15,new s0,Phi(Region35,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop17,s0,Phi(Region38,s0,Phi_ret));", stop.toString()); } @@ -286,7 +286,7 @@ return ret; """); StopNode stop = parser.parse(true).iterate(true); System.out.println(IRPrinter.prettyPrint(stop, 99, true)); - assertEquals("return Phi(Loop12,new s0,Phi(Region33,new s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop13,s0,Phi(Region35,s0,Phi_ret));", stop.toString()); } @Test @@ -330,7 +330,7 @@ else return new s0; if(new s0.f0) return 0; """); StopNode stop = parser.parse(true).iterate(true); - assertEquals("return new s0;", stop.toString()); + assertEquals("return s0;", stop.toString()); } @Test @@ -358,7 +358,7 @@ s0 v1 = v0; return v1; """); StopNode stop = parser.parse().iterate(true); - assertEquals("return new s0;", stop.toString()); + assertEquals("return s0;", stop.toString()); } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 3b9cac7d..9f5119f5 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -347,6 +347,8 @@ return i; """); StopNode stop = parser.parse(false).iterate(true); assertEquals("return .f;", stop.toString()); + assertEquals(2L, Evaluator.evaluate(stop, 0)); + assertEquals(2L, Evaluator.evaluate(stop, 1)); } @Test @@ -355,6 +357,7 @@ return i; """ struct S { int f; } S v = new S; +v.f = arg; S t = new S; int i = 0; if (arg) { @@ -366,7 +369,7 @@ if (arg) { return i; """); StopNode stop = parser.parse(false).iterate(true); - assertEquals("return Phi(Region34,.f,0);", stop.toString()); + assertEquals("return Phi(Region40,.f,0);", stop.toString()); } @Test @@ -385,7 +388,7 @@ if (v1) { return v0; """); StopNode stop = parser.parse(false).iterate(true); - assertEquals("return new S;", stop.toString()); + assertEquals("return S;", stop.toString()); } @@ -395,6 +398,7 @@ return v0; """ struct S { int f; } S v = new S; +v.f = arg; S t = new S; int i = v.f; if (arg+1) arg= 0; @@ -419,7 +423,7 @@ while(1) { return v; """); StopNode stop = parser.parse(false).iterate(true); - assertEquals("return new S;", stop.toString()); + assertEquals("return S;", stop.toString()); } @Test @@ -452,7 +456,7 @@ while (arg) { return i; """); StopNode stop = parser.parse(false).iterate(false); - assertEquals("return .f;", stop.toString()); + assertEquals("return 0;", stop.toString()); } @Test @@ -472,7 +476,7 @@ while(arg) { return arg; """); StopNode stop = parser.parse(false).iterate(false); - assertEquals("return Phi(Loop15,arg,Phi(Region37,.f,0));", stop.toString()); + assertEquals("return Phi(Loop17,arg,Phi(Region42,.f,0));", stop.toString()); } @Test @@ -490,7 +494,7 @@ if (arg) { return v; """); StopNode stop = parser.parse(false).iterate(false); - assertEquals("return new S;", stop.toString()); + assertEquals("return S;", stop.toString()); } @Test diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter13Test.java index f9aa3016..97e6808e 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -35,7 +35,7 @@ while( arg ) { return head.next.i; """); try { parser.parse(true).iterate(true); fail(); } - catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); } + catch( Exception e ) { assertEquals("Might be null accessing 'next'",e.getMessage()); } } @Test @@ -101,7 +101,7 @@ n.next = new N; return n.next; """); StopNode stop = parser.parse(false).iterate(false); - assertEquals("return new N;", stop.toString()); + assertEquals("return N;", stop.toString()); } @Test @@ -161,6 +161,6 @@ struct S2 { int x; } return new S1.s=new S2; """); StopNode stop = parser.parse(false).iterate(false); - assertEquals("return new S1;", stop.toString()); + assertEquals("return S2;", stop.toString()); } } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 550c3165..f884f18d 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -33,4 +33,14 @@ return is[1]; assertEquals(0L, Evaluator.evaluate(stop, 0)); } + @Test + public void testBad0() { + Parser parser = new Parser( +""" +return new flt; +"""); + try { parser.parse(false).iterate(false); fail(); } + catch( Exception e ) { assertEquals("Cannot allocate a FltBot",e.getMessage()); } + } + } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/chapter15/src/test/java/com/seaofnodes/simple/SchedulerTest.java index e5961815..6f65f834 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/SchedulerTest.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/SchedulerTest.java @@ -48,7 +48,7 @@ return v0; """); StopNode stop = parser.parse(false).iterate(true); var eval = new Evaluator(stop); - assertObj(eval.evaluate(0, 10), "S", 0L); + assertObj(eval.evaluate(0, 10), "S", new Object[1]); assertObj(eval.evaluate(1, 10), "S", 1L); } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter15/src/test/java/com/seaofnodes/simple/TypeTest.java index 9e8a1418..cb45a0d7 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -13,32 +13,32 @@ public class TypeTest { @Test public void testTypeAdHoc() { TypeStruct s1 = TypeStruct.make("s1", new Field[]{ - Field.make("a", TypeInteger.BOT), - Field.make("b", TypeInteger.BOT) }); + Field.make("a",-1, TypeInteger.BOT), + Field.make("b",-2, TypeInteger.BOT) }); TypeStruct s2 = TypeStruct.make("s2", new Field[]{ - Field.make("a", TypeInteger.BOT), - Field.make("b", TypeInteger.BOT) }); + Field.make("a",-3, TypeInteger.BOT), + Field.make("b",-4, TypeInteger.BOT) }); Assert.assertEquals(s1, s1.glb()); Assert.assertNotEquals(s1, s1.dual()); Assert.assertEquals(s1, s1.dual().glb()); - TypeMem m1 = TypeMem.make(1); - TypeMem m2 = TypeMem.make(2); - TypeMem m3 = TypeMem.make(3); - TypeMem m4 = TypeMem.make(4); + TypeMem m1 = TypeMem.make(1,TypeInteger.ZERO); + TypeMem m2 = TypeMem.make(2,TypeInteger.U16); + TypeMem m3 = TypeMem.make(3,TypeFloat.BOT); + TypeMem m4 = TypeMem.make(4,TypeInteger.BOT); Assert.assertNotEquals(m1, m2); Assert.assertNotEquals(m2, m3); Assert.assertNotEquals(m3, m4); Assert.assertEquals(TypeStruct.BOT, s1.meet(s2)); - Assert.assertEquals(TypeMem .BOT, m1.meet(m2)); + Assert.assertEquals(TypeMem.make(-1,TypeInteger.U16), m1.meet(m2)); Assert.assertEquals(TypeMem .BOT, m2.meet(m3)); Assert.assertEquals(TypeMem .BOT, m3.meet(m4)); - Assert.assertEquals(m1, m1.glb()); - Assert.assertEquals(TypeMem.make(1), m1.dual()); - Assert.assertEquals(m1.dual(), m1.glb().dual()); + Assert.assertEquals(TypeMem.make(1,TypeInteger.BOT), m1.glb()); + Assert.assertEquals(TypeMem.make(1,TypeInteger.ZERO), m1.dual()); + Assert.assertEquals(m4.dual(), m4.glb().dual()); TypeMemPtr ptr1 = TypeMemPtr.make(s1); Assert.assertEquals(s1, ptr1._obj); @@ -58,12 +58,12 @@ public class TypeTest { Assert.assertEquals(ptr1, ptr1.dual().dual()); Assert.assertEquals(ptr1.glb(), ptr1.dual().glb()); - Assert.assertEquals(TypeMemPtr.BOT, ptr1.meet(ptr2nil)); + Assert.assertEquals(TypeMemPtr.make(TypeStruct.BOT,true), ptr1.meet(ptr2nil)); Assert.assertEquals(ptr1.glb(), ptr1.meet(TypeMemPtr.NULLPTR)); TypeMemPtr TOP = TypeMemPtr.TOP; - TypeMemPtr BOT = TypeMemPtr.BOT; - TypeMemPtr PTR = TypeMemPtr.VOIDPTR; + TypeMemPtr BOT = TypeMemPtr.make(TypeStruct.BOT,true ); + TypeMemPtr PTR = TypeMemPtr.make(TypeStruct.BOT,false); TypeMemPtr NULL = TypeMemPtr.NULLPTR; Type PTR_meet_NULL = NULL.meet(PTR); Assert.assertEquals(BOT, PTR_meet_NULL); diff --git a/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 31a14c05..b897af7d 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -26,7 +26,7 @@ public class Evaluator { } } - private static int getFieldIndex(TypeStruct struct, MemOpNode memop) { + private static int getFieldIndex(TypeStruct struct, MemOpNode memop, long off) { int idx = struct.find(memop._name); if( idx >= 0 ) return idx; throw new AssertionError("Field "+memop._name+" not found in struct " + struct._name); @@ -83,20 +83,25 @@ public class Evaluator { } private Object alloc(NewNode alloc) { - var type = ((TypeMemPtr)alloc.compute())._obj; - return new Obj(type, new Object[type._fields.length]); + TypeTuple tt = alloc.compute(); + TypeStruct type = ((TypeMemPtr)tt._types[1])._obj; + Object[] mems = new Object[type._fields.length+2]; + mems[1] = new Obj(type,new Object[type._fields.length]); + return mems; } private Object load(LoadNode load) { - var from = (Obj)val(load.in(2)); - var idx = getFieldIndex(from.struct, load); + var from = (Obj)val(load.ptr()); + var off = val(load.off()); + var idx = getFieldIndex(from.struct, load, (Long)off); return from.fields[idx]; } private Object store(StoreNode store) { - var to = (Obj)val(store.in(2)); - var val = val(store.in(3)); - var idx = getFieldIndex(to.struct, store); + var to = (Obj)val(store.ptr()); + var off = val(store.off()); + var val = val(store.val()); + var idx = getFieldIndex(to.struct, store, (Long)off); to.fields[idx] = val; return null; } diff --git a/chapter15/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/chapter15/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index ec6e7816..324dd42d 100644 --- a/chapter15/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/chapter15/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -25,7 +25,7 @@ public class ScriptGenerator { private static final int MAX_BLOCK_DEPTH = 4; private static final int MAX_EXPRESSION_DEPTH = 10; private static final int MAX_SUFFIX_RECURSIVE_DEPTH = 10; - + /** * Number of spaces per indentation */ @@ -109,7 +109,7 @@ public class ScriptGenerator { static { new Parser("", TypeInteger.BOT); - for(var e:Parser.TYPES.entrySet()) { + for(var e : Parser.TYPES.entrySet() ) { if (e.getValue() instanceof TypeInteger) { INTTYPES.add(new TypeInt(e.getKey())); } |