Bug Fix RegAlloc

RA, self-conflict around backedge of loop predates loop, must still split.  Eager splitting here leads to bad allocations, but never splitting is broken.
Move building adj lists into IFG from Coalesce.
testNewtonFloat not so fragile.
Hack around bug SetArm

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);
     }