summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2026-11-15 16:54:06 -0800
committerCliff Click <cliffc@acm.org>2026-11-15 16:54:06 -0800
commit8b80d94ce545060c09dab9487393f64acbc3e6fe (patch)
tree4517ec6518e5617a5e7f64ff3ec891a5b2c83d8c
parent9fe7c6f9697b5bbf3041261fdc60040e75cc674f (diff)
downloadSimple-8b80d94ce545060c09dab9487393f64acbc3e6fe.tar.gz
Simple-8b80d94ce545060c09dab9487393f64acbc3e6fe.zip
Bunch of unrelated speedups
And some modest tracking bugs
-rw-r--r--chapter32/README.md59
-rw-r--r--chapter32/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java12
-rw-r--r--chapter32/src/main/java/com/seaofnodes/simple/node/IfNode.java4
-rw-r--r--chapter32/src/main/java/com/seaofnodes/simple/node/PhiNode.java3
-rw-r--r--chapter32/src/test/java/com/seaofnodes/simple/Chapter13Test.java4
-rw-r--r--chapter32/src/test/java/com/seaofnodes/simple/SchedulingTest.java39
-rw-r--r--chapter32/src/test/java/com/seaofnodes/simple/WorklistTest.java49
7 files changed, 166 insertions, 4 deletions
diff --git a/chapter32/README.md b/chapter32/README.md
index 53847ea4..4cb1d79b 100644
--- a/chapter32/README.md
+++ b/chapter32/README.md
@@ -162,6 +162,65 @@ also wake on use-count changes. Any narrower filter must preserve the topology
and use-count changes that actually enable a rewrite; deleting subscriptions
just because a sample showed no progress is not enough.
+### MemPhi and IfNode follow-up
+
+The next trace records the notifying node as well as the enqueue stack.
+BulkMemPhi splitting and MemMerge cleanup repeatedly queue precise memory Phis
+as inputs of successful peepholes. Removing memory Phis also changes a Region's
+users, waking IfNodes which subscribed while walking the dominator chain.
+Unlinking callers produces similar notifications from CallNodes.
+
+Two small filters are retained. A type-only update of a user no longer queues
+an already-used, stable MemPhi input. New or edited inputs and first-use Phis
+remain eligible; replacement and edge-edit notifications retain their existing
+behavior. `IfNode.idealize` searches dominators only when both branches remain
+possible. Known branches already fold through CProj and need no new distant
+subscriptions.
+
+On the same 794-method profiling sweep, MemPhi visits fell from 474,510 to
+469,866, IfNode visits from 254,787 to 249,609, and total visits from 3,695,609
+to 3,661,560. The total reduction is 0.9%; whole-suite elapsed times of 91.88
+and 91.64 seconds do not establish a meaningful timing improvement. Existing
+spill expectations still pass. One graph expectation loses a redundant integer
+narrowing; both branches also have execution checks.
+
+A broader experiment separated dependency use-count notifications from type
+and input-edge notifications, and filtered more MemPhi use-count revisits.
+That version changed optimizer ordering enough to increase the Sieve spill
+score from 216 to 343 and the forward-field example from 23 to 31. It is not
+enabled: reducing compiler work is not a reason to silently raise code-quality
+expectations. The broader filter also requires notifying a node's dependents
+when `delDef` changes its inputs, rather than redundantly notifying the old
+input's use-count listeners.
+
+In the 302-method non-chapter group, that isolated experiment reduced MemPhi
+visits from 367,387 to 205,245 and IfNode visits from 144,652 to 59,185. Total
+visits fell 9.7%, but elapsed time was essentially unchanged at 57.48 versus
+57.75 seconds. Fewer visits alone do not demonstrate a runtime improvement.
+
+These measurements precede the verifier fixes below.
+
+### Every-step verifier fixes
+
+Checking every progress step exposed two bugs, both reproducible before the
+MemPhi/IfNode filters:
+
+- `Chapter05Test.testMerge4` fails at iteration 38: replacing `Phi#44` with
+ `arg` changes `If#52`'s predicate and enables `Phi#75`'s guard-merge rewrite.
+ `matchingGuardMerge` had no dependency on that predicate comparison. It now
+ subscribes to the If for direct input edits and to its predicate for replacement
+ through `subsume`. Tests cover both notification paths.
+- `Chapter15Test.testArrayLoadDominatingControl` fails at iteration 30, when a
+ bulk memory Phi splits into a MemMerge. The verifier treated the consuming
+ load's earlier range-check control as its execution block. A memory operation's
+ control is only a lower bound: its data inputs can force it later. The check
+ now includes those inputs, matching early scheduling. Regression tests accept
+ this legal placement and still reject a load used before its memory is ready.
+
+After these fixes, all 802 suite executions pass at log 8; 444 chapter tests and
+34 focused worklist, scheduling, and memory tests pass at log 1. Existing spill
+expectations are unchanged.
+
## Build and test
From `chapter32`, using the existing offline dependency caches:
diff --git a/chapter32/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java b/chapter32/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java
index ba6cb5d8..fe935a69 100644
--- a/chapter32/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java
+++ b/chapter32/src/main/java/com/seaofnodes/simple/codegen/IterPeeps.java
@@ -125,7 +125,13 @@ public class IterPeeps {
// A self-returning peephole can have rewritten its input
// edges. The new defs gained a user and may have
// backwards, user-sensitive peepholes of their own.
- for( Node z : x._inputs ) _work.push(z);
+ boolean edited = x!=n || x.isUnlocked();
+ for( Node z : x._inputs )
+ // A type-only update adds no users. A stable memory
+ // Phi has no backwards rewrite based on user types.
+ // Keep first-use and edited/unprocessed Phis queued.
+ if( edited || !(z instanceof MemPhiNode) || z.nOuts()<=1 || z.isUnlocked() )
+ _work.push(z);
// If the result is not self, revisit all inputs (because
// there's a new user), and replace in the graph.
if( x != n ) {
@@ -237,7 +243,9 @@ public class IterPeeps {
}
return found;
}
- return CFGNode.safeCFG(use);
+ // A memory op can execute after its control (e.g. a range check).
+ // Like schedEarly, include its data inputs before constraining its defs.
+ return use instanceof MemOpNode ? CFGNode.earlyCFG(use,earlyCache,VISIT) : CFGNode.safeCFG(use);
}
private static String badSchedule(Node n, CFGNode early, CFGNode lca) {
diff --git a/chapter32/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter32/src/main/java/com/seaofnodes/simple/node/IfNode.java
index c83c81d0..ad8de653 100644
--- a/chapter32/src/main/java/com/seaofnodes/simple/node/IfNode.java
+++ b/chapter32/src/main/java/com/seaofnodes/simple/node/IfNode.java
@@ -56,7 +56,9 @@ public class IfNode extends CFGNode implements MultiNode {
public Node idealize() {
// Hunt up the immediate dominator tree. If we find an identical if
// test on either the true or false branch, that side wins.
- if( !pred()._type.isHighOrConst() )
+ // Known branches fold through CProj; they need no dominator search
+ // or subscriptions to changes higher up the control flow.
+ if( _type==TypeTuple.IF_BOTH )
for( CFGNode dom = idom(), prior=this; dom!=null; prior = dom, dom = dom.idom() )
if( addDep(dom) instanceof IfNode iff &&
prior instanceof CProjNode prj &&
diff --git a/chapter32/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter32/src/main/java/com/seaofnodes/simple/node/PhiNode.java
index f45c7325..7544962f 100644
--- a/chapter32/src/main/java/com/seaofnodes/simple/node/PhiNode.java
+++ b/chapter32/src/main/java/com/seaofnodes/simple/node/PhiNode.java
@@ -147,6 +147,9 @@ public class PhiNode extends Node {
return null;
if( !(r.in(3-nzIdx) instanceof CProjNode z && z._idx==1 && z.ctrl()==iff) )
return null;
+ // A rewritten predicate can make this guard match without changing the Phi inputs.
+ addDep(iff);
+ addDep(iff.pred()); // subsume wakes the replaced predicate's dependents.
// Predicate was guarded?
Node n = cast.in(1), tested = null;
while( true ) {
diff --git a/chapter32/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter32/src/test/java/com/seaofnodes/simple/Chapter13Test.java
index 70cfe25e..738a4d15 100644
--- a/chapter32/src/test/java/com/seaofnodes/simple/Chapter13Test.java
+++ b/chapter32/src/test/java/com/seaofnodes/simple/Chapter13Test.java
@@ -116,7 +116,9 @@ if (v1) {
return v0.f;
""");
code.driver(CodeGen.Phase.FinalizeIR);
- assertEquals("return ((Phi(Region,((.f<<32)>>32),2)<<32)>>32);", code.print());
+ assertEquals("return Phi(Region,((.f<<32)>>32),2);", code.print());
+ assertEquals("2",Eval2.eval(code,0));
+ assertEquals("0",Eval2.eval(code,1));
}
diff --git a/chapter32/src/test/java/com/seaofnodes/simple/SchedulingTest.java b/chapter32/src/test/java/com/seaofnodes/simple/SchedulingTest.java
index 16e12b0f..28b84ee1 100644
--- a/chapter32/src/test/java/com/seaofnodes/simple/SchedulingTest.java
+++ b/chapter32/src/test/java/com/seaofnodes/simple/SchedulingTest.java
@@ -1,8 +1,47 @@
package com.seaofnodes.simple;
import org.junit.Test;
+import com.seaofnodes.simple.codegen.CodeGen;
+import com.seaofnodes.simple.codegen.IterPeeps;
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
+import static org.junit.Assert.*;
public class SchedulingTest {
+ @Test public void verifierAllowsLoadAfterMemoryMerge() {
+ CodeGen code = loadAfterMemoryMerge();
+ assertTrue(IterPeeps.schedulableUses(code));
+ }
+
+ @Test public void verifierRejectsLoadUsedBeforeMemoryMerge() {
+ CodeGen code = loadAfterMemoryMerge();
+ ReturnNode ret = (ReturnNode)code._stop.walk(n -> n instanceof ReturnNode ? n : null);
+ LoadNode load = (LoadNode)ret.expr();
+ // The load may move below its check, but cannot serve a use above its memory.
+ ret.setDef(0,load.in(0));
+ try {
+ IterPeeps.schedulableUses(code);
+ fail("A load cannot execute before its memory is available");
+ } catch( AssertionError error ) {
+ assertTrue(error.getMessage(),error.getMessage().contains("Unschedulable data node LoadNode"));
+ }
+ }
+
+ private static CodeGen loadAfterMemoryMerge() {
+ CodeGen code = new CodeGen("return arg;").parse();
+ ReturnNode ret = (ReturnNode)code._stop.walk(n -> n instanceof ReturnNode ? n : null);
+ Node ctrl = ret.ctrl();
+ IfNode iff = new IfNode(ctrl,ret.expr()).init();
+ Node yes = new CProjNode(iff,0,"True").init();
+ Node no = new CProjNode(iff,1,"False").init();
+ RegionNode region = new RegionNode(null,null,yes,no).init();
+ Node phi = new BulkMemPhiNode("mem",region,ret.mem(),ret.mem()).init();
+ Node mem = new MemMergeNode(null,phi).init();
+ Node load = new LoadNode(null,"[]",2,ctrl,mem,code.con(TypeMemPtr.BOT),code.con(TypeInteger.ZERO)).init();
+ ret.setDef(0,region);
+ ret.setDef(2,load);
+ return code;
+ }
@Test public void nativeFoldedLoadsWithLaterOperands() throws Exception {
TestC.runSYS("""
val compare_noInline={ i64[] a, int flag ->
diff --git a/chapter32/src/test/java/com/seaofnodes/simple/WorklistTest.java b/chapter32/src/test/java/com/seaofnodes/simple/WorklistTest.java
new file mode 100644
index 00000000..fce15418
--- /dev/null
+++ b/chapter32/src/test/java/com/seaofnodes/simple/WorklistTest.java
@@ -0,0 +1,49 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.codegen.CodeGen;
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.type.*;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+public class WorklistTest {
+ @Test public void testGuardMergeAfterPredicateRewrite() { guardMergeAfterPredicateRewrite(false); }
+ @Test public void testGuardMergeAfterPredicateSubsume() { guardMergeAfterPredicateRewrite(true); }
+
+ private static void guardMergeAfterPredicateRewrite(boolean subsume) {
+ CodeGen code = new CodeGen("");
+ Node ctrl = new CProjNode(code._start,0,"Ctrl").init();
+ Node old = code.con(TypeInteger.BOOL), value = code.con(TypeInteger.BOT);
+ IfNode iff = new IfNode(ctrl,old).init();
+ Node yes = new CProjNode(iff,0,"True").init();
+ Node no = new CProjNode(iff,1,"False").init();
+ RegionNode region = new RegionNode(null,null,yes,no).init();
+ Node guard = new GuardNode(true,yes,value).init();
+ PhiNode phi = new PhiNode("guard",region,guard,code.con(TypeInteger.ZERO)).init();
+ phi.keep();
+ code._iter._work.clear();
+ assertNull(phi.idealize());
+ assertFalse(code._iter._work.on(phi));
+ // Neither edit changes a Phi input; its predicate dependency must wake it.
+ if( subsume ) old.subsume(value);
+ else iff.setDef(1,value);
+ assertTrue("Predicate rewrite must requeue the guard merge",code._iter._work.on(phi));
+ assertSame(value,phi.idealize());
+ phi.unkeep();
+ }
+ @Test public void testKnownIfDoesNotSearchDominators() {
+ CodeGen code = new CodeGen("");
+ Node ctrl = new CProjNode(code._start,0,"Ctrl").init();
+ IfNode outer = new IfNode(ctrl,code.con(TypeInteger.BOOL)).init();
+ Node yes = new CProjNode(outer,0,"True").init();
+ // Nonconstant, but already known to be nonzero.
+ IfNode inner = new IfNode(yes,code.con(TypeInteger.make(1,2))).init();
+ assertSame(TypeTuple.IF_TRUE,inner._type);
+ assertNull(inner.idealize());
+ for( int i=0; i<outer.nDeps(); i++ ) assertNotSame(inner,outer.dep(i));
+ CProjNode live = new CProjNode(inner,0,"Live").init();
+ CProjNode dead = new CProjNode(inner,1,"Dead").init();
+ assertSame(yes,live.idealize());
+ assertSame(code.XCTRL,dead.idealize());
+ }
+}