Proposal: BRIL to RISC-V Lowering System

[jdroob]

What will you do?

We will develop a system for lowering Bril programs to RISC-V assembly code, enabling the execution of Bril programs in a RISC-V environment. We will also focus on verifying the accuracy and correctness of this lowering system.

How will you do it?

To achieve this goal, we will do the following:

1. Familiarization: We will better acquaint ourselves with both the Bril language and the RISC-V architecture. One team member is actively working on implementing a RISC-V processor in Verilog for another course, and we feel as though we have a solid foundation in Bril. However, we will dive deeper into both before we begin implementation.

2. Lowering Design: We will design a system for lowering Bril instructions into RISC-V assembly code. Initially, our focus will be on creating a minimum viable implementation. In this phase, we will use a 1-to-N approach, where one Bril instruction corresponds to multiple RISC-V instructions. This basic version will serve as our foundation.

3. Optimization (Stretch Goal): If time permits, we will explore an M-to-N approach. This strategy will involve optimizing the translation by recognizing dependencies between multiple Bril instructions and generating a more efficient sequence of RISC-V instructions.

How will you empirically measure success?

We will evaluate the success of our project by assessing two key criteria:

1. Semantic Equivalence: We will verify the correctness of our project by ensuring that the translated RISC-V code is semantically equivalent to the source Bril code. We will utilize Cranelift's ISLE domain-specific language to specify our translation rules and use Crocus to verify the correctness of these rules. It's imperative that the RISC-V code generated by our system matches that produced by Cranelift. This will be tested using rigorous benchmarks.

2. Performance Improvement: We will assess the improvement in performance from interpreted Bril code to compiled RISC-V code in terms of execution time. We are currently researching tools to accurately measure wall clock time for comparing the two execution modes.

Team members: @20ashah

[sampsyo]

OK, cool! This sounds ambitious, but I think you can make it work. :smiley:

Here are a few questions I think will be important for this project's eval:

• How will you run RISC-V programs? I suspect you don't have real RISC-V hardware… do you have an emulator picked out? These can be really complicated to get working, so it will be extremely important to get something installed/running on small assembly programs early, before you start trying to generate code.
• What will your approach to register allocation be? Maybe the answer is "trivial," i.e., all variables will be on the stack. That would be a good place to start.
• Do you know how much of core Bril you hope to support? Will you support print (and if so, how)? How about function calls?

Please try to answer these questions within, say, ~1 week so we can agree on how to approach stuff here. I'm particularly interested in knowing that y'all have a RISC-V emulator up and running that you think will work for your purposes.

[jdroob]

• I'm 90% sure that the ECE 4750 course I'm enrolled in provides an emulator we should be able to use. I will do some further investigation into this and circle back.
• For register allocation, we are thinking that we will implement trivial register allocation in order to get a minimum viable version of the lowering system working. However, a much more fun and interesting goal of ours is to use LLVM's greedy allocator for register allocation. In order to do this, there are additional problems for us to solve - most importantly: How can we convert to LLVM IR in order to use the allocator? This is something that I'm not totally clear on. I'm looking into some of LLVM's APIs but haven't found anything yet. Are there any APIs you know of for converting generic IRs to LLVM IR? If not, would it be feasible to try to convert SSA Bril to LLVM? I sense that we're quickly letting the scope of this project grow out of control - but at the same time, I'd like to use something LLVM-related in our final project :)
• We were thinking of just supporting the basic Bril (i.e. without the memory extension). We would like to be able to support print but we need to look further into the implementation details on how to accomplish this. I'm currently looking into this post for implementation details on how to print to screen in RISC-V assembly.
• We certainly plan to support function calls using the standard RISC-V calling conventions (e.g. JAL, JALR, saving ret address, saving ret val, caller / callee-save registers, etc.)

[sampsyo]

OK, sounds good!

To be clear, if you want to try to reuse LLVM's register allocator, this has profound implications for the project: namely, you will not be generating RISC-V assembly. Your options include generating LLVM IR (which would be completely target-agnostic and not specific to RISC-V at all) or generating the LLVM MachineInstr IR (which sounds interesting but I have no idea what it would entail). I can't see a way to reuse LLVM's register allocator without reusing its code generator.

[jdroob]

Including a link to the project repo