More RegAlloc

Forcing kills on allocations broke a bunch of things.
Color: pickRisky single-Def cloneables that are not next to their uses.  I.e., a X86 flags-producer far away from a required jump:
Pick as Risky, fail to color, and spill (clone) next to jump.
Remove a bunch of premature split fold-thrus

4 files changed, 46 insertions, 22 deletions

diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
index 8788d109..1a148910 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java
@@ -48,7 +48,6 @@ public class CodeGen {
         P = new Parser(this,arg);
     }
 
-
     // ---------------------------
     /**
      *  A counter, for unique node id generation.  Starting with value 1, to
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 729ec88e..df5976a4 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/IFG.java
@@ -125,18 +125,18 @@ abstract public class IFG {
             TMP.remove(lrg);    // Kill def
         }
 
+        // Phis use and define the same live range, i.e. these LRGs already
+        // marked conflicted, no need to mark again
         if( n instanceof PhiNode )
             return;
-        // A copy does not define a new value, and the src and dst can use the
-        // same register.  Remove the input from TMP/liveout set before
-        // interfering.
-        //if( n instanceof MachNode m && m.isSplit() )
-        //    TMP.remove(alloc.lrg(n.in(1))); // Kill spill-use
+
+        // Kill any killed registers; milli-code routines like New can kill
+        // will not being a CFG.
+        if( n instanceof MachNode m )
+            kills(alloc,m);
 
         // Interfere n with all live
         if( lrg!=null ) {
-            if( n instanceof MachNode m )
-                kills(alloc,m);
             // Interfere n with all live
             for( LRG tlrg : TMP.keySet() ) {
                 assert tlrg.leader();
@@ -148,7 +148,7 @@ abstract public class IFG {
                     // last tlrg register at some point, either tlrg or lrg
                     // must fail.  If *n* (a subset of lrg) needs the single
                     // last tlrg register then only tlrg must fail.
-                    if( lrg.size1() && !tlrg.clr(lrg._mask.firstReg()) )
+                    if( ((MachNode)n).outregmap().size1() && !tlrg.clr(lrg._mask.firstReg()) )
                         alloc.fail(tlrg);
                     else addIFG(lrg,tlrg); // Add interference
             }
@@ -412,7 +412,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 == 999999 ) return best; // Already max score
+            if( bestScore == 1000000 ) return best; // Already max score
             int iScore = pickRiskyScore(color_stack[i]);
             if( iScore > bestScore )
                 { best = i; bestScore = iScore; }
@@ -429,13 +429,24 @@ 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
+        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 999998;
+            return 1000000-2;
         if( lrg._splitDef != null && lrg._splitDef.in(1) instanceof CalleeSaveNode &&
             lrg._splitUse != null && lrg._splitUse.out(0) instanceof ReturnNode )
-            return 999999;
+            return 1000000-1;
 
         // TODO: cost/benefit model.  Perhaps counting loop-depth (freq) of def/use for cost
         // and "area" for benefit
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/codegen/LRG.java b/chapter21/src/main/java/com/seaofnodes/simple/codegen/LRG.java
index 394c4a01..d44dffb8 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/LRG.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/LRG.java
@@ -37,6 +37,8 @@ public class LRG {
 
     // Count of single-register defs and uses
     short _1regDefCnt, _1regUseCnt;
+    // Count of all defs, uses.  Mostly interested 1 vs many
+    boolean _multiDef, _multiUse;
 
     // A sample MachNode def in the live range
     public MachNode _machDef, _machUse;
@@ -121,22 +123,28 @@ public class LRG {
         if( _machDef==null ) {
             _machDef = lrg._machDef;
         } else if( lrg._machDef!=null ) {
+            if( _machDef != lrg._machDef ) _multiDef=true;
             if( _1regDefCnt==0 )
                 _machDef = lrg._machDef;
             else if( _machDef==lrg._machDef )
                 _1regDefCnt--;
         }
         _1regDefCnt += lrg._1regDefCnt;
+        _multiDef |= lrg._multiDef;
 
         if( _machUse==null ) {
             _machUse = lrg._machUse;
         } else if( lrg._machUse!=null ) {
-            if( _1regUseCnt==0 )
+            if( _machUse != lrg._machUse ) _multiUse=true;
+            if( _1regUseCnt==0 ) {
                 _machUse = lrg._machUse;
+                _uidx = lrg._uidx;
+            }
             else if( _machUse==lrg._machUse )
                 _1regUseCnt--;
         }
         _1regUseCnt += lrg._1regUseCnt;
+        _multiUse |= lrg._multiUse;
 
         // Fold deepest Split
         _splitDef = deepSplit(_splitDef,lrg._splitDef);
@@ -153,6 +161,8 @@ public class LRG {
 
     // Record any Mach def for spilling heuristics
     LRG machDef( MachNode def, boolean size1 ) {
+        if( _machDef!=null && _machDef!=def )
+            _multiDef = true;
         if( _machDef==null || size1 )
             _machDef = def;
         if( size1 )
@@ -164,6 +174,8 @@ public class LRG {
 
     // Record any Mach use for spilling heuristics
     LRG machUse( MachNode use, short uidx, boolean size1 ) {
+        if( _machUse!=null && _machUse!=use )
+            _multiUse = true;
         if( _machUse==null || size1 )
             { _machUse = use; _uidx = uidx; }
         if( size1 )
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 f323ea22..ebcf614d 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
@@ -213,7 +213,7 @@ public class RegAlloc {
 
         // Register mask when empty; split around defs and uses with limited
         // register masks.
-        if( lrg._mask.isEmpty() ) {
+        if( lrg._mask.isEmpty() && (!lrg._multiDef || lrg._1regUseCnt==1) ) {
             if( lrg._1regDefCnt <= 1 &&
                 lrg._1regUseCnt <= 1 &&
                 (lrg._1regDefCnt + lrg._1regUseCnt) > 0 )
@@ -244,8 +244,8 @@ public class RegAlloc {
             //   st4 [V1],len - No good, must split around
             makeSplit("def/empty1",round,lrg).insertAfter((Node)lrg._machDef, false/*true*/);
         // Split just before use
