From df5efaa0d05b3583eb6ca3b5f67df83827889e42 Mon Sep 17 00:00:00 2001
From: Cliff Click <cliffc@acm.org>
Date: Wed, 7 Oct 2026 11:18:47 -0700
Subject: Make RA deterministic

---
 .../java/com/seaofnodes/simple/codegen/RegAlloc.java  | 16 ++++++++++++----
 .../java/com/seaofnodes/simple/codegen/RegAlloc.java  | 16 ++++++++++++----
 .../java/com/seaofnodes/simple/codegen/RegAlloc.java  | 16 ++++++++++++----
 .../java/com/seaofnodes/simple/codegen/RegAlloc.java  | 16 ++++++++++++----
 .../java/com/seaofnodes/simple/codegen/RegAlloc.java  | 16 ++++++++++++----
 .../java/com/seaofnodes/simple/codegen/RegAlloc.java  | 16 ++++++++++++----
 .../main/java/com/seaofnodes/simple/node/FunNode.java |  7 ++++++-
 docs/chapter-backports.md                             | 19 +++++++++++++++++++
 skills/chapter25-codex-notes.md                       | 12 ++++++++++++
 9 files changed, 109 insertions(+), 25 deletions(-)

diff --git a/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
index 420f1007..af28cbb3 100644
--- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
+++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
@@ -290,15 +290,17 @@ public class RegAlloc {
                         (use instanceof MachNode mach && mach.twoAddress()!=0 && use.in(mach.twoAddress())==def) )
                     insertBefore( use, use._inputs.find(def), "use/self/use",round,lrg );
             }
-            // Split after the Phi which extends the LRG.  Split also before
-            // Phi slot 1 (and not all inputs), because Phis extend the live range.
-            // TODO: split before all inputs (except the last; at least 1 split here must be extra)
+            // Split after the Phi and before its entry.  Also isolate inputs
+            // shared with another Phi: otherwise the shared input keeps the
+            // conflicting live ranges joined, even after splitting the entry.
             if( def instanceof PhiNode phi && !(def instanceof ParmNode) ) {
                 SplitNode split = makeSplit("def/self",round,lrg);
                 insertAfterAndReplace(split,def,false);
                 if( split.nOuts()==0 )
                     split.killOrdered();
-                insertBefore(phi,1,"use/self/phi",round,lrg);
+                for( int i=1; i<phi.nIns(); i++ )
+                    if( i==1 || sharedPhiInput(phi,i) )
+                        insertBefore(phi,i,"use/self/phi",round,lrg);
             }
             // Split before two-address ops which extend the live range
             if( def instanceof MachNode mach && mach.twoAddress()!= 0 )
@@ -308,6 +310,12 @@ public class RegAlloc {
     }
 
 
+    private static boolean sharedPhiInput(PhiNode phi, int i) {
+        for( Node use : phi.in(i)._outputs )
+            if( use instanceof PhiNode && use!=phi ) return true;
+        return false;
+    }
+
     // Generic: split around the outermost loop with non-split def/uses.  This
     // covers both self-conflicts (once we split deep enough) and register
     // pressure issues.
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
index 6a9798b3..dd3d2acb 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
@@ -305,15 +305,17 @@ public class RegAlloc {
                         (use instanceof MachNode mach && mach.twoAddress()!=0 && use.in(mach.twoAddress())==def) )
                     insertBefore( use, use._inputs.find(def), "use/self/use",round,lrg );
             }
-            // Split after the Phi which extends the LRG.  Split also before
-            // Phi slot 1 (and not all inputs), because Phis extend the live range.
-            // TODO: split before all inputs (except the last; at least 1 split here must be extra)
+            // Split after the Phi and before its entry.  Also isolate inputs
+            // shared with another Phi: otherwise the shared input keeps the
+            // conflicting live ranges joined, even after splitting the entry.
             if( def instanceof PhiNode phi && !(def instanceof ParmNode) ) {
                 SplitNode split = makeSplit("def/self",round,lrg);
                 insertAfterAndReplace(split,def,false);
                 if( split.nOuts()==0 )
                     split.killOrdered();
-                insertBefore(phi,1,"use/self/phi",round,lrg);
+                for( int i=1; i<phi.nIns(); i++ )
+                    if( i==1 || sharedPhiInput(phi,i) )
+                        insertBefore(phi,i,"use/self/phi",round,lrg);
             }
             // Split before two-address ops which extend the live range
             if( def instanceof MachNode mach && mach.twoAddress()!= 0 )
