藉由 JIT 編譯加速 rv32emu

contributed by < LambertWSJ >

目標

rv32emu 是針對 RISC-V 32 位元指令集開發的精簡高效模擬器，本任務是引入 JIT 編譯器，以加速 RV32 指令的執行。
2022 年 7 月 31 日在 COSCUP 2022 以〈設計精簡又快速的 RISC-V 指令集模擬器〉為題，發表相關成果。

編譯 RISC-V toolchain

$ sudo apt-get install autoconf automake autotools-dev \
       curl python3 libmpc-dev libmpfr-dev libgmp-dev gawk \
       build-essential bison flex texinfo gperf libtool patchutils bc zlib1g-dev libexpat-dev
$ git clone https://github.com/riscv/riscv-gnu-toolchain
$ cd riscv-gnu-toolchain
$ ./configure --prefix=/opt/riscv --enable-multilib
$ make
$ sudo make install
$ export PATH=$PATH:/opt/riscv/bin

安裝 submodule 的時候會花一點時間，從 release 選一個版本解壓縮後放到要執行的 PATH 也可以但生成 ELF 會出錯，所以不建議這麼做。

riscv64-unknown-elf-gcc -march=rv32i -mabi=ilp32 demo.c -o demo
./rv32emu demo

參考 Run Quake on rv32emu-next

安裝 riscv-none-embed-gcc

為了要執行 arch-test 需要安裝 riscv-none-embed-gcc，可以簡單的從 release 選對應的 OS 跟架構下載壓縮檔，解壓後在用 mv 搬到 /opt，之後把 riscv-embed bin 的資料夾更新到 PATH

code ~/.bashrc

在 .bashrc 將 riscv-embed 的路徑更新到 PATH，就像更新 Windows 的環境變數一樣

export PATH=${PATH}:/opt/riscv-embed/bin

RISC-V 指令集

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

32 bit 的 RISC-V 指令有不同的種類，每個種類的指令集都有固定位置跟長度來表示指令集的欄位

欄位	說明
imm	在不同的指令有不同的作用，用來輔助指令
rs1	第 1 個保存來源的暫存器索引值
rs2	第 2 個保存來源的暫存器索引值
rd	儲存運算結果的暫存器索引值
opcode	用來表示指令集要做什麼操作 e.g. add, sub
funct3	額外的 opcode
funct7	額外的 opcode

模擬器運作原理

簡單來說，模擬器就是用軟體去模擬硬體的行為，模擬器要模擬一系列的硬體，使其可以運行特定軟體，舉例來說，如果依照 Game Boy 的規格把 Game Boy 模擬器實作出來，那你就能在電腦上懷舊寶可夢紅／綠。

rv32emu 是模擬 RISC-V 指令集的 CPU，因此要依照 RISC-V 的規格書定義暫存器的數量跟功能以及不同指令集的操作和欄位來實作 CPU 的解碼碼器跟指令集對應的操作(e.g. 加減乘除)，並將結果存在暫存器，也就是模擬 CPU 的指令周期，這樣一來就能在不同的指令集架構的電腦上模擬 RISC-V 指令集的軟體。

記憶體 I/O

RISC-V 是 load–store architecture 指令跟資料回存在記憶體中，當要執行指令的時候才會載入到暫存器去做對應的操作，而且是 Byte addressing，所以記憶體讀取單位為一個 byte。

rv32emu 的記憶體大小為 $2^{16} \times 2^{16}$ byte，X 軸為 data 組成的 chunk，Y 軸為 byte 組成的 data 並以 uint8_t 呈現資料，至於為何無論縱橫都是 $2^{16}$ 次方？這跟讀取方式有關。

typedef struct {
    uint8_t data[0x10000];
} chunk_t;

typedef struct {
    chunk_t *chunks[0x10000];
} memory_t;

讀寫記憶體要考慮如何將 32 位元的地址對應到記憶體的 X 軸跟 Y 軸，可以將 32 位元拆成一半，如下圖所示，用兩個 16 位元分別表示 X 跟 Y 便能夠讀取 memory[x][y]

其中 X 可以將地址右移 16 位元取得地址的前半段，Y 可以用 0xFFFF 作為 bit mask 再跟 addr 做 and 運算就能取得地址的後半段的位元。

因為 X 跟 Y 都是 16 位元，數值的範圍為 0 到 $2^{16}$ ，如果讀取記憶體不發生越界的情況就要把記憶體的大小設為 $2^{16} \times 2^{16}$ 。知道如何將地址對應到記憶體位址後就可以做讀寫的操作了。

寫入記憶體

從 addr 開始逐 byte 將大小為 size 的資料寫入到記憶體，如果 chunk 還沒初始化就配置記憶體到 chunk 並存入到 memory。
寫入記憶體依然按照前述規則將地址的每一段 (addr + i) 轉為記憶體的 X 跟 Y，這樣就能將 src 寫入到 memory[x][y]。

void memory_write(memory_t *m, uint32_t addr, const uint8_t *src, uint32_t size)
{
    for (uint32_t i = 0; i < size; ++i) {
        uint32_t p = addr + i;
        uint32_t x = p >> 16;
        chunk_t *c = m->chunks[x];
        if (!c) {
            c = malloc(sizeof(chunk_t));
            memset(c->data, 0, sizeof(c->data));
            m->chunks[x] = c;
        }
        c->data[p & 0xffff] = src[i];
    }
}

讀取記憶體

從記憶體的 addr 讀取 size 大小的資料到 dst。如果 addr 跟 addr + size 在記憶體的位置是同個 X，也就是同個 chunk ，如果這個 chunk 沒有資料的話就寫入 size 個 0 到 dst。否則從memory[x][p] 開始寫入大小為 size 的資料。

static const uint32_t mask_hi = ~(0xffff);

void memory_read(memory_t *m, uint8_t *dst, uint32_t addr, uint32_t size)
{
    /* test if this read is entirely within one chunk */
    if ((addr & mask_hi) == ((addr + size) & mask_hi)) {
        chunk_t *c;
        if ((c = m->chunks[addr >> 16])) {
            /* get the subchunk pointer */
            const uint32_t p = (addr & mask_lo);

            /* copy over the data */
            memcpy(dst, c->data + p, size);
        } else {
            memset(dst, 0, size);
        }
    } else {
        /* naive copy */
        for (uint32_t i = 0; i < size; ++i) {
            uint32_t p = addr + i;
            chunk_t *c = m->chunks[p >> 16];
            dst[i] = c ? c->data[p & 0xffff] : 0;
        }
    }
}

ELF 載入器

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

ELF 檔可以用來當作執行檔也可以當作物件檔來連結，如果作為執行檔則可以從 .text 的區段讀取 RISC-V 的指令讓模擬器運行，.text 可以用 riscv-gnu-toolchain 的 riscv32-unknown-linux-gnu-objdump 印出 RISC-V 的組語，如果要用程式來讀取指令則可以依據規格書給的欄位來定義如下的 header

Header	struct
ELF	ELF32_Ehdr
Program	ELF32_Phdr
Section	ELF32_Shdr

elf_open 開啟 ELF 檔並配置一塊跟檔案一樣大的記憶體給 raw_data，配置完記憶體後再把 ELF 檔整個寫入到 raw_data，raw_data 也相當於 ELF 的開頭，回顧一下上圖，無論是連結或是執行，開頭都是 ELF header，因此用 elf->hdr 指向 raw_data，就能存取到 ELF header 的資料了

