Popular use grouping for RegAlloc

Fix arm BL encodings; ADD/SUB with reversed sign.

4 files changed, 40 insertions, 54 deletions

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 4a880a19..196a1142 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/RegAlloc.java
@@ -344,56 +344,40 @@ public class RegAlloc {
         return true;
     }
 
-    // Single-def live range with an empty mask.  There are many single-reg
-    // uses.  Theory is there's many repeats of the same reg amongst the uses.
-    // In of splitting once per use, start by splitting into groups based on
-    // required input register.
+    // Popular single-def value: share a split among uses with compatible masks.
     boolean splitEmptyMaskByUse( byte round, LRG lrg ) {
         Node def = (Node)lrg._machDef;
+        // Snapshot distinct users: rewriting an input changes def's output list,
+        // and a call can use the same value in more than one argument.
+        Ary<Node> uses = new Ary<>(Node.class);
+        for( Node use : def._outputs )
+            if( uses.find(use)==-1 ) uses.push(use);
 
-        // Look at each use, and break into non-overlapping register classes.
         Ary<RegMask> rclass = new Ary<>(RegMask.class);
-        boolean done=false;
         int ncalls=0;
-        while( !done ) {
-            done = true;
-            for( Node use : def._outputs )
-                if( use instanceof MachNode mach ) {
-                    if( mach instanceof CallNode ) ncalls++;
-                    for( int i=1; i<use.nIns(); i++ )
-                        if( use.in(i)==def )
-                            done = putIntoRegClass( rclass, mach.regmap(i) );
-                }
-        }
-
-        // See how many register classes we split into.  Generally not
-        // productive to split like this across calls, which are going to kill
-        // all registers anyways.
-        if( rclass._len <= 1 || ncalls > 1 ) return false;
+        for( Node use : uses )
+            if( use instanceof MachNode mach ) {
+                // Sharing copies across several calls usually loses to their kills.
+                if( use instanceof CallNode && ++ncalls > 1 ) return false;
+                for( int i=1; i<use.nIns(); i++ )
+                    if( use.in(i)==def && mach.regmap(i)!=null )
+                        putIntoRegClass(rclass,mach.regmap(i));
+            }
+        if( rclass._len <= 1 ) return false;
 
-        // Split by class
-        Ary<Node> ns = new Ary<>(Node.class);
         for( RegMask rmask : rclass ) {
-            ns.addAll(def._outputs);
             Node split = makeSplit(def,"popular",round,lrg,rmask);
-            split.insertAfter( def );
+            split.insertAfter(def);
             if( split.nIns()>1 ) split.setDef(1,def);
-            // all uses by class to split
-            for( int j=0; j < def._outputs._len; j++ ) {
-                Node use = def._outputs.at(j);
-                if( use instanceof MachNode mach && use!=split ) {
-                    // Check all use inputs for n, in case there's several
-                    for( int i = 1; i < use.nIns(); i++ )
-                        // Find a def input, and check register class
-                        if( use.in( i ) == def && mach.regmap( i ).overlap( rmask ) ) {
-                            RegMask m = mach.regmap( i );
-                            if( m!=null && mach.regmap( i ).overlap( rmask ) )
-                                // Modify use to use the split version specialized to this rclass
-                                { use.setDefOrdered( i, split ); j--; break; }
+            for( Node use : uses )
+                if( use instanceof MachNode mach )
+                    for( int i=1; i<use.nIns(); i++ ) {
+                        RegMask mask = mach.regmap(i);
+                        if( use.in(i)==def && mask!=null && mask.overlap(rmask) ) {
+                            assert rmask.and(mask)==rmask;
+                            use.setDefOrdered(i,split);
                         }
-                }
-            }
-            ns.clear();
+                    }
         }
         return true;
     }
@@ -419,22 +403,20 @@ public class RegAlloc {
         return progress;
     }
 
-    // Put use into a register class, perhaps adding a class or perhaps
-    // narrowing a class (and causing a repeat)
-    private static boolean putIntoRegClass( Ary<RegMask> rclass, RegMask rmask ) {
+    // Narrowing preserves all earlier users of a class; new classes are disjoint.
+    // Each use contains its first overlapping class, so one pass suffices.
+    private static void putIntoRegClass( Ary<RegMask> rclass, RegMask rmask ) {
         for( int i=0; i<rclass._len; i++ ) {
             RegMask omask = rclass.at(i);
-            if( omask.and(rmask) == omask ) return true; // Within the same register class
-            if( omask.overlap(rmask) ) {
+            if( !omask.overlap(rmask) ) continue;
+            if( omask.and(rmask)!=omask )
                 rclass.set(i,new RegMask(omask.copy().and(rmask)));
-                return false;   // Need go again
-            }
+            return;
         }
-        // Add a new class, no need to go again
         rclass.push(rmask);
-        return true;
     }
 
+
     // Self conflicts require Phis (or two-address).
     // Insert a split after every def.
     boolean splitSelfConflict( byte round, LRG lrg ) {
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/FunARM.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/FunARM.java
index 44a417f9..b9e85202 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/FunARM.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/FunARM.java
@@ -10,13 +10,12 @@ public class FunARM  extends FunNode implements MachNode {
     FunARM(FunNode fun) { super(fun); }
     @Override public void computeFrameAdjust(CodeGen code, int maxReg) {
         super.computeFrameAdjust(code,maxReg);
-        if( _hasCalls )         // If non-leaf, pad to 16b
-            _frameAdjust = ((_frameAdjust+8) & -16);
+        _frameAdjust = (_frameAdjust+15) & -16; // Keep SP aligned, including leaf spills.
     }
     @Override public void encoding( Encoding enc ) {
         int sz = _frameAdjust;
         if( sz == 0 ) return;   // Skip if no frame adjust
         if( sz >= 1L<<12 ) throw Utils.TODO();
-        enc.add4(arm.imm_inst(arm.OPI_ADD, -sz&0xFFF, arm.RSP, arm.RSP));
+        enc.add4(arm.imm_inst(arm.OPI_SUB, sz, arm.RSP, arm.RSP));
     }
 }
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/RetARM.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/RetARM.java
index 2136ebf5..4597666b 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/RetARM.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/RetARM.java
@@ -9,7 +9,7 @@ public class RetARM extends ReturnNode implements MachNode {
     @Override public void encoding( Encoding enc ) {
         int frameAdjust = ((FunARM)fun())._frameAdjust;
         if( frameAdjust > 0 )
-            enc.add4(arm.imm_inst(arm.OPI_ADD, (frameAdjust*-8)&0xFFF, arm.RSP, arm.RSP));
+            enc.add4(arm.imm_inst(arm.OPI_ADD, frameAdjust, arm.RSP, arm.RSP));
         enc.add4(arm.ret(arm.OP_RET));
     }
 }
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java
index 20343fb4..510d5e78 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java
@@ -319,6 +319,11 @@ public class arm extends Machine {
         short self = enc.reg(n);
         short reg1 = enc.reg(n2);
 
+        // ADD/SUB encode an unsigned magnitude; switch operation for a negative addend.
+        if( imm12<0 && (opcode==OPI_ADD || opcode==OPI_SUB) ) {
+            opcode ^= OPI_ADD ^ OPI_SUB;
+            imm12 = -imm12;
+        }
         int body = imm_inst(opcode, imm12&0xFFF, reg1, self);
         enc.add4(body);
     }
@@ -429,7 +434,7 @@ public class arm extends Machine {
     }
 
     public static int ret(int opcode) {
-        return (opcode << 10);
+        return (opcode << 10) | (X30 << 5);
     }
 
     // FMOV (scalar, immediate)