diff options
Diffstat (limited to 'chapter21/src/main')
5 files changed, 79 insertions, 157 deletions
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java index e9b5eb2e..f4ce4366 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java +++ b/chapter21/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/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java index fdd4e2f9..2912e179 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter21/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); } } } @@ -419,7 +406,7 @@ abstract public class IFG { int best=sptr; int bestScore = pickRiskyScore(color_stack[best]); for( int i=sptr+1; i<color_stack.length; i++ ) { - if( bestScore == 1000000 ) return best; // Already max score + if( bestScore == 999999 ) return best; // Already max score int iScore = pickRiskyScore(color_stack[i]); if( iScore > bestScore ) { best = i; bestScore = iScore; } @@ -436,25 +423,13 @@ abstract public class IFG { // Picking a live range that is very close to coloring might allow it to // color despite being risky. 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); - CFGNode cfg = def.cfg0(); - if( cfg != use.cfg0() || // Different blocks OR - // Same block, but not close - cfg._outputs.find(def) < cfg._outputs.find(use)+1 ) - return 1000000; - } - // Always pick callee-save registers as being very large area recovered // 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 && + return 999998; + if( lrg._splitDef != null && lrg._splitDef.in(1) instanceof CalleeSaveNode && lrg._splitUse != null && lrg._splitUse.out(0) instanceof ReturnNode ) - return 1000000-1; + return 999999; // TODO: cost/benefit model. Perhaps counting loop-depth (freq) of def/use for cost // and "area" for benefit @@ -465,39 +440,36 @@ abstract public class IFG { if( mask.size1() ) return reg; // Check chain of splits up the def-chain. Take first allocated // register, and if it's available in the mask, take it. - Node def = lrg._splitDef, use = lrg._splitUse; - int tidx=0, cnt=0; + Node defSplit = lrg._splitDef, useSplit = lrg._splitUse; + int tidx, cnt=0; - while( def != null || use != null ) { + while( (tidx=biasable(defSplit)) != 0 || biasable(useSplit) != 0 ) { if( cnt++ > 10 ) break; - if( def != null ) { - short bias = biasColor( alloc, def, mask ); + if( tidx != 0 ) { + short bias = biasColor( alloc, defSplit, mask ); if( bias >= 0 ) return bias; // Good bias - if( bias == -2 ) def = null; // Kill this side, no more searching - else if( (tidx=biasable(def)) == 0 ) def = null; - } + if( bias == -2 ) defSplit = null; // Kill this side, no more searching + } else defSplit = null; - if( use != null ) { - short bias = biasColor( alloc, use, mask ); + if( biasable(useSplit) != 0 ) { + short bias = biasColor( alloc, useSplit, mask ); if( bias >= 0 ) return bias; // Good bias - if( bias == -2 ) use = null; // Kill this side, no more searching - else if( biasable(use)==0 ) use = null; - } + if( bias == -2 ) useSplit = null; // Kill this side, no more searching + } else useSplit = null; - if( def != null ) { - short bias = biasColorNeighbors( alloc, def, mask ); + if( defSplit != null ) { + short bias = biasColorNeighbors( alloc, defSplit, mask ); if( bias >= 0 ) return bias; // Advance def side - def = def.in(tidx); - if( alloc.lrg(def)==null ) def=null; + defSplit = defSplit.in(tidx); + if( alloc.lrg(defSplit)==null ) defSplit=null; } - if( use != null ) { - short bias = biasColorNeighbors( alloc, use, mask ); + if( useSplit != null ) { + short bias = biasColorNeighbors( alloc, useSplit, mask ); if( bias >= 0 ) return bias; - use = use.out(0); - if( biasable(use)==0 ) use=null; + useSplit = useSplit.out(0); } } @@ -506,7 +478,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 ) return 1; // Yes biasable, advance is slot 1 if( !(split instanceof MachNode mach) ) return 0; // Not biasable return mach.twoAddress(); // Only biasable if 2-addr } 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 0c79ecb0..5d6ba060 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter21/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.nIns(); i++ ) { + Node def = use.in(i); + if( def==null || mach.regmap(i)==null || def.cfg0()==null || def.cfg0() instanceof StartNode ) continue; + assert def.cfg0().fun()==fun : "Cross-function register edge: "+def.uniqueName()+" -> "+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,90 +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<RegMask> 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<use.nIns(); i++ ) - if( use.in(i)==def ) - done = putIntoRegClass( rclass, mach.regmap(i) ); - } - } - - // See how many register classes we split into. Generally not - // productive to split like this across calls, which are going to kill - // all registers anyways. - if( rclass._len <= 1 || ncalls > 1 ) return false; - - // Split by class - Ary<Node> ns = new Ary<>(Node.class); - for( RegMask rmask : rclass ) { - ns.addAll(def._outputs); - Node split = makeSplit(def,"popular",round,lrg); - split.insertAfter( def ); - if( split.nIns()>1 ) split.setDef(1,def); - // all uses by class to split - for( Node use : ns ) { - 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 ) { - 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 ); - } - } - } - 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<RegMask> rclass, RegMask rmask ) { - for( int i=0; i<rclass._len; i++ ) { - RegMask omask = rclass.at(i); - if( omask.and(rmask) == omask ) return true; // Within the same register class - if( omask.overlap(rmask) ) { - rclass.set(i,new RegMask(omask.copy().and(rmask))); - return false; // Need go again - } - } - // Add a new class, no need to go again - rclass.push(rmask); - return true; - } - // Self conflicts require Phis (or two-address). // Insert a split after every def. boolean splitSelfConflict( byte round, LRG lrg ) { @@ -490,8 +436,8 @@ public class RegAlloc { void findAllLRG( LRG lrg ) { _ns.clear(); int wd = 0; - _ns.push((Node)lrg._machDef); - _ns.push((Node)lrg._machUse); + if( lrg._machDef!=null ) _ns.push((Node)lrg._machDef); + if( lrg._machUse!=null ) _ns.push((Node)lrg._machUse); while( wd < _ns._len ) { Node n = _ns.at(wd++); if( lrg(n)!=lrg ) continue; @@ -511,13 +457,14 @@ public class RegAlloc { CFGNode cfg = n instanceof PhiNode phi ? phi.region().cfg(i) : n.cfg0(); // Def is a split ? if( skip && def instanceof SplitNode ) { - boolean singleReg = n instanceof MachNode mach && mach.regmap(i).size1(); + boolean singleReg = n instanceof MachNode mach && mach.regmap(i)!=null && mach.regmap(i).size1(); // Same block, multiple registers, split is only used by n, // assume this is good enough and do not split again. if( cfg==def.cfg0() && def.nOuts()==1 && !singleReg ) return; } - makeSplit(def,kind,round,lrg).insertBefore(n, i); + RegMask use = n instanceof MachNode mach ? mach.regmap(i) : null; + makeSplit(def,kind,round,lrg,use).insertBefore(n, i); // Skip split-of-split same block if( skip && def instanceof SplitNode && cfg==def.cfg0() ) n.in(i).setDefOrdered(1,def.in(1)); @@ -544,8 +491,9 @@ public class RegAlloc { } } - private Node makeSplit( Node def, String kind, byte round, LRG lrg ) { - Node split = def instanceof MachNode mach && mach.isClone() + private Node makeSplit( Node def, String kind, byte round, LRG lrg, RegMask use ) { + // A clone must be able to satisfy the use's register class. + Node split = def instanceof MachNode mach && mach.isClone() && (use==null || mach.outregmap().overlap(use)) ? mach.copy() : _code._mach.split(kind,round,lrg); _lrgs.put(split,lrg); @@ -611,10 +559,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)); @@ -622,6 +570,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(); @@ -635,7 +589,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(); diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegMask.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegMask.java index ec0c4e30..f73cd9a1 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegMask.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegMask.java @@ -72,16 +72,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; } @@ -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/chapter21/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter21/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 929deefd..5c76116f 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -51,7 +51,7 @@ public class ReturnNode extends CFGNode { @Override public Type compute() { if( inProgress () ) return TypeTuple.RET; // In progress - if( _fun.isDead() ) return TypeTuple.RET.dual(); // Dead another way + // Inlining can delete the entry while callers still use this return. return TypeTuple.make(ctrl()._type,mem()._type,expr()._type); } |