From 75b57151ed57efc3e74cf2bf929c1800dd97680e Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 29 Sep 2026 16:33:36 -0700 Subject: Forward port mem to ch16 --- README.md | 6 +- .../main/java/com/seaofnodes/simple/node/Node.java | 1 + .../main/java/com/seaofnodes/simple/node/Node.java | 1 + .../main/java/com/seaofnodes/simple/node/Node.java | 1 + .../main/java/com/seaofnodes/simple/node/Node.java | 1 + .../main/java/com/seaofnodes/simple/node/Node.java | 1 + .../main/java/com/seaofnodes/simple/node/Node.java | 1 + .../main/java/com/seaofnodes/simple/node/Node.java | 1 + chapter16/README.md | 30 ++- .../com/seaofnodes/simple/GlobalCodeMotion.java | 30 +-- .../main/java/com/seaofnodes/simple/Parser.java | 86 ++++---- .../com/seaofnodes/simple/node/BulkMemPhiNode.java | 237 +++++++++++++++++++++ .../java/com/seaofnodes/simple/node/LoadNode.java | 89 ++++++-- .../com/seaofnodes/simple/node/MemMergeNode.java | 89 ++++++++ .../java/com/seaofnodes/simple/node/MemOpNode.java | 7 + .../com/seaofnodes/simple/node/MemPhiNode.java | 42 ++++ .../java/com/seaofnodes/simple/node/NewNode.java | 48 ++--- .../main/java/com/seaofnodes/simple/node/Node.java | 36 +++- .../java/com/seaofnodes/simple/node/PhiNode.java | 91 ++++++-- .../com/seaofnodes/simple/node/RegionNode.java | 2 +- .../com/seaofnodes/simple/node/ReturnNode.java | 23 +- .../com/seaofnodes/simple/node/ScopeMinNode.java | 137 ------------ .../java/com/seaofnodes/simple/node/ScopeNode.java | 96 +++++---- .../java/com/seaofnodes/simple/node/StartNode.java | 12 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 20 +- .../simple/print/SimpleGraphAdapter.java | 2 +- .../java/com/seaofnodes/simple/Chapter04Test.java | 5 +- .../java/com/seaofnodes/simple/Chapter05Test.java | 14 +- .../java/com/seaofnodes/simple/Chapter06Test.java | 10 +- .../java/com/seaofnodes/simple/Chapter07Test.java | 26 +-- .../java/com/seaofnodes/simple/Chapter08Test.java | 16 +- .../java/com/seaofnodes/simple/Chapter09Test.java | 10 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 129 ++++++++++- .../java/com/seaofnodes/simple/Chapter10bTest.java | 64 ++++++ .../java/com/seaofnodes/simple/Chapter11Test.java | 6 +- .../java/com/seaofnodes/simple/Chapter12Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter14Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter15Test.java | 3 +- .../java/com/seaofnodes/simple/Chapter16Test.java | 25 ++- .../com/seaofnodes/simple/evaluator/Evaluator.java | 16 +- .../com/seaofnodes/simple/evaluator/Scheduler.java | 33 ++- docs/chapter-backports.md | 47 +++- skills/chapter25-codex-notes.md | 20 +- 43 files changed, 1076 insertions(+), 444 deletions(-) create mode 100644 chapter16/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java create mode 100644 chapter16/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java create mode 100644 chapter16/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java delete mode 100644 chapter16/src/main/java/com/seaofnodes/simple/node/ScopeMinNode.java create mode 100644 chapter16/src/test/java/com/seaofnodes/simple/Chapter10bTest.java diff --git a/README.md b/README.md index d12e95f6..bcc7c986 100644 --- a/README.md +++ b/README.md @@ -83,9 +83,9 @@ The top-level Makefile runs each chapter's `tests`, `tags` (also `tag`), The [chapter backport queue](docs/chapter-backports.md) records proposed small corrections and the per-chapter test/review workflow. Larger architectural moves are tracked separately there. The 10a/10b split is complete; forwarding 10b's -memory representation now runs through Chapter 15, including two-result -allocation with partial memory and typed alias contents. Chapter 15 is ready -for review; Chapters 16-24 still use their earlier parser-managed alias chains. +memory representation now runs through Chapter 16, including two-result +allocation with partial memory and explicit constructor values. Chapter 16 is +ready for review; Chapters 17-24 still use their earlier parser-managed alias chains. To build and test just the memory chapters: diff --git a/chapter10a/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter10a/src/main/java/com/seaofnodes/simple/node/Node.java index 6a4d6334..0a64a7b9 100644 --- a/chapter10a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter10a/src/main/java/com/seaofnodes/simple/node/Node.java @@ -266,6 +266,7 @@ public abstract class Node implements Cloneable { n.unlock(); int idx = Utils.find(n._inputs, this); n._inputs.set(idx,nnn); + n.moveDepsToWorklist(); // Rewiring can change a dependent query without changing type. nnn.addUse(n); } kill(); diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java index 55fa6efd..9a48c515 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -266,6 +266,7 @@ public abstract class Node implements Cloneable { n.unlock(); int idx = Utils.find(n._inputs, this); n._inputs.set(idx,nnn); + n.moveDepsToWorklist(); // Rewiring can change a dependent query without changing type. nnn.addUse(n); } kill(); diff --git a/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java index c712a017..2d09db40 100644 --- a/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter11/src/main/java/com/seaofnodes/simple/node/Node.java @@ -264,6 +264,7 @@ public abstract class Node implements OutNode, Cloneable { n.unlock(); int idx = Utils.find(n._inputs, this); n._inputs.set(idx,nnn); + n.moveDepsToWorklist(); // Rewiring can change a dependent query without changing type. nnn.addUse(n); } kill(); diff --git a/chapter12/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter12/src/main/java/com/seaofnodes/simple/node/Node.java index 228ebc6a..ff8415c5 100644 --- a/chapter12/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter12/src/main/java/com/seaofnodes/simple/node/Node.java @@ -267,6 +267,7 @@ public abstract class Node implements OutNode, Cloneable { n.unlock(); int idx = Utils.find(n._inputs, this); n._inputs.set(idx,nnn); + n.moveDepsToWorklist(); // Rewiring can change a dependent query without changing type. nnn.addUse(n); } kill(); diff --git a/chapter13/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter13/src/main/java/com/seaofnodes/simple/node/Node.java index d1fff75f..2082168a 100644 --- a/chapter13/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter13/src/main/java/com/seaofnodes/simple/node/Node.java @@ -267,6 +267,7 @@ public abstract class Node implements OutNode, Cloneable { n.unlock(); int idx = Utils.find(n._inputs, this); n._inputs.set(idx,nnn); + n.moveDepsToWorklist(); // Rewiring can change a dependent query without changing type. nnn.addUse(n); } kill(); 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 469badc4..61679fa4 100644 --- a/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter14/src/main/java/com/seaofnodes/simple/node/Node.java @@ -265,6 +265,7 @@ public abstract class Node implements OutNode, Cloneable { n.unlock(); int idx = Utils.find(n._inputs, this); n._inputs.set(idx,nnn); + n.moveDepsToWorklist(); // Rewiring can change a dependent query without changing type. nnn.addUse(n); } kill(); diff --git a/chapter15/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter15/src/main/java/com/seaofnodes/simple/node/Node.java index 7f0415ae..54fbc68f 100644 --- a/chapter15/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter15/src/main/java/com/seaofnodes/simple/node/Node.java @@ -264,6 +264,7 @@ public abstract class Node implements OutNode, Cloneable { n.unlock(); int idx = Utils.find(n._inputs, this); n._inputs.set(idx,nnn); + n.moveDepsToWorklist(); // Rewiring can change a dependent query without changing type. nnn.addUse(n); } kill(); diff --git a/chapter16/README.md b/chapter16/README.md index a19c68db..1c598568 100644 --- a/chapter16/README.md +++ b/chapter16/README.md @@ -6,6 +6,7 @@ 2. [Initialization code](#initialization-code) 3. [Final fields](#final-fields) 4. [Multiple Decls](#multiple-declarations-of-the-same-type) +5. [Memory through constructors](#memory-through-constructors) In this chapter, we add constructors and final fields. @@ -125,4 +126,31 @@ struct Point { int x,y,z; }; // Three fields declared ``` int !x=3,!y=5; // Two int variables declared, both are final and initialized -``` \ No newline at end of file +``` +## Memory through constructors + +The lazy memory partitioning from [Chapter 10b](../chapter10b/README.md) continues +through constructors. The parser tracks one `$mem` variable alongside its scalar +variables. Branches and loops merge that binding with BulkMemPhi; field access +splits out precise MemPhis when needed. The variable records for types and final +fields live in ScopeNode. There is no separate parser table of memory aliases. + +A constructor computes its field values before the allocation. Reads, writes, +and loops in its body update the same `$mem` binding as ordinary code. New then +takes `{ctrl, $mem, size, field values...}` and produces `{ptr, $mem}`. The input +memory is a partial MemMerge containing the struct's aliases; the output memory +covers those same aliases. A whole-memory MemMerge preserves unrelated slices. +Arrays use the same layout, supplying their length and default element value as +initializer inputs. + +A Load from its own New can use the matching initializer input. Alias contents +combine the initializer's type with incoming contents from older objects, so a +new object does not erase facts or effects for existing objects. Loads bypass +only allocations proven to be distinct. Scheduling follows partial aggregates +when establishing read-before-write order. + +Sharing one allocation memory result makes Store-to-New folding more +conservative: the existing sole-use check now sees users of every covered +alias. This can leave a field Load where separate memory projections previously +allowed a constant fold. Phi factoring also retains the simple one-step Load +safety check. diff --git a/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java b/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java index 31302ffd..bb109fc9 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/GlobalCodeMotion.java @@ -148,13 +148,8 @@ public abstract class GlobalCodeMotion { // Loads need their memory inputs' uses also done if( n instanceof LoadNode ld ) - for( Node memuse : ld.mem()._outputs ) - if( !(memuse instanceof PhiNode) && - late[memuse._nid]==null && - // Load-use directly defines memory - (memuse._type instanceof TypeMem || - // Load-use indirectly defines memory - (memuse._type instanceof TypeTuple tt && tt._types[ld._alias] instanceof TypeMem)) ) + for( Node memuse : ld.antiDeps() ) + if( late[memuse._nid]==null ) continue outer; // All uses done, schedule @@ -166,9 +161,7 @@ public abstract class GlobalCodeMotion { for( Node def : n._inputs ) { if( def==null ) continue; if( late[def._nid]==null ) work.push(def); - for( Node out : def._outputs ) - if( out instanceof LoadNode ld && late[ld._nid]==null ) - work.push(ld); + wakeLoads(def,late,work,new BitSet()); } if( n instanceof LoopNode loop ) for( Node phi : loop._outputs ) @@ -225,13 +218,24 @@ public abstract class GlobalCodeMotion { best instanceof IfNode; } + // An allocation may consume a load's memory through a partial aggregate. + private static void wakeLoads(Node def, CFGNode[] late, WorkList work, BitSet visit) { + if( visit.get(def._nid) ) return; + visit.set(def._nid); + for( Node out : def._outputs ) + if( out instanceof LoadNode ld && late[ld._nid]==null ) work.push(ld); + if( def instanceof MemMergeNode ) + for( int i=1; iearly, flagging Load's block location choices for( CFGNode cfg=lca; early!=null && cfg!=early.idom(); cfg = cfg.idom() ) anti[cfg._nid] = load._nid; // Walk load->mem uses, looking for Stores causing an anti-dep - for( Node mem : load.mem()._outputs ) { + for( Node mem : load.antiDeps() ) { switch( mem ) { case StoreNode st: assert late[st._nid]!=null; @@ -248,10 +252,6 @@ public abstract class GlobalCodeMotion { if( phi.in(i)==load.mem() ) lca = anti_dep(load,phi.region().cfg(i),load.mem().cfg0(),lca,null,anti); break; - case LoadNode ld: break; // Loads do not cause anti-deps on other loads - case ReturnNode ret: break; // Load must already be ahead of Return - case ScopeMinNode ret: break; // Mem uses now on ScopeMin - case NeverNode never: break; default: throw Utils.TODO(); } } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/Parser.java b/chapter16/src/main/java/com/seaofnodes/simple/Parser.java index 1f20a913..a7d31584 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/Parser.java @@ -163,11 +163,8 @@ public class Parser { _xScopes.push(_scope); // Enter a new scope for the initial control and arguments _scope.push(); - ScopeMinNode mem = new ScopeMinNode(); - mem.addDef(null); _scope.define(ScopeNode.CTRL, Type.CONTROL , false, new CProjNode(START, 0, ScopeNode.CTRL).peephole()); - mem.addDef( new ProjNode(START, 1, ScopeNode.MEM0).peephole()); - _scope.define(ScopeNode.MEM0, TypeMem.TOP , false, mem .peephole()); + _scope.define(ScopeNode.MEM0, TypeMem.BOT , false, new ProjNode(START, 1, ScopeNode.MEM0).peephole()); _scope.define(ScopeNode.ARG0, TypeInteger.BOT, false, new ProjNode(START, 2, ScopeNode.ARG0).peephole()); // Parse whole program @@ -430,7 +427,7 @@ public class Parser { // Defining a new variable vs updating an old one if( !isDecl ) { // Assigning over an existing name // Lookup - ScopeMinNode.Var def = _scope.lookup(name); + ScopeNode.Var def = _scope.lookup(name); if( def==null ) throw error("Undefined name '" + name + "'"); // TOP fields are for late-initialized fields; these have never @@ -526,7 +523,7 @@ public class Parser { Field[] fs = new Field[varlen-lexlen]; for( int i=lexlen; i ALTMP = new Ary<>(Node.class); @@ -845,16 +846,23 @@ public class Parser { int scale= ary.aryScale(); Node size = new AddNode(con(base),new ShlNode(len,con(scale)).peephole()).peephole(); ALTMP.clear(); ALTMP.add(len); ALTMP.add(con(ary._fields[1]._type.makeInit())); - return newStruct(ary,size,0,ALTMP); + Node ptr = newStruct(ary,size,0,ALTMP); + len.unkeep(); + return ptr; } - // We set up memory aliases by inserting special vars in the scope these - // variables are prefixed by $ so they cannot be referenced in Simple code. - // Using vars has the benefit that all the existing machinery of scoping - // and phis work as expected - private Node memAlias(int alias ) { return _scope.mem(alias ); } - private void memAlias(int alias, Node st) { _scope.mem(alias, st); } - public static String memName(int alias) { return ("$"+alias).intern(); } + // Memory is one hidden SSA variable, including across branches and loops. + private Node mem() { return _scope.mem(); } + private void mem(Node n) { _scope.mem(n); } + + private void store(String name, int alias, Type glb, Node ptr, Node off, Node val, boolean init, Node ctrl) { + Node prior = mem().keep(); + Node st = new StoreNode(name,alias,glb,prior,ptr,off,val,init); + st.setDef(0,ctrl); + st = st.peephole(); + mem(new MemMergeNode(prior,alias,st).peephole()); + prior.unkeep(); + } /** * Parse postfix expression. For now this is just a field @@ -894,6 +902,7 @@ public class Parser { // Get field type and layout offset from base type and field index fidx Field f = base._fields[fidx]; // Field from field index + expr.keep(); Node off = name.equals("[]") // If field is an array body // Array index math ? new AddNode(con(base.aryBase()),new ShlNode(require(parseExpression(),"]"),con(base.aryScale())).peephole()).peephole() @@ -902,19 +911,14 @@ public class Parser { // Disambiguate "obj.fld==x" boolean test from "obj.fld=x" field assignment if( matchOpx('=','=') ) { - Node val = parseExpression(); - // Auto-truncate when storing to narrow fields - val = zsMask(val,f._type); - Node st = new StoreNode(name, f._alias, f._type, memAlias(f._alias), expr, off, val, false); - // Arrays include control, as a proxy for a safety range check. - // Structs don't need this; they only need a NPE check which is - // done via the type system. - if( base.isAry() ) st.setDef(0,ctrl()); - memAlias(f._alias, st.peephole()); - return val; // "obj.a = expr" returns the expression while updating memory + off.keep(); + Node val = zsMask(parseExpression(),f._type).keep(); + // Array control stands in for the future bounds check. + store(name,f._alias,f._type,expr.unkeep(),off.unkeep(),val,false,base.isAry() ? ctrl() : null); + return val.unkeep(); } - Node load = new LoadNode(name, f._alias, f._type.glb(), memAlias(f._alias), expr, off); + Node load = new LoadNode(name, f._alias, f._type.glb(), mem(), expr.unkeep(), 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. diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java new file mode 100644 index 00000000..84f97189 --- /dev/null +++ b/chapter16/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= mmm.nIns() || mmm.in(alias)==null) ) + return false; + return true; + } + + + // True if the MemMerge has no precise slice still covered by this Phi. + private boolean canPeek(MemMergeNode mmm) { + return mmm.in(1)!=null && missingAlias(mmm)==0; + } + + // Return an alias required by an input but still covered by this Phi, or 0. + private int inputAlias(Node n) { + return switch(n) { + case ProjNode proj -> 0; + case ConstantNode con -> 0; + case MemMergeNode mmm -> missingAlias(mmm); + case MemOpNode mem -> unsplit(mem._alias); + case BulkMemPhiNode bulk -> missingAlias(bulk); + default -> throw new AssertionError("Unexpected memory input "+n); + }; + } + + // Return an alias required by a user but still covered by this Phi, or 0. + private int outputAlias(Node use) { + // This decision depends backwards on an immediate user's alias/set. + // Normal graph-neighbor enqueueing flows from defs to uses, so retain + // an explicit forward dependency to revisit this Phi when the user + // sharpens. + use.addDepForwards(this); + return switch(use) { + case ScopeNode scope -> 0; + case MemMergeNode mmm -> missingAlias(mmm); + case BulkMemPhiNode bulk -> missingAlias(bulk); + case MemOpNode mem -> unsplit(mem._alias); + case MemPhiNode phi -> unsplit(phi._alias); + default -> { + assert use instanceof ReturnNode + : "Unexpected bulk-memory user "+use; + yield 0; + } + }; + } + + // Alias zero/one is bulk, and an already excluded precise alias cannot + // trigger another split of this Phi. + private int unsplit(int alias) { + if( alias <= 1 ) return 0; + assert !_aliases.get(alias); + return alias; + } + + // First alias excluded by the neighboring bulk Phi but not by this one. + private int missingAlias(BulkMemPhiNode bulk) { + for( int alias = bulk._aliases.nextSetBit(0); alias >= 0; alias = bulk._aliases.nextSetBit(alias+1) ) + if( !_aliases.get(alias) ) + return alias; + return 0; + } + + // Every explicit slot requests that alias, including a partial allocation + // input whose slot still points to this bulk Phi. + private int missingAlias(MemMergeNode mmm) { + for( int alias=2; alias= 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= 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/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 60be3baa..46938f7b 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -1,9 +1,10 @@ package com.seaofnodes.simple.node; import com.seaofnodes.simple.Utils; -import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.type.*; import java.util.BitSet; +import java.util.ArrayList; /** * Load represents extracting a value from inside a memory object, @@ -23,6 +24,25 @@ public class LoadNode extends MemOpNode { super(name, alias, glb, mem, ptr, off); } + @Override boolean canDrop(MemOpNode other, Node dep) { + return super.canDrop(other,dep) && !clobbered(dep); + } + + // Check only immediate memory users. Stores clobber memory; Phis and + // aggregates might lead to a clobber, so stop rather than search further. + private boolean clobbered(Node dep) { + Node mem = mem(); + mem.addDepForwards(dep); + for( Node use : mem._outputs ) { + if( use==null ) continue; + use.addDepForwards(dep); + if( use instanceof StoreNode || use instanceof PhiNode || + use instanceof MemMergeNode || + use instanceof NewNode ) return true; + } + return false; + } + // Debugger label @Override public String label() { return "ld_"+mlabel(); } @Override @@ -30,28 +50,29 @@ public class LoadNode extends MemOpNode { @Override public Type compute() { - if( mem()._type instanceof TypeMem mem && - // No constant folding if ptr might null-check - _declaredType != mem._t && err()==null ) { - return _declaredType.join(mem._t); - } - return _declaredType; + Type t = MemMergeNode.contents(mem(),_alias,this); + // No constant folding if the pointer still needs a null check. + return err()==null ? _declaredType.join(t) : _declaredType; } @Override public Node idealize() { + if( mem() instanceof MemMergeNode merge ) { + setDef(1,IterPeeps.add(merge.alias(_alias))); + return this; + } Node ptr = ptr(); // Simple Load-after-Store on same address. if( mem() instanceof StoreNode st && - ptr == st.ptr() && off() == st.off() ) { // Must check same object + _alias==st._alias && ptr == st.ptr() && off() == st.off() ) { // Must check same object assert _name.equals(st._name); // Equiv class aliasing is perfect return st.val(); } // Simple Load-after-New on same address. if( mem() instanceof ProjNode p && p.in(0) instanceof NewNode nnn && - ptr == nnn.proj(1) ) // Must check same object + ptr == nnn.proj(0) ) // Must check same object return nnn.in(nnn.findAlias(_alias)); // Load from New init // Load-after-Store on same address, but bypassing provably unrelated @@ -60,12 +81,16 @@ public class LoadNode extends MemOpNode { Node mem = mem(); outer: while( true ) { + mem.addDep(this); switch( mem ) { + case MemMergeNode merge: + mem = merge.alias(_alias); + break; case StoreNode st: - if( ptr == st.ptr() && off() == st.off() ) + if( _alias==st._alias && ptr == st.ptr() && off() == st.off() ) return st.val(); // Proved equal // Can we prove unequal? Offsets do not overlap? - if( !off()._type.join(st.off()._type).isHigh() && // Offsets overlap + if( _alias==st._alias && !off()._type.join(st.off()._type).isHigh() && // Offsets overlap !neverAlias(ptr,st.ptr()) ) // And might alias break outer; // Cannot tell, stop trying // Pointers cannot overlap @@ -79,11 +104,11 @@ public class LoadNode extends MemOpNode { return nnn1.in(nnn1.findAlias(_alias)); // Load from New init if( !(ptr instanceof ProjNode pproj && pproj.in(0) instanceof NewNode nnn2) ) break outer; // Cannot tell, ptr not related to New - mem = nnn1.in(_alias);// Bypass unrelated New + mem = nnn1.mem();// Bypass unrelated New break; - } else throw Utils.TODO(); + } else break outer; default: - throw Utils.TODO(); + break outer; } } @@ -94,7 +119,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 && off() instanceof ConstantNode ) { // Profit on RHS/Loop backedge if( profit(memphi,2) || @@ -110,7 +135,9 @@ public class LoadNode extends MemOpNode { } private Node ld( int idx ) { Node mem = mem(), ptr = ptr(); - return new LoadNode(_name,_alias,_declaredType,mem.in(idx),ptr instanceof PhiNode && ptr.in(0)==mem.in(0) ? ptr.in(idx) : ptr, off()).peephole(); + LoadNode ld = new LoadNode(_name,_alias,_declaredType,mem.in(idx),ptr instanceof PhiNode && ptr.in(0)==mem.in(0) ? ptr.in(idx) : ptr,off()); + ld.setDef(0,in(0)); + return ld.peephole(); } private static boolean neverAlias( Node ptr1, Node ptr2 ) { return ptr1.in(0) != ptr2.in(0) && @@ -123,8 +150,34 @@ public class LoadNode extends MemOpNode { private boolean profit(PhiNode phi, int idx) { Node px = phi.in(idx); if( px==null ) return false; - if( px._type instanceof TypeMem mem && mem._t.isHighOrConst() ) { px.addDep(this); return true; } - if( px instanceof StoreNode st1 && ptr()==st1.ptr() && off()==st1.off() ) { px.addDep(this); return true; } + px.addDep(this); + if( px._type instanceof TypeMem mem && mem._t.isHighOrConst() ) return true; + if( px instanceof StoreNode st1 && _alias==st1._alias && ptr()==st1.ptr() && off()==st1.off() ) return true; return false; } + + // 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 antiDeps() { + ArrayList deps = new ArrayList<>(); + antiDeps(mem(),deps,new BitSet()); + return deps; + } + + private void antiDeps(Node mem, ArrayList 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 1; + while( nIns()<=alias ) addDef(null); + setDef(alias,mem); + } + + // Scalar contents of one alias. New's field inputs supply the initialized type; + // join it with the incoming contents for all previously allocated objects. + // Phis use their cached types, so this query does not recurse around loops. + static Type contents(Node mem, int alias, Node dep) { + mem.addDep(dep); + if( mem instanceof MemMergeNode merge ) + return contents(merge.alias(alias),alias,dep); + if( mem instanceof ProjNode proj && proj.in(0) instanceof NewNode nnn ) { + assert proj._idx==1 && nnn.field(alias)!=null; + nnn.addDep(dep); + Node init = nnn.in(nnn.findAlias(alias)).addDep(dep); + return contents(nnn.mem(),alias,dep).meet(init._type); + } + // There are no heap arguments in this chapter. Before the first New, + // the set of allocated objects (and hence stored values) is empty. + if( mem instanceof ProjNode proj && proj.in(0) instanceof StartNode ) return Type.TOP; + if( mem._type==Type.TOP || mem._type==TypeMem.TOP ) return Type.TOP; + if( mem._type instanceof TypeMem mt && mt._alias==alias ) return mt._t; + return Type.BOTTOM; + } + + @Override public String label() { return "MemMerge"; } + @Override public boolean isMem() { return true; } + @Override public Type compute() { return TypeMem.BOT; } + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { + sb.append("MEM["); + for( int i=1; i=nIns() || 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/chapter16/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index c7a1efec..9c222ad2 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -32,6 +32,13 @@ public abstract class MemOpNode extends Node { public Node ptr() { return in(2); } public Node off() { return in(3); } + // Extra conditions for factoring matching memory operations through a Phi. + // The caller has already checked the opcode, input shape and control. + boolean canDrop(MemOpNode other, Node dep) { + ptr().addDep(dep); + return _alias==other._alias && _declaredType==other._declaredType && err()==null; + } + @Override boolean eq(Node n) { MemOpNode mem = (MemOpNode)n; // Invariant diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java new file mode 100644 index 00000000..6aae00f9 --- /dev/null +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/MemPhiNode.java @@ -0,0 +1,42 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; + +/** A Phi for one field alias, parallel to a bulk Phi at the same Region. */ +public class MemPhiNode extends PhiNode { + public final int _alias; + + public MemPhiNode(String label, int alias, Node... inputs) { + super(label,TypeMem.make(alias,Type.BOTTOM),inputs); + assert alias > 1; + _alias = alias; + } + + @Override public String label() { return "MemPhi_"+_alias; } + + @Override public Type compute() { + assert BulkMemPhiNode.checkMem(this,_alias); + if( !(region() instanceof RegionNode r) ) + return region()._type==Type.XCONTROL ? TypeMem.TOP : _type; + if( r.inProgress() ) return _declaredType; + Type t = Type.TOP; + for( int i=1; i _inputs; + public Ary _inputs; /** * Outputs reference Nodes that are not null and have this Node as an @@ -43,7 +43,7 @@ public abstract class Node implements OutNode { * walked in either direction. These outputs are typically used for * efficient optimizations but otherwise have no semantics meaning. */ - public final Ary _outputs; + public Ary _outputs; /** @@ -214,6 +214,7 @@ public abstract class Node implements OutNode { // Error is 'use' does not exist; ok for 'use' to be null. protected boolean delUse( Node use ) { _outputs.del(_outputs.find(use)); + moveDepsToWorklist(); // User-count and anti-dependence queries can now change. return _outputs.isEmpty(); } @@ -270,6 +271,7 @@ public abstract class Node implements OutNode { n.unlock(); int idx = n._inputs.find(this); n._inputs.set(idx,nnn); + n.moveDepsToWorklist(); // Rewiring can change a dependent query without changing type. nnn.addUse(n); } kill(); @@ -455,6 +457,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; @@ -462,8 +472,8 @@ public abstract class Node implements OutNode { if( obs != null ) obs.dep(this, dep); if( _deps==null ) _deps = new Ary<>(Node.class); if( _deps .find(dep) != -1 ) return this; // Already on list - if( _inputs .find(dep) != -1 ) return this; // No need for deps on immediate neighbors - if( _outputs.find(dep) != -1 ) return this; + if( !forwards && _inputs .find(dep) != -1 ) return this; // No need for deps on immediate neighbors + if( !forwards && _outputs.find(dep) != -1 ) return this; _deps.add(dep); return this; } @@ -592,6 +602,20 @@ public abstract class Node implements OutNode { // Does not need to be implemented in isCFG() nodes. Node copy(Node lhs, Node rhs) { throw Utils.TODO("Binary ops need to implement copy"); } + // Exact-class copy preserving operation attributes, with fresh identity + // and no edges, dependencies, or GVN membership. + public final Node copyEmpty() { + Node n; + try { n = (Node)clone(); } + catch( CloneNotSupportedException e ) { throw new AssertionError(e); } + n._nid = UNIQUE_ID++; + n._inputs = new Ary<>(Node.class); + n._outputs = new Ary<>(Node.class); + n._deps = null; + n._hash = 0; + return n; + } + // Report any post-optimize errors String err() { return null; } diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/PhiNode.java index f533a7a4..6a9a8aae 100644 --- a/chapter16/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter16/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -16,6 +16,10 @@ public class PhiNode extends Node { public PhiNode(String label, Type declaredType, Node... inputs) { super(inputs); _label = label; assert declaredType!=null; _declaredType = declaredType; } + public static PhiNode make(String label, Type type, Node... inputs) { + return type instanceof TypeMem ? new BulkMemPhiNode(label,inputs) : new PhiNode(label,type,inputs); + } + @Override public String label() { return "Phi_"+MemOpNode.mlabel(_label); } @Override @@ -65,24 +69,9 @@ public class PhiNode extends Node { if (live != null) return live; - // Pull "down" a common data op. One less op in the world. One more - // Phi, but Phis do not make code. - // Phi(op(A,B),op(Q,R),op(X,Y)) becomes - // op(Phi(A,Q,X), Phi(B,R,Y)). - Node op = in(1); - if( op.nIns()==3 && op.in(0)==null && same_op() ) { - assert !(op instanceof CFGNode); - Node[] lhss = new Node[nIns()]; - Node[] rhss = new Node[nIns()]; - lhss[0] = rhss[0] = in(0); // Set Region - for( int i=1; i op(Phi(a,c),Phi(b,d),...). + Node down; + if( same_op() && (down=drop_same_op())!=null ) return down; // If merging Phi(N, cast(N)) - we are losing the cast JOIN effects, so just remove. if( nIns()==3 ) { @@ -112,12 +101,72 @@ public class PhiNode extends Node { } private boolean same_op() { - for( int i=2; i1 ) { + 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 - * In this presentation, Return functions as a Stop node, since multiple return statements are not possible. - * The Stop node will be introduced in Chapter 6 when we implement if statements. - *

- * The Return's output is the value from the data node. - */ +/** Keeps all preceding memory effects and the return value alive: {ctrl, $mem, value}. */ public class ReturnNode extends CFGNode { public ReturnNode(Node ctrl, Node data, ScopeNode scope) { - // Add memory slices to Return, so all memory updates are live-on-exit. - super(ctrl, data); - if( scope!=null ) - for( int i=2; i= nIns() ) addDef(null); - return setDef(alias,st); - } - - - // Read or update from memory. - // A shared implementation allows us to create lazy phis both during - // lookups and updates; the lazy phi creation is part of chapter 8. - Node _mem( int alias, Node st ) { - // Memory projections are made lazily; if one does not exist - // then it must be START.proj(1) - Node old = alias(alias); - if( old instanceof ScopeNode loop ) { - ScopeMinNode loopmem = loop.mem(); - Node memdef = loopmem.alias(alias); - // Lazy phi! - old = memdef instanceof PhiNode phi && loop.ctrl()==phi.region() - // Loop already has a real Phi, use it - ? memdef - // Set real Phi in the loop head - // The phi takes its one input (no backedge yet) from a recursive - // lookup, which might have insert a Phi in every loop nest. - : loopmem.alias(alias, new PhiNode(Parser.memName(alias), TypeMem.BOT,loop.ctrl(),loopmem._mem(alias,null),null).peephole() ); - alias(alias,old); - } - // Memory projections are made lazily; expand as needed - return st==null ? old : alias(alias,st); // Not lazy, so this is the answer - } - - - void _merge(ScopeMinNode that, RegionNode r) { - int len = Math.max(nIns(),that.nIns()); - for( int i = 2; i < len; i++) - if( alias(i) != that.alias(i) ) { // No need for redundant Phis - // If we are in lazy phi mode we need to a lookup - // by name as it will trigger a phi creation - //Var v = _vars.at(i); - Node lhs = this._mem(i,null); - Node rhs = that._mem(i,null); - alias(i, new PhiNode(Parser.memName(i), TypeMem.BOT, r, lhs, rhs).peephole()); - } - } - - // Fill in the backedge of any inserted Phis - void _endLoopMem( ScopeNode scope, ScopeMinNode back, ScopeMinNode exit ) { - for( int i=2; i _vars; - // Since of each nested lexical scope + // Size of each nested lexical scope public final Ary _lexSize; // A new ScopeNode - public ScopeNode() { _vars = new Ary<>(Var.class); _lexSize = new Ary<>(Integer.class); } + public ScopeNode() { _type = Type.BOTTOM; _vars = new Ary<>(Var.class); _lexSize = new Ary<>(Integer.class); } @Override public String label() { return "Scope"; } @@ -63,7 +79,8 @@ public class ScopeNode extends ScopeMinNode { public Node ctrl() { return in(0); } - public ScopeMinNode mem() { return (ScopeMinNode)in(1); } + public Node mem() { return in(lookup(MEM0)); } + public void mem(Node n) { update(MEM0,n); } /** * The ctrl of a ScopeNode is always bound to the currently active @@ -110,12 +127,6 @@ public class ScopeNode extends ScopeMinNode { return true; } - // Read from memory - public Node mem( int alias ) { return mem()._mem(alias,null); } - // Write to memory - public void mem( int alias, Node st ) { mem()._mem(alias,st); } - - /** * Lookup a name in all scopes starting from most deeply nested. * @@ -151,7 +162,7 @@ public class ScopeNode extends ScopeMinNode { // Set real Phi in the loop head // The phi takes its one input (no backedge yet) from a recursive // lookup, which might have insert a Phi in every loop nest. - : loop.setDef(v._idx,new PhiNode(v._name, v._type instanceof TypeMemPtr ? v._type : v._type.glb(), loop.ctrl(), loop.in(loop._update(v,null)._idx),null).peephole()); + : loop.setDef(v._idx,PhiNode.make(v._name, v._type instanceof TypeMemPtr ? v._type : v._type.glb(), loop.ctrl(), loop.in(loop._update(v,null)._idx),null).peephole()); setDef(v._idx,old); } if( st!=null ) setDef(v._idx,st); // Set new value @@ -182,20 +193,8 @@ public class ScopeNode extends ScopeMinNode { dup._lexSize.addAll(_lexSize); dup.addDef(ctrl()); // Control input is just copied - // Memory input is a shallow copy - ScopeMinNode memdup = new ScopeMinNode(), mem = mem(); - memdup.addDef(null); - memdup.addDef(loop ? this : mem.in(1)); - for( int i=2; i { return n instanceof CFGNode ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA; if( n instanceof RegionNode && i == 0 ) return Role.ASSOC; if( i == 0 || n instanceof RegionNode || n instanceof StopNode ) return Role.CTRL; - if( i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode) ) return Role.MEM; + if( i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode || n instanceof NewNode) ) return Role.MEM; Node def = n.in(i); if( def != null && isMem(def) ) return Role.MEM; return Role.DATA; diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter04Test.java index a3109ff7..14d31245 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -84,7 +84,10 @@ public class Chapter04Test { StopNode stop = parser.parse(); ReturnNode ret = stop.ret(); assertTrue(ret.in(0) instanceof CProjNode); - assertTrue(ret.in(1) instanceof ProjNode); + assertTrue(ret.in(1) instanceof ProjNode); + assertEquals(1, ((ProjNode)ret.in(1))._idx); + assertTrue(ret.in(2) instanceof ProjNode); + assertEquals(2, ((ProjNode)ret.in(2))._idx); } @Test diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter05Test.java index b5920125..ca7bb482 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -22,7 +22,7 @@ else { return a;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region23,(arg+2),(arg-3));", ret.toString()); + assertEquals("return Phi(Region21,(arg+2),(arg-3));", ret.toString()); } @Test @@ -37,7 +37,7 @@ if (arg == 1) { } return c;""", TypeInteger.BOT); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region22,4,3);", ret.toString()); + assertEquals("return Phi(Region20,4,3);", ret.toString()); } @Test @@ -65,7 +65,7 @@ else b=a+1; return a+b;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return ((arg*2)+Phi(Region26,2,3));", ret.toString()); + assertEquals("return ((arg*2)+Phi(Region24,2,3));", ret.toString()); } @Test @@ -80,7 +80,7 @@ else a=b+1; return a+b;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return ((Phi(Region37,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); + assertEquals("return ((Phi(Region35,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); } @Test @@ -100,7 +100,7 @@ else return a; """, TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region43,Phi(Region28,2,3),Phi(Region41,4,5));", stop.toString()); + assertEquals("return Phi(Region39,Phi(Region25,2,3),Phi(Region37,4,5));", stop.toString()); } @Test @@ -116,7 +116,7 @@ if( arg==0 ) return arg+a+b; """, TypeInteger.BOT); StopNode stop = parser.parse(); - assertEquals("return ((arg+Phi(Region20,1,0))+Phi(Region37,2,0));", stop.toString()); + assertEquals("return ((arg+Phi(Region18,1,0))+Phi(Region34,2,0));", stop.toString()); } @Test @@ -130,7 +130,7 @@ if( arg==1 ) } return a;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return (arg==Phi(Region22,3,2));", ret.toString()); + assertEquals("return (arg==Phi(Region20,3,2));", ret.toString()); } @Test diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter06Test.java index ff1f3251..d2c46df5 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -65,7 +65,7 @@ else b=5; return b;""", TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region43,42,5);", stop.toString()); + assertEquals("return Phi(Region40,42,5);", stop.toString()); } @Test @@ -84,7 +84,7 @@ else b=5; return b;""", TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region38,2,5);", stop.toString()); + assertEquals("return Phi(Region33,2,5);", stop.toString()); } @Test @@ -144,7 +144,7 @@ else return a; """, TypeInteger.BOT); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region48,3,Phi(Region46,4,5));", stop.toString()); + assertEquals("return Phi(Region44,3,Phi(Region42,4,5));", stop.toString()); } @Test @@ -200,7 +200,7 @@ if( arg ) { return a+b; """); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region35,4,1);", ret.toString()); + assertEquals("return Phi(Region29,4,1);", ret.toString()); } @@ -251,7 +251,7 @@ if( arg ) { return a+b+c; """); StopNode ret = parser.parse().iterate(); - assertEquals("return (Phi(Region48,Phi(Region29,2,3),0)+Phi(Region,3,1));", ret.toString()); + assertEquals("return (Phi(Region41,Phi(Region26,2,3),0)+Phi(Region,3,1));", ret.toString()); } diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter07Test.java index 390e1da5..443b0d17 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -17,7 +17,7 @@ public class Chapter07Test { return arg; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop10,arg,(Phi_arg+1));", stop.toString()); + assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -34,7 +34,7 @@ if(arg){}else{ return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region31,1,Phi(Loop18,1,(Phi_a+1)));", stop.toString()); + assertEquals("return Phi(Region27,1,Phi(Loop16,1,(Phi_a+1)));", stop.toString()); } @Test @@ -54,7 +54,7 @@ while(i < arg) { return sum; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,0,Phi(Loop26,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); + assertEquals("return Phi(Loop11,0,Phi(Loop23,Phi_sum,(Phi_sum+Phi(Loop,0,(Phi_j+1)))));", stop.toString()); } @Test @@ -70,7 +70,7 @@ while(a < 10) { return b; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop12,2,Phi(Region34,Phi_b,4));", stop.toString()); + assertEquals("return Phi(Loop11,2,Phi(Region30,Phi_b,4));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -89,7 +89,7 @@ while(a < 10) { return b; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,2,(Phi(Region34,Phi_b,4)+1));", stop.toString()); + assertEquals("return Phi(Loop11,2,(Phi(Region30,Phi_b,4)+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -106,7 +106,7 @@ while(a < 10) { return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString()); + assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -122,7 +122,7 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString()); + assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -135,7 +135,7 @@ while(arg) a = 2; return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop11,1,2);", stop.toString()); + assertEquals("return Phi(Loop10,1,2);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -148,7 +148,7 @@ while(arg) a = 2; return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,1,2);", stop.toString()); + assertEquals("return Phi(Loop10,1,2);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -164,7 +164,7 @@ while(a < 10) { return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString()); + assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -180,7 +180,7 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString()); + assertEquals("return Phi(Loop10,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -197,7 +197,7 @@ while(a < 10) { return a; """); StopNode stop = parser.parse(); - assertEquals("return Phi(Loop12,1,(Phi_a+3));", stop.toString()); + assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -214,7 +214,7 @@ while(a < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,1,(Phi_a+3));", stop.toString()); + assertEquals("return Phi(Loop11,1,(Phi_a+3));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter08Test.java index c199b78c..89ce8313 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -23,7 +23,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region45,Phi(Region32,Phi(Loop10,arg,(Phi_arg+1)),Add),Add);", stop.toString()); + assertEquals("return Phi(Region38,Phi(Region27,Phi(Loop9,arg,(Phi_arg+1)),Add),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); Assert.assertEquals(5L, Evaluator.evaluate(stop, 1)); Assert.assertEquals(10L, Evaluator.evaluate(stop, 6)); @@ -46,7 +46,7 @@ while(arg < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,1,Phi(Region52,Phi_a,(Phi_a+1)));", stop.toString()); + assertEquals("return Phi(Loop10,1,Phi(Region44,Phi_a,(Phi_a+1)));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -65,7 +65,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region43,Phi(Loop10,arg,(Phi_arg+1)),Add);", stop.toString()); + assertEquals("return Phi(Region36,Phi(Loop9,arg,(Phi_arg+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -81,7 +81,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region32,Phi(Loop10,arg,(Phi_arg+1)),Add);", stop.toString()); + assertEquals("return Phi(Region27,Phi(Loop9,arg,(Phi_arg+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -100,7 +100,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,arg,(Phi_arg+1));", stop.toString()); + assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -117,7 +117,7 @@ while(arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,arg,(Phi_arg+1));", stop.toString()); + assertEquals("return Phi(Loop9,arg,(Phi_arg+1));", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode); } @@ -185,7 +185,7 @@ while(arg < 10) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region35,Phi(Loop11,1,(Phi_a+1)),Add);", stop.toString()); + assertEquals("return Phi(Region30,Phi(Loop10,1,(Phi_a+1)),Add);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } @@ -201,7 +201,7 @@ while(1) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return (Phi(Loop11,1,Add)+1);", stop.toString()); + assertEquals("return (Phi(Loop10,1,Add)+1);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof CProjNode prj && prj._idx==1 ); } diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter09Test.java index b1d9d6e5..49ee75a2 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -69,7 +69,7 @@ while (arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,arg,(Phi_arg+2));", stop.toString()); + assertEquals("return Phi(Loop10,arg,(Phi_arg+2));", stop.toString()); Assert.assertEquals(11L, Evaluator.evaluate(stop, 1)); } @@ -86,7 +86,7 @@ while (arg < 10) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop12,arg,(Phi_arg+4));", stop.toString()); + assertEquals("return Phi(Loop11,arg,(Phi_arg+4));", stop.toString()); Assert.assertEquals(13L, Evaluator.evaluate(stop, 1)); } @@ -115,7 +115,7 @@ while (arg) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop18,arg,(Phi_arg+1));", stop.toString()); + assertEquals("return Phi(Loop17,arg,(Phi_arg+1));", stop.toString()); } @Test @@ -185,7 +185,7 @@ while(arg) { return a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop13,0,(-(Phi_a+3)));", stop.toString()); + assertEquals("return Phi(Loop12,0,(-(Phi_a+3)));", stop.toString()); } @Test @@ -283,7 +283,7 @@ return v1+v0; public void testFuzz8() { Parser parser = new Parser("while(arg) arg = arg - 1; return arg;"); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop10,arg,(Phi_arg-1));", stop.toString()); + assertEquals("return Phi(Loop9,arg,(Phi_arg-1));", stop.toString()); } @Test diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 408a4814..75119a75 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -1,7 +1,8 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.evaluator.Evaluator; -import com.seaofnodes.simple.node.StopNode; +import com.seaofnodes.simple.node.*; +import java.util.BitSet; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; @@ -160,7 +161,7 @@ while (arg) { return bar.a; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop16,0,(Phi_a+2));", stop.toString()); + assertEquals("return Phi(Loop17,0,(Phi_a+2));", stop.toString()); } @Test @@ -282,7 +283,7 @@ while( i.x < i.len ) { return sum; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop21,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); + assertEquals("return Phi(Loop22,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString()); } @@ -301,7 +302,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop16,s0,Phi(Region43,s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop17,s0,Phi(Region44,s0,Phi_ret));", stop.toString()); } @Test @@ -319,7 +320,7 @@ while(arg) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop20,s0,Phi(Region44,s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop23,s0,Phi(Region45,s0,Phi_ret));", stop.toString()); } @@ -336,7 +337,7 @@ while(arg < 10) { return ret; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop16,s0,Phi(Region41,s0,Phi_ret));", stop.toString()); + assertEquals("return Phi(Loop17,s0,Phi(Region41,s0,Phi_ret));", stop.toString()); } @Test @@ -452,4 +453,120 @@ return 0; assertEquals("return 0;", stop.toString()); } + @Test public void testReadBeforeStores() { + var stop = new Parser(""" + struct S { int x; int y; }; + S a = new S; S b = new S; + a.x = 11; b.x = 22; + S p = a; if (arg) p = b; + int before = p.x; + a.y = 55; b.y = 66; + a.x = 33; b.x = 44; + return before*100 + p.x; + """).parse().iterate(); + assertEquals(1133L, com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,0)); + assertEquals(2244L, com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,1)); + } + + static final String NESTED_MEMORY = """ + struct S { int x; int y; int z; }; + S s = new S; + s.x = 5; s.y = 7; s.z = 11; + while (arg > 0) { + s.x = s.x + 1; + int j = 3; + while (j > 0) { + j = j - 1; + if (j == 1) continue; + s.y = s.y + arg; + if (arg == 2) break; + s.z = s.z + 1; + } + arg = arg - 1; + } + return s; + """; + + @Test public void testMemoryAcrossNestedLoops() { + var stop = new Parser(NESTED_MEMORY).parse().iterate(); + for (int arg=0; arg<7; arg++) { + var obj = (com.seaofnodes.simple.evaluator.Evaluator.Obj) + com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,arg); + org.junit.Assert.assertArrayEquals(new Object[] { + 5L+arg, 7L+arg*(arg+1)-(arg>=2 ? 2 : 0), 11L+2*arg-(arg>=2 ? 2 : 0) + }, obj.fields()); + } + } + + @Test public void testMemoryAtEarlyReturns() { + var stop = new Parser(""" + struct S { int x; int y; int z; }; + S s = new S; + s.x = 3; s.y = 5; s.z = 7; + if (arg) { s.x = 11; s.z = 13; return s; } + s.y = 17; + return s; + """).parse().iterate(); + for (int arg=0; arg<2; arg++) { + var obj = (com.seaofnodes.simple.evaluator.Evaluator.Obj) + com.seaofnodes.simple.evaluator.Evaluator.evaluate(stop,arg); + org.junit.Assert.assertArrayEquals(arg==0 ? new Object[]{3L,17L,7L} : new Object[]{11L,5L,13L}, obj.fields()); + } + } + + @Test public void testKeepLoadsAtMerge() { + StopNode stop = new Parser(""" + struct S { int x; }; + S a = new S; S b = new S; + a.x = arg; b.x = arg+1; + S p = a; S q = b; + if (arg<0) { p=b; q=a; } + int v; + if (arg>1) v=p.x; else v=q.x; + return v; + """).parse().iterate(); + // The one-step safety check stops at the memory aggregate. + assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet())); + assertEquals(-1L,Evaluator.evaluate(stop,-1)); + assertEquals(1L,Evaluator.evaluate(stop,0)); + assertEquals(3L,Evaluator.evaluate(stop,3)); + } + + @Test public void testDropStores() { + StopNode stop = new Parser(""" + struct S { int x; }; + S s = new S; + if (arg) s.x=arg+1; else s.x=arg+2; + return s; + """).parse().iterate(); + assertEquals(1,countMemoryNodes(stop,StoreNode.class,new BitSet())); + assertEquals(2L,((Evaluator.Obj)Evaluator.evaluate(stop,0)).fields()[0]); + assertEquals(4L,((Evaluator.Obj)Evaluator.evaluate(stop,3)).fields()[0]); + } + + @Test public void testKeepReadsBeforeWrites() { + StopNode stop = new Parser(""" + struct S { int x; int y; }; + S a = new S; S b = new S; + a.x=arg; b.x=arg+1; + S p=a; S q=b; + if (arg<0) { p=b; q=a; } + int v; + if (arg>1) { v=p.x; p.x=41; p.y=5; } + else { v=q.x; q.x=42; } + return v; + """).parse().iterate(); + assertEquals(2,countMemoryNodes(stop,LoadNode.class,new BitSet())); + assertEquals(-1L,Evaluator.evaluate(stop,-1)); + assertEquals(1L,Evaluator.evaluate(stop,0)); + assertEquals(3L,Evaluator.evaluate(stop,3)); + } + + private static int countMemoryNodes(Node n, Class kind, BitSet seen) { + if (n==null || seen.get(n._nid)) return 0; + seen.set(n._nid); + int cnt=kind.isInstance(n) ? 1 : 0; + for (Node def : n._inputs) cnt+=countMemoryNodes(def,kind,seen); + return cnt; + } } diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter10bTest.java new file mode 100644 index 00000000..4281f0a1 --- /dev/null +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter10bTest.java @@ -0,0 +1,64 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.evaluator.Evaluator; +import org.junit.Test; +import static org.junit.Assert.*; + +public class Chapter10bTest { + @Test public void testIndependentField() { + var stop = new Parser(""" + struct S { int x; int y; }; + S s = new S; + s.x = 42; + while (arg > 0) { s.y = s.y + arg; arg = arg - 1; } + return s.x; + """).parse().iterate(); + assertEquals("return 42;",stop.toString()); + assertEquals(42L,Evaluator.evaluate(stop,5)); + assertNull(stop.walk(n -> n instanceof LoadNode ? n : null)); + } + + @Test public void testParallelMemoryPhis() { + var stop = new Parser(""" + struct S { int x; int y; int z; }; + S a = new S; S b = new S; + S p = a; if (arg) p = b; + while (arg > 0) { + a.x = p.x + arg; + a.y = p.y + 2; + a.z = p.z + 3; + arg = arg - 1; + } + return a; + """).parse().iterate(); + int[] phis = {0}; + stop.walk(n -> { + if (n instanceof MemPhiNode) phis[0]++; + if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b) + for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1)) + assertTrue(a=3); + assertArrayEquals(new Object[]{1L,2L,3L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); + } + + @Test public void testLateSliceWorklist() throws ReflectiveOperationException { + // Seed 97 exposed a store selecting a bulk predecessor without queuing + // it. Keep both the worklist assertion and the final heap check. + for (int seed : new int[]{0,97,123,456}) { + var parser = new Parser(Chapter10Test.NESTED_MEMORY); + var field = IterPeeps.class.getDeclaredField("WORK"); + field.setAccessible(true); + Object work = field.get(null); + field = work.getClass().getDeclaredField("_R"); + field.setAccessible(true); + ((java.util.Random)field.get(work)).setSeed(seed); + var stop = parser.parse().iterate(); + assertArrayEquals(new Object[]{9L,25L,17L},((Evaluator.Obj)Evaluator.evaluate(stop,4)).fields()); + } + } +} diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter11Test.java index 30bcab1e..1183da5f 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -325,7 +325,7 @@ while( prime <= arg ) { return primeCount; """); StopNode stop = parser.parse().iterate(); - assertEquals("Stop[ return 0; return Phi(Loop23,1,Phi(Region100,Phi_primeCount,Phi(Region93,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString()); + assertEquals("Stop[ return 0; return Phi(Loop21,1,Phi(Region88,Phi_primeCount,Phi(Region82,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString()); assertEquals(0L, Evaluator.evaluate(stop, 1)); // No primes 1 or below assertEquals(1L, Evaluator.evaluate(stop, 2)); // 2 assertEquals(2L, Evaluator.evaluate(stop, 3)); // 2, 3 @@ -370,7 +370,7 @@ if (arg) { return i; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Region45,.f,0);", stop.toString()); + assertEquals("return Phi(Region48,.f,0);", stop.toString()); } @Test @@ -477,7 +477,7 @@ while(arg) { return arg; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop20,arg,Phi(Region48,.f,0));", stop.toString()); + assertEquals("return Phi(Loop23,arg,Phi(Region50,.f,0));", stop.toString()); } @Test diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter12Test.java index c93f905d..998053ec 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -64,7 +64,7 @@ while( 1 ) { return guess; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0));", stop.toString()); + assertEquals("return Phi(Loop10,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0));", stop.toString()); assertEquals(3.0, Evaluator.evaluate(stop, 9)); assertEquals(1.414213562373095, Evaluator.evaluate(stop, 2)); } diff --git a/chapter16/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter16/src/test/java/com/seaofnodes/simple/Chapter14Test.java index 7d7bb25a..03a02795 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -59,7 +59,7 @@ while( b ) b = b + 456;// Truncate return b; """); StopNode stop = parser.parse().iterate(); - assertEquals("return Phi(Loop11,123,((Phi_b+456)&255));", stop.toString()); + assertEquals("return Phi(Loop10,123,((Phi_b+456)&255));", stop.toString()); } @Test @@ -175,7 +175,7 @@ while(v1) break; return v1; """); StopNode stop = parser.parse().iterate(); - assertEquals("return (Phi(Loop18,((1<{side=3.0,diag=1.7320508075688772}", Evaluator.evaluate(stop, 3).toString()); assertEquals("Obj{side=4.0,diag=2.0}", Evaluator.evaluate(stop, 4).toString()); } + static final String CONSTRUCTOR_MEMORY = """ + struct S { int x; int y; }; + struct T { int z=arg+40; }; + T t = new T; + S a = new S { x=11; y=7; }; + S b = new S { x=22; y=9; }; + S p=a; + if (arg) p=b; + int before=p.x; + S c = new S { + x=p.x+1; + { int i=0; while (i<2) { p.y=p.y+1; i=i+1; } } + y=p.y; + }; + p.x=33; + return before*10000+c.x*100+c.y+t.z; + """; + + @Test public void testConstructorMemory() { + StopNode stop = new Parser(CONSTRUCTOR_MEMORY).parse().iterate(); + assertEquals(111249L,Evaluator.evaluate(stop,0)); + assertEquals(222352L,Evaluator.evaluate(stop,1)); + } } diff --git a/chapter16/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter16/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index c215de00..3eb406eb 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -187,7 +187,7 @@ public class Evaluator { Object[] body=null; int num; if( type.isAry() ) { - long sz = (Long)val(alloc.in(1)); + long sz = (Long)val(alloc.size()); long n = offToIdx(sz, type); if( n < 0 ) throw new NegativeArraySizeException(""+n); @@ -201,17 +201,13 @@ public class Evaluator { assert elem instanceof TypeMemPtr; } // Length value - body[0] = vall(alloc.in(2+2)); + body[0] = vall(alloc.in(3)); } else { body = new Object[num = type._fields.length]; for (int i=0; i (double)vall(cast.in(1)); case LoadNode load -> load(load); case StoreNode store -> store(store); + case MemMergeNode merge -> MEMORY; case NewNode alloc -> alloc(alloc); case CProjNode cproj -> ((Object[])val(cproj.ctrl()))[cproj._idx]; case ProjNode proj -> ((Object[])val( proj.in(0) ))[ proj._idx]; - case ScopeMinNode mem -> null; default -> throw new AssertionError("Unexpected node " + node); }; } @@ -330,7 +326,7 @@ public class Evaluator { case null: return Status.FALLTHROUGH; case ReturnNode ret: - return val(ret.in(1)); + return val(ret.expr()); case IfNode ifn: block = block.next()[isTrue(val(ifn.in(1))) ? 0 : 1]; if (block == null) return Status.FALLTHROUGH; diff --git a/chapter16/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java b/chapter16/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java index 06169e2c..afcc700f 100644 --- a/chapter16/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java +++ b/chapter16/src/test/java/com/seaofnodes/simple/evaluator/Scheduler.java @@ -31,6 +31,8 @@ import java.util.*; */ public class Scheduler { + private final HashMap> readers = new HashMap<>(); + /** * A basic block with a schedule of the containing nodes. * @@ -252,7 +254,7 @@ public class Scheduler { // but they did not refine the placement // so do that now. var mem = l.in(1); - for(var out : mem._outputs) { + for(var out : l.antiDeps()) { if (out instanceof PhiNode p) { var r = p.in(0); for (int i = 1; i < p.nIns(); i++) { @@ -270,13 +272,9 @@ public class Scheduler { for(var in:data.node._inputs) { if (in!=null) update(d(in), data.block); } - if (data.node instanceof StoreNode s) { - // Store nodes have anti-deps to load nodes. - // So decrease the uses of these loads when the store is placed. - for (var out: s.in(1)._outputs) { - if (out instanceof LoadNode) od(out).ifPresent(this::decUsers); - } - } + var loads = readers.get(data.node); + if (loads != null) + for (var load : loads) decUsers(load); } // Now all nodes should be placed and have a block assigned @@ -442,7 +440,6 @@ public class Scheduler { private void doMarkAlive(Node node) { var cfgQueue = new Stack(); var dataQueue = new Stack(); - var mem = new Stack(); markAlive(cfgQueue, node, true); // Mark all CFG nodes. while (!cfgQueue.isEmpty()) { @@ -467,16 +464,16 @@ public class Scheduler { } else { for (var in : node._inputs) if (in != null && !(in instanceof CFGNode)) markAlive(dataQueue, in, false); } - if (node instanceof StoreNode) mem.push(data); - } - // Handle store nodes and increase load with an anti-dep to the store. - while (!mem.isEmpty()) { - var data = mem.pop(); - node = data.node; - for(var out:node.in(1)._outputs) { - if (out instanceof LoadNode) od(out).ifPresent(d->d.users++); - } } + // Writes, including New behind an aggregate, schedule before their + // anti-dependent reads in this reverse scheduling pass. + for (var load : data.values()) + if (load.node instanceof LoadNode l) + for (var use : l.antiDeps()) + if ((use instanceof StoreNode || use instanceof NewNode) && data.containsKey(use)) { + load.users++; + readers.computeIfAbsent(use,k->new ArrayList<>()).add(load); + } } /** diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md index d7674559..5b16c7fe 100644 --- a/docs/chapter-backports.md +++ b/docs/chapter-backports.md @@ -22,16 +22,15 @@ Splitting Chapter 25 is deferred, not an instruction to renumber. ## Pending corrections -- **Forward Chapter 10b memory partitioning through 16-24.** The 10a/10b split +- **Forward Chapter 10b memory partitioning through 17-24.** The 10a/10b split introduces whole-memory SSA first, then `MemMerge`, `MemPhi`, and `BulkMemPhi`. - Cliff reviewed and committed Chapter 11 as `b475b072`. Chapters 12-15 are - implemented and tested. Chapter 15's approved allocation design is now ready - for implementation review; stop here before proceeding to 16. Subsequent - boundaries include the parser's `ScopeMinNode` in 16 and call/return - aggregation in 18. Keep private constructor memory, escape tracking, and - incomplete-type inference in 25. - Carry the generalized Phi factoring and its dependency fixes from 10a-15 - with the next ports; later snapshots already have parts of that rewrite. + Cliff reviewed and committed the port through 15 in `684c23f1`. Chapter 16 is + implemented and tested; stop here for review of constructor integration and + removal of `ScopeMinNode`. The next boundary is call/return aggregation in 18. + Keep private constructor memory, escape tracking, and incomplete-type + inference in 25. Carry generalized Phi factoring, its one-step Load guard, + and dependency fixes with the next ports; later snapshots already have parts + of that rewrite. ### Chapter 15 allocation design (implemented) @@ -65,6 +64,22 @@ Global code motion and the evaluator scheduler both follow an alias through MemMerge to discover the allocation's ordering constraint. MemMerge is packaging, not itself a clobber. The viewer and evaluator use the new slot conventions. +### Chapter 16 constructor integration (implemented, review checkpoint) + +ScopeNode now owns the variable records and one `$mem` binding; the obsolete +ScopeMin alias table is removed. New inputs are `{ctrl, $mem, size, fields...}`, +with initializer inputs in struct-field order. Outputs remain `{ptr, $mem}`; +partial memory coverage and whole-memory integration are unchanged from 15. +Alias contents read initializer types with dependencies, rather than assuming +zero. The evaluator reads these same inputs, including array length. Constructor +body effects participate in ordinary lazy branch/loop memory SSA. + +The sole-use Store-to-New check is deliberately unchanged. A shared allocation +memory result has more users than a per-alias result, so it permits fewer folds. +`Chapter15Test.testBasic5` retains a `.y` Load instead of folding it to 3.14; +both runtime results remain checked. Other changed printed expectations only +adjust Region/Loop IDs after removing parser memory nodes. + ### Other pending corrections - **Chapter 24 Load BOTTOM-on-error backport, unwound/deferred (2026-09-28).** @@ -255,6 +270,20 @@ The top-level runner accepts explicit chapter lists, e.g. ## Validation record +- **Chapter 16 lazy memory and constructors.** Baseline: 237 tests. The port + passes 247 tests, including nine carried memory regressions and one constructor + case combining reads, writes, a loop, and an unrelated alias. Full Make tests + and release builds for 10a-16 pass: **1,568 tests across eight snapshots**. + An additional **7,700 evaluations across 100 optimizer seeds** check memory + behavior, complete scheduling, two-result New, and partial allocation inputs. + Logs: `build/memory16-baseline.log`, `build/memory16-all-tests.log`, and + `build/memory16-seeds.log`. + The changed graph order exposed a dependency notification gap in + `Chapter14Test.testCloneAnd`: replacing Minus#25 rewired And#28 without waking + its dependent Phi#26. `Node.subsume` now wakes each rewired user's recorded + dependents in 10a-16. The existing test passes without weakening its assertions. + Chapters 17+ are unchanged; constructor integration is the review boundary. + - **Generalized Phi factoring, 10a through 15.** Replaced binary-only factoring and the blanket memory exclusion with operand-wise Phis and exact-class `copyEmpty`. Matching Loads and sole-use Stores are eligible when unbound to diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md index f82e8e41..d2b97bdd 100644 --- a/skills/chapter25-codex-notes.md +++ b/skills/chapter25-codex-notes.md @@ -44,9 +44,9 @@ For shared viewer work, read [the graph viewer notes](graph-viewer-codex-notes.m - Chapter 10 is split into `chapter10a` (one bulk memory chain) and `chapter10b` (lazy graph partitioning). Both are standalone snapshots. Cliff reviewed and - committed Chapter 11; the forward port now runs through Chapter 15, whose - allocation design Cliff approved for implementation. Stop for implementation - review here; leave 16-24 unchanged. See the concrete boundary notes + committed the forward port through Chapter 15. Chapter 16 now carries lazy + memory through constructors and removes ScopeMinNode. Stop for implementation + review here; leave 17-24 unchanged. See the concrete boundary notes in `docs/chapter-backports.md`. GCM readiness and anti-dependency checks must both filter by alias and ignore MemMerge as a clobber; keep the evaluator's same alias filtering too. MemMerge still needs ordinary data-dependency placement. @@ -70,7 +70,14 @@ For shared viewer work, read [the graph viewer notes](graph-viewer-codex-notes.m Use a locally sensible fix when the general solution requires concepts not yet introduced; report substantial representation changes for review. -- Generalized Phi factoring now starts in 10a and is forwarded through 15. +- Chapter 16 extends New inputs to `{ctrl, $mem, size, fields...}` while + retaining `{ptr, $mem}` outputs and partial alias coverage. Constructor values + determine alias contents; register dependencies on their nodes as well as + New. ScopeNode owns Var records and the single memory binding. The existing + sole-use Store-to-New guard is intentionally conservative with a shared memory + result; do not add alias traversal just to recover a small constant fold. + +- Generalized Phi factoring now starts in 10a and is forwarded through 16. Memory-specific eligibility lives in `MemOpNode.canDrop`, with virtual Load and Store checks. Load owns `clobbered`: all these chapters check only immediate memory users, without recursion or a visited set. Stop at Stores, @@ -85,8 +92,11 @@ For shared viewer work, read [the graph viewer notes](graph-viewer-codex-notes.m lookup assumes Region/alias identifies the completed memory point. Existing control-bound Stores in 11-14 remain ineligible. `delUse` wakes recorded dependents for user-count queries; Region's empty-diamond fold depends on - projection rewiring as well as projection types. Carry these with the 16+ + projection rewiring as well as projection types. Carry these with the 17+ memory port; do not duplicate the later chapters' existing `copyEmpty`. + `subsume` must wake each rewired user's recorded dependents, just as `setDef` + does: operand identity changes can enable a Phi fold without changing the + intervening operation's type (`Chapter14Test.testCloneAnd` in 16). - Find the chapter where the relevant feature first appears, not just the chapter that can parse the original reproducer. Reduce away later syntax/features when possible. Put the regression in that earliest `ChapterNTest.java`, and forward -- cgit v1.2.3