From 4369fd94247acf5fef5ebff0ac644671bf165e42 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 12 Sep 2024 11:13:31 -0700 Subject: Chapter 15: Arrays MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: XmiliaH Co-authored-by: Thalia Archibald Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Robert Obkircher Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- .../com/seaofnodes/simple/GlobalCodeMotion.java | 46 ++-- src/main/java/com/seaofnodes/simple/Parser.java | 241 +++++++++++++++------ src/main/java/com/seaofnodes/simple/Utils.java | 11 +- .../java/com/seaofnodes/simple/node/AddNode.java | 5 +- .../java/com/seaofnodes/simple/node/AndNode.java | 1 - .../java/com/seaofnodes/simple/node/BoolNode.java | 22 +- .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 16 +- .../java/com/seaofnodes/simple/node/CFGNode.java | 2 - .../java/com/seaofnodes/simple/node/CProjNode.java | 17 +- .../com/seaofnodes/simple/node/ConstantNode.java | 1 - .../java/com/seaofnodes/simple/node/DivNode.java | 2 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 127 +++++++++-- .../com/seaofnodes/simple/node/MemMergeNode.java | 36 ++- .../java/com/seaofnodes/simple/node/MemOpNode.java | 23 +- .../com/seaofnodes/simple/node/MemPhiNode.java | 12 +- .../java/com/seaofnodes/simple/node/MinusNode.java | 4 +- .../java/com/seaofnodes/simple/node/NewNode.java | 37 +++- src/main/java/com/seaofnodes/simple/node/Node.java | 16 +- .../java/com/seaofnodes/simple/node/OrNode.java | 1 - .../java/com/seaofnodes/simple/node/PhiNode.java | 10 +- .../java/com/seaofnodes/simple/node/ProjNode.java | 5 +- .../com/seaofnodes/simple/node/RegionNode.java | 59 ++++- .../java/com/seaofnodes/simple/node/SarNode.java | 16 +- .../java/com/seaofnodes/simple/node/ScopeNode.java | 82 ++++--- .../java/com/seaofnodes/simple/node/ShlNode.java | 18 +- .../java/com/seaofnodes/simple/node/ShrNode.java | 17 +- .../java/com/seaofnodes/simple/node/StartNode.java | 4 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 26 ++- .../java/com/seaofnodes/simple/node/SubNode.java | 7 +- .../java/com/seaofnodes/simple/node/XorNode.java | 1 - .../simple/print/SimpleGraphAdapter.java | 9 +- .../simple/print/SimpleGraphObserver.java | 2 +- .../java/com/seaofnodes/simple/type/Field.java | 24 +- src/main/java/com/seaofnodes/simple/type/Type.java | 10 + .../java/com/seaofnodes/simple/type/TypeFloat.java | 6 + .../com/seaofnodes/simple/type/TypeInteger.java | 17 +- .../java/com/seaofnodes/simple/type/TypeMem.java | 36 +-- .../com/seaofnodes/simple/type/TypeMemPtr.java | 15 +- .../com/seaofnodes/simple/type/TypeStruct.java | 114 ++++++++-- .../java/com/seaofnodes/simple/type/TypeTuple.java | 9 +- 40 files changed, 762 insertions(+), 345 deletions(-) (limited to 'src/main/java/com/seaofnodes/simple') diff --git a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 78a0dcde..d17ec3b6 100644 --- a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -93,11 +93,12 @@ 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 inputs first, except Phis: following their backedges would // enter a data cycle before its control has been scheduled. for( Node def : n._inputs ) - if( def!=null && !(def instanceof PhiNode) ) + if( def!=null ) _schedEarly(def,visit); // An existing edge 0 already supplies control (or a Phi/Proj binding). if( n.in(0)==null ) { @@ -122,7 +123,7 @@ public abstract class GlobalCodeMotion { // Copy the best placement choice into the control slot for( int i=0; i st._alias==load._alias; - case MemPhiNode phi -> phi._alias==load._alias; - case BulkMemPhiNode phi -> !phi.isSplit(load._alias); - default -> false; - }; + // An allocation may consume a load's memory through a partial aggregate. + private static void wakeLoads(Node def, CFGNode[] late, WorkList work, BitSet visit) { + if( visit.get(def._nid) ) return; + visit.set(def._nid); + for( Node out : def._outputs ) + if( out instanceof LoadNode ld && late[ld._nid]==null ) work.push(ld); + if( def instanceof MemMergeNode ) + for( int i=1; imem uses, looking for Stores causing an anti-dep - for( Node mem : load.mem()._outputs ) { - if( !antiUse(load,mem) ) continue; + for( Node mem : load.antiDeps() ) { switch( mem ) { case StoreNode st: assert late[st._nid]!=null; lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); break; + case NewNode st: + assert late[st._nid]!=null; + lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st,anti); + 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/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 0602d290..81291326 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -31,14 +31,13 @@ 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 - public StopNode STOP; + // Next available memory alias number + static int ALIAS; - // Field identities are independent of the memory graph and Start's tuple. - private final HashMap _aliases = new HashMap<>(); - private int _alias = 2; + public StopNode STOP; // Debugger Printing. public static boolean SCHEDULED; // True if debug printer can use schedule info @@ -101,7 +100,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 TYPES = new HashMap<>(); public Parser(String source, TypeInteger arg) { @@ -129,8 +130,9 @@ public class Parser { _continueScope = _breakScope = null; START = new StartNode(new Type[]{ Type.CONTROL, TypeMem.BOT, 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) { @@ -157,8 +159,9 @@ public class Parser { _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 2, ScopeNode.ARG0).peephole()); _scope.define("$mem", TypeMem.BOT, new ProjNode(START, 1, "$mem").peephole()); 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()); @@ -218,7 +221,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),";"); } /** @@ -232,7 +235,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 fields = new ArrayList<>(); require("{"); while (!peek('}') && !_lexer.isEOF()) { @@ -242,10 +247,8 @@ public class Parser { } require("}"); // Build and install the TypeStruct - TypeStruct ts = TypeStruct.make(typeName, fields); - TYPES.put(typeName, ts); // Insert the struct name in the collection of all struct names - _aliases.put(typeName,_alias); - _alias += ts._fields.length; + TypeStruct ts = TypeStruct.make(typeName, fields.toArray(new Field[fields.size()])); + TYPES.put(typeName, TypeMemPtr.make(ts)); return parseStatement(); } @@ -337,7 +340,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 @@ -345,7 +348,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; } @@ -469,33 +472,69 @@ 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); + return tary; } @@ -643,22 +682,36 @@ public class Parser { * Parse a primary expression: * * 
-     *     primaryExpr : integerLiteral | Identifier | true | false | null | new Identifier | '(' expression ')'
+     *     primaryExpr : integerLiteral | Identifier | true | false | null | new Type | '(' expression ')'
      *
