diff options
Diffstat (limited to 'chapter17')
27 files changed, 965 insertions, 402 deletions
diff --git a/chapter17/README.md b/chapter17/README.md index cdbca21b..a3a2d992 100644 --- a/chapter17/README.md +++ b/chapter17/README.md @@ -165,3 +165,18 @@ for( int i=0; i<ary#; i++ ) return i; return -1; ``` + +## Memory effects + +The lazy memory representation from [Chapter 10b](../chapter10b/README.md) and +constructor layout from [Chapter 16](../chapter16/README.md#memory-through-constructors) +continue here. ScopeNode tracks one `$mem` binding. Field and array writes, +including increments, update their alias in a MemMerge. Branches, conditional +expressions, and loops merge whole memory with BulkMemPhi; MemPhis are discovered +as field uses require them. + +Readonly references retain their deep immutability when Loads fold through +Stores or allocations. Forward reference types still resolve lazily. Phi +factoring uses the same one-step Load safety check. Allocation memory remains +shared across the struct's aliases, so the sole-use Store-to-New check may +leave a Load that separate memory projections allowed to fold. diff --git a/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index ee6e1f1a..eba99128 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -109,12 +109,8 @@ public abstract class GlobalCodeMotion { // Loads need their memory inputs' uses also done if( n instanceof LoadNode ld ) - for( Node memuse : ld.mem()._outputs ) - if( late[memuse._nid]==null && - // Load-use directly defines memory - (memuse._type instanceof TypeMem || - // Load-use indirectly defines memory - (memuse._type instanceof TypeTuple tt && tt._types[ld._alias] instanceof TypeMem)) ) + for( Node memuse : ld.antiDeps() ) + if( late[memuse._nid]==null ) continue outer; // All uses done, schedule @@ -126,9 +122,7 @@ public abstract class GlobalCodeMotion { for( Node def : n._inputs ) { if( def==null ) continue; if( late[def._nid]==null ) work.push(def); - for( Node out : def._outputs ) - if( out instanceof LoadNode ld && late[ld._nid]==null ) - work.push(ld); + wakeLoads(def,late,work,new BitSet()); } if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) @@ -185,13 +179,24 @@ public abstract class GlobalCodeMotion { best instanceof IfNode; } + // An allocation may consume a load's memory through a partial aggregate. + private static void wakeLoads(Node def, CFGNode[] late, WorkList<Node> work, BitSet visit) { + if( visit.get(def._nid) ) return; + visit.set(def._nid); + for( Node out : def._outputs ) + if( out instanceof LoadNode ld && late[ld._nid]==null ) work.push(ld); + if( def instanceof MemMergeNode ) + for( int i=1; i<def.nIns(); i++ ) + if( def.in(i)!=null ) wakeLoads(def.in(i),late,work,visit); + } + private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late, int[] anti) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep - for( Node mem : load.mem()._outputs ) { + for( Node mem : load.antiDeps() ) { switch( mem ) { case StoreNode st: assert late[st._nid]!=null; @@ -208,10 +213,6 @@ public abstract class GlobalCodeMotion { if( phi.in(i)==load.mem() ) lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null,anti); 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(); } } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java index 86b59dc3..9f81d556 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/Parser.java @@ -164,11 +164,8 @@ public class Parser { _xScopes.push(_scope); // Enter a new scope for the initial control and arguments _scope.push(); - 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.MEM0, TypeMem.BOT , false, new ProjNode(START, 1, ScopeNode.MEM0).peephole()); _scope.define(ScopeNode.ARG0, TypeInteger.BOT, false, new ProjNode(START, 2, ScopeNode.ARG0).peephole()); // Parse whole program @@ -525,7 +522,7 @@ public class Parser { Node expr = parseAsgn(); // Final variable to update - ScopeMinNode.Var def = _scope.lookup(name); + ScopeNode.Var def = _scope.lookup(name); if( def==null ) throw error("Undefined name '" + name + "'"); @@ -654,7 +651,7 @@ public class Parser { 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); + ScopeNode.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); @@ -873,7 +870,7 @@ public class Parser { int delta = _lexer.peek(-1)=='+' ? 1 : -1; // Pre vs post String name = _lexer.matchId(); if( name!=null ) { - ScopeMinNode.Var n = _scope.lookup(name); + ScopeNode.Var n = _scope.lookup(name); if( n != null ) { if( n._final ) throw error("Cannot reassign final '"+n._name+"'"); @@ -906,7 +903,7 @@ public class Parser { if( match("(") ) return require(parseAsgn(), ")"); if( matchx("new" ) ) return alloc(); // Expect an identifier now - ScopeMinNode.Var n = requireLookupId("an identifier or expression"); + ScopeNode.Var n = requireLookupId("an identifier or expression"); Node rvalue = _scope.in(n); if( rvalue._type == Type.BOTTOM ) throw error("Cannot read uninitialized field '"+n._name+"'"); @@ -941,11 +938,11 @@ public class Parser { return pre ? op : rvalue.unkeep(); } - ScopeMinNode.Var requireLookupId(String msg) { + ScopeNode.Var requireLookupId(String msg) { String id = _lexer.matchId(); if( id == null || KEYWORDS.contains(id) ) throw errorSyntax(msg); - ScopeMinNode.Var n = _scope.lookup(id); + ScopeNode.Var n = _scope.lookup(id); if( n==null ) throw error("Undefined name '" + id + "'"); return n; @@ -1010,21 +1007,25 @@ public class Parser { Field[] fs = obj._fields; if( fs==null ) throw error("Unknown struct type '" + obj._name + "'"); - int len = fs.length; - Node[] ns = new Node[2+len+len]; - ns[0] = ctrl(); // Control in slot 0 - // Total allocated length in bytes - 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.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(); + Node prior = mem().keep(); + MemMergeNode input = new MemMergeNode(null); + for( Field f : fs ) input.alias(f._alias,prior); + // Constructor values follow control, memory, and allocation size. + Node[] ns = new Node[3+fs.length]; + ns[0] = ctrl(); + ns[1] = input.peephole(); + ns[2] = size; + for( int i=0; i<fs.length; i++ ) ns[3+i] = init.get(idx+i); + Node nnn = new NewNode(TypeMemPtr.make(obj),ns).peephole().keep(); + Node ptr = new ProjNode(nnn,0,obj._name).peephole().keep(); + Node out = new ProjNode(nnn,1,"$mem").peephole().keep(); + MemMergeNode after = new MemMergeNode(prior); + for( Field f : fs ) after.alias(f._alias,out); + mem(after.peephole()); + out.unkeep(); + nnn.unkeep(); + prior.unkeep(); + return ptr.unkeep(); } private static final Ary<Node> ALTMP = new Ary<>(Node.class); @@ -1036,13 +1037,18 @@ public class Parser { return newStruct(ary,size,0,ALTMP); } - // 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.mem(alias ); } - private void memAlias(int alias, Node st) { _scope.mem(alias, st); } - public static String memName(int alias) { return ("$"+alias).intern(); } + // Memory is one hidden SSA variable, including across branches and loops. + private Node mem() { return _scope.mem(); } + private void mem(Node n) { _scope.mem(n); } + + private void store(String name, int alias, Type glb, Node ptr, Node off, Node val, boolean init, Node ctrl) { + Node prior = mem().keep(); + Node st = new StoreNode(name,alias,glb,prior,ptr,off,val,init); + st.setDef(0,ctrl); + st = st.peephole(); + mem(new MemMergeNode(prior,alias,st).peephole()); + prior.unkeep(); + } /** * Parse postfix expression. For now this is just a field @@ -1085,6 +1091,7 @@ public class Parser { if( tf instanceof TypeMemPtr ftmp && ftmp.isFRef() ) tf = ftmp.makeFrom(((TypeMemPtr)(TYPES.get(ftmp._obj._name)))._obj); + expr.keep(); // Field offset; fixed for structs, computed for arrays Node off = (name.equals("[]") // If field is an array body // Array index math @@ -1097,16 +1104,11 @@ public class Parser { Node val = parseAsgn().keep(); Node lift = liftExpr( val, tf, f._final ); - Node st = new StoreNode(name, f._alias, tf, memAlias(f._alias), expr, off.unkeep(), lift, false); - // Arrays include control, as a proxy for a safety range check. - // Structs don't need this; they only need a NPE check which is - // done via the type system. - if( base.isAry() ) st.setDef(0,ctrl()); - memAlias(f._alias, st.peephole()); + store(name,f._alias,tf,expr.unkeep(),off.unkeep(),lift,false,base.isAry() ? ctrl() : null); return val.unkeep(); // "obj.a = expr" returns the expression while updating memory } - Node load = new LoadNode(name, f._alias, tf.glb(), memAlias(f._alias), expr.keep(), off); + Node load = new LoadNode(name, f._alias, tf.glb(), mem(), expr, off); // Arrays include control, as a proxy for a safety range check // Structs don't need this; they only need a NPE check which is // done via the type system. @@ -1119,12 +1121,7 @@ public class Parser { throw error("Cannot reassign final '"+f._fname+"'"); Node inc = peep(new AddNode(load,con( _lexer.peek(-1)=='+' ? 1 : -1))); Node val = zsMask(inc,tf); - Node st = new StoreNode(name, f._alias, tf, memAlias(f._alias), expr.unkeep(), off, val, false); - // Arrays include control, as a proxy for a safety range check. - // Structs don't need this; they only need a NPE check which is - // done via the type system. - if( base.isAry() ) st.setDef(0,ctrl()); - memAlias(f._alias, peep(st)); + store(name,f._alias,tf,expr.unkeep(),off,val,false,base.isAry() ? ctrl() : null); // And use the original loaded value as the result } else expr.unkill(); off.unkill(); diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java new file mode 100644 index 00000000..84f97189 --- /dev/null +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -0,0 +1,237 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; +import java.util.BitSet; + +/** + * A Phi for bulk memory. It covers all aliases except {@link #_aliases}; + * those aliases must be represented by parallel precise MemPhis at the same + * program slice. + */ +public class BulkMemPhiNode extends PhiNode { + + private static final BitSet EMPTY = new BitSet(); + + // Excluded Aliases; empty means NO exclusions. + // Each split clones the exclusions; published sets are never mutated. + public final BitSet _aliases; + + public BulkMemPhiNode(String label, Node... inputs) { + this(label,EMPTY,inputs); + } + + private BulkMemPhiNode(String label, BitSet aliases, Node... inputs) { + super(label,TypeMem.BOT,inputs); + _aliases = aliases; + } + + public boolean isSplit(int alias) { return _aliases.get(alias); } + + @Override public String label() { return "BulkPhi"+_aliases; } + + @Override + public Type compute() { + Type t = super.compute(); + return t instanceof TypeMem mem ? mem : + t==Type.BOTTOM ? TypeMem.BOT : + TypeMem.TOP; + } + + @Override + public Node idealize() { + Node progress = super.idealize(); + if( progress != null ) return progress; + if( ((RegionNode)region()).inProgress() || region().nIns()<=1 ) + return null; // Input is in-progress + + // "Peek through" a MemMerge that covers this alias set on its default + for( int i=1; i<nIns(); i++ ) + if( in(i) instanceof MemMergeNode mmm && canPeek(mmm) ) { + setDef(i,IterPeeps.add(mmm.in(1))); + return this; + } + + // If any input or output uses or defines a specific alias we cover, + // make a private MemPhi for it, and add it to the excluded list. + for( int i=1; i<nIns(); i++ ) { + int alias = inputAlias(in(i)); + if( alias!=0 ) + return slice(alias); + } + + for( int i=0; i<_outputs.size(); i++ ) { + int alias = outputAlias(_outputs.get(i)); + if( alias!=0 ) + return slice(alias); + } + + return null; + } + + static public boolean checkMem(Node n, int alias) { + for( Node m : n._inputs ) + // Bulk memory supplies this alias + if( m instanceof BulkMemPhiNode bulk ) { + if( bulk._aliases.get(alias) ) + return false; + } else if( m instanceof MemMergeNode mmm && + mmm.in(1) instanceof BulkMemPhiNode bulk && + bulk._aliases.get(alias) && + (alias >= mmm.nIns() || mmm.in(alias)==null) ) + return false; + return true; + } + + + // True if the MemMerge has no precise slice still covered by this Phi. + private boolean canPeek(MemMergeNode mmm) { + return mmm.in(1)!=null && missingAlias(mmm)==0; + } + + // Return an alias required by an input but still covered by this Phi, or 0. + private int inputAlias(Node n) { + return switch(n) { + case ProjNode proj -> 0; + case ConstantNode con -> 0; + case MemMergeNode mmm -> missingAlias(mmm); + case MemOpNode mem -> unsplit(mem._alias); + case BulkMemPhiNode bulk -> missingAlias(bulk); + default -> throw new AssertionError("Unexpected memory input "+n); + }; + } + + // Return an alias required by a user but still covered by this Phi, or 0. + private int outputAlias(Node use) { + // This decision depends backwards on an immediate user's alias/set. + // Normal graph-neighbor enqueueing flows from defs to uses, so retain + // an explicit forward dependency to revisit this Phi when the user + // sharpens. + use.addDepForwards(this); + return switch(use) { + case ScopeNode scope -> 0; + case MemMergeNode mmm -> missingAlias(mmm); + case BulkMemPhiNode bulk -> missingAlias(bulk); + case MemOpNode mem -> unsplit(mem._alias); + case MemPhiNode phi -> unsplit(phi._alias); + default -> { + assert use instanceof ReturnNode + : "Unexpected bulk-memory user "+use; + yield 0; + } + }; + } + + // Alias zero/one is bulk, and an already excluded precise alias cannot + // trigger another split of this Phi. + private int unsplit(int alias) { + if( alias <= 1 ) return 0; + assert !_aliases.get(alias); + return alias; + } + + // First alias excluded by the neighboring bulk Phi but not by this one. + private int missingAlias(BulkMemPhiNode bulk) { + for( int alias = bulk._aliases.nextSetBit(0); alias >= 0; alias = bulk._aliases.nextSetBit(alias+1) ) + if( !_aliases.get(alias) ) + return alias; + return 0; + } + + // Every explicit slot requests that alias, including a partial allocation + // input whose slot still points to this bulk Phi. + private int missingAlias(MemMergeNode mmm) { + for( int alias=2; alias<mmm.nIns(); alias++ ) + if( mmm.in(alias)!=null && + mmm.alias(alias)!=mmm.in(1) && + !_aliases.get(alias) ) + return alias; + return 0; + } + + // Slice out given alias + private MemMergeNode slice( int alias ) { + assert !_aliases.get(alias); + // Inputs are the same; MemPhi will sharpen his own inputs. If a + // parallel precise Phi already exists, reuse it instead of building a + // duplicate for the same Region/alias pair. + Node mem = precisePhi(alias); + + BitSet aliases = ((BitSet)_aliases.clone()); + aliases.set(alias); + BulkMemPhiNode bphi = new BulkMemPhiNode(_label,aliases); + for( int i=0; i<nIns(); i++ ) + bphi.addDef(in(i)); + // Installing bphi creates a new bulk user with a different exclusion + // set. Queue the original memory inputs before bphi itself can peep + // away and hide those neighbor relationships. + for( int i=1; i<bphi.nIns(); i++ ) + IterPeeps.add(bphi.in(i)); + // Do not peephole bphi here, as BulkMemPhi can recursively start a + // second bulk rewrite before this one has finished. Let the worklist + // discover any further splits + bphi.setType(TypeMem.BOT); + Node bulk = bphi; + IterPeeps.add(bulk); + IterPeeps.add(mem); + return aggregate(bulk,alias,mem); + } + + // Build aggregate memory over a bulk Phi, preserving every precise slice + // which the bulk has already excluded. The named alias is newly supplied + // (or replaces its old slice). + MemMergeNode aggregate(Node bulk, int alias, Node precise) { + MemMergeNode mmm = new MemMergeNode(bulk); + for( int old = _aliases.nextSetBit(0); old >= 0; old = _aliases.nextSetBit(old+1) ) + { assert old != alias; mmm.alias(old,precisePhi(old));} + mmm.alias(alias,precise); + assert checkMerge(mmm); + return mmm; + } + + // Find or make the precise Phi parallel to this bulk Phi at the same merge. + private Node precisePhi(int alias) { + MemPhiNode mphi = _findPhi(alias); + if( mphi!=null ) return mphi; + + mphi = new MemPhiNode("$"+alias,alias); + mphi.addDef(region()); + // Due to cycles, must set before calling peephole + mphi.setType(TypeMem.make(alias,Type.BOTTOM)); + for( int i=1; i<nIns(); i++ ) + mphi.addDef(IterPeeps.add(preciseInput(in(i),alias))); + return IterPeeps.add(mphi); + } + + MemPhiNode _findPhi(int alias) { + for( Node use : region()._outputs ) + if( use instanceof MemPhiNode mphi && mphi._alias==alias ) + return mphi; + return null; + } + + // Select an alias already split out of a predecessor's bulk memory. + private Node preciseInput(Node mem, int alias) { + if( mem instanceof MemMergeNode mmm ) + return mmm.alias(alias); + if( mem instanceof BulkMemPhiNode bulk && bulk.isSplit(alias) ) + return bulk.precisePhi(alias); + return mem; + } + + // Every alias excluded by a bulk default must be supplied explicitly. + static boolean checkMerge(MemMergeNode mmm) { + if( !(mmm.in(1) instanceof BulkMemPhiNode bulk) ) return true; + for( int alias = bulk._aliases.nextSetBit(0); alias >= 0; alias = bulk._aliases.nextSetBit(alias+1) ) + if( alias >= mmm.nIns() || mmm.in(alias)==null ) + return false; + return true; + } + + @Override public boolean eq(Node n) { + return _aliases.equals(((BulkMemPhiNode)n)._aliases) && super.eq(n); + } + + @Override int hash() { return _aliases.hashCode(); } +} 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 17ed127c..2b430df4 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -1,9 +1,10 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.*; import java.util.BitSet; +import java.util.ArrayList; /** * Load represents extracting a value from inside a memory object, @@ -23,6 +24,25 @@ public class LoadNode extends MemOpNode { super(name, alias, glb, mem, ptr, off); } + @Override boolean canDrop(MemOpNode other, Node dep) { + return super.canDrop(other,dep) && !clobbered(dep); + } + + // Check only immediate memory users. Stores clobber memory; Phis and + // aggregates might lead to a clobber, so stop rather than search further. + private boolean clobbered(Node dep) { + Node mem = mem(); + mem.addDepForwards(dep); + for( Node use : mem._outputs ) { + if( use==null ) continue; + use.addDepForwards(dep); + if( use instanceof StoreNode || use instanceof PhiNode || + use instanceof MemMergeNode || + use instanceof NewNode ) return true; + } + return false; + } + // Debugger label @Override public String label() { return "ld_"+mlabel(); } @Override @@ -30,31 +50,31 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { - 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; + Type t = MemMergeNode.contents(mem(),_alias,this); + // Update declared forward ref to the actual. + if( _declaredType.isFRef() && t instanceof TypeMemPtr tmp && !tmp.isFRef() ) + _declaredType = tmp; + return err()==null ? _declaredType.join(t) : _declaredType; } @Override public Node idealize() { + if( mem() instanceof MemMergeNode merge ) { + setDef(1,IterPeeps.add(merge.alias(_alias))); + return this; + } Node ptr = ptr(); // Simple Load-after-Store on same address. if( mem() instanceof StoreNode st && - ptr == st.ptr() && off() == st.off() ) { // Must check same object + _alias==st._alias && ptr == st.ptr() && off() == st.off() ) { // Must check same object assert _name.equals(st._name); // Equiv class aliasing is perfect return st.val(); } // Simple Load-after-New on same address. if( mem() instanceof ProjNode p && p.in(0) instanceof NewNode nnn && - ptr == nnn.proj(1) ) // Must check same object + ptr == nnn.proj(0) ) // Must check same object return nnn.in(nnn.findAlias(_alias)); // Load from New init // Load-after-Store on same address, but bypassing provably unrelated @@ -65,12 +85,16 @@ public class LoadNode extends MemOpNode { Node mem = mem(); outer: while( true ) { + mem.addDep(this); switch( mem ) { + case MemMergeNode merge: + mem = merge.alias(_alias); + break; case StoreNode st: - if( ptr == st.ptr() && off() == st.off() ) + if( _alias==st._alias && ptr == st.ptr() && off() == st.off() ) return castRO(st.val()); // Proved equal // Can we prove unequal? Offsets do not overlap? - if( !off()._type.join(st.off()._type).isHigh() && // Offsets overlap + if( _alias==st._alias && !off()._type.join(st.off()._type).isHigh() && // Offsets overlap !neverAlias(ptr,st.ptr()) ) // And might alias break outer; // Cannot tell, stop trying // Pointers cannot overlap @@ -84,13 +108,11 @@ public class LoadNode extends MemOpNode { return castRO(nnn1.in(nnn1.findAlias(_alias))); // Load from New init if( !(ptr instanceof ProjNode pproj && pproj.in(0) instanceof NewNode nnn2) ) break outer; // Cannot tell, ptr not related to New - mem = nnn1.in(_alias);// Bypass unrelated New + mem = nnn1.mem();// Bypass unrelated New break; - } else if( mproj.in(0) instanceof StartNode ) { - break outer; - } else throw Utils.TODO(); + } else break outer; default: - throw Utils.TODO(); + break outer; } } @@ -101,7 +123,7 @@ public class LoadNode extends MemOpNode { // if( pred ) ptr.x = e0; val = pred ? e0 // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; - if( mem() instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 && + if( mem() instanceof MemPhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 && // Offset can be hoisted off() instanceof ConstantNode && // Pointer can be hoisted @@ -122,7 +144,9 @@ public class LoadNode extends MemOpNode { private Node ld( int idx ) { Node mem = mem(), ptr = ptr(); - return new LoadNode(_name,_alias,_declaredType,mem.in(idx),ptr instanceof PhiNode && ptr.in(0)==mem.in(0) ? ptr.in(idx) : ptr, off()).peephole(); + LoadNode ld = new LoadNode(_name,_alias,_declaredType,mem.in(idx),ptr instanceof PhiNode && ptr.in(0)==mem.in(0) ? ptr.in(idx) : ptr,off()); + ld.setDef(0,in(0)); + return ld.peephole(); } private static boolean neverAlias( Node ptr1, Node ptr2 ) { @@ -155,8 +179,9 @@ public class LoadNode extends MemOpNode { private boolean profit(PhiNode phi, int idx) { Node px = phi.in(idx); if( px==null ) return false; - if( px._type instanceof TypeMem mem && mem._t.isHighOrConst() ) { px.addDep(this); return true; } - if( px instanceof StoreNode st1 && ptr()==st1.ptr() && off()==st1.off() ) { px.addDep(this); return true; } + px.addDep(this); + if( px._type instanceof TypeMem mem && mem._t.isHighOrConst() ) return true; + if( px instanceof StoreNode st1 && _alias==st1._alias && ptr()==st1.ptr() && off()==st1.off() ) return true; return false; } @@ -166,4 +191,29 @@ public class LoadNode extends MemOpNode { return new ReadOnlyNode(rez).peephole(); return rez; } + + // Memory writers which must follow this read. A packaging node is not a + // write, but can hide New's input, so follow this alias through aggregates. + public ArrayList<Node> antiDeps() { + ArrayList<Node> deps = new ArrayList<>(); + antiDeps(mem(),deps,new BitSet()); + return deps; + } + + private void antiDeps(Node mem, ArrayList<Node> deps, BitSet visit) { + if( visit.get(mem._nid) ) return; + visit.set(mem._nid); + for( Node use : mem._outputs ) { + if( use instanceof MemMergeNode merge ) { + Node slice = _alias<merge.nIns() ? merge.in(_alias) : null; + if( (slice==mem) || (slice==null && merge.in(1)==mem) ) + antiDeps(merge,deps,visit); + } else if( (use instanceof StoreNode st && st._alias==_alias) || + (use instanceof NewNode nnn && nnn.field(_alias)!=null) || + (use instanceof MemPhiNode phi && phi._alias==_alias) || + (use instanceof BulkMemPhiNode phi && !phi.isSplit(_alias)) ) { + if( !deps.contains(use) ) deps.add(use); + } + } + } } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java new file mode 100644 index 00000000..ff040b99 --- /dev/null +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -0,0 +1,89 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; +import java.util.BitSet; + +/** A default slice and explicit alias overrides. A null default means partial + * memory: absent aliases are not covered, rather than having unknown contents. + */ +public class MemMergeNode extends Node { + public MemMergeNode(Node bulk) { super(null,bulk); _type = TypeMem.BOT; } + public MemMergeNode(Node bulk, int alias, Node precise) { + this(bulk); + alias(alias,precise); + } + + public Node alias(int alias) { + Node n = alias < nIns() ? in(alias) : null; + assert n!=null || !(in(1) instanceof BulkMemPhiNode bulk) || !bulk.isSplit(alias); + n = n==null ? in(1) : n; + assert n!=null : "Alias not covered: "+alias; + return n; + } + + public void alias(int alias, Node mem) { + assert alias > 1; + while( nIns()<=alias ) addDef(null); + setDef(alias,mem); + } + + // Scalar contents of one alias. New's field inputs supply the initialized type; + // join it with the incoming contents for all previously allocated objects. + // Phis use their cached types, so this query does not recurse around loops. + static Type contents(Node mem, int alias, Node dep) { + mem.addDep(dep); + if( mem instanceof MemMergeNode merge ) + return contents(merge.alias(alias),alias,dep); + if( mem instanceof ProjNode proj && proj.in(0) instanceof NewNode nnn ) { + assert proj._idx==1 && nnn.field(alias)!=null; + nnn.addDep(dep); + Node init = nnn.in(nnn.findAlias(alias)).addDep(dep); + return contents(nnn.mem(),alias,dep).meet(init._type); + } + // There are no heap arguments in this chapter. Before the first New, + // the set of allocated objects (and hence stored values) is empty. + if( mem instanceof ProjNode proj && proj.in(0) instanceof StartNode ) return Type.TOP; + if( mem._type==Type.TOP || mem._type==TypeMem.TOP ) return Type.TOP; + if( mem._type instanceof TypeMem mt && mt._alias==alias ) return mt._t; + return Type.BOTTOM; + } + + @Override public String label() { return "MemMerge"; } + @Override public boolean isMem() { return true; } + @Override public Type compute() { return TypeMem.BOT; } + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { + sb.append("MEM["); + for( int i=1; i<nIns(); i++ ) + if( in(i)!=null ) { + sb.append(i==1 ? "default:" : i+":"); + in(i)._print0(sb,visited).append(" "); + } + return sb.append("]"); + } + + @Override public Node idealize() { + boolean progress=false, allDefault=true; + for( int i=2; i<nIns(); i++ ) { + if( in(i)!=null && in(i)==in(1) ) { setDef(i,null); progress=true; } + if( in(i) instanceof MemMergeNode mem ) { + setDef(i,IterPeeps.add(mem.alias(i))); + progress=true; + } + if( in(i)!=null ) allDefault=false; + } + if( allDefault && in(1)!=null ) return in(1); + + if( in(1) instanceof MemMergeNode mem ) { + for( int i=2; i<mem.nIns(); i++ ) + if( mem.in(i)!=null && (i>=nIns() || in(i)==null) ) + alias(i,mem.in(i)); + IterPeeps.add(mem.in(1)); + setDef(1,mem.in(1)); + return this; + } + assert BulkMemPhiNode.checkMerge(this); + return progress ? this : null; + } +} 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 82aab8ac..0bf9b6ac 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -33,6 +33,13 @@ public abstract class MemOpNode extends Node { public Node ptr() { return in(2); } public Node off() { return in(3); } + // Extra conditions for factoring matching memory operations through a Phi. + // The caller has already checked the opcode, input shape and control. + boolean canDrop(MemOpNode other, Node dep) { + ptr().addDep(dep); + return _alias==other._alias && _declaredType==other._declaredType && err()==null; + } + @Override boolean eq(Node n) { MemOpNode mem = (MemOpNode)n; // Invariant diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java new file mode 100644 index 00000000..6aae00f9 --- /dev/null +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java @@ -0,0 +1,42 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; + +/** A Phi for one field alias, parallel to a bulk Phi at the same Region. */ +public class MemPhiNode extends PhiNode { + public final int _alias; + + public MemPhiNode(String label, int alias, Node... inputs) { + super(label,TypeMem.make(alias,Type.BOTTOM),inputs); + assert alias > 1; + _alias = alias; + } + + @Override public String label() { return "MemPhi_"+_alias; } + + @Override public Type compute() { + assert BulkMemPhiNode.checkMem(this,_alias); + if( !(region() instanceof RegionNode r) ) + return region()._type==Type.XCONTROL ? TypeMem.TOP : _type; + if( r.inProgress() ) return _declaredType; + Type t = Type.TOP; + for( int i=1; i<nIns(); i++ ) + if( r.in(i).addDep(this)._type!=Type.XCONTROL ) + t = t.meet(MemMergeNode.contents(in(i),_alias,this)); + return TypeMem.make(_alias,t); + } + + @Override public Node idealize() { + for( int i=1; i<nIns(); i++ ) + if( in(i) instanceof MemMergeNode mem ) { + setDef(i,IterPeeps.add(mem.alias(_alias))); + return this; + } + return super.idealize(); + } + + @Override boolean eq(Node n) { return _alias==((MemPhiNode)n)._alias && super.eq(n); } + @Override int hash() { return _alias; } +} diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/NewNode.java index 77800be2..bdccc681 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -1,34 +1,33 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.type.*; -import com.seaofnodes.simple.Utils; import java.util.BitSet; -/** - * Allocation! Allocate a chunk of memory, and pre-zero it. - * The inputs include control and size, and ALL aliases being set. - * The output is large tuple, one for every alias plus the created pointer. - * New is expected to be followed by projections for every alias. +/** Allocate and initialize an object. Inputs {ctrl, $mem, size, fields...}; + * results {ptr, $mem}. + * The memory input and result cover only the aliases in the allocated struct. */ public class NewNode extends Node implements MultiNode { public final TypeMemPtr _ptr; - public final int _len; public NewNode(TypeMemPtr ptr, Node... nodes) { super(nodes); _ptr = ptr; - _len = ptr._obj._fields.length; - // Control in slot 0 - assert nodes[0]._type==Type.CONTROL || nodes[0]._type == Type.XCONTROL; - // Malloc-length in slot 1 - assert nodes[1]._type instanceof TypeInteger; - for( int i=0; i<_len; i++ ) { - // Memory slices for all fields. - assert nodes[2+ i]._type instanceof TypeMem; - // Value slices for all fields. - assert nodes[2 + _len + i]._type != null; - } + assert nodes.length==3+ptr._obj._fields.length; + assert nodes[0]._type==Type.CONTROL || nodes[0]._type==Type.XCONTROL; + assert nodes[1]._type instanceof TypeMem; + assert nodes[2]._type instanceof TypeInteger; + for( int i=3; i<nodes.length; i++ ) assert nodes[i]._type!=null; + } + + public Node mem() { return in(1); } + public Node size() { return in(2); } + + public Field field(int alias) { + for( Field f : _ptr._obj._fields ) + if( f._alias==alias ) return f; + return null; } @Override public String label() { @@ -42,22 +41,13 @@ public class NewNode extends Node implements MultiNode { // Find matching alias input int findAlias(int alias) { - return 2+_ptr._obj.findAlias(alias)+_len; + return 3+_ptr._obj.findAlias(alias); } @Override public TypeTuple compute() { - Field[] fs = _ptr._obj._fields; - Type[] ts = new Type[fs.length+2]; - ts[0] = Type.CONTROL; - ts[1] = _ptr; - for( int i=0; i<fs.length; i++ ) { - TypeMem mem = (TypeMem)in(i+2)._type; - Type tfld = in(2+_len+i)._type.meet(mem._t); - ts[i+2] = TypeMem.make(fs[i]._alias,tfld); - } - return TypeTuple.make(ts); + return TypeTuple.make(_ptr,TypeMem.BOT); } @Override 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 24934c7b..dc952d87 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/Node.java @@ -16,14 +16,14 @@ import java.util.function.Function; * The Node class provides common functionality used by all subtypes. * Subtypes of Node specialize by overriding methods. */ -public abstract class Node implements OutNode { +public abstract class Node implements OutNode, Cloneable { /** * Each node has a unique dense Node ID within a compilation context * The ID is useful for debugging, for using as an offset in a bitvector, * as well as for computing equality of nodes (to be implemented later). */ - public final int _nid; + public int _nid; /** * Inputs to the node. These are use-def references to Nodes. @@ -32,7 +32,7 @@ public abstract class Node implements OutNode { * Ordering is required because e.g. "a/b" is different from "b/a". * The first input (offset 0) is often a {@link CFGNode} node. */ - public final Ary<Node> _inputs; + public Ary<Node> _inputs; /** * Outputs reference Nodes that are not null and have this Node as an @@ -43,7 +43,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 Ary<Node> _outputs; + public Ary<Node> _outputs; /** @@ -214,6 +214,7 @@ public abstract class Node implements OutNode { // Error is 'use' does not exist; ok for 'use' to be null. protected boolean delUse( Node use ) { _outputs.del(_outputs.find(use)); + moveDepsToWorklist(); // User-count and anti-dependence queries can now change. return _outputs.isEmpty(); } @@ -274,6 +275,7 @@ public abstract class Node implements OutNode { n.unlock(); int idx = n._inputs.find(this); n._inputs.set(idx,nnn); + n.moveDepsToWorklist(); // Rewiring can change a dependent query without changing type. nnn.addUse(n); IterPeeps.addAll(n._outputs); } @@ -460,6 +462,14 @@ public abstract class Node implements OutNode { * being added must benefit from this node being peepholed. */ Node addDep( Node dep ) { + return addDep(dep,false); + } + + // A bulk Phi inspects its users' partitions. Def-to-use propagation does + // not revisit that producer when an immediate user's partition changes. + Node addDepForwards(Node dep) { return addDep(dep,true); } + + private Node addDep(Node dep, boolean forwards) { // Running peepholes during the big assert cannot have side effects // like adding dependencies. if( IterPeeps.midAssert() ) return this; @@ -467,8 +477,8 @@ public abstract class Node implements OutNode { if( obs != null ) obs.dep(this, dep); 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; + if( !forwards && _inputs .find(dep) != -1 ) return this; // No need for deps on immediate neighbors + if( !forwards && _outputs.find(dep) != -1 ) return this; _deps.add(dep); return this; } @@ -594,6 +604,20 @@ public abstract class Node implements OutNode { // Does not need to be implemented in isCFG() nodes. Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); } + // Exact-class copy preserving operation attributes, with fresh identity + // and no edges, dependencies, or GVN membership. + public final Node copyEmpty() { + Node n; + try { n = (Node)clone(); } + catch( CloneNotSupportedException e ) { throw new AssertionError(e); } + n._nid = UNIQUE_ID++; + n._inputs = new Ary<>(Node.class); + n._outputs = new Ary<>(Node.class); + n._deps = null; + n._hash = 0; + return n; + } + // Report any post-optimize errors String err() { return null; } diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 0532d2b7..c6cbd3dd 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -16,6 +16,10 @@ public class PhiNode extends Node { public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label; assert declaredType!=null; _declaredType = declaredType; } + public static PhiNode make(String label, Type type, Node... inputs) { + return type instanceof TypeMem ? new BulkMemPhiNode(label,inputs) : new PhiNode(label,type,inputs); + } + @Override public String label() { return "Phi_"+MemOpNode.mlabel(_label); } @Override @@ -65,24 +69,9 @@ public class PhiNode extends Node { if (live != null) return live; - // Pull "down" a common data op. One less op in the world. One more - // Phi, but Phis do not make code. - // Phi(op(A,B),op(Q,R),op(X,Y)) becomes - // op(Phi(A,Q,X), Phi(B,R,Y)). - Node op = in(1); - if( op.nIns()==3 && op.in(0)==null && same_op() ) { - assert !(op instanceof CFGNode); - Node[] lhss = new Node[nIns()]; - Node[] rhss = new Node[nIns()]; - lhss[0] = rhss[0] = in(0); // Set Region - for( int i=1; i<nIns(); i++ ) { - lhss[i] = in(i).in(1); - rhss[i] = in(i).in(2); - } - Node phi_lhs = new PhiNode(_label, _declaredType,lhss).peephole(); - Node phi_rhs = new PhiNode(_label, _declaredType,rhss).peephole(); - return op.copy(phi_lhs,phi_rhs); - } + // Phi(op(a,b,...),op(c,d,...)) -> op(Phi(a,c),Phi(b,d),...). + Node down; + if( same_op() && (down=drop_same_op())!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -112,12 +101,72 @@ public class PhiNode extends Node { } private boolean same_op() { - for( int i=2; i<nIns(); i++ ) - if( in(1).getClass() != in(i).getClass() ) - return false; + Node op = in(1); + if( op instanceof CFGNode || op instanceof ConstantNode || op instanceof PhiNode || + op instanceof ProjNode || op instanceof NewNode || op instanceof ScopeNode || op instanceof MemMergeNode ) return false; + // A bulk Phi must split its aliases before factoring precise Stores. + if( this instanceof BulkMemPhiNode ) return false; + // Bulk splitting currently identifies parallel slices by Region/alias. + // Factoring can introduce another slice at a different memory point; + // wait until that Region's bulk partitioning has finished. + if( op instanceof MemOpNode ) + for( Node use : region()._outputs ) + if( use instanceof BulkMemPhiNode ) { + use.addDepForwards(this); + return false; + } + Node busy = null; + for( int i=1; i<nIns(); i++ ) { + Node n = in(i); + if( region().in(i).addDep(this)._type==Type.XCONTROL || + op.getClass()!=n.getClass() || n.nIns()!=op.nIns() || n.in(0)!=null || !op.eq(n) ) return false; + if( n instanceof MemOpNode mem && !mem.canDrop((MemOpNode)op,this) ) return false; + // Moving a Store must remove the old effect, not duplicate it. + // Allow one shared arm: the other arms disappear into the single + // factored operation, usually reducing the total operation count. + n.addDepForwards(this); + if( n.nOuts()>1 ) { + for( Node use : n._outputs ) + if( use!=null && use!=this ) use.addDepForwards(this); + if( n instanceof StoreNode || busy!=null ) return false; + busy=n; + } + for( int j=1; j<n.nIns(); j++ ) + if( n.in(j) instanceof ScopeNode || ((n.in(j)==null) != (op.in(j)==null)) ) return false; + } return true; } + private Node drop_same_op() { + Node op = in(1), cp = op.copyEmpty(); + cp._type = null; + cp.addDef(null); + for( int j=1; j<op.nIns(); j++ ) { + Node x = op.in(j); + boolean different = false; + for( int i=2; i<nIns(); i++ ) + if( in(i).in(j)!=x ) different=true; + if( different ) { + Node[] ins = new Node[nIns()]; + ins[0] = region(); + Type t = Type.TOP; + for( int i=1; i<nIns(); i++ ) { + ins[i] = in(i).in(j); + t = t.meet(ins[i]._type); + } + PhiNode phi = j==1 && op instanceof MemOpNode mem + ? new MemPhiNode(_label,mem._alias,ins) + : PhiNode.make(_label,t.glb(),ins); + x = phi.peephole(); + } + cp.addDef(x); + } + // Factoring must not widen the result (e.g. correlated And operands). + if( cp.compute().isa(compute()) ) return cp; + cp.kill(); + return null; + } + /** * If only single unique input, return it */ 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 59da86ff..2155bd94 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter17/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).addDep(this)==p2.in(0).addDep(this) && + p1.addDepForwards(this).in(0)==p2.addDepForwards(this).in(0) && p1.in(0) instanceof IfNode iff ) return iff.ctrl(); 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 b586a44f..1049fa18 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -4,27 +4,17 @@ import com.seaofnodes.simple.type.*; import java.util.BitSet; -/** - * The Return node has two inputs. The first input is a control node and the - * second is the data node that supplies the return value. - * <p> - * In this presentation, Return functions as a Stop node, since multiple <code>return</code> statements are not possible. - * The Stop node will be introduced in Chapter 6 when we implement <code>if</code> statements. - * <p> - * The Return's output is the value from the data node. - */ +/** Keeps all preceding memory effects and the return value alive: {ctrl, $mem, value}. */ public class ReturnNode extends CFGNode { public ReturnNode(Node ctrl, Node data, ScopeNode scope) { - // Add memory slices to Return, so all memory updates are live-on-exit. - super(ctrl, data); - if( scope!=null ) - for( int i=2; i<scope.mem().nIns(); i++ ) - addDef(scope.mem().in(i)); + // A synthetic never-taken loop exit has no source scope. + super(ctrl, scope == null ? null : scope.mem(), data); } public Node ctrl() { return in(0); } - public Node expr() { return in(1); } + public Node mem () { return in(1); } + public Node expr() { return in(2); } @Override public String label() { return "Return"; } @@ -38,7 +28,8 @@ public class ReturnNode extends CFGNode { @Override public Type compute() { - return TypeTuple.make(ctrl()._type,expr()._type); + // Return exposes the complete memory state. + return TypeTuple.make(ctrl()._type,TypeMem.BOT,expr()._type); } @Override diff --git a/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java deleted file mode 100644 index 9134f9c3..00000000 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java +++ /dev/null @@ -1,150 +0,0 @@ -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 static class Var { - 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; - // Update self to no longer use the forward ref type - Type def = Parser.TYPES.get(((TypeMemPtr)_type)._obj._name); - return (_type=_type.meet(def)); - } - public Type lazyGLB() { - Type t = type(); - return t instanceof TypeMemPtr ? t : t.glb(); - } - @Override public String toString() { - return _type.toString()+(_final ? " ": " !")+_name; - } - } - - 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/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index e71c669f..d44535dc 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -1,17 +1,16 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.Parser; 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. + * stack of variable records. */ -public class ScopeNode extends ScopeMinNode { +public class ScopeNode extends Node { /** * The control is a name that binds to the currently active control @@ -21,10 +20,43 @@ public class ScopeNode extends ScopeMinNode { public static final String ARG0 = "arg"; public static final String MEM0 = "$mem"; + /** The tracked fields are now complex enough to deserve a array-of-structs layout + */ + public static class Var { + 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; + // Update self to no longer use the forward ref type + Type def = Parser.TYPES.get(((TypeMemPtr)_type)._obj._name); + return (_type=_type.meet(def)); + } + public Type lazyGLB() { + Type t = type(); + return t instanceof TypeMemPtr ? t : t.glb(); + } + @Override public String toString() { + return _type.toString()+(_final ? " ": " !")+_name; + } + } + + public Node in(Var v) { return in(v._idx); } + + @Override public Type compute() { return Type.BOTTOM; } + @Override public Node idealize() { return null; } + // All active/live variables in all nested scopes, all run together public final Ary<Var> _vars; - // Since of each nested lexical scope + // Size of each nested lexical scope public final Ary<Integer> _lexSize; // True if parsing inside of a constructor @@ -35,6 +67,7 @@ public class ScopeNode extends ScopeMinNode { // A new ScopeNode public ScopeNode() { + _type = Type.BOTTOM; _vars = new Ary<>(Var .class); _lexSize= new Ary<>(Integer.class); _inCons = new Ary<>(Boolean.class); @@ -70,7 +103,8 @@ public class ScopeNode extends ScopeMinNode { public Node ctrl() { return in(0); } - public ScopeMinNode mem() { return (ScopeMinNode)in(1); } + public Node mem() { return in(lookup(MEM0)); } + public void mem(Node n) { update(MEM0,n); } /** * The ctrl of a ScopeNode is always bound to the currently active @@ -124,12 +158,6 @@ public class ScopeNode extends ScopeMinNode { 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. * @@ -165,7 +193,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.lazyGLB(), loop.ctrl(), loop.in(loop.update(v,null)._idx),null).peephole()); + : loop.setDef(v._idx,PhiNode.make(v._name, v.lazyGLB(), 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 @@ -203,20 +231,8 @@ public class ScopeNode extends ScopeMinNode { n.keep(); dup.addDef(ctrl()); // Control input is just copied - // 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 + // Memory is one binding, with the same lazy loop Phi as scalar names. + for( int i=1; i<nIns(); i++ ) dup.addDef(loop ? this : in(i)); return dup; } @@ -231,22 +247,21 @@ public class ScopeNode extends ScopeMinNode { */ public RegionNode mergeScopes(ScopeNode that) { RegionNode r = (RegionNode) ctrl(new RegionNode(null,ctrl(), that.ctrl()).keep()); - mem()._merge(that.mem(),r); - this ._merge(that ,r); + _merge(that,r); that.kill(); // Kill merged scope IterPeeps.add(r); return r.unkeep(); } private void _merge(ScopeNode that, RegionNode r) { - for( int i = 2; i < nIns(); i++) + 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 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()); + setDef(i, PhiNode.make(v._name, v.type(), r, lhs, rhs).peephole()); } } @@ -257,21 +272,15 @@ public class ScopeNode extends ScopeMinNode { assert ctrl instanceof LoopNode loop && loop.inProgress(); ctrl.setDef(2,back.ctrl()); - mem()._endLoopMem( this, back.mem(), exit.mem() ); - this ._endLoop ( this, back , exit ); + _endLoop(this,back,exit); back.kill(); // Loop backedge is dead // Now one-time do a useless-phi removal - 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)); + _useless(); } // Fill in the backedge of any inserted Phis void _endLoop( ScopeNode scope, Node back, Node exit ) { - for( int i=2; i<nIns(); i++ ) { + for( int i=1; i<nIns(); i++ ) { if( back.in(i) != scope ) { PhiNode phi = (PhiNode)in(i); assert phi.region()==scope.ctrl() && phi.in(2)==null; @@ -283,6 +292,23 @@ public class ScopeNode extends ScopeMinNode { } + // Now one-time do a useless-phi removal + void _useless( ) { + 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 + } + } + } + } + // Up-casting: using the results of an If to improve a value. // E.g. "if( ptr ) ptr.field;" is legal because ptr is known not-null. public void addGuards( Node ctrl, Node pred, boolean invert ) { 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 ab6e4931..0dd10c22 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,19 +1,11 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; 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. - * - * Start initially has 1 input (arg) from outside and the initial control. - * In ch10 we also add mem aliases as structs get defined; each field in struct - * adds a distinct alias to Start's tuple. - */ +/** Start supplies control, whole memory, and the argument, in that order. */ public class StartNode extends LoopNode implements MultiNode { final Type _arg; @@ -32,7 +24,7 @@ public class StartNode extends LoopNode implements MultiNode { @Override public CFGNode cfg0() { return this; } @Override public TypeTuple compute() { - return TypeTuple.make(Type.CONTROL,TypeMem.TOP,_arg); + return TypeTuple.make(Type.CONTROL,TypeMem.BOT,_arg); } @Override public Node idealize() { return null; } 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 a5618960..4ec106ac 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.*; import java.util.BitSet; @@ -26,6 +27,10 @@ public class StoreNode extends MemOpNode { } // Debugger label + @Override boolean canDrop(MemOpNode other, Node dep) { + return super.canDrop(other,dep) && _init==((StoreNode)other)._init; + } + @Override public String label() { return "st_"+mlabel(); } @Override public boolean isMem() { return true; } @@ -39,27 +44,25 @@ public class StoreNode extends MemOpNode { @Override public Type compute() { Type val = val()._type; - TypeMem mem = (TypeMem)mem()._type; // Invariant - 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); - } + if( _declaredType.isFRef() && val instanceof TypeMemPtr tmp && !tmp.isFRef() ) + _declaredType = tmp; + Type t = val.join(_declaredType).meet(MemMergeNode.contents(mem(),_alias,this)); return TypeMem.make(_alias,t); } @Override public Node idealize() { + if( mem() instanceof MemMergeNode merge ) { + setDef(1,IterPeeps.add(merge.alias(_alias))); + return this; + } + // Simple store-after-store on same address. Should pick up the // required init-store being stomped by a first user store. if( mem() instanceof StoreNode st && - ptr()==st.ptr() && // Must check same object - off()==st.off() && // And same offset (could be "same alias" but this handles arrays to same index) + ptr()==st.ptr() && _alias==st._alias && // Must check same object + off()==st.off() && // And same offset ptr()._type instanceof TypeMemPtr && // No bother if weird dead pointers // Must have exactly one use of "this" or you get weird // non-serializable memory effects in the worse case. diff --git a/chapter17/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/chapter17/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index a88987d5..55961293 100644 --- a/chapter17/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/chapter17/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -54,7 +54,7 @@ public class SimpleGraphAdapter extends GraphAdapter<Node> { return n instanceof CFGNode ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA; if( n instanceof RegionNode && i == 0 ) return Role.ASSOC; if( i == 0 || n instanceof RegionNode || n instanceof StopNode ) return Role.CTRL; - if( i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode) ) return Role.MEM; + if( i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode || n instanceof NewNode) ) return Role.MEM; Node def = n.in(i); if( def != null && isMem(def) ) return Role.MEM; return Role.DATA; diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter04Test.java index dfd3569f..36727a8f 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -84,7 +84,10 @@ public class Chapter04Test { StopNode stop = parser.parse(); ReturnNode ret = stop.ret(); assertTrue(ret.in(0) instanceof CProjNode); - assertTrue(ret.in(1) instanceof ProjNode); + assertTrue(ret.in(1) instanceof ProjNode); + assertEquals(1, ((ProjNode)ret.in(1))._idx); + assertTrue(ret.in(2) instanceof ProjNode); + assertEquals(2, ((ProjNode)ret.in(2))._idx); } @Test diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java index e3d8b177..86a9937f 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -1,7 +1,8 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.evaluator.Evaluator; -import com.seaofnodes.simple.node.StopNode; +import com.seaofnodes.simple.node.*; +import java.util.BitSet; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -452,4 +453,120 @@ return 0; assertEquals("return 0;", stop.toString()); } + @Test public void testReadBeforeStores() { + var stop = new Parser(""" + struct S { int x; int y; }; + S !a = new S; S !b = new S; + a.x = 11; b.x = 22; + S !p = a; if (arg) p = b; + int before = p.x; + a.y = 55; b.y = 66; + a.x = 33; b.x = 44; + return before*100 + p.x; + """).parse().iterate(); + assertEquals(1133L, com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0)); + assertEquals(2244L, com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,1)); + } + + static final String NESTED_MEMORY = """ + struct S { int x; int y; int z; }; + S !s = new S; + s.x = 5; s.y = 7; s.z = 11; + while (arg > 0) { + s.x = s.x + 1; + int j = 3; + while (j > 0) { + j = j - 1; + if (j == 1) continue; + s.y = s.y + arg; + if (arg == 2) break; + s.z = s.z + 1; + } + arg = arg - 1; + } + return s; + """; + + @Test public void testMemoryAcrossNestedLoops() { + var stop = new Parser(NESTED_MEMORY).parse().iterate(); + for (int arg=0; arg<7; arg++) { + var obj = (com.seaofnodes.simple.evaluator.Evaluator.Obj) + com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,arg); + org.junit.Assert.assertArrayEquals(new Object[] { + 5L+arg, 7L+arg*(arg+1)-(arg>=2 ? 2 : 0), 11L+2*arg-(arg>=2 ? 2 : 0) + }, obj.fields()); + } + } + + @Test public void testMemoryAtEarlyReturns() { + var stop = new Parser(""" + struct S { int x; int y; int z; }; + S !s = new S; + s.x = 3; s.y = 5; s.z = 7; + if (arg) { s.x = 11; s.z = 13; return s; } + s.y = 17; + return s; + """).parse().iterate(); + for (int arg=0; arg<2; arg++) { + var obj = (com.seaofnodes.simple.evaluator.Evaluator.Obj) + com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,arg); + org.junit.Assert.assertArrayEquals(arg==0 ? new Object[]{3L,17L,7L} : new Object[]{11L,5L,13L}, obj.fields()); + } + } + + @Test public void testKeepLoadsAtMerge() { + StopNode stop = new Parser(""" + struct S { int x; }; + S !a = new S; S !b = new S; + a.x = arg; b.x = arg+1; + S !p = a; S !q = b; + if (arg<0) { p=b; q=a; } + int v; + if (arg>1) v=p.x; else v=q.x; + return v; + """).parse().iterate(); + // The one-step safety check stops at the memory aggregate. + assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet())); + assertEquals(-1L,Evaluator.evaluate(stop,-1)); + assertEquals(1L,Evaluator.evaluate(stop,0)); + assertEquals(3L,Evaluator.evaluate(stop,3)); + } + + @Test public void testDropStores() { + StopNode stop = new Parser(""" + struct S { int x; }; + S !s = new S; + if (arg) s.x=arg+1; else s.x=arg+2; + return s; + """).parse().iterate(); + assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); + assertEquals(2L,((Evaluator.Obj)Evaluator.evaluate(stop,0)).fields()[0]); + assertEquals(4L,((Evaluator.Obj)Evaluator.evaluate(stop,3)).fields()[0]); + } + + @Test public void testKeepReadsBeforeWrites() { + StopNode stop = new Parser(""" + struct S { int x; int y; }; + S !a = new S; S !b = new S; + a.x=arg; b.x=arg+1; + S !p=a; S !q=b; + if (arg<0) { p=b; q=a; } + int v; + if (arg>1) { v=p.x; p.x=41; p.y=5; } + else { v=q.x; q.x=42; } + return v; + """).parse().iterate(); + assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet())); + assertEquals(-1L,Evaluator.evaluate(stop,-1)); + assertEquals(1L,Evaluator.evaluate(stop,0)); + assertEquals(3L,Evaluator.evaluate(stop,3)); + } + + private static int countMemoryNodes(Node n, Class<?> kind, BitSet seen) { + if (n==null || seen.get(n._nid)) return 0; + seen.set(n._nid); + int cnt=kind.isInstance(n) ? 1 : 0; + for (Node def : n._inputs) cnt+=countMemoryNodes(def,kind,seen); + return cnt; + } } diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter10bTest.java new file mode 100644 index 00000000..fd6fdf36 --- /dev/null +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter10bTest.java @@ -0,0 +1,64 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.evaluator.Evaluator; +import org.junit.Test; +import static org.junit.Assert.*; + +public class Chapter10bTest { + @Test public void testIndependentField() { + var stop = new Parser(""" + struct S { int x; int y; }; + S !s = new S; + s.x = 42; + while (arg > 0) { s.y = s.y + arg; arg = arg - 1; } + return s.x; + """).parse().iterate(); + assertEquals("return 42;",stop.toString()); + assertEquals(42L,Evaluator.evaluate(stop,5)); + assertNull(stop.walk(n -> n instanceof LoadNode ? n : null)); + } + + @Test public void testParallelMemoryPhis() { + var stop = new Parser(""" + struct S { int x; int y; int z; }; + S !a = new S; S !b = new S; + S !p = a; if (arg) p = b; + while (arg > 0) { + a.x = p.x + arg; + a.y = p.y + 2; + a.z = p.z + 3; + arg = arg - 1; + } + return a; + """).parse().iterate(); + int[] phis = {0}; + stop.walk(n -> { + if (n instanceof MemPhiNode) phis[0]++; + if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b) + for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1)) + assertTrue(a<m.nIns() && m.in(a)!=null); + assertFalse(n instanceof PhiNode && n.isMem() && + !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode)); + return null; + }); + assertTrue(phis[0]>=3); + assertArrayEquals(new Object[]{1L,2L,3L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); + } + + @Test public void testLateSliceWorklist() throws ReflectiveOperationException { + // Seed 97 exposed a store selecting a bulk predecessor without queuing + // it. Keep both the worklist assertion and the final heap check. + for (int seed : new int[]{0,97,123,456}) { + var parser = new Parser(Chapter10Test.NESTED_MEMORY); + var field = IterPeeps.class.getDeclaredField("WORK"); + field.setAccessible(true); + Object work = field.get(null); + field = work.getClass().getDeclaredField("_R"); + field.setAccessible(true); + ((java.util.Random)field.get(work)).setSeed(seed); + var stop = parser.parse().iterate(); + assertArrayEquals(new Object[]{9L,25L,17L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); + } + } +} diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 862b75e3..a1fdeb3a 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -183,7 +183,7 @@ return new S1.s=new S2; struct I {int i;}; struct P { I? pi; }; P !p1 = new P; -P p2 = new P; +P !p2 = new P; p2.pi = new I; p2.pi.i = 2; if (arg) p1 = new P; diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter14Test.java index 23c82358..6846e7af 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -175,7 +175,7 @@ while(v1) break; return v1; """); StopNode stop = parser.parse().iterate(); - assertEquals("return (Phi(Loop,((1<<arg)&1),0)&Phi(Loop,Shl,4294967295));", stop.toString()); + assertEquals("return Phi(Loop,(((1<<arg)&1)&Shl),0);", stop.toString()); assertEquals(1L, Evaluator.evaluate(stop, 0)); } diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 4e2682dc..e66a009b 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -130,7 +130,7 @@ else { return rez; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region,1.2,Phi(Region,2.3,3.14));", stop.toString()); + assertEquals("return Phi(Region,1.2,Phi(Region,2.3,.y));", stop.toString()); assertEquals(3.14, Evaluator.evaluate(stop, 0)); assertEquals(1.2 , Evaluator.evaluate(stop, 1)); } @@ -156,7 +156,7 @@ if( iss[arg] ) return rez; """); try { parser.parse().iterate(); fail(); } - catch( Exception e ) { assertEquals("Might be null accessing 'y'",e.getMessage()); } + catch( Exception e ) { assertEquals("Might be null accessing '[]'",e.getMessage()); } } @Test diff --git a/chapter17/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter17/src/test/java/com/seaofnodes/simple/Chapter16Test.java index 36510737..d9edf0e6 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -254,4 +254,27 @@ return new Square; assertEquals("Obj<Square>{side=3.0,diag=1.7320508075688772}", Evaluator.evaluate(stop, 3).toString()); assertEquals("Obj<Square>{side=4.0,diag=2.0}", Evaluator.evaluate(stop, 4).toString()); } + static final String CONSTRUCTOR_MEMORY = """ + struct S { int x; int y; }; + struct T { int z=arg+40; }; + T !t = new T; + S !a = new S { x=11; y=7; }; + S !b = new S { x=22; y=9; }; + S !p=a; + if (arg) p=b; + int before=p.x; + S !c = new S { + x=p.x+1; + { int i=0; while (i<2) { p.y=p.y+1; i=i+1; } } + y=p.y; + }; + p.x=33; + return before*10000+c.x*100+c.y+t.z; + """; + + @Test public void testConstructorMemory() { + StopNode stop = new Parser(CONSTRUCTOR_MEMORY).parse().iterate(); + assertEquals(111249L,Evaluator.evaluate(stop,0)); + assertEquals(222352L,Evaluator.evaluate(stop,1)); + } } diff --git a/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 72f84fa2..30af9895 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -187,7 +187,7 @@ public class Evaluator { Object[] body=null; int num; if( type.isAry() ) { - long sz = (Long)val(alloc.in(1)); + long sz = (Long)val(alloc.size()); long n = offToIdx(sz, type); if( n < 0 ) throw new NegativeArraySizeException(""+n); @@ -201,17 +201,13 @@ public class Evaluator { assert elem instanceof TypeMemPtr; } // Length value - body[0] = vall(alloc.in(2+2)); + body[0] = vall(alloc.in(3)); } else { body = new Object[num = type._fields.length]; for (int i=0; i<num; i++) - body[i] = val(alloc.in(2+i+num)); + body[i] = val(alloc.in(3+i)); } - Object[] mems = new Object[type._fields.length+2]; - // mems[0] is control - mems[1] = new Obj(type,body); // the ref - // mems[2+...] are memory aliases - return mems; + return new Object[]{new Obj(type,body),MEMORY}; } private Object load(LoadNode load) { @@ -304,10 +300,10 @@ public class Evaluator { case ToFloatNode cast -> (double)vall(cast.in(1)); case LoadNode load -> load(load); case StoreNode store -> store(store); + case MemMergeNode merge -> MEMORY; case NewNode alloc -> alloc(alloc); case CProjNode cproj -> ((Object[])val(cproj.ctrl()))[cproj._idx]; case ProjNode proj -> ((Object[])val( proj.in(0) ))[ proj._idx]; - case ScopeMinNode mem -> null; case ReadOnlyNode ro -> val(ro.in(1)); default -> throw new AssertionError("Unexpected node " + node); }; @@ -331,7 +327,7 @@ public class Evaluator { case null: return Status.FALLTHROUGH; case ReturnNode ret: - return val(ret.in(1)); + return val(ret.expr()); case IfNode ifn: block = block.next()[isTrue(val(ifn.in(1))) ? 0 : 1]; if (block == null) return Status.FALLTHROUGH; diff --git a/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index 06169e2c..afcc700f 100644 --- a/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/chapter17/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -31,6 +31,8 @@ import java.util.*; */ public class Scheduler { + private final HashMap<Node,ArrayList<NodeData>> readers = new HashMap<>(); + /** * A basic block with a schedule of the containing nodes. * @@ -252,7 +254,7 @@ public class Scheduler { // but they did not refine the placement // so do that now. var mem = l.in(1); - for(var out : mem._outputs) { + for(var out : l.antiDeps()) { if (out instanceof PhiNode p) { var r = p.in(0); for (int i = 1; i < p.nIns(); i++) { @@ -270,13 +272,9 @@ public class Scheduler { for(var in:data.node._inputs) { if (in!=null) update(d(in), data.block); } - if (data.node instanceof StoreNode s) { - // Store nodes have anti-deps to load nodes. - // So decrease the uses of these loads when the store is placed. - for (var out: s.in(1)._outputs) { - if (out instanceof LoadNode) od(out).ifPresent(this::decUsers); - } - } + var loads = readers.get(data.node); + if (loads != null) + for (var load : loads) decUsers(load); } // Now all nodes should be placed and have a block assigned @@ -442,7 +440,6 @@ public class Scheduler { private void doMarkAlive(Node node) { var cfgQueue = new Stack<NodeData>(); var dataQueue = new Stack<NodeData>(); - var mem = new Stack<NodeData>(); markAlive(cfgQueue, node, true); // Mark all CFG nodes. while (!cfgQueue.isEmpty()) { @@ -467,16 +464,16 @@ public class Scheduler { } else { for (var in : node._inputs) if (in != null && !(in instanceof CFGNode)) markAlive(dataQueue, in, false); } - if (node instanceof StoreNode) mem.push(data); - } - // Handle store nodes and increase load with an anti-dep to the store. - while (!mem.isEmpty()) { - var data = mem.pop(); - node = data.node; - for(var out:node.in(1)._outputs) { - if (out instanceof LoadNode) od(out).ifPresent(d->d.users++); - } } + // Writes, including New behind an aggregate, schedule before their + // anti-dependent reads in this reverse scheduling pass. + for (var load : data.values()) + if (load.node instanceof LoadNode l) + for (var use : l.antiDeps()) + if ((use instanceof StoreNode || use instanceof NewNode) && data.containsKey(use)) { + load.users++; + readers.computeIfAbsent(use,k->new ArrayList<>()).add(load); + } } /** |