diff options
Diffstat (limited to 'chapter21/src')
39 files changed, 1496 insertions, 494 deletions
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/Parser.java b/chapter21/src/main/java/com/seaofnodes/simple/Parser.java index fb108447..3b502c44 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/Parser.java @@ -138,7 +138,7 @@ public class Parser { _scope.define(ScopeNode.ARG0, TypeInteger.BOT, false, null, _lexer); ctrl(XCTRL); - _scope.mem(new MemMergeNode(false)); + _scope.mem(con(TypeMem.BOT)); // Parse whole program, as-if function header "{ int arg -> body }" parseFunctionBody(_code._main,loc(),"arg"); @@ -196,7 +196,7 @@ public class Parser { // Build a multi-exit return point for all function returns RegionNode r = new RegionNode((Lexer)null,null,null).init(); assert r.inProgress(); - PhiNode rmem = new PhiNode(ScopeNode.MEM0,TypeMem.BOT,r,null).init(); + PhiNode rmem = new BulkMemPhiNode(ScopeNode.MEM0,r,null).init(); PhiNode rrez = new PhiNode(ScopeNode.ARG0,Type.BOTTOM,r,null).init(); ReturnNode ret = new ReturnNode(r, rmem, rrez, rpc, fun).init(); fun.setRet(ret); @@ -208,11 +208,8 @@ public class Parser { // external calls. _scope.push(ScopeNode.Kind.Function); ctrl(fun); // Scope control from function - // Private mem alias tracking per function - MemMergeNode mem = new MemMergeNode(true); - mem.addDef(null); // Alias#0 - mem.addDef(new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,con(TypeMem.BOT)).peephole()); // All aliases - _scope.mem(mem); + // Unknown callers supply whole memory; field aliases are discovered lazily. + _scope.mem(new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,con(TypeMem.BOT)).peephole()); // All args, "as-if" called externally for( int i=0; i<ids.length; i++ ) { Type t = sig.arg(i); @@ -226,7 +223,7 @@ public class Parser { // Last expression is the return if( ctrl()._type==Type.CONTROL ) - fun.addReturn(ctrl(), _scope.mem().merge(), last); + fun.addReturn(ctrl(), _scope.mem(), last); // Pop off the inProgress node on the multi-exit Region merge assert r.inProgress(); @@ -586,9 +583,8 @@ public class Parser { */ private Node parseReturn() { var expr = require(parseAsgn(), ";"); - // Need default memory, since it can be lazy, need to force - // a non-lazy Phi - _fun.addReturn(ctrl(), _scope.mem().merge(), expr); + // Force the lazy whole-memory Phi before closing this exit. + _fun.addReturn(ctrl(), _scope.mem(), expr); ctrl(XCTRL); // Kill control return expr; } @@ -1201,29 +1197,31 @@ 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]; - 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); - Node nnn = new NewNode(TypeMemPtr.make(obj), ns).peephole().keep(); - for( int i = 0; i < len; i++ ) - memAlias(fs[i]._alias, new ProjNode(nnn,i+2,memName(fs[i]._alias)).peephole()); - Node ptr = new ProjNode(nnn.unkeep(),1,obj._name).peephole().keep(); - - // Initial nonzero values for every field - for( int i = 0; i < len; i++ ) { - Node val = init.get( i + idx ); + Node prior = mem().keep(); + MemMergeNode input = new MemMergeNode((Node)null); + for( Field f : fs ) input.alias(f._alias,prior); + // Allocation zeroes its fields; nonzero initializers become explicit Stores. + Node[] ns = new Node[3]; + ns[0] = ctrl(); + ns[1] = input.peephole(); + ns[2] = size; + 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(); + for( int i=0; i<fs.length; i++ ) { + Node val = init.get(idx+i); if( val._type != val._type.makeZero() ) { - Node mem = memAlias(fs[i]._alias); - Node st = new StoreNode(loc(),fs[i]._fname,fs[i]._alias,fs[i]._type,mem,ptr,con(obj.offset(i)),val,true).peephole(); - memAlias(fs[i]._alias,st); + Field f = fs[i]; + Node st = new StoreNode(loc(),f._fname,f._alias,f._type,mem(),ptr,con(obj.offset(i)),val,true).peephole(); + mem(new MemMergeNode(mem(),f._alias,st).peephole()); } } - return ptr.unkeep(); } @@ -1236,13 +1234,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(loc(),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; this can be a field expression, an array @@ -1285,6 +1288,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 @@ -1297,16 +1301,11 @@ public class Parser { Node val = parseAsgn().keep(); Node lift = liftExpr( val, tf, f._final ); - Node st = new StoreNode(loc(), 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(loc(),name, f._alias, tf, memAlias(f._alias), expr.keep(), off); + Node load = new LoadNode(loc(),name, f._alias, tf, 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. @@ -1317,12 +1316,7 @@ public class Parser { char ch = _lexer.matchOperAssign(); if( ch!=0 ) { Node op = opAssign(ch,load,f._final,tf,name); - Node st = new StoreNode(loc(), name, f._alias, tf, memAlias(f._alias), expr.unkeep(), off, op, 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,op,false,base.isAry() ? ctrl() : null); load = postfix(ch) ? load.unkeep() : op; // And use the original loaded value as the result } else expr.unkill(); @@ -1403,7 +1397,7 @@ public class Parser { } // Control & memory after parsing args args.set(0,ctrl().keep()); - args.set(1,_scope.mem().merge().keep()); + args.set(1,_scope.mem().keep()); args.push(expr); // Function pointer // Unkeep them all for( Node arg : args ) @@ -1424,11 +1418,8 @@ public class Parser { call.peephole(); // Rerun peeps after CallEnd, allows early inlining // Control from CallEnd ctrl(new CProjNode(cend,0,ScopeNode.CTRL).peephole()); - // Memory from CallEnd - MemMergeNode mem = new MemMergeNode(true); - mem.addDef(null); // Alias#0 - mem.addDef(new ProjNode(cend,1,ScopeNode.MEM0).peephole()); - _scope.mem(mem); + // A call may update any alias, so its memory result is the new whole state. + _scope.mem(new ProjNode(cend,1,ScopeNode.MEM0).peephole()); // Call result return new ProjNode(cend,2,"#2").peephole(); } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index 064d5820..2c44cb05 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -429,7 +429,7 @@ public class CodeGen { @Override public String toString() { return _phase.ordinal() > Phase.Schedule.ordinal() ? IRPrinter._prettyPrint( this ) - : _stop.p(9999); + : IRPrinter.prettyPrint(this); } // Debugging helper diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index 5c119251..9945374a 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -51,7 +51,7 @@ public abstract class GlobalCodeMotion { var cons = new ArrayList<Node>(); for( Node con : start._outputs ) if( con!=null && !(con instanceof CFGNode) && - (con.isConst() || con instanceof MachNode mach && mach.outregmap()!=null) ) { + (con.isConst() || (con instanceof MachNode mach && mach.outregmap()!=null)) ) { globals.put(con,true); cons.add(con.keep()); // Preserve original inputs while rewiring users. } @@ -173,16 +173,8 @@ public abstract class GlobalCodeMotion { // Loads need their memory inputs' uses also done if( n instanceof MemOpNode ld && ld._isLoad ) - for( Node memuse : ld.mem()._outputs ) - if( late[memuse._nid]==null && - // New makes new memory, never crushes load memory - !(memuse instanceof NewNode) && - // Load-use directly defines memory - (memuse._type instanceof TypeMem || - // Load-use directly defines memory - memuse instanceof CallNode || - // 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 @@ -194,9 +186,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 MemOpNode ld && ld._isLoad && late[ld._nid]==null ) - work.push(ld); + wakeLoads(def,late,work,new BitSet()); } if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) @@ -256,23 +246,32 @@ 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 MemOpNode ld && ld._isLoad && 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, MemOpNode 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 MemOpNode st: - if( !st._isLoad ) { - assert late[mem._nid] != null; - lca = anti_dep(load,late[mem._nid],lca,st,anti); - } - break; // Loads do not cause anti-deps on other loads - case CallNode call: - assert late[call._nid]!=null; - lca = anti_dep(load,late[call._nid],lca,call,anti); + assert late[st._nid]!=null; + lca = anti_dep(load,late[st._nid],lca,st,anti); + break; + case CallNode st: + assert late[st._nid]!=null; + lca = anti_dep(load,late[st._nid],lca,st,anti); break; case PhiNode phi: // Repeat anti-dep for matching Phi inputs. @@ -281,10 +280,10 @@ public abstract class GlobalCodeMotion { if( phi.in(i)==load.mem() ) lca = anti_dep(load,phi.region().cfg(i),lca,null,anti); break; - case NewNode st: break; - case ReturnNode ret: break; // Load must already be ahead of Return - case MemMergeNode ret: break; // Mem uses now on ScopeMin - case NeverNode never: break; + case NewNode st: + assert late[st._nid]!=null; + lca = anti_dep(load,late[st._nid],lca,st,anti); + break; default: throw Utils.TODO(); } } @@ -296,7 +295,7 @@ public abstract class GlobalCodeMotion { // Stores are already placed. Constrain the load at that block only. if( anti[stblk._nid]==load._nid ) { lca = stblk.domLCA(lca,null); - if( lca==stblk && st!=null && st._inputs.find(load) == -1 ) + if( lca==stblk && st!=null && !(st instanceof CallNode) && st._inputs.find(load) == -1 ) st.addDef(load); // Same-block load must precede the store. } return lca; diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 5d6ba060..fc60a385 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -535,8 +535,8 @@ public class RegAlloc { if( defreg != usereg && splitBypass(bb,j,n,defreg) ) usereg = lrg(n.in(1))._reg; - // Split has same reg? Useless! Can remove it! - if( defreg == usereg ) { + // Same register, or the next instruction can use the source directly. + if( defreg == usereg || splitForward(bb,j,n,usereg) ) { n.removeSplit(); j--; continue; @@ -549,6 +549,18 @@ public class RegAlloc { } } + // A sole, adjacent use can read the source register directly. Nothing can + // clobber it in between; only the operand mask and two-address tie remain. + private boolean splitForward( CFGNode bb, int j, Node split, int reg ) { + if( split.nOuts()!=1 || j+1==bb.nOuts() ) return false; + Node use = split.out(0); + if( use!=bb.out(j+1) || use instanceof PhiNode || use instanceof CFGNode || + !(use instanceof MachNode mach) ) return false; + int i = use._inputs.find(split); + RegMask mask = mach.regmap(i); + return mask!=null && mask.test(reg) && mach.twoAddress()!=i; + } + private boolean splitBypass( CFGNode bb, int j, Node lo, int defreg ) { // Attempt to bypass split Node hi = lo.in(1); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java new file mode 100644 index 00000000..7d4f1fb8 --- /dev/null +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -0,0 +1,240 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.codegen.CodeGen; +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); } + + public BulkMemPhiNode(BulkMemPhiNode phi) { super(phi); _aliases = phi._aliases; } + + @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,CodeGen.CODE.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 ParmNode parm -> 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. + addDepForwards(use); + 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 || use instanceof CallNode || use instanceof ParmNode + : "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++ ) + CodeGen.CODE.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; + CodeGen.CODE.add(bulk); + CodeGen.CODE.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(CodeGen.CODE.add(preciseInput(in(i),alias))); + return CodeGen.CODE.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/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java index c8cca355..0432bcbc 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.Utils; import com.seaofnodes.simple.type.*; import java.util.BitSet; @@ -23,6 +23,25 @@ public class LoadNode extends MemOpNode { super(loc, name, alias, true, glb, mem, ptr, off); } + @Override boolean canDrop(MemOpNode other, Node dep) { + return super.canDrop(other,dep) && !clobbered(dep); + } + + // Check only immediate memory users. Writers clobber memory; Phis and + // aggregates might lead to a clobber, so stop rather than search further. + private boolean clobbered(Node dep) { + Node mem = mem(); + dep.addDepForwards(mem); + for( Node use : mem._outputs ) { + if( use==null ) continue; + dep.addDepForwards(use); + if( use instanceof StoreNode || use instanceof PhiNode || + use instanceof MemMergeNode || + use instanceof NewNode || use instanceof CallNode ) return true; + } + return false; + } + // Debugger label @Override public String label() { return "ld_"+mlabel(); } @Override @@ -30,33 +49,24 @@ 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,CodeGen.CODE.add(merge.alias(_alias))); + return this; + } Node ptr = ptr(); Node mem = mem(); - // Simple Load-after-Store on same address. - if( mem instanceof StoreNode st && - ptr == st.ptr() && off() == st.off() ) { // Must check same object - assert _name.equals(st._name); // Equiv class aliasing is perfect - return extend(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 - return zero(nnn); // Load zero from new + Node win = find(mem,ptr,null,null); + if( win!=null ) return folded(win); // Uplift control to a prior dominating load. for( Node memuse : mem._outputs ) @@ -65,49 +75,7 @@ public class LoadNode extends MemOpNode { cfg0()!=null && cfg0().domLCA(ld.cfg0(),this) == ld.cfg0() ) // Higher control means load is legal earlier return ld; - // Load-after-Store on same address, but bypassing provably unrelated - // stores. This is a more complex superset of the above two peeps. - // "Provably unrelated" is really weak. - if( ptr instanceof ReadOnlyNode ro ) - ptr = ro.in(1); - outer: - while( true ) { - switch( mem ) { - case StoreNode st: - if( ptr == addDep(st.ptr()) && off() == st.off() ) - return extend(castRO(st.val())); // Proved equal - // Can we prove unequal? Offsets do not overlap? - if( !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 - mem = st.mem(); // Proved never equal - break; - case PhiNode phi: - // Assume related - addDep(phi); - break outer; - case ConstantNode top: break outer; // Assume shortly dead - case ProjNode mproj: // Memory projection - switch( mproj.in(0) ) { - case NewNode nnn1: - if( ptr instanceof ProjNode pproj && pproj.in(0) == mproj.in(0) ) - return zero(nnn1); - if( !(ptr instanceof ProjNode pproj && pproj.in(0) instanceof NewNode) ) - break outer; // Cannot tell, ptr not related to New - mem = nnn1.in(nnn1.findAlias(_alias));// Bypass unrelated New - break; - case StartNode start: break outer; - case CallEndNode cend: break outer; // TODO: Bypass no-alias call - default: throw Utils.TODO(); - } - break; - case MemMergeNode merge: mem = merge.alias(_alias); break; - - default: - throw Utils.TODO(); - } - } + if( ptr instanceof ReadOnlyNode ro ) ptr=ro.in(1); // Push a Load up through a Phi, as long as it collapses on at least // one arm. If at a Loop, the backedge MUST collapse - else we risk @@ -116,19 +84,27 @@ 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 && + // Array access control must not be moved across the merge. + in(0)==null && // Offset can be hoisted off() instanceof ConstantNode && // Pointer can be hoisted hoistPtr(ptr,memphi) ) { - // Profit on RHS/Loop backedge - if( profit(memphi,2) || - // Else must not be a loop to count profit on LHS. - (!(memphi.region() instanceof LoopNode) && profit(memphi,1)) ) { - Node ld1 = ld(1); - Node ld2 = ld(2); - return new PhiNode(_name,_declaredType,memphi.region(),ld1,ld2); + // Returning to this memory means no change only if the pointer + // is also loop invariant. A pointer Phi may select another object. + Node stop = memphi.region() instanceof LoopNode && + !(ptr instanceof PhiNode p && p.region()==memphi.region()) ? memphi : null; + if( find(memphi.in(2),ptr,stop,new BitSet())!=null || + (!(memphi.region() instanceof LoopNode) && find(memphi.in(1),ptr,null,new BitSet())!=null) ) { + PhiNode phi = new PhiNode(_name,_declaredType,memphi.region()).keep(); + phi.setType(_type); // Backedge searches may return this value Phi. + for( int i=1; i<memphi.nIns(); i++ ) { + Node p = ptr instanceof PhiNode pp && pp.region()==memphi.region() ? pp.in(i) : ptr; + phi.addDef(load(memphi.in(i),p,stop,phi)); + } + return CodeGen.CODE.add(phi.unkeep()); } } @@ -143,9 +119,66 @@ public class LoadNode extends MemOpNode { return castRO(new ConstantNode(zero).peephole()); } - private Node ld( int idx ) { - Node mem = mem(), ptr = ptr(); - return new LoadNode(_loc,_name,_alias,_declaredType,mem.in(idx),ptr instanceof PhiNode && ptr.in(0)==mem.in(0) ? ptr.in(idx) : ptr, off()).peephole(); + // Search only; no new nodes or rewiring. Return a Store/New that folds, + // the unchanged loop memory, or a merge whose every arm folds. Null fails. + // Register dependencies so a later pointer/offset rewrite retries the query. + private Node find(Node mem, Node ptr, Node stop, BitSet visit) { + if( ptr instanceof ReadOnlyNode ro ) ptr=ro.in(1); + while( mem!=null ) { + addDep(mem); + if( mem==stop ) return mem; + switch( mem ) { + case MemMergeNode merge: mem=merge.alias(_alias); break; + case StoreNode st: + addDep(st.ptr()); + if( _alias==st._alias && ptr==st.ptr() && off()==st.off() ) return st; + if( _alias==st._alias && !neverAlias(ptr,st.ptr()) && + !addDep(off())._type.join(addDep(st.off())._type).isHigh() ) return null; + mem=st.mem(); + break; + case ProjNode proj: + if( !(proj.in(0) instanceof NewNode nnn) ) return null; + if( ptr instanceof ProjNode p && p.in(0)==nnn ) return nnn; + if( !(ptr instanceof ProjNode p && p.in(0) instanceof NewNode) ) return null; + mem=nnn.mem(); // Distinct allocations cannot overlap. + break; + case MemPhiNode phi: + addDep(phi.region()); + // Only the original loop closes a successful cycle. Another + // loop or an unfinished merge needs a separate proof. + if( visit==null || !(phi.region() instanceof RegionNode r) || r instanceof LoopNode || + r.inProgress() || phi.inProgress() || r._type!=Type.CONTROL ) return null; + if( visit.get(phi._nid) ) return phi; // Already proved every arm. + for( int i=1; i<phi.nIns(); i++ ) + if( find(phi.in(i),ptr,stop,visit)==null ) return null; + visit.set(phi._nid); + return phi; + default: return null; + } + } + return null; + } + + private Node folded(Node win) { + return win instanceof StoreNode st ? extend(castRO(st.val())) : zero((NewNode)win); + } + + // Materialize only after the profitability search succeeds. The value Phi + // stands for a load which comes back around the loop with unchanged memory. + private Node load(Node mem, Node ptr, Node stop, PhiNode value) { + Node win=find(mem,ptr,stop,new BitSet()); + if( win!=null ) { + if( win==stop ) return value; + if( win instanceof MemPhiNode mp ) { + PhiNode phi=new PhiNode(_name,_declaredType,mp.region()).keep(); + for( int i=1; i<mp.nIns(); i++ ) phi.addDef(load(mp.in(i),ptr,stop,value)); + return phi.unkeep().peephole(); + } + return folded(win).peephole(); + } + LoadNode ld=new LoadNode(_loc,_name,_alias,_declaredType,mem,ptr,off()); + ld.setDef(0,in(0)); + return ld.peephole(); } private static boolean neverAlias( Node ptr1, Node ptr2 ) { @@ -174,16 +207,6 @@ public class LoadNode extends MemOpNode { return false; } - // Profitable if we find a matching Store on this Phi arm. - 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() ) return true; - if( px instanceof StoreNode st1 && ptr()==st1.ptr() && off()==st1.off() ) return true; - addDep(px); - return false; - } - // Read-Only is a deep property, and cannot be cast-away private Node castRO(Node rez) { if( ptr()._type.isFinal() && !rez._type.isFinal() ) @@ -205,4 +228,5 @@ public class LoadNode extends MemOpNode { Node shl = new ShlNode(null,val,shf.keep()).peephole(); return new SarNode(null,shl,shf.unkeep()); } + } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 3d69b94d..bb82fe1a 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -57,11 +57,12 @@ public class LoopNode extends RegionNode { // Now fold control into the exit. Might have 1 valid exit, or an // XCtrl or a bunch of prior NeverNode exits. Node top = new ConstantNode(Type.TOP).peephole(); - Node memout = new MemMergeNode(false); - memout.addDef(f); // placeholder for control + MemMergeNode memout = new MemMergeNode(new ConstantNode(TypeMem.BOT).peephole()); + memout.setDef(0,f); for( Node u : _outputs ) - if( u instanceof PhiNode phi && phi._type.isa(TypeMem.BOT) ) - memout.addDef(phi); + if( u instanceof BulkMemPhiNode ) memout.setDef(1,u); + else if( u instanceof MemPhiNode phi ) memout.alias(phi._alias,phi); + memout.init(); Node ctrl = ret.ctrl(), mem = ret.mem(), expr = ret.expr(); if( ctrl!=null && ctrl._type != Type.XCONTROL ) { @@ -72,7 +73,7 @@ public class LoopNode extends RegionNode { // Nope, insert an aligned exit layer RegionNode r = new RegionNode(_loc,null,ctrl).init(); ctrl = r; r._ltree = stop._ltree; - mem = new PhiNode(r,mem ).init(); + mem = new BulkMemPhiNode(ScopeNode.MEM0,r,mem).init(); expr = new PhiNode(r,expr).init(); } // Append new Never exit diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 72e381ca..c1d11f88 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -5,158 +5,84 @@ import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.*; import java.util.*; -/** - * Memory Merge - a merge of many aliases into a "fat memory". All aliases - * are here, but most will be lazy - take the default fat memory. +/** 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(MemMergeNode mem) { super(mem); } - /* - * In-Progress means this is being used by the Parser to track memory - * aliases. No optimizations are allowed. When no longer "in progress" - * normal peeps work. - */ - public final boolean _inProgress; - - public MemMergeNode( boolean inProgress) { _type = TypeMem.BOT; _inProgress = inProgress; } - public MemMergeNode(MemMergeNode mem) { super(mem); _inProgress = false; } - - - // If being used by a Scope, this is "in progress" from the Parser. - // Otherwise, it's a memory merge - boolean inProgress() { return _inProgress; } - - @Override public String label() { return "ALLMEM"; } - @Override public boolean isMem() { return true; } - - @Override - public StringBuilder _print1(StringBuilder sb, BitSet visited) { - sb.append(_inProgress ? "Merge[" : "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.mem().alias(j); - } - if( n==null ) sb.append("___ "); - else n._print0(sb, visited).append(" "); - } - sb.setLength(sb.length()-1); - return sb.append("]"); + public MemMergeNode(Node bulk) { super(null,bulk); _type = TypeMem.BOT; } + public MemMergeNode(Node bulk, int alias, Node precise) { + this(bulk); + alias(alias,precise); } - - // Make a memory merge: no longer a Scope really, tracking memory state but - // not related to the parser in any way. - public Node merge() { - // Force default memory to not be lazy - MemMergeNode merge = new MemMergeNode(false); - for( Node n : _inputs ) - merge.addDef(n); - merge._mem(1,null); - return merge.peephole(); + 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; } - - @Override public Type compute() { return TypeMem.BOT; } - - @Override public Node idealize() { - if( inProgress() ) return null; - - // If not merging any memory (all memory is just the default) - if( allDefault() ) - return in(1); // Become default memory - - return null; + public void alias(int alias, Node mem) { + assert alias > 1; + while( nIns()<=alias ) addDef(null); + setDef(alias,mem); } - private boolean allDefault() { - for( int i=2; i<nIns(); i++ ) - if( in(1) != in(i) ) - return false; - return true; - } - - public Node in( Var v ) { return in(v._idx); } - - public 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 ) { - MemMergeNode 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); + // Scalar contents of one alias. New zeroes the allocated fields; + // 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) { + dep.addDep(mem); + 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; + dep.addDep(nnn); + return contents(nnn.mem(),alias,dep).meet(nnn.field(alias)._type.makeZero()); } - // Memory projections are made lazily; expand as needed - return st==null ? old : alias(alias,st); // Not lazy, so this is the answer - } - - - void _merge( MemMergeNode 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 alias as it will trigger a phi creation - Node lhs = this._mem(i,null); - Node rhs = that._mem(i,null); - alias(i, new PhiNode(Parser.memName(i), lhs._type.glb().meet(rhs._type.glb()), r, lhs, rhs).peephole()); - } + // Function parameters and call results may contain arbitrary heap values. + // Their bulk memory types do not imply empty or zero-filled storage. + 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; } - // Fill in the backedge of any inserted Phis - void _endLoopMem( ScopeNode scope, MemMergeNode back, MemMergeNode exit ) { - Node exit_def = exit.alias(1); - for( int i=1; i<nIns(); i++ ) { - if( in(i) instanceof PhiNode phi && phi.region()==scope.ctrl() ) { - assert phi.in(2)==null; - phi.setDef(2,back.in(i)==scope ? phi : back.in(i)); // Fill backedge + @Override public String label() { return "MemMerge"; } + @Override public boolean isMem() { return true; } + @Override public Type compute() { return TypeMem.BOT; } + @Override public 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(" "); } - if( exit_def == scope ) // Replace a lazy-phi on the exit path also - exit.alias(i,in(i)); - } + return sb.append("]"); } - // Now one-time do a useless-phi removal - void _useless( ) { + @Override public Node idealize() { + boolean progress=false, allDefault=true; for( int i=2; i<nIns(); i++ ) { - if( in(i) instanceof PhiNode phi ) { - // Do an eager useless-phi removal - Node in = phi.peephole(); - CodeGen.CODE.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 - } + if( in(i)!=null && in(i)==in(1) ) { setDef(i,null); progress=true; } + if( in(i) instanceof MemMergeNode mem ) { + setDef(i,CodeGen.CODE.add(mem.alias(i))); + progress=true; } + if( in(i)!=null ) allDefault=false; } - } - - @Override public boolean eq( Node n ) { - return this==n || !_inProgress; + 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)); + CodeGen.CODE.add(mem.in(1)); + setDef(1,mem.in(1)); + return this; + } + assert BulkMemPhiNode.checkMerge(this); + return progress ? this : null; } } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 058c86fa..344e8b2c 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -6,6 +6,7 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeMemPtr; import java.lang.StringBuilder; import java.util.BitSet; +import java.util.ArrayList; /** * Convenience common base for Load and Store. @@ -79,6 +80,8 @@ public abstract class MemOpNode extends Node { static String mlabel(String name) { return "[]".equals(name) ? "ary" : ("#".equals(name) ? "len" : name); } String mlabel() { return mlabel(_name); } + @Override public boolean isMem() { return !_isLoad; } + public Node mem() { return in(1); } public Node ptr() { return in(2); } public Node off() { return in(3); } @@ -87,6 +90,13 @@ public abstract class MemOpNode extends Node { public StringBuilder _printMach( StringBuilder sb, BitSet visited ) { throw Utils.TODO(); } + // 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) { + dep.addDep(ptr()); + return _alias==other._alias && _declaredType==other._declaredType && err()==null; + } + @Override public boolean eq(Node n) { MemOpNode mem = (MemOpNode)n; // Invariant @@ -107,4 +117,29 @@ public abstract class MemOpNode extends Node { return null; return Parser.error( "Might be null accessing '" + _name + "'",_loc); } + // 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 CallNode || + (use instanceof MemOpNode st && !st._isLoad && 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/chapter21/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java new file mode 100644 index 00000000..e5a29329 --- /dev/null +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java @@ -0,0 +1,44 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.codegen.CodeGen; +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; + } + + public MemPhiNode(MemPhiNode phi) { super(phi); _alias = phi._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( addDep(r.in(i))._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,CodeGen.CODE.add(mem.alias(_alias))); + return this; + } + return super.idealize(); + } + + @Override public boolean eq(Node n) { return _alias==((MemPhiNode)n)._alias && super.eq(n); } + @Override int hash() { return _alias; } +} diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/NewNode.java index 27f7d634..57d351ef 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -6,34 +6,35 @@ import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.type.*; 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 a zeroed object. Inputs {ctrl, $mem, size}; + * 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); assert !ptr.nullable(); _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 || nodes[1]._type==Type.NIL; - for( int i=0; i<_len; i++ ) - // Memory slices for all fields. - assert nodes[2+i]._type.isa(TypeMem.BOT); + assert nodes.length==3; + assert nodes[0]._type==Type.CONTROL || nodes[0]._type==Type.XCONTROL; + assert nodes[1]._type instanceof TypeMem; + assert nodes[2]._type instanceof TypeInteger || nodes[2]._type==Type.NIL; } - public NewNode(NewNode nnn) { super(nnn); _ptr = nnn._ptr; _len = nnn._len; } + 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; + } + + public NewNode(NewNode nnn) { super(nnn); _ptr = nnn._ptr; } - public Node mem (int idx) { return in(idx+2); } @Override public String label() { return "new_"+(_ptr._obj.isAry() ? "ary_"+_ptr._obj._fields[1]._type.str() : _ptr._obj.str()); } @Override @@ -42,32 +43,10 @@ public class NewNode extends Node implements MultiNode { return sb.append(_ptr._obj.str()); } - int findAlias(int alias) { - int idx = _ptr._obj.findAlias(alias); - assert idx!= -1; // Error, caller should be calling - return idx+2; // Skip ctrl, size - } - - // 0 - ctrl - // 1 - byte size - // 2-len+2 - aliases, one per field - // len+2 - 2*len+2 - initial values, one per field - public Node size() { return in(1); } @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++ ) { - Type mt = in(i+2)._type; - TypeMem mem = mt==Type.TOP ? TypeMem.TOP : (TypeMem)mt; - Type tfld = mem._t.meet(mem._t.makeZero()); - Type tfld2 = tfld.join(fs[i]._type); - ts[i+2] = TypeMem.make(fs[i]._alias,tfld2); - } - return TypeTuple.make(ts); + return TypeTuple.make(_ptr,TypeMem.BOT); } @Override @@ -105,9 +84,9 @@ public class NewNode extends Node implements MultiNode { _kills = kills; } public String op() { return "alloc"; } - public RegMask regmap(int i) { return i==1 ? _arg3Mask : null; } + public RegMask regmap(int i) { return i==2 ? _arg3Mask : null; } public RegMask outregmap() { return null; } - public RegMask outregmap(int idx) { return idx==1 ? _retMask : null; } + public RegMask outregmap(int idx) { return idx==0 ? _retMask : null; } public RegMask killmap() { return _kills; } public void asm(CodeGen code, SB sb) { sb.p("#calloc, ").p(code.reg(size())); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java index 1b543c69..12faf706 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/Node.java @@ -230,6 +230,7 @@ public abstract class Node implements Cloneable { // 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(); } @@ -299,6 +300,7 @@ public abstract class Node implements Cloneable { 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); CODE.addAll(n._outputs); } @@ -545,7 +547,12 @@ public abstract class Node implements Cloneable { * or output of this node, that is, it is at least one step away. The node * being added must benefit from this node being peepholed. */ - <N extends Node> N addDep( N dep ) { + <N extends Node> N addDep( N dep ) { return addDep(dep,false); } + + // Keep an explicit dependency when inspecting an immediate user's shape. + <N extends Node> N addDepForwards(N dep) { return addDep(dep,true); } + + private <N extends Node> N addDep(N dep, boolean forwards) { // Running peepholes during the big assert cannot have side effects // like adding dependencies. if( CODE._midAssert ) return dep; @@ -553,8 +560,8 @@ public abstract class Node implements Cloneable { if( obs != null ) obs.dep(this, dep); if( dep._deps==null ) dep._deps = new Ary<>(Node.class); if( dep._deps .find(this) != -1 ) return dep; // Already on list - if( dep._inputs .find(this) != -1 ) return dep; // No need for deps on immediate neighbors - if( dep._outputs.find(this) != -1 ) return dep; + if( !forwards && dep._inputs .find(this) != -1 ) return dep; // No need for deps on immediate neighbors + if( !forwards && dep._outputs.find(this) != -1 ) return dep; dep._deps.add(this); return dep; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 8ab40af6..23acd75e 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -24,6 +24,10 @@ public class PhiNode extends Node { addDef(sample); } + 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 @@ -77,10 +81,9 @@ public class PhiNode extends Node { if( r.in(i)._type == Type.XCONTROL ) return null; - // Generic "pull down op" - Node progress; - if( same_op() && (progress = drop_same_op()) != null ) - return progress; + // 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 ) { @@ -114,45 +117,71 @@ public class PhiNode extends Node { // Same op on all Phi paths; all ops have only the Phi as a use. // None have a control input. private boolean same_op() { + 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 ) { + addDepForwards(use); + return false; + } + Node busy = null; for( int i=1; i<nIns(); i++ ) { - Node op = in(i); - if( in(1).getClass() != op.getClass() || op.in(0)!=null || in(1).nIns() != op.nIns() ) - return false; // Wrong class or CFG bound or mismatched inputs - if( op.nOuts() > 1 ) { // Too many users, but addDep in case lose users - for( Node out : op._outputs ) - if( out!=null && out!=this ) - addDep(out); - return false; + Node n = in(i); + if( addDep(region().in(i))._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. + addDepForwards(n); + if( n.nOuts()>1 ) { + for( Node use : n._outputs ) + if( use!=null && use!=this ) addDepForwards(use); + 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() { - assert !(in(1) instanceof CFGNode); - Node op = in(1); - Node cp = op.copy(); - cp._type = null; // Fresh type - cp.addDef(null); // No control - + Node op = in(1), cp = op.copyEmpty(); + cp._type = null; + cp.addDef(null); for( int j=1; j<op.nIns(); j++ ) { - boolean needsPhi = false; - Node x = op.in(j); // Jth input from sample #1 + Node x = op.in(j); + boolean different = false; for( int i=2; i<nIns(); i++ ) - if( in(i).in(j) != x ) - { needsPhi=true; break; } - if( needsPhi ) { - x = new PhiNode(_label,op.in(j)._type.glb()); - x.addDef(region()); - for( int i=1; i<nIns(); i++ ) - x.addDef(in(i).in(j)); - x = x.peephole(); + 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); } - // Test not running backwards, which can happen for e.g. And's - if( cp.compute().isa(compute()) ) - return cp; + // Factoring must not widen the result (e.g. correlated And operands). + if( cp.compute().isa(compute()) ) return cp; + for( int i=1; i<nIns(); i++ ) + for( int j=1; j<in(i).nIns(); j++ ) + if( in(i).in(j)!=null ) addDep(in(i).in(j)); cp.kill(); return null; } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 64747c63..84383845 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -48,7 +48,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 && - addDep(p1.in(0))==addDep(p2.in(0)) && + addDepForwards(p1).in(0)==addDepForwards(p2).in(0) && p1.in(0) instanceof IfNode iff ) { // Replace with the iff.ctrl directly if( nIns()==3 ) return iff.ctrl(); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 5c76116f..05b19682 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -9,15 +9,7 @@ import com.seaofnodes.simple.codegen.Encoding; 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, rpc}. */ public class ReturnNode extends CFGNode { public FunNode _fun; @@ -52,7 +44,7 @@ public class ReturnNode extends CFGNode { public Type compute() { if( inProgress () ) return TypeTuple.RET; // In progress // Inlining can delete the entry while callers still use this return. - return TypeTuple.make(ctrl()._type,mem()._type,expr()._type); + return TypeTuple.make(ctrl()._type,TypeMem.BOT,expr()._type); } @Override public Node idealize() { diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 298c5a5f..e8c4f0d5 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -7,9 +7,9 @@ import java.util.*; /** * The Scope node is purely a parser helper - it tracks names to nodes with a - * stack of variables. + * stack of variable records. */ -public class ScopeNode extends MemMergeNode { +public class ScopeNode extends Node { /** * The control is a name that binds to the currently active control @@ -19,6 +19,11 @@ public class ScopeNode extends MemMergeNode { public static final String ARG0 = "arg"; public static final String MEM0 = "$mem"; + 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; @@ -34,7 +39,7 @@ public class ScopeNode extends MemMergeNode { // A new ScopeNode public ScopeNode() { - super(true); + _type = Type.BOTTOM; _vars = new Ary<>(Var .class); _lexSize= new Ary<>(Integer.class); _kinds = new Ary<>(Kind .class); @@ -70,7 +75,7 @@ public class ScopeNode extends MemMergeNode { public Node ctrl() { return in(0); } - public MemMergeNode mem() { return (MemMergeNode)in(1); } + public Node mem() { return in(lookup(MEM0)); } /** * The ctrl of a ScopeNode is always bound to the currently active @@ -83,7 +88,7 @@ public class ScopeNode extends MemMergeNode { * @return Node that was bound */ public <N extends Node> N ctrl(N n) { return setDef(0,n); } - public Node mem(Node n) { return setDef(1,n); } + public Node mem(Node n) { update(MEM0,n); return n; } public void push(Kind kind) { assert _lexSize._len==_kinds._len; @@ -166,12 +171,6 @@ public class ScopeNode extends MemMergeNode { 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. * @@ -207,7 +206,7 @@ public class ScopeNode extends MemMergeNode { // 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); } assert !v._final || st==null; @@ -246,20 +245,8 @@ public class ScopeNode extends MemMergeNode { n.keep(); dup.addDef(ctrl()); // Control input is just copied - // Memory input is a shallow copy - MemMergeNode memdup = new MemMergeNode(true), 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 && !_vars.at(i)._final ? this : in(i)); return dup; } @@ -274,22 +261,21 @@ public class ScopeNode extends MemMergeNode { */ public RegionNode mergeScopes(ScopeNode that, Parser.Lexer loc) { RegionNode r = ctrl(new RegionNode(loc,null,ctrl(), that.ctrl()).keep()); - mem()._merge(that.mem(),r); - this ._merge(that ,r); + _merge(that,r); that.kill(); // Kill merged scope CodeGen.CODE.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()); } } @@ -314,21 +300,15 @@ public class ScopeNode extends MemMergeNode { 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( _vars.at(i)._final ) continue; // Final vars did not get modified in the loop if( _vars.at(i).type().isHighOrConst() ) continue; // Cannot lift higher than a constant, so no Phi if( back.in(i) != scope ) { @@ -342,6 +322,23 @@ public class ScopeNode extends MemMergeNode { } + // 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(); + CodeGen.CODE.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/chapter21/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/StartNode.java index 4bd76f50..91bf85a1 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -3,18 +3,11 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.codegen.CodeGen; 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; @@ -45,7 +38,7 @@ public class StartNode extends LoopNode implements MultiNode { @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/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java index f15ff9bb..86dce4fc 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.node; +import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.*; import com.seaofnodes.simple.type.*; import java.util.BitSet; @@ -25,6 +26,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; } @@ -38,28 +43,25 @@ public class StoreNode extends MemOpNode { @Override public Type compute() { Type val = val()._type; - TypeMem mem = (TypeMem)mem()._type; // Invariant - if( mem == TypeMem.TOP ) return TypeMem.TOP; - 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,CodeGen.CODE.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/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index 533f2d7b..c8dea1f4 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java @@ -671,6 +671,8 @@ public class arm extends Machine { case NotNode not -> new NotARM(not); case OrNode or -> or(or); case ParmNode parm -> new ParmARM(parm); + case BulkMemPhiNode phi -> new BulkMemPhiNode(phi); + case MemPhiNode phi -> new MemPhiNode(phi); case PhiNode phi -> new PhiNode(phi); case ProjNode prj -> new ProjARM(prj); case ReadOnlyNode read -> new ReadOnlyNode(read); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java index 54c6b828..8e1cccf9 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java @@ -345,6 +345,8 @@ public class riscv extends Machine { case NotNode not -> new NotRISC(not); case OrNode or -> or(or); case ParmNode parm -> new ParmRISC(parm); + case BulkMemPhiNode phi -> new BulkMemPhiNode(phi); + case MemPhiNode phi -> new MemPhiNode(phi); case PhiNode phi -> new PhiNode(phi); case ProjNode prj -> prj(prj); case ReadOnlyNode read-> new ReadOnlyNode(read); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/LoadX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/LoadX86.java index 6e72a540..c712eb7d 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/LoadX86.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/LoadX86.java @@ -27,6 +27,11 @@ public class LoadX86 extends MemOpX86 { } static void enc( Encoding enc, Type decl, short dst, short ptr, short idx, int off, int scale ) { + // Allocation may put a full-width integer in an XMM register (or a + // floating value in a GPR). Move its bits using the selected register bank. + if( dst>=x86_64_v2.XMM_OFFSET && decl.log_size()==3 ) decl=TypeFloat.F64; + else if( dst<x86_64_v2.XMM_OFFSET && decl instanceof TypeFloat ) + decl = decl==TypeFloat.F32 ? TypeInteger.U32 : TypeInteger.BOT; if( decl == TypeFloat.F32) enc.add1(0xF3); if( decl == TypeFloat.F64) enc.add1(0xF2); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java index 2b7fddb1..4e3cda14 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java @@ -360,6 +360,8 @@ public class x86_64_v2 extends Machine { case NotNode not -> new NotX86(not); case OrNode or -> or(or); case ParmNode parm -> new ParmX86(parm); + case BulkMemPhiNode phi -> new BulkMemPhiNode(phi); + case MemPhiNode phi -> new MemPhiNode(phi); case PhiNode phi -> new PhiNode(phi); case ProjNode prj -> prj(prj); case ReadOnlyNode read-> new ReadOnlyNode(read); @@ -393,9 +395,8 @@ public class x86_64_v2 extends Machine { if( lhs instanceof LoadNode ld && ld.nOuts() == 1 && ld._declaredType.log_size() >= 3) return new AddMemX86(add, address(ld), ld.ptr(), idx, off, scale, 0, rhs); -// if(rhs instanceof LoadNode ld && ld.nOuts() == 1 && ld._declaredType.log_size() >= 3) { -// throw Utils.TODO(); // Swap load sides -// } + if( rhs instanceof LoadNode ld && ld.nOuts()==1 && ld._declaredType.log_size()>=3 ) + return new AddMemX86(add,address(ld),ld.ptr(),idx,off,scale, 0,lhs); // Attempt a full LEA-style break down. // Returns one of AddX86, AddIX86, LeaX86, or LHS diff --git a/chapter21/src/main/java/com/seaofnodes/simple/print/IRPrinter.java b/chapter21/src/main/java/com/seaofnodes/simple/print/IRPrinter.java index ffa1d742..54063cf8 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/print/IRPrinter.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/print/IRPrinter.java @@ -9,6 +9,9 @@ import com.seaofnodes.simple.type.TypeFunPtr; import java.util.ArrayList; import java.util.BitSet; import java.util.HashMap; +import java.util.Collections; +import java.util.Comparator; +import java.util.IdentityHashMap; public abstract class IRPrinter { @@ -178,6 +181,168 @@ public abstract class IRPrinter { } } + // Whole-program dump before scheduling, using printer-private RPO. + public static String prettyPrint(CodeGen code) { + SB sb = new SB(); + printLine(code._start,sb); + ArrayList<Node> globals = new ArrayList<>(); + ArrayList<FunNode> funs = new ArrayList<>(); + for( Node n : code._start._outputs ) { + if( n!=null && n.isConst() ) globals.add(n); + if( n instanceof FunNode fun && !fun.isDead() ) funs.add(fun); + } + globals.sort(Comparator.comparingInt(n -> n._nid)); + for( Node n : globals ) printLine(n,sb); + funs.sort(Comparator.comparingInt(n -> n._nid)); + for( FunNode fun : funs ) printFunction(fun,sb); + printLine(code._stop,sb); + return sb.toString(); + } + + /** Print one function without ever traversing a call-graph linkage. */ + private static void printFunction(FunNode fun, SB sb) { + sb.nl().p("--- "); + fun.sig().print(sb.p(fun._name==null ? "" : fun._name).p(" "),false); + sb.p("----------------------\n"); + + IdentityHashMap<Node,Boolean> owned = new IdentityHashMap<>(); + collectFunction(fun,fun,owned); + ArrayList<CFGNode> post = new ArrayList<>(); + controlPost(fun,owned,new IdentityHashMap<>(),post); + Collections.reverse(post); + + IdentityHashMap<Node,Integer> blocks = new IdentityHashMap<>(); + ArrayList<ArrayList<Node>> body = new ArrayList<>(); + for( int i=0; i<post.size(); i++ ) { + blocks.put(post.get(i),i); + body.add(new ArrayList<>()); + } + ArrayList<Node> nodes = new ArrayList<>(owned.keySet()); + nodes.sort(Comparator.comparingInt(n -> n._nid)); + for( Node n : nodes ) + if( !(n instanceof CFGNode) && !(n instanceof ConstantNode) ) + body.get(block(n,owned,blocks)).add(n); + + IdentityHashMap<Node,Boolean> emitted = new IdentityHashMap<>(); + for( int i=0; i<post.size(); i++ ) { + CFGNode cfg = post.get(i); + sb.nl(); + emitLocalDefs(cfg,owned,emitted,sb); + printLine(cfg,sb); + emitted.put(cfg,Boolean.TRUE); + if( cfg instanceof MultiNode ) emitProjections(cfg,emitted,sb); + // Loop-carried inputs belong in the body, not before their Phi. + for( Node n : body.get(i) ) + if( n instanceof PhiNode ) { + printLine(n,sb); + emitted.put(n,Boolean.TRUE); + } + for( Node n : body.get(i) ) emit(n,owned,emitted,sb); + } + sb.p("--- ").p(fun._name==null ? "" : fun._name).p(" ----------------------\n"); + } + + private static void emit(Node n, IdentityHashMap<Node,Boolean> owned, + IdentityHashMap<Node,Boolean> emitted, SB sb) { + if( emitted.containsKey(n) || n instanceof CFGNode || n instanceof ConstantNode || + n instanceof PhiNode || !owned.containsKey(n) ) return; + if( n instanceof ProjNode ) { + emit(input0(n),owned,emitted,sb); + return; + } + emitted.put(n,Boolean.TRUE); + emitLocalDefs(n,owned,emitted,sb); + printLine(n,sb); + if( n instanceof MultiNode ) emitProjections(n,emitted,sb); + } + + private static void emitProjections(Node n, IdentityHashMap<Node,Boolean> emitted, SB sb) { + for( Node proj : projections(n) ) { + printLine(proj,sb); + emitted.put(proj,Boolean.TRUE); + } + } + + private static void emitLocalDefs(Node n, IdentityHashMap<Node,Boolean> owned, + IdentityHashMap<Node,Boolean> emitted, SB sb) { + for( Node def : n._inputs ) + if( def!=null ) emit(def,owned,emitted,sb); + } + + // Diagnostic placement only: anchor data at its latest definition in CFG + // RPO. Phi inputs do not move the Phi out of its owning header. This uses + // local identity state, never compiler scheduling or dominator caches. + private static int block(Node n, IdentityHashMap<Node,Boolean> owned, + IdentityHashMap<Node,Integer> blocks) { + Integer old = blocks.get(n); + if( old!=null ) return old; + if( !owned.containsKey(n) || n instanceof ConstantNode ) return 0; + blocks.put(n,0); // Break incomplete data cycles in debugger snapshots. + int b=0; + if( input0(n) instanceof CFGNode || n instanceof ProjNode ) + b=block(input0(n),owned,blocks); + else + for( Node def : n._inputs ) + if( def!=null ) b=Math.max(b,block(def,owned,blocks)); + blocks.put(n,b); + return b; + } + + // Complete the CFG walk before inspecting data uses: a Phi's backedge + // users must not pull the loop's closing Region ahead of its body. + private static void controlPost(CFGNode n, IdentityHashMap<Node,Boolean> owned, + IdentityHashMap<Node,Boolean> visit, + ArrayList<CFGNode> post) { + if( visit.put(n,Boolean.TRUE)!=null ) return; + ArrayList<CFGNode> uses = new ArrayList<>(); + if( !(n instanceof ReturnNode) ) + for( Node use : n._outputs ) + if( use instanceof CFGNode cfg && owned.containsKey(cfg) && + !(cfg instanceof FunNode) && + ((cfg instanceof RegionNode && cfg._inputs.find(n)>0) || input0(cfg)==n) ) + uses.add(cfg); + uses.sort(Comparator.comparingInt(use -> use._nid)); + for( CFGNode use : uses ) controlPost(use,owned,visit,post); + post.add(n); + } + + /** Collect one function without following call-graph linkage. */ + private static void collectFunction(Node n, FunNode owner, + IdentityHashMap<Node,Boolean> visit) { + if( n==null || n.isDead() || visit.containsKey(n) ) return; + if( n instanceof FunNode fun && fun!=owner ) return; + if( n instanceof ParmNode && input0(n)!=owner ) return; + if( n instanceof StopNode || n instanceof StartNode ) return; + if( n instanceof CallEndNode && input0(n) instanceof CallNode call && + !visit.containsKey(call) ) return; + visit.put(n,Boolean.TRUE); + // A Return's users are linkage hooks, not continuation in this function. + if( !(n instanceof ReturnNode) ) + for( Node use : n._outputs ) collectFunction(use,owner,visit); + } + + private static ArrayList<Node> projections(Node multi) { + ArrayList<Node> ps = new ArrayList<>(); + for( Node use : multi._outputs ) + if( use instanceof ProjNode && !use.isDead() && input0(use)==multi ) ps.add(use); + ps.sort(Comparator.comparingInt(IRPrinter::sortOrder)); + return ps; + } + + // Raw, bounds-safe graph inspection for the debugger. In particular do + // not call an accessor which might assert, sharpen, cache, or lazily kill. + private static Node input0(Node n) { + return n==null || n._inputs.isEmpty() + ? null : n._inputs.at(0); + } + + + private static int sortOrder(Node n) { + if( n instanceof ProjNode proj ) return proj._idx; + if( n instanceof CProjNode proj ) return proj._idx; + return n._nid; + } + public static String _prettyPrint( CodeGen code ) { SB sb = new SB(); // Print the Start "block" diff --git a/chapter21/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/chapter21/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java index d6dc6ae1..a0f1ba74 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java @@ -67,7 +67,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( n instanceof MemMergeNode || i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode || n instanceof CallNode) ) return Role.MEM; + if( n instanceof MemMergeNode || (i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode || n instanceof CallNode || 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/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 14cf6e01..7da1354f 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -2,6 +2,8 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; import org.junit.Test; +import com.seaofnodes.simple.node.*; +import java.util.BitSet; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -450,4 +452,121 @@ return 0; assertEquals("return 0;", code.print()); } + @Test public void testReadBeforeStores() { + var code = new CodeGen(""" + 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().opto(); + StopNode stop = code._stop; + assertEquals("1133",Eval2.eval(code,0)); + assertEquals("2244",Eval2.eval(code,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 code = new CodeGen(NESTED_MEMORY).parse().opto(); + StopNode stop = code._stop; + for (int arg=0; arg<7; arg++) { + assertEquals("S{x="+(5L+arg)+",y="+(7L+arg*(arg+1)-(arg>=2 ? 2 : 0))+ + ",z="+(11L+2*arg-(arg>=2 ? 2 : 0))+"}",Eval2.eval(code,arg)); + } + } + + @Test public void testMemoryAtEarlyReturns() { + var code = new CodeGen(""" + 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().opto(); + StopNode stop = code._stop; + for (int arg=0; arg<2; arg++) { + assertEquals(arg==0 ? "S{x=3,y=17,z=7}" : "S{x=11,y=5,z=13}",Eval2.eval(code,arg)); + } + } + + @Test public void testKeepLoadsAtMerge() { + var code = new CodeGen(""" + 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().opto(); + StopNode stop = code._stop; + // The one-step safety check stops at the memory aggregate. + assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet())); + assertEquals("-1",Eval2.eval(code,-1)); + assertEquals("1",Eval2.eval(code,0)); + assertEquals("3",Eval2.eval(code,3)); + } + + @Test public void testDropStores() { + var code = new CodeGen(""" + struct S { int x; }; + S !s = new S; + if (arg) s.x=arg+1; else s.x=arg+2; + return s; + """).parse().opto(); + StopNode stop = code._stop; + assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); + assertEquals("S{x=2}",Eval2.eval(code,0)); + assertEquals("S{x=4}",Eval2.eval(code,3)); + } + + @Test public void testKeepReadsBeforeWrites() { + var code = new CodeGen(""" + 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().opto(); + StopNode stop = code._stop; + assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet())); + assertEquals("-1",Eval2.eval(code,-1)); + assertEquals("1",Eval2.eval(code,0)); + assertEquals("3",Eval2.eval(code,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/chapter21/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter10bTest.java new file mode 100644 index 00000000..5d78ae06 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter10bTest.java @@ -0,0 +1,60 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; +import org.junit.Test; +import static org.junit.Assert.*; + +public class Chapter10bTest { + @Test public void testIndependentField() { + var code = new CodeGen(""" + 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().opto(); + var stop = code._stop; + assertEquals("return 42;",stop.toString()); + assertEquals("42",Eval2.eval(code,5)); + assertNull(stop.walk(n -> n instanceof LoadNode ? n : null)); + } + + @Test public void testParallelMemoryPhis() { + var code = new CodeGen(""" + 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().opto(); + var stop = code._stop; + 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) && !(n instanceof ParmNode)); + return null; + }); + assertTrue(phis[0]>=3); + assertEquals("S{x=1,y=2,z=3}",Eval2.eval(code,4)); + } + + @Test public void testLateSliceWorklist() { + // 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 code = new CodeGen(Chapter10Test.NESTED_MEMORY,com.seaofnodes.simple.type.TypeInteger.BOT,seed).parse(); + code.opto(); + assertEquals("S{x=9,y=25,z=17}",Eval2.eval(code,4)); + } + } +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java index 7af35b56..b83516e3 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -174,7 +174,7 @@ while(v1) break; return v1; """); code.parse().opto(); - assertEquals("return Phi(Loop,(((1<<arg)&1)&Shl),0);", code.print()); + assertEquals("return (Phi(Loop,((1<<arg)&1),0)&Phi(Loop,Shl,4294967295));", code.print()); assertEquals("1", Eval2.eval(code, 0)); } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java index 5899763f..571a0d54 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -255,4 +255,27 @@ return new Square; assertEquals("Square{side=3.0,diag=1.7320508075688772}", Eval2.eval(code, 3)); assertEquals("Square{side=4.0,diag=2.0}", Eval2.eval(code, 4)); } + 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() { + var code = new CodeGen(CONSTRUCTOR_MEMORY).parse().opto(); + assertEquals("111249",Eval2.eval(code,0)); + assertEquals("222352",Eval2.eval(code,1)); + } } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter17Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter17Test.java index 78515083..5de4ec3c 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter17Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter17Test.java @@ -368,7 +368,7 @@ var b = arg ? new Bar { next = (arg==2) ? new Bar{x=2;}; x=1; }; return b ? b.next ? b.next.x : b.x; // parses "b ? (b.next ? b.next.x : b.x) : 0" """); code.parse().opto(); - assertEquals("return Phi(Region,.x,0);", code.print()); + assertEquals("return Phi(Region,.x,0,.x);", code.print()); assertEquals("0", Eval2.eval(code, 0)); assertEquals("1", Eval2.eval(code, 1)); assertEquals("2", Eval2.eval(code, 2)); diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 5743546e..e1e254fe 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -438,4 +438,70 @@ return p.coffee_count; assertEquals("1", Eval2.eval(code, 2)); } + static final String CALL_MEMORY = """ + struct S { int x; int y; }; + val bump = { S s, int d -> int old=s.x; s.x=old+d; return old; }; + S !a = new S { x=10; y=7; }; + S !b = new S { x=20; y=9; }; + S !p=a; if (arg) p=b; + int before=p.x; + int old=bump(p,3); + int after=p.x; + bump(a,5); + return before*1000000+old*10000+after*100+a.x+a.y; + """; + + @Test public void testCallMemory() { + var code = new CodeGen(CALL_MEMORY).parse().opto(); + int[] calls={0}; + code._stop.walk(n -> { if(n instanceof CallNode) calls[0]++; return null; }); + assertEquals(2,calls[0]); // Keep real calls so this checks scheduling across them. + assertEquals("10101325",Eval2.eval(code,0)); + assertEquals("20202322",Eval2.eval(code,1)); + code._stop.walk(n -> { + if(n instanceof CallNode call) { + assertEquals(5,call.nIns()); // No scheduling edges may become extra arguments. + assertTrue(call.fptr()._type instanceof TypeFunPtr); + } + return null; + }); + } + + static final String RECURSIVE_MEMORY = """ + struct S { int x; }; + val rec = { S s, int n -> + if (n==0) return s.x; + int before=s.x; + s.x=before+1; + return before+rec(s,n-1); + }; + S !s=new S { x=10; }; + int value=rec(s,arg); + return value*100+s.x; + """; + + @Test public void testRecursiveMemory() { + var code = new CodeGen(RECURSIVE_MEMORY).parse().opto(); + for(int n=0; n<7; n++) + assertEquals(Long.toString((10L*(n+1)+n*(n+1)/2)*100+10+n),Eval2.eval(code,n)); + } + + static final String INLINE_MEMORY = """ + struct S { int x; int y; }; + val make = { S s -> + S t = new S { x=s.x+1; y=3; }; + s.y=9; + return t; + }; + S !a = new S { x=arg+40; y=7; }; + S t=make(a); + return a.x*10000+a.y*100+t.x+t.y; + """; + + @Test public void testInlineAllocationMemory() { + var code = new CodeGen(INLINE_MEMORY).parse().opto(); + assertNull(code._stop.walk(n -> n instanceof CallNode ? n : null)); + assertEquals("400944",Eval2.eval(code,0)); + assertEquals("420946",Eval2.eval(code,2)); + } } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java index 1c427d4f..1149c518 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -350,4 +350,72 @@ return sq(arg) + sq(3); code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("Stop[ return (add,#2,#2); return (mul,Parm_x(sq,int),x); ]", code.print()); } + + @Test public void testSelectedMemory() { + for( String cpu : new String[]{"x86_64_v2","riscv","arm"} ) + for( String src : new String[]{Chapter10Test.NESTED_MEMORY,Chapter16Test.CONSTRUCTOR_MEMORY, + Chapter18Test.CALL_MEMORY,Chapter18Test.RECURSIVE_MEMORY} ) { + var code = new CodeGen(src).parse().opto().typeCheck(); + var aliases = memoryPhis(code._stop); + code.loopTree().instSelect(cpu,"SystemV"); + assertEquals(aliases,memoryPhis(code._stop)); + code.GCM().localSched(); + code._stop.walk(n -> { + if( !(n instanceof CFGNode) && !(n instanceof ProjNode) ) + assertTrue(n.in(0) instanceof CFGNode); + if( n instanceof NewNode nn ) { + assertEquals(2,((TypeTuple)nn._type)._types.length); + assertTrue(nn.mem() instanceof MemMergeNode); + assertNull(nn.mem().in(1)); // Partial allocation input. + nn.cacheRegs(code); + MachNode mach = (MachNode)nn; + assertNull(mach.regmap(1)); + assertNotNull(mach.regmap(2)); + assertNotNull(mach.outregmap(0)); + assertNull(mach.outregmap(1)); + } + if( n instanceof CallNode call ) { + assertEquals(4,call.nIns()); // ctrl, memory, two args; direct target is embedded. + } + return null; + }); + } + } + + private static java.util.ArrayList<String> memoryPhis(Node stop) { + var phis = new java.util.ArrayList<String>(); + stop.walk(n -> { + if( n instanceof MemPhiNode phi ) phis.add("alias:"+phi._alias); + if( n instanceof BulkMemPhiNode phi ) phis.add("bulk:"+phi._aliases); + assertFalse(n instanceof PhiNode && n.isMem() && + !(n instanceof MemPhiNode) && !(n instanceof BulkMemPhiNode) && !(n instanceof ParmNode)); + return null; + }); + java.util.Collections.sort(phis); + return phis; + } + + @Test public void testFoldedReadBeforeWrites() { + var code = new CodeGen(""" + struct S { int x; }; + S !a = new S { x=11; }; S !b = new S { x=22; }; + S !p = a; if( arg ) p = b; + int before = p.x + arg; + a.x=33; b.x=44; + return before; + """).parse().opto().typeCheck().loopTree().instSelect("x86_64_v2","SystemV").GCM().localSched(); + var read = (MemOpNode)code._stop.walk(n -> + n instanceof com.seaofnodes.simple.node.cpus.x86_64_v2.AddMemX86 ? n : null); + assertNotNull(read); + int writes = 0; + for( Node use : read.antiDeps() ) + if( use instanceof MemOpNode st && st.isMem() ) { + assertSame(read.cfg0(),st.cfg0()); + assertTrue(st._inputs.find(read)>=0); + assertTrue(read.cfg0()._outputs.find(read)<st.cfg0()._outputs.find(st)); + assertNull(((MachNode)st).regmap(st._inputs.find(read))); + writes++; + } + assertEquals(1,writes); // The next Store follows this first clobber through memory. + } } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 0691d4a2..250acaa2 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -142,9 +142,9 @@ return sqrt(farg) + sqrt(farg+2.0); @Test public void testAlloc2() { String src = "int[] !xs = new int[3]; xs[arg]=1; return xs[arg&1];"; - testTarget(src,"x86_64_v2","SystemV",3,"return .[];"); + testTarget(src,"x86_64_v2","SystemV",4,"return .[];"); testTarget(src,"riscv","SystemV",8,"return .[];"); - testTarget(src,"arm","SystemV",10,"return .[];"); + testTarget(src,"arm","SystemV",9,"return .[];"); } @Test @@ -160,7 +160,7 @@ for( int i=0; i<ary#-1; i++ ) ary[i+1] += ary[i]; return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 """; - testTarget(src,"x86_64_v2", "SystemV",9,"return .[];"); + testTarget(src,"x86_64_v2", "SystemV",7,"return .[];"); testTarget(src,"riscv" , "SystemV",7,"return (add,.[],(mul,.[],1000));"); testTarget(src,"arm" , "SystemV",5,"return (add,.[],(mul,.[],1000));"); } @@ -203,9 +203,9 @@ s.cs[0] = 67; // C s.cs[1] = 108; // l hashCode(s); """; - testTarget(src,"x86_64_v2", "SystemV",14,null); - testTarget(src,"riscv" , "SystemV", 14,null); - testTarget(src,"arm" , "SystemV", 13,null); + testTarget(src,"x86_64_v2", "SystemV",15,null); + testTarget(src,"riscv" , "SystemV", 10,null); + testTarget(src,"arm" , "SystemV", 10,null); } @Test @@ -364,8 +364,29 @@ return a; """; testTarget(src,"x86_64_v2", "SystemV",52,null); testTarget(src,"riscv" , "SystemV",44,null); - testTarget(src,"arm" , "SystemV",44,null); + testTarget(src,"arm" , "SystemV",41,null); //assertEquals("int[ 1,2,3,4,5,6,7,8,9,10,11]", Eval2.eval(code, 11)); } + + @Test public void testMemoryAllocation() { + for( String cpu : new String[]{"x86_64_v2","riscv","arm"} ) + for( String src : new String[]{Chapter10Test.NESTED_MEMORY,Chapter16Test.CONSTRUCTOR_MEMORY, + Chapter18Test.CALL_MEMORY,Chapter18Test.RECURSIVE_MEMORY, + "int[] !a = new int[3]; a[arg]=arg; return a[0]+1;"} ) { + var code = new CodeGen(src).parse().opto().typeCheck().loopTree() + .instSelect(cpu,"SystemV").GCM().localSched().regAlloc(); + com.seaofnodes.simple.codegen.RegAllocTestSupport.checkRegisters(code); + code._stop.walk(n -> { + // Whole memory, precise Phis, and memory projections need no register. + if( n._type instanceof com.seaofnodes.simple.type.TypeMem ) + assertEquals(-1,code._regAlloc.regnum(n)); + if( n instanceof com.seaofnodes.simple.node.NewNode nn ) { + assertTrue(code._regAlloc.regnum(nn.proj(0))>=0); + assertEquals(-1,code._regAlloc.regnum(nn.proj(1))); + } + return null; + }); + } + } } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java index 39b410d5..bc300217 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21AllocTest.java @@ -49,7 +49,7 @@ return sqrt(arg) + sqrt(arg+2); String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash.smp")); Chapter21Test.testCPU(src,"x86_64_v2", "SystemV", 9,null); Chapter21Test.testCPU(src,"riscv" , "SystemV", 3,null); - Chapter21Test.testCPU(src,"arm" , "SystemV", 3,null); + Chapter21Test.testCPU(src,"arm" , "SystemV", 1,null); } } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 6c943904..a8712a2e 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -217,6 +217,7 @@ public class Chapter21Test { @Test public void testCoalescing() { com.seaofnodes.simple.codegen.RegAllocTestSupport.coalescing(); } + @Test public void testCopyForward() throws Exception { com.seaofnodes.simple.codegen.RegAllocTestSupport.copyForward(); } @Test public void testRisc64BitStore() { byte[] mem = new byte[24]; EvalRisc5 cpu = new EvalRisc5(mem,mem.length); @@ -299,7 +300,7 @@ public class Chapter21Test { String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/stringHash.smp")); testCPU(src,"x86_64_v2", "SystemV", 9,null); testCPU(src,"riscv" , "SystemV", 3,null); - testCPU(src,"arm" , "SystemV", 3,null); + testCPU(src,"arm" , "SystemV", 1,null); } @Test public void testStringExport() throws IOException { @@ -353,11 +354,11 @@ public class Chapter21Test { String sprimes = sb.p("]").toString(); // Compile, link against native C; expect the above string of primes to be printed out by C - TestC.run("sieve",sprimes, 178); + TestC.run("sieve",sprimes, 185); // Evaluate on RISC5 emulator; expect return of an array of primes in // the simulated heap. - EvalRisc5 R5 = TestRisc5.build("sieve", 100, 89, false); + EvalRisc5 R5 = TestRisc5.build("sieve", 100, 92, false); int trap = R5.step(10000); assertEquals(0,trap); // Return register A0 holds sieve(100) @@ -369,7 +370,7 @@ public class Chapter21Test { // Evaluate on ARM5 emulator; expect return of an array of primes in // the simulated heap. - EvalArm64 A5 = TestArm64.build("sieve", 100, 93, false); + EvalArm64 A5 = TestArm64.build("sieve", 100, 91, false); int trap_arm = A5.step(10000); assertEquals(0, trap_arm); int ary_arm = (int)A5.regs[arm.X0]; diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Eval2.java b/chapter21/src/test/java/com/seaofnodes/simple/Eval2.java index 82839399..dabd63cc 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Eval2.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Eval2.java @@ -331,7 +331,7 @@ public abstract class Eval2 { private static Object alloc(NewNode alloc) { TypeStruct type = alloc._ptr._obj; if( type.isAry() ) { - long sz = (Long)val(alloc.in(1)); + long sz = (Long)val(alloc.size()); long x = offToIdx(sz, type); int n = (int)x; if( n!=x || n<0 ) @@ -444,9 +444,9 @@ public abstract class Eval2 { case TypeRPC rpc -> sb.p(x.toString()); case TypeMem mem -> sb.p("$mem"); case TypeTuple tt -> { - if( tt._types.length>1 && tt._types[1] instanceof TypeMemPtr ) + if( tt._types.length>1 && tt._types[0] instanceof TypeMemPtr ) // Assume a NewNode - yield _print( tt._types[1], x, sb, visit ); + yield _print( tt._types[0], x, sb, visit ); throw Utils.TODO(); } case Type tt -> { diff --git a/chapter21/src/test/java/com/seaofnodes/simple/EvalArm64.java b/chapter21/src/test/java/com/seaofnodes/simple/EvalArm64.java index e5aa729b..f8996b00 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/EvalArm64.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/EvalArm64.java @@ -116,10 +116,11 @@ public class EvalArm64 { } // for the opcode we just match for bits[31:24]; switch(opcode1) { - case 0xD2: { - // movz - // get immediate - rval = (ir >> 5) & 0x7FFF; + case 0xD2: // MOVZ + case 0xF2: { // MOVK preserves the other halfwords + int shift = ((ir >> 21) & 3)*16; + rval = ((ir >> 5) & 0xFFFFL) << shift; + if( opcode1==0xF2 ) rval |= regs[rdid] & ~(0xFFFFL << shift); break; } case 0x38: { diff --git a/chapter21/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java b/chapter21/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java new file mode 100644 index 00000000..0de4e960 --- /dev/null +++ b/chapter21/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java @@ -0,0 +1,176 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.codegen.RegAllocTestSupport; +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.node.cpus.arm.arm; +import com.seaofnodes.simple.node.cpus.riscv.riscv; +import java.io.IOException; +import java.nio.file.Files; +import java.nio.file.Path; +import org.junit.Test; +import static org.junit.Assert.*; + +// Execution regressions are separate from the fixed spill-measurement cohorts. +public class MemoryEncodingTest { + @Test public void testLoopLoadSearch() { + String[] sources = { + """ + u8[] !program=new u8[106]; u8[] !out=new u8[0]; + int sum=0; + for(int i=0; i<arg; i++) { + sum+=program#; + if(i==1) out=new u8[i+1]; + else if(i==3) out=new u8[2]; + } + return sum+out#; + """, + // One possibly aliasing arm must reject the unchanged-memory proof. + """ + struct S { int x; }; S !a=new S; S !b=new S; + a.x=10; b.x=20; S !p=a; if(arg&1) p=b; + int sum=0; + for(int i=0; i<6; i++) { + if(i==2) p.x=30; + else if(i==4) b.x=40; + sum+=a.x; + } + return sum; + """, + // Unchanged memory does not imply an unchanged loop-carried pointer. + """ + struct S { int x; }; S !a=new S; S !b=new S; + a.x=10; b.x=20; S !p=a; int sum=0; + for(int i=0; i<6; i++) { + if(i==2) a.x=30; + sum+=p.x; + p=b; if(i&1) p=a; + } + return sum; + """, + // All arms fold, but their values differ: build a value Phi. + """ + struct S { int x; }; S !a=new S; a.x=1; int sum=0; + for(int i=0; i<6; i++) { + sum+=a.x; + if(i&1) a.x=2; + else if(i==2) a.x=3; + else a.x=4; + } + return sum; + """ + }; + for( int p=0; p<sources.length; p++ ) { + CodeGen code=new CodeGen(sources[p]).parse().opto(); + if( p==0 ) assertNull(code._stop.walk(n -> + n instanceof LoadNode ld && ld.ptr() instanceof ProjNode ptr && + ptr.in(0) instanceof NewNode nn && + nn.size()._type==com.seaofnodes.simple.type.TypeInteger.constant(110) ? ld : null)); + for( int arg=0; arg<7; arg++ ) { + long expected=switch(p) { + case 0 -> 106*arg+(arg>=2 ? 2 : 0); + case 1 -> (arg&1)==0 ? 140 : 60; + case 2 -> 130; + default -> 16; + }; + assertEquals(Long.toString(expected),Eval2.eval(code,arg)); + } + } + } + + private static final String[] SOURCES = { + Chapter16Test.CONSTRUCTOR_MEMORY, + Chapter18Test.CALL_MEMORY, + Chapter18Test.RECURSIVE_MEMORY, + Chapter18Test.INLINE_MEMORY, + "int[] !a = new int[7]; a[arg]=arg+3; return a[0]+1;", + """ + int[] !a = new int[7]; + for( int i=0; i<7; i++ ) a[i]=i+arg; + for( int i=0; i<6; i++ ) a[i+1]+=a[i]; + return a[6]; + """ + }; + + private static long expected(int program, long arg) { + return switch(program) { + case 0 -> arg==0 ? 111249 : 222351+arg; + case 1 -> arg==0 ? 10101325 : 20202322; + case 2 -> (10*(arg+1)+arg*(arg+1)/2)*100+10+arg; + case 3 -> 400944+arg*10001; + case 4 -> arg==0 ? 4 : 1; + case 5 -> 21+7*arg; + default -> throw new AssertionError(); + }; + } + + @Test public void testEmulatedMemory() throws IOException { + for( String target : new String[]{"riscv","arm"} ) + for( int p=0; p<SOURCES.length; p++ ) { + CodeGen code = new CodeGen(SOURCES[p]).driver(target,"SystemV",null); + RegAllocTestSupport.checkRegisters(code); + int entry=0; + for( var n : code._start._outputs ) + if( n instanceof FunNode fun && "main".equals(fun._name) ) + entry=code._encoding._opStart[fun._nid]; + for( int arg=0; arg<7; arg++ ) { + byte[] image = new byte[1<<20]; + byte[] bits = code._encoding.bits(); + System.arraycopy(bits,0,image,0,bits.length); + long result; + if( target.equals("riscv") ) { + EvalRisc5 cpu = new EvalRisc5(image,1<<16); + cpu._pc=entry; + cpu.regs[riscv.A0]=arg; + assertEquals(target+" program "+p+" arg "+arg,0,cpu.step(100000)); + result=cpu.regs[riscv.A0]; + } else { + EvalArm64 cpu = new EvalArm64(image,1<<16); + cpu._pc=entry; + cpu.regs[arm.X0]=arg; + assertEquals(target+" program "+p+" arg "+arg,0,cpu.step(100000)); + result=cpu.regs[arm.X0]; + } + assertEquals(target+" program "+p+" arg "+arg,expected(p,arg),result); + } + } + } + + @Test public void testNeverMemory() { + // A synthetic exit must retain both precise slices of a no-exit loop. + // Stop at scheduling: the existing allocator cannot coalesce TOP on + // the synthetic scalar return arm. + for( String target : new String[]{"x86_64_v2","riscv","arm"} ) { + CodeGen code = new CodeGen(""" + struct S { int x; int y; }; + S !a=new S; + if( arg ) while( 1 ) { a.x+=arg; a.y+=a.x; } + return a.x+a.y; + """).driver(CodeGen.Phase.LoopTree); + assertNotNull(code._stop.walk(n -> { + if( n instanceof MemMergeNode mem && + mem.in(0) instanceof CProjNode exit && exit.in(0) instanceof NeverNode ) { + assertTrue(mem.alias(2) instanceof MemPhiNode); + assertTrue(mem.alias(3) instanceof MemPhiNode); + return mem; + } + return null; + })); + code.instSelect(target,"SystemV").GCM().localSched(); + } + } + + @Test public void testNativeMemory() throws IOException { + Files.createDirectories(Path.of("build/objs")); + for( int p=0; p<SOURCES.length; p++ ) { + String file="build/objs/memory"+p; + StringBuilder c = new StringBuilder("extern long long memory(long long);\nint main() {\n"); + for( int arg=0; arg<7; arg++ ) + c.append("if(memory(").append(arg).append(")!=").append(expected(p,arg)).append("LL) return ").append(arg+1).append(";\n"); + c.append("return 0;\n}\n"); + Files.writeString(Path.of(file+".c"),c); + TestC._run("val memory = { int arg -> "+SOURCES[p]+" };", + TestC.CALL_CONVENTION,"",file+".c",file,"S","",-1); + } + } +} diff --git a/chapter21/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java b/chapter21/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java index abc2ae82..3f624fcd 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/codegen/RegAllocTestSupport.java @@ -166,6 +166,31 @@ public class RegAllocTestSupport { assertFalse("A fixed definition clobbers even before coloring",uncolored.sameBlockNoClobber(copy)); } + public static void copyForward() throws Exception { + // Forwarding, fixed operand, two-address tie, intervening clobber, + // another user, and a scheduling-only edge. + for( int kind=0; kind<6; kind++ ) { + CodeGen code = graph(); + RegAlloc alloc = new RegAlloc(code); + Op def = new Op(A,null,null,false,code._start); + alloc.newLRG(def)._reg=0; + SplitNode copy = code._mach.split("test",(byte)0,null); + copy.setDef(0,code._start); copy.setDef(1,def); + alloc.newLRG(copy)._reg=1; + if( kind==3 ) new Op(null,null,A,false,code._start); + int twoAddress = kind==2 ? 1 : 0; + RegMask mask = kind==1 ? B : kind==5 ? null : new RegMask(3L); + Op use = new Op(null,mask,null,false,code._start,copy) { + @Override public int twoAddress() { return twoAddress; } + }; + if( kind==4 ) new Op(null,B,null,false,code._start,copy); + var post = RegAlloc.class.getDeclaredMethod("postColor"); + post.setAccessible(true); post.invoke(alloc); + assertSame("copy case "+kind,kind==0 ? def : copy,use.in(1)); + assertEquals(kind==0 ? 0 : 1,alloc._spills); + } + } + public static void coalescing() { // Merge, incompatible masks, interference, capacity, and adjacency remapping. for( int kind=0; kind<5; kind++ ) { diff --git a/chapter21/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter21/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index a3b87e90..3f023bb2 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -185,7 +185,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); @@ -199,21 +199,17 @@ public class Evaluator { assert elem instanceof TypeMemPtr; } // Length value - body[0] = vall(alloc.in(2+2)); + body[0] = n; } else { body = new Object[num = type._fields.length]; for( int i=0; i<num; i++ ) body[i] = switch( alloc._ptr._obj._fields[i]._type ) { case TypeInteger ti -> 0L; - case TypeFloat tf -> 0; + case TypeFloat tf -> 0D; default -> null; }; } - 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),null}; } private Object load(LoadNode load) { |