Fix CmpIX86/Jmp swap args bug

Some x86 cmp need to swap args, then Set/Jmp both need to swap `bop`.
Fix missing padding in ASM printer.
MergeSort test like brainfuck - runs on arm.

10 files changed, 135 insertions, 108 deletions

diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpIX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpIX86.java
index d274875a..91b6d43c 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpIX86.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpIX86.java
@@ -7,9 +7,9 @@ import com.seaofnodes.simple.node.*;
 // Compare immediate.  Sets flags.
 public class CmpIX86 extends MachConcreteNode implements MachNode {
     final int _imm;
-    CmpIX86( Node cmp, int imm ) {
+    CmpIX86( Node cmp, int imm, boolean swap ) {
         super(cmp);
-        _inputs.pop();
+        _inputs.del(swap ? 1 : 2);
         _imm = imm;
     }
     CmpIX86( CmpIX86 cmp ) {
@@ -18,11 +18,6 @@ public class CmpIX86 extends MachConcreteNode implements MachNode {
         addDef(cmp.in(1));
         _imm = cmp._imm;
     }
-    CmpIX86( Node lhs, int imm, double ignore ) {
-        super(lhs);
-        _inputs.del(1);
-        _imm = imm;
-    }
 
     @Override public String op() { return _imm==0 ? "test" : "cmp"; }
     @Override public RegMask regmap(int i) { return x86_64_v2.RMASK; }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java
index f9cd597b..489853eb 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/CmpMemX86.java
@@ -7,10 +7,11 @@ import com.seaofnodes.simple.type.Type;
 import com.seaofnodes.simple.type.TypeFloat;
 
 public class CmpMemX86 extends MemOpX86 {
-    final boolean _invert;      // Op switched LHS, RHS
-    CmpMemX86( BoolNode bool, LoadNode ld, Node base, Node idx, int off, int scale, int imm, Node val, boolean invert ) {
+    final boolean _swap;      // Op switched LHS, RHS
+    CmpMemX86( BoolNode bool, LoadNode ld, Node base, Node idx, int off, int scale, int imm, Node val, boolean swap ) {
         super(bool,ld, base, idx, off, scale, imm, val );
-        _invert = invert;
+        _swap = swap;
+        assert !_swap || val() == null || bool.op()=="==" || bool.op()=="!="; // Cannot swap with immediate
     }
     @Override public String op() { return ((val()==null && _imm==0) ? "test" : "cmp") + _sz; }
     @Override public RegMask outregmap() { return x86_64_v2.FLAGS_MASK; }
@@ -23,52 +24,55 @@ public class CmpMemX86 extends MemOpX86 {
         short src = enc.reg(val());
 
         if(src == -1) {
+            assert !_swap;
             int log = _declaredType.log_size();
             x86_64_v2.rexF(-1, ptr, idx, log==3, enc);
             switch(log) {
-                case 0: enc.add1(0x80); break;
-                case 1: enc.add1(0x66).add1(0x81); break;
-                case 2: enc.add1(0x81); break;
-                case 3: enc.add1(0x81); break;
+            case 0: enc.add1(0x80); break;
+            case 1: enc.add1(0x66).add1(0x81); break;
+            case 2: enc.add1(0x81); break;
+            case 3: enc.add1(0x81); break;
             }
             x86_64_v2.indirectAdr(_scale, idx, ptr, _off,  7, enc);
             switch(log) {
-                case 0: enc.add1(_imm); break;
-                case 1: enc.add2(_imm); break;
-                case 2: enc.add4(_imm); break;
-                case 3: enc.add8(_imm); break;
+            case 0: enc.add1(_imm); break;
+            case 1: enc.add2(_imm); break;
+            case 2: enc.add4(_imm); break;
+            case 3: enc.add8(_imm); break;
             }
         } else {
-            encVal(enc, _declaredType, ptr, idx, src, _off, _scale);
+            encVal(enc, _declaredType, ptr, idx, src, _off, _scale, _swap);
         }
     }
 
-    static void encVal(Encoding enc, Type decl, short ptr, short idx, short src, int off, int scale) {
+    static void encVal(Encoding enc, Type decl, short ptr, short idx, short src, int off, int scale, boolean _swap) {
         if(decl instanceof TypeFloat) {
             src -= (short)x86_64_v2.XMM_OFFSET;
             enc.add1(decl==TypeFloat.F32 ? 0xF3 : 0xF2).add1(0x0F).add1(0xC2);
         } else {
             int log = decl.log_size();
             x86_64_v2.rexF(src, ptr, idx, log == 3, enc);
+            int swap = _swap ? 2 : 0;
             switch(log) {
-                case 0: enc.add1(0x38); break;
-                case 1: enc.add1(0x66).add1(0x3B); break;
-                case 2: enc.add1(0x3B); break;
-                case 3: enc.add1(0x3B); break;
+            case 0: enc.add1(0x38+swap); break;
+            case 1: enc.add1(0x66).add1(0x39+swap); break;
+            case 2: enc.add1(0x39+swap); break;
+            case 3: enc.add1(0x39+swap); break;
             }
         }
         x86_64_v2.indirectAdr(scale, idx, ptr, off, src, enc);
     }
+
     // General form: "cmp  dst = src, [base + idx<<2 + 12]"
     @Override public void asm(CodeGen code, SB sb) {
         String dst = code.reg(this);
         if( dst!="flags" )  sb.p(dst).p(" = ");
-        if( _invert ) asm_address(code,sb).p(",");
+        if( _swap ) asm_address(code,sb).p(",");
         if( val()==null ) {
             if( _imm!=0 )  sb.p("#").p(_imm);
         } else {
             sb.p(code.reg(val()));
         }
-        if( !_invert ) asm_address(code,sb.p(", "));
+        if( !_swap ) asm_address(code,sb.p(", "));
     }
 }
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java
index e6390386..23c12ae7 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java
@@ -476,21 +476,23 @@ public class x86_64_v2 extends Machine {
         Node lhs = bool.in(1);
         Node rhs = bool.in(2);
 
+        // Since cmp does not record a BOP, SetX/Jmp need to know if the CMP is swapped.
+
         // Vs memory
         if( lhs instanceof LoadNode ld && ld.nOuts() == 1 && rhs._type.isa(ld._declaredType) )
             return new CmpMemX86(bool, address(ld), ld.ptr(), idx, off, scale, imm(rhs), val, false);
 
+        // Operands swap in the encoding directly, no need for Set/Jmp to swap `bop`
         if( rhs instanceof LoadNode ld && ld.nOuts() == 1 && lhs._type.isa(ld._declaredType))
             return new CmpMemX86(bool, address(ld), ld.ptr(), idx, off, scale, imm(lhs), val, true );
 
         // Vs immediate
         if( rhs instanceof ConstantNode con && con._con instanceof TypeInteger ti && imm32(ti.value()) )
-            return new CmpIX86(bool, (int)ti.value());
+            return new CmpIX86(bool, (int)ti.value(), false);
 
-        if( lhs instanceof ConstantNode con && con._con instanceof TypeInteger ti && imm32(ti.value()) ) {
-            swap = true;
-            return new CmpIX86(bool, (int)ti.value(), 0.5);
-        }
+        // Operand swap compare; Set and Jmp need to swap `bop`
+        if( lhs instanceof ConstantNode con && con._con instanceof TypeInteger ti && imm32(ti.value()) )
+            return new CmpIX86(bool, (int)ti.value(), swap=true);
 
         // x vs y
         return new CmpX86(bool);
@@ -519,7 +521,7 @@ public class x86_64_v2 extends Machine {
         // Most general arith ops will also set flags, which the Jmp needs directly.
         // Loads do not set the flags, and will need an explicit TEST
         String op = "!=";
-        if( iff.in(1) instanceof BoolNode bool ) op = bool.op();
+        if( iff.in(1) instanceof BoolNode bool ) op = swap ? IfNode.swap(bool.op()) : bool.op();
         else if( iff.in(1)==null ) op = "=="; // Never-node cutout
         else iff.setDef(1, new BoolNode.NE(iff.in(1), new ConstantNode(TypeInteger.ZERO)));
         return new JmpX86(iff, op);
diff --git a/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java b/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java
index 8f3c9bb2..cf3bdde3 100644
--- a/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java
+++ b/chapter21/src/main/java/com/seaofnodes/simple/print/ASMPrinter.java
@@ -79,6 +79,7 @@ public abstract class ASMPrinter {
         if( fun._name != null ) sb.p(fun._name).p(" ");
         fun.sig().print(sb);
         sb.p("---------------------------").nl();
+        iadr = (iadr + 15)&-16; // All function entries padded to 16 align
 
         if( fun._frameAdjust != 0 )
             iadr = doInst(iadr,sb,code,fun,cfgidx,fun,true,true);
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/MergeSortTest.java b/chapter21/src/test/java/com/seaofnodes/simple/MergeSortTest.java
index fb250fc8..5624ee1b 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/MergeSortTest.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/MergeSortTest.java
@@ -1,67 +1,44 @@
 package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.codegen.CodeGen;
+import com.seaofnodes.simple.node.cpus.riscv.riscv;
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Path;
 import org.junit.Test;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
 public class MergeSortTest {
 
-    @Test
-    public void testMergeSort() {
-        String src =
-"""
-// based on the top-down version from https://en.wikipedia.org/wiki/Merge_sort
-
-val merge_sort = { int[] a, int[] b, int n ->
-    copy_array(a, 0, n, b);
-    split_merge(a, 0, n, b);
-};
-
-val split_merge = { int[] b, int begin, int end, int[] a ->
-    if (end - begin <= 1)
-        return 0;
-    int middle = (end + begin) / 2;
-    split_merge(a, begin, middle, b);
-    split_merge(a, middle, end, b);
-    merge(b, begin, middle, end, a);
-    return 0;
-};
-
-val merge = { int[] b, int begin, int middle, int end, int[] a ->
-    int i = begin, j = middle;
-
-    for (int k = begin; k < end; k++) {
-        // && and ||
-        bool cond = false;
-        if (i < middle) {
-            if (j >= end)          cond = true;
-            else if (a[i] <= a[j]) cond = true;
-        }
-        if (cond) b[k] = a[i++];
-        else      b[k] = a[j++];
+    @Test public void testMergeSort0() throws IOException {
+        int[] primes = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, };
+        SB sb = new SB().p(primes.length).p("[");
+        for( int prime : primes )
+            sb.p(prime).p(", ");
+        String sprimes = sb.p("]").toString();
+        TestC.run("sort", sprimes, 40);
+
+
+        EvalRisc5 R5 = TestRisc5.build("sort", 0, 36);
+        // Allocate an array of primes, filled in reverse order
+        int ps = R5._heap;
+        R5._heap += (primes.length+1)*8; // 25 primes, and length
+        R5.st4(ps,primes.length);
+        for( int i=0; i<primes.length; i++ )
+            R5.st8(ps+(primes.length-1-i+1)*8,primes[i]);
+        // Pass array base when calling `merge_sort`
+        R5.regs[riscv.A0] = ps;          // Array base to be sorted
+
+        int trap = R5.step(100000);
+        assertEquals(0,trap);
+
+        assertEquals(primes.length,R5.ld4s(ps));
+        for( int i=0; i<primes.length; i++ )
+            assertEquals(primes[i], R5.ld8(ps+(i+1)*8));
+
+        // TODO: replace with ARM Eval
+        String src = Files.readString(Path.of("src/test/java/com/seaofnodes/simple/progs/sort.smp"));
+        Chapter21Test.testCPU(src,"arm", "SystemV",36,null);
     }
-};
-
-val copy_array = { int[] a, int begin, int end, int[] b ->
-    for (int k = begin; k < end; k++)
-        b[k] = a[k];
-};
-
-int[] !a = new int[arg];
-int[] !b = new int[a#];
-
-for (int i = 0; i < a#; i++)
-    a[i] = a# - i;
-
-merge_sort(a, b, a#);
-
-return a;
-""";
-        Chapter21Test.testCPU(src,"x86_64_v2", "SystemV",54,"Stop[ return mov(mov([int])); return 0; ]");
-        Chapter21Test.testCPU(src,"riscv"    , "SystemV",44,"Stop[ return mov(mov([int])); return 0; ]");
-        Chapter21Test.testCPU(src,"arm"      , "SystemV",44,"Stop[ return mov(mov([int])); return 0; ]");
-//assertEquals("int[ 1,2,3,4,5,6,7,8,9,10,11]", Eval2.eval(code, 11));
-    }
-
 }
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/TestC.java b/chapter21/src/test/java/com/seaofnodes/simple/TestC.java
index 81742cab..5609758b 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/TestC.java
+++ b/chapter21/src/test/java/com/seaofnodes/simple/TestC.java
@@ -77,7 +77,7 @@ public abstract class TestC {
             System.err.println(result);
         }
         assertEquals( 0, error );
-        assertEquals(expected,result.replace("\r",""));
+        assertEquals(expected,result);
 
         // Allocation quality not degraded
         int delta = spills>>3;
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/progs/HellowWorld.smp b/chapter21/src/test/java/com/seaofnodes/simple/progs/HellowWorld.smp
deleted file mode 100644
index 172dffa0..00000000
--- a/chapter21/src/test/java/com/seaofnodes/simple/progs/HellowWorld.smp
+++ /dev/null
@@ -1,18 +0,0 @@
-
-{ i32 byte[] i64 -> i64 } write = extern;
-byte[] buf = new byte[100];
-buf[ 0] = 'H';
-buf[ 1] = 'e';
-buf[ 2] = 'l';
-buf[ 3] = 'l';
-buf[ 4] = 'o';
-buf[ 5] = ',';
-buf[ 6] = 'W';
-buf[ 7] = 'o';
-buf[ 8] = 'r';
-buf[ 9] = 'l';
-buf[10] = 'd';
-buf[11] = '!';
-buf[12] = '\n';
-
-return write(0,buf,12);
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/progs/brain_fuck.c b/chapter21/src/test/java/com/seaofnodes/simple/progs/brain_fuck.c
index 15de1864..127cbe73 100644
--- a/chapter21/src/test/java/com/seaofnodes/simple/progs/brain_fuck.c
+++ b/chapter21/src/test/java/com/seaofnodes/simple/progs/brain_fuck.c
@@ -15,4 +15,4 @@ int main() {
   printf("%.*s", ps->len, ps->data);
 
   return 0;
-}
\ No newline at end of file
+}
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/progs/sort.c b/chapter21/src/test/java/com/seaofnodes/simple/progs/sort.c
new file mode 100644
index 00000000..ad76cc7f
--- /dev/null
+++ b/chapter21/src/test/java/com/seaofnodes/simple/progs/sort.c
@@ -0,0 +1,28 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+// Test wrapper to call `sort.smp`
+
+typedef struct AryInt {
+    unsigned int len;
+    long long data[];
+} AryInt;
+
+__attribute__ ((CALL_CONV))
+extern AryInt* merge_sort(AryInt*);
+
+
+long long primes[] = { 25, 97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2 };
+
+int main() {
+  AryInt *as = (AryInt*)primes;
+
+  merge_sort(as);
+
+  printf("%d[",as->len);
+  for( int i=0; i<as->len; i++ )
+    printf("%d, ",as->data[i]);
+  printf("]");
+
+  return 0;
+}
\ No newline at end of file
diff --git a/chapter21/src/test/java/com/seaofnodes/simple/progs/sort.smp b/chapter21/src/test/java/com/seaofnodes/simple/progs/sort.smp
new file mode 100644
index 00000000..ae3f4f23
--- /dev/null
+++ b/chapter21/src/test/java/com/seaofnodes/simple/progs/sort.smp
@@ -0,0 +1,38 @@
+// -*- mode: java;  -*-
+// based on the top-down version from https://en.wikipedia.org/wiki/Merge_sort
+
+val merge_sort = { int[] a ->
+    int[] !b = new int[a#];
+    copy_array (a, 0, a#, b);
+    split_merge(a, 0, a#, b);
+};
+
+val split_merge = { int[] b, int begin, int end, int[] a ->
+    if (end - begin <= 1)
+        return 0;
+    int middle = (end + begin) / 2;
+    split_merge(a, begin, middle, b);
+    split_merge(a, middle, end, b);
+    merge(b, begin, middle, end, a);
+    return 0;
+};
+
+val merge = { int[] b, int begin, int middle, int end, int[] a ->
+    int i = begin, j = middle;
+
+    for (int k = begin; k < end; k++) {
+        // && and ||
+        bool cond = false;
+        if (i < middle) {
+            if (j >= end)          cond = true;
+            else if (a[i] <= a[j]) cond = true;
+        }
+        if (cond) b[k] = a[i++];
+        else      b[k] = a[j++];
+    }
+};
+
+val copy_array = { int[] a, int begin, int end, int[] b ->
+    for (int k = begin; k < end; k++)
+        b[k] = a[k];
+};