@@ -323,6 +325,12 @@ public class RegAlloc {
     }
 
 
+    private static boolean sharedPhiInput(PhiNode phi, int i) {
+        for( Node use : phi.in(i)._outputs )
+            if( use instanceof PhiNode && use!=phi ) return true;
+        return false;
+    }
+
     // Generic: split around the outermost loop with non-split def/uses.  This
     // covers both self-conflicts (once we split deep enough) and register
     // pressure issues.
diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
index b7e105ba..5a641490 100644
--- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
+++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
@@ -305,15 +305,17 @@ public class RegAlloc {
                         (use instanceof MachNode mach && mach.twoAddress()!=0 && use.in(mach.twoAddress())==def) )
                     insertBefore( use, use._inputs.find(def), "use/self/use",round,lrg );
             }
-            // Split after the Phi which extends the LRG.  Split also before
-            // Phi slot 1 (and not all inputs), because Phis extend the live range.
-            // TODO: split before all inputs (except the last; at least 1 split here must be extra)
+            // Split after the Phi and before its entry.  Also isolate inputs
+            // shared with another Phi: otherwise the shared input keeps the
+            // conflicting live ranges joined, even after splitting the entry.
             if( def instanceof PhiNode phi && !(def instanceof ParmNode) ) {
                 SplitNode split = makeSplit("def/self",round,lrg);
                 insertAfterAndReplace(split,def,false);
                 if( split.nOuts()==0 )
                     split.killOrdered();
-                insertBefore(phi,1,"use/self/phi",round,lrg);
+                for( int i=1; i<phi.nIns(); i++ )
+                    if( i==1 || sharedPhiInput(phi,i) )
+                        insertBefore(phi,i,"use/self/phi",round,lrg);
             }
             // Split before two-address ops which extend the live range
             if( def instanceof MachNode mach && mach.twoAddress()!= 0 )
@@ -323,6 +325,12 @@ public class RegAlloc {
     }
 
 
+    private static boolean sharedPhiInput(PhiNode phi, int i) {
+        for( Node use : phi.in(i)._outputs )
+            if( use instanceof PhiNode && use!=phi ) return true;
+        return false;
+    }
+
     // Generic: split around the outermost loop with non-split def/uses.  This
     // covers both self-conflicts (once we split deep enough) and register
     // pressure issues.
diff --git a/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
index 43180b64..6518f3b3 100644
--- a/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
+++ b/chapter23/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
@@ -360,15 +360,17 @@ public class RegAlloc {
                         (use instanceof MachNode mach && mach.twoAddress()!=0 && use.in(mach.twoAddress())==def) )
                     insertBefore( use, use._inputs.find(def), "use/self/use",round,lrg );
             }
-            // Split after the Phi which extends the LRG.  Split also before
-            // Phi slot 1 (and not all inputs), because Phis extend the live range.
-            // TODO: split before all inputs (except the last; at least 1 split here must be extra)
+            // Split after the Phi and before its entry.  Also isolate inputs
+            // shared with another Phi: otherwise the shared input keeps the
+            // conflicting live ranges joined, even after splitting the entry.
             if( def instanceof PhiNode phi && !(def instanceof ParmNode) ) {
                 SplitNode split = makeSplit("def/self",round,lrg);
                 insertAfterAndReplace(split,def,false);
                 if( split.nOuts()==0 )
                     split.killOrdered();
-                insertBefore(phi,1,"use/self/phi",round,lrg);
+                for( int i=1; i<phi.nIns(); i++ )
+                    if( i==1 || sharedPhiInput(phi,i) )
+                        insertBefore(phi,i,"use/self/phi",round,lrg);
             }
             // Split before two-address ops which extend the live range
             if( def instanceof MachNode mach && mach.twoAddress()!= 0 )
@@ -378,6 +380,12 @@ public class RegAlloc {
     }
 
 
+    private static boolean sharedPhiInput(PhiNode phi, int i) {
+        for( Node use : phi.in(i)._outputs )
+            if( use instanceof PhiNode && use!=phi ) return true;
+        return false;
+    }
+
     // Generic: split around the outermost loop with non-split def/uses.  This
     // covers both self-conflicts (once we split deep enough) and register
     // pressure issues.
