Ch 20 Reg Alloc

Includes all bug fixes from later chapters, so its at least correct.
Skips a lot of improvement heuristics, these get added in later chapters.
Includes spill-stats, to more easily track improvements.
Includes targeted tests.

6 files changed, 40 insertions, 61 deletions

diff --git a/chapter20/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java
index 88b49863..2bd64c50 100644
--- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java
+++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/BuildLRG.java
@@ -41,8 +41,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();
                     }
 
@@ -56,7 +56,7 @@ abstract public class BuildLRG {
                             LRG lrg2 = alloc.lrg(n.in(i));
                             if( lrg2 != null ) { // Anti-dep or other, no LRG
                                 RegMask use_mask = mach.regmap(i);
-                                if( !lrg2.machUse(mach,(short)i,use_mask.size1()).and(use_mask) )
+                                if( use_mask!=null && !lrg2.machUse(mach,(short)i,use_mask.size1()).and(use_mask) )
                                     alloc.fail(lrg2); // Empty register mask, must split
                             }
                         }
@@ -64,7 +64,7 @@ abstract public class BuildLRG {
                 }
 
                 // MultiNodes have projections which set registers
-                if( n instanceof MultiNode )
+                if( n instanceof MultiNode && !(n instanceof CFGNode) )
                     for( Node proj : n.outs() )
                         if( proj instanceof MachNode )
                             defLRG(alloc,proj);
diff --git a/chapter20/src/main/java/com/seaofnodes/simple/codegen/IFG.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/IFG.java
index 1f3186ff..acfec53f 100644
--- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/IFG.java
+++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/IFG.java
@@ -127,16 +127,11 @@ abstract public class IFG {
 
         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
+        // Instructions can clobber registers without defining an LRG.
+        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,9 +143,9 @@ 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()) )
-                        alloc.fail(tlrg);
-                    else addIFG(lrg,tlrg); // Add interference
+                    if( ((MachNode)n).outregmap().size1() ) {
+                        if( !tlrg.clr(lrg._mask.firstReg()) ) alloc.fail(tlrg);
+                    } else addIFG(lrg,tlrg); // Add interference
             }
         }
 
