Popular use grouping for RegAlloc

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

5 files changed, 111 insertions, 13 deletions

diff --git a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/FunARM.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/FunARM.java
index 32777f03..3ee75608 100644
--- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/FunARM.java
+++ b/chapter22/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/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/RetARM.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/RetARM.java
index 2136ebf5..4597666b 100644
--- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/RetARM.java
+++ b/chapter22/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/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java
index e6f64158..b619899a 100644
--- a/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java
+++ b/chapter22/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java
@@ -317,6 +317,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);
     }
@@ -427,7 +432,7 @@ public class arm extends Machine {
     }
 
     public static int ret(int opcode) {
-        return (opcode << 10);
+        return (opcode << 10) | (X30 << 5);
     }
 
     // FMOV (scalar, immediate)
diff --git a/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java
index 72f79d6c..85e92bd8 100644
--- a/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java
+++ b/chapter22/src/test/java/com/seaofnodes/simple/Chapter21Test.java
@@ -12,6 +12,94 @@ import org.junit.Test;
 import static org.junit.Assert.*;
 
 public class Chapter21Test {
+    @Test public void testArmCallInstructions() {
+        EvalArm64 cpu = new EvalArm64(new byte[512],256);
+        for( int delta : new int[]{4,32,-4} ) {
+            cpu._pc = 128;
+            for( int i=0; i<32; i++ ) cpu.regs[i]=1000+i;
+            cpu.st4(128,0x94000000 | ((delta>>2)&0x03FFFFFF)); // BL
+            assertEquals(0,cpu.step(1));
+            assertEquals(128+delta,cpu._pc);
+            for( int i=0; i<32; i++ ) assertEquals(i==30 ? 132 : 1000+i,cpu.regs[i]);
+        }
+        for( int rn : new int[]{9,30} )
+            for( boolean call : new boolean[]{false,true} ) {
+                cpu._pc=4;
+                cpu.regs[rn]=64;
+                cpu.st4(4,(call ? 0xD63F0000 : 0xD65F0000) | (rn<<5)); // BLR / RET
+                assertEquals(0,cpu.step(1));
+                assertEquals(64,cpu._pc);
+                if( call ) assertEquals(8,cpu.regs[30]);
+            }
+    }
+
+    @Test public void testArmImmediateArithmetic() {
+        EvalArm64 cpu = new EvalArm64(new byte[16],16);
+        // Unsigned imm12, including bit 11 and the optional 12-bit shift.
+        for( int[] test : new int[][]{{0x91200020,2148},{0xD1200020,-1948},
+                                     {0x91400420,4196},{0xD1400420,-3996}} ) {
+            cpu._pc=0; cpu.regs[1]=100;
+            cpu.N=true; cpu.Z=false; cpu.C=true; cpu.V=true;
+            cpu.st4(0,test[0]);
+            assertEquals(0,cpu.step(1));
+            assertEquals(test[1],cpu.regs[0]);
+            assertTrue(cpu.N); assertFalse(cpu.Z); assertTrue(cpu.C); assertTrue(cpu.V);
+        }
+    }
+
+    @Test public void testArmCallsAndFrames() throws IOException {
+        String src = """
+            val sum = { int n ->
+                if( n<=0 ) return 1;
+                return sum(n-1)+n;
+            };
+            val run = { int n -> return sum(n)+sum(n+1); };
+            """;
+        assertTrue("Ordinary calls must survive optimization",checkArmCalls(src,"run",4,27)>0);
+    }
+
+    private static int checkArmCalls(String src, String entryName, int arg, int result) throws IOException {
+        CodeGen code = new CodeGen(src).driver("arm","SystemV",null);
+        byte[] image = new byte[1<<20];
+        System.arraycopy(code._encoding.bits(),0,image,0,code._encoding.bits().length);
+        EvalArm64 cpu = new EvalArm64(image,1<<16);
+        boolean entry=false;
+        int frames=0, calls=0;
+        for( var bb : code._cfg ) {
+            if( bb instanceof com.seaofnodes.simple.node.FunNode fun ) {
+                int off = code._encoding._opStart[fun._nid];
+                if( entryName.equals(fun._name) ) { cpu._pc=off; entry=true; }
+                int frame=fun._frameAdjust;
+                assertEquals(0,frame&15);
+                if( frame>0 ) {
+                    frames++;
+                    assertEquals(0xD10003FF | (frame<<10),cpu.ld4s(off)); // SUB SP,SP,#bytes
+                }
+            }
+            if( bb instanceof com.seaofnodes.simple.node.ReturnNode ret ) {
+                int off=code._encoding._opStart[ret._nid];
+                int frame=ret.fun()._frameAdjust;
+                if( frame>0 ) {
+                    assertEquals(0x910003FF | (frame<<10),cpu.ld4s(off)); // ADD SP,SP,#bytes
+                    off+=4;
+                }
+                assertEquals(0xD65F03C0,cpu.ld4s(off)); // RET X30
+            }
+            if( bb instanceof com.seaofnodes.simple.node.cpus.arm.CallARM ) calls++;
+        }
+        assertTrue("Must execute the program entry",entry);
+        assertTrue("Exercise stack frames",frames>0);
+        for( int i=19; i<=29; i++ ) cpu.regs[i]=1000+i;
+        cpu.regs[0]=arg;
+        assertEquals(0,cpu.step(10000));
+        assertEquals("Must return to the harness",0,cpu._pc);
+        assertEquals(result,cpu.regs[0]);
+        assertEquals(1<<16,cpu.regs[31]);
+        for( int i=19; i<=29; i++ ) assertEquals(1000+i,cpu.regs[i]);
+        return calls;
+    }
+
+
     @Test public void testArmSubtractRegisters() {
         EvalArm64 cpu = new EvalArm64(new byte[16],16);
         cpu.st4(0,0xCB020020); // SUB X0,X1,X2, no shift or flag update.
diff --git a/chapter22/src/test/java/com/seaofnodes/simple/EvalArm64.java b/chapter22/src/test/java/com/seaofnodes/simple/EvalArm64.java
index 42f225fa..b9c5e415 100644
--- a/chapter22/src/test/java/com/seaofnodes/simple/EvalArm64.java
+++ b/chapter22/src/test/java/com/seaofnodes/simple/EvalArm64.java
@@ -306,11 +306,11 @@ public class EvalArm64 {
                 break;
             }
 
-            case 0x91: {  // add(immediate)
+            case 0x91, 0xD1: { // ADD/SUB (immediate), unsigned imm12, optional LSL #12
                 int rn = (ir >> 5) & 0x1F;
-                int immediate = ir << 10 >> 20;
-                // only hit it twice
-                rval = regs[rn] + immediate;
+                long immediate = (ir >>> 10) & 0xFFF;
+                if( (ir & (1<<22))!=0 ) immediate <<= 12;
+                rval = opcode1==0x91 ? regs[rn] + immediate : regs[rn] - immediate;
                 break;
             }
             case 0x92: {        // and(immediate)
@@ -329,6 +329,7 @@ public class EvalArm64 {
             }
 
             case 0x94, 0x95, 0x96, 0x97: { // bl
+                rdid = -1; // BL writes only X30, not a displacement-selected register.
                 rval = pc + 4;
                 regs[arm.X30] = rval;
                 int imm26 = (ir & 0x03FFFFFF);
@@ -572,11 +573,16 @@ public class EvalArm64 {
                 break;
             }
             case 0xD6: {
+                int op = ir & 0xFFFFFC1F;
+                int rn = (ir >>> 5) & 31;
+                int target = (int)regs[rn]; // Read before BLR overwrites X30.
                 rdid = -1;
-                // Return to zero breaks simulation
-                if(regs[30] == 0)
-                    break outer;
-                throw Utils.TODO();
+                if( op==0xD63F0000 ) regs[arm.X30] = pc+4; // BLR
+                else if( op!=0xD65F0000 ) { trap = 3; break; } // RET
+                pc = target;
+                if( op==0xD65F0000 && pc==0 ) break outer;
+                pc -= 4;
+                break;
             }
 
             case 0xF1: {