Chapter 1: Introduction

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>

2 files changed, 250 insertions, 0 deletions

diff --git a/isa/src/test/java/com/seaofnodes/isa/RiscTest.java b/isa/src/test/java/com/seaofnodes/isa/RiscTest.java
new file mode 100644
index 00000000..d10f97a4
--- /dev/null
+++ b/isa/src/test/java/com/seaofnodes/isa/RiscTest.java
@@ -0,0 +1,122 @@
+package com.seaofnodes.isa;
+
+import com.seaofnodes.isa.eval.EvalArm64;
+import com.seaofnodes.isa.eval.EvalRisc5;
+
+/** Fixed instruction words plus execution checks of the shared test emulators. */
+public class RiscTest {
+    static void word(int expected, int actual) {
+        assert expected==actual : String.format("Expected %08x, got %08x",expected,actual);
+    }
+    public static void main(String[] args) {
+        // Instructions encountered by dynamic allocation measurements.
+        for( long[] pair : new long[][]{{17,3},{-17,3},{17,0},{Long.MIN_VALUE,-1}} ) {
+            var a=new EvalArm64(new byte[1024],512);
+            a.st4(4,0x9AC20C20); // sdiv x0,x1,x2
+            a._pc=4;a.regs[1]=pair[0];a.regs[2]=pair[1];
+            assert a.step(1)==0;
+            assert a.regs[0]==(pair[1]==0 ? 0 : pair[0]/pair[1]);
+        }
+        var discard=new EvalArm64(new byte[1024],512);
+        discard.st4(4,0x3862683F); // ldrb wzr,[x1,x2]; discard without changing SP
+        discard._pc=4;discard.regs[1]=100;discard.regs[2]=4;discard.st1(104,91);
+        assert discard.step(1)==0 && discard.regs[31]==512;
+        for(long value:new long[]{-1,0,1,Long.MIN_VALUE}) {
+            var unsigned=new EvalRisc5(new byte[1024],512);
+            unsigned.st4(4,0x00113193); // sltiu x3,x2,1 (seqz)
+            unsigned._pc=4;unsigned.regs[2]=value;
+            assert unsigned.step(1)==0;
+            assert unsigned.regs[3]==(value==0 ? 1 : 0);
+        }
+        var logical=new EvalArm64(new byte[1024],512);
+        logical.st4(4,0xB27F0020); // orr x0,x1,#2
+        logical.st4(8,0x9A9F17E2); // cset x2,eq; false must not retain prior result
+        logical._pc=4;logical.regs[1]=8;
+        assert logical.step(2)==0;
+        assert logical.regs[0]==10 && logical.regs[2]==0;
+        for(double rhs:new double[]{1,2,3,Double.NaN}) {
+            var r=new EvalRisc5(new byte[1024],512);
+            r.st4(4,0xA220A1D3); // feq.d x3,f1,f2
+            r.st4(8,0xA2209253); // flt.d x4,f1,f2
+            r._pc=4;r.fregs[1]=2;r.fregs[2]=rhs;
+            assert r.step(2)==0;
+            assert r.regs[3]==(2==rhs ? 1 : 0);
+            assert r.regs[4]==(2<rhs ? 1 : 0);
+        }
+        var store=new EvalRisc5(new byte[1024],512);
+        store.st4(4,0x00113827); // fsd f1,16(sp)
+        store.st4(8,0xFE112E27); // fsw f1,-4(sp)
+        store._pc=4;store.fregs[1]=-3.25;
+        assert store.step(2)==0;
+        assert store.ld8(528)==Double.doubleToRawLongBits(-3.25);
+        assert store.ld4s(508)==Float.floatToRawIntBits(-3.25f);
+        word(0x9E780020,Arm64.floatToInteger(1,0)); // FCVTZS x0,d1
+        for( double value : new double[]{0.0,-0.0,6.92,-6.92,0.99,-0.99,
+                0x1p63,Math.nextDown(0x1p63),-0x1p63,Math.nextDown(-0x1p63),
+                Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.NaN,
+                Double.longBitsToDouble(0xFFF0000000000001L)} ) {
+            var a=new EvalArm64(new byte[1024],512);
+            a.st4(4,0x9E780020);
+            a._pc=4;
+            a.fregs[1]=value;
+            a.step(1);
+            assert a.regs[0]==(long)value : "ARM conversion: "+value;
+
+            var bytes=new X86Test.Bytes();
+            RiscV.floatToInteger(bytes,10,1);
+            var r=new EvalRisc5(new byte[1024],512);
+            System.arraycopy(bytes.toByteArray(),0,r._buf,4,bytes.size());
+            r._pc=4;
+            r.fregs[1]=value;
+            // NaN takes four instructions; a finite value takes five.
+            r.step(Double.isNaN(value) ? 4 : 5);
+            assert r.regs[10]==(long)value : "RISC-V conversion: "+value;
+        }
+        word(0x8B020020,Arm64.r_reg(Arm64.OP_ADD,0,2,0,1,0)); // add x0,x1,x2
+        word(0x9100A420,Arm64.imm_inst(Arm64.OPI_ADD,41,1,0));
+        word(0xD2800540,Arm64.mov(Arm64.OP_MOVZ,0,42,0));
+        word(0xF9400BE0,Arm64.load_str_imm(Arm64.OP_LOAD_IMM_64,16,31,0,8));
+        word(0xF9000BE0,Arm64.load_str_imm(Arm64.OP_STORE_IMM_64,16,31,0,8));
+        word(0xD65F03C0,Arm64.ret(Arm64.OP_RET));
+        word(0x17FFFFFF,Arm64.b(Arm64.OP_UJMP,-4));
+        word(0x16000000,Arm64.b(Arm64.OP_UJMP,-(1<<27)));
+        word(0x54000040,Arm64.b_cond(Arm64.OP_BRANCH,8,Arm64.COND.EQ));
+        word(0x54800001,Arm64.b_cond(Arm64.OP_BRANCH,-(1<<20),Arm64.COND.NE));
+        word(0x5CFFFFE0,Arm64.load_pc(Arm64.OPF_ARM,-4,0));
+
+        word(0x002081B3,RiscV.r_type(RiscV.OP,3,0,1,2,0)); // add x3,x1,x2
+        word(0x02A00513,RiscV.i_type(RiscV.OP_IMM,10,0,0,42));
+        word(0x123451B7,RiscV.u_type(RiscV.OP_LUI,3,0x12345));
+        word(0x00B13823,RiscV.s_type(RiscV.OP_STORE,3,2,11,16));
+        word(0x00208463,RiscV.b_type(RiscV.OP_BRANCH,0,(short)1,(short)2,8));
+        word(0xFE208EE3,RiscV.b_type(RiscV.OP_BRANCH,0,(short)1,(short)2,-4));
+        word(0x008000EF,RiscV.j_type(RiscV.OP_JAL,1,8));
+        word(0xFFDFF0EF,RiscV.j_type(RiscV.OP_JAL,1,-4));
+        word(0x000800EF,RiscV.j_type(RiscV.OP_JAL,1,1<<19));
+        word(0x800000EF,RiscV.j_type(RiscV.OP_JAL,1,-(1<<20)));
+
+        // Constants exercise MOVN, MOVZ and multiple MOVK lanes, including all 0/1.
+        for( long x : new long[]{0,-1,42,0xFFFF0000FFFFL,0x1122334455667788L,Long.MIN_VALUE} ) {
+            var bytes=new X86Test.Bytes();
+            Arm64.constant(bytes,0,x);
+            byte[] image=new byte[1024];
+            System.arraycopy(bytes.toByteArray(),0,image,4,bytes.size());
+            var arm=new EvalArm64(image,512);
+            arm._pc=4;
+            arm.step(bytes.size()/4);
+            assert arm.regs[0]==x : String.format("Constant %016x became %016x",x,arm.regs[0]);
+        }
+        // Raw instructions make these emulator checks independent of the encoder.
+        var arm=new EvalArm64(new byte[1024],512);
+        arm.st4(4,0xD2800540); // mov x0,#42
+        arm._pc=4;
+        arm.step(1);
+        assert arm.regs[0]==42;
+        var risc=new EvalRisc5(new byte[1024],512);
+        risc.st4(4,0x02A00513); // addi a0,zero,42
+        risc._pc=4;
+        risc.step(1);
+        assert risc.regs[10]==42;
+        System.out.println("Shared ARM/RISC-V encoding and evaluator tests passed");
+    }
+}
diff --git a/isa/src/test/java/com/seaofnodes/isa/X86Test.java b/isa/src/test/java/com/seaofnodes/isa/X86Test.java
new file mode 100644
index 00000000..8af84ae8
--- /dev/null
+++ b/isa/src/test/java/com/seaofnodes/isa/X86Test.java
@@ -0,0 +1,128 @@
+package com.seaofnodes.isa;
+
+import java.io.ByteArrayOutputStream;
+import java.util.HexFormat;
+import java.util.function.Consumer;
+
+/** Fixed instruction bytes, independent of the compiler and register allocator. */
+public class X86Test {
+    static class Bytes extends ByteArrayOutputStream implements CodeSink {
+        @Override public Bytes add1(int value) { write(value); return this; }
+    }
+    static void check(String expected, Consumer<CodeSink> emit) {
+        var bytes=new Bytes();
+        emit.accept(bytes);
+        String actual=HexFormat.of().formatHex(bytes.toByteArray());
+        assert expected.equals(actual) : "Expected "+expected+", got "+actual;
+    }
+    public static void main(String[] args) {
+        check("f2480f2cc04883f801711c660f2ec07a1366480f7ec048c1f83f48f7d0480fbaf83feb034833c0",
+              b -> X86.floatToInteger(b,0,0));
+        check("f24d0f2cca4983f901711d66450f2ed27a13664d0f7ed149c1f93f49f7d1490fbaf93feb034d33c9",
+              b -> X86.floatToInteger(b,9,10));
+        check("4d03ca", b -> X86.reg(b,0x03,9,10));
+        check("4d0fafca", b -> X86.reg(b,0x0FAF,9,10));
+        check("4981c17fffffff", b -> X86.imm(b,0x81,0,9,-129));
+        check("4983c180", b -> X86.imm(b,0x81,0,9,-128));
+        check("4983c17f", b -> X86.imm(b,0x81,0,9,127));
+        check("4981c180000000", b -> X86.imm(b,0x81,0,9,128));
+        check("4d6bca80", b -> X86.imul(b,9,10,-128));
+        check("4d69ca80000000", b -> X86.imul(b,9,10,128));
+
+        // TEST; SETZ; MOVZX. Both overlapping and distinct input/output registers.
+        int[][] regs={{0,0},{1,1},{7,7},{9,9},{1,9},{9,1},{6,0},{15,8}};
+        String[] not={"4885c00f94c00fb6c0","4885c90f94c10fb6c9",
+            "4885ff400f94c7400fb6ff","4d85c9410f94c1450fb6c9",
+            "4d85c90f94c10fb6c9","4885c9410f94c1450fb6c9",
+            "4885c0400f94c6400fb6f6","4d85c0410f94c7450fb6ff"};
+        for( int i=0; i<regs.length; i++ ) {
+            int dst=regs[i][0], src=regs[i][1];
+            check(not[i],b -> X86.not(b,dst,src));
+        }
+
+        // SIB, rbp/r13 zero displacement, displacement boundaries, and an extended index.
+        check("488b0424", b -> X86.load(b,3,false,false,0,4,-1,0,0));
+        check("498b0424", b -> X86.load(b,3,false,false,0,12,-1,0,0));
+        check("488b4500", b -> X86.load(b,3,false,false,0,5,-1,0,0));
+        check("498b4500", b -> X86.load(b,3,false,false,0,13,-1,0,0));
+        check("488b437f", b -> X86.load(b,3,false,false,0,3,-1,127,0));
+        check("488b8380000000", b -> X86.load(b,3,false,false,0,3,-1,128,0));
+        check("488b4380", b -> X86.load(b,3,false,false,0,3,-1,-128,0));
+        check("488b837fffffff", b -> X86.load(b,3,false,false,0,3,-1,-129,0));
+        check("4b8b44e508", b -> X86.load(b,3,false,false,0,13,12,8,3));
+        check("4f8d4ca508", b -> X86.lea(b,9,13,12,8,2));
+        check("4e8d0ce520000000", b -> X86.lea(b,9,-1,12,32,3));
+
+        check("480fbe03", b -> X86.load(b,0,true,false,0,3,-1,0,0));
+        check("480fb603", b -> X86.load(b,0,false,false,0,3,-1,0,0));
+        check("480fbf03", b -> X86.load(b,1,true,false,0,3,-1,0,0));
+        check("480fb703", b -> X86.load(b,1,false,false,0,3,-1,0,0));
+        check("486303", b -> X86.load(b,2,true,false,0,3,-1,0,0));
+        check("8b03", b -> X86.load(b,2,false,false,0,3,-1,0,0));
+        check("f3470f104ca508", b -> X86.load(b,2,false,true,9,13,12,8,2));
+        check("f2470f104ca508", b -> X86.load(b,3,false,true,9,13,12,8,2));
+
+        check("408823", b -> X86.store(b,0,false,4,3,-1,0,0)); // spl, not ah
+        check("408833", b -> X86.store(b,0,false,6,3,-1,0,0)); // sil, not dh
+        check("44883b", b -> X86.store(b,0,false,15,3,-1,0,0));
+        check("6647894ca508", b -> X86.store(b,1,false,9,13,12,8,2));
+        check("47894ca508", b -> X86.store(b,2,false,9,13,12,8,2));
+        check("4f894ca508", b -> X86.store(b,3,false,9,13,12,8,2));
+        check("f3470f114ca508", b -> X86.store(b,2,true,9,13,12,8,2));
+        check("f2470f114ca508", b -> X86.store(b,3,true,9,13,12,8,2));
+        check("c603ff", b -> X86.storeImm(b,0,-1,3,-1,0,0));
+        check("6643c744a5083412", b -> X86.storeImm(b,1,0x1234,13,12,8,2));
+        check("c70378563412", b -> X86.storeImm(b,2,0x12345678,3,-1,0,0));
+        check("48c703ffffffff", b -> X86.storeImm(b,3,-1,3,-1,0,0));
+        check("803bff", b -> X86.cmpImm(b,0,-1,3,-1,0,0));
+        check("6643817ca5083412", b -> X86.cmpImm(b,1,0x1234,13,12,8,2));
+        check("813b78563412", b -> X86.cmpImm(b,2,0x12345678,3,-1,0,0));
+        check("48813b15cd5b07", b -> X86.cmpImm(b,3,123456789,3,-1,0,0));
+        check("49f7da", b -> X86.unary(b,0xF7,3,10));
+        check("49c1e1ff", b -> X86.shift(b,4,9,255));
+        check("489949f7fa", b -> X86.divide(b,10));
+        check("f2450f58ca", b -> X86.sse(b,0xF2,0x0F58,false,9,10));
+        check("f24d0f2aca", b -> X86.sse(b,0xF2,0x0F2A,true,9,10));
+        check("66450f2eca", b -> X86.sse(b,0x66,0x0F2E,false,9,10));
+        check("4d0fbeca", b -> X86.extend(b,8,true,9,10));
+        check("4c0fb6ce", b -> X86.extend(b,8,false,9,6));
+        check("6647394ca508", b -> X86.cmpMem(b,1,9,13,12,8,2,false));
+        check("66473b4ca508", b -> X86.cmpMem(b,1,9,13,12,8,2,true));
+        check("403833", b -> X86.cmpMem(b,0,6,3,-1,0,0,false));
+        check("400f95c6400fb6f6", b -> X86.set(b,5,6));
+        check("410f95c1450fb6c9", b -> X86.set(b,5,9));
+        check("4d33c9", b -> X86.constant(b,9,0));
+        check("49c7c1ffffffff", b -> X86.constant(b,9,-1));
+        check("41b9ffffffff", b -> X86.constant(b,9,0xFFFFFFFFL));
+        check("49b98877665544332211", b -> X86.constant(b,9,0x1122334455667788L));
+        check("4c8d0d00000000", b -> { assert X86.rip(b,0,0x8D,true,9)==7; });
+        check("f2440f100d00000000", b -> { assert X86.rip(b,0xF2,0x0F10,false,9)==9; });
+        check("e800000000c3", b -> { X86.call(b); X86.ret(b); });
+        check("ffd0", b -> X86.callRegister(b,0));
+        check("41ffd2", b -> X86.callRegister(b,10));
+        check("41519d", b -> X86.flags(b,9,true));
+        check("9c4159", b -> X86.flags(b,9,false));
+        check("ff7424088f442410", b -> X86.stackCopy(b,8,16));
+        check("4d8bca", b -> X86.move(b,false,false,9,10));
+        check("4d0f28ca", b -> X86.move(b,true,true,9,10));
+        check("664d0f6eca", b -> X86.move(b,true,false,9,10));
+        check("664d0f7ed1", b -> X86.move(b,false,true,9,10));
+        branch("eb7f",129,-1);
+        branch("eb80",-126,-1);
+        branch("e97d000000",130,-1);
+        branch("e97cffffff",-127,-1);
+        branch("757f",129,5);
+        branch("0f857c000000",130,5);
+        branch("0f857bffffff",-127,5);
+        System.out.println("Shared x86 encoding tests passed");
+    }
+    static void branch(String expected, int delta, int condition) {
+        int size=X86.branchSize(delta,condition>=0);
+        byte[] bytes=new byte[size];
+        var shortForm=new Bytes();
+        X86.branch(shortForm,condition);
+        System.arraycopy(shortForm.toByteArray(),0,bytes,0,2);
+        X86.patchBranch(bytes,0,size,delta,condition);
+        assert expected.equals(HexFormat.of().formatHex(bytes));
+    }
+}