* @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"); @@ -668,25 +721,46 @@ 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 = _aliases.get(obj._name); - for( Field field : obj._fields ) { - store(field._fname,alias,field._type,n,new ConstantNode(field._type.makeInit()).peephole(),true); - alias++; - } - return n.unkeep(); + private Node newStruct(TypeStruct obj, Node size) { + Node prior = mem().keep(); + // No default: only the aliases initialized by this allocation. + MemMergeNode input = new MemMergeNode(null); + for( Field f : obj._fields ) + input.alias(f._alias,prior); + Node nnn = new NewNode(TypeMemPtr.make(obj),ctrl(),input.peephole(),size).peephole().keep(); + Node ptr = new ProjNode(nnn,0,obj._name).peephole().keep(); + Node out = new ProjNode(nnn,1,"$mem").peephole().keep(); + MemMergeNode after = new MemMergeNode(prior); + for( Field f : obj._fields ) + after.alias(f._alias,out); + mem(after.peephole()); + out.unkeep(); + nnn.unkeep(); + if( prior.unkeep().isUnused() ) prior.kill(); + return ptr.unkeep(); + } + + 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 + store("#",alias,TypeInteger.BOT,ptr,con(ary.offset(0)),len.unkeep(),true,null); + return ptr; } // Memory is one hidden SSA variable, including across branches and loops. private Node mem() { return _scope.lookup("$mem"); } private Node mem(Node n) { return _scope.update("$mem",n); } - private void store(String name, int alias, Type glb, Node ptr, Node val, boolean init) { + private void store(String name, int alias, Type glb, Node ptr, Node off, Node val, boolean init, Node ctrl) { Node prior = mem().keep(); - Node st = new StoreNode(name,alias,glb,ctrl(),prior,ptr,val,init).peephole(); + Node st = new StoreNode(name,alias,glb,prior,ptr,off,val,init); + st.setDef(0,ctrl); + st = st.peephole(); mem(new MemMergeNode(prior,alias,st).peephole()); if( prior.unkeep().isUnused() ) prior.kill(); } @@ -697,39 +771,66 @@ public class Parser { * * 
      *     expr ('.' IDENTIFIER)* [ = expr ]
