Analyze ria-jit and Contribute
===
[TOC]
## Introduction
[RIA-JIT](https://github.com/ria-jit/ria-jit) aims to build a RISC-V emulator on x86-64 ISA machine, and take advantage of **dynamic binary translation** to provide a faster emulator, allowing the execution of RV64 on an x86–64 machine. Authors want to provide a tool to execute binaries compiled for RISC–V Linux on Linux for x86–64, what is conventionally called user space emulation, full system emulation is not supported. Currently only single threaded applications are supported, since managing the execution environment and guaranteeing atomicity for the respective instructions would be rather difficult.
:::info
Dynamic Binary Translation (DBT), which serves as a middle ground between interpreting and statically translating the executable. It aims to translate the program on the fly, while only focusing on the parts that are actually needed for execution. Therefore, it can save some of the overhead of a static translator by not spending execution time on unused code paths. The other issues are also fairly easily resolved. Unlike an interpreter, every instruction only has to be translated once and can then be run without any unnecessary overhead.
:::

Our work is to understand the problems stated in the [paper](https://github.com/ria-jit/ria-jit) issued by project contributors, along with their solutions and implementation details.

## Problems Found in Implementation
### ISA Related Issues
1. Memory Access in RV64
**RV64 is a 3-operand ISA with explicit load/store instructions**
**x86-64 is a 2-operand ISA with register-memory architecture(without load/store instructions)**
This DBT is translating code from a three-operand instruction format into a register-memory architecture in which one of the source operands is also the implicit destination operand.
This means that the single arithmetic instruction `sub rd, rs1, rs2` in RISC–V assembly language generally can not be translated via a single instruction, but rather requires two instructions: moving `rs1` to `rd`, then subtracting the value of `rs2` from `rd`.
This problem can be resolved by applying [Instruction Fusion](https://hackmd.io/x_gfPC-HSY-1Jqxs_ygX1A?both#ISA-Related-Issues1), for example, that an instruction like `xori x10, x10, -1` can be directly translated as a `not x10`, without needing to resort to `mov` and `xor`.

2. Immediate Loading in RV64
**RV64 handles loading immediate in length of word or double word with multiple LUIs and ANDI/ORI**
**x86-64 can deal with MOV `r/m64, imm`**
Same problem arising from difference between three-operand instruction and register-memory instruction is long immediate loading, which would take several RV64 instructions but the number of instructions can be reduced or even replaced by single x86 instruction with [Instruction Fusion](https://hackmd.io/x_gfPC-HSY-1Jqxs_ygX1A?both#ISA-Related-Issues1).
For example, an `lui rd, imm1` followed by `addi rd, rd, imm2` may for example be translated as directly loading the result of the computation `imm1 + imm2` into `rd`.

3. Number of General Purpose Registers
**RV64 has 31 GPRs excluding x0**
**x86-64 has 16 GPRs and some of them have specific functions**
Keeping a guest register file exclusively in memory, and loading them when needed within the translations of single instructions is technically possible. However, a large number of memory accesses for both memory operands in the instructions and local register allocation within the translated blocks is needed.
Thus, authors designed a tool and utilized it to determine register mapping, which is described in [GPRs Mapping](https://hackmd.io/x_gfPC-HSY-1Jqxs_ygX1A?both#ISA-Related-Issues1).

### Floating Point Processing
1. Register Handling
**RV64 has 32 floating-point registers**
**x86-64 has 16 XMM registers**
Same problem as GPRs in RV64 and x86-64, the RISC–V architecture consists of 32 floating point registers (f0–f31) which can hold a single precision (F-extension) or double precision (D-extension) floating point value, whereas the SSE-extensions only provide 16 registers XMM0–XMM15. The means of mapping 32 floating point registers to XMM registers is also described in [GPRs Mapping](https://hackmd.io/x_gfPC-HSY-1Jqxs_ygX1A?both#ISA-Related-Issues1).

2. Missing Corresponding Instructions in x86-64 for Fused Instruction in RV64
Because SSE extensions do not support immediate operands, constants or masks need to be loaded in from either memory or the general purpose registers can lead to huge overhead.
The instructions that need to be emulated are unsigned conversion instructions, e.g. FCVT.WU.S, sign-injection instructions, e.g. FSGNJ.S, compare instructions, e.g. FEQ.S, fused multiply-add instructions, e.g. FMADD.S and the FCLASS.S instruction that classifies a floating point value.
The solution is described in [Using AVX extension or GCC Generated Code to Replace Fused Instruction Missing](https://hackmd.io/x_gfPC-HSY-1Jqxs_ygX1A?both#Floating-Point-Processing1)

3. Different Rounding Mode in x86-64 and RV64
Rounding modes are handled differently in the RISC–V architecture, as the rounding mode can be set individually for every instruction.
The solution is described in [Temporary Alter Rounding Mode](https://hackmd.io/x_gfPC-HSY-1Jqxs_ygX1A?both#Floating-Point-Processing1)

4. Floating Point Exception Handling
Exception handling in RISC–V is realized by reading the `fcsr` floating-point control and status register, traps are not supported. To prevent trap from occurring in host process, host needs to utilize `MXCSR` multimedia extension control and status register, which is described in [Intercept and Handle Exception in Run Time](https://hackmd.io/x_gfPC-HSY-1Jqxs_ygX1A?both#Floating-Point-Processing1).

### Input(Guest) Code Partitioning and Caching
To suffice the characteristic of DBT, translator divides guest code into several basic blocks. Basic blocks, by definition, have only a single point of entry and exit; for our purposes, a basic block will be terminated by any control-flow altering instruction like a jump, call or return statement, or a system call.
To accelerate the generated code access, software-based code cache and TLB are designed by authors, but when dealing with code in huge size, code blocks might exceed code cache; thus, different proposed methods are described in [InputGuest-Code-Partitioning-and-Caching1](https://hackmd.io/x_gfPC-HSY-1Jqxs_ygX1A?both#InputGuest-Code-Partitioning-and-Caching1)

### System Call Handling
For RISC–V, the instruction `ECALL` handles system calls, with the system call number residing in register `a7` and the arguments passed in `a0`–`a6`.
In order to handle the ECALL instruction correctly, the translator can usually build the translated instruction to call a specific handler routine with system calls that exist natively on the host architecture, i.e.: `write` or `clock_gettime`.
However, below are different types of things to be taken care of:
1. Different Data Structure
2. System Calls Affecting Host Program
3. System Calls for Inter-Process Communication
The solution to above mentioned problems are described in [System Call Handling](https://hackmd.io/x_gfPC-HSY-1Jqxs_ygX1A?both#System-Call-Handling1)
### Optimization
1. Resolving Penalties Stemming from Context Switches between Guest Code and Translation Loop
To reduce the performance penalties imposed by the concept of dynamic binary translation. Authors optimize control flow to avoid leaving guest context in several means mentioned in [Optimization](https://hackmd.io/x_gfPC-HSY-1Jqxs_ygX1A?both#Optimization1).

2. Taking Advantage of CISC ISA
To further increases execution efficiency of the generated arithmetic instructions, authors conduct the optimization by means of macro opcode fusion as [Instruction Fusion](https://hackmd.io/x_gfPC-HSY-1Jqxs_ygX1A?both#ISA-Related-Issues1) mentioned.

## Solutions to the Problems
### ISA Related Issues
1. Instruction Fusion
As RISC–V is a RISC and x86–64 a CISC architecture, programs often need more instructions on RISC–V than on x86–64 to achieve the same effect. Authors employed a technique known as macro operation fusion to translate specific patterns of RISC–V instructions into shorter, equivalent x86–64 code, thereby increasing performance of the generated code, and solved the memory access and immediate value loading issues.
There is a pattern matcher detecting these patterns after parsing, as the below source code located in `src/gen/optimize.c` indicates. Once the pattern is matched, the mnemonic of the pattern would be noted as `PATTERN_EMIT`, and use `optype` to differentiate in patterns.

    void optimize_patterns(t_risc_instr block_cache[], int len) {
        for(int i = 0; patterns[i].len > 0; i++) {
            for(int j = 0; j < len - patterns[i].len; j++) {
                for(int k = 0; k < patterns[i].len; k++) {
                    ///mnem match
                    if(patterns[i].elements[k].mnem != block_cache[j + k].mnem) {
                        goto MISMATCH;
                    }
                    ///rs1 match
                    switch(patterns[i].elements[k].rs1) {
                        case DONT_CARE : {} break;

                        case rd_h1: {
                            if (block_cache[j + k].reg_src_1 !=
                                    block_cache[j + patterns[i].elements[k].h1].reg_dest) {
                                goto MISMATCH;
                            }
                        }
                            break;
                        case not_rd_h1 : {
                            if (block_cache[j + k].reg_src_1 ==
                                    block_cache[j + patterns[i].elements[k].h1].reg_dest) {
                                goto MISMATCH;
                            }
                        }
                            break;
                        case rd_h2: {
                            if(block_cache[j + k].reg_src_1 !=
                                    block_cache[j + patterns[i].elements[k].h2].reg_dest) {
                                goto MISMATCH;
                            }
                        }
                            break;
                        default: {
                            if(block_cache[j + k].reg_src_1 != patterns[i].elements[k].rs1) {
                                goto MISMATCH;
                            }
                        }
                    }
                    ///rs2 match
                    switch (patterns[i].elements[k].rs2) {
                        case DONT_CARE : {} break;
                        case rd_h1 : {
                            if(block_cache[j + k].reg_src_2 !=
                                    block_cache[j + patterns[i].elements[k].h1].reg_dest) {
                                goto MISMATCH;
                            }
                        }   break;
                        case rd_h2 : {
                            if(block_cache[j + k].reg_src_2 !=
                                    block_cache[j + patterns[i].elements[k].h2].reg_dest) {
                                goto MISMATCH;
                            }
                        }   break;
                        default: {
                            if(block_cache[j + k].reg_src_2 != patterns[i].elements[k].rs2) {
                                goto MISMATCH;
                            }
                        }
                    }
                    ///rd match
                    switch (patterns[i].elements[k].rd) {
                        case DONT_CARE : {} break;
                        //insert as needed
                        case rd_h1 : {
                            if(block_cache[j + k].reg_dest !=
                                    block_cache[j + patterns[i].elements[k].h1].reg_dest) {
                                goto MISMATCH;
                            }
                        } break;
                        case rd_h2 : {
                            if(block_cache[j + k].reg_dest !=
                                    block_cache[j + patterns[i].elements[k].h2].reg_dest) {
                                goto MISMATCH;
                            }
                        }
                            break;
                        case rs1_h1 : {
                            if (block_cache[j + k].reg_dest !=
                                    block_cache[j + patterns[i].elements[k].h1].reg_src_1) {
                                goto MISMATCH;
                            }
                        }
                            break;
                        case not_rd_h1 : {
                            if (block_cache[j + k].reg_dest ==
                                    block_cache[j + patterns[i].elements[k].h1].reg_dest) {
                                goto MISMATCH;
                            }
                        }
                            break;
                        default: {
                            if (block_cache[j + k].reg_dest != patterns[i].elements[k].rd) {
                                goto MISMATCH;
                            }
                        }
                    }
                    ///imm match
                    switch (patterns[i].elements[k].imm) {
                        case 0 : {} break;
                        case 1 : {
                            if (block_cache[j + k].imm != patterns[i].elements[k].imm_value) {
                                goto MISMATCH;
                            }
                        } break;
                        case 2 : {
                            if (block_cache[j + k].imm != block_cache[j + patterns[i].elements[k].imm_value].imm) {
                                goto MISMATCH;
                            }
                        } break;
                        default : {
                            goto MISMATCH;
                        }
                    }
                }
                ///match:
                ///insert pseudo instruction
                block_cache[j].mnem = PATTERN_EMIT;
                block_cache[j].optype = i;

                //invalidate matched sequence ??

                ///skip to end of pattern
                j = j + patterns[i].len - 1;

                MISMATCH:;
            }
        }
    }

Patterns are stored in data structure given in `src/gen/instr/patterns.c` as below. Each pattern contains pattern elements, number of elements and corresponding code emitter.

    const pattern patterns[] = {
        {p_2_elem,  5, &emit_pattern_2},  //inc mem64
        {p_9_elem,  4, &emit_pattern_9},  //LUI + ADDI + SRLI + SLLI
        {p_7_elem,  3, &emit_pattern_7},  //ADDIW + SLLI + SRLI
        {p_3_elem,  2, &emit_pattern_3},  //AUIPC + ADDI
        {p_4_elem,  2, &emit_pattern_4},  //AUIPC + LW
        {p_5_elem,  2, &emit_pattern_5},  //AUIPC + LD
        {p_6_elem,  2, &emit_pattern_6},  //SLLI + SRLI
        {p_21_elem, 2, &emit_pattern_21}, //zero-extend, then multiply
        {p_19_elem, 2, &emit_pattern_19_LI}, //LUI + ADDI
        {p_23_elem, 2, &emit_pattern_23},  //ADDIW + ANDI 0xff
        {p_11_elem, 1, &emit_pattern_11_MV}, //ADDI MV
        {p_20_elem, 1, &emit_pattern_20_small_LI}, //ADDI small LI
        {p_8_elem,  1, &emit_pattern_8_SEXTW},  //ADDIW SX only
        {p_22_elem, 1, &emit_pattern_22}, //ANDI zero-extend 0xff
        {p_10_elem, 1, &emit_pattern_10_NOP}, //ADDI NOP
        {p_12_elem, 1, &emit_pattern_12_NOT}, //XORI NOT
        {p_13_elem, 1, &emit_pattern_13_NEG}, //SUB NEG
        {p_14_elem, 1, &emit_pattern_14_NEGW}, //SUBW NEGW
        {p_15_elem, 1, &emit_pattern_15_SEQZ}, //SLTIU SEQZ
        {p_16_elem, 1, &emit_pattern_16_SNEZ}, //SLTU SNEZ
        {p_17_elem, 1, &emit_pattern_17_SLTZ}, //SLT SLTZ gcc seems to emit slti rd, rs, 0 instead
        {p_18_elem, 1, &emit_pattern_18_SGTZ}, //SLT SGTZ
        {0,         0, 0},      //stopper
        //unused
        {p_0_elem,  4, &emit_pattern_0},
        {p_1_elem,  4, &emit_pattern_0},
        {0}
    };

Taking pattern that can emit `ADD32mi` for example, corresponding `p_2_elem` contains below data, which represent load a whole 64-bit address, load a 32-bit data, add the data with immediate in fourth instruction and store the 32-bit data back.

        {AUIPC, DONT_CARE, DONT_CARE, DONT_CARE, 0, 0, 0, 0},
        {ADDI,  rd_h1,     DONT_CARE, DONT_CARE, 0, 0, 0, 0},
        {LW,    rd_h1,     DONT_CARE, DONT_CARE, 1, 0, 0, 0},
        {ADDIW, rd_h1,     DONT_CARE, DONT_CARE, 2, 0, 0, 0},
        {SW,    rd_h1,     rd_h2,     DONT_CARE, 0, 3, 2, 2}

After matching the above elements, code would be generated in below routine. If the address is 32-bit wide, the generated code is dealing with this action in "add 32-bit immediate to memory address", `ADD32MI`. Otherwise, the address would be first load into `RAX` register and later do the `ADD32MI`.

    void emit_pattern_2(const t_risc_instr instrs[static 5], const register_info *r_info) {
        log_asm_out("emit pattern 2: inc m64 at 0x%lx\n", instrs[0].addr);
        invalidateAllReplacements(r_info);

        t_risc_addr addr = instrs[0].addr + instrs[0].imm + instrs[1].imm + instrs[2].imm;
        if ((int64_t) addr == (int32_t) addr) {
            err |= fe_enc64(&current, FE_ADD32mi, FE_MEM(0, 0, 0, addr), instrs[3].imm);
        } 
        else {
            err |= fe_enc64(&current, FE_MOV64ri, FE_AX, addr);
            err |= fe_enc64(&current, FE_ADD32mi, FE_MEM(FE_AX, 0, 0, 0), instrs[3].imm);
        }
    }

2. GPRs Mapping
For shortness in the number of GPRs in x86-64 ISA, authors utilize the tools built by themselves in the translator to discover the most-used registers in the guest programs, and statically map these to general purpose x86–64 registers. The remaining operands are then dynamically allocated into reserved host registers inside the translation of a single block. The loaded values are then lazily kept in the temporary registers for as long as possible in order to avoid unnecessary memory accesses.
After their research, they found that it can covers the most use case to map GPRs and FP registers as below. As for `RAX`, `RCX`, `RDX`, `RSP` they are for temporary register mapping usage.
| RISC–V register | x86–64 mapping |
| --------------- | -------------- |
| a5 | RBX |
| a4 | RBP |
| a3 | RSI |
| a0 | RDI |
| fp | R8 |
| sp | R9 |
| a2 | R10 |
| a1 | R11 |
| s1 | R12 |
| ra | R13 |
| a7 | R14 |
| s2 | R15 |

As for FP registers, the mapping is as below, `XMM0` and `XMM1` are reserved for temporary usage.
| RISC–V register | x86–64 mapping |
| --------------- | -------------- |
| f15 | FE_XMM2 |
| f14 | FE_XMM3 |
| f9 | FE_XMM4 |
| f13 | FE_XMM5 |
| f12 | FE_XMM6 |
| f10 | FE_XMM7 |
| f11 | FE_XMM8 |
| f1 | FE_XMM9 |
| f0 | FE_XMM10 |
| f3 | FE_XMM11 |
| f2 | FE_XMM12 |
| f31 | FE_XMM13 |
| f20 | FE_XMM14 |
| f24 | FE_XMM15 |
### Floating Point Processing
1. Using AVX extension or GCC Generated Code to Replace Fused Instruction Missing in x86-64 instrinsics
One could use the FMA–extension to implement the fused multiply-add instructions natively, but these instructions require AVX, which is not generally available on x86–64 hardware. As an implementation reference for these instructions, the assembly generated by GCC was used.
Taking `FNMADDS` (`-(rs1xrs2)-rs3`) for example, below is the code generating routine. The first part is the code generating with AVX support, and second part is without AVX support. It's quite obvious that the code generation is much complex without AVX support.

         void translate_FNMADDS(const t_risc_instr *instr, const register_info *r_info) {
            log_asm_out("Translate FNMADDS...\n");
            if (instr->rounding_mode != DYN) {
                saveAndSetRound(r_info, instr->rounding_mode);
            }

        #ifdef AVX_SUPPORT
            FeReg regSrc1 = getFpReg(instr->reg_src_1, r_info, FIRST_FP_REG);
            FeReg regSrc2 = getFpReg(instr->reg_src_2, r_info, SECOND_FP_REG);
            FeReg regDest = getFpRegNoLoad(instr->reg_dest, r_info, FIRST_FP_REG);

            //move src1 to dest if src1 was mapped
            if (regSrc1 != regDest) {
                err |= fe_enc64(&current, FE_SSE_MOVSSrr, regDest, regSrc1); 
            }

            //depending if src3 was mapped or not use memory or register operand
            FeReg regSrc3 = getFpRegNoLoad(instr->reg_src_3, r_info, FIRST_FP_REG);
            if (regSrc3 == FIRST_FP_REG) {
                //regSrc3 is in memory
                err |= fe_enc64(&current, FE_VFNMADD213SSrrr, regDest, regSrc2,
                                FE_MEM_ADDR(r_info->fp_base + 8 * instr->reg_src_3));
            } else {
                err |= fe_enc64(&current, FE_VFNMADD213SSrrr, regDest, regSrc2, regSrc3);
            }
        #else
            FeReg regSrc1 = getFpReg((t_risc_fp_reg) instr->reg_src_1, r_info, SECOND_FP_REG);
            FeReg regSrc2 = getFpReg((t_risc_fp_reg) instr->reg_src_2, r_info, FIRST_FP_REG);

            FeReg regDest = getFpRegNoLoad((t_risc_fp_reg) instr->reg_dest, r_info, FIRST_FP_REG);

            //multiply rs1 and rs2
            //move src1 to SECOND_FP_REG if src1 was mapped
            if (regSrc1 != SECOND_FP_REG) {
                err |= fe_enc64(&current, FE_SSE_MOVSSrr, SECOND_FP_REG, regSrc1);
            }

            err |= fe_enc64(&current, FE_SSE_MULSSrr, SECOND_FP_REG, regSrc2);

            //negate by subtracting
            err |= fe_enc64(&current, FE_SSE_XORPSrr, FIRST_FP_REG, FIRST_FP_REG);
            err |= fe_enc64(&current, FE_SSE_SUBSSrr, FIRST_FP_REG, SECOND_FP_REG);

            FeReg regSrc3 = getFpReg(instr->reg_src_3, r_info, SECOND_FP_REG);
            //if src3 is already in dest save it
            if (regDest == regSrc3) {
                err |= fe_enc64(&current, FE_SSE_MOVSSrr, SECOND_FP_REG, regSrc3);
                regSrc3 = SECOND_FP_REG;
            }


            //move negated multiply result in FIRST_FP_REG to regDest
            if (regDest != FIRST_FP_REG) {
                err |= fe_enc64(&current, FE_SSE_MOVSSrr, regDest, FIRST_FP_REG);
            }

            //subtract rs3
            err |= fe_enc64(&current, FE_SSE_SUBSSrr, regDest, regSrc3);
        #endif
            setFpReg((t_risc_fp_reg) instr->reg_dest, r_info, regDest);
            if (instr->rounding_mode != DYN) {
                restoreFpRound(r_info);
            }
        }

2. Temporary Alter Rounding Mode
Below codes in `src/util/util.h` are to save/restore rounding mode. For every floating point code generation, save and restore rounding mode are necessary, and they are processed in below sequence.

    static inline void saveAndSetRound(const register_info *r_info, int round) {
        //convert to SSE_ROUND mode
        round = to_SSE_RoundMode(round);
        FeReg temp = invalidateOldest(r_info);
        err |= fe_enc64(&current, FE_STMXCSRm, MXCSR_SAVE); //load control register
        err |= fe_enc64(&current, FE_MOV32rm, temp, MXCSR_SAVE);
        err |= fe_enc64(&current, FE_AND16mi, MXCSR_SAVE, (int16_t) ~0x9fff); //clear all but round bits
        err |= fe_enc64(&current, FE_AND16ri, temp, (int16_t) 0x9fff); //clear round bits
        err |= fe_enc64(&current, FE_OR16ri, temp, (round << SSE_ROUND_SHIFT)); //set new round mode
        err |= fe_enc64(&current, FE_MOV32mr, MXCSR_SCRATCH, temp);
        err |= fe_enc64(&current, FE_LDMXCSRm, MXCSR_SCRATCH);//store control register
    }

    static inline void restoreFpRound(const register_info *r_info) {
        FeReg temp = invalidateOldest(r_info);
        err |= fe_enc64(&current, FE_STMXCSRm, MXCSR_SCRATCH); //load control register
        err |= fe_enc64(&current, FE_MOV32rm, temp, MXCSR_SCRATCH);
        err |= fe_enc64(&current, FE_AND16ri, temp, (int16_t) 0x9fff); //clear round bits
        err |= fe_enc64(&current, FE_OR16mr, MXCSR_SAVE, temp);
        err |= fe_enc64(&current, FE_LDMXCSRm, MXCSR_SAVE);//store control register
    }


3. Intercept and Handle Exception in Run Time
In `src/runtime/manualCSRR.c`, to handle CSR related instructions, MXCSR related code generation is utilized

    if (!((mnem == CSRRS || mnem == CSRRSI || mnem == CSRRC || mnem == CSRRCI) && src_1 == x0)) {
        //write back csr
        switch (imm) {
            case FFLAGS: {
                //only write flags
                //clear flags
                mxcsr &= ~SSE_FLAGS_MASK;
                //set new flags
                mxcsr |= to_SSE_flags(csr);
            }
                break;
            case FRM: {
                //only write rounding mode
                //clear rounding mode
                mxcsr &= ~(SSE_ROUND_MASK << SSE_ROUND_SHIFT);
                //set new rounding mode
                mxcsr |= to_SSE_RoundMode(csr & 0x7) << SSE_ROUND_SHIFT; //only lowest 3bits should have round mode
            }
                break;
            case FCSR: {
                //write rounding mode and flags
                //clear flags and round mode
                mxcsr &= ~(SSE_FLAGS_MASK | (SSE_ROUND_MASK << SSE_ROUND_SHIFT));
                //set new flags
                mxcsr |= to_SSE_flags(csr);
                //shift csr to get round mode in first 3 bits
                csr >>= FE_COUNT_RISCV;
                //set new rounding mode
                mxcsr |= to_SSE_RoundMode(csr & 0x7) << SSE_ROUND_SHIFT; //only lowest 3bits should have round mode
            }
                break;
            default:
                critical_not_yet_implemented("unsupported immediate in manualCSRR");
                break;
        }
        _mm_setcsr(mxcsr);
    }

### Input(Guest) Code Partitioning and Caching

### Optimization
1. Recursive jump translation
Returning from translated guest code to the main transcode loop comes with big performance penalties. These are imposed by the first context switch, code cache lookup, and second context switch necessary for starting execution of the next basic block. To avoid these negative performance impacts, authors implemented the method of recursive translation: When the parser arrives at an unconditional jump, translation of the jump target is started recursively. That way, the jump target will always be translated before the jump itself. Because the host code address of the jump target is now already known at translate time, DBT can make the emitted host code jump to the target directly instead of returning to the transcode loop. The blocks containing jump and target are thereby chained.
In`translate_JALR` function located in `src/gen/instr/core/translate_controlflow.c`, once the chaining option is set, the routine is gone through. If the translation of next block is done, then directly load address and jump to link; otherwise, the address is calculated in relative to instruction pointer.

    if (instr->reg_src_2 == 1 && flag_translate_opt_chain) {

        //TODO: more efficient way of obtaining target (without parsing)

        t_risc_instr tmp_p_instr;
        tmp_p_instr.addr = instr->addr - 4;

        parse_instruction(&tmp_p_instr);

        t_risc_addr target = tmp_p_instr.addr + tmp_p_instr.imm + instr->imm;

        t_cache_loc cache_loc;

        if ((cache_loc = lookup_cache_entry(target)) == UNSEEN_CODE || cache_loc == TRANSLATION_STARTED) {
            ///4: write chainEnd to be chained by chainer
            log_asm_out("CHAIN JALR\n");
            err |= fe_enc64(&current, FE_LEA64rm, FE_AX, FE_MEM(FE_IP, 0, 0, 0));
            err |= fe_enc64(&current, FE_MOV64mr, FE_MEM_ADDR((uint64_t) &chain_end), FE_AX);
            err |= fe_enc64(&current, FE_MOV32mi, FE_MEM_ADDR((uint64_t) &chain_type), FE_JMP);
        } else {
            log_asm_out("DIRECT JUMP JALR\n");
            err |= fe_enc64(&current, FE_MOV64ri, FE_CX, (FeOp) cache_loc);
            err |= fe_enc64(&current, FE_JMPr, FE_CX);
        }

    } else {
        ///dont chain
        log_asm_out("DON'T CHAIN JALR\n");
        if (flag_translate_opt_chain) {
            err |= fe_enc64(&current, FE_MOV64mi, FE_MEM_ADDR((uint64_t) &chain_end), 0);
            //no need to set chain type here
        }
    }

2. Retroactive block chaining
Translation in general is done lazily. This especially applies to the handling of conditional jumps, as it is nearly impossible to know at parsing time whether a branch will actually be taken or not. In cases where the translated conditional jump is not taken during execution, translating the target would cause unnecessary overhead. For that reason, authors do not recursively translate conditional jumps. If a branch is reached during translation, its two sides can only be chained if the respective target blocks have already been translated and their host code addresses are thus known. If that is not the case, the targets can instead be chained retroactively after the respective sides of the branch are first taken: following translation of the target block, the host code of the branch is modified to jump directly to the target address, which is now known, instead of returning to the translation loop. Further cache lookup and context switching are thus avoided for this side of the branch.
Taking the control flow in translating branch equal as an example, first translator generates control flow related instructions, and call `translate_controlflow_set_pc2` routine.

    void translate_BEQ(const t_risc_instr *instr, const register_info *r_info) {
        log_asm_out("Translate BRANCH BEQ\n");
        ///compare registers:
        translate_controlflow_cmp_rs1_rs2(instr, r_info);
        ///dummy jump
        uint8_t *jump_b = current;
        err |= fe_enc64(&current, FE_JNZ|FE_JMPL, (intptr_t) current);
        ///set pc
        translate_controlflow_set_pc2(instr, r_info, jump_b, FE_JNZ);
    }

As `traslate_controlflow_set_pc2` in `src/gen/instr/core/translate_controlflow.c` indicates, once code appears in cache, directly linked jump would be inserted into translated code, instead of below relative jump.

    if (flag_translate_opt_chain && (cache_loc = lookup_cache_entry(target)) != UNSEEN_CODE &&
            cache_loc != TRANSLATION_STARTED) {
        log_asm_out("DIRECT JUMP BRANCH 1\n");
        err |= fe_enc64(&current, FE_JMP, (intptr_t) cache_loc);
    } else {
        ///write chainEnd to be chained by chainer
        if (flag_translate_opt_chain) {
            err |= fe_enc64(&current, FE_LEA64rm, FE_AX, FE_MEM(FE_IP, 0, 0, 0));
            err |= fe_enc64(&current, FE_MOV64mr, FE_MEM_ADDR((uint64_t) &chain_end), FE_AX);
            err |= fe_enc64(&current, FE_MOV32mi, FE_MEM_ADDR((uint64_t) &chain_type), FE_JMP);
        }

        if (r_info->gp_mapped[pc]) {
            err |= fe_enc64(&current, FE_MOV64ri, r_info->gp_map[pc], (instr->addr + ((int64_t) (instr->imm))));
        } else {
            err |= fe_enc64(&current, FE_MOV64mi, FE_MEM_ADDR(r_info->base + 8 * pc),
                            instr->addr + (int64_t) instr->imm);
        }
    }

3. Return address stack
Dynamic jumps can not be statically chained, because their target address may vary. Still, there is potential for optimization, as the majority of dynamic jumps found in a typical program are function returns. By keeping track of function calls, it is possible to predict the return addresses. In order to do so, we use a stack that holds entries consisting of pairs containing both the guest return address and its corresponding host code address. The stack is implemented as a ring buffer to prevent over- and underflow. Calls are first detected at parsing time and have their return targets recursively translated. After that, host code will be emitted that pushes the corresponding return address pair onto the stack at every execution without having to leave guest context. Following dynamic jumps will compare their target guest-address with the entry in the top stack element. If the values match, the address pair is popped, and the target block is jumped to directly. Thus, returning to the translation loop is avoided. If the values do not match, control is handed back to the host. In this case the stack will not be changed, as it is assumed that a return corresponding to the top stack element will still follow.
Given in `src/cache/stack.c`, there are push and pop operations which can be committed after initialization by utilizing `r_stack` pointer. Taking push return stack for example, once the destination instructions appear in code cache, the translator generate the code which would calculate stack position first with `RDX` and store RV64 address and corresponding code cache address in the entry.

    void rs_emit_push(const t_risc_instr *instr, const register_info *r_info, bool save_rax) {
    invalidateAllReplacements(r_info);

    ///push to return stack
    t_risc_addr ret_target = instr->addr + 4;

    t_cache_loc cache_loc;

    if ((cache_loc = lookup_cache_entry(ret_target)) == UNSEEN_CODE) {
        log_asm_out("rs_emit_push: flag_translate_op is enabled, but return target is not in cache RISC-V: %p\n",
               (void *) instr->addr);
    }

    if (cache_loc == TRANSLATION_STARTED){
        log_asm_out("Return stack return target still in translation. RISC-V: 0x%lx\n", instr->addr);
        goto NOT_CACHED;
    }

    if(save_rax) {
        err |= fe_enc64(&current, FE_PUSHr, FE_AX);
    }

    err |= fe_enc64(&current, FE_MOV32rm, FE_AX, FE_MEM_ADDR((uint64_t) &rs_front));    //get front
    err |= fe_enc64(&current, FE_MOV64rm, FE_DX, FE_MEM_ADDR((intptr_t) &r_stack));     //get base
    err |= fe_enc64(&current, FE_MOV64ri, FE_CX, instr->addr + 4);                      //risc return addr
    err |= fe_enc64(&current, FE_ADD32ri, FE_AX, 0x10);                                 //increment front by "1" (=16)
    err |= fe_enc64(&current, FE_AND32ri, FE_AX, 0x3f0);                                //mod 64 (*16..)
    err |= fe_enc64(&current, FE_MOV32mr, FE_MEM_ADDR((uint64_t) &rs_front), FE_AX);    //save front
    err |= fe_enc64(&current, FE_ADD64rr, FE_AX, FE_DX);                                //base + front
    err |= fe_enc64(&current, FE_MOV64ri, FE_DX, (uintptr_t) cache_loc);                //x86 addr
    err |= fe_enc64(&current, FE_MOV64mr, FE_MEM(FE_AX, 0, 0, 0), FE_CX);               //save risc ret addr
    err |= fe_enc64(&current, FE_MOV64mr, FE_MEM(FE_AX, 0, 0, 8), FE_DX);               //save x86 addr

    if(save_rax) {
        err |= fe_enc64(&current, FE_POPr, FE_AX);
    }

    NOT_CACHED:;
}


### System Call Handling
1. Adapting structure data format
    There are system calls like fstat and fstatat that exist both on RISC–V as well as x86–64, but use different data structure layouts in their return values. Thus, the DBT must adapt the data returned by the host to the required format prior to passing it back to the guest. Defined in `src/runtime/emulateEcall.c`, authors implement how system call should be handled. For example, when `fstat` is called, after calling `__NR_fstat` syscall, translator needs to convert data in buffer into space pointed by simulated `a1` register.

case 80: //fstat
{
log_syscall("Emulate syscall fstat (80)...\n");
statRiscV *pStatRiscV = (statRiscV *) registerValues[a1];
struct stat buf = {0};
registerValues[a0] = syscall2(__NR_fstat, registerValues[a0], (size_t) &buf);
pStatRiscV->st_blksize = buf.st_blksize;
pStatRiscV->st_size = buf.st_size;
pStatRiscV->st_atim = buf.st_atime;
pStatRiscV->st_atime_nsec = buf.st_atime_nsec;
pStatRiscV->st_blocks = buf.st_blocks;
pStatRiscV->st_ctim = buf.st_ctime;
pStatRiscV->st_ctime_nsec = buf.st_ctime_nsec;
pStatRiscV->st_dev = buf.st_dev;
pStatRiscV->st_gid = buf.st_gid;
pStatRiscV->st_ino = buf.st_ino;
pStatRiscV->st_mode = buf.st_mode;
pStatRiscV->st_mtim = buf.st_mtime;
pStatRiscV->st_mtime_nsec = buf.st_mtime_nsec;
pStatRiscV->st_nlink = buf.st_nlink;
pStatRiscV->st_rdev = buf.st_rdev;
pStatRiscV->st_uid = buf.st_uid;
}
break;

    
2. Emulation
    The DBT captures the exit and exit_group calls. Passing them through would immediately terminate the DBT – an action that is undesirable as it prevents any form of clean-up or post-execution profiling and analysis to take place. Thus, the DBT uses these system calls to set a flag which stops the main loop from executing the next iteration.
    The brk system call must also be entirely emulated, as it would otherwise allow the guest program to modify the data segment (program break) belonging to the DBT, thus potentially deallocating some of the critically required memory.
    Below we take system call `exit` as an example. First DBT sets global variable `guest_exit_status` with corresponding exit code and set `finalize` flag as true. The flag `finalize` controls whether code translation loop should be running; thus setting it true can make guest code generation and execution stop.

case 93: //Exit
{
log_syscall("Emulate syscall exit (93)...\n");

//note the guest exit code and stop main loop
guest_exit_status = (int) get_value((t_risc_reg) a0);
finalize = true;
}
break;

    
3. Ignoring system calls 
    The rt_sigaction system call is ignored by the DBT. Because DBT only supports single process, any signal handler installed by the guest binary through rt_sigaction would also capture the respective signal sent to the translator. As it is impossible to distinguish the DBT from the guest program in inter-process communication, DBT must ignore this call in order to avoid undefined behaviour on signal handling. In `rt_sigaction` system call handling, DBT would simply clear `a0` in guest machine and do nothing.

case 134: //rt_sigaction
{
log_syscall("Ignore syscall rt_sigaction (134) return success...\n");
//registerValues[a0] = syscall2(__NR_rt_sigaction, registerValues[a0], registerValues[a1]);
registerValues[a0] = 0;
}
break;

4. Guarded pass-through to host. 
    Essentially, any system call that has the possibility to influence the state or memory of the translator needs to have respective safe-guards in place. A good example of this behaviour is the mmap system call. In any case, we must prevent a memory mapping into a memory region reserved by the translator. Mappings that do not interfere with the memory of the DBT can be passed along to the host directly. 
    Below we takes `mmap` as an example, DBT is responsible for memory region protection and error code returning.
    

case 222: //mmap
{
log_syscall("Emulate syscall mmap (222)...\n");
t_risc_reg_val mmapAddr = registerValues[a0];
t_risc_reg_val flags = registerValues[a3];
if (!(flags & MAP_FIXED || flags & MAP_FIXED_NOREPLACE)) {
if (mmapAddr == 0 || mmapAddr > (TRANSLATOR_BASE - STACK_OFFSET)) {
//non hinted mmap: hint to top of guest space or
//hinted mmap into translator region: re-hint to top of guest space
t_risc_addr hint = ALIGN_DOWN(lastHint - registerValues[a1], 4096lu);
registerValues[a0] =
syscall6(__NR_mmap, hint, registerValues[a1], registerValues[a2], flags,
registerValues[a4], registerValues[a5]);
lastHint = hint;
} else {
//Hinted Mapping that does not interfere with the translator's region.
registerValues[a0] =
syscall6(__NR_mmap, mmapAddr, registerValues[a1], registerValues[a2],
flags, registerValues[a4], registerValues[a5]);
}
} else if (mmapAddr > (TRANSLATOR_BASE - STACK_OFFSET)) {
log_general("Prevented mmap into translator region.");
if (flags & MAP_FIXED) {
registerValues[a0] = -EINVAL; //Is this a fitting error code to return?
} else {
registerValues[a0] = -EEXIST; //Simulate existing mapping for MAP_FIXED_NOREPLACE
}
} else {
//Fixed mapping that does not interfere with translator region
registerValues[a0] =
syscall6(__NR_mmap, mmapAddr, registerValues[a1], registerValues[a2],
flags, registerValues[a4], registerValues[a5]);
}
}
break;

## Implementation Details
### Execution Flow
![](https://i.imgur.com/ndoj2wB.jpg)


## Analysis of Test Suites
* DBT is verified by [Google Test](https://github.com/google/googletest) Framework

* DBT is tested by [SPEC CPU 2017 benchmark suite](https://www.spec.org/cpu2017/)
![](https://i.imgur.com/mfV7C9v.png)
* Evaluate different optimisation option with [SPEC CPU 2017 benchmark suite](https://www.spec.org/cpu2017/)
![](https://i.imgur.com/jeWl3BD.png)
**We can find that** 
    1. the option, fusion, is an ineffective optimisation.
    2. ras, jump do a significant performance increasing in most of the cases.

* Run gzip to simulate the real world scenario
![](https://i.imgur.com/6nZtoda.png)
    The DBT is better than QUMU when doing some optimisation.



## Discussion
1. According to the test suite above, DBT with optimisation is "**always**" better than QEMU.
2. **Fusion** is nearly none contribution.
3. There is a **critical problem** when "jump into middle of an already-translated block will be viewed as a new block". Since cache wouldn't disable any already-translated block now, the already-traslated block will permanently alive in cahce until stop the DBT. And when cache haven't enough space to save an already-translated block, its space will expand double. This will be a problem to lead to core dump because of out of memory.

## Future work
1. Improve disabling some cache space which unused for a long time.
2. Try to combine [RISC-V Compliance Test](https://github.com/riscv/riscv-compliance) with DBT.
3. Support Multi-Thread can be an optional work.