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 | 4 +- .../java/com/seaofnodes/simple/codegen/IFG.java | 29 ++--- .../com/seaofnodes/simple/codegen/RegAlloc.java | 133 +++++++-------------- .../com/seaofnodes/simple/codegen/RegMask.java | 18 ++- .../simple/node/cpus/riscv/StoreRISC.java | 4 +- .../simple/node/cpus/x86_64_v2/MemOpX86.java | 2 +- 6 files changed, 63 insertions(+), 127 deletions(-) (limited to 'chapter22/src/main/java/com') diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index e9b5eb2e..f4ce4366 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java @@ -40,8 +40,8 @@ abstract public class BuildLRG { int uidx = n.out(0)._inputs.find(n); 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): alloc.lrg(n )._mask; - if( !mask1.overlap(masko) && mask2.overlap(masko) ) + RegMask masko = n.out(0) instanceof MachNode machx ? machx.regmap(uidx): mach.outregmap(); + if( masko!=null && !mask1.overlap(masko) && mask2.overlap(masko) ) n.swap12(); } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/IFG.java index fdd4e2f9..1268db6a 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -207,20 +207,7 @@ abstract public class IFG { assert tlrg.leader(); // Always, tlrg cannot use kills if( tlrg._mask.overlap(killMask) ) { - // Disallow clone-ables from killing registers. Just fail - // them and re-clone closer to target... so no kill. - // Special case for Intel XOR used to zero. - Node n = (Node)m; - CFGNode effUseBlk = n.out(0) instanceof PhiNode phi ? phi.region().cfg(phi._inputs.find(n)) : n.out(0).cfg0(); - if( m.isClone() && // Must be clonable - (n.nOuts()>1 || // Has many users OR - // Only 1 user but effective use is remote block - effUseBlk != n.cfg0() )) - // Then fail the clonable; it should split or move - alloc.fail(alloc.lrg((Node)m)); - // Else clonable cannot move - else if( !tlrg.sub(killMask) ) - alloc.fail(tlrg); + if( !tlrg.sub(killMask) ) alloc.fail(tlrg); } } } @@ -438,13 +425,13 @@ abstract public class IFG { private static int pickRiskyScore( LRG lrg ) { // Pick single-def clonables that are not right next to their single-use. // Failing to color these will clone them closer to their uses. - if( !lrg._multiDef && lrg._machDef.isClone() ) { - Node def = ((Node)lrg._machDef); - Node use = ((Node)lrg._machUse); + 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(); - if( cfg != use.cfg0() || // Different blocks OR + if( lrg._multiUse || cfg != use.cfg0() || // Many uses or different blocks OR // Same block, but not close - cfg._outputs.find(def) < cfg._outputs.find(use)+1 ) + cfg._outputs.find(def)+1 < cfg._outputs.find(use) ) return 1000000; } @@ -452,7 +439,7 @@ abstract public class IFG { // and very cheap to spill. if( lrg._machDef instanceof CalleeSaveNode ) return 1000000-2-lrg._mask.firstReg(); - if( lrg._splitDef != null && lrg._splitDef. in(1) instanceof CalleeSaveNode && + if( lrg._splitDef != null && lrg._splitDef.in(1) instanceof CalleeSaveNode && lrg._splitUse != null && lrg._splitUse.out(0) instanceof ReturnNode ) return 1000000-1; @@ -506,7 +493,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/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java b/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java index 835ca2a5..c0be96f1 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -176,17 +176,35 @@ public class RegAlloc { if( n instanceof NewNode nnn ) nnn.cacheRegs(_code); } + // Optional diagnostic for values accidentally shared across functions. + //assert verifyFunctionLocalEdges(); + // Top driver: repeated rounds of coloring and splitting. byte round=0; 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 } + boolean verifyFunctionLocalEdges() { + for( CFGNode bb : _code._cfg ) { + if( bb instanceof StartNode ) continue; + FunNode fun = bb.fun(); + for( Node use : bb._outputs ) + if( use instanceof MachNode mach && !(use instanceof ParmNode) ) + for( int i=1; i "+use.uniqueName()+" input "+i; + } + } + return true; + } + private boolean graphColor(byte round) { _failed.clear(); _lrgs.clear(); @@ -233,13 +251,11 @@ public class RegAlloc { if( lrg._mask.isEmpty() && (!lrg._multiDef || lrg._1regUseCnt==1) ) { 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. - if( !lrg._multiDef && lrg._1regDefCnt <= 1 && lrg._1regUseCnt > 2 ) - if( splitEmptyMaskByUse(round,lrg) ) - return true; + // More complex conflicts use loop-boundary splitting. } // Generic split-by-loop depth. @@ -255,91 +271,20 @@ public class RegAlloc { // Split just after def if( lrg._1regDefCnt==1 && !lrg._machDef.isClone() ) - // Force must-split, even if a prior split same block because register - // conflicts. Example: + // An earlier copy is reusable only if no intervening clobber. + // Being in the same block alone is insufficient. Example: // alloc // V1/rax - forced by alloc // alloc // V2/rax - kills prior RAX // st4 [V1],len - No good, must split around - insertAfterAndReplace( makeSplit("def/empty1",round,lrg), (Node)lrg._machDef, false/*true*/); + insertAfterAndReplace(makeSplit("def/empty1",round,lrg),(Node)lrg._machDef,false); // Split just before use - if( lrg._1regUseCnt==1 || (lrg._1regDefCnt==1 && ((Node)lrg._machDef).nOuts()==1) ) + if( lrg._1regUseCnt==1 ) insertBefore((Node)lrg._machUse,lrg._uidx,"use/empty1",round,lrg); return true; } - // Single-def live range with an empty mask. There are many single-reg - // uses. Theory is there's many repeats of the same reg amongst the uses. - // In of splitting once per use, start by splitting into groups based on - // required input register. - boolean splitEmptyMaskByUse( byte round, LRG lrg ) { - Node def = (Node)lrg._machDef; - - // Look at each use, and break into non-overlapping register classes. - Ary rclass = new Ary<>(RegMask.class); - boolean done=false; - int ncalls=0; - while( !done ) { - done = true; - for( Node use : def._outputs ) - if( use instanceof MachNode mach ) { - if( mach instanceof CallNode ) ncalls++; - for( int i=1; i 1 ) return false; - - // Split by class - Ary ns = new Ary<>(Node.class); - for( RegMask rmask : rclass ) { - ns.addAll(def._outputs); - Node split = makeSplit(def,"popular",round,lrg,rmask); - split.insertAfter( def ); - if( split.nIns()>1 ) split.setDef(1,def); - // all uses by class to split - for( int j=0; j < def._outputs._len; j++ ) { - Node use = def._outputs.at(j); - if( use instanceof MachNode mach && use!=split ) { - // Check all use inputs for n, in case there's several - for( int i = 1; i < use.nIns(); i++ ) - // Find a def input, and check register class - if( use.in( i ) == def && mach.regmap( i ).overlap( rmask ) ) { - RegMask m = mach.regmap( i ); - if( m!=null && mach.regmap( i ).overlap( rmask ) ) - // Modify use to use the split version specialized to this rclass - { use.setDefOrdered( i, split ); j--; break; } - } - } - } - ns.clear(); - } - return true; - } - - - // Put use into a register class, perhaps adding a class or perhaps - // narrowing a class (and causing a repeat) - private static boolean putIntoRegClass( Ary rclass, RegMask rmask ) { - for( int i=0; i> (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; } @@ -98,8 +94,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 diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java index 7305c4d9..f07389eb 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/riscv/StoreRISC.java @@ -26,7 +26,9 @@ public class StoreRISC extends MemOpRISC { if( i==1 ) return null; // mem if( i==2 ) return riscv.RMASK; // ptr // 2 - index - if( i==4 ) return riscv.MEM_MASK; // Wide mask to store GPR and FPR + if( i==4 ) return _sz >= '4' + ? riscv.MEM_MASK // Word/dword value in GPR or FPR + : riscv.RMASK; // Byte/short stores require a GPR return null; // Anti-dependence } @Override public RegMask outregmap() { return null; } diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java index 97586d87..9f80b1f5 100644 --- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java +++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/MemOpX86.java @@ -66,7 +66,7 @@ public abstract class MemOpX86 extends MemOpNode implements MachNode { if( i==1 ) return null; // Memory if( i==2 ) return x86_64_v2.RMASK; // base in GPR if( i==3 ) return x86_64_v2.RMASK; // index in GPR - if( i==4 ) return _sz >= 2 + if( i==4 ) return _sz >= '4' ? x86_64_v2.MEM_MASK // value in GPR or XMM : x86_64_v2.RMASK; // Bytes and shorts in GPR only return null; // Anti-dependence -- cgit v1.2.3