diff options
Diffstat (limited to 'chapter17/src/main/java/com')
17 files changed, 86 insertions, 113 deletions
diff --git a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java index d2a1a9ae..9710be30 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java @@ -96,7 +96,7 @@ public class Parser { // Mapping from a type name to a Type. The string name matches // `type.str()` call. No TypeMemPtrs are in here, because Simple does not // have C-style '*ptr' references. - public final HashMap<String, Type> TYPES; + public static HashMap<String, Type> TYPES; // Mapping from a type name to the constructor for a Type. public final HashMap<String, StructNode> INITS; @@ -267,6 +267,7 @@ public class Parser { // the loop predicate. Note that body Scope is still our current scope. ctrl(ifF); _xScopes.push(_breakScope = _scope.dup()); + _breakScope.upcast(ifF,pred,true); // Up-cast predicate // No continues yet _continueScope = null; @@ -274,6 +275,7 @@ public class Parser { // Parse the true side, which corresponds to loop body // Our current scope is the body Scope ctrl(ifT.unkeep()); // set ctrl token to ifTrue projection + _scope.upcast(ifT,pred,false); // Up-cast predicate parseStatement(); // Parse loop body // Merge the loop bottom into other continue statements @@ -302,7 +304,8 @@ public class Parser { // the scope is the exit scope after the exit test. _xScopes.pop(); _xScopes.push(exit); - return _scope = exit; + _scope = exit; + return _scope; } private ScopeNode jumpTo(ScopeNode toScope) { @@ -438,7 +441,7 @@ public class Parser { // need to check the final bit. if( _scope.in(def._idx)._type!=Type.TOP && def._final ) throw error("Cannot reassign final '"+name+"'"); - t = def._type; // Declared field type + t = def.type(); // Declared field type } // Auto-widen int to float @@ -527,7 +530,7 @@ public class Parser { 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); + 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)); @@ -550,7 +553,7 @@ public class Parser { if( tname==null ) return null; // Convert the type name to a type. Type t0 = TYPES.get(tname); - Type t1 = t0 == null ? TypeMemPtr.make(TypeStruct.make(tname)) : t0; // Null: assume a forward ref type + Type t1 = t0 == null ? TypeMemPtr.make(TypeStruct.makeFRef(tname)) : t0; // Null: assume a forward ref type // Nest arrays and '?' as needed while( true ) { assert !(t1 instanceof TypeStruct); @@ -744,23 +747,33 @@ public class Parser { * Parse a primary expression: * * <pre> - * primaryExpr : integerLiteral | Identifier | true | false | null | new Type | '(' expression ')' + * primaryExpr : integerLiteral | true | false | null | new Type | '(' expression ')' | Id['++','--'] * </pre> * @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { if( _lexer.isNumber(_lexer.peek()) ) return parseLiteral(); - if( match("(") ) return require(parseExpression(), ")"); if( matchx("true" ) ) return con(1); if( matchx("false") ) return ZERO; if( matchx("null" ) ) return con(TypeMemPtr.NULLPTR); + if( match("(") ) return require(parseExpression(), ")"); if( matchx("new" ) ) return alloc(); // Expect an identifier now - String name = _lexer.matchId(); - if( name == null) throw errorSyntax("an identifier or expression"); - ScopeMinNode.Var n = _scope.lookup(name); - if( n!=null ) return _scope.in(n); - throw error("Undefined name '" + name + "'"); + ScopeMinNode.Var n = requireLookupId("an identifier or expression"); + Node rvalue = _scope.in(n).keep(); + if( matchx("++") ) _scope.update(n,new AddNode(rvalue,con( 1)).peephole()); + if( matchx("--") ) _scope.update(n,new AddNode(rvalue,con(-1)).peephole()); + return rvalue.unkeep(); + } + + ScopeMinNode.Var requireLookupId(String msg) { + String id = _lexer.matchId(); + if( id == null || KEYWORDS.contains(id) ) + throw errorSyntax(msg); + ScopeMinNode.Var n = _scope.lookup(id); + if( n==null ) + throw error("Undefined name '" + id + "'"); + return n; } /** diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/CProjNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/CProjNode.java index 3d6fd1fa..d2f1bbe1 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/CProjNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/CProjNode.java @@ -52,10 +52,6 @@ public class CProjNode extends CFGNode { } @Override - public Node getBlockStart() { - return ctrl() instanceof IfNode ? this : ctrl().getBlockStart(); - } - @Override boolean eq( Node n ) { return _idx == ((CProjNode)n)._idx; } @Override diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/IfNode.java index 3cce89ab..41de4c82 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -66,6 +66,4 @@ public class IfNode extends CFGNode implements MultiNode { unreach.add((CProjNode)proj); super._walkUnreach(visit,unreach); } - - @Override public Node getBlockStart() { return ctrl().getBlockStart(); } } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java index d15d4f83..2c0afda2 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -33,10 +33,13 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { - if( mem()._type instanceof TypeMem mem && - // No constant folding if ptr might null-check - _declaredType != mem._t && err()==null ) { - return _declaredType.join(mem._t); + if( mem()._type instanceof TypeMem mem ) { + // Update declared forward ref to the actual + if( _declaredType.isFRef() && mem._t instanceof TypeMemPtr tmp && !tmp.isFRef() ) + _declaredType = tmp; + // No lifting if ptr might null-check + if( err()==null ) + return _declaredType.join(mem._t); } return _declaredType; } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index c7a1efec..82aab8ac 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -1,6 +1,5 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.type.Field; import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMemPtr; @@ -11,7 +10,9 @@ public abstract class MemOpNode extends Node { public final String _name; public final int _alias; - public final Type _declaredType; + // Declared type; not final because it might be a forward-reference + // which will be lazily improved when the reference is declared. + public Type _declaredType; public MemOpNode(String name, int alias, Type glb, Node mem, Node ptr, Node off) { super(null, mem, ptr, off); diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java index 462a403c..c67fb910 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java @@ -278,6 +278,7 @@ public abstract class Node implements OutNode { int idx = n._inputs.find(this); n._inputs.set(idx,nnn); nnn.addUse(n); + IterPeeps.addAll(n._outputs); } kill(); } @@ -419,7 +420,7 @@ public abstract class Node implements OutNode { * And more folding: * <pre> ary + ((idx<<2) + 16)</pre> * And during code-gen: - * <pre> MOV4 Rary,Ridx,16 // or some such hardware-specific notation </pre> + * <pre> MOV4 Rary,[Ridx<<2 +16] // or some such hardware-specific notation </pre> * <p> * {@link #idealize} has a very specific calling convention: * <ul> @@ -542,9 +543,6 @@ public abstract class Node implements OutNode { /** Is this Node Memory related */ public boolean isMem() { return false; } - /** Return block start from a isCFG() */ - public Node getBlockStart() { return null; } - /** Pinned in the schedule; these are data nodes whose input#0 is not allowed to change */ public boolean isPinned() { return false; } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 941de76b..a55bb479 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -72,65 +72,9 @@ public class RegionNode extends CFGNode { p1.in(0) instanceof IfNode iff ) return iff.ctrl(); - - // Look for direct uses of a guarded expression, and replace with the guard result. - if( !(idom() instanceof StartNode) && // Dead or dying - !(this instanceof LoopNode) ) { - VISIT.clear(); - boolean progress = false; - outer: - for( int i=1; i<nIns(); i++ ) { - CFGNode idom = cfg(i); - while( !(idom instanceof CProjNode cproj) ) { - idom = idom.idom(); - if( idom==null || idom.idepth() < idom().idepth() ) - continue outer; - } - if( cproj.cfg0() instanceof IfNode iff && cproj.compute()==Type.CONTROL ) { - VISIT.set(iff.pred()._nid); - for( Node out : _outputs ) - if( out instanceof PhiNode phi ) - progress |= walk(iff,cproj,phi.in(i)); - } - } - if( progress ) - return this; - } - return null; } - // A walk that can be cutoff early - private static final BitSet VISIT = new BitSet(); - private boolean walk( IfNode iff, CProjNode cproj, Node n ) { - if( VISIT.get(n._nid) ) return false; - VISIT.set(n._nid); - if( n instanceof CFGNode ) return false; - if( n.in(0)!=null && n.cfg0().idepth() < iff.idepth() ) - return false; - boolean progress = false; - Node pred = iff.pred(); - if( pred._type.isHighOrConst() ) return false; // This will collapse the IF already - for( int i=1; i<n.nIns(); i++ ) { - // Using a tested value - if( n.in(i) == pred && !(n instanceof CastNode) ) { - // Checking pred for T/F - Type t = pred._type; - Type tcast = cproj._idx==0 ? t.nonZero() : t.makeInit(); - if( t!=tcast ) { // Progress to cast - Node cast = new CastNode( tcast, cproj, pred ).peephole(); - n.setDef( i, cast ); - IterPeeps.add(n); - progress = true; - } else pred.addDep( this ); - } - if( n.in(i)!=null ) - progress |= walk(iff,cproj,n.in(i)); - } - return progress; - } - - private int findDeadInput() { for( int i=1; i<nIns(); i++ ) if( in(i)._type==Type.XCONTROL ) @@ -180,6 +124,4 @@ public class RegionNode extends CFGNode { @Override boolean eq( Node n ) { return !inProgress(); } - - @Override public Node getBlockStart() { return this; } } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index de4eba52..b586a44f 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -47,6 +47,4 @@ public class ReturnNode extends CFGNode { return ctrl(); return null; } - - @Override public Node getBlockStart() { return ctrl().getBlockStart(); } } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java index e4874e15..c51349fa 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java @@ -14,16 +14,28 @@ public class ScopeMinNode extends Node { /** The tracked fields are now complex enough to deserve a array-of-structs layout */ public static class Var { - public final int _idx; - public final String _name; - public final Type _type; - public final boolean _final; + public final int _idx; // index in containing scope + public final String _name; // Declared name + private Type _type; // Declared type + public final boolean _final; // Final field public Var(int idx, String name, Type type, boolean xfinal) { _idx = idx; _name = name; _type = type; _final = xfinal; } + public Type type() { + if( !_type.isFRef() ) return _type; + Type def = Parser.TYPES.get(((TypeMemPtr)_type)._obj._name); + return (_type=_type.meet(def)); + } + public Type glb() { + Type t = type(); + return t instanceof TypeMemPtr ? t : t.glb(); + } + @Override public String toString() { + return _type.toString()+(_final ? " !": " ")+_name; + } } public ScopeMinNode() { _type = TypeMem.BOT; } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 11e54d82..f7446c51 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -43,7 +43,7 @@ public class ScopeNode extends ScopeMinNode { 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); + v.type().print(sb); sb.append(" "); if( v._final ) sb.append("!"); sb.append(v._name); @@ -125,7 +125,7 @@ public class ScopeNode extends ScopeMinNode { 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); + return idx == -1 ? null : update(_vars.at(idx),null); } /** @@ -137,10 +137,10 @@ public class ScopeNode extends ScopeMinNode { public void update( String name, Node n ) { int idx = find(name); assert idx>=0; - _update(_vars.at(idx),n); + update(_vars.at(idx),n); } - Var _update( ScopeNode.Var v, Node st ) { + public Var update( ScopeNode.Var v, Node st ) { Node old = in(v._idx); if( old instanceof ScopeNode loop ) { // Lazy Phi! @@ -151,7 +151,7 @@ public class ScopeNode extends ScopeMinNode { // 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(v._idx,new PhiNode(v._name, v._type instanceof TypeMemPtr ? v._type : v._type.glb(), loop.ctrl(), loop.in(loop._update(v,null)._idx),null).peephole()); + : loop.setDef(v._idx,new PhiNode(v._name, v.glb(), loop.ctrl(), loop.in(loop.update(v,null)._idx),null).peephole()); setDef(v._idx,old); } if( st!=null ) setDef(v._idx,st); // Set new value @@ -223,9 +223,9 @@ public class ScopeNode extends ScopeMinNode { // 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()); + 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()); } } @@ -268,6 +268,8 @@ public class ScopeNode extends ScopeMinNode { // This Scope looks for direct variable uses, or certain simple // combinations, and replaces the variable with the upcast variant. public Node upcast( Node ctrl, Node pred, boolean invert ) { + if( ctrl._type == Type.XCONTROL || pred.isDead() ) + return null; // Dead, do not do anything // Invert the If conditional if( invert ) pred = pred instanceof NotNode not ? not.in(1) : IterPeeps.add(new NotNode(pred).peephole()); diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/ShlNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/ShlNode.java index b67d985a..6fd951e4 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/ShlNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/ShlNode.java @@ -44,7 +44,7 @@ public class ShlNode extends Node { if( (shl.value()&63)==0 ) return lhs; // (x + c) << i => (x << i) + (c << i) - if( lhs instanceof AddNode add && add.in(2)._type instanceof TypeInteger c && c.isConstant() && c!=TypeInteger.ZERO ) { + if( lhs instanceof AddNode add && add.addDep(this).in(2)._type instanceof TypeInteger c && c.isConstant() && c!=TypeInteger.ZERO ) { long sum = c.value() << shl.value(); if( Integer.MIN_VALUE <= sum && sum <= Integer.MAX_VALUE ) return new AddNode( new ShlNode(add.in(1),rhs).peephole(), Parser.con(sum) ); diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/StartNode.java index c03a4b06..d82030f8 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -44,6 +44,4 @@ public class StartNode extends CFGNode implements MultiNode { @Override void _walkUnreach( BitSet visit, HashSet<CFGNode> unreach ) { } @Override public int loopDepth() { return (_loopDepth=1); } - - @Override public Node getBlockStart() { return this; } } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java index 0eacc1f4..5a02190a 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -84,6 +84,4 @@ public class StopNode extends CFGNode { GlobalCodeMotion.buildCFG(this); return this; } - - @Override public Node getBlockStart() { return this; } } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 7b1bddd5..8e3e6693 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -42,9 +42,15 @@ public class StoreNode extends MemOpNode { public Type compute() { Type val = val()._type; TypeMem mem = (TypeMem)mem()._type; // Invariant - Type t = mem._alias==_alias - ? val.meet(mem._t) // Meet into existing memory - : Type.BOTTOM; + Type t = Type.BOTTOM; // No idea on field contents + // Same alias, lift val to the declared type and then meet into other fields + if( mem._alias == _alias ) { + // Update declared forward ref to the actual + if( _declaredType.isFRef() && val instanceof TypeMemPtr tmp && !tmp.isFRef() ) + _declaredType = tmp; + val = val.join(_declaredType); + t = val.meet(mem._t); + } return TypeMem.make(_alias,t); } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java index 989eff9e..7467be79 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/type/Type.java @@ -179,6 +179,9 @@ public class Type { */ public Type glb() { return _type==TCTRL ? XCONTROL : BOTTOM; } + // Is forward-reference + public boolean isFRef() { return false; } + // ---------------------------------------------------------- // Size in bits to hold an instance of this type. diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index ec059b8f..449bf89e 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -57,6 +57,8 @@ public class TypeMemPtr extends Type { @Override public TypeMemPtr glb() { return make(_obj.glb(),true); } + // Is forward-reference + @Override public boolean isFRef() { return _obj.isFRef(); } @Override public TypeMemPtr makeInit() { return NULLPTR; } @Override public Type nonZero() { return VOIDPTR; } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 4e4d1305..39011ce2 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -36,7 +36,7 @@ public class TypeStruct extends Type { public static final TypeStruct BOT = make("$BOT",new Field[0]); public static final TypeStruct TEST = make("test",new Field[]{Field.TEST}); // Forward-ref version - public static TypeStruct make(String name) { return make(name, (Field[])null); } + public static TypeStruct makeFRef(String name) { return make(name, (Field[])null); } // Array public static TypeStruct makeAry(TypeInteger len, int lenAlias, Type body, int bodyAlias) { @@ -47,8 +47,8 @@ public class TypeStruct extends Type { } // A pair of self-cyclic types - private static final TypeStruct S1F = make("S1"); - private static final TypeStruct S2F = make("S2"); + private static final TypeStruct S1F = makeFRef("S1"); + private static final TypeStruct S2F = makeFRef("S2"); public static final TypeStruct S1 = make("S1", new Field[]{ Field.make("a", TypeInteger.BOT, -1, false), Field.make("s2",TypeMemPtr.make(S2F,false),-2, false) }); private static final TypeStruct S2 = make("S2", new Field[]{ Field.make("b", TypeFloat .BOT, -3, false), Field.make("s1",TypeMemPtr.make(S1F,false),-4, false) }); @@ -89,8 +89,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; + if( this._fields==null ) return that; + if( that._fields==null ) return this; if( _fields.length != that._fields.length ) return BOT; // Just do field meets Field[] flds = new Field[_fields.length]; @@ -132,6 +132,9 @@ public class TypeStruct extends Type { return true; } + // Is forward-reference + @Override public boolean isFRef() { return _fields==null; } + @Override boolean eq(Type t) { TypeStruct ts = (TypeStruct)t; // Invariant |