-        if( lrg._1regUseCnt==1 )
-            insertBefore((Node)lrg._machUse,lrg._uidx,"use/empty1",round,lrg,false);
+        if( lrg._1regUseCnt==1 || (lrg._1regDefCnt==1 && ((Node)lrg._machDef).nOuts()==1) )
+            insertBefore((Node)lrg._machUse,lrg._uidx,"use/empty1",round,lrg,true);
         return true;
     }
 
@@ -376,13 +376,15 @@ public class RegAlloc {
             } else {
                 // Others check uses
                 for( int i=1; i<n.nIns(); i++ ) {
-                    if( lrgSame(n.in(i),lrg) && // This is a LRG use
-                        // splitting in inner loop or at loop border
-                        (min==max || n.cfg0().loopDepth() <= min) &&
+                    boolean sizeN=false;
+                    // This is a LRG use
+                    // splitting in inner loop or at loop border
+                    if( lrgSame( n.in( i ), lrg ) &&
+                        (min == max || (n.in(i) instanceof MachNode mach && mach.isClone()) || n.cfg0().loopDepth() <= min) )
                         // Not a single-use split same block already
-                        !(n.in(i) instanceof SplitNode && n.in(i).nOuts()==1 && n.cfg0()==n.in(i).cfg0()) )
+                        //!(n.in(i) instanceof SplitNode && n.in(i).nOuts()==1 && n.cfg0()==n.in(i).cfg0() && (sizeN=!((MachNode)n).regmap(i).size1())) )
                         // Split before in this block
-                        insertBefore( n, i, "use/loop/use", round,lrg );
+                        insertBefore( n, i, "use/loop/use", round,lrg, sizeN );
                 }
             }
         }
@@ -433,7 +435,7 @@ public class RegAlloc {
         // Effective block for use
         CFGNode cfg = n instanceof PhiNode phi ? phi.region().cfg(i) : n.cfg0();
         // Def is a split ?
-        if( def instanceof SplitNode ) {
+        if( skip && def instanceof SplitNode ) {
             boolean singleReg = n instanceof MachNode mach && mach.regmap(i).size1();
             // Same block, multiple registers, split is only used by n,
             // assume this is good enough and do not split again.