@@ -171,7 +166,7 @@ abstract public class IFG {
             // Look for a must-use single register conflicting with some other must-def.
             if( n instanceof MachNode m ) {
                 RegMask ni_mask = m.regmap(i);
-                if( ni_mask.size1() ) { // Must-use single register
+                if( ni_mask!=null && ni_mask.size1() ) { // Must-use single register
                     // Search all current live
                     for( LRG tlrg : TMP.keySet() ) {
                         assert tlrg.leader();
@@ -204,15 +199,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.
-                if( m.isClone() )
-                    alloc.fail(alloc.lrg((Node)m));
-                else if( !tlrg.sub(killMask) ) {
-                    tlrg._killed = true; // Failed by a kill-mask
-                    alloc.fail(tlrg);
-                }
+                if( !tlrg.sub(killMask) ) alloc.fail(tlrg);
             }
         }
     }
@@ -234,7 +221,7 @@ abstract public class IFG {
     private static void mergeLiveOut( RegAlloc alloc, CFGNode priorbb, int i ) {
         CFGNode bb = priorbb.cfg(i);
         if( bb == null ) return; // Start has no prior
-        if( !bb.blockHead() ) bb = bb.cfg0();
+        while( !bb.blockHead() ) bb = bb.cfg0();
         //if( i==0 && !(bb instanceof StartNode) ) bb = bb.cfg0();
         assert bb.blockHead();
 
diff --git a/chapter20/src/main/java/com/seaofnodes/simple/codegen/LRG.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/LRG.java
index 394c4a01..5803cad8 100644
--- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/LRG.java
+++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/LRG.java
@@ -42,11 +42,6 @@ public class LRG {
     public MachNode _machDef, _machUse;
     short _uidx;                // _machUse input
 
-    // Mask set to empty via a kill-mask.  This is usually a capacity kill,
-    // which means we need to split and spill into memory - which means even if
-    // the def-side has many registers, it MUST spill.
-    boolean _killed;
-
     // Some splits used in biased coloring
     MachConcreteNode _splitDef, _splitUse;
 
@@ -130,9 +125,12 @@ public class LRG {
 
         if( _machUse==null ) {
             _machUse = lrg._machUse;
+            _uidx = lrg._uidx;
         } else if( lrg._machUse!=null ) {
-            if( _1regUseCnt==0 )
+            if( _1regUseCnt==0 ) {
                 _machUse = lrg._machUse;
+                _uidx = lrg._uidx;
+            }
             else if( _machUse==lrg._machUse )
                 _1regUseCnt--;
         }
@@ -143,7 +141,8 @@ public class LRG {
         _splitUse = deepSplit(_splitUse,lrg._splitUse);
 
         // Fold together masks
-        _mask = _mask.and(lrg._mask);
+        RegMask mask = _mask.and(lrg._mask);
+        _mask = mask==null ? _mask.copy().and(lrg._mask) : mask;
         return this;
     }
 
diff --git a/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegMask.java b/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegMask.java
index f28805b5..5227c11e 100644
--- a/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegMask.java
+++ b/chapter20/src/main/java/com/seaofnodes/simple/codegen/RegMask.java
@@ -28,7 +28,7 @@ public class RegMask {
 
     public RegMask(int bit) {
         if( bit < 64 ) _bits0 = 1L<<bit;
-        else _bits1 = 1L<<(bit=64);
+        else _bits1 = 1L<<(bit-64);
     }
     public RegMask(long bits ) { _bits0 = bits; }
     public RegMask(long bits0, long bits1 ) { _bits0 = bits0; _bits1 = bits1; }
@@ -65,21 +65,18 @@ public class RegMask {
 
 
     public short firstReg() {
+        if( isEmpty() ) return -1;
         return (short)(_bits0 != 0
                        ? Long.numberOfTrailingZeros(_bits0)
                        : 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; }
@@ -96,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
diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter20/src/main/java/com/seaofnodes/simple/node/Node.java
index 55ffe378..f7cb1672 100644
--- a/chapter20/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter20/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -297,9 +297,8 @@ public abstract class Node implements Cloneable {
         kill();
     }
 
-    // Replace uses of `def` with `this`, and insert `this` immediately after
-    // `def` in the basic block.
-    public void insertAfter( Node def, boolean must ) {
+    // insert `this` immediately after `def` in the same basic block.
+    public void insertAfter( Node def ) {
         CFGNode cfg = def.cfg0();
         int i = cfg._outputs.find(def)+1;
         if( cfg instanceof CallEndNode ) {
@@ -312,19 +311,6 @@ public abstract class Node implements Cloneable {
         while( cfg.out(i) instanceof PhiNode || cfg.out(i) instanceof CalleeSaveNode )  i++;
         cfg._outputs.insert(this,i);
         _inputs.set(0,cfg);
-        for( int j=def.nOuts()-1; j>=0; j-- ) {
-            // Can we avoid a split of a split?  'this' split is used by
-            // another split in the same block.
-            if( !must && def.out(j) instanceof SplitNode split && def.out(j).cfg0()==cfg &&
-                !split._kind.contains("self") )
-                continue;
-            Node use = def._outputs.del(j);
-            use.unlock();
-            int idx = use._inputs.find(def);
-            use._inputs.set(idx,this);
-            addUse(use);
-        }
-        if( nIns()>1 ) setDef(1,def);
     }
 
     // Insert this in front of use.in(uidx) with this, and insert this
@@ -358,6 +344,13 @@ public abstract class Node implements Cloneable {
         setDef(idx,def);
     }
 
+    public void killOrdered() {
+        CFGNode cfg = cfg0();
+        cfg._outputs.remove(cfg._outputs.find(this));
+        _inputs.set(0,null);
+        kill();
+    }
+
     public void removeSplit() {
         CFGNode cfg = cfg0();
         cfg._outputs.remove(cfg._outputs.find(this));
diff --git a/chapter20/src/main/java/com/seaofnodes/simple/node/SplitNode.java b/chapter20/src/main/java/com/seaofnodes/simple/node/SplitNode.java
index 22cb9bb9..37d1a63d 100644
--- a/chapter20/src/main/java/com/seaofnodes/simple/node/SplitNode.java
+++ b/chapter20/src/main/java/com/seaofnodes/simple/node/SplitNode.java
@@ -11,7 +11,10 @@ public abstract class SplitNode extends MachConcreteNode {
     public SplitNode(String kind, byte round, Node[] nodes) { super(nodes); _kind = kind; _round = round; }
     @Override public String op() { return "mov"; }
     @Override public StringBuilder _print1(StringBuilder sb, BitSet visited) {
-        return in(1)._print0(sb.append("mov("),visited).append(")");
+        sb.append("mov(");
+        if( in(1)==null ) sb.append("---");
+        else in(1)._print0(sb,visited);
+        return sb.append(")");
     }
     @Override public Type compute() { return in(0)._type; }
     @Override public Node idealize() { return null; }