diff options
Diffstat (limited to 'chapter21/src')
6 files changed, 49 insertions, 37 deletions
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java index 255e4e5e..e2fac779 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/Coalesce.java @@ -10,20 +10,6 @@ import java.util.IdentityHashMap; abstract public class Coalesce { public static boolean coalesce( int round, RegAlloc alloc ) { - // Convert the 2-D array of bits (a 1-D array of BitSets) into an - // adjacency matrix. - int maxlrg = alloc._LRGS.length; - for( int i=1; i<maxlrg; i++ ) { - BitSet ifg = IFG.IFG.atX(i); - if( ifg != null ) { - LRG lrg0 = alloc._LRGS[i]; - for( int lrg = ifg.nextSetBit(0); lrg>=0; lrg=ifg.nextSetBit(lrg+1) ) { - LRG lrg1 = alloc._LRGS[lrg]; - lrg0.addNeighbor(lrg1); - lrg1.addNeighbor(lrg0); - } - } - } // Walk all the splits, looking for coalesce chances boolean progress = false; 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 e85bce5d..34b755b0 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java @@ -79,6 +79,8 @@ abstract public class IFG { while( !WORK.isEmpty() ) do_block(round,alloc,WORK.pop()); + if( alloc.success() ) + convert2DAdjacency(alloc); return alloc.success(); } @@ -266,6 +268,24 @@ abstract public class IFG { } + static void convert2DAdjacency( RegAlloc alloc ) { + // Convert the 2-D array of bits (a 1-D array of BitSets) into an + // adjacency matrix. + int maxlrg = alloc._LRGS.length; + for( int i=1; i<maxlrg; i++ ) { + BitSet ifg = IFG.atX(i); + if( ifg != null ) { + LRG lrg0 = alloc._LRGS[i]; + for( int lrg = ifg.nextSetBit(0); lrg>=0; lrg=ifg.nextSetBit(lrg+1) ) { + LRG lrg1 = alloc._LRGS[lrg]; + lrg0.addNeighbor(lrg1); + lrg1.addNeighbor(lrg0); + } + } + } + } + + // ------------------------------------------------------------------------ // Color the inference graph. @@ -447,35 +467,39 @@ 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 defSplit = lrg._splitDef, useSplit = lrg._splitUse; - int tidx, cnt=0; + Node def = lrg._splitDef, use = lrg._splitUse; + int tidx=0, cnt=0; - while( (tidx=biasable(defSplit)) != 0 || biasable(useSplit) != 0 ) { + while( def != null || use != null ) { if( cnt++ > 10 ) break; - if( tidx != 0 ) { - short bias = biasColor( alloc, defSplit, mask ); + if( def != null ) { + short bias = biasColor( alloc, def, mask ); if( bias >= 0 ) return bias; // Good bias - if( bias == -2 ) defSplit = null; // Kill this side, no more searching - } else defSplit = null; + if( bias == -2 ) def = null; // Kill this side, no more searching + else if( (tidx=biasable(def)) == 0 ) def = null; + } - if( biasable(useSplit) != 0 ) { - short bias = biasColor( alloc, useSplit, mask ); + if( use != null ) { + short bias = biasColor( alloc, use, mask ); if( bias >= 0 ) return bias; // Good bias - if( bias == -2 ) useSplit = null; // Kill this side, no more searching - } else useSplit = null; + if( bias == -2 ) use = null; // Kill this side, no more searching + else if( biasable(use)==0 ) use = null; + } - if( defSplit != null ) { - short bias = biasColorNeighbors( alloc, defSplit, mask ); + if( def != null ) { + short bias = biasColorNeighbors( alloc, def, mask ); if( bias >= 0 ) return bias; // Advance def side - defSplit = defSplit.in(tidx); + def = def.in(tidx); + if( alloc.lrg(def)==null ) def=null; } - if( useSplit != null ) { - short bias = biasColorNeighbors( alloc, useSplit, mask ); + if( use != null ) { + short bias = biasColorNeighbors( alloc, use, mask ); if( bias >= 0 ) return bias; - useSplit = useSplit.out(0); + use = use.out(0); + if( biasable(use)==0 ) use=null; } } @@ -484,7 +508,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 ) 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 MachNode mach) ) return 0; // Not biasable return mach.twoAddress(); // Only biasable if 2-addr } @@ -509,7 +533,7 @@ abstract public class IFG { // Can I limit my own choices to valid neighbor choices? for( LRG alrg : slrg._adj ) { - int reg = alrg._reg; + short reg = alrg._reg; if( reg == -1 && alrg._mask.size1() ) reg = alrg._mask.firstReg(); if( reg != -1 ) { 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 4162bece..56b5aa52 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java @@ -332,7 +332,8 @@ public class RegAlloc { // Phi or two-address for( int i=0; i<def._outputs._len; i++ ) { Node use = def.out(i); - if( (use instanceof PhiNode phi && !(phi.region() instanceof LoopNode && phi.in(2)==def ) ) || + if( (use instanceof PhiNode phi && + !(phi.region() instanceof LoopNode loop && phi.in(2)==def && def.cfg0().idepth() > loop.idepth() ) ) || (use instanceof MachNode mach && mach.twoAddress()!=0 && use.in(mach.twoAddress())==def) ) insertBefore( use, use._inputs.find(def), "use/self/use",round,lrg ); } @@ -606,6 +607,7 @@ public class RegAlloc { for( int idx = cfg._outputs.find(split) -1; idx >= 0; idx-- ) { 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 ) return false; // Clobbered } diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/SetARM.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/SetARM.java index a78312fa..52f448df 100644 --- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/SetARM.java +++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/arm/SetARM.java @@ -20,7 +20,7 @@ public class SetARM extends MachConcreteNode implements MachNode { @Override public RegMask outregmap() { return arm.RMASK; } @Override public void encoding( Encoding enc ) { - int body = arm.cset(arm.OP_CSET,0b11111, arm.make_condition(_bop), 0b0111111, enc.reg(this)); + int body = arm.cset(arm.OP_CSET,0b11111, arm.make_condition(_bop), 0b011111, enc.reg(this)); enc.add4(body); } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java index b83db0d1..81000f9e 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -75,7 +75,7 @@ return sqrt(arg) + sqrt(arg+2); public void testNewtonFloat() throws IOException { String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp")) + "flt farg = arg; return sqrt(farg) + sqrt(farg+2.0);"; - testCPU(src,"x86_64_v2", "SystemV",25,null); + testCPU(src,"x86_64_v2", "SystemV",39,null); testCPU(src,"riscv" , "SystemV",17,null); testCPU(src,"arm" , "SystemV",18,null); } diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 617284ca..e726ada3 100644 --- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -48,7 +48,7 @@ public class Chapter21Test { public void testNewtonFloat() throws IOException { String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp")) + "flt farg = arg; return sqrt(farg) + sqrt(farg+2.0);"; - testCPU(src,"x86_64_v2", "SystemV",23,null); + testCPU(src,"x86_64_v2", "SystemV",39,null); testCPU(src,"riscv" , "SystemV",18,null); testCPU(src,"arm" , "SystemV",19,null); } |