Popular use grouping for RegAlloc

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

2 files changed, 103 insertions, 13 deletions

diff --git a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java
index 20d94f92..5e86d21c 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/Chapter21Test.java
@@ -11,6 +11,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/chapter21/src/test/java/com/seaofnodes/simple/EvalArm64.java b/chapter21/src/test/java/com/seaofnodes/simple/EvalArm64.java
index 99807345..66772060 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/EvalArm64.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/EvalArm64.java
@@ -97,18 +97,15 @@ public class EvalArm64 {
                     continue ;
                 }
                 case 0x25: {
-                    // bl (just calloc)
+                    // BL, including ordinary calls
                     rval = pc + 4;
                     regs[arm.X30] = rval;
-                    if(pc + 4 == 0) {
-                        regs[rdid] = rval;
-                        break outer;
-                    }
                     int imm26 = (ir & 0x03FFFFFF);
                     int imm = (imm26 << 6) >> 6;
                     pc = pc + (imm << 2) ;
                     if (pc == SENTINEL_CALLOC) {
                         long size = regs[arm.X0]*regs[arm.X1];
+                        size = (size+7) & -8;
                         regs[arm.X0] = _heap;
                         _heap += (int)size;
                         // unwind pc
@@ -637,12 +634,11 @@ public class EvalArm64 {
                     rval = opcode1==0x8B ? lhs + rhs : lhs - rhs;
                     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 0xD3: {
@@ -674,10 +670,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;
-                    if(ld4s(pc + 4) == 0) {
-                        break outer;
-                    }
+                    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;
                 }
                 // bitwise
                 case 0x8A: {