diff options
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. |