From 684c23f1c5257886a219d540ac4ec0e574b7e49b Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 29 Sep 2026 16:16:13 -0700 Subject: Bring forward the lazy mem alias Integrate with ch15 NewNode creating aliases --- chapter10b/README.md | 22 ++++-- .../java/com/seaofnodes/simple/node/LoadNode.java | 18 +++++ .../java/com/seaofnodes/simple/node/MemOpNode.java | 7 ++ .../main/java/com/seaofnodes/simple/node/Node.java | 23 +++++- .../java/com/seaofnodes/simple/node/PhiNode.java | 86 +++++++++++++++++----- .../com/seaofnodes/simple/node/RegionNode.java | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 61 +++++++++++++++ 7 files changed, 189 insertions(+), 30 deletions(-) (limited to 'chapter10b') diff --git a/chapter10b/README.md b/chapter10b/README.md index c033a850..dfdf74d5 100644 --- a/chapter10b/README.md +++ b/chapter10b/README.md @@ -123,8 +123,17 @@ not to an expanded type lattice. As in Chapter 10a, diagram edges show lattice order, with top above bottom; field and tuple-element type lattices are elided. Scalar Phis remain ordinary PhiNodes. The scope's Phi factory chooses a -BulkMemPhi for whole memory; splitting constructs MemPhis explicitly. Generic -arithmetic factoring through Phis must not factor a memory aggregate. +BulkMemPhi for whole memory; splitting constructs MemPhis explicitly. Phi +factoring can combine matching Loads or Stores as in Chapter 10a, but cannot +factor MemMerge or BulkMemPhi. Its new memory operands use precise MemPhis for +the operation's alias. Load safety checks only immediate memory users, rejecting +Stores, Phis, and MemMerges. A Phi or aggregate might lead to a later write; +we conservatively skip the rewrite instead of searching farther to save one Load. + +Factoring waits while a BulkMemPhi remains at the same Region. Bulk splitting +identifies parallel slices by Region and alias, whereas factoring a Store can +introduce a memory Phi *before* the Store at that same Region. Waiting avoids +mistaking that earlier memory for the aggregate's completed slice. Memory splitting can increase node count. Progress comes from extracting an alias from a bulk Phi and simplifying its precise chain, rather than from @@ -137,7 +146,9 @@ This also extends the worklist lesson from Chapter 9. A bulk Phi inspects its users, so changes to a user's partition must wake the producer. Selecting a slice from an aggregate can expose a new bulk-Phi user; that selected definition must be queued too. The optimizer's worklist completeness assertion remains -enabled and checks these dependencies. +enabled and checks these dependencies. Factoring also depends on user counts: +removing a use wakes recorded dependents even when the definition's type stays +unchanged. ## Evaluation and ordering @@ -160,8 +171,9 @@ alias to become known later, using the same representation. Its private constructor memory, escape tracking, incomplete types, and module alias remapping are separate extensions and are not needed here. -Chapter 11 schedules this representation, including alias-specific load/store -anti-dependencies. Chapters 12-24 currently retain their older parser-managed +Chapters 11-15 use this representation, including alias-specific load/store +anti-dependencies. Chapter 15 adds allocation with partial memory and typed +alias contents. Chapters 16-24 currently retain their older parser-managed memory chains; forwarding through those snapshots is tracked in the [backport queue](../docs/chapter-backports.md). diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 55822722..5f096ef7 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -26,6 +26,24 @@ public class LoadNode extends MemOpNode { _declaredType = glb; } + @Override boolean canDrop(MemOpNode other, Node dep) { + return super.canDrop(other,dep) && _declaredType==((LoadNode)other)._declaredType && !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 "Load"; } diff --git a/chapter10b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 08e08bbf..44304bcb 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -21,6 +21,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 && err()==null; + } + @Override boolean eq(Node n) { MemOpNode mem = (MemOpNode)n; // Invariant 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 f4972f96..55fa6efd 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -15,14 +15,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 { +public abstract class Node implements 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. @@ -31,7 +31,7 @@ public abstract class Node { * 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 _inputs; + public ArrayList _inputs; /** * Outputs reference Nodes that are not null and have this Node as an @@ -42,7 +42,7 @@ public abstract class Node { * walked in either direction. These outputs are typically used for * efficient optimizations but otherwise have no semantics meaning. */ - public final ArrayList _outputs; + public ArrayList _outputs; /** @@ -210,6 +210,7 @@ public abstract class Node { // 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(); } @@ -598,6 +599,20 @@ public abstract class Node { // 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/chapter10b/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter10b/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 650edd6b..cdb4b7cc 100644 --- a/chapter10b/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter10b/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -70,23 +70,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( !isMem() && 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 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 ) { @@ -116,12 +102,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; j1) 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(); + // The initializing slice also remains live as the aggregate default. + assertEquals(2,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; + } } -- cgit v1.2.3