diff options
Diffstat (limited to 'src/main/java/com/seaofnodes')
22 files changed, 225 insertions, 136 deletions
diff --git a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 4e0a31d5..8a96e69c 100644 --- a/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/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/src/main/java/com/seaofnodes/simple/IterPeeps.java b/src/main/java/com/seaofnodes/simple/IterPeeps.java index 121d0233..783fc4f1 100644 --- a/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/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/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 1a223726..71bd6d02 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -179,7 +179,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()+"'"); @@ -191,25 +191,26 @@ public class Parser { * Only allowed in top level scope. * Structs cannot be redefined. * - * @return The statement following the struct + * @return null */ private Node parseStruct() { if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope"); String typeName = requireId(); - if ( TYPES.containsKey(typeName)) throw errorSyntax("struct '" + typeName + "' cannot be redefined"); + Type t = TYPES.get(typeName); + if( t!=null && !(t instanceof TypeStruct ts && ts._fields==null) ) throw errorSyntax("struct '" + typeName + "' cannot be redefined"); 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(); + return null; } /** @@ -350,8 +351,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; } @@ -433,24 +434,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; } @@ -567,7 +580,8 @@ public class Parser { if( matchx("new") ) { String structName = requireId(); Type t = TYPES.get(structName); - if( t == null || !(t instanceof TypeStruct obj) ) throw errorSyntax("Unknown struct type '" + structName + "'"); + if( !(t instanceof TypeStruct obj) || obj._fields==null ) + throw error("Unknown struct type '" + structName + "'"); return newStruct(obj); } String name = _lexer.matchId(); @@ -584,7 +598,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, ctrl(), memAlias(alias), n, ZERO).peephole()); + memAlias(alias, new StoreNode(field._fname, alias, field._type, ctrl(), memAlias(alias), n, new ConstantNode(field._type.makeInit()).peephole(),true).peephole()); alias++; } return n.unkeep(); @@ -614,7 +628,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; @@ -623,13 +639,14 @@ public class Parser { if( peek('=') ) _lexer._position--; else { Node val = parseExpression(); - memAlias(alias, new StoreNode(name, alias, ctrl(), memAlias(alias), expr, val).peephole()); + Type glb = base._fields[idx]._type; + memAlias(alias, new StoreNode(name, alias,glb, ctrl(), memAlias(alias), expr, val, false).peephole()); return expr; // "obj.a = expr" returns the expression while updating memory } } - Type declaredType = ptr._obj._fields[idx]._type; - return parsePostfix(new LoadNode(name, alias, declaredType, memAlias(alias), expr).peephole()); + Type declaredType = base._fields[idx]._type; + return parsePostfix(new LoadNode(name, alias, declaredType.glb(), memAlias(alias), expr).peephole()); } /** @@ -637,7 +654,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/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index 48350957..67eacd3a 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -173,4 +173,9 @@ public class AddNode extends Node { @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } @Override Node copyF() { return new AddFNode(null,null); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/CastNode.java b/src/main/java/com/seaofnodes/simple/node/CastNode.java index fec540f7..fbf0e518 100644 --- a/src/main/java/com/seaofnodes/simple/node/CastNode.java +++ b/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/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 31edb848..bbd0ce8a 100644 --- a/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/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/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 244a0919..a033a7cf 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/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; @@ -12,7 +11,6 @@ import java.util.BitSet; */ public class LoadNode extends MemOpNode { - Type _declaredType; /** * Load a value from a ptr.field. * @@ -21,15 +19,11 @@ public class LoadNode extends MemOpNode { * @param memPtr The ptr to the struct from where we load a field */ public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) { - super(name, alias, null, memSlice, memPtr); - _declaredType = glb; + super(name, alias, glb, null, memSlice, memPtr); } - @Override - public String label() { return "Load"; } - - @Override - public String glabel() { return "."+_name; } + @Override public String label() { return _name; } + @Override public String glabel() { return "."+_name; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(".").append(_name); } diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 551d2aa9..95319c24 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -11,11 +11,14 @@ public abstract class MemOpNode extends Node { public final String _name; public final int _alias; + public final Type _declaredType; - public MemOpNode(String name, int alias, Node... nodes) { + + public MemOpNode(String name, int alias, Type glb, Node... nodes ) { super(nodes); _name = name; _alias = alias; + _declaredType = glb; } public Node mem() { return in(1); } diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 8c8a6e0a..16915a1c 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -55,4 +55,9 @@ public class MulNode extends Node { } @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } @Override Node copyF() { return new MulFNode(null,null); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + 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 52282737..d846fcef 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -137,7 +137,7 @@ public abstract class Node implements OutNode { public boolean isUnused() { return nOuts() == 0; } - public CFGNode cfg0() { return (CFGNode)in(0); } + public CFGNode cfg0() { return (CFGNode)in(0); } /** * Change a <em>def</em> into a Node. Keeps the edges correct, by removing diff --git a/src/main/java/com/seaofnodes/simple/node/StopNode.java b/src/main/java/com/seaofnodes/simple/node/StopNode.java index ab567bae..0eacc1f4 100644 --- a/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/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/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index db8e2ce6..57e8b3ad 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -11,22 +11,23 @@ import java.util.BitSet; */ 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 value Value to be stored */ - public StoreNode(String name, int alias, Node ctrl, Node memSlice, Node memPtr, Node value) { - super(name, alias, ctrl, memSlice, memPtr, value); + 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); + _init = init; } - @Override - public String label() { return "Store"; } - @Override - public String glabel() { return "."+_name+" ="; } - @Override - public boolean isMem() { return true; } + @Override public String label() { return "." +_name+"="; } + @Override public String glabel() { return "." +_name+"="; } + @Override public boolean isMem() { return true; } + public Node val() { return in(3); } @Override @@ -67,4 +68,11 @@ public class StoreNode extends MemOpNode { return false; } + @Override + 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; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/SubFNode.java b/src/main/java/com/seaofnodes/simple/node/SubFNode.java index b591718d..682930e0 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubFNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubFNode.java @@ -34,7 +34,7 @@ public class SubFNode extends Node { Node lhs = in(1); Type t2 = in(2)._type; - // Sub of 0. + // Sub of 1. if ( t2.isConstant() && t2 instanceof TypeFloat i && i.value()==0 ) return lhs; diff --git a/src/main/java/com/seaofnodes/simple/node/SubNode.java b/src/main/java/com/seaofnodes/simple/node/SubNode.java index f0c77743..81cc6076 100644 --- a/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -37,6 +37,7 @@ public class SubNode extends Node { @Override public Node idealize() { + // x - (-y) is x+y if( in(2) instanceof MinusNode minus ) return new AddNode(in(1),minus.in(1)); diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java index e1c337d4..b2c006dd 100644 --- a/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/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/src/main/java/com/seaofnodes/simple/type/Type.java b/src/main/java/com/seaofnodes/simple/type/Type.java index f3152719..1f211430 100644 --- a/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/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/src/main/java/com/seaofnodes/simple/type/TypeFloat.java b/src/main/java/com/seaofnodes/simple/type/TypeFloat.java index 36bc61f5..738aebc9 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFloat.java +++ b/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/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index f2a93a3a..8c77672b 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/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/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 198d49ee..b2d081f4 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/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/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 9392da20..81725a87 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -13,21 +13,27 @@ import java.util.ArrayList; */ public class TypeMemPtr extends Type { // A TypeMemPtr is pair (obj,nil) - // where obj is one of - // (null,TypeStruct). - // where nil is one of - // (true,false) meaning an explicit null is allowed or not + // where obj is a TypeStruct, possibly TypeStruct.BOT + // where nil is an explicit null is allowed or not - public final TypeStruct _obj; // null, a TypeStruct, or sentinel TypeStruct.MANY + // Examples: + // (Person,false) - a not-nil Person + // (Person,true ) - a Person or a nil + // (BOT ,false) - a not-nil void* (unspecified struct) + // (TOP ,true ) - a nil + + public final TypeStruct _obj; public final boolean _nil; private TypeMemPtr(TypeStruct obj, boolean nil) { super(TMEMPTR); + assert obj!=null; _obj = obj; _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 final TypeMemPtr BOT = make(TypeStruct.BOT,true); public static final TypeMemPtr TOP = BOT.dual(); @@ -43,17 +49,14 @@ public class TypeMemPtr extends Type { } @Override - public TypeMemPtr dual() { return TypeMemPtr.make(_obj==null ? null : _obj.dual(), !_nil); } + public TypeMemPtr dual() { return TypeMemPtr.make(_obj.dual(), !_nil); } @Override - public Type glb() { - if( _obj==null ) return BOT; - return make(_obj.glb(),true); - } + public Type glb() { return make(_obj.glb(),true); } @Override public TypeMemPtr makeInit() { return NULLPTR; } @Override - int hash() { return (_obj==null ? 0xDEADBEEF : _obj.hashCode()) ^ (_nil ? 1024 : 0); } + int hash() { return _obj.hashCode() ^ (_nil ? 1024 : 0); } @Override boolean eq(Type t) { @@ -63,10 +66,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/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 29102675..e2489d6f 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/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/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 01bcbe9f..783f3f60 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/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 |