diff --git a/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
index 0899099e..7e826661 100644
--- a/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
+++ b/chapter24/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
@@ -378,9 +378,9 @@ public class RegAlloc {
                         (use instanceof MachNode mach && mach.twoAddress()!=0 && use.in(mach.twoAddress())==def) )
                     insertBefore( use, use._inputs.find(def), "use/self/use",round,lrg );
             }
-            // Split after the Phi which extends the LRG.  Split also before
-            // Phi slot 1 (and not all inputs), because Phis extend the live range.
-            // TODO: split before all inputs (except the last; at least 1 split here must be extra)
+            // Split after the Phi and before its entry.  Also isolate inputs
+            // shared with another Phi: otherwise the shared input keeps the
+            // conflicting live ranges joined, even after splitting the entry.
             if( def instanceof PhiNode phi && !(def instanceof ParmNode) ) {
                 if( !deferred.containsKey(phi) ) {
                     SplitNode split = makeSplit("def/self",round,lrg);
@@ -388,7 +388,9 @@ public class RegAlloc {
                     if( split.nOuts()==0 )
                         split.killOrdered();
                 }
-                insertBefore(phi,1,"use/self/phi",round,lrg);
+                for( int i=1; i<(deferred.containsKey(phi) ? 2 : phi.nIns()); i++ )
+                    if( i==1 || sharedPhiInput(phi,i) )
+                        insertBefore(phi,i,"use/self/phi",round,lrg);
             }
             // Split before two-address ops which extend the live range
             if( def instanceof MachNode mach && mach.twoAddress()!= 0 )
@@ -405,6 +407,12 @@ public class RegAlloc {
     }
 
 
+    private static boolean sharedPhiInput(PhiNode phi, int i) {
+        for( Node use : phi.in(i)._outputs )
+            if( use instanceof PhiNode && use!=phi ) return true;
+        return false;
+    }
+
     // Generic: split around the outermost loop with non-split def/uses.  This
     // covers both self-conflicts (once we split deep enough) and register
     // pressure issues.
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
index 756262ee..1ce68080 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
@@ -451,9 +451,9 @@ public class RegAlloc {
                         (use instanceof MachNode mach && mach.twoAddress()!=0 && use.in(mach.twoAddress())==def) )
                     insertBefore( use, use._inputs.find(def), "use/self/use",round,lrg );
             }