bool elf_open(elf_t *e, const char *path)
{
    /* free previous memory */
    if (e->raw_data)
        release(e);

    FILE *f = fopen(path, "rb");
    if (!f)
        return false;

    /* get file size */
    fseek(f, 0, SEEK_END);
    e->raw_size = ftell(f);
    fseek(f, 0, SEEK_SET);
    if (e->raw_size == 0) {
        fclose(f);
        return false;
    }

    /* allocate memory */
    free(e->raw_data);
    e->raw_data = malloc(e->raw_size);

    /* read data into memory */
    const size_t r = fread(e->raw_data, 1, e->raw_size, f);

    fclose(f);
    if (r != e->raw_size) {
        release(e);
        return false;
    }

    /* point to the header */
    e->hdr = (const struct Elf32_Ehdr *) e->raw_data;

    /* check it is a valid ELF file */
    if (!is_valid(e)) {
        release(e);
        return false;
    }

    return true;
}

從程式碼來看 e->hdr = (const struct Elf32_Ehdr *) e->raw_data 這一行看不出來 e->hdr 的欄位有什麼資料，因此我們需要 gdb 來觀察 ELF header，以 build/puzzle.elf 為例，當 elf_open 執行完畢再印出來

(gdb) set print pretty
(gdb) p *elf->hdr
$4 = {
  e_ident = "\177ELF\001\001\001\000\000\000\000\000\000\000\000",
  e_type = 2,
  e_machine = 243,
  e_version = 1,
  e_entry = 65680,
  e_phoff = 52,
  e_shoff = 92888,
  e_flags = 0,
  e_ehsize = 52,
  e_phentsize = 32,
  e_phnum = 2,
  e_shentsize = 40,
  e_shnum = 13,
  e_shstrndx = 12
}

如果還要更清楚的話可以比照 readelf -h 來觀察 puzzle.elf 就可以知道 header 各欄位的意思了，記得要先安裝 riscv-gnu-toolchain

> riscv32-unknown-linux-gnu-readelf -h puzzle.elf 
ELF Header:
  Magic:   7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00 
  Class:                             ELF32
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           RISC-V
  Version:                           0x1
  Entry point address:               0x10090
  Start of program headers:          52 (bytes into file)
  Start of section headers:          92888 (bytes into file)
  Flags:                             0x0
  Size of this header:               52 (bytes)
  Size of program headers:           32 (bytes)
  Number of program headers:         2
  Size of section headers:           40 (bytes)
  Number of section headers:         13
  Section header string table index: 12

In-depth: ELF - The Extensible & Linkable Format

bool elf_load(elf_t *e, struct riscv_t *rv, memory_t *mem)
{
    rv_set_pc(rv, e->hdr->e_entry); /* set the entry point */

    /* loop over all of the program headers */
    for (int p = 0; p < e->hdr->e_phnum; ++p) {
        /* find next program header */
        uint32_t offset = e->hdr->e_phoff + (p * e->hdr->e_phentsize);
        const struct Elf32_Phdr *phdr =
            (const struct Elf32_Phdr *) (e->raw_data + offset);

        /* check this section should be loaded */
        if (phdr->p_type != PT_LOAD)
            continue;

        /* memcpy required range */
        const int to_copy = min(phdr->p_memsz, phdr->p_filesz);
        if (to_copy)
            memory_write(mem, phdr->p_vaddr, e->raw_data + phdr->p_offset,
                         to_copy);

        /* zero fill required range */
        const int to_zero = max(phdr->p_memsz, phdr->p_filesz) - to_copy;
        if (to_zero)
            memory_fill(mem, phdr->p_vaddr + to_copy, to_zero, 0);
    }

    return true;
}

透過 ELF open 開啟檔案之後依據 ELF header 得知程式的開頭、程式檔頭的地址以及有多少個程式檔頭，而程式檔頭彼此的間距是一樣的，如下圖所示

因此只要計算好偏移量就能逐個讀取程式檔頭，讀到程式檔頭接著去判斷這個程式檔頭的類型是不是可以載入的 (PT_LOAD)，如果可以載入的程式檔頭，就依照規格書的規範來處理 PT_LOAD，去比較分區的檔案大小 (p_filesz) 跟分區的記憶體大小 (p_memsz)，取小的那個寫入到記憶體，剩下的用0補上。

ELF 規格書關於 PT_LOAD 的規範

The array element specifies a loadable segment, described by p_filesz and
p_memsz. The bytes from the file are mapped to the beginning of the memory
segment. If the segment's memory size (p_memsz) is larger than the file size
(p_filesz), the "extra'' bytes are defined to hold the value 0 and to follow the
segment's initialized area. The file size may not be larger than the memory size.
Loadable segment entries in the program header table appear in ascending order,
sorted on the p_vaddr member.

CPU 指令周期

擷取

static const uint32_t mask_lo = 0xffff;

uint32_t memory_read_ifetch(memory_t *m, uint32_t addr)
{
    const uint32_t addr_lo = addr & mask_lo;
    assert((addr_lo & 1) == 0);

    chunk_t *c = m->chunks[addr >> 16];
    assert(c);
    return *(const uint32_t *) (c->data + addr_lo);
}

擷取指令透過將 32 位元的地址拆成一半，前半段 (addr >> 16) 用來定位記憶體 chunks 的位置，後半段(addr_lo)用來找出指令的開頭地址，相當於 addr 的前半段是 y 後半段是 x，指令在 memory[x][y]

當找到指令的開頭地址之後再轉型成 32 位元的指令，便能夠從開頭的地址往後讀取 32 位元，也就是 4 個 8 bit，這樣就能夠取出完整的 32 位元指令，這也是為何 32 位元的指令執行完後更新 PC 要加上 4，壓縮指令集執行完後 PC 要加 2，這樣才能確保下次要取出指令的時候位址是正確的。

解碼

要擷取 RV32I 指令集中 $r d$ , $r s 1$ , $r s 2$ , $f u n c 3$ , $f u n c 7$ , $i m m$ 可以透過 bitmask 來讀取指令集的欄位

enum {
    INST_6_2     = 0b00000000000000000000000001111100,
    FR_C_1_0     = 0b00000000000000000000000000000011, // c-type
    FR_C_15_13   = 0b00000000000000001110000000000000,
    FR_RD        = 0b00000000000000000000111110000000,
    FR_RS1       = 0b00000000000011111000000000000000,
    FR_RS2       = 0b00000001111100000000000000000000,
    ...
    FS_IMM_4_0   = 0b00000000000000000000111110000000, // s-type
    FS_IMM_11_5  = 0b11111110000000000000000000000000,
    //               ....xxxx....xxxx....xxxx....xxxx
    FB_IMM_11    = 0b00000000000000000000000010000000, // b-type
    FB_IMM_4_1   = 0b00000000000000000000111100000000,
    FB_IMM_10_5  = 0b01111110000000000000000000000000,
    FB_IMM_12    = 0b10000000000000000000000000000000,
    //               ....xxxx....xxxx....xxxx....xxxx
    FU_IMM_31_12 = 0b11111111111111111111000000000000, // u-type
    //               ....xxxx....xxxx....xxxx....xxxx
    FJ_IMM_19_12 = 0b00000000000011111111000000000000, // j-type
    FJ_IMM_11    = 0b00000000000100000000000000000000,
    FJ_IMM_10_1  = 0b01111111111000000000000000000000,
    FJ_IMM_20    = 0b10000000000000000000000000000000,
    ...
}

