diff options
Diffstat (limited to 'chapter25/src/main/java/com')
9 files changed, 254 insertions, 187 deletions
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index ecd23c1e..484bcaa9 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -172,17 +172,9 @@ 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) ) { - assert !( 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 _doSchedLate(n,ns,late,anti); @@ -193,9 +185,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 ) @@ -255,25 +245,32 @@ public abstract class GlobalCodeMotion { best instanceof IfNode; } + // A writer may consume a load's memory through an 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; 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 && load._alias == st._alias ) { - 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 EscapeNode esc: - if( load._alias == esc.fld()._alias ) { - assert late[mem._nid] != null; - lca = anti_dep(load,late[mem._nid],lca,mem,anti); - } + assert late[st._nid]!=null; + lca = anti_dep(load,late[st._nid],lca,st,anti); + break; + case EscapeNode st: + assert late[st._nid]!=null; + lca = anti_dep(load,late[st._nid],lca,st,anti); break; case CallNode call: assert late[call._nid]!=null; @@ -286,8 +283,6 @@ public abstract class GlobalCodeMotion { if( phi.in(i)==load.mem() ) lca = anti_dep(load,phi.region().cfg(i),lca,null,anti); break; - case ReturnNode ret: break; // Load must already be ahead of Return - case MemMergeNode ret: break; // Mem uses now on ScopeMin default: throw Utils.TODO("Should not reach here"); } } @@ -299,7 +294,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/chapter25/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java index cabf7d69..82c4af10 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -253,7 +253,7 @@ public class BulkMemPhiNode extends PhiNode { mphi.setType(TypeMem.BOT.makeFrom(alias)); for( int i=1; i<nIns(); i++ ) mphi.addDef(CodeGen.CODE.add(preciseInput(in(i),alias))); - return (MemPhiNode)mphi.peephole(); + return CodeGen.CODE.add(mphi); } MemPhiNode _findPhi(int alias) { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 193fbe17..85ca42cd 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -31,6 +31,25 @@ public class LoadNode extends MemOpNode { } @Override public Tag serialTag() { return Tag.Load; } + @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 EscapeNode || use instanceof CallNode ) return true; + } + return false; + } + // Debugger label @Override public String label() { return "ld_"+mlabel(); } @Override @@ -89,10 +108,10 @@ public class LoadNode extends MemOpNode { Node mem = mem(); Node ptr = ptr(); - // Loads into structs do not need a ctrl edge, as null-ptr checking is - // baked into the type system. Loads into arrays DO need the ctrl - // edge, at least until proper range-checking is in place. - if( in(0)!=null && ptr._type instanceof TypeMemPtr tmp && !tmp._obj.isAry() ) { + // Null checks are handled by types. Array elements retain control for + // range checks, but reading an array's length has no index to check. + if( in(0)!=null && ptr._type instanceof TypeMemPtr tmp && + (!tmp._obj.isAry() || _name.equals("#")) ) { setDef(0,null); return this; } @@ -112,19 +131,6 @@ public class LoadNode extends MemOpNode { if( _alias == 1 ) return null; - // External storage is shared even through different class namespaces. - boolean external = ptr._type instanceof TypeMemPtr tmp && - (fld=tmp._obj.field(_name)) != null && fld._extern; - - // Simple Load-after-Store on same address. - if( mem instanceof StoreNode st && - ptr == st.nnptr() && - off() == st.off() && // Must check same object - st.val()._type.isa(_type) ) { - assert _name.equals(st._name); // Equiv class aliasing is perfect - return extend(st.val()); - } - if( mem instanceof MemMergeNode merge ) { setDef(1,merge.alias(_alias)); // In support of uplifting control to a prior dominating load, if @@ -144,67 +150,9 @@ public class LoadNode extends MemOpNode { addDep(ld)._type.isa(_type) ) // and not rolling backwards 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 - (external || !neverAlias(ptr,st.ptr())) ) { // And might alias - addDep( off()); // Offsets can fold, proving unequal - addDep(st.off()); // Offsets can fold, proving unequal - 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 con: - // Load from constant memory - if( con._con instanceof TypeMem tmem ) - throw Utils.TODO("need to see a test case"); - // return ConstantNode.make(tmem._t); - break outer; // Assume shortly dead - case ProjNode mproj: // Memory projection - switch( mproj.in(0) ) { - case NewNode nnn1: - if( external ) break outer; // Class allocation does not initialize C storage - // Direct load from fresh zero/default-filled allocation. - Type decl = declaredType(); - assert decl!=Type.BOTTOM; - Type zero = decl.makeZero(); - assert zero.isa(_type); // Catch bug uninitialized null field - return ConstantNode.make(zero); - case CallEndNode cend: addDep(mproj); break outer; // TODO: Bypass no-alias call - default: throw Utils.TODO("Should not reach here"); - } - case MemMergeNode merge: mem = merge.alias(_alias); break; - case EscapeNode esc: - if( esc.self()==ptr ) // Proved equal - { mem = esc.priv(); break; } - // Mal-formed, dying - if( !(esc.self().in(0) instanceof NewNode) ) - break outer; - // Two NewNodes are always unequal - if( ptr.in(0) instanceof NewNode ) - { mem = esc.pub(); break; } - // TODO: Can we prove unequal? - break outer; - - default: - throw Utils.TODO(); - } - } + Node win = find(mem,ptr,null,null); + if( win!=null ) return folded(win); + 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 @@ -213,34 +161,119 @@ 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 && - // Not control dependent - in(0)==null && // 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); - PhiNode phi = new PhiNode(_name, memphi.region(),ld1,ld2); - phi.setType(phi.compute().join(_type)); - return phi; + // 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) ) { + // Integer loop Phis widen to i64. Keep the load's declared + // width at the result, as for ordinary typed loop variables. + if( _type instanceof TypeInteger && !declaredType().isa(_type) ) return null; + PhiNode phi = new PhiNode(_name,memphi.region()).keep(); + phi.setType(_type instanceof TypeInteger ? TypeInteger.BOT : _type); + 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)); + } + CodeGen.CODE.add(phi.unkeep()); + return _type instanceof TypeInteger ? new ConvertNode(declaredType(),phi) : phi; } } return null; } - private Node ld( int idx ) { - Node mem = mem(), ptr = ptr(); - assert in(0)==null; - assert !(ptr instanceof PhiNode && ptr.in(0)==mem.in(0)); // If fails, need to use pre-merged ptr at same phi - return new LoadNode(_loc,_name,_alias,null,mem.in(idx),ptr, off()).peephole(); + // Load a flavored zero from a New + private Node zero(NewNode nnn) { + Type zero = declaredType().makeZero(); + assert zero.isa(_type); // Catch an uninitialized non-null field + return castRO(new ConstantNode(zero).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); + Field fld; + boolean external = ptr._type instanceof TypeMemPtr tmp && + (fld=tmp._obj.field(_name))!=null && fld._extern; + while( mem!=null ) { + addDep(mem); + if( mem==stop ) return mem; + switch( mem ) { + case MemMergeNode merge: mem=merge.alias(_alias); break; + case StoreNode st: + // Alias 1 is still unresolved, not a proven different field. + if( st._alias==1 ) return null; + addDep(st.ptr()); + if( _alias==st._alias && (ptr==st.ptr() || ptr==st.nnptr()) && off()==st.off() ) { + // A full-width load cannot narrow the forwarded value. + if( declaredType() instanceof TypeInteger ti && ti.log_size()==3 && + !addDep(st.val())._type.isa(_type) ) return null; + return st; + } + if( (external || _alias==st._alias) && (external || !neverAlias(ptr,st.ptr())) && + !addDep(off())._type.join(addDep(st.off())._type).isHigh() ) return null; + mem=st.mem(); + break; + case ProjNode proj: + // New's memory is private; public memory is joined at Escape. + if( external || !(proj.in(0) instanceof NewNode nnn) ) return null; + if( declaredType()==Type.BOTTOM ) return null; + return nnn; + case EscapeNode esc: + if( external ) return null; + addDep(esc.self()); + if( esc.self()==ptr ) { mem=esc.priv(); break; } + if( neverAlias(ptr,esc.self()) ) { mem=esc.pub(); break; } + return null; + 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,mp.region()).keep(); + for( int i=1; i<mp.nIns(); i++ ) phi.addDef(load(mp.in(i),ptr,stop,value)); + return CodeGen.CODE.add(phi.unkeep().peephole()); + } + Node fold=folded(win); + if( fold!=null ) return fold.peephole(); + } + LoadNode ld=new LoadNode(_loc,_name,_alias,in(0),mem,ptr,off()); + return ld.peephole(); } private static boolean neverAlias( Node ptr1, Node ptr2 ) { @@ -269,21 +302,6 @@ public class LoadNode extends MemOpNode { return false; } - // Profitable if we find a matching Store on this Phi arm. - private boolean profit(PhiNode memphi, int idx) { - Node px = memphi.in(idx); - if( px==null ) return false; - // Memory is collapsing, no bother - if( px._type instanceof TypeMem mem && mem._t.isHighOrConst() ) - return false; - if( px instanceof StoreNode st1 && ptr()==addDep(st1.nnptr() ) && off()==st1.off() && addDep(st1.val())._type.isa(_type) ) - // To avoid cyclic pushing a Load up then down, getting here means - // the load *must* match against the Store - 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() ) diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 441edc3e..de7adede 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -8,6 +8,7 @@ import com.seaofnodes.simple.util.BAOS; import com.seaofnodes.simple.util.Utils; import java.lang.StringBuilder; import java.util.BitSet; +import java.util.ArrayList; import java.util.HashMap; import java.util.IdentityHashMap; @@ -101,6 +102,13 @@ public abstract class MemOpNode extends TypeNode { 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>1 && _alias==other._alias && declaredType()==other.declaredType() && err()==null; + } + @Override public boolean eq(Node n) { MemOpNode mem = (MemOpNode)n; // Invariant @@ -128,4 +136,30 @@ public abstract class MemOpNode extends TypeNode { return null; } + + // Memory writers which must follow this read. A packaging node is not a + // write; follow this alias through aggregates to its writers. + 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 EscapeNode esc && esc.fld()._alias==_alias) || + (use instanceof MemPhiNode phi && phi._alias==_alias) || + (use instanceof BulkMemPhiNode phi && !phi.isSplit(_alias)) ) { + if( !deps.contains(use) ) deps.add(use); + } + } + } } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java index 59c9f8e3..8842db78 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java @@ -306,6 +306,7 @@ public abstract class Node implements Cloneable { // Error is 'use' does not exist; ok for 'use' to be null. public boolean delUse( Node use ) { _outputs.del(_outputs.find(use)); + moveDepsToWorklist(); // User-count and anti-dependence queries can now change. return _outputs.isEmpty(); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java index a4c73472..9d8adb15 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -154,67 +154,77 @@ 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 busy=null; - if( in(1) instanceof ConstantNode ) - return false; - 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( in(1) instanceof MemOpNode mem ) { - // Mismatched aliases - if( mem._alias != ((MemOpNode)op)._alias ) return false; - // Load is clobbered somewhere, and can not be pulled forward past the Phi? - if( mem instanceof LoadNode ) - for( Node use : op.outs() ) - if( use instanceof StoreNode ) - return false; - } - if( in(1) instanceof EscapeNode ) - return false; - if( in(1) instanceof MemMergeNode ) - return false; // Have to keep aliases straight - if( op.nOuts() > 1 ) { - if( busy==null ) busy = op; - else { // Too many users, but addDep in case lose users - for( Node out : op._outputs ) - if( out!=null && out!=this ) - addDep(out); - for( Node out : busy._outputs ) - if( out!=null && out!=this ) - addDep(out); + Node op = in(1); + if( op instanceof EscapeNode || 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 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 = make(_label,op.in(j)._type); - 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); + } + // Do not introduce an operand Phi mixing incompatible type families. + if( t==Type.BOTTOM ) { + for( int i=1; i<ins.length; i++ ) addDep(ins[i]); + cp.kill(); + return null; + } + PhiNode phi = j==1 && op instanceof MemOpNode mem + ? new MemPhiNode(_label,mem._alias,ins) + : PhiNode.make(_label,t,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/chapter25/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 32434850..a886183e 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -48,7 +48,7 @@ public class RegionNode extends CFGNode { if( !hasPhi() && nIns()>3 && // 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/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 2683ddf5..fe379c80 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -49,6 +49,10 @@ public class StoreNode extends MemOpNode { baos.write(_size); } + @Override boolean canDrop(MemOpNode other, Node dep) { + return super.canDrop(other,dep) && _init==((StoreNode)other)._init; + } + // Debugger label @Override public String label() { return "st_"+mlabel(); } @Override public boolean isMem() { return true; } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/LoadX86.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/LoadX86.java index c55002c1..aca0eea1 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/LoadX86.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/LoadX86.java @@ -24,6 +24,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); |