rv32emu 改進方案

issues

過多 block

每個 block 紀錄到的指令數量有多有少，執行頻率也不一樣，最遭的情況是指令多的執行1次，指令少的執行很多次。

解法： 合併 block
以 c2mir 的 API 來看只有兩種做法，合併 function body 或是合併 insn 再重新 codegen。

MIR 的文件關於 module 有提到 MIR_new_import 的函式，我看不懂怎麼用，因為參數只要丟 ctx 跟字串就好了，但是我追蹤 MIR_link 使用 import_resolver 時會用到這個函式。

從 MIR 輸出的 IR 可以看到 import_solver 引入的函式(假設是 printf)會變成 import printf，我不確定 MIR 的編譯器會不會去優化 printf 還是單純 import，看起來後者比較有可能發生。

MIR module 沒有清理

• 以 rv32emu 的現況來看，編譯出 JIT 函式就可以刪掉，因為 module 之後不會用到
• ravi 沒看到有刪除 module 的操作，但是會去用 GC 回收編譯後的程式碼

The compiled code is garbage collected as normal by Lua

Control flow graph 紀錄 Hot path

有學過 graph，不過目前還不會寫 CFG 但是想到怎麼用 CFG 來 codegen 跟處理 branch 的方式。

使用 CFG 紀錄 hot path 直到超過預期的數量或是回到迴圈的開頭，也可以像 ravi 設定一個指令數量的 range 來判斷是否要 codegen，這能夠比過往單存紀錄 branch, jal/jalr 還要多的指令，也可以改善目前執行 block by block 遇到的問題。

步驟如下

• 建立 CFG 並開始紀錄指令，重複的指令就不要放進 CFG，如此便能夠紀錄迴圈而不紀錄重複的 insn 到 CFG。
• 走訪 CFG 來 codegen
• 編譯 codegen 的 C 程式碼
• 快取 JIT 函式

分支 codegen 的處理方式

分支的 codegen 用 next 紀錄跳躍的地址也就能夠檢查是否要跳躍，再去生成 true 跟 false 的對應程式碼。

先把 true 的 blocks 都生成完才生成 } else { 跟之後的 blocks，因此 traversal 的方式很重要。

void emit_branch(rv, insn) {
    bool taken = false;
    // ....
    
    uint32_t next = 0;
    if(taken) {
        rv->PC += imm;
        next = pc;
    } else {
        rv->PC += 4;
    }
}

if(rv->PC == next) {
    // true 
} else {
    // false 
}

以下圖的 CFG 為例，其中 A 跟 B 有分支，true 用紅色表示，false 則用藍色，黑色表示下一個

digraph
{
    rankdir="TD";
    block_a[label="A",shape="circle", style="bold, filled", fillcolor="#ffffff"]
    block_b[label="B",shape="circle", style="bold, filled", fillcolor="#ffffff"]
    block_c[label="C",shape="circle", style="bold, filled", fillcolor="#ffffff"]
    block_d[label="D",shape="circle", style="bold, filled", fillcolor="#ffffff"]
    
    node [ shape="circle", style="bold, filled", fillcolor="#dddddd",fixedsize=true,width=0.53 ];
    
    block_a -> block_b[color=red]
    block_a -> block_c[color=blue]
    block_b -> block_c[color=red]
    block_b -> block_d[color=blue]
    block_c -> block_b
    block_c -> block_d[style=invis]
    
}

預期生成的 C code 大致會像下面這樣，為了避免重複生成一樣的 block 可以用 goto 來處理

[block A]

if(rv->PC == next_A) {
block_B:
    [block B]
} else {
block_C:
    [block C]
    goto block_B
}

if(rv->PC == next_B) {
   goto block_C;
} else {
   [block D]
}

• 因為有 goto 跟 if 的緣故，不能保證執行指令就跟紀錄到的指令長度一樣，因此要在 codegen 時寫入更新虛擬機 cycle 的程式碼
• 或許能用 predict 的方式去合併下一塊 block，如下範例，剛開始會先生成 i < 500 的 block 之後才生成 else 區塊的 block，兩者可以做合併

int sum = 0;
for(int i = 0; i < 1000; i++) {
    if(i < 500) {
        sum += 2;
    } else {
        sum += 1
    }
}