解碼出 $r d$ , $r s 1$ , $r s 2$ 的方式很簡單，把指令集中要解碼的欄位在 bitmask 中設為1其餘設為0，因為 and 運算只有兩者都是1的時候才會得出1其它都是0，如此一來 bitmask 跟指令集做 and 運算就能夠取出特定欄位，接著再將其偏移的長度右移到指令集的最低位即可。

// decode rd field
static inline uint32_t dec_rd(uint32_t inst)
{
    return (inst & FR_RD) >> 7;
}

// decode rs1 field
static inline uint32_t dec_rs1(uint32_t inst)
{
    return (inst & FR_RS1) >> 15;
}

// decode rs2 field
static inline uint32_t dec_rs2(uint32_t inst)
{
    return (inst & FR_RS2) >> 20;
}

以 dec_rd 為例，要取出指令集中 $r d$ 這個欄位，只要跟 FR_RD 做 and 運算後就能將 $r d$ 以外的欄位都清除，接著向右位移7 bit 就可以得出 $r d$

        inst = 0b00111001100101011010111010100010
     & FR_RD = 0b00000000000000000000111110000000
  ---------------------------------------------------
          rd = 0b00000000000000000000111010000000
     rd >> 7 = 0b00000000000000000000000000011101

$r d$ 是運算結果的索引值，運算結果會保存在暫存器中，因為暫存器只有32個，因此 $r d$ 作為索引值只需要指令集中的5 bit 即可表達暫存器中 $0$ 到 $2^{5} - 1$ 的位置。

若要解碼指令集中的 $i m m$ 稍微複雜一些，以 J-type 的指令集為例

inst 跟 FJ_IMM_20 做 and 運算後得出 imm[20] 的位置，再跟 dst 就 or 運算保留結果，接著跟 FJ_IMM_19_12 做 and 運算取出 imm[19:12] 的位置再左移11個 bit 後跟 dst 做 or 運算後會接在 imm[20] 後面，imm[11] 跟 imm[10:1] 依此類推，當 dst 取得所有 imm 後會佔有指令集21個bit的位置，因此要將 imm 左移11個 bit 來得出指令集中的 imm 。

// decode jtype instruction immediate
static inline int32_t dec_jtype_imm(uint32_t inst)
{
    uint32_t dst = 0;
    dst |= (inst & FJ_IMM_20);
    dst |= (inst & FJ_IMM_19_12) << 11;
    dst |= (inst & FJ_IMM_11) << 2;
    dst |= (inst & FJ_IMM_10_1) >> 9;
    // note: shifted to 2nd least significant bit
    return ((int32_t) dst) >> 11;
}

// decode btype instruction immediate
static inline int32_t dec_btype_imm(uint32_t inst)
{
    uint32_t dst = 0;
    dst |= (inst & FB_IMM_12);
    dst |= (inst & FB_IMM_11) << 23;
    dst |= (inst & FB_IMM_10_5) >> 1;
    dst |= (inst & FB_IMM_4_1) << 12;
    // note: shifted to 2nd least significant bit
    return ((int32_t) dst) >> 19;
}

// decode stype instruction immediate
static inline int32_t dec_stype_imm(uint32_t inst)
{
    uint32_t dst = 0;
    dst |= (inst & FS_IMM_11_5);
    dst |= (inst & FS_IMM_4_0) << 13;
    return ((int32_t) dst) >> 20;
}

執行與寫入

由 rv32emu 的 Makefile 得知編譯時有如下的巨集

CFLAGS += -D ENABLE_RV32M
CFLAGS += -D ENABLE_Zicsr
CFLAGS += -D ENABLE_Zifencei
CFLAGS += -D ENABLE_RV32A
CFLAGS += -D ENABLE_RV32C

ENABLE_COMPUTED_GOTO ?= 1
ifeq ("$(ENABLE_COMPUTED_GOTO)", "1")
ifneq ($(filter $(CC), gcc clang),)
riscv.o: CFLAGS += -D ENABLE_COMPUTED_GOTO
	ifeq ("$(CC)", "gcc")
riscv.o: CFLAGS += -fno-gcse -fno-crossjumping 
	endif
endif
endif

其中 ENABLE_COMPUTED_GOTO 表示執行指令集時會編譯使用 computed goto 的程式碼，因此分別說明開啟跟關閉 computed goto 的程式碼。

在 riscv.c 所有對應到指令集模擬的識別符號都以 op_ 開頭，而 computed goto 的語法要在 label 前面新增 &&，使用條件式編譯可以簡單的做出區隔就不用因為要使用 computed goto 而修改程式碼。

#ifdef ENABLE_COMPUTED_GOTO
#define OP(instr) &&op_##instr
#define TABLE_TYPE const void *
#define TABLE_TYPE_RVC const void *
#else  // ENABLE_COMPUTED_GOTO = false
#define OP(instr) op_##instr
#define TABLE_TYPE const opcode_t
#define TABLE_TYPE_RVC const c_opcode_t
#endif

// clang-format off
TABLE_TYPE jump_table[] = {
//  000         001           010        011           100         101        110   111
    OP(load),   OP(load_fp),  OP(unimp), OP(misc_mem), OP(op_imm), OP(auipc), OP(unimp), OP(unimp), // 00
    OP(store),  OP(store_fp), OP(unimp), OP(amo),      OP(op),     OP(lui),   OP(unimp), OP(unimp), // 01
    OP(madd),   OP(msub),     OP(nmsub), OP(nmadd),    OP(fp),     OP(unimp), OP(unimp), OP(unimp), // 10
    OP(branch), OP(jalr),     OP(unimp), OP(jal),      OP(system), OP(unimp), OP(unimp), OP(unimp), // 11
};

jump_table 依據規格書的 opcode map 的順序以及函式名稱整理出來的，row 是取出 opcode 的2到4碼( $i n s t [4 : 2]$ )，column 是取出 opcode 的5到6碼( $i n s t [6 : 5]$ )，因此 opcode map
的索引值就是指令的2到6碼即 $i n s t [6 : 2]$ ，例如 AMO 的索引值是 11 也就是 $\underset{i n s t [6 : 5]}{\underset{⏟}{01}} \underset{i n s t [4 : 2]}{\underset{⏟}{011}}$ ，而 AMO 要執行的指令則可以透過 $i n s t [6 : 2]$ 來看規格書查表，像是 LR.W, SC.W, AMOSWAP.W, etc.

							opcode	inst
00010	aq	rl	00000	rs1	010	rd	0101111	LR.W
00011	aq	rl	rs2	rs1	010	rd	0101111	SC.W
00001	aq	rl	rs2	rs1	010	rd	0101111	AMOSWAP.W

#ifdef ENABLE_RV32C
    TABLE_TYPE_RVC jump_table_rvc[] = {
    //  00             01             10          11
        OP(caddi4spn), OP(caddi),     OP(cslli),  OP(unimp),  // 000
        OP(cfld),      OP(cjal),      OP(cfldsp), OP(unimp),  // 001
        OP(clw),       OP(cli),       OP(clwsp),  OP(unimp),  // 010
        OP(cflw),      OP(clui),      OP(cflwsp), OP(unimp),  // 011
        OP(unimp),     OP(cmisc_alu), OP(ccr),    OP(unimp),  // 100
        OP(cfsd),      OP(cj),        OP(cfsdsp), OP(unimp),  // 101
        OP(csw),       OP(cbeqz),     OP(cswsp),  OP(unimp),  // 110
        OP(cfsw),      OP(cbnez),     OP(cfswsp), OP(unimp),  // 111
    };
#endif

