diff options
Diffstat (limited to 'chapter14/src/main/java')
14 files changed, 526 insertions, 128 deletions
diff --git a/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index a270f026..78a0dcde 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -149,7 +149,7 @@ public abstract class GlobalCodeMotion { // Loads need their memory inputs' uses also done if( n instanceof LoadNode ld ) for( Node memuse : ld.mem()._outputs ) - if( memuse._type instanceof TypeMem && late[memuse._nid]==null ) + if( antiUse(ld,memuse) && late[memuse._nid]==null ) continue outer; // All uses done, schedule @@ -219,6 +219,17 @@ public abstract class GlobalCodeMotion { best instanceof IfNode; } + // Only a store or memory Phi covering this alias can constrain a load. + // MemMerge packages slices without overwriting them. + private static boolean antiUse(LoadNode load, Node use) { + return switch( use ) { + case StoreNode st -> st._alias==load._alias; + case MemPhiNode phi -> phi._alias==load._alias; + case BulkMemPhiNode phi -> !phi.isSplit(load._alias); + default -> false; + }; + } + private static CFGNode find_anti_dep(CFGNode lca, LoadNode load, CFGNode early, CFGNode[] late, int[] anti) { // We could skip final-field loads here. // Walk LCA->early, flagging Load's block location choices @@ -226,6 +237,7 @@ public abstract class GlobalCodeMotion { anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep for( Node mem : load.mem()._outputs ) { + if( !antiUse(load,mem) ) continue; switch( mem ) { case StoreNode st: assert late[st._nid]!=null; @@ -238,9 +250,6 @@ public abstract class GlobalCodeMotion { if( phi.in(i)==load.mem() ) lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null,anti); break; - case LoadNode ld: break; // Loads do not cause anti-deps on other loads - case ReturnNode ret: break; // Load must already be ahead of Return - case NeverNode never: break; default: throw Utils.TODO(); } } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/Parser.java b/chapter14/src/main/java/com/seaofnodes/simple/Parser.java index 34fac183..bce192c2 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/Parser.java @@ -36,6 +36,10 @@ public class Parser { public StopNode STOP; + // Field identities are independent of the memory graph and Start's tuple. + private final HashMap<String,Integer> _aliases = new HashMap<>(); + private int _alias = 2; + // Debugger Printing. public static boolean SCHEDULED; // True if debug printer can use schedule info @@ -123,7 +127,7 @@ public class Parser { _lexer = new Lexer(source); _scope = new ScopeNode(); _continueScope = _breakScope = null; - START = new StartNode(new Type[]{ Type.CONTROL, arg }); + START = new StartNode(new Type[]{ Type.CONTROL, TypeMem.BOT, arg }); STOP = new StopNode(source); ZERO = new ConstantNode(TypeInteger.constant(0)).peephole().keep(); XCTRL= new XCtrlNode().peephole().keep(); @@ -150,7 +154,8 @@ public class Parser { // Enter a new scope for the initial control and arguments _scope.push(); _scope.define(ScopeNode.CTRL, Type.CONTROL , new CProjNode(START, 0, ScopeNode.CTRL).peephole()); - _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 1, ScopeNode.ARG0).peephole()); + _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 2, ScopeNode.ARG0).peephole()); + _scope.define("$mem", TypeMem.BOT, new ProjNode(START, 1, "$mem").peephole()); parseBlock(); if( ctrl()._type==Type.CONTROL ) STOP.addReturn(new ReturnNode(ctrl(), new ConstantNode(TypeInteger.constant(0)).peephole(), _scope).peephole()); @@ -238,8 +243,9 @@ public class Parser { require("}"); // Build and install the TypeStruct TypeStruct ts = TypeStruct.make(typeName, fields); - TYPES.put(typeName, ts); - START.addMemProj(ts, _scope); // Insert memory edges + TYPES.put(typeName, ts); // Insert the struct name in the collection of all struct names + _aliases.put(typeName,_alias); + _alias += ts._fields.length; return parseStatement(); } @@ -666,21 +672,24 @@ public class Parser { */ private Node newStruct(TypeStruct obj) { Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep(); - int alias = START._aliasStarts.get(obj._name); + int alias = _aliases.get(obj._name); for( Field field : obj._fields ) { - memAlias(alias, new StoreNode(field._fname, alias, field._type, ctrl(), memAlias(alias), n, new ConstantNode(field._type.makeInit()).peephole(),true).peephole()); + store(field._fname,alias,field._type,n,new ConstantNode(field._type.makeInit()).peephole(),true); alias++; } return n.unkeep(); } - // We set up memory aliases by inserting special vars in the scope these - // variables are prefixed by $ so they cannot be referenced in Simple code. - // Using vars has the benefit that all the existing machinery of scoping - // and phis work as expected - private Node memAlias(int alias ) { return _scope.lookup(memName(alias) ); } - private Node memAlias(int alias, Node st) { return _scope.update(memName(alias), st); } - 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.lookup("$mem"); } + private Node mem(Node n) { return _scope.update("$mem",n); } + + private void store(String name, int alias, Type glb, Node ptr, Node val, boolean init) { + Node prior = mem().keep(); + Node st = new StoreNode(name,alias,glb,ctrl(),prior,ptr,val,init).peephole(); + mem(new MemMergeNode(prior,alias,st).peephole()); + prior.unkeep(); + } /** * Parse postfix expression. For now this is just a field @@ -702,7 +711,7 @@ public class Parser { TypeStruct base = (TypeStruct)TYPES.get(ptr._obj._name); int idx = base==null ? -1 : base.find(name); if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); - int alias = START._aliasStarts.get(ptr._obj._name)+idx; + int alias = _aliases.get(ptr._obj._name)+idx; if( match("=") ) { // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment @@ -712,13 +721,13 @@ public class Parser { Type glb = base._fields[idx]._type; // Auto-truncate when storing to narrow fields val = zsMask(val,glb); - memAlias(alias, new StoreNode(name, alias,glb, ctrl(), memAlias(alias), expr, val, false).peephole()); + store(name,alias,glb,expr,val,false); return expr; // "obj.a = expr" returns the expression while updating memory } } Type declaredType = base._fields[idx]._type; - return parsePostfix(new LoadNode(name, alias, declaredType.glb(), memAlias(alias), expr).peephole()); + return parsePostfix(new LoadNode(name, alias, declaredType.glb(), mem(), expr).peephole()); } // zero/sign extend. "i" is limited to either classic unsigned (min==0) or diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java new file mode 100644 index 00000000..8d512f21 --- /dev/null +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -0,0 +1,237 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; +import java.util.BitSet; + +/** + * A Phi for bulk memory. It covers all aliases except {@link #_aliases}; + * those aliases must be represented by parallel precise MemPhis at the same + * program slice. + */ +public class BulkMemPhiNode extends PhiNode { + + private static final BitSet EMPTY = new BitSet(); + + // Excluded Aliases; empty means NO exclusions. + // Each split clones the exclusions; published sets are never mutated. + public final BitSet _aliases; + + public BulkMemPhiNode(String label, Node... inputs) { + this(label,EMPTY,inputs); + } + + private BulkMemPhiNode(String label, BitSet aliases, Node... inputs) { + super(label,TypeMem.BOT,inputs); + _aliases = aliases; + } + + public boolean isSplit(int alias) { return _aliases.get(alias); } + + @Override public String label() { return "BulkPhi"+_aliases; } + + @Override + public Type compute() { + Type t = super.compute(); + return t instanceof TypeMem mem ? mem : + t==Type.BOTTOM ? TypeMem.BOT : + TypeMem.TOP; + } + + @Override + public Node idealize() { + Node progress = super.idealize(); + if( progress != null ) return progress; + if( ((RegionNode)region()).inProgress() || region().nIns()<=1 ) + return null; // Input is in-progress + + // "Peek through" a MemMerge that covers this alias set on its default + for( int i=1; i<nIns(); i++ ) + if( in(i) instanceof MemMergeNode mmm && canPeek(mmm) ) { + setDef(i,IterPeeps.add(mmm.in(1))); + return this; + } + + // If any input or output uses or defines a specific alias we cover, + // make a private MemPhi for it, and add it to the excluded list. + for( int i=1; i<nIns(); i++ ) { + int alias = inputAlias(in(i)); + if( alias!=0 ) + return slice(alias); + } + + for( int i=0; i<_outputs.size(); i++ ) { + int alias = outputAlias(_outputs.get(i)); + if( alias!=0 ) + return slice(alias); + } + + return null; + } + + static public boolean checkMem(Node n, int alias) { + for( Node m : n._inputs ) + // Bulk memory supplies this alias + if( m instanceof BulkMemPhiNode bulk ) { + if( bulk._aliases.get(alias) ) + return false; + } else if( m instanceof MemMergeNode mmm && + mmm.in(1) instanceof BulkMemPhiNode bulk && + bulk._aliases.get(alias) && + (alias >= mmm.nIns() || mmm.in(alias)==null) ) + return false; + return true; + } + + + // True if the MemMerge has no precise slice still covered by this Phi. + private boolean canPeek(MemMergeNode mmm) { + return missingAlias(mmm,false)==0; + } + + // Return an alias required by an input but still covered by this Phi, or 0. + private int inputAlias(Node n) { + return switch(n) { + case ProjNode proj -> 0; + case ConstantNode con -> 0; + case MemMergeNode mmm -> missingAlias(mmm,false); + case MemOpNode mem -> unsplit(mem._alias); + case BulkMemPhiNode bulk -> missingAlias(bulk); + default -> throw new AssertionError("Unexpected memory input "+n); + }; + } + + // Return an alias required by a user but still covered by this Phi, or 0. + private int outputAlias(Node use) { + // This decision depends backwards on an immediate user's alias/set. + // Normal graph-neighbor enqueueing flows from defs to uses, so retain + // an explicit forward dependency to revisit this Phi when the user + // sharpens. + use.addDepForwards(this); + return switch(use) { + case ScopeNode scope -> 0; + case MemMergeNode mmm -> missingAlias(mmm,true); + case BulkMemPhiNode bulk -> missingAlias(bulk); + case MemOpNode mem -> unsplit(mem._alias); + case MemPhiNode phi -> unsplit(phi._alias); + default -> { + assert use instanceof ReturnNode + : "Unexpected bulk-memory user "+use; + yield 0; + } + }; + } + + // Alias zero/one is bulk, and an already excluded precise alias cannot + // trigger another split of this Phi. + private int unsplit(int alias) { + if( alias <= 1 ) return 0; + assert !_aliases.get(alias); + return alias; + } + + // First alias excluded by the neighboring bulk Phi but not by this one. + private int missingAlias(BulkMemPhiNode bulk) { + for( int alias = bulk._aliases.nextSetBit(0); alias >= 0; alias = bulk._aliases.nextSetBit(alias+1) ) + if( !_aliases.get(alias) ) + return alias; + return 0; + } + + // First precise MemMerge slice still covered by this Phi. When inspecting + // a user, ignore slots which point back to this Phi. + private int missingAlias(MemMergeNode mmm, boolean user) { + for( int alias=2; alias<mmm.nIns(); alias++ ) + if( mmm.in(alias)!=null && + mmm.alias(alias)!=mmm.in(1) && + !_aliases.get(alias) ) + { assert (!user || mmm.in(alias)!=this); return alias; } + return 0; + } + + // Slice out given alias + private MemMergeNode slice( int alias ) { + assert !_aliases.get(alias); + // Inputs are the same; MemPhi will sharpen his own inputs. If a + // parallel precise Phi already exists, reuse it instead of building a + // duplicate for the same Region/alias pair. + Node mem = precisePhi(alias); + + BitSet aliases = ((BitSet)_aliases.clone()); + aliases.set(alias); + BulkMemPhiNode bphi = new BulkMemPhiNode(_label,aliases); + for( int i=0; i<nIns(); i++ ) + bphi.addDef(in(i)); + // Installing bphi creates a new bulk user with a different exclusion + // set. Queue the original memory inputs before bphi itself can peep + // away and hide those neighbor relationships. + for( int i=1; i<bphi.nIns(); i++ ) + IterPeeps.add(bphi.in(i)); + // Do not peephole bphi here, as BulkMemPhi can recursively start a + // second bulk rewrite before this one has finished. Let the worklist + // discover any further splits + bphi.setType(TypeMem.BOT); + Node bulk = bphi; + IterPeeps.add(bulk); + IterPeeps.add(mem); + return aggregate(bulk,alias,mem); + } + + // Build aggregate memory over a bulk Phi, preserving every precise slice + // which the bulk has already excluded. The named alias is newly supplied + // (or replaces its old slice). + MemMergeNode aggregate(Node bulk, int alias, Node precise) { + MemMergeNode mmm = new MemMergeNode(bulk); + for( int old = _aliases.nextSetBit(0); old >= 0; old = _aliases.nextSetBit(old+1) ) + { assert old != alias; mmm.alias(old,precisePhi(old));} + mmm.alias(alias,precise); + assert checkMerge(mmm); + return mmm; + } + + // Find or make the precise Phi parallel to this bulk Phi at the same merge. + private Node precisePhi(int alias) { + MemPhiNode mphi = _findPhi(alias); + if( mphi!=null ) return mphi; + + mphi = new MemPhiNode("$"+alias,alias); + mphi.addDef(region()); + // Due to cycles, must set before calling peephole + mphi.setType(TypeMem.make(alias)); + for( int i=1; i<nIns(); i++ ) + mphi.addDef(IterPeeps.add(preciseInput(in(i),alias))); + return IterPeeps.add(mphi); + } + + MemPhiNode _findPhi(int alias) { + for( Node use : region()._outputs ) + if( use instanceof MemPhiNode mphi && mphi._alias==alias ) + return mphi; + return null; + } + + // Select an alias already split out of a predecessor's bulk memory. + private Node preciseInput(Node mem, int alias) { + if( mem instanceof MemMergeNode mmm ) + return mmm.alias(alias); + if( mem instanceof BulkMemPhiNode bulk && bulk.isSplit(alias) ) + return bulk.precisePhi(alias); + return mem; + } + + // Every alias excluded by a bulk default must be supplied explicitly. + static boolean checkMerge(MemMergeNode mmm) { + if( !(mmm.in(1) instanceof BulkMemPhiNode bulk) ) return true; + for( int alias = bulk._aliases.nextSetBit(0); alias >= 0; alias = bulk._aliases.nextSetBit(alias+1) ) + if( alias >= mmm.nIns() || mmm.in(alias)==null ) + return false; + return true; + } + + @Override public boolean eq(Node n) { + return _aliases.equals(((BulkMemPhiNode)n)._aliases) && super.eq(n); + } + + @Override int hash() { return _aliases.hashCode(); } +} diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 2db5e469..5cd39a33 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.Type; import java.util.BitSet; @@ -22,6 +23,24 @@ public class LoadNode extends MemOpNode { super(name, alias, glb, null, memSlice, memPtr); } + @Override boolean canDrop(MemOpNode other, Node dep) { + return super.canDrop(other,dep) && !clobbered(dep); + } + + // Check only immediate memory users. Stores clobber memory; Phis and + // aggregates might lead to a clobber, so stop rather than search further. + private boolean clobbered(Node dep) { + Node mem = mem(); + mem.addDepForwards(dep); + for( Node use : mem._outputs ) { + if( use==null ) continue; + use.addDepForwards(dep); + if( use instanceof StoreNode || use instanceof PhiNode || + use instanceof MemMergeNode ) return true; + } + return false; + } + @Override public String label() { return _name; } @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { return sb.append(".").append(_name); } @@ -33,10 +52,15 @@ public class LoadNode extends MemOpNode { @Override public Node idealize() { + if( mem() instanceof MemMergeNode merge ) { + setDef(1,IterPeeps.add(merge.alias(_alias))); + return this; + } + // Simple Load-after-Store on same address. if( mem() instanceof StoreNode st && - ptr() == st.ptr() ) { // Must check same object + ptr() == st.ptr() && _alias==st._alias ) { // Must check same object assert _name.equals(st._name); // Equiv class aliasing is perfect return st.val(); } @@ -48,7 +72,7 @@ public class LoadNode extends MemOpNode { // if( pred ) ptr.x = e0; val = pred ? e0 // else ptr.x = e1; : e1; // val = ptr.x; ptr.x = val; - if( mem() instanceof PhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 ) { + if( mem() instanceof MemPhiNode memphi && memphi.region()._type == Type.CONTROL && memphi.nIns()== 3 ) { // Profit on RHS/Loop backedge if( profit(memphi,2) || // Else must not be a loop to count profit on LHS. @@ -69,7 +93,7 @@ public class LoadNode extends MemOpNode { // Profitable if we find a matching Store on this Phi arm. private boolean profit(PhiNode phi, int idx) { Node px = phi.in(idx); - return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr(); + return px!=null && px.addDep(this) instanceof StoreNode st1 && ptr()==st1.ptr() && _alias==st1._alias; } Node copy(Node mem, Node ptr) { diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java new file mode 100644 index 00000000..d7fed402 --- /dev/null +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -0,0 +1,60 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; +import java.util.BitSet; + +/** All memory: a default slice and explicit overrides for individual aliases. */ +public class MemMergeNode extends Node { + public MemMergeNode(Node bulk) { super(null,bulk); _type = TypeMem.BOT; } + public MemMergeNode(Node bulk, int alias, Node precise) { + this(bulk); + alias(alias,precise); + } + + public Node alias(int alias) { + Node n = alias < nIns() ? in(alias) : null; + assert n!=null || !(in(1) instanceof BulkMemPhiNode bulk) || !bulk.isSplit(alias); + return n==null ? in(1) : n; + } + + public void alias(int alias, Node mem) { + assert alias > 1; + while( nIns()<=alias ) addDef(null); + setDef(alias,mem); + } + + @Override public String label() { return "MemMerge"; } + @Override public boolean isMem() { return true; } + @Override public Type compute() { return TypeMem.BOT; } + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { + sb.append("MEM["); + for( int i=1; i<nIns(); i++ ) + if( in(i)!=null ) { + sb.append(i==1 ? "default:" : i+":"); + in(i)._print0(sb,visited).append(" "); + } + return sb.append("]"); + } + + @Override public Node idealize() { + boolean progress=false, allDefault=true; + for( int i=2; i<nIns(); i++ ) { + if( in(i)==in(1) ) { setDef(i,null); progress=true; } + if( in(i)!=null ) allDefault=false; + } + if( allDefault ) return in(1); + + if( in(1) instanceof MemMergeNode mem ) { + for( int i=2; i<mem.nIns(); i++ ) + if( mem.in(i)!=null && (i>=nIns() || in(i)==null) ) + alias(i,mem.in(i)); + IterPeeps.add(mem.in(1)); + setDef(1,mem.in(1)); + return this; + } + assert BulkMemPhiNode.checkMerge(this); + return progress ? this : null; + } +} diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 76564db0..29d302cb 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -24,6 +24,13 @@ public abstract class MemOpNode extends Node { public Node mem() { return in(1); } public Node ptr() { return in(2); } + // Extra conditions for factoring matching memory operations through a Phi. + // The caller has already checked the opcode, input shape and control. + boolean canDrop(MemOpNode other, Node dep) { + ptr().addDep(dep); + return _alias==other._alias && _declaredType==other._declaredType && err()==null; + } + @Override boolean eq(Node n) { MemOpNode mem = (MemOpNode)n; // Invariant diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java new file mode 100644 index 00000000..c806bede --- /dev/null +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java @@ -0,0 +1,36 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; + +/** A Phi for one field alias, parallel to a bulk Phi at the same Region. */ +public class MemPhiNode extends PhiNode { + public final int _alias; + + public MemPhiNode(String label, int alias, Node... inputs) { + super(label,TypeMem.make(alias),inputs); + assert alias > 1; + _alias = alias; + } + + @Override public String label() { return "MemPhi_"+_alias; } + + @Override public Type compute() { + assert BulkMemPhiNode.checkMem(this,_alias); + Type t = super.compute(); + return t==Type.TOP || t==TypeMem.TOP ? TypeMem.TOP : TypeMem.make(_alias); + } + + @Override public Node idealize() { + for( int i=1; i<nIns(); i++ ) + if( in(i) instanceof MemMergeNode mem ) { + setDef(i,IterPeeps.add(mem.alias(_alias))); + return this; + } + return super.idealize(); + } + + @Override boolean eq(Node n) { return _alias==((MemPhiNode)n)._alias && super.eq(n); } + @Override int hash() { return _alias; } +} diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java index af59cb0d..469badc4 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java @@ -16,14 +16,14 @@ import java.util.function.Function; * The Node class provides common functionality used by all subtypes. * Subtypes of Node specialize by overriding methods. */ -public abstract class Node implements OutNode { +public abstract class Node implements OutNode, Cloneable { /** * Each node has a unique dense Node ID within a compilation context * The ID is useful for debugging, for using as an offset in a bitvector, * as well as for computing equality of nodes (to be implemented later). */ - public final int _nid; + public int _nid; /** * Inputs to the node. These are use-def references to Nodes. @@ -32,7 +32,7 @@ public abstract class Node implements OutNode { * Ordering is required because e.g. "a/b" is different from "b/a". * The first input (offset 0) is often a {@link #isCFG} node. */ - public final ArrayList<Node> _inputs; + public ArrayList<Node> _inputs; /** * Outputs reference Nodes that are not null and have this Node as an @@ -43,7 +43,7 @@ public abstract class Node implements OutNode { * walked in either direction. These outputs are typically used for * efficient optimizations but otherwise have no semantics meaning. */ - public final ArrayList<Node> _outputs; + public ArrayList<Node> _outputs; /** @@ -208,6 +208,7 @@ public abstract class Node implements OutNode { // Error is 'use' does not exist; ok for 'use' to be null. protected boolean delUse( Node use ) { Utils.del(_outputs, Utils.find(_outputs, use)); + moveDepsToWorklist(); // User-count and anti-dependence queries can now change. return _outputs.isEmpty(); } @@ -449,6 +450,14 @@ public abstract class Node implements OutNode { * being added must benefit from this node being peepholed. */ Node addDep( Node dep ) { + return addDep(dep,false); + } + + // A bulk Phi inspects its users' partitions. Def-to-use propagation does + // not revisit that producer when an immediate user's partition changes. + Node addDepForwards(Node dep) { return addDep(dep,true); } + + private Node addDep(Node dep, boolean forwards) { // Running peepholes during the big assert cannot have side effects // like adding dependencies. if( IterPeeps.midAssert() ) return this; @@ -456,8 +465,8 @@ public abstract class Node implements OutNode { if( obs != null ) obs.dep(this, dep); if( _deps==null ) _deps = new ArrayList<>(); if( Utils.find(_deps ,dep) != -1 ) return this; // Already on list - if( Utils.find(_inputs,dep) != -1 ) return this; // No need for deps on immediate neighbors - if( Utils.find(_outputs,dep)!= -1 ) return this; + if( !forwards && Utils.find(_inputs,dep) != -1 ) return this; + if( !forwards && Utils.find(_outputs,dep)!= -1 ) return this; _deps.add(dep); return this; } @@ -589,6 +598,20 @@ public abstract class Node implements OutNode { // Does not need to be implemented in isCFG() nodes. Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); } + // Exact-class copy preserving operation attributes, with fresh identity + // and no edges, dependencies, or GVN membership. + public final Node copyEmpty() { + Node n; + try { n = (Node)clone(); } + catch( CloneNotSupportedException e ) { throw new AssertionError(e); } + n._nid = UNIQUE_ID++; + n._inputs = new ArrayList<>(); + n._outputs = new ArrayList<>(); + n._deps = null; + n._hash = 0; + return n; + } + // Report any post-optimize errors String err() { return null; } diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 1d4b3fba..0f8b06f5 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -16,6 +16,10 @@ public class PhiNode extends Node { public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label; assert declaredType!=null; _declaredType = declaredType; } + public static PhiNode make(String label, Type type, Node... inputs) { + return type instanceof TypeMem ? new BulkMemPhiNode(label,inputs) : new PhiNode(label,type,inputs); + } + @Override public String label() { return "Phi_"+_label; } @Override @@ -65,30 +69,9 @@ public class PhiNode extends Node { if (live != null) return live; - // Pull "down" a common data op. One less op in the world. One more - // Phi, but Phis do not make code. - // Phi(op(A,B),op(Q,R),op(X,Y)) becomes - // op(Phi(A,Q,X), Phi(B,R,Y)). - Node op = in(1); - if( op.nIns()==3 && op.in(0)==null && !op.isCFG() && same_op() ) { - Node[] lhss = new Node[nIns()]; - Node[] rhss = new Node[nIns()]; - lhss[0] = rhss[0] = in(0); // Set Region - for( int i=1; i<nIns(); i++ ) { - lhss[i] = in(i).in(1); - rhss[i] = in(i).in(2); - } - Node phi_lhs = new PhiNode(_label, in(1).in(1)._type.glb(),lhss).peephole(); - Node phi_rhs = new PhiNode(_label, in(1).in(2)._type.glb(),rhss).peephole(); - Node phi_op = op.copy(phi_lhs,phi_rhs); - phi_op.setType(phi_op.compute()); - // If losing precision, don't do it - if( !phi_op._type.isa(_type) ) { - phi_op.kill(); - return null; - } - return phi_op; - } + // 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 ) { @@ -118,16 +101,72 @@ public class PhiNode extends Node { } private boolean same_op() { - for( int i=2; i<nIns(); i++ ) { - if( in(1).getClass() != in(i).getClass() ) return false; - if( in(1).in(1)._type.glb() != in(i).in(1)._type.glb() ) return false; - if( in(1).in(2)._type.glb() != in(i).in(2)._type.glb() ) return false; + Node op = in(1); + if( op.isCFG() || op instanceof ConstantNode || op instanceof PhiNode || + op instanceof ProjNode || op instanceof NewNode || op instanceof ScopeNode || op instanceof MemMergeNode ) return false; + // A bulk Phi must split its aliases before factoring precise Stores. + if( this instanceof BulkMemPhiNode ) return false; + // Bulk splitting currently identifies parallel slices by Region/alias. + // Factoring can introduce another slice at a different memory point; + // wait until that Region's bulk partitioning has finished. + if( op instanceof MemOpNode ) + for( Node use : region()._outputs ) + if( use instanceof BulkMemPhiNode ) { + use.addDepForwards(this); + return false; + } + Node busy = null; + for( int i=1; i<nIns(); i++ ) { + Node n = in(i); + if( region().in(i).addDep(this)._type==Type.XCONTROL || + op.getClass()!=n.getClass() || n.nIns()!=op.nIns() || n.in(0)!=null || !op.eq(n) ) return false; + if( n instanceof MemOpNode mem && !mem.canDrop((MemOpNode)op,this) ) return false; + // Moving a Store must remove the old effect, not duplicate it. + // Allow one shared arm: the other arms disappear into the single + // factored operation, usually reducing the total operation count. + n.addDepForwards(this); + if( n.nOuts()>1 ) { + for( Node use : n._outputs ) + if( use!=null && use!=this ) use.addDepForwards(this); + if( n instanceof StoreNode || busy!=null ) return false; + busy=n; + } + for( int j=1; j<n.nIns(); j++ ) + if( n.in(j) instanceof ScopeNode || ((n.in(j)==null) != (op.in(j)==null)) ) return false; } - // Load merging needs an anti-dep check. - if( in(1) instanceof MemOpNode ) return false; return true; } + private Node drop_same_op() { + Node op = in(1), cp = op.copyEmpty(); + cp._type = null; + cp.addDef(null); + for( int j=1; j<op.nIns(); j++ ) { + Node x = op.in(j); + boolean different = false; + for( int i=2; i<nIns(); i++ ) + if( in(i).in(j)!=x ) different=true; + if( different ) { + Node[] ins = new Node[nIns()]; + ins[0] = region(); + Type t = Type.TOP; + for( int i=1; i<nIns(); i++ ) { + ins[i] = in(i).in(j); + t = t.meet(ins[i]._type); + } + PhiNode phi = j==1 && op instanceof MemOpNode mem + ? new MemPhiNode(_label,mem._alias,ins) + : PhiNode.make(_label,t.glb(),ins); + x = phi.peephole(); + } + cp.addDef(x); + } + // Factoring must not widen the result (e.g. correlated And operands). + if( cp.compute().isa(compute()) ) return cp; + cp.kill(); + return null; + } + /** * If only single unique input, return it */ diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/RegionNode.java index fb934511..d7e934d7 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -68,7 +68,7 @@ public class RegionNode extends CFGNode { if( !hasPhi() && // No Phi users, just a control user in(1) instanceof ProjNode p1 && in(2) instanceof ProjNode p2 && - p1.in(0)==p2.in(0) && + p1.addDepForwards(this).in(0)==p2.addDepForwards(this).in(0) && p1.in(0) instanceof IfNode iff ) return iff.ctrl(); diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 444b76a8..725c704f 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -4,32 +4,17 @@ import com.seaofnodes.simple.type.*; import java.util.BitSet; -/** - * The Return node has two inputs. The first input is a control node and the - * second is the data node that supplies the return value. - * <p> - * In this presentation, Return functions as a Stop node, since multiple <code>return</code> statements are not possible. - * The Stop node will be introduced in Chapter 6 when we implement <code>if</code> statements. - * <p> - * The Return's output is the value from the data node. - */ +/** Keeps all preceding memory effects and the return value alive: {ctrl, $mem, value}. */ public class ReturnNode extends CFGNode { public ReturnNode(Node ctrl, Node data, ScopeNode scope) { - super(ctrl, data); - // We lookup memory slices by the naming convention that they start with $ - // We could also use implicit knowledge that all memory projects are at offset >= 2 - if( scope != null ) { - String[] names = scope.reverseNames(); - for (String name: names) { - if (!name.equals("$ctrl") && name.startsWith("$")) - addDef(scope.lookup(name)); - } - } + // A synthetic never-taken loop exit has no source scope. + super(ctrl, scope == null ? null : scope.lookup("$mem"), data); } public Node ctrl() { return in(0); } - public Node expr() { return in(1); } + public Node mem () { return in(1); } + public Node expr() { return in(2); } @Override public String label() { return "Return"; } @@ -43,7 +28,8 @@ public class ReturnNode extends CFGNode { @Override public Type compute() { - return TypeTuple.make(ctrl()._type,expr()._type); + // Return exposes the complete memory state. + return TypeTuple.make(ctrl()._type,TypeMem.BOT,expr()._type); } @Override diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 455f4b3a..b931e862 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -129,7 +129,7 @@ public class ScopeNode extends Node { // Set real Phi in the loop head // The phi takes its one input (no backedge yet) from a recursive // lookup, which might have insert a Phi in every loop nest. - : loop.setDef(idx,new PhiNode(name, lookupDeclaredType(name),loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); + : loop.setDef(idx,PhiNode.make(name, lookupDeclaredType(name),loop.ctrl(),loop.update(name,null,nestingLevel),null).peephole()); setDef(idx,old); } return n==null ? old : setDef(idx,n); // Not lazy, so this is the answer @@ -207,7 +207,7 @@ public class ScopeNode extends Node { if( in(i) != that.in(i) ) // No need for redundant Phis // If we are in lazy phi mode we need to a lookup // by name as it will trigger a phi creation - setDef(i, new PhiNode(ns[i], this.lookupDeclaredType(ns[i]), r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); + setDef(i, PhiNode.make(ns[i], this.lookupDeclaredType(ns[i]), r, this.lookup(ns[i]), that.lookup(ns[i])).peephole()); that.kill(); // Kill merged scope IterPeeps.add(r); return r.unkeep().peephole(); diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/StartNode.java index 5f205ffd..2cedf0f6 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -1,59 +1,17 @@ package com.seaofnodes.simple.node; -import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.type.*; -import java.util.Arrays; import java.util.BitSet; -import java.util.HashMap; import java.util.HashSet; -/** - * 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 CFGNode implements MultiNode { - // This field is NOT final, because the tuple expands as we add memory aliases - TypeTuple _args; - - // The alias number of the first field in the struct. - // - public final HashMap<String,Integer> _aliasStarts; - + private final TypeTuple _args; public StartNode(Type[] args) { super(); - _args = TypeTuple.make(args); - _type = _args; - _aliasStarts = new HashMap<>(); - } - - /** - * Creates a projection for each of the struct's fields, using the field alias - * as the key. - */ - public void addMemProj( TypeStruct ts, ScopeNode scope) { - int len = _args._types.length; - _aliasStarts.put(ts._name,len); - - // resize the tuple's type array to include all fields of the struct - int max = len + ts._fields.length; - Type[] args = Arrays.copyOf(_args._types, max); - - // The new members of the tuple get a mem type with an alias - for( int alias = len; alias < max; alias++ ) - args[alias] = TypeMem.make(alias); _type = _args = TypeTuple.make(args); - // For each of the fields we now add a mem projection. Note that the - // alias matches the slot of the field in the tuple - for( int alias = len; alias < max; alias++ ) { - String name = Parser.memName(alias); - Node n = new ProjNode(this, alias, name).peephole(); - scope.define(name, args[alias], n); - } } @Override diff --git a/chapter14/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/chapter14/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 142aebc3..031240ce 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -1,6 +1,7 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.*; import java.util.BitSet; @@ -24,6 +25,10 @@ public class StoreNode extends MemOpNode { _init = init; } + @Override boolean canDrop(MemOpNode other, Node dep) { + return super.canDrop(other,dep) && _init==((StoreNode)other)._init; + } + @Override public String label() { return "." +_name+"="; } @Override public boolean isMem() { return true; } @@ -39,11 +44,16 @@ public class StoreNode extends MemOpNode { @Override public Node idealize() { + if( mem() instanceof MemMergeNode merge ) { + setDef(1,IterPeeps.add(merge.alias(_alias))); + return this; + } + // Simple store-after-store on same address. Should pick up the // required init-store being stomped by a first user store. if( mem() instanceof StoreNode st && - ptr()==st.ptr() && // Must check same object + ptr()==st.ptr() && _alias==st._alias && // Must check same object 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. |