+     *     expr #
+     *     expr ('[' expr ']')* = [ = expr ]
      *
*/ 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 = _aliases.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); - store(name,alias,glb,expr,val,false); - return expr; // "obj.a = expr" returns the expression while updating memory + val = zsMask(val,f._type).keep(); + // Array control stands in for the future bounds check. + store(name,f._alias,f._type,expr.unkeep(),off.unkeep(),val,false,base.isAry() ? ctrl() : null); + return val.unkeep(); // "obj.a = expr" returns the expression while updating memory } } - Type declaredType = base._fields[idx]._type; - return parsePostfix(new LoadNode(name, alias, declaredType.glb(), mem(), expr).peephole()); + Node load = new LoadNode(name, f._alias, f._type.glb(), mem(), 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 ) { @@ -742,10 +843,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(); @@ -764,6 +865,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 del(ArrayList 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 void del(ArrayList 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 0046bd03..5875a73d 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -15,7 +15,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()) @@ -29,7 +30,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 e2729e60..0844f2ea 100644 --- a/src/main/java/com/seaofnodes/simple/node/AndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AndNode.java @@ -14,7 +14,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 8a25e8d9..6efde623 100644 --- a/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -32,9 +32,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); @@ -50,6 +47,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) ) { @@ -61,11 +62,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 ((phi cons) cmp con) ? + // Do we have ((phi cons) cmp (phi cons)) ? + // Push the compare up through the phi: (phi con0 cmp con, con1 cmp con...) + Node phicon = AddNode.phiCon(this,this instanceof EQ); + if( phicon!=null ) return phicon; + return null; } @@ -103,8 +107,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/BulkMemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java index 8d512f21..84f97189 100644 --- a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -87,7 +87,7 @@ public class BulkMemPhiNode extends PhiNode { // True if the MemMerge has no precise slice still covered by this Phi. private boolean canPeek(MemMergeNode mmm) { - return missingAlias(mmm,false)==0; + return mmm.in(1)!=null && missingAlias(mmm)==0; } // Return an alias required by an input but still covered by this Phi, or 0. @@ -95,7 +95,7 @@ public class BulkMemPhiNode extends PhiNode { return switch(n) { case ProjNode proj -> 0; case ConstantNode con -> 0; - case MemMergeNode mmm -> missingAlias(mmm,false); + case MemMergeNode mmm -> missingAlias(mmm); case MemOpNode mem -> unsplit(mem._alias); case BulkMemPhiNode bulk -> missingAlias(bulk); default -> throw new AssertionError("Unexpected memory input "+n); @@ -111,7 +111,7 @@ public class BulkMemPhiNode extends PhiNode { use.addDepForwards(this); return switch(use) { case ScopeNode scope -> 0; - case MemMergeNode mmm -> missingAlias(mmm,true); + case MemMergeNode mmm -> missingAlias(mmm); case BulkMemPhiNode bulk -> missingAlias(bulk); case MemOpNode mem -> unsplit(mem._alias); case MemPhiNode phi -> unsplit(phi._alias); @@ -139,14 +139,14 @@ public class BulkMemPhiNode extends PhiNode { return 0; } - // First precise MemMerge slice still covered by this Phi. When inspecting - // a user, ignore slots which point back to this Phi. - private int missingAlias(MemMergeNode mmm, boolean user) { + // Every explicit slot requests that alias, including a partial allocation + // input whose slot still points to this bulk Phi. + private int missingAlias(MemMergeNode mmm) { for( int alias=2; alias _print1(ExprPrinter p) { return p.p(".").p(_name); } @Override public Type compute() { - return _declaredType; + Type t = MemMergeNode.contents(mem(),_alias,this); + // No constant folding if the pointer still needs a null check. + return err()==null ? _declaredType.join(t) : _declaredType; } @Override @@ -57,15 +63,57 @@ public class LoadNode extends MemOpNode { setDef(1,IterPeeps.add(merge.alias(_alias))); return this; } - + Node ptr = ptr(); // Simple Load-after-Store on same address. if( mem() instanceof StoreNode st && - ptr() == st.ptr() && _alias==st._alias ) { // Must check same object + _alias==st._alias && ptr == st.ptr() && off() == st.off() ) { // Must check same object assert _name.equals(st._name); // Equiv class aliasing is perfect return st.val(); } + // Simple Load-after-New on same address. + if( mem() instanceof ProjNode p && p.in(0) instanceof NewNode nnn && + ptr == nnn.proj(0) ) // Must check same object + return 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 ) { + mem.addDep(this); + switch( mem ) { + case MemMergeNode merge: + mem = merge.alias(_alias); + break; + case StoreNode st: + if( _alias==st._alias && ptr == st.ptr() && off() == st.off() ) + return st.val(); // Proved equal + // Can we prove unequal? Offsets do not overlap? + if( _alias==st._alias && !off()._type.join(st.off()._type).isHigh() && // Offsets overlap + !neverAlias(ptr,st.ptr()) ) // And might alias + 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.mem();// Bypass unrelated New + break; + } else break outer; + default: + break outer; + } + } + // 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. @@ -73,31 +121,66 @@ 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 MemPhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 ) { + if( mem() instanceof MemPhiNode 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(); + LoadNode ld = new LoadNode(_name,_alias,_declaredType,mem.in(idx),ptr instanceof PhiNode && ptr.in(0)==mem.in(0) ? ptr.in(idx) : ptr,off()); + ld.setDef(0,in(0)); + return ld.peephole(); + } + private static boolean neverAlias( Node ptr1, Node ptr2 ) { + return ptr1.in(0) != ptr2.in(0) && + // Unrelated allocations + 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() && _alias==st1._alias; + if( px==null ) return false; + px.addDep(this); + if( px._type instanceof TypeMem mem && mem._t.isHighOrConst() ) return true; + if( px instanceof StoreNode st1 && _alias==st1._alias && ptr()==st1.ptr() && off()==st1.off() ) return true; + return false; + } + + // Memory writers which must follow this read. A packaging node is not a + // write, but can hide New's input, so follow this alias through aggregates. + public ArrayList antiDeps() { + ArrayList deps = new ArrayList<>(); + antiDeps(mem(),deps,new BitSet()); + return deps; } - Node copy(Node mem, Node ptr) { - return new LoadNode(_name,_alias,_declaredType,mem,ptr); + private void antiDeps(Node mem, ArrayList deps, BitSet visit) { + if( visit.get(mem._nid) ) return; + visit.set(mem._nid); + for( Node use : mem._outputs ) { + if( use instanceof MemMergeNode merge ) { + Node slice = _alias 1; _alias = alias; } @@ -18,8 +18,14 @@ public class MemPhiNode extends PhiNode { @Override public Type compute() { assert BulkMemPhiNode.checkMem(this,_alias); - Type t = super.compute(); - return t==Type.TOP || t==TypeMem.TOP ? TypeMem.TOP : TypeMem.make(_alias); + if( !(region() instanceof RegionNode r) ) + return region()._type==Type.XCONTROL ? TypeMem.TOP : _type; + if( r.inProgress() ) return _declaredType; + Type t = Type.TOP; + for( int i=1; i _print1(ExprPrinter p) { return p.p("new ").p(_ptr._obj.str()); } - @Override - public Type compute() { return _ptr; } + public TypeTuple compute() { + return TypeTuple.make(_ptr,TypeMem.BOT); + } @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 4ee82187..541c8eb1 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -92,7 +92,7 @@ public abstract class Node extends BaseNode implements OutNode, Cloneable public boolean isUnused() { return nOuts() == 0; } - public CFGNode cfg0() { return (CFGNode)in(0); } + public CFGNode cfg0() { return (CFGNode)in(0); } /** * Change a def into a Node. Keeps the edges correct, by removing @@ -136,11 +136,10 @@ public abstract class Node extends BaseNode implements OutNode, Cloneable 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; } @@ -489,8 +488,6 @@ public abstract class Node extends BaseNode implements OutNode, Cloneable // ------------------------------------------------------------------------ // - /** Is this Node control-flow-graph related */ - /** Is this Node Memory related */ public boolean isMem() { return false; } @@ -593,12 +590,7 @@ public abstract class Node extends BaseNode implements OutNode, Cloneable 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 67585423..1f312d10 100644 --- a/src/main/java/com/seaofnodes/simple/node/OrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/OrNode.java @@ -14,7 +14,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 309cd8b5..ea5eeb89 100644 --- a/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -12,7 +12,7 @@ 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; } @@ -21,7 +21,7 @@ public class PhiNode extends Node { return type instanceof TypeMem ? new BulkMemPhiNode(label,inputs) : new PhiNode(label,type,inputs); } - @Override public String label() { return "Phi_"+_label; } + @Override public String label() { return "Phi_"+MemOpNode.mlabel(_label); } @Override protected ExprPrinter _print1(ExprPrinter p) { @@ -82,9 +82,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; @@ -97,7 +97,7 @@ public class PhiNode extends Node { private boolean same_op() { Node op = in(1); - if( op.isCFG() || op instanceof ConstantNode || op instanceof PhiNode || + if( op instanceof CFGNode || op instanceof ConstantNode || op instanceof PhiNode || op instanceof ProjNode || op instanceof NewNode || op instanceof ScopeNode || op instanceof MemMergeNode ) return false; // A bulk Phi must split its aliases before factoring precise Stores. if( this instanceof BulkMemPhiNode ) return false; diff --git a/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/src/main/java/com/seaofnodes/simple/node/ProjNode.java index e82c69b3..668e20ad 100644 --- a/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -21,12 +21,13 @@ public class ProjNode extends Node { _label = label; } - @Override - public String label() { return _label; } + @Override public String label() { return _label; } @Override protected ExprPrinter _print1(ExprPrinter p) { return p.p(_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; } diff --git a/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/src/main/java/com/seaofnodes/simple/node/RegionNode.java index cdfd10ad..d4f73ddf 100644 --- a/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -67,15 +67,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.addDepForwards(this).in(0)==p2.addDepForwards(this).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>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 b408eb2f..36a5060b 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -3,10 +3,9 @@ package com.seaofnodes.simple.node; import com.seaofnodes.print.ExprPrinter; 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.*; /** @@ -23,24 +22,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> _scopes; + public final Stack> _idxs; /** - * Tracks declared types for every name + * Map variable names to declared Type */ - public Stack> _types; - + final Stack> _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 @@ -59,6 +56,20 @@ public class ScopeNode extends Node { return p.unchar(' ').p("]"); } + 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 @@ -68,7 +79,7 @@ public class ScopeNode extends Node { */ public String[] reverseNames() { String[] names = new String[nIns()]; - for( HashMap syms : _scopes ) + for( HashMap syms : _idxs ) for( String name : syms.keySet() ) names[syms.get(name)] = name; return names; @@ -78,33 +89,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 syms = _scopes.lastElement(); - _types.lastElement().put(name,declaredType); + HashMap 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. *