jump_table_rvc 跟 jump_table 一樣也是按造規格書整理出來的，行跟列的存取原理相同。差別在於 jump_table_rvc 是整理壓縮指令集的表格，壓縮指令集的長度只有一般指令集的一半，另外要顧及陣列的存取順序以及可讀性，所以依照指令集小的位元去排，因此 jump_table_rvc 每4個就切換到下一列。

關閉 Computed goto

當擷取到指令之後要先判斷是不是壓縮指令集，32位元指令集的最後兩位是11，而壓縮指令集最後兩位可以是 00, 01, 10，因此只要判斷指令的最後兩位就可以區分開來，利用 3(0b11) 取出最低2位就能知道是不是一般指令集了。

當分辨完指令集之後的第一件事就是去找出它的 index，如果是一般指令集，只要取出 $i n s t [6 : 2]$ 就可以了，用 bitmask 取出之後要位移到最低位才是正確的索引值，接著用 index 對 jump_table 查表再去執行 op，同時在 op 函式內更新現在執行的位置(PC)，多數的 op 都是 PC 加上指令長度，因為執行的時候會讀取一道指令的長度，所以執行完畢後要讀取下一道指令就要把位置往前移動一個指令長度才能存取，也有少數指令是修改 PC 的位置，比如說跳躍跟分支。

執行完 op 如果有問題就離開迴圈，也相當於結束 rv_step，反之如果執行成功就更新指令集長度，這是為了更新下一次的 PC，32 位元的指令集是 4 byte 因此 INST_32 是4，當執行完畢之後表示已完成一個指令周期，因次 csr_cycle 加一，接著進行下一輪指令周期，直到比 cycle_target 還要大為止。

壓縮指令集只有 16 bit 的長度，因此先用 0x0000FFFF 把指令的16位給過濾出來，而壓縮指令集的 op map 的索引值是依據 $i n s t [1 : 0]$ 跟 $i n s t [15 : 13]$ ，要將 $i n s t [15 : 13]$ 取出後向左位移11 bit 再跟最後兩位做 or 運算的時候才不會重疊又能取得正確的索引值。

void rv_step(struct riscv_t *rv, int32_t cycles)
{
    assert(rv);
    const uint64_t cycles_target = rv->csr_cycle + cycles;
    uint32_t inst;
    
    // TABLE_TYPE jump_table[] = { ... };
    
    while (rv->csr_cycle < cycles_target && !rv->halt) {
        // fetch the next instruction
        inst = rv->io.mem_ifetch(rv, rv->PC);

        // standard uncompressed instruction
        if ((inst & 3) == 3) {
            uint32_t index = (inst & INST_6_2) >> 2;

            // dispatch this opcode
            TABLE_TYPE op = jump_table[index];
            assert(op);
            if (!op(rv, inst))
                break;
            rv->inst_len = INST_32;

        } else {
            // standard compressed instruction
            inst &= 0x0000FFFF;
            const uint16_t c_index =
                (inst & FC_FUNC3 >> 11) | (inst & FC_OPCODE);

            // dispactch c_opcode (compressed instructions)
            TABLE_TYPE_RVC op = jump_table_rvc[c_index];
            assert(op);
            if (!op(rv, inst))
                break;
            rv->inst_len = INST_16;
        }
        
        // increment the cycles csr
        rv->csr_cycle++;
    }
}

開啟 Computed goto

預先定義好的 macro

#ifdef ENABLE_COMPUTED_GOTO
#define OP(instr) &&op_##instr
#else
#define OP(instr) op_##instr

#define DISPATCH_RV32C()                                            \
    inst &= 0x0000FFFF;                                             \
    int16_t c_index = (inst & FC_FUNC3) >> 11 | (inst & FC_OPCODE); \
    rv->inst_len = INST_16;                                         \
    goto *jump_table_rvc[c_index];
#else

#define DISPATCH()                                      \
{                                                   \
    if (rv->csr_cycle >= cycles_target || rv->halt) \
        return;                                  \
    /* fetch the next instruction */                \
    inst = rv->io.mem_ifetch(rv, rv->PC);           \
    /* standard uncompressed instruction */         \
    if ((inst & 3) == 3) {                          \
        uint32_t index = (inst & INST_6_2) >> 2;    \
        rv->inst_len = INST_32;                     \
        goto *jump_table[index];                    \
    } else {                                        \
        /* Compressed Extension Instruction */      \
        DISPATCH_RV32C()                            \
    }                                               \
}

