Forward-port allocator bug fixes and test support through ch25

Improved spilling

4 files changed, 25 insertions, 21 deletions

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