-            // Split after the Phi which extends the LRG.  Split also before
-            // Phi slot 1 (and not all inputs), because Phis extend the live range.
-            // TODO: split before all inputs (except the last; at least 1 split here must be extra)
+            // Split after the Phi and before its entry.  Also isolate inputs
+            // shared with another Phi: otherwise the shared input keeps the
+            // conflicting live ranges joined, even after splitting the entry.
             if( def instanceof PhiNode phi && !(def instanceof ParmNode) ) {
                 if( !deferred.containsKey(phi) ) {
                     SplitNode split = makeSplit("def/self",round,lrg);
@@ -461,7 +461,9 @@ public class RegAlloc {
                     if( split.nOuts()==0 )
                         split.killOrdered();
                 }
-                insertBefore(phi,1,"use/self/phi",round,lrg);
+                for( int i=1; i<(deferred.containsKey(phi) ? 2 : phi.nIns()); i++ )
+                    if( i==1 || sharedPhiInput(phi,i) )
+                        insertBefore(phi,i,"use/self/phi",round,lrg);
             }
             // Split before two-address ops which extend the live range
             if( def instanceof MachNode mach && mach.twoAddress()!= 0 )
@@ -478,6 +480,12 @@ public class RegAlloc {
     }
 
 
+    private static boolean sharedPhiInput(PhiNode phi, int i) {
+        for( Node use : phi.in(i)._outputs )
+            if( use instanceof PhiNode && use!=phi ) return true;
+        return false;
+    }
+
     // Generic: split around the outermost loop with non-split def/uses.  This
     // covers both self-conflicts (once we split deep enough) and register
     // pressure issues.
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java
index 19b459df..29e9900a 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/FunNode.java
@@ -6,6 +6,7 @@ import com.seaofnodes.simple.type.*;
 import com.seaofnodes.simple.util.BAOS;
 import com.seaofnodes.simple.util.SB;
 import com.seaofnodes.simple.util.Utils;
+import java.util.Arrays;
 import java.util.BitSet;
 import java.util.HashMap;
 import java.util.IdentityHashMap;
@@ -341,7 +342,11 @@ public class FunNode extends RegionNode {
             if( !(fun2.in(i) instanceof CallNode call) || !body2.get(call._nid) )
                 fun2.removeDeadPath(i--);
 
-        for( Node old : map.keySet() )
+        // Linking adds graph edges and worklist entries; identity-map order
+        // would make inlining depend on the host JVM's object hashes.
+        Node[] olds = map.keySet().toArray(new Node[0]);
+        Arrays.sort(olds, (x,y) -> Integer.compare(x._nid,y._nid));
+        for( Node old : olds )
             if( old instanceof CallNode oldCall )
                 relinkClonedCall(oldCall,(CallNode)map.get(oldCall),map);
 
diff --git a/docs/chapter-backports.md b/docs/chapter-backports.md
index 220bc073..e909e573 100644
--- a/docs/chapter-backports.md
+++ b/docs/chapter-backports.md
@@ -670,6 +670,25 @@ The top-level runner accepts explicit chapter lists, e.g.
 
 ## Validation record
 
+- **Shared Phi inputs and deterministic inlining (2026-10-07).** Chapters
+  20-25 split a self-conflicting Phi's inputs when another Phi shares them;
+  splitting only the entry and result could leave two loop Phis joined through
+  their backedge forever. Chapters 24-25 keep their first cold-only attempt.
+  Chapter 25 relinks cloned calls in node-ID order, removing identity-map
+  iteration order from graph edges and optimizer worklists. The original
+  SystemV sys-library allocation failure reproduced directly on Windows with
+  `-XX:+UnlockExperimentalVMOptions -XX:hashCode=2`. With both fixes, complete
+  phase dumps through allocation agree between Windows Java 21.0.4, Windows
+  with constant identity hashes, and Linux Temurin 21.0.12.1. Windows suites
+  pass in all six affected chapters (406, 445, 466, 488, 518, and 494 tests),
+  including native tests and unchanged spill expectations. No tests were added.
+  A fresh Linux checkout with Temurin 21 passes the exact CI command
+  `make lib tests CTAGS=`, including all chapters, a fresh SystemV sys library,
+  native tests, and shared printer/ISA checks.
+  Logs: `build/ci-linux-all-tests.log`, `build/ci-windows-tests.log`,
+  `build/ci-windows-ch25-final.log`, and
+  `build/ci-fixed-{default,constant,linux}.log`.
+
 - **Unused parser memory aggregates, Chapters 11-24 (2026-10-03).** Release
   temporary prior-memory keeps with dead-node cleanup after publishing the new
   memory value. Flattening a MemMerge could remove its last real use while the
diff --git a/skills/chapter25-codex-notes.md b/skills/chapter25-codex-notes.md
index 2f2f299c..7c33d608 100644
--- a/skills/chapter25-codex-notes.md
+++ b/skills/chapter25-codex-notes.md
@@ -331,6 +331,18 @@ For shared viewer work, read [the graph viewer notes](graph-viewer-codex-notes.m
 
 ## Register allocation review
 
+- Phi self-conflict splitting must isolate inputs shared with another Phi,
+  not only the entry input and result. Two loop Phis sharing a backedge value
+  otherwise stay in one conflicting LRG across every round. The correction
+  starts in 20; 24-25 retain their first cold-only attempt.
+- Chapter 25's cloned-call relinking must visit old nodes in node-ID order.
+  Iterating the clone IdentityHashMap changed call edges and optimizer worklist
+  order across JVMs. The SystemV sys build reproduced on Windows with
+  `-XX:+UnlockExperimentalVMOptions -XX:hashCode=2`; WSL was not essential.
+  When investigating reproducibility, compare phase dumps before blaming the
+  allocator or target ABI. Even diagnostic identity maps can perturb JVM hash
+  assignment and expose an existing dependence on identity iteration order.
+
 - Allocation starts in 20; native encoding in 21. Backport legality and
   no-progress fixes to the first applicable chapter, but introduce spill-quality
   heuristics gradually. Do not import the complete Chapter 25 allocator into 20.
-- 
cgit v1.2.3