#define EXEC(instr)                    \
{                                  \
    /* dispatch this opcode */     \
    if (!op_##instr(rv, inst))     \
        return;                 \
    /* increment the cycles csr */ \
    rv->csr_cycle++;               \
}
    
#define TARGET(instr)         \
    op_##instr : EXEC(instr); \
    DISPATCH();

void rv_step(struct riscv_t *rv, int32_t cycles) {
    assert(rv);
    const uint64_t cycles_target = rv->csr_cycle + cycles;
    uint32_t inst;
    
    // TABLE_TYPE jump_table[] = {...};
    // TABLE_TYPE jump_table_rvc[] = {...};
    DISPATCH();

    // main loop
    TARGET(load)
    TARGET(op_imm)
    TARGET(auipc)
    TARGET(store)
    TARGET(op)
    TARGET(lui)
    TARGET(branch)
    TARGET(jalr)
    TARGET(jal)
    TARGET(system)
#ifdef ENABLE_RV32C
    TARGET(caddi4spn)
    TARGET(caddi)
    TARGET(cslli)
    TARGET(cjal)
    TARGET(clw)
    TARGET(cli)
    TARGET(clwsp)
    TARGET(clui)
    TARGET(cmisc_alu)
    TARGET(ccr)
    TARGET(cj)
    TARGET(csw)
    TARGET(cbeqz)
    TARGET(cswsp)
    TARGET(cbnez)
#endif
#ifdef ENABLE_Zifencei
    TARGET(misc_mem)
#endif
#ifdef ENABLE_RV32A
    TARGET(amo)
#endif
    TARGET(unimp)
}

JIT 編譯器

MIR

mir 的意思是 Medium Internal Representation，如同函式庫所表達的意思一樣，mir 提供一系列基本的函式也可以用不同的語言當作輸入再轉成 MIR 接著優化後再編譯成特定平台的機器語言，也可以直接當成函式來呼叫，這樣便能讓開發者方便的實做出直譯器或是 JIT 編譯器。

mir 目前能做到的功能如下圖所示，可以自己寫 MIR 或是 C 語言當作輸入再輸出 MIR 或是編譯成特定平台的機器碼。

如果用 MIR 的函式去實作功能的話程式碼會變的很多且不易閱讀，因此以 C 語言的程式碼當作輸入再去編譯會簡單很多。

mir API 介紹

Code Generation

雖然能執行了，但目前還在嘗試的實驗階段，之後還會再更新成正式版筆記。

若要運行請使用 jit 的分支。

先來觀察 rv_step 執行 op 的部份，jump table 的 op 函式已經把要執行的指令歸類在一起，op 又可以從 index 得知，因此可以從 index 跟 inst 來得知要用哪種類型的解碼方式跟指令，也就可以針對指令生成程式碼讓 c2mir 來編譯。

while (rv->csr_cycle < cycles_target && !rv->halt) {
    // fetch the next instruction
    inst = rv->io.mem_ifetch(rv, rv->PC);

    // standard uncompressed instruction
    if ((inst & 3) == 3) {
        uint32_t index = (inst & INST_6_2) >> 2;

        // dispatch this opcode
        TABLE_TYPE op = jump_table[index];
        assert(op);
        if (!op(rv, inst))
            break;
        rv->inst_len = INST_32;
    } 
}

仔細觀察 op 後或許可以搭配 macro 將常用到的部分簡化成輸入 code 的模板就可以生成整個 op 的字串又不失可讀性，因此參考 LuaJIT-5.3.6 的方式先定義 CODE 用來寫入程式碼到 buffer，有了這個像原子一樣最基礎的 macro 就可以衍生出不同的模板來重複使用，如此就能大幅簡化 codegen 實作。

void str2buffer(rv_buffer *buffer, const char *fmt, ...)
{
    va_list args;
    char code[1024];
    va_start(args, fmt);
    int n = vsnprintf(code, sizeof(code), fmt, args);

    va_end(args);
    if (n < 0)
        abort();
    size_t len = strlen(code);
    size_t new_size = buffer->size + len;
    if (new_size > buffer->capacity) {
        buffer->src = realloc(buffer->src, new_size);
        buffer->capacity = new_size;
    }
    strncpy(&buffer->src[buffer->size], code, len);
    buffer->size = new_size;
}

#define CODE(fmt, ...) str2buffer(buff, fmt, ##__VA_ARGS__)

觀察除 RV32C 用到的 OP 之外後初步設計的模板，這部份我認為還有很大的改進空間，希望之後可以像 ravi 或是 LuaJIT-5.3.6 一樣包裝到簡單又直覺。


#define DECLEAR_FUNC(name) \
    CODE("bool %s(struct riscv_t *rv, uint32_t inst) {\n", name)
#define END_FUNC CODE("return true;}\n")
#define DEC_RD CODE("const uint32_t rd = dec_rd(inst);\n")
#define DEC_RS1 CODE("const uint32_t rs1 = dec_rs1(inst);\n")
#define DEC_RS2 CODE("const uint32_t rs2 = dec_rs2(inst);\n")
#define DEC_FUNCT3 CODE("const uint32_t funct3 = dec_funct3(inst);\n")
#define DEC_FUNCT7 CODE("const uint32_t funct7 = dec_funct7(inst);\n")
#define DEC_U_IMM CODE("const int32_t imm = dec_utype_imm(inst);\n")
#define DEC_J_IMM CODE("const int32_t imm = dec_jtype_imm(inst);\n")
#define DEC_I_IMM CODE("const int32_t imm = dec_itype_imm(inst);\n")
#define DEC_B_IMM CODE("const int32_t imm = dec_btype_imm(inst);\n")
#define DEC_S_IMM CODE("const int32_t imm = dec_stype_imm(inst);\n")
#define SWITCH(val) CODE("switch(%s) {\n", val)
#define CASE(val) CODE("case %s: \n", val)
#define END CODE("}\n")
#define UPDATE_PC(val) CODE("rv->PC += %s;\n", val)
#define ENFORCE_ZERO CODE("if (rd == rv_reg_zero)\n rv->X[rv_reg_zero] = 0;\n")
#define LOAD_ADDR(reg) CODE("const uint32_t addr = rv->X[%s] + imm;", reg)
#define RV_DATA CODE("const uint32_t data = rv->X[rs2];\n")

#define inst_misaligned CODE("rv_except_inst_misaligned(rv, pc);\n");

#define load_misaligned(num)        \
    CODE("if(addr & %d) {\n", num); \
    CODE("rv_except_load_misaligned(rv, addr);return false; }\n");

#define store_misaligned(num)       \
    CODE("if(addr & %s) {\n", num); \
    CODE(" rv_except_store_misaligned(rv, addr);\n return false; }\n");

#define illegal_inst CODE("rv_except_illegal_inst(rv, inst); return false;\n")

#define _OP_UNIMP             \
    DECLEAR_FUNC("op_unimp"); \
    illegal_inst;             \
    END;

有了模板之後就按造 op 來生成程式碼，生成程式碼的部份用 enum 按造 jump_table 設定索引值，這樣只要 switch(index) 就知道要生成哪個 op 函式，由於 system 會跟內建函式有衝突，固改成 op_system。

enum {
    load = 0b00000,
    load_fp = 0b00001,
    misc_mem = 0b00011,
    op_imm = 0b00100,
    auipc = 0b00101,

    store = 0b01000,
    store_fp = 0b01001,
    amo = 0b01011,
    op = 0b01100,
    lui = 0b01101,

    madd = 0b10000,
    msub = 0b10001,
    nmsub = 0b10010,
    nmadd = 0b10011,
    fp = 0b10100,

    branch = 0b11000,
    jalr = 0b11001,
    jal = 0b11011,
    op_system = 0b11100,
};

codegen 搭配 enum 的索引值，來分配要生成的 op，為了要讓 c2mir 可以順利編譯，因此在生成 op 前先將模板給寫入到 buffer，模板包括了 riscv_t 的原型、typedef 的型別，為了避免編譯的時候找不到定義而失敗。

jump table 中有些函式還沒有實作出來(e.g. load_fp)，所以都先生成 op_unimp，當 index 不慎呼叫到沒實作的 op，就會發生例外。

由於 codegen 的程式碼很長，這裡以 auipc 舉例，其他的 op 函式依此類推。

static bool op_auipc(struct riscv_t *rv, uint32_t inst)
{
    // u-type decode
    const uint32_t rd = dec_rd(inst);
    const uint32_t val = dec_utype_imm(inst) + rv->PC;
    rv->X[rd] = val;

    // step over instruction
    rv->PC += rv->inst_len;

    // enforce zero register
    if (rd == rv_reg_zero)
        rv->X[rv_reg_zero] = 0;
    return true;
}

op_auipc 用設計好的 macro 模板來寫的話則如下所示

void jit_codegen(rv_buffer *buff, int32_t index) {
    size_t tem_len = strlen(template);
    strncpy(buff->src, template, tem_len);
    buff->size += tem_len;

    switch(index) {
        case auipc:
            DECLEAR_FUNC("auipc");
            DEC_RD;
            CODE("const uint32_t val = dec_utype_imm(inst) + rv->PC;");
            CODE("rv->X[rd] = val;");
            UPDATE_PC("rv->inst_len");

            CODE("if (rd == rv_reg_zero) rv->X[rv_reg_zero] = 0;");
            END_FUNC;
            break;
        case store:
            // ...
        case fp:
        case store_fp:
        case load_fp:
        case madd:
        case msub:
        case nmsub:
        case nmadd:
            _OP_UNIMP;
        break;
        default:
            _OP_UNIMP;
    }
}

c2mir 編譯

當 codegen 完成之後便交給 c2mir 來編譯成可呼叫的機械碼，經過 c2mir_compile 的 module 會新增在 jit->ctx 的雙向鏈結串列的尾端，因此要透過 DLIST_TAIL 取出，接著再從 module->items 的 list 找出編譯完的 op 函式，有找到就回傳編譯完的函式否則就回傳 NULL mir_func 給，最後再結束 generator 跟 c2mir。

opcode_t jit_compile(rv_jit *jit, uint32_t index)
{
    c2mir_init(jit->ctx);
    MIR_gen_init(jit->ctx, 0);
    MIR_gen_set_optimize_level(jit->ctx, 0, 3);
    char op_name[20];
    snprintf(op_name, 20, "jit_func_%d", ++jit->count);
    size_t tem_size = strlen(template);
    const size_t n = tem_size + 4096;
    
    // initial buffer
    rv_buffer *code = malloc(sizeof(rv_buffer));
    code->src = (char *) malloc(n);
    code->capacity = n;
    code->size = 0;
    code->cur = 0;
    // codegen and compile
    jit_codegen(code, index);

    if (!c2mir_compile(jit->ctx, jit->options, getc_func, code, op_name,
                       NULL)) {
        perror("can't compile\n");
        return NULL;
    }
    free(code->src);
    free(code);
    
    // find module and generate machine code
    MIR_module_t module =
        DLIST_TAIL(MIR_module_t, *MIR_get_module_list(jit->ctx));
    MIR_load_module(jit->ctx, module);
    MIR_link(jit->ctx, MIR_set_gen_interface, import_solver);
    MIR_item_t mir_func = DLIST_HEAD(MIR_item_t, module->items);
    while (mir_func) {
        if (mir_func->item_type == MIR_func_item) {
            break;
        }
        mir_func = DLIST_NEXT(MIR_item_t, mir_func);
    }
    
    opcode_t op_func = mir_func? MIR_gen(jit->ctx, 0, mir_func): NULL;
    MIR_gen_finish(jit->ctx);
    c2mir_finish(jit->ctx);
    
    return op_func;
}

能夠動態生成 machine code 後接著寫個簡單 jit 版的 rv_step，為了避免不段的編譯完才執行這種會拖慢速度的方式，於是使用陣列當作快取，畢竟只有 32 個 op 而且 index 不會超出範圍，使用陣列來查表只要 $O (1)$ 即可讀取。

void rv_jit_step(struct riscv_t *rv, rv_jit *jit, int32_t cycles)
{
    assert(rv);
    const uint64_t cycles_target = rv->csr_cycle + cycles;

    while (rv->csr_cycle < cycles_target && !rv->halt) {
        // fetch the next instruction
        uint32_t inst = rv->io.mem_ifetch(rv, rv->PC);

        // standard uncompressed instruction
        if ((inst & 3) == 3) {
            uint32_t index = (inst & INST_6_2) >> 2;
            if (!jit->cache[index]) {
                jit->cache[index] = jit_compile(jit, index);
            }
            opcode_t op = jit->cache[index];
            assert(op);
            if (!op(rv, inst))
                break;
            rv->inst_len = INST_32;
        }
        // increment the cycles csr
        rv->csr_cycle++;
    }
}

使用 make check 確保可以執行。

> make check
(cd build; ../build/rv32emu hello.elf)
jit_func_7:67:1: warning -- incompatible argument type for pointer type parameter
jit_func_7:71:1: warning -- incompatible argument type for pointer type parameter
jit_func_7:75:1: warning -- incompatible argument type for pointer type parameter
Hello World!
inferior exit code 0
(cd build; ../build/rv32emu puzzle.elf)
jit_func_8:77:13: warning -- incompatible argument type for pointer type parameter
jit_func_10:69:1: warning -- incompatible argument type for pointer type parameter
jit_func_10:70:1: warning -- incompatible argument type for pointer type parameter
success in 2005 trials
inferior exit code 0

Tracing JIT

把每個 op 分別用 JIT 編譯，這樣的作法速度並不快很多時候甚至比沒有 JIT 編譯還要慢，應改成追蹤程式在執行時期的資訊，例如哪些函式呼叫的很頻繁，迴圈執行的次數是否夠多，如果超過一定的閥值(threshold)，就追蹤這些熱點，並把這些熱點的指令紀錄下來透過 JIT 編譯，等到下次要執行的時候就換成執行 JIT 最佳化的機械碼，這樣的作法又稱為 Tracing JIT compilation，以下簡稱 Tracing JIT。

Tracing JIT 基於以下假設:

程式的執行時間大部份都花在迴圈
迴圈每次都有相似的執行路徑

Tracing JIT 有下面幾個步驟:

profile
找出程式中執行頻繁的熱點，紀錄 jump 發生次數超過一定的閥值就進入追蹤階段
tracing
當程式執行到熱點的時候紀錄執行的指令，這裡要考慮的情況很多，像是如下 case
- 巢狀迴圈、分支
- break / continue
- 結合上述兩點的情況
  以下論文提到藉由 Trace tree 跟 Control flow graph (CFG) 來紀錄指令，兩者相同的地方都是透過走訪來得到 Hot path。
- Trace tree / 簡報
- Dynamo $\to$ 第一個實做出 tracing jit
- HotpathVM: An Effective JIT Compiler for Resource-constrained Devices
- TigerShrimp: An Understandable Tracing JIT Compiler
compile and optimize
簡單的方式是逐一指令以 codegen 產生機械碼 $\to$ RVVM
複雜一點的則是生成 IR 來優化再編譯成機械碼 $\to$ MIR
execute code
當程式執行到同樣的地方時，換成執行 JIT 編譯後的機械碼

RVVM 也有只自己的 tracing jit，不過並沒有做 profile 而是一邊執行一邊做 tracing 跟 codegen，編譯完後等下次執行到同個地方時執行機械碼

實作概念介紹

暫時想不到如何用 Trace tree 或 Control flow graph 來處理複雜的 case，只能用相對簡單的作法來解決，這個作法藉由觀察組語跟聯想 RVVM JIT 以及 Tracing JIT 的概念才想出來的，沒那麼優雅但簡單。

無論是巢狀迴圈，還是巢狀迴圈內有多個分支或是有 break / continue 在迴圈，這些都由分支決定執行方向，因此可以改成紀錄分支發生的次數，超過閥值就開始追蹤，不只要追蹤 if 的區塊，else 也是潛在的熱點，一旦開始追蹤就追到下個分支出現就停止，當程式執行久了，就可以涵蓋到多數的熱點。

用機率的大數法則來解釋，這些熱點就是執行機率高的分佈，剛開始這些熱點並不明顯，但只要程式執行的愈久，這些熱點就會愈加明顯，而閥值決定誰要被最佳化，這是靜態編譯所做不到的。

以第4行的 blt 為例，如果條件滿足就跳躍到 .LBB1_6 開始執行，不然就執行下一道指令 j .LBB1_4，所以兩邊都有可能是熱點，執行到 PC + Offset 跟 PC + 4 的位址都要計數，超過閥值就開始追蹤。

blt x5 x6 offset $\to$ if(x5 < x6) goto PC + offset



















.LBB1_3:                                
    lw      a1, -24(s0)
    li      a0, 10                      # PC - 4
    blt     a0, a1, .LBB1_6             # PC
    j       .LBB1_4                     # PC + 4
.LBB1_4:                                
    lw      a0, -20(s0)
    lw      a1, -24(s0)
    add     a0, a0, a1
    call    my_func
    mv      a1, a0
    lw      a0, -16(s0)
    add     a0, a0, a1
.LBB1_6:                                # PC + offset
    lw      a0, -16(s0)
    lw      ra, 28(sp)                  
    lw      s0, 24(sp)                  
    addi    sp, sp, 32
    ret

這種作法的缺點會有很多 hot path 要快取，所以 hot path 太短就放棄追蹤，這樣在一定程度上可以減少記憶體開銷。

實作

程式開始執行 rv_step 時就紀錄指令直到遇到 branch 跟 jalr，前者不確定程式選擇的執行路徑，後者則是執行的過程中會修改到暫存器，故無法確定程式會跳躍到哪個地址，所以遇到這兩種指令時就停止紀錄，這些紀錄起來的指令就是 basic block，經過 c2mir 編譯之後把 block 存到 hash table 作為快取等到下次執行時就呼叫編譯好的 block，因為 block 是連續執行沒有出現分支，所以執行完直接將指令的數量更新到 cycle 的暫存器即可。

此外，執行 block_find_or_translate 時會將下一塊 block 存入到 predict，使用預測的方式來降低查訊快取的次數。

void rv_step(struct riscv_t *rv, int32_t cycles)
{
    /* find or translate a block for our starting PC */
    struct block_t *prev = NULL;

    const uint64_t cycles_start = rv->csr_cycle;
    const uint64_t cycles_target = rv->csr_cycle + cycles;

    /* loop until we hit out cycle target */
    while (rv->csr_cycle < cycles_target && !rv->halt) {
        const uint32_t pc = rv->PC;
        struct block_t *block;
        /* try to predict the next block */
        if (prev && prev->predict && prev->predict->pc_start == pc) {
            block = block->predict;
        } else {
            /* lookup the next block in block map or translate a new block,
             * and move onto the next block */
            block = block_find_or_translate(rv, prev);
        }
        /* we should have a block by now */
        assert(block);

        /* if this block has no instructions we cant make forward progress so
         * must fallback to instruction emulation
         */
        if (!block->instructions) {
            assert(!"unable to execute empty block");
        }

        /* call the translated block */
        call_block_t c = (call_block_t) block->func;
        c(rv);

        /* increment the cycles csr */
        rv->csr_cycle += block->instructions;
        prev = block;
    }
}

struct block_t *block_find_or_translate(struct riscv_t *rv,
                                        struct block_t *prev)
{
    /* lookup the next block in the block map */
    struct block_t *next = block_find(rv->jit->block_map, rv->PC);
    struct block_map_t *block_map = rv->jit->block_map;

    /* translate if we did not find one */
    if (!next) {
        if (block_map->size * 1.25 > block_map->capacity) {
            block_map_clear(block_map);
            prev = NULL;
        }

        next = block_alloc();
        assert(next);
        rv_translate_block(rv, next);
        block_finish(rv, next);

        /* update the block predictor
         *
         * If the block predictor gives us a win when we
         * translate a new block but gives us a huge penalty when
         * updated after we find a new block.  did not expect that.
         */
        if (prev)
            prev->predict = next;
    }
    assert(next);
    return next;
}

block 初始化之後開始紀錄指令，透過 decode 來得知是指令的類型，同時更新 pc_end 這樣才能再之後提取下一道指令，並將指令存到 code 裡面，更新指令數量，如果滿了就 realloc，多配置 20 道指令的空間來持續紀錄指令。

static void rv_translate_block(struct riscv_t *rv, struct block_t *block)
{
    assert(rv && block);
    /* setup the basic block */
    block->instructions = 0;
    block->pc_start = rv->PC;
    block->pc_end = rv->PC;

    /* translate the basic block */
    for (;;) {
        /* fetch the next instruction */
        const uint32_t insn = rv->io.mem_ifetch(rv, block->pc_end);
        const uint32_t index = (insn & INSN_6_2) >> 2;

        decode(rv, insn, rv->jit->insn_len, &block->pc_end);
        rv->jit->insn_len = INSN_32;

        if (block->instructions >= block->code_capacity) {
            break;
            block->code_capacity += 20;
            block->code =
                realloc(block->code, sizeof(uint32_t *) * block->code_capacity);
        }
        block->code[block->instructions++] = insn;
        /* stop on branch and jalr */
        if (index == op_branch || index == op_jalr) {
            break;
        }
    }
}

指令紀錄好之後交由 block_finish 編譯成機械碼。初始化 c2mir 跟設定優化等級之後就準備 codegen，把一道道指令轉成 C 字串，先格式化函式名稱 jit_func_{PC}_{instructions}，這麼做是為了之後載入 MIR 快取時能夠設定 block 的起始地址跟數量，之後初始化 buffer 完便開使 codegen，把模板、函式名稱、指令寫入到 buffer 的 source 裡。

codegen 完就可以將 buffer 透過 c2mir_compile，編譯成 MIR module 新增到 module list 的尾端，取得 module 之後要載入跟連結才能夠生成可執行的機械碼，之後就從 module 找出編譯完的函式，DLIST_ITEM_FOREACH 是從 linux list 學到的技巧，MIR 並未提供這個巨集，module 有很多種類型的 item，編譯好的機械碼屬於 MIR_func_item，但 module 可能有其他的 function item，所以還要比對函式名稱才能正確取得要執行的 JIT 函式。

有了 JIT 函式就能用 MIR_gen 生成機械碼到 block，之後結束 c2mir 跟 generator，等下次要編譯再開啟，而編譯好的 block 就插入到 hash table 等待執行。

因篇幅問題，刪除小部份程式碼

static void block_finish(struct riscv_t *rv, struct block_t *block)
{
    struct riscv_jit_t *jit = rv->jit;
    c2mir_init(jit->ctx);
    size_t gen_num = 0;
    MIR_gen_init(jit->ctx, gen_num);
    MIR_gen_set_optimize_level(jit->ctx, gen_num, 3);

    char func_name[25];
    snprintf(func_name, 25, "jit_func_%d_%d", block->pc_start,
             block->instructions);

    size_t tem_size = sizeof(template) - 1;
    const size_t n = tem_size + 4096;
    rv_buffer *buffer = malloc(sizeof(rv_buffer));
    buffer->src = (char *) malloc(n);
    buffer->capacity = n;
    buffer->size = 0;
    buffer->cur = 0;

    jit_codegen(buffer, func_name, block, rv);
    int ret = c2mir_compile(jit->ctx, jit->options, getc_func, buffer,
                            func_name, NULL);
    assert(ret);
    free(buffer->src);
    free(buffer);

    MIR_module_t module =
        DLIST_TAIL(MIR_module_t, *MIR_get_module_list(jit->ctx));
    MIR_load_module(jit->ctx, module);
    MIR_link(jit->ctx, MIR_set_gen_interface, import_solver);

    MIR_item_t mir_func;
    DLIST_ITEM_FOREACH (module, mir_func) {
        if (mir_func->item_type == MIR_func_item &&
            !strcmp(mir_func->u.func->name, func_name)) {
            break;
        }
    }
    assert(mir_func);
    block->func = MIR_gen(jit->ctx, gen_num, mir_func);

    MIR_gen_finish(jit->ctx);
    c2mir_finish(jit->ctx);

    /* insert new block into block map */
    block_map_insert(jit->block_map, block);
}

c2mir_compile(jit->ctx, jit->options, getc_func, buffer, func_name, NULL) 的參數 getc_func 如下，其中 data 就是就是 c2mir_compile 的 buffer，這個函式會一個字一個字的回傳，直到結束為止，因為編譯的過程中要做詞法分析將 token 標注屬性。

static int getc_func(void *data)
{
    rv_buffer *buffer = data;
    return buffer->cur >= buffer->size ? EOF : buffer->src[buffer->cur++];
}

codegen 的部份先將模板跟函式名稱寫入到 buffer，之後將紀錄到的指令依序生成 C 語言。得益於c2mir，不必徒手撰寫機械碼，codegen 實作流程簡化成下面的步驟

複製貼上
用 CODE 跟其它巨集小改程式即可
預先解碼指令的欄位
代入參數到格式化字串

以 emit_load 為例，幾乎跟 op_load 一樣，只要複製貼上，再去帶入參數到格式化的字串，不過要注意的地方除了細心之外，還有 rv_step 執行完執令之後會去更新指令長度，codegen 也要做同樣的事，這樣才會跟原來的程式的行為是一樣的。

由於指令執行的過程中不會改變，會變的只有暫存器，所以在 codegen 的時候可以先解碼在代入參數到字串，做到 constant folding 的最佳化。

static void emit_load(rv_buffer *buff, uint32_t insn, struct riscv_t *rv UNUSED)
{
    const int32_t imm = dec_itype_imm(insn);
    const uint32_t rs1 = dec_rs1(insn);
    const uint32_t funct3 = dec_funct3(insn);
    const uint32_t rd = dec_rd(insn);

    /* load address */
    LOAD_ADDR;
    bool end = true;
    switch (funct3) {
    case 0: /* LB */
        COMMENT("LB");
        CODE("rv->X[%u] = sign_extend_b(rv->io.mem_read_b(rv, addr));\n", rd);
        goto update;
    case 1: /* LH */
        COMMENT("LH");
        load_misaligned(1);
        CODE(
            "else {\nrv->X[%u] = sign_extend_h(rv->io.mem_read_s(rv, addr));\n",
            rd);
        end = false;
        goto update;
    case 2: /* LW */
        COMMENT("LW");
        load_misaligned(3);
        CODE("else {\nrv->X[%u] = rv->io.mem_read_w(rv, addr);\n", rd);
        end = false;
        goto update;
    case 4: /* LBU */
        COMMENT("LBU");
        CODE("rv->X[%u] = rv->io.mem_read_b(rv, addr);\n", rd);
        goto update;
    case 5: /* LHU */
        COMMENT("LHU");
        load_misaligned(1);
        CODE("else {\nrv->X[%u] = rv->io.mem_read_s(rv, addr);\n", rd);
        end = false;
        goto update;
    default:
        illegal_insn;
        return;
    }
update:
    CODE("rv->PC += rv->insn_len;\n");
    UPDATE_INSN32_LEN;

    if (!end)
        END;
}

jit_codegen 的實作，index 跟要生成 op 是一對一的關係，可以用 switch 寫的話，那也就可以改寫成 computed-goto 來加速，跟 rv_step 一樣先呼叫 DISPATCH 來觸發後面一系列的 codegen 函式。

DISPATCH: 將指令轉成對應的索引值，接著 goto 到指定的 label
TARGET: 執行完 codegen 之後，接著呼叫 DISPATCH 分發到下一道指令

static void jit_codegen(rv_buffer *buff,
                        char *func_name,
                        struct block_t *block,
                        struct riscv_t *rv)
{
    size_t tem_len = sizeof(template) - 1;
    strncpy(buff->src, template, tem_len);
    buff->size += tem_len;
    uint32_t *insns = block->code;
    DECLARE_FUNC(func_name);
    DECLARE_VAR;
    
#define emit(op) &&emit_##op

#define DISPATCH()                          \
    {                                       \
        if (i < block->instructions) {      \
            insn = insns[i++];              \
            index = (insn & INSN_6_2) >> 2; \
            goto *emit_table[index];        \
        } else {                            \
            END;                            \
            return;                         \
        }                                   \
    }
#define TARGET(op)                             \
    {                                          \
        emit_##op : emit_##op(buff, insn, rv); \
        DISPATCH();                            \
    }

    void *emit_table[] = {
        [op_load] = emit(load),     [op_misc_mem] = emit(misc_mem),
        [op_op_imm] = emit(op_imm), [op_auipc] = emit(auipc),
        [op_store] = emit(store),   [op_amo] = emit(amo),
        [op_op] = emit(op),         [op_lui] = emit(lui),
        [op_branch] = emit(branch), [op_jalr] = emit(jalr),
        [op_jal] = emit(jal),       [_op_system] = emit(op_system),
    };
    uint32_t i = 0;
    uint32_t insn, index;

    DISPATCH();

    TARGET(load);
    TARGET(misc_mem);
    TARGET(op_imm);
    TARGET(auipc);
    TARGET(store);
    TARGET(amo);
    TARGET(op);
    TARGET(lui);
    TARGET(branch);
    TARGET(jalr);
    TARGET(jal);
    TARGET(op_system);
}

後續改進事項

引入編譯器優化的技術

現階段已實作出相當初階的 JIT 編譯器，實作簡單易懂，還能處理複雜的 if-else，但存在若干缺點

記錄到的指令數量太少
建立 block 紀錄指令的過程遇到分支或跳耀的指令就會結束，這導致 block 記錄到的指令數量不多，如果分支跟跳耀的指令數量一多，就會建立更多的 block，這意味著在更頻繁的函式呼叫與 JIT 編譯。
執行效率不佳
即便在 codegen 的階段提前解碼指令的欄位，但是每次編譯的指令數量不多，這使得函式呼叫的成本不划算，即便有 Hash table 以及 prediction 的最佳化策略，改進仍有限。

Control-Flow Graph

要從根本上解決問題就要從編譯器的知識著手，目前能夠建立 basic block，下一步則按造執行流程將每一塊 block 連接成 Control-Flow Graph(CFG)，透過走訪 CFG 來做 C 語言的 codegen 再交由 c2mir 編譯，如此一來便能夠編譯大量的指令做更激進的最佳化。

codegen 的部分會透過走訪 CFG 來生成程式碼，所以走訪的路徑要跟程式執行的路徑一樣，所以這時候不能用圖 BFS 或是 DFS，而是要找出 block 間的支配(dominate)關系，由 immediate dominator 建構 dominator tree，再透過先序走訪(pre-order) 才會是程式的執行路徑

Dominator tree

支配關系的表示法如下

$D O M (n) = {\begin{cases} {n} & if n = n 0 \\ {n} \cup (⋂_{p \in p r e d s (n)} D O M (p)) & if n \neq n 0 \end{cases}$

如果節點 $n$ 不是初始節點 $n_{0}$ 則為 n 之前的 Dom 節點跟自己的聯集

注意，節點的 DOM 有好幾個，但是 IDOM 只有一個。

Dominator (graph theory)

關於 DOM 與建構 dominator tree 都可以在《Engineering a Compiler》作者的這篇論文找到演算法的細節。
A Simple, Fast Dominance Algorithm
圖論相關知識: reverse postorder(topological sort)

依照論文提到的建立支配樹的實作可以參考 ravi-compiler，其中 cfg.c 還包含輸出 graphviz script 的函式來檢視建立的 CFG。其中關於 graph 的實做可以參考 Bob Morgan 的《Building an Optimizing Compiler》

Codegen 優化

因為是用 MIR，將 RISC-V 指令轉成 C 字串給編譯器優化，所以在優化 C 字串可以思考以下的方案

當建立好 CFG 之後，如果遇到迴圈或是 go back 可能會重複產生一樣的 block，因為所有 block 都是寫在函式裡面，所以能用 goto 解決重複產生 block 的問題
參閱 rv32emu 改進方案
有的指令會需要用到額外的變數，有的則不用，目前的做法是把所有會用到的變數都先宣告好，再交由 MIR 做 deadcode eliminate，可以改成如果需要額外的變數就先標記，等指令都 codegen 完再生成必要的額外變數，減少編譯器優化的成本。

LRU 快取

目前的實作是使用 hashmap 來保存編譯的 basic block 但是程式執行到後期，之前生成的 block 未必會頻繁執行，亦即成為過期的快取，因此可以改成使用 LRU 快取淘汰策略來保存最近使用到的 block，這些 block 可以視為程式的熱點。

bitmap

目前的 hashmap 儲存 block 的數量達到 hashmap 使用空間的 80% 便會清空，但是清除 block 的方式是走訪每一個 entry，這樣很沒效率，應改用 bitmap 紀錄索引，再用 clz 找出索引值。