diff options
Diffstat (limited to 'chapter16/src/main/java')
17 files changed, 715 insertions, 365 deletions
diff --git a/chapter16/src/main/java/com/seaofnodes/simple/Ary.java b/chapter16/src/main/java/com/seaofnodes/simple/Ary.java new file mode 100644 index 00000000..8654d41e --- /dev/null +++ b/chapter16/src/main/java/com/seaofnodes/simple/Ary.java @@ -0,0 +1,217 @@ +package com.seaofnodes.simple; + +import java.lang.StringBuilder; +import java.lang.reflect.Array; +import java.util.*; + +// ArrayList with saner syntax +public class Ary<E> extends AbstractList<E> implements List<E> { + public E[] _es; + public int _len; + + public Ary(E[] es) { this(es,es.length); } + public Ary(E[] es, int len) { if( es.length==0 ) es=Arrays.copyOf(es,1); _es=es; _len=len; } + @SuppressWarnings("unchecked") + public Ary(Class<E> clazz) { this((E[]) Array.newInstance(clazz, 1),0); } + + /** @return list is empty */ + public boolean isEmpty() { return _len==0; } + /** @return active list length */ + public int len() { return _len; } + public int size() { return len(); } + + /** @param i element index + * @return element being returned; throws if OOB + * @exception AIOOBE if !(0 <= i < _len) + */ + public E get( int i ) { return at(i); } + public E at( int i ) { + range_check(i); + return _es[i]; + } + + /** @return last element */ + public E last( ) { return at(_len-1); } + + /** Add element in amortized constant time + * @param e Element to add at end of list + **/ + public E push( E e ) { + if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); + return (_es[_len++] = e); + } + /** @return remove and return last element */ + public E pop( ) { + range_check(0); + return _es[--_len]; + } + @Override public E removeLast() { return pop(); } + + + /** Add element in amortized constant time + * @param e Element to add at end of list + * @return true */ + public boolean add( E e ) { + if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); + _es[_len++] = e; + return true; + } + + ///** Slow, linear-time, element insert. Preserves order. + // * @param i index to insert at, between 0 and _len inclusive. + // * @param e Element to insert + // */ + //public void insert( int i, E e ) { + // if( i < 0 || i>_len ) + // throw new ArrayIndexOutOfBoundsException(""+i+" >= "+_len); + // if( _len >= _es.length ) _es = Arrays.copyOf(_es,Math.max(1,_es.length<<1)); + // System.arraycopy(_es,i,_es,i+1,(_len++)-i); + // _es[i] = e; + //} + + /** Fast, constant-time, element removal. Does not preserve order + * @param i element to be removed + * @return element removed */ + public E del( int i ) { + range_check(i); + E tmp = _es[i]; + _es[i]=_es[--_len]; + return tmp; + } + + ///** Element removal, using '=='. Does not preserve order. + // * @param e element to be removed + // * @return element removed */ + //public E del( E e ) { + // for( int i=0; i<_len; i++ ) { + // E tmp = _es[i]; + // if( tmp==e ) { + // _es[i]=_es[--_len]; + // return tmp; + // } + // } + // return null; + //} + + /** Slow, linear-time, element removal. Preserves order. + * @param i element to be removed + * @return element removed */ + @Override public E remove( int i ) { + range_check(i); + E e = _es[i]; + System.arraycopy(_es,i+1,_es,i,(--_len)-i); + return e; + } + + /** Remove all elements */ + public void clear( ) { _len=0; } + + /** Set existing element + * @param i element to set + * @param e value to set + * @return old value + * @exception AIOOBE if !(0 <= i < _len) + */ + public E set( int i, E e ) { + range_check(i); + E old = _es[i]; + _es[i] = e; + return old; + } + + public Ary<E> setLen( int len ) { + if( len > _len ) + while( len>= _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + _len = len; + while( _es.length > (len<<1) ) // Shrink if hugely too large + _es = Arrays.copyOf(_es,_es.length>>1); + Arrays.fill(_es,len,_es.length,null); + return this; + } + + /** @param c Collection to be added */ + public boolean addAll( Collection<? extends E> c ) { + if( c==null ) return false; + for( E e : c ) add(e); + return true; + } + public Ary<E> addAll( Iterable<? extends E> it ) { for( E e : it ) add(e); return this; } + + /** @param es Array to be added */ + public <F extends E> Ary<E> addAll( F[] es ) { + if( es==null || es.length==0 ) return this; + while( _len+es.length > _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + System.arraycopy(es,0,_es,_len,es.length); + _len += es.length; + return this; + } + + /** @param c Collection to be added */ + public Ary<E> addAll( Ary<? extends E> c ) { + if( c==null || c._len==0 ) return this; + while( _len+c._len > _es.length ) _es = Arrays.copyOf(_es,_es.length<<1); + System.arraycopy(c._es,0,_es,_len,c._len); + _len += c._len; + return this; + } + + /** @return compact array version */ + public E[] asAry() { return Arrays.copyOf(_es,_len); } + + /** Sorts in-place + * @param c Comparator to sort by */ + public void sort_update(Comparator<? super E> c ) { Arrays.sort(_es, 0, _len, c); } + + /** Find the first matching element using ==, or -1 if none. Note that + * most del calls shuffle the list, so the first element might be random. + * @param e Element to find + * @return index of first matching element, or -1 if none */ + public int find( E e ) { + for( int i=0; i<_len; i++ ) if( _es[i]==e ) return i; + return -1; + } + + + /** @return an iterator */ + @Override public Iterator<E> iterator() { return new Iter(); } + private class Iter implements Iterator<E> { + int _i=0; + @Override public boolean hasNext() { return _i<_len; } + @Override public E next() { return _es[_i++]; } + } + + @Override public String toString() { + StringBuilder sb = new StringBuilder().append('{'); + for( int i=0; i<_len; i++ ) { + if( i>0 ) sb.append(','); + if( _es[i] != null ) sb.append(_es[i].toString()); + } + return sb.append('}').toString(); + } + + private void range_check( int i ) { + if( i < 0 || i>=_len ) + throw new ArrayIndexOutOfBoundsException(""+i+" >= "+_len); + } + + // Note that the hashCode() and equals() are not invariant to changes in the + // underlying array. If the hashCode() is used (e.g., inserting into a + // HashMap) and the then the array changes, the hashCode() will change also. + @Override public boolean equals( Object o ) { + if( this==o ) return true; + if( !(o instanceof Ary ary) ) return false; + if( _len != ary._len ) return false; + if( _es == ary._es ) return true; + for( int i=0; i<_len; i++ ) + if( !(_es[i]==null ? (ary._es[i] == null) : _es[i].equals(ary._es[i])) ) + return false; + return true; + } + @Override public int hashCode( ) { + int sum=_len; + for( int i=0; i<_len; i++ ) + sum += _es[i]==null ? 0 : _es[i].hashCode(); + return sum; + } + +} diff --git a/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 2eac6ccc..d2bbdc1e 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -235,6 +235,7 @@ public abstract class GlobalCodeMotion { break; case LoadNode ld: break; // Loads do not cause anti-deps on other loads case ReturnNode ret: break; // Load must already be ahead of Return + case ScopeMinNode ret: break; // Mem uses now on ScopeMin case NeverNode never: break; default: throw Utils.TODO(); } @@ -249,7 +250,7 @@ public abstract class GlobalCodeMotion { // Store and Load overlap, need anti-dependence if( stblk._anti==load._nid ) { lca = stblk._idom(lca,null); // Raise Loads LCA - if( lca == stblk && st != null && Utils.find(st._inputs,load) == -1 ) // And if something moved, + if( lca == stblk && st != null && st._inputs.find(load) == -1 ) // And if something moved, st.addDef(load); // Add anti-dep as well return lca; // Cap this stores' anti-dep to here } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter16/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index f5fa1350..9e0700d5 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -5,6 +5,8 @@ import com.seaofnodes.simple.node.*; import java.util.*; +import static com.seaofnodes.simple.Utils.TODO; + /** * Simple visualizer that outputs GraphViz dot format. * The dot output must be saved to a file and run manually via dot to generate the SVG output. @@ -155,25 +157,26 @@ public class GraphVisualizer { private void scope( StringBuilder sb, ScopeNode scope ) { sb.append("\tnode [shape=plaintext];\n"); int level=1; - for( int idx = scope._idxs.size()-1; idx>=0; idx-- ) { - var syms = scope._idxs.get(idx); - String scopeName = makeScopeName(scope, level); - sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name - sb.append("\t\t").append(scopeName).append(" [label=<\n"); - sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n"); - // Add the scope level - int scopeLevel = scope._idxs.size()-level; - sb.append("\t\t\t<TR><TD BGCOLOR=\"cyan\">").append(scopeLevel).append("</TD>"); - for(String name: syms.keySet()) - sb.append("<TD PORT=\"").append(makePortName(scopeName, name)).append("\">").append(name).append("</TD>"); - sb.append("</TR>\n"); - sb.append("\t\t\t</TABLE>>];\n"); - level++; - } - // Scope clusters nest, so the graphics shows the nested scopes, so - // they are not closed as they are printed; so they just keep nesting. - // We close them all at once here. - sb.append( "\t}\n".repeat( level-1 ) ); // End all Scope clusters + //for( int idx = scope._idxs.size()-1; idx>=0; idx-- ) { + // var syms = scope._idxs.get(idx); + // String scopeName = makeScopeName(scope, level); + // sb.append("\tsubgraph cluster_").append(scopeName).append(" {\n"); // Magic "cluster_" in the subgraph name + // sb.append("\t\t").append(scopeName).append(" [label=<\n"); + // sb.append("\t\t\t<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\">\n"); + // // Add the scope level + // int scopeLevel = scope._idxs.size()-level; + // sb.append("\t\t\t<TR><TD BGCOLOR=\"cyan\">").append(scopeLevel).append("</TD>"); + // for(String name: syms.keySet()) + // sb.append("<TD PORT=\"").append(makePortName(scopeName, name)).append("\">").append(name).append("</TD>"); + // sb.append("</TR>\n"); + // sb.append("\t\t\t</TABLE>>];\n"); + // level++; + //} + //// Scope clusters nest, so the graphics shows the nested scopes, so + //// they are not closed as they are printed; so they just keep nesting. + //// We close them all at once here. + //sb.append( "\t}\n".repeat( level-1 ) ); // End all Scope clusters + throw TODO(); } private String makeScopeName(ScopeNode sn, int level) { return sn.uniqueName() + "_" + level; } @@ -230,27 +233,28 @@ public class GraphVisualizer { private void scopeEdges( StringBuilder sb, ScopeNode scope ) { sb.append("\tedge [style=dashed color=cornflowerblue];\n"); int level=1; - for( int i = scope._idxs.size()-1; i>=0; i-- ) { - var syms = scope._idxs.get(i); - String scopeName = makeScopeName(scope, level); - for( String name : syms.keySet() ) { - int idx = syms.get(name); - Node def = scope.in(idx); - while( def instanceof ScopeNode lazy ) - def = lazy.in(idx); - if( def==null ) continue; - sb.append("\t") - .append(scopeName).append(":") - .append('"').append(makePortName(scopeName, name)).append('"') // wrap port name with quotes because $ctrl is not valid unquoted - .append(" -> "); - if( def instanceof CProjNode proj ) { - String mname = proj.ctrl().uniqueName(); - sb.append(mname).append(":p").append(proj._idx); - } else sb.append(def.uniqueName()); - sb.append(";\n"); - } - level++; - } + //for( int i = scope._idxs.size()-1; i>=0; i-- ) { + // var syms = scope._idxs.get(i); + // String scopeName = makeScopeName(scope, level); + // for( String name : syms.keySet() ) { + // int idx = syms.get(name); + // Node def = scope.in(idx); + // while( def instanceof ScopeNode lazy ) + // def = lazy.in(idx); + // if( def==null ) continue; + // sb.append("\t") + // .append(scopeName).append(":") + // .append('"').append(makePortName(scopeName, name)).append('"') // wrap port name with quotes because $ctrl is not valid unquoted + // .append(" -> "); + // if( def instanceof CProjNode proj ) { + // String mname = proj.ctrl().uniqueName(); + // sb.append(mname).append(":p").append(proj._idx); + // } else sb.append(def.uniqueName()); + // sb.append(";\n"); + // } + // level++; + //} + throw TODO(); } /** diff --git a/chapter16/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter16/src/main/java/com/seaofnodes/simple/IterPeeps.java index 783fc4f1..96ae350e 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -50,7 +50,7 @@ public abstract class IterPeeps { return (N)WORK.push(n); } - public static void addAll( ArrayList<Node> ary ) { + public static void addAll( Ary<Node> ary ) { WORK.addAll(ary); } @@ -170,7 +170,7 @@ public abstract class IterPeeps { return x; } - public void addAll( ArrayList<E> ary ) { + public void addAll( Ary<E> ary ) { for( E n : ary ) push(n); } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/Parser.java b/chapter16/src/main/java/com/seaofnodes/simple/Parser.java index 572c170a..c77792de 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/Parser.java @@ -2,6 +2,7 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.node.*; import com.seaofnodes.simple.type.*; +import static com.seaofnodes.simple.Utils.TODO; import java.util.*; @@ -124,7 +125,7 @@ public class Parser { _lexer = new Lexer(source); _scope = new ScopeNode(); _continueScope = _breakScope = null; - START = new StartNode(new Type[]{ Type.CONTROL, arg }); + START = new StartNode(arg); STOP = new StopNode(source); ZERO = con(0).keep(); XCTRL= new XCtrlNode().peephole().keep(); @@ -138,13 +139,10 @@ public class Parser { @Override public String toString() { return _lexer.toString(); } - String src() { return new String( _lexer._input ); } - // Debugging utility to find a Node by index public static Node find(int nid) { return START.find(nid); } private Node ctrl() { return _scope.ctrl(); } - private Node ctrl(Node n) { return _scope.ctrl(n); } public StopNode parse() { return parse(false); } @@ -152,8 +150,12 @@ public class Parser { _xScopes.push(_scope); // Enter a new scope for the initial control and arguments _scope.push(); - _scope.define(ScopeNode.CTRL, Type.CONTROL , new CProjNode(START, 0, ScopeNode.CTRL).peephole(), false); - _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 1, ScopeNode.ARG0).peephole(), false); + ScopeMinNode mem = new ScopeMinNode(); + mem.addDef(null); + _scope.define(ScopeNode.CTRL, Type.CONTROL , false, new CProjNode(START, 0, ScopeNode.CTRL).peephole()); + mem.addDef( new ProjNode(START, 1, ScopeNode.MEM0).peephole()); + _scope.define(ScopeNode.MEM0, TypeMem.TOP , false, mem .peephole()); + _scope.define(ScopeNode.ARG0, TypeInteger.BOT, false, new ProjNode(START, 2, ScopeNode.ARG0).peephole()); // Parse whole program parseBlock(); @@ -162,6 +164,9 @@ public class Parser { STOP.addReturn(new ReturnNode(ctrl(), ZERO, _scope).peephole()); _scope.pop(); _xScopes.pop(); + for( StructNode init : INITS.values() ) + init.unkeep().kill(); + INITS.clear(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); STOP.peephole(); if( show ) showGraph(); @@ -298,15 +303,15 @@ 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._idxs.size() > _breakScope._idxs.size() ) + while( cur._lexSize.size() > _breakScope._lexSize.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 // "continue" - if (toScope == null) + if( toScope == null ) return cur; // toScope is either the break scope, or a scope that was created here - assert toScope._idxs.size() <= _breakScope._idxs.size(); + assert toScope._lexSize.size() <= _breakScope._lexSize.size(); toScope.ctrl(toScope.mergeScopes(cur)); return toScope; } @@ -407,7 +412,7 @@ public class Parser { ? Type.TOP // Else takes the default : t.makeInit(); - expr = new ConstantNode(init).peephole(); + expr = con(init); } else if( !match("=") ) { // Something else _lexer._position = old; @@ -418,15 +423,15 @@ public class Parser { // Defining a new variable vs updating an old one if( !isDecl ) { // Assigning over an existing name // Lookup - Node def = _scope.lookup(name); + ScopeMinNode.Var def = _scope.lookup(name); if( def==null ) throw error("Undefined name '" + name + "'"); // TOP fields are for late-initialized fields; these have never // been written to, and this must be the final write. Other writes // need to check the final bit. - if( def._type!=Type.TOP && _scope.lookupFinal(name) ) + if( _scope.in(def._idx)._type!=Type.TOP && def._final ) throw error("Cannot reassign final '"+name+"'"); - t = _scope.lookupDeclaredType(name); + t = def._type; // Declared field type } // Auto-widen int to float @@ -443,7 +448,7 @@ public class Parser { throw error("Type " + e.str() + " is not of declared type " + t.str()); if( isDecl ) { - if( !_scope.define(name,t,expr,xfinal) ) + if( !_scope.define(name,t,xfinal,expr) ) throw error("Redefining name '" + name + "'"); } else _scope.update(name,expr); @@ -501,41 +506,29 @@ public class Parser { if( t!=null && !(t instanceof TypeMemPtr tmp && tmp._obj._fields==null) ) throw errorSyntax("struct '" + typeName + "' cannot be redefined"); - // A Block scope parse, and inspect the scope afterwards for fields. + // A Block scope parse, and inspect the scope afterward for fields. _scope.push(); require("{"); while (!peek('}') && !_lexer.isEOF()) parseStatement(); // Grab the declarations and build fields and a Struct - HashMap<String,Type> decls = _scope._decls.lastElement(); - HashMap<String,Integer> idxs = _scope._idxs.lastElement(); - BitSet finals = _scope._finals; - - StructNode s = new StructNode().keep(); - Field[] fs = new Field[decls.size()]; int i=0; - for( String fname : decls.keySet() ) { - int idx = idxs.get(fname); - boolean isFinal = finals.get(idx); - Type decl = decls.get(fname); - fs[i++] = Field.make(fname,decl,ALIAS++,isFinal); - s.addDef(_scope.in(idx)); + int lexlen = _scope._lexSize.last(); + int varlen = _scope._vars._len; + StructNode s = new StructNode(); + Field[] fs = new Field[varlen-lexlen]; + for( int i=lexlen; i<varlen; i++ ) { + s.addDef(_scope.in(i)); + ScopeMinNode.Var v = _scope._vars.at(i); + fs[i-lexlen] = Field.make(v._name,v._type,ALIAS++,v._final); } + TypeStruct ts = s._ts = TypeStruct.make(typeName, fs); + TYPES.put(typeName, TypeMemPtr.make(ts)); + INITS.put(typeName,(StructNode)s.peephole().keep()); // Done with struct/block scope require("}"); - _scope.pop(); - - // Build and install the TypeStruct - TypeStruct ts = TypeStruct.make(typeName, fs); - TYPES.put(typeName, TypeMemPtr.make(ts)); require(";"); - // Save initial constructor - s._ts = ts; - INITS.put(typeName,(StructNode)s.peephole()); - - // Insert memory edges - START.addMemProj(ts, _scope); - + _scope.pop(); return null; } @@ -588,14 +581,15 @@ public class Parser { 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()+"[]"; + 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++); + assert ts.str().equals(tname); TypeMemPtr tary = TypeMemPtr.make(ts); TYPES.put(tname,tary); - START.addMemProj(ts, _scope); // Insert memory alias edges + //START.addMemProj(ts, _scope); // Insert memory alias edges return tary; } @@ -753,61 +747,72 @@ public class Parser { if( match("(") ) return require(parseExpression(), ")"); if( matchx("true" ) ) return con(1); if( matchx("false") ) return ZERO; - if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole(); - if( matchx("new") ) { - 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 ) { - StructNode s = INITS.get(tmp._obj._name); - if( s==null ) throw error("Unknown struct type '" + tmp._obj._name + "'"); - Field[] fs = s._ts._fields; - // if the object is fully initialized, we can skip a block here. - // Check for constructor block: - boolean hasConstructor = match("{"); - Node init=s; int idx=0; - if( hasConstructor ) { - init = _scope; - idx = _scope.nIns(); - // Push a scope, and pre-assign all struct fields. - _scope.push(); - for( int i=0; i<fs.length; i++ ) - _scope.define(fs[i]._fname, fs[i]._type, s.in(i), fs[i]._final); - // Parse the constructor body - parseBlock(); - require("}"); - } - // Check that all fields are initialized - for( int i=idx; i<init.nIns(); i++ ) - if( init.in(i)._type == Type.TOP ) - throw error("'"+tmp._obj._name+"' is not fully initialized, field '" + fs[i-idx]._fname + "' needs to be set in a constructor"); - Node ptr = newStruct(tmp._obj, init, idx ); - if( hasConstructor ) - _scope.pop(); - return ptr; - } - throw error("Cannot allocate a "+t.str()); - } + if( matchx("null" ) ) return con(TypeMemPtr.NULLPTR); + if( matchx("new" ) ) return alloc(); + // Expect an identifier now String name = _lexer.matchId(); if( name == null) throw errorSyntax("an identifier or expression"); - Node n = _scope.lookup(name); - if( n!=null ) return n; + ScopeMinNode.Var n = _scope.lookup(name); + if( n!=null ) return _scope.in(n); throw error("Undefined name '" + name + "'"); } /** + Parse an allocation + */ + private Node alloc() { + Type t = type(); + if( t==null ) throw error("Expected a type"); + // Parse ary[ length_expr ] + 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) ) + throw error("Cannot allocate a "+t.str()); + + // Parse new struct { default_initialization } + StructNode s = INITS.get(tmp._obj._name); + if( s==null ) throw error("Unknown struct type '" + tmp._obj._name + "'"); + + Field[] fs = s._ts._fields; + // if the object is fully initialized, we can skip a block here. + // Check for constructor block: + boolean hasConstructor = match("{"); + Ary<Node> init=s._inputs; int idx=0; + if( hasConstructor ) { + init = _scope._inputs; + idx = _scope.nIns(); + // Push a scope, and pre-assign all struct fields. + _scope.push(); + for( int i=0; i<fs.length; i++ ) + _scope.define(fs[i]._fname, fs[i]._type, fs[i]._final, s.in(i)); + // Parse the constructor body + parseBlock(); + require("}"); + } + // Check that all fields are initialized + for( int i=idx; i<init.size(); i++ ) + if( init.get(i)._type == Type.TOP ) + throw error("'"+tmp._obj._name+"' is not fully initialized, field '" + fs[i-idx]._fname + "' needs to be set in a constructor"); + Node ptr = newStruct(tmp._obj, con(tmp._obj.offset(fs.length)), idx, init ); + if( hasConstructor ) + _scope.pop(); + return ptr; + } + + + /** * Return a NewNode initialized memory. * @param obj is the declared type, with GLB fields * @param init is a collection of initialized fields */ - private Node newStruct( TypeStruct obj, Node init, int idx ) { + private Node newStruct( TypeStruct obj, Node size, int idx, Ary<Node> init ) { Field[] fs = obj._fields; if( fs==null ) throw error("Unknown struct type '" + obj._name + "'"); @@ -815,36 +820,37 @@ public class Parser { Node[] ns = new Node[2+len+len]; ns[0] = ctrl(); // Control in slot 0 // Total allocated length in bytes - ns[1] = con(obj.offset(len)); + ns[1] = size; // Memory aliases for every field for( int i = 0; i < len; i++ ) ns[2 +i] = memAlias(fs[i]._alias); // Initial values for every field for( int i = 0; i < len; i++ ) - ns[2+len+i] = init.in(i+idx); + ns[2+len+i] = init.get(i+idx); Node nnn = new NewNode(TypeMemPtr.make(obj), ns).peephole(); for( int i = 0; i < len; i++ ) memAlias(fs[i]._alias, new ProjNode(nnn,i+2,memName(fs[i]._alias)).peephole()); return new ProjNode(nnn,1,obj._name).peephole(); } + private static final Ary<Node> ALTMP = new Ary<>(Node.class); 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); + ALTMP.clear(); ALTMP.add(len); ALTMP.add(con(ary._fields[1]._type.makeInit())); + Node ptr = newStruct(ary,size,0,ALTMP); //int alias = ary._fields[0]._alias; // Length alias //memAlias(alias,new StoreNode("#",alias,TypeInteger.BOT,memAlias(alias),ptr,con( ary.offset(0) ), len.unkeep(), true ).peephole()); - //return ptr; - throw Utils.TODO(); + return ptr; } // We set up memory aliases by inserting special vars in the scope these // variables are prefixed by $ so they cannot be referenced in Simple code. // Using vars has the benefit that all the existing machinery of scoping // and phis work as expected - private Node memAlias(int alias ) { return _scope.lookup(memName(alias) ); } - private Node memAlias(int alias, Node st) { return _scope.update(memName(alias), st); } + private Node memAlias(int alias ) { return _scope.mem(alias ); } + private void memAlias(int alias, Node st) { _scope.mem(alias, st); } public static String memName(int alias) { return ("$"+alias).intern(); } /** @@ -942,13 +948,9 @@ public class Parser { * floatLiteral: [digits].[digits]?[e [digits]]? * </pre> */ - private ConstantNode parseLiteral() { - return (ConstantNode) new ConstantNode(_lexer.parseNumber()).peephole(); - } - - public static Node con( long con ) { - return new ConstantNode(TypeInteger.constant(con)).peephole(); - } + private ConstantNode parseLiteral() { return con(_lexer.parseNumber()); } + public static Node con( long con ) { return con(TypeInteger.constant(con)); } + public static ConstantNode con( Type t ) { return (ConstantNode)new ConstantNode(t).peephole(); } ////////////////////////////////// // Utilities for lexical analysis diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java index bc3f4335..be6fba11 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -38,7 +38,6 @@ public class LoadNode extends MemOpNode { if( mem()._type instanceof TypeMem mem && // No constant folding if ptr might null-check _declaredType != mem._t && err()==null ) { - assert mem._alias == _alias; return _declaredType.join(mem._t); } return _declaredType; diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/NewNode.java index c65d7ca5..cb6ee464 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -32,7 +32,10 @@ public class NewNode extends Node implements MultiNode { } @Override public String label() { - return "new_" + (_ptr._obj.isAry() ? "ary_"+_ptr._obj._fields[1]._type.str() : _ptr._obj.str()); + return "new_"+glabel(); + } + @Override public String glabel() { + return _ptr._obj.isAry() ? "ary_"+_ptr._obj._fields[1]._type.str() : _ptr._obj.str(); } @Override @@ -43,10 +46,7 @@ public class NewNode extends Node implements MultiNode { // Find matching alias input Node findAlias(int alias) { - for( int i=0; i<_len; i++ ) - if( ((TypeMem)in(2+i)._type)._alias == alias ) - return in(2+i+_len); - throw Utils.TODO(); // Must find + return in(2+_ptr._obj.findAlias(alias)+_len); } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter16/src/main/java/com/seaofnodes/simple/node/Node.java index e4b887a0..462a403c 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/Node.java @@ -1,11 +1,11 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.Ary; import com.seaofnodes.simple.IRPrinter; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeFloat; - import java.util.*; import java.util.function.Function; @@ -28,9 +28,9 @@ public abstract class Node implements OutNode { * <p> * Generally fixed length, ordered, nulls allowed, no unused trailing space. * Ordering is required because e.g. "a/b" is different from "b/a". - * The first input (offset 0) is often a {@link #isCFG} node. + * The first input (offset 0) is often a {@link CFGNode} node. */ - public final ArrayList<Node> _inputs; + public final Ary<Node> _inputs; /** * Outputs reference Nodes that are not null and have this Node as an @@ -41,7 +41,7 @@ public abstract class Node implements OutNode { * walked in either direction. These outputs are typically used for * efficient optimizations but otherwise have no semantics meaning. */ - public final ArrayList<Node> _outputs; + public final Ary<Node> _outputs; /** @@ -61,9 +61,9 @@ public abstract class Node implements OutNode { protected Node(Node... inputs) { _nid = UNIQUE_ID++; // allocate unique dense ID - _inputs = new ArrayList<>(); + _inputs = new Ary<>(Node.class); Collections.addAll(_inputs,inputs); - _outputs = new ArrayList<>(); + _outputs = new Ary<>(Node.class); for( Node n : _inputs ) if( n != null ) n.addUse( this ); @@ -127,7 +127,7 @@ public abstract class Node implements OutNode { */ public Node in(int i) { return _inputs.get(i); } public Node out(int i) { return _outputs.get(i); } - @Override public ArrayList<Node> outs() { return _outputs; } + @Override public Ary<Node> outs() { return _outputs; } public int nIns() { return _inputs.size(); } @@ -168,7 +168,7 @@ public abstract class Node implements OutNode { old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def moveDepsToWorklist(); - // Return self for easy flow-coding + // Return new_def for easy flow-coding return new_def; } @@ -179,13 +179,20 @@ public abstract class Node implements OutNode { Node delDef(int idx) { unlock(); Node old_def = in(idx); - Utils.del(_inputs, idx); + _inputs.del(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(); return this; } + // Insert the numbered input, sliding other inputs to the right + Node insertDef(int idx, Node new_def) { + _inputs.add(idx,null); + return setDef(idx,new_def); + } + + /** * Add a new def to an existing Node. Keep the edges correct by * adding the corresponding <em>def->use</em> edge. @@ -210,16 +217,16 @@ public abstract class Node implements OutNode { // Return true if the output list is empty afterward. // Error is 'use' does not exist; ok for 'use' to be null. protected boolean delUse( Node use ) { - Utils.del(_outputs, Utils.find(_outputs, use)); + _outputs.del(_outputs.find(use)); return _outputs.isEmpty(); } - // Shortcut for "popping" n nodes. A "pop" is basically a + // Shortcut for "popping" until n nodes. A "pop" is basically a // setDef(last,null) followed by lowering the nIns() count. - void popN(int n) { + void popUntil(int n) { unlock(); - for( int i=0; i<n; i++ ) { - Node old_def = _inputs.removeLast(); + while( nIns() > n ) { + Node old_def = _inputs.pop(); if( old_def != null && // If it exists and old_def.delUse(this) ) // If we removed the last use, the old def is now dead old_def.kill(); // Kill old def @@ -259,7 +266,7 @@ public abstract class Node implements OutNode { return (N)this; } // Test "keep" status - public boolean iskeep() { return Utils.find(_outputs,null) != -1; } + public boolean iskeep() { return _outputs.find(null) != -1; } // Replace self with nnn in the graph, making 'this' go dead @@ -268,7 +275,7 @@ public abstract class Node implements OutNode { while( nOuts() > 0 ) { Node n = _outputs.removeLast(); n.unlock(); - int idx = Utils.find(n._inputs, this); + int idx = n._inputs.find(this); n._inputs.set(idx,nnn); nnn.addUse(n); } @@ -451,7 +458,7 @@ public abstract class Node implements OutNode { // on a node some distance away, and if that node ever changes we should // retry the peephole. Track a set of Nodes dependent on `this`, and // revisit them if `this` changes. - ArrayList<Node> _deps; + Ary<Node> _deps; /** * Add a node to the list of dependencies. Only add it if its not an input @@ -462,10 +469,10 @@ public abstract class Node implements OutNode { // Running peepholes during the big assert cannot have side effects // like adding dependencies. if( IterPeeps.midAssert() ) return this; - if( _deps==null ) _deps = new ArrayList<>(); - if( Utils.find(_deps ,dep) != -1 ) return this; // Already on list - if( Utils.find(_inputs,dep) != -1 ) return this; // No need for deps on immediate neighbors - if( Utils.find(_outputs,dep)!= -1 ) return this; + if( _deps==null ) _deps = new Ary<>(Node.class); + if( _deps .find(dep) != -1 ) return this; // Already on list + if( _inputs .find(dep) != -1 ) return this; // No need for deps on immediate neighbors + if( _outputs.find(dep) != -1 ) return this; _deps.add(dep); return this; } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/OutNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/OutNode.java index 7e531145..dbac136b 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/OutNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/OutNode.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.node; -import java.util.ArrayList; +import com.seaofnodes.simple.Ary; public interface OutNode { - ArrayList<Node> outs(); + Ary<Node> outs(); } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/RegionNode.java index bd05ce01..09a32c95 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -68,7 +68,7 @@ public class RegionNode extends CFGNode { if( !hasPhi() && // No Phi users, just a control user in(1) instanceof CProjNode p1 && in(2) instanceof CProjNode p2 && - p1.in(0)==p2.in(0) && + p1.in(0).addDep(this)==p2.in(0).addDep(this) && p1.in(0) instanceof IfNode iff ) return iff.ctrl(); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index e12f1fef..de4eba52 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -16,17 +16,11 @@ import java.util.BitSet; public class ReturnNode extends CFGNode { public ReturnNode(Node ctrl, Node data, ScopeNode scope) { - super(ctrl, data); // Add memory slices to Return, so all memory updates are live-on-exit. - // We look up memory slices by the naming convention that they start with $. - // We could also use implicit knowledge that all memory projects are at offset >= 2 - if( scope != null ) { - String[] names = scope.reverseNames(); - for (String name: names) { - if (!name.equals("$ctrl") && name.startsWith("$")) - addDef(scope.lookup(name)); - } - } + super(ctrl, data); + if( scope!=null ) + for( int i=2; i<scope.mem().nIns(); i++ ) + addDef(scope.mem().in(i)); } public Node ctrl() { return in(0); } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java new file mode 100644 index 00000000..48f81ddb --- /dev/null +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java @@ -0,0 +1,137 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.type.*; +import java.util.*; + +import static com.seaofnodes.simple.Utils.TODO; + +/* */ +public class ScopeMinNode extends Node { + + /** The tracked fields are now complex enough to deserve a array-of-structs layout + */ + public class Var { + public final int _idx; + public final String _name; + public final Type _type; + public final boolean _final; + public Var(int idx, String name, Type type, boolean xfinal) { + _idx = idx; + _name = name; + _type = type; + _final = xfinal; + } + } + + public ScopeMinNode() { _type = TypeMem.BOT; } + + + @Override public String label() { return "MEM"; } + + @Override + StringBuilder _print1(StringBuilder sb, BitSet visited) { + sb.append("MEM[ "); + for( int j=2; j<nIns(); j++ ) { + sb.append(j); + sb.append(":"); + Node n = in(j); + while( n instanceof ScopeNode loop ) { + sb.append("Lazy_"); + n = loop.in(j); + } + if( n==null ) sb.append("___ "); + else n._print0(sb, visited).append(" "); + } + sb.setLength(sb.length()-1); + return sb.append("]"); + } + + + @Override public Type compute() { return TypeMem.BOT; } + + @Override public Node idealize() { return null; } + + public Node in( Var v ) { return in(v._idx); } + + Node alias( int alias ) { + return in(alias<nIns() && in(alias)!=null ? alias : 1); + } + + Node alias( int alias, Node st ) { + while( alias >= nIns() ) addDef(null); + return setDef(alias,st); + } + + + // Read or update from memory. + // A shared implementation allows us to create lazy phis both during + // lookups and updates; the lazy phi creation is part of chapter 8. + Node _mem( int alias, Node st ) { + // Memory projections are made lazily; if one does not exist + // then it must be START.proj(1) + Node old = alias(alias); + if( old instanceof ScopeNode loop ) { + ScopeMinNode loopmem = loop.mem(); + Node memdef = loopmem.alias(alias); + // Lazy phi! + old = memdef instanceof PhiNode phi && loop.ctrl()==phi.region() + // Loop already has a real Phi, use it + ? memdef + // Set real Phi in the loop head + // The phi takes its one input (no backedge yet) from a recursive + // lookup, which might have insert a Phi in every loop nest. + : loopmem.alias(alias, new PhiNode(Parser.memName(alias), TypeMem.BOT,loop.ctrl(),loopmem._mem(alias,null),null).peephole() ); + alias(alias,old); + } + // Memory projections are made lazily; expand as needed + return st==null ? old : alias(alias,st); // Not lazy, so this is the answer + } + + + void _merge(ScopeMinNode that, RegionNode r) { + int len = Math.max(nIns(),that.nIns()); + for( int i = 2; i < len; i++) + if( alias(i) != that.alias(i) ) { // No need for redundant Phis + // If we are in lazy phi mode we need to a lookup + // by name as it will trigger a phi creation + //Var v = _vars.at(i); + Node lhs = this._mem(i,null); + Node rhs = that._mem(i,null); + alias(i, new PhiNode(Parser.memName(i), TypeMem.BOT, r, lhs, rhs).peephole()); + } + } + + // Fill in the backedge of any inserted Phis + void _endLoopMem( ScopeNode scope, ScopeMinNode back, ScopeMinNode exit ) { + for( int i=2; i<back.nIns(); i++ ) { + if( back.in(i) != scope ) { + PhiNode phi = (PhiNode)in(i); + assert phi.region()==scope.ctrl() && phi.in(2)==null; + phi.setDef(2,back.in(i)); // Fill backedge + } + if( exit.alias(i) == scope ) // Replace a lazy-phi on the exit path also + exit.alias(i,in(i)); + } + } + + // Now one-time do a useless-phi removal + void _useless( ) { + for( int i=2; i<nIns(); i++ ) { + if( in(i) instanceof PhiNode phi ) { + // Do an eager useless-phi removal + Node in = phi.peephole(); + IterPeeps.addAll(phi._outputs); + phi.moveDepsToWorklist(); + if( in != phi ) { + if( !phi.iskeep() ) // Keeping phi around for parser elsewhere + phi.subsume(in); + setDef(i,in); // Set the update back into Scope + } + } + } + } + +} diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 5842f5b5..388a2760 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -3,14 +3,17 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.Ary; import com.seaofnodes.simple.type.*; import java.util.*; +import static com.seaofnodes.simple.Utils.TODO; + /** * The Scope node is purely a parser helper - it tracks names to nodes with a * stack of hashmaps. */ -public class ScopeNode extends Node { +public class ScopeNode extends ScopeMinNode { /** * The control is a name that binds to the currently active control @@ -18,51 +21,49 @@ public class ScopeNode extends Node { */ public static final String CTRL = "$ctrl"; public static final String ARG0 = "arg"; + public static final String MEM0 = "$mem"; - /** - * Map variable names to Scope input edge - */ - public final Stack<HashMap<String, Integer>> _idxs; + // All active/live variables in all nested scopes, all run together + public final Ary<Var> _vars; - /* - * Map input edge to Final bit - */ - public final BitSet _finals; + // Since of each nested lexical scope + public final Ary<Integer> _lexSize; - /** - * Map variable names to declared Type - */ - public final Stack<HashMap<String, Type>> _decls; // A new ScopeNode - public ScopeNode() { - _idxs = new Stack<>(); - _decls= new Stack<>(); - _finals = new BitSet(); - _type = Type.BOTTOM; - } + public ScopeNode() { _vars = new Ary<>(Var.class); _lexSize = new Ary<>(Integer.class); } @Override public String label() { return "Scope"; } + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { sb.append("Scope[ "); - String[] names = reverseNames(); - for( int j=0; j<nIns(); j++ ) { - sb.append(names[j]).append(":"); - Node n = in(j); + int j=1; + for( int i=0; i<nIns(); i++ ) { + if( j < _lexSize._len && i == _lexSize.at(j) ) { sb.append("| "); j++; } + Var v = _vars.get(i); + v._type.print(sb); + sb.append(" "); + if( v._final ) sb.append("!"); + sb.append(v._name); + sb.append("="); + Node n = in(i); while( n instanceof ScopeNode loop ) { sb.append("Lazy_"); - n = loop.in(j); + n = loop.in(i); } if( n==null ) sb.append("___"); - else n._print0(sb, visited).append(" "); + else n._print0(sb, visited); + sb.append(", "); } - sb.setLength(sb.length()-1); + sb.setLength(sb.length()-2); return sb.append("]"); } + public Node ctrl() { return in(0); } + public ScopeMinNode mem() { return (ScopeMinNode)in(1); } /** * The ctrl of a ScopeNode is always bound to the currently active @@ -76,106 +77,85 @@ public class ScopeNode extends Node { */ 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 - * inputs to the Node. - * - * This is an expensive operation. - */ - public String[] reverseNames() { - String[] names = new String[nIns()]; - for( HashMap<String,Integer> syms : _idxs ) - for( String name : syms.keySet() ) - names[syms.get(name)] = name; - return names; + public void push() { + _lexSize.push(_vars.size()); } - - @Override public Type compute() { return Type.BOTTOM; } - - @Override public Node idealize() { return null; } - - public void push() { _idxs.push(new HashMap<>()); _decls.push(new HashMap<>()); } public void pop() { - popN(_idxs.pop().size()); - _finals.clear(nIns()); - _decls.pop(); + int n = _lexSize.pop(); + popUntil(n); + _vars.setLen(n); + } + + // Find name in reverse, return an index into _vars or -1. Linear scan + // instead of hashtable, but probably doesn't matter until the scan + // typically hits many dozens of variables. + int find( String name ) { + for( int i=_vars.size()-1; i>=0; i-- ) + if( _vars.get(i)._name.equals(name) ) + return i; + return -1; } /** * Create a new variable name in the current scope */ - public boolean define( String name, Type declaredType, Node n, boolean xfinal ) { - HashMap<String,Integer> syms = _idxs.lastElement(); - _decls.lastElement().put(name,declaredType); - if( syms.put(name,nIns()) != null ) - return false; // Double define - if( xfinal ) _finals.set(nIns()); // track finals - addDef(n); + public boolean define( String name, Type declaredType, boolean xfinal, Node init ) { + assert name.charAt(0)!='$' || _lexSize.size()==1; // Later scopes do not define memory + if( _lexSize._len > 1 ) + for( int i=_vars.size()-1; i>=_lexSize.last(); i-- ) + if( _vars.get(i)._name.equals(name) ) + return false; // Double define + _vars.add(new Var(nIns(),name,declaredType,xfinal)); + addDef(init); return true; } + // Read from memory + public Node mem( int alias ) { return mem()._mem(alias,null); } + // Write to memory + public void mem( int alias, Node st ) { mem()._mem(alias,st); } + + /** * Lookup a name in all scopes starting from most deeply nested. * * @param name Name to be looked up - * @see #update(String, Node, int) + * @return null if not found, or the implementing Node */ - public Node lookup( String name ) { return update(name,null,_idxs.size()-1); } + public Var lookup( String name ) { + int idx = find(name); + // -1 is missed in all scopes, not found + return idx == -1 ? null : _update(_vars.at(idx),null); + } + /** * 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,_idxs.size()-1); } - /** - * Both recursive lookup and update. - * <p> - * A shared implementation allows us to create lazy phis both during - * lookups and updates; the lazy phi creation is part of chapter 8. - * - * @param name Name whose binding is being updated or looked up - * @param n If null, do a lookup, else update binding - * @param nestingLevel The starting nesting level - * @return node being looked up, or the one that was updated - */ - private Node update( String name, Node n, int nestingLevel ) { - if( nestingLevel<0 ) return null; // Missed in all scopes, not found - 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); + public void update( String name, Node n ) { + int idx = find(name); + assert idx>=0; + _update(_vars.at(idx),n); + } + + Var _update( ScopeNode.Var v, Node st ) { + Node old = in(v._idx); if( old instanceof ScopeNode loop ) { // Lazy Phi! - old = loop.in(idx) instanceof PhiNode phi && loop.ctrl()==phi.region() + Node def = loop.in(v._idx); + old = def instanceof PhiNode phi && loop.ctrl()==phi.region() // Loop already has a real Phi, use it - ? loop.in(idx) + ? def // Set real Phi in the loop head // The phi takes its one input (no backedge yet) from a recursive // lookup, which might have insert a Phi in every loop nest. - : loop.setDef(idx,new PhiNode(name, lookupDeclaredType(name),loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); - setDef(idx,old); + : loop.setDef(v._idx,new PhiNode(v._name, v._type, loop.ctrl(), loop.in(loop._update(v,null)._idx),null).peephole()); + setDef(v._idx,old); } - return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer - } - - // Return declared type for a variable - public Type lookupDeclaredType( String name ) { - for( int i=_decls.size(); i>0; i-- ) { - Type t = _decls.get(i-1).get(name); - if( t != null ) return t; - } - return null; - } - - // Return declared type for a variable - public boolean lookupFinal( String name ) { - for( int i=_idxs.size(); i>0; i-- ) { - Integer t = _idxs.get(i-1).get(name); - if( t != null ) return _finals.get(t); - } - throw Utils.TODO(); // Should not reach here + if( st!=null ) setDef(v._idx,st); // Set new value + return v; } /** @@ -198,13 +178,22 @@ public class ScopeNode extends Node { // 1) duplicate the name bindings of the ScopeNode across all stack levels // 2) Make the new ScopeNode a user of all the nodes bound // 3) Ensure that the order of defs is the same to allow easy merging - for( HashMap<String,Integer> syms : _idxs ) - dup._idxs.push(new HashMap<>(syms)); - for( HashMap<String,Type> ts : _decls ) - dup._decls.push(ts); // Types don't change, just keep stacks aligned - + dup._vars.addAll(_vars); + dup._lexSize.addAll(_lexSize); dup.addDef(ctrl()); // Control input is just copied - for( int i=1; i<nIns(); i++ ) + + // Memory input is a shallow copy + ScopeMinNode memdup = new ScopeMinNode(), mem = mem(); + memdup.addDef(null); + memdup.addDef(loop ? this : mem.in(1)); + for( int i=2; i<mem.nIns(); i++ ) + // For lazy phis on loops we use a sentinel + // that will trigger phi creation on update + memdup.addDef(loop ? this : mem.in(i)); + dup.addDef(memdup); + + // Copy of other inputs + for( int i=2; i<nIns(); i++ ) // For lazy phis on loops we use a sentinel // that will trigger phi creation on update dup.addDef(loop ? this : in(i)); @@ -221,49 +210,55 @@ public class ScopeNode extends Node { */ public Node mergeScopes(ScopeNode that) { RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep()); - String[] ns = reverseNames(); - // Note that we skip i==0, which is bound to '$ctrl' - for (int i = 1; i < nIns(); i++) - if( in(i) != that.in(i) ) // No need for redundant Phis - // If we are in lazy phi mode we need to a lookup - // by name as it will trigger a phi creation - setDef(i, new PhiNode(ns[i], this.lookupDeclaredType(ns[i]), r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); + mem()._merge(that.mem(),r); + this ._merge(that ,r); that.kill(); // Kill merged scope IterPeeps.add(r); return r.unkeep().peephole(); } - // Merge the backedge scope into this loop head scope + private void _merge(ScopeNode that, RegionNode r) { + for( int i = 2; i < nIns(); i++) + if( in(i) != that.in(i) ) { // No need for redundant Phis + // If we are in lazy phi mode we need to a lookup + // by name as it will trigger a phi creation + Var v = _vars.at(i); + Node lhs = this.in(this._update(v,null)); + Node rhs = that.in(that._update(v,null)); + setDef(i, new PhiNode(v._name, v._type, r, lhs, rhs).peephole()); + } + } + + // peephole the backedge scope into this loop head scope // We set the second input to the phi from the back edge (i.e. loop body) public void endLoop(ScopeNode back, ScopeNode exit ) { Node ctrl = ctrl(); assert ctrl instanceof LoopNode loop && loop.inProgress(); ctrl.setDef(2,back.ctrl()); - for( int i=1; i<nIns(); i++ ) { - if( back.in(i) != this ) { - PhiNode phi = (PhiNode)in(i); - assert phi.region()==ctrl && phi.in(2)==null; - phi.setDef(2,back.in(i)); - } - if( exit.in(i) == this ) // Replace a lazy-phi on the exit path also - exit.setDef(i,in(i)); - } + + mem()._endLoopMem( this, back.mem(), exit.mem() ); + this ._endLoop ( this, back , exit ); back.kill(); // Loop backedge is dead // Now one-time do a useless-phi removal - for( int i=1; i<nIns(); i++ ) { - if( in(i) instanceof PhiNode phi ) { - // Do an eager useless-phi removal - Node in = phi.peephole(); - IterPeeps.addAll(phi._outputs); - phi.moveDepsToWorklist(); - if( in != phi ) { - if( !phi.iskeep() ) // Keeping phi around for parser elsewhere - phi.subsume(in); - setDef(i,in); // Set the update back into Scope - } + mem()._useless(); + this ._useless(); + + // The exit mem's lazy default value had been the loop top, + // now it goes back to predating the loop. + exit.mem().setDef(1,mem().in(1)); + } + + // Fill in the backedge of any inserted Phis + void _endLoop( ScopeNode scope, Node back, Node exit ) { + for( int i=2; i<nIns(); i++ ) { + if( back.in(i) != scope ) { + PhiNode phi = (PhiNode)in(i); + assert phi.region()==scope.ctrl() && phi.in(2)==null; + phi.setDef(2,back.in(i)); // Fill backedge } + if( exit.in(i) == scope ) // Replace a lazy-phi on the exit path also + exit.setDef(i,in(i)); } - } @@ -279,7 +274,7 @@ public class ScopeNode extends Node { pred = pred instanceof NotNode not ? not.in(1) : IterPeeps.add(new NotNode(pred).peephole()); // Direct use of a value as predicate. This is a zero/null test. - if( Utils.find(_inputs, pred) != -1 ) { + if( _inputs.find(pred) != -1 ) { if( !(pred._type instanceof TypeMemPtr tmp) ) // Must be an `int`, since int and ptr are the only two value types // being tested. No representation for a generic not-null int, so no upcast. @@ -292,7 +287,7 @@ public class ScopeNode extends Node { if( pred instanceof NotNode not ) { // Direct use of a !value as predicate. This is a zero/null test. - if( Utils.find(_inputs, not.in(1)) != -1 ) { + if( _inputs.find(not.in(1)) != -1 ) { Type tinit = not.in(1)._type.makeInit(); if( not.in(1)._type.isa(tinit) ) return null; // Already zero/null, no reason to upcast return replace(not.in(1), new ConstantNode(tinit).peephole()); diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/StartNode.java index bbeb7fa1..c03a4b06 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.simple.type.*; import java.util.Arrays; import java.util.BitSet; import java.util.HashSet; +import static com.seaofnodes.simple.Utils.TODO; /** * The Start node represents the start of the function. @@ -15,41 +16,9 @@ import java.util.HashSet; */ public class StartNode extends CFGNode implements MultiNode { - // This field is NOT final, because the tuple expands as we add memory aliases - TypeTuple _args; + final Type _arg; - public StartNode(Type[] args) { - super(); - _args = TypeTuple.make(args); - _type = _args; - } - - /** - * Creates a projection for each of the struct's fields, using the field alias - * as the key. - */ - public void addMemProj( TypeStruct ts, ScopeNode scope) { - if( ts._fields.length==0 ) return; - // Expand args type for more memory projections - Type[] args = _args._types; - int max = args.length; - for( Field f : ts._fields ) - max = Math.max(max,f._alias); - args = Arrays.copyOf(args, max+1); - // For each of the fields we now add a mem projection. - for( Field f : ts._fields ) { - TypeMem tm_decl = TypeMem.make(f._alias,f._type.glb()); - args[f._alias] = tm_decl.dual(); - String name = Parser.memName(f._alias); - Node n = new ProjNode(this, f._alias, name); // No 'compute' until ScopeNode gets typed - n._type = args[f._alias]; - scope.define(name, tm_decl, n, false); - } - for (int i = 0; i < args.length; i++) - if (args[i] == null) - args[i] = Type.TOP; // We parsed a nested struct/array. Avoid nulls until a caller replaces this alias. - _type = _args = TypeTuple.make(args); - } + public StartNode(Type arg) { super(); _arg = arg; _type = compute(); } @Override public String label() { return "Start"; } @@ -62,11 +31,11 @@ public class StartNode extends CFGNode implements MultiNode { @Override public boolean blockHead() { return true; } @Override public CFGNode cfg0() { return this; } - @Override - public TypeTuple compute() { return _args; } + @Override public TypeTuple compute() { + return TypeTuple.make(Type.CONTROL,TypeMem.TOP,_arg); + } - @Override - public Node idealize() { return null; } + @Override public Node idealize() { return null; } // No immediate dominator, and idepth==0 @Override public int idepth() { return 0; } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/StructNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/StructNode.java index 69e9f444..4583e1ae 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/StructNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/StructNode.java @@ -33,9 +33,22 @@ public class StructNode extends Node { return null; } - // Sample field not initialized + // If this is a mem struct, then alias inputs are made lazily. + // If missing, use Start.Mem instead. + Node alias( int alias ) { + return in( alias >= nIns() || in(alias)==null ? 1 : alias ); + } + + Node alias( int alias, Node st ) { + while( alias >= nIns() ) + addDef(null); + return setDef(alias,st); + } + + @Override public TypeStruct compute() { + if( _ts==null ) return TypeStruct.BOT; Field[] fs = new Field[_ts._fields.length]; for( int i=0; i<fs.length; i++ ) fs[i] = _ts._fields[i].makeFrom(in(i)==null ? Type.TOP : in(i)._type); @@ -49,5 +62,5 @@ public class StructNode extends Node { boolean eq(Node n) { return _ts == ((StructNode)n)._ts; } @Override - int hash() { return _ts.hashCode(); } + int hash() { return _ts==null ? 0 : _ts.hashCode(); } } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter16/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index fbbb814f..4e4d1305 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -41,7 +41,7 @@ public class TypeStruct extends Type { // Array public static TypeStruct makeAry(TypeInteger len, int lenAlias, Type body, int bodyAlias) { assert !(body instanceof TypeMemPtr tmp && !tmp._nil); - return make(body.str() + "[]", + return make("[" + body.str() + "]", Field.make("#" ,len , lenAlias,true), Field.make("[]",body,bodyAlias,true)); } @@ -56,6 +56,7 @@ public class TypeStruct extends Type { public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); ts.add(ARY); } + // Find field index by name public int find(String fname) { for( int i=0; i<_fields.length; i++ ) if( _fields[i]._fname.equals(fname) ) @@ -63,6 +64,15 @@ public class TypeStruct extends Type { return -1; } + // Find field index by alias + public int findAlias( int alias ) { + for( int i=0; i<_fields.length; i++ ) + if( _fields[i]._alias==alias ) + return i; + return -1; + } + + @Override Type xmeet(Type t) { TypeStruct that = (TypeStruct) t; @@ -150,10 +160,10 @@ public class TypeStruct extends Type { public StringBuilder print(StringBuilder sb) { sb.append(_name); if( _fields == null ) return sb; // Forward reference struct, just print the name - sb.append(" {\n"); + sb.append(" {"); for( Field f : _fields ) { sb.append(" ").append(f._fname).append(" :"); - f._type.print(sb).append(";\n"); + f._type.print(sb).append("; "); } return sb.append("}"); } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter16/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index 59ddf34b..a34c64db 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -7,15 +7,17 @@ public class TypeTuple extends Type { public final Type[] _types; private TypeTuple(Type[] types) { super(TTUPLE); _types = types; } - public static TypeTuple make(Type... types) { return new TypeTuple(types).intern(); } + public static TypeTuple make(Type... types) { return new TypeTuple(types).intern(); } - private static TypeTuple TEST = make(TypeInteger.BOT,TypeMemPtr.TEST); - public static void gather(ArrayList<Type> ts) { ts.add(TEST); } + private static final TypeTuple TEST = make(TypeInteger.BOT,TypeMemPtr.TEST); + public static final TypeTuple START = make(Type.CONTROL,TypeMem.TOP,TypeInteger.BOT); + public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(START); } @Override Type xmeet(Type other) { TypeTuple tt = (TypeTuple)other; // contract from xmeet - assert _types.length == tt._types.length; + if( _types.length != tt._types.length ) + return BOTTOM; Type[] ts = new Type[_types.length]; for( int i=0; i<_types.length; i++ ) ts[i] = _types[i].meet(tt._types[i]); |