@@ -118,7 +130,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); @@ -136,29 +148,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 @@ -166,7 +164,7 @@ public class ScopeNode extends Node { * also the program Nodes). *

* 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. *

@@ -179,10 +177,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 syms : _scopes ) - dup._scopes.push(new HashMap<>(syms)); - for( HashMap ts : _types ) - dup._types.push(ts); // Types don't change, just keep stacks aligned + for( HashMap syms : _idxs ) + dup._idxs.push(new HashMap<>(syms)); + for( HashMap 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 (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 b89f5191..2193965b 100644 --- a/src/main/java/com/seaofnodes/simple/node/ShrNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ShrNode.java @@ -14,19 +14,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 a5d4923f..812305d5 100644 --- a/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -16,8 +16,7 @@ public class StartNode extends CFGNode implements MultiNode { _type = _args = TypeTuple.make(args); } - @Override - public String label() { return "Start"; } + @Override public String label() { return "Start"; } @Override protected ExprPrinter _print1(ExprPrinter p) { return p.p(label()); @@ -25,6 +24,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 e9eaaf2e..485491c0 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -16,24 +16,26 @@ 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; } + // Debugger label @Override boolean canDrop(MemOpNode other, Node dep) { return super.canDrop(other,dep) && _init==((StoreNode)other)._init; } - @Override public String label() { return "." +_name+"="; } + @Override public String label() { return "st_"+mlabel(); } @Override public boolean isMem() { return true; } - public Node val() { return in(3); } + public Node val() { return in(4); } @Override protected ExprPrinter _print1(ExprPrinter p) { @@ -41,7 +43,10 @@ public class StoreNode extends MemOpNode { } @Override - public Type compute() { return TypeMem.make(_alias); } + public Type compute() { + Type t = val()._type.meet(MemMergeNode.contents(mem(),_alias,this)); + return TypeMem.make(_alias,t); + } @Override public Node idealize() { @@ -55,6 +60,7 @@ public class StoreNode extends MemOpNode { // required init-store being stomped by a first user store. if( mem() instanceof StoreNode st && ptr()==st.ptr() && _alias==st._alias && // 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. @@ -82,7 +88,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 d5e54e73..134f7cd6 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -15,10 +15,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; @@ -27,6 +23,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 720fb8e4..dbff90cf 100644 --- a/src/main/java/com/seaofnodes/simple/node/XorNode.java +++ b/src/main/java/com/seaofnodes/simple/node/XorNode.java @@ -14,7 +14,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/print/SimpleGraphAdapter.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index 26897a7c..e2bf366d 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -6,7 +6,7 @@ import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.node.Node; import com.seaofnodes.simple.type.TypeMem; -/** Chapter 14's view of the IR; browser, transport and layout are shared. */ +/** Chapter 15's view of the IR; browser, transport and layout are shared. */ public class SimpleGraphAdapter extends GraphAdapter { @Override protected String[] edgeNames(Node n) { @@ -21,16 +21,17 @@ public class SimpleGraphAdapter extends GraphAdapter { if( n instanceof LoopNode ) return Kind.LOOP; if( n instanceof RegionNode ) return Kind.REGION; if( n instanceof PhiNode ) return Kind.PHI; - return n.isCFG() ? Kind.CTRL : isMem(n) ? Kind.MEM : Kind.DATA; + return n instanceof CFGNode ? Kind.CTRL : isMem(n) ? Kind.MEM : Kind.DATA; } @Override protected Role role(Node n, int i) { if( n instanceof ScopeNode || n instanceof ConstantNode || n instanceof XCtrlNode ) return Role.ASSOC; if( n instanceof PhiNode ) return i == 0 ? Role.ASSOC : isMem(n) ? Role.MEM : Role.DATA; - if( n instanceof ProjNode || n instanceof CProjNode ) return n.isCFG() ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA; + if( n instanceof ProjNode || n instanceof CProjNode ) + return n instanceof CFGNode ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA; if( n instanceof RegionNode && i == 0 ) return Role.ASSOC; if( i == 0 || n instanceof RegionNode || n instanceof StopNode ) return Role.CTRL; - if( i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode) ) return Role.MEM; + if( i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode || n instanceof NewNode) ) return Role.MEM; Node def = n.in(i); if( def != null && isMem(def) ) return Role.MEM; return Role.DATA; diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index 202aa9d9..450922d7 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 14's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 15's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture { private Parser _parser; private Node _ret; diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java index 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 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(); } // ---------------------------------------------------------- @@ -177,6 +179,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. 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 38b3635a..76288d3e 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -16,49 +16,55 @@ 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 ts) { ts.add(make(1)); ts.add(BOT); } + public static void gather(ArrayList 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) { if( this==BOT ) return sb.append("MemBot"); if( this==TOP ) return sb.append("MemTop"); - 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 e6e40fe2..ceba733d 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 final TypeMemPtr BOT = make(TypeStruct.BOT,true); public static final TypeMemPtr TOP = BOT.dual(); + // An abstract null (can be Struct or Array) or not-null C void* public static final TypeMemPtr NULLPTR = make(TypeStruct.TOP,true); public static final TypeMemPtr VOIDPTR = NULLPTR.dual(); // A bottom mix of not-null ptrs, like C's void* but not null + public static final TypeMemPtr TEST= make(TypeStruct.TEST,false); public static void gather(ArrayList 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 8ad59a39..922b7914 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -8,38 +8,53 @@ import java.util.ArrayList; */ public class TypeStruct extends Type { - // Immutable shallow references, resolved by name in Parser.TYPES when needed. - // A name-only struct has _fields == null, even after its definition is known. - // For LLI { LLI? next; int i; }, L0 is name-only and L1.next points to L0; - // TYPES["LLI"] holds L1. We deliberately stop recursive type expansion here, - // keeping interning and lattice operations finite and acyclic. Never patch - // L0 into L1: field access looks up the complete declaration by name instead. + // A Struct has a name and a set of fields; the fields themselves have + // 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 + // "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 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 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 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++ ) @@ -66,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); } @@ -109,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++ ) @@ -145,4 +165,52 @@ public class TypeStruct extends Type { if( this==TOP ) return "StructTop"; 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]<