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 ++++++++++++----
 .../main/java/com/seaofnodes/simple/node/FunNode.java    |  7 ++++++-
 2 files changed, 18 insertions(+), 5 deletions(-)

(limited to 'chapter25/src')

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);
 
-- 
cgit v1.2.3