From 38fd3c17c672c42fc768b0f31680b5d9679cac6d Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 17 Apr 2025 09:42:52 -0700 Subject: 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. --- .../simple/node/cpus/x86_64_v2/CmpIX86.java | 9 +-- .../simple/node/cpus/x86_64_v2/CmpMemX86.java | 42 +++++----- .../simple/node/cpus/x86_64_v2/x86_64_v2.java | 14 ++-- .../com/seaofnodes/simple/print/ASMPrinter.java | 1 + .../java/com/seaofnodes/simple/MergeSortTest.java | 89 ++++++++-------------- .../src/test/java/com/seaofnodes/simple/TestC.java | 2 +- .../com/seaofnodes/simple/progs/HellowWorld.smp | 18 ----- .../java/com/seaofnodes/simple/progs/brain_fuck.c | 2 +- .../test/java/com/seaofnodes/simple/progs/sort.c | 28 +++++++ .../test/java/com/seaofnodes/simple/progs/sort.smp | 38 +++++++++ 10 files changed, 135 insertions(+), 108 deletions(-) delete mode 100644 chapter21/src/test/java/com/seaofnodes/simple/progs/HellowWorld.smp create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/progs/sort.c create mode 100644 chapter21/src/test/java/com/seaofnodes/simple/progs/sort.smp 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 - 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 +#include + +// 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; ilen; 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]; +}; -- cgit v1.2.3