diff options
Diffstat (limited to 'chapter13/src/main/java')
16 files changed, 169 insertions, 107 deletions
diff --git a/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 4e0a31d5..8a96e69c 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple; +import com.seaofnodes.simple.IterPeeps.WorkList; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; import java.util.*; @@ -12,14 +13,14 @@ public abstract class GlobalCodeMotion { public static void buildCFG( StopNode stop ) { schedEarly(); Parser.SCHEDULED = true; - schedLate(Parser.START); + schedLate( stop); } // ------------------------------------------------------------------------ // Backwards walk on the CFG only, looking for unreachable code - which has // to be an infinite loop. Insert a bogus never-taken exit to Stop, so the // loop becomes reachable. Also, set loop nesting depth - static void fixLoops(StopNode stop) { + public static void fixLoops(StopNode stop) { // Backwards walk from Stop, looking for unreachable code BitSet visit = new BitSet(); HashSet<CFGNode> unreach = new HashSet<>(); @@ -54,6 +55,10 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ + // Visit all nodes in CFG Reverse Post-Order, essentially defs before uses + // (except at loops). Since defs are visited first - and hoisted as early + // as possible, when we come to a use we place it just after its deepest + // input. private static void schedEarly() { ArrayList<CFGNode> rpo = new ArrayList<>(); BitSet visit = new BitSet(); @@ -110,38 +115,60 @@ public abstract class GlobalCodeMotion { } // ------------------------------------------------------------------------ - private static void schedLate(StartNode start) { + private static void schedLate( StopNode stop) { CFGNode[] late = new CFGNode[Node.UID()]; Node[] ns = new Node[Node.UID()]; - _schedLate(start,ns,late); + // Breadth-first scheduling + breadth(stop,ns,late); + + // Copy the best placement choice into the control slot for( int i=0; i<late.length; i++ ) if( ns[i] != null ) ns[i].setDef(0,late[i]); } - // Forwards post-order pass. Schedule all outputs first, then draw a - // idom-tree line from the LCA of uses to the early schedule. Schedule is - // legal anywhere on this line; pick the most control-dependent (largest - // idepth) in the shallowest loop nest. - private static void _schedLate(Node n, Node[] ns, CFGNode[] late) { - if( late[n._nid]!=null ) return; // Been there, done that - // 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); - if( n instanceof PhiNode phi ) late[n._nid] = phi.region(); - - // Walk Stores before Loads, so we can get the anti-deps right - for( Node use : n._outputs ) - if( isForwardsEdge(use,n) && - use._type instanceof TypeMem ) - _schedLate(use,ns,late); - // Walk everybody now - for( Node use : n._outputs ) - if( isForwardsEdge(use,n) ) - _schedLate(use,ns,late); - // Already implicitly scheduled - if( n.isPinned() ) return; - // Need to schedule n + private static void breadth(Node stop, Node[] ns, CFGNode[] late) { + // Things on the worklist have some (but perhaps not all) uses done. + WorkList<Node> work = new WorkList<>(); + work.push(stop); + Node n; + outer: + while( (n = work.pop()) != null ) { + assert late[n._nid]==null; // No double visit + // 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 { + + // All uses done? + for( Node use : n._outputs ) + if( 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 ) + continue outer; + + // All uses done, schedule + _doSchedLate(n,ns,late); + } + + // Walk all inputs and put on worklist, as their last-use might now be done + for( Node def : n._inputs ) + if( def!=null && late[def._nid]==null ) { + work.push(def); + // if the def has a load use, maybe the load can fire + for( Node ld : def._outputs ) + if( ld instanceof LoadNode && late[ld._nid]==null ) + work.push(ld); + } + } + } + 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); assert early != null; @@ -154,7 +181,7 @@ public abstract class GlobalCodeMotion { lca = find_anti_dep(lca,load,early,late); // Walk up from the LCA to the early, looking for best place. This is - // lowest execution frequency, approximated by least loop depth and + // the lowest execution frequency, approximated by least loop depth and // deepest control flow. CFGNode best = lca; lca = lca.idom(); // Already found best for starting LCA @@ -187,12 +214,6 @@ public abstract class GlobalCodeMotion { (lca.idepth() > best.idepth() || best instanceof IfNode); } - // Skip iteration if a backedge - private static boolean isForwardsEdge(Node use, Node def) { - return use != null && def != null && - !(use.nIns()>2 && use.in(2)==def && (use instanceof LoopNode || (use instanceof PhiNode phi && phi.region() instanceof LoopNode))); - } - private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices @@ -202,6 +223,7 @@ public abstract class GlobalCodeMotion { for( Node mem : load.mem()._outputs ) { switch( mem ) { case StoreNode st: + assert late[st._nid]!=null; lca = anti_dep(load,late[st._nid],st.cfg0(),lca,st); break; case PhiNode phi: diff --git a/chapter13/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter13/src/main/java/com/seaofnodes/simple/IterPeeps.java index 121d0233..783fc4f1 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -57,7 +57,7 @@ public abstract class IterPeeps { /** * Iterate peepholes to a fixed point */ - public static StopNode iterate(StopNode stop, boolean show) { + public static StopNode iterate(StopNode stop) { assert progressOnList(stop); int cnt=0; @@ -92,11 +92,6 @@ public abstract class IterPeeps { n.kill(); // Just plain dead } - // Break infinite loops, forcing a Never-branch to exit - GlobalCodeMotion.fixLoops(stop); - if( show ) - System.out.println(new GraphVisualizer().generateDotOutput(stop,null,null)); - GlobalCodeMotion.buildCFG(stop); return stop; } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/Parser.java b/chapter13/src/main/java/com/seaofnodes/simple/Parser.java index 9182a74c..56c8e955 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/Parser.java @@ -178,7 +178,7 @@ public class Parser { * type IDENTIFIER ; * </pre> */ - private Field parseField(String sname) { + private Field parseField() { Type t = type(); if( t==null ) throw errorSyntax("Requires a field type, found '"+_lexer.getAnyNextToken()+"'"); @@ -199,14 +199,14 @@ public class Parser { ArrayList<Field> fields = new ArrayList<>(); require("{"); while (!peek('}') && !_lexer.isEOF()) { - Field field = parseField(typeName); + Field field = parseField(); if (fields.contains(field)) throw errorSyntax("Field '" + field + "' already defined in struct '" + typeName + "'"); fields.add(field); } 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 + TYPES.put(typeName, ts); START.addMemProj(ts, _scope); // Insert memory edges return parseStatement(); } @@ -349,8 +349,8 @@ public class Parser { // Parse the false side _scope = fScope; // Restore scope, then parse else block if any ctrl(ifF.unkeep()); // Ctrl token is now set to ifFalse projection + _scope.upcast(ifF,pred,true); // Up-cast predicate if (matchx("else")) { - _scope.upcast(ifF,pred,true); // Up-cast predicate parseStatement(); fScope = _scope; } @@ -432,24 +432,36 @@ public class Parser { // Auto-widen int to float if( expr._type instanceof TypeInteger && t instanceof TypeFloat ) expr = new ToFloatNode(expr).peephole(); + // 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)); // Type is sane - if( !expr._type.isa(t) ) - throw error("Type " + expr._type.str() + " is not of declared type " + t.str()); + if( !e.isa(t) ) + throw error("Type " + e.str() + " is not of declared type " + t.str()); return _scope.update(name,expr); } - // Parse a type-or-null + // Parse a "type id" and return "type" (and re-parse "id" in caller) or + // return null. private Type type() { int old = _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 ) { - // Not a type; unwind the parse - _lexer._position = old; - return 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,match("?")) : t; + return t instanceof TypeStruct obj ? TypeMemPtr.make(obj,nullable) : t; } @@ -583,7 +595,7 @@ public class Parser { 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, memAlias(alias), n, ZERO).peephole()); + memAlias(alias, new StoreNode(field._fname, alias, memAlias(alias), n, new ConstantNode(field._type.makeInit()).peephole()).peephole()); alias++; } return n.unkeep(); @@ -613,7 +625,9 @@ public class Parser { String name = requireId().intern(); if( expr._type == TypeMemPtr.TOP ) throw error("Accessing field '" + name + "' from null"); - int idx = ptr._obj==null ? -1 : ptr._obj.find(name); + if( ptr._obj == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); + TypeStruct base = (TypeStruct)TYPES.get(ptr._obj._name); + int idx = base==null ? -1 : base.find(name); if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); int alias = START._aliasStarts.get(ptr._obj._name)+idx; @@ -627,7 +641,7 @@ public class Parser { } } - Type declaredType = ptr._obj._fields[idx]._type; + Type declaredType = base._fields[idx]._type; return parsePostfix(new LoadNode(name, alias, declaredType, memAlias(alias), expr).peephole()); } @@ -636,7 +650,7 @@ public class Parser { * * <pre> * integerLiteral: [1-9][0-9]* | [0] - * floatLiteral: [1-9][0-9]* | [0] + * floatLiteral: [digits].[digits]?[e [digits]]? * </pre> */ private ConstantNode parseLiteral() { diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/CastNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/CastNode.java index fec540f7..fbf0e518 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/CastNode.java @@ -22,6 +22,9 @@ public class CastNode extends Node { public String uniqueName() { return "Cast_" + _nid; } @Override + public boolean isPinned() { return true; } + + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return in(1)._print0(sb.append(label()), visited); } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index cf1a76b0..016b0b9b 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -32,7 +32,7 @@ public class ConstantNode extends Node { @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { - return _con._print(sb); + return _con.print(sb); } @Override public boolean isMultiTail() { return true; } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 95d49662..e235cc36 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -2,7 +2,6 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; -import com.seaofnodes.simple.type.Field; import java.util.BitSet; @@ -26,10 +25,7 @@ public class LoadNode extends MemOpNode { } @Override - public String label() { return "Load"; } - - @Override - public String glabel() { return "."+_name; } + public String label() { return "."+_name; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(".").append(_name); } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/StopNode.java index ab567bae..0eacc1f4 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.GlobalCodeMotion; +import com.seaofnodes.simple.GraphVisualizer; import java.util.BitSet; @@ -67,13 +69,21 @@ public class StopNode extends CFGNode { return addDef(node); } - public StopNode iterate( ) { return IterPeeps.iterate(this,false).typeCheck(); } - public StopNode iterate(boolean show) { return IterPeeps.iterate(this,show ).typeCheck(); } + public StopNode iterate( ) { return IterPeeps.iterate(this).typeCheck().GCM(false); } + public StopNode iterate(boolean show) { return IterPeeps.iterate(this).typeCheck().GCM(show ); } StopNode typeCheck() { String err = walk( Node::err ); if( err != null ) throw new RuntimeException(err); return this; } + StopNode GCM(boolean show) { + // Break infinite loops, forcing a Never-branch to exit + GlobalCodeMotion.fixLoops(this); + if( show ) + System.out.println(new GraphVisualizer().generateDotOutput(this,null,null)); + GlobalCodeMotion.buildCFG(this); + return this; + } @Override public Node getBlockStart() { return this; } } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter13/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 7c41e767..2b4a46dd 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -22,9 +22,7 @@ public class StoreNode extends MemOpNode { } @Override - public String label() { return "Store"; } - @Override - public String glabel() { return "."+_name+" ="; } + public String label() { return "."+_name+"="; } @Override public boolean isMem() { return true; } public Node val() { return in(3); } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/type/Field.java b/chapter13/src/main/java/com/seaofnodes/simple/type/Field.java index e1c337d4..b2c006dd 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/type/Field.java @@ -52,8 +52,8 @@ public class Field extends Type { @Override - public StringBuilder _print( StringBuilder sb ) { - return _type._print(sb.append(_fname).append(":")); + public StringBuilder print( StringBuilder sb ) { + return _type.print(sb.append(_fname).append(" :")); } @Override public String str() { return _fname; } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter13/src/main/java/com/seaofnodes/simple/type/Type.java index f3152719..1f211430 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/type/Type.java @@ -76,20 +76,22 @@ public class Type { /** * Display Type name in a format that's good for IR printer */ - public StringBuilder typeName( StringBuilder sb) { return _print(sb); } + public StringBuilder typeName( StringBuilder sb) { return print(sb); } public Type makeInit() { return null; } // ---------------------------------------------------------- - // Notes on Type interning. - // At the moment it is not easy to reset the interned types - // because we hold static references to several types and these are scattered - // around. This means the INTERN cache will retain all types from - // every run of the Parser. For this to work correctly types must be - // rigorous about defining when they are the same. Also types need to be - // immutable once defined. - // The rationale for interning is performance. + // Notes on Type interning: At the moment it is not easy to reset the + // interned types because we hold static references to several types and + // these are scattered around. This means the INTERN cache will retain all + // types from every run of the Parser. For this to work correctly types + // must be rigorous about defining when they are the same. Also types need + // to be immutable once defined. The rationale for interning is + // *correctness* with cyclic type definitions. Simple structural recursive + // checks go exponential with merely sharing, but with cycles they will + // stack overflow and crash. Intering means we do not need to have sharing + // checks with every type compare, only during interning. // Factory method which interns "this" public <T extends Type> T intern() { @@ -178,10 +180,10 @@ public class Type { // This is a more verbose dev-friendly print. @Override public final String toString() { - return _print(new StringBuilder()).toString(); + return print(new StringBuilder()).toString(); } - public StringBuilder _print(StringBuilder sb) { return is_simple() ? sb.append(STRS[_type]) : sb;} + public StringBuilder print(StringBuilder sb) { return is_simple() ? sb.append(STRS[_type]) : sb;} // This is used by error messages, and is a shorted print. public String str() { return STRS[_type]; } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeFloat.java index 36bc61f5..738aebc9 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeFloat.java @@ -35,7 +35,7 @@ public class TypeFloat extends Type { // FIXME this display format is problematic // In visualizer '#' gets prepended if its a constant @Override - public StringBuilder _print(StringBuilder sb) { + public StringBuilder print(StringBuilder sb) { if( this==TOP ) return sb.append("FltTop"); if( this==BOT ) return sb.append("FltBot"); return sb.append(_con); diff --git a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index f2a93a3a..8c77672b 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -35,7 +35,7 @@ public class TypeInteger extends Type { // FIXME this display format is problematic // In visualizer '#' gets prepended if its a constant @Override - public StringBuilder _print(StringBuilder sb) { + public StringBuilder print(StringBuilder sb) { if( this==TOP ) return sb.append("IntTop"); if( this==BOT ) return sb.append("IntBot"); return sb.append(_con); diff --git a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 198d49ee..b2d081f4 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -15,7 +15,7 @@ public class TypeMem extends Type { // 0 means TOP, no slice. // -1 means BOT, all memory. // N means slice#N. - private final int _alias; + public final int _alias; private TypeMem(int alias) { super(TMEM); _alias = alias; } @@ -23,7 +23,6 @@ public class TypeMem extends Type { public static final TypeMem TOP = make( 0); public static final TypeMem BOT = make(-1); - public static void gather(ArrayList<Type> ts) { ts.add(make(1)); ts.add(BOT); } @Override @@ -40,7 +39,7 @@ public class TypeMem extends Type { } @Override - public Type glb() { return TypeMem.BOT; } + public Type glb() { return make(_alias); } @Override int hash() { return 9876543 + _alias; } @@ -52,7 +51,7 @@ public class TypeMem extends Type { } @Override - public StringBuilder _print(StringBuilder sb) { + public StringBuilder print(StringBuilder sb) { return sb.append("MEM#").append( switch(_alias) { case 0 -> "TOP"; case -1 -> "BOT"; @@ -60,5 +59,5 @@ public class TypeMem extends Type { }); } - @Override public String str() { return _print(new StringBuilder()).toString(); } + @Override public String str() { return toString(); } } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 65352402..1ad65611 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -27,7 +27,8 @@ public class TypeMemPtr extends Type { _nil = nil; } public static TypeMemPtr make(TypeStruct obj, boolean nil) { return new TypeMemPtr(obj, nil).intern(); } - public static TypeMemPtr make(TypeStruct obj) { return TypeMemPtr.make(obj, false); } + public static TypeMemPtr make(TypeStruct obj) { return make(obj, false); } + public TypeMemPtr make_from(TypeStruct obj) { return make(obj, _nil); } public static TypeMemPtr BOT = make(TypeStruct.BOT,true); public static TypeMemPtr TOP = BOT.dual(); @@ -63,10 +64,10 @@ public class TypeMemPtr extends Type { // [void,name,MANY]*[,?] @Override - public StringBuilder _print(StringBuilder sb) { + public StringBuilder print(StringBuilder sb) { if( this== NULLPTR) return sb.append("null"); if( this== VOIDPTR) return sb.append("*void"); - return _obj._print(sb.append("*")).append(_nil ? "?" : ""); + return _obj.print(sb.append("*")).append(_nil ? "?" : ""); } @Override public String str() { diff --git a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 29102675..e2489d6f 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -8,9 +8,14 @@ import java.util.ArrayList; */ public class TypeStruct extends Type { - // For now in terms of the lattice - // a struct type just stays as is - + // 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. + // Its illegal to attempt to load a field from a forward-ref struct. + // + // 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; @@ -20,13 +25,23 @@ public class TypeStruct extends Type { _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 final TypeStruct TEST = make("test",new Field[]{Field.TEST}); - public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); } + + // A pair of self-cyclic types + private static final TypeStruct S1F = make("S1"); + private static final TypeStruct S2F = make("S2"); + public static final TypeStruct S1 = make("S1", new Field[]{ Field.make("a", TypeInteger.BOT), Field.make("s2",TypeMemPtr.make(S2F,false)) }); + private static final TypeStruct S2 = make("S2", new Field[]{ Field.make("b", TypeFloat .BOT), Field.make("s1",TypeMemPtr.make(S1F,false)) }); + public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); } public int find(String fname) { for( int i=0; i<_fields.length; i++ ) @@ -51,6 +66,8 @@ public class TypeStruct extends Type { // And the answer is: "don't ask". if( !_name.equals(that._name) ) return BOT; // It's a struct; that's about all we know + if( this._fields==null ) return this; + if( that._fields==null ) return that; // Now all fields should be the same, so just do field meets assert _fields.length == that._fields.length; Field[] flds = new Field[_fields.length]; @@ -63,6 +80,7 @@ public class TypeStruct extends Type { public TypeStruct dual() { if( this==TOP ) return BOT; if( this==BOT ) return TOP; + if( _fields == null ) return this; Field[] flds = new Field[_fields.length]; for( int i=0; i<_fields.length; i++ ) flds[i] = _fields[i].dual(); @@ -80,9 +98,10 @@ public class TypeStruct extends Type { return make(_name,flds); } private boolean _glb() { - for( Field f : _fields ) - if( f.glb() != f ) - return false; + if( _fields!=null ) + for( Field f : _fields ) + if( f.glb() != f ) + return false; return true; } @@ -91,6 +110,7 @@ public class TypeStruct extends Type { TypeStruct ts = (TypeStruct)t; // Invariant if( !_name.equals(ts._name) ) return false; + if( _fields == ts._fields ) return true; if( _fields.length!=ts._fields.length ) return false; for( int i = 0; i < _fields.length; i++ ) @@ -102,17 +122,20 @@ public class TypeStruct extends Type { @Override int hash() { long hash = _name.hashCode(); - for( Field f : _fields ) hash = Utils.rot(hash,13) ^ f.hashCode(); + if( _fields != null ) + for( Field f : _fields ) + hash = Utils.rot(hash,13) ^ f.hashCode(); return Utils.fold(hash); } @Override - public StringBuilder _print(StringBuilder sb) { - sb.append(_name).append(" {\n"); + public StringBuilder print(StringBuilder sb) { + sb.append(_name); + if( _fields == null ) return sb; // Forward reference struct, just print the name + sb.append(" {\n"); for( Field f : _fields ) { - sb.append(" ").append(f._fname).append(":"); - f._type._print(sb); - sb.append(";\n"); + sb.append(" ").append(f._fname).append(" :"); + f._type.print(sb).append(";\n"); } return sb.append("}"); } diff --git a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 01bcbe9f..783f3f60 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -37,17 +37,16 @@ public class TypeTuple extends Type { return make(ts); } - @Override - public StringBuilder _print(StringBuilder sb) { - sb.append("["); + @Override public StringBuilder print(StringBuilder sb) { + sb.append("[ "); for( Type t : _types ) - t._print(sb).append(","); - sb.setLength(sb.length()-1); + t.print(sb).append(", "); + sb.setLength(sb.length()-2); sb.append("]"); return sb; } - @Override public String str() { return _print(new StringBuilder()).toString(); } + @Override public String str() { return print(new StringBuilder()).toString(); } /** * Display Type name in a format that's good for IR printer |