Analyze ria-jit and Contribute

Analyze ria-jit and Contribute

Introduction

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.

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 issued by project contributors, along with their solutions and implementation details.

Problems Found in Implementation

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, 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.
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.
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.
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.

Floating Point Processing

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.
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
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
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.

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

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:

Different Data Structure
System Calls Affecting Host Program
System Calls for Inter-Process Communication
The solution to above mentioned problems are described in System Call Handling

Optimization

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.
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 mentioned.

Solutions to the Problems

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);
    }
}

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

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);
       }
   }

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
}

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

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.
Intranslate_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
    }
}

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);
    }
}

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

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;

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;
```
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;
```

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

Analysis of Test Suites

DBT is verified by Google Test Framework
DBT is tested by SPEC CPU 2017 benchmark suite
Evaluate different optimisation option with SPEC CPU 2017 benchmark suite

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

The DBT is better than QUMU when doing some optimisation.

Discussion

According to the test suite above, DBT with optimisation is "always" better than QEMU.
Fusion is nearly none contribution.
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

Improve disabling some cache space which unused for a long time.
Try to combine RISC-V Compliance Test with DBT.
Support Multi-Thread can be an optional work.

Analyze ria-jit and Contribute

Introduction

Problems Found in Implementation

ISA Related Issues

Floating Point Processing

Input(Guest) Code Partitioning and Caching

System Call Handling

Optimization

Solutions to the Problems

ISA Related Issues

Floating Point Processing

Input(Guest) Code Partitioning and Caching

Optimization

System Call Handling

Implementation Details

Execution Flow

Analysis of Test Suites

Discussion

Future work