From c1d8d90f5246a41e42189ffbfcde017873bf5b72 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sun, 20 Sep 2026 16:23:20 -0700 Subject: Forward-port allocator bug fixes and test support through ch25 Improved spilling --- .../com/seaofnodes/simple/codegen/BuildLRG.java | 2 +- .../java/com/seaofnodes/simple/codegen/IFG.java | 4 ++-- .../com/seaofnodes/simple/codegen/RegAlloc.java | 22 +++++++++++++++------- .../com/seaofnodes/simple/codegen/RegMask.java | 18 +++++++----------- 4 files changed, 25 insertions(+), 21 deletions(-) (limited to 'chapter25/src/main/java/com/seaofnodes') diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index 911e69f6..aa33a7ec 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -46,7 +46,7 @@ abstract public class BuildLRG { RegMask mask1 = n.in (1) instanceof MachNode machx ? machx.outregmap() : alloc.lrg(n.in(1))._mask; RegMask mask2 = n.in (2) instanceof MachNode machx ? machx.outregmap() : alloc.lrg(n.in(2))._mask; RegMask masko = n.out(0) instanceof MachNode machx ? machx.regmap(uidx): mach.outregmap(); - if( !mask1.overlap(masko) && mask2.overlap(masko) ) + if( masko!=null && !mask1.overlap(masko) && mask2.overlap(masko) ) n.swap12(); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java index e4e9dd69..8d09b58c 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -447,7 +447,7 @@ abstract public class IFG { // Pick single-def clonables that are not right next to their single-use. // Rank by the area recovered by cloning closer to the use. - if( !lrg._multiDef && lrg._machDef.isClone() && lrg._machUse != null ) { + if( !lrg._multiDef && lrg._machDef!=null && lrg._machUse!=null && lrg._machDef.isClone() ) { Node def = ((Node)lrg._machDef); Node use = ((Node)lrg._machUse); CFGNode cfg = def.cfg0(); @@ -527,7 +527,7 @@ abstract public class IFG { private static int biasable(Node split) { if( split instanceof SplitNode ) return 1; // Yes biasable, advance is slot 1 - if( split instanceof PhiNode phi ) return phi.region() instanceof LoopNode ? 2 : 1; // Yes biasable, advance is slot 1 + if( split instanceof PhiNode phi ) return phi.region() instanceof LoopNode ? 2 : 1; // Prefer the backedge in loops if( !(split instanceof MachNode mach) ) return 0; // Not biasable return mach.twoAddress(); // Only biasable if 2-addr } 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 f8c96ff2..4a880a19 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -190,14 +190,14 @@ public class RegAlloc { while( !graphColor(round) ) { split(round); if( round >= 7 ) // Really expect to be done soon - throw Utils.TODO("Allocator taking too long"); + throw new IllegalStateException("Register allocation made no progress after eight rounds"); round++; } postColor(); // Remove no-op spills _done = true; } - private boolean verifyFunctionLocalEdges() { + boolean verifyFunctionLocalEdges() { for( CFGNode bb : _code._cfg ) for( Node use : bb._outputs ) { FunNode useFun = funOf(use); @@ -300,7 +300,9 @@ public class RegAlloc { if( lrg._mask.isEmpty() ) { if( lrg._1regDefCnt <= 1 && lrg._1regUseCnt <= 1 && - (lrg._1regDefCnt + lrg._1regUseCnt) > 0 ) + (lrg._1regDefCnt + lrg._1regUseCnt) > 0 && + // A fixed-register clone with flexible uses must split at the uses. + !(lrg._1regDefCnt==1 && lrg._machDef.isClone() && lrg._1regUseCnt==0) ) return splitEmptyMaskSimple(round,lrg); // Repeated single-reg uses from a single def. Special for archs // with more fixed regs. @@ -734,10 +736,10 @@ public class RegAlloc { break; hi = hi.in(1); } - // Check no clobbers - for( int idx = j-1; bb.out(idx) != hi; idx++) { + // Walk backward from the later copy, including instructions without results. + for( int idx = j-1; bb.out(idx) != hi; idx--) { Node n = bb.out(idx); - if( lrg(n)!=null && lrg(n)._reg == defreg ) + if( clobbers(n,defreg) ) return false; // Clobbered } lo.setDefOrdered(1,hi.in(1)); @@ -745,6 +747,12 @@ public class RegAlloc { } + private boolean clobbers(Node n, int reg) { + LRG lrg = lrg(n); + return lrg!=null && (lrg._reg==reg || lrg._reg==-1 && lrg._mask.size1() && lrg._mask.firstReg()==reg) || + n instanceof MachNode mach && mach.killmap()!=null && mach.killmap().test(reg); + } + public boolean sameBlockNoClobber( SplitNode split ) { Node def = split.in(1); CFGNode cfg = def.cfg0(); @@ -758,7 +766,7 @@ public class RegAlloc { Node n = cfg.out(idx); if( n==def0 ) return true; // No clobbers if( lrg(n) == lrg(def) ) return false; // Self conflict - if( lrg(n)!=null && lrg(n)._reg == defreg ) + if( clobbers(n,defreg) ) return false; // Clobbered } throw Utils.TODO("Should not reach here"); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegMask.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegMask.java index 81e47e8e..9cb9ec16 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegMask.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegMask.java @@ -71,16 +71,12 @@ public class RegMask { : Long.numberOfTrailingZeros(_bits1)+64); } public short nextReg(short reg) { - if( reg<64 ) { - long bits0 = _bits0 >> (reg+1); - if( bits0!=0 ) - return (short)(reg+1+Long.numberOfTrailingZeros(bits0)); - reg=64; + if( reg < 63 ) { + long bits0 = _bits0 & (-1L << (reg+1)); + if( bits0!=0 ) return (short)Long.numberOfTrailingZeros(bits0); } - long bits1 = _bits1 >> (reg-64+1); - if( bits1!=0 ) - return (short)(reg+1+Long.numberOfTrailingZeros(bits1)); - return -1; + long bits1 = reg < 64 ? _bits1 : reg < 127 ? _bits1 & (-1L << (reg-63)) : 0; + return bits1==0 ? -1 : (short)(64+Long.numberOfTrailingZeros(bits1)); } boolean isEmpty() { return _bits0==0 && _bits1==0; } @@ -97,8 +93,8 @@ public class RegMask { // Has exactly 1 bit set public boolean size1() { - return ((_bits0 & -_bits0)==_bits0 && _bits1==0) || - ((_bits1 & -_bits1)==_bits1 && _bits0==0); + return !isEmpty() && (((_bits0 & -_bits0)==_bits0 && _bits1==0) || + ((_bits1 & -_bits1)==_bits1 && _bits0==0)); } // Cardinality -- cgit v1.2.3