Intertect Journal Day 10 (Afternoon)
As Yash mentioned, I definitely slipped up on the blog post yesterday. Unstructured free time does terrible, terrible things to my memory. I supposed I could have dashed one out quickly before bed but I figured it would be more informative if it wasn’t written by a delirious person. Yesterday I finally got machine code to be output. Hurrah! Currently, the compiler will only parse R and I format instructions and only supports theadd and addi instructions, but now that the structure is mostly in place, new instructions will be quite easy to add.
Still on the to-do list for the compiler are:
- Setting up testing infrastructure (already in progress)
- Parsing for J format instruction
- Parsing for the different format that store and load instructions use
- Parsing for shift instrcutions. They’re R format but only use two registers
- Parsing labels and segments (This is going to be the hardest part, I think)
- Adding the rest of the instructions
Instruction Formats
Now might be a good time to explain what on earth I’m talking about when I talk about R, I, and J format instructions. The basic idea is that different instructions have different requirements for what data they need to contain. Therefore, instructions are split into 3 different formats based on what information they require.
R Format Instructions
R format instructions are so called because they operate on registers with data contained in registers (for the most part). They are laid out like so
6 bits 5 5 5 5 6
+--------+----+----+----+-------+-------+
| opcode | rs | rt | rd | shamt | funct |
+--------+----+----+----+-------+-------+The opcode, combined with the funct field, determine what the operation being performed is. The idea with the funct field is that many R format instructions are essentially the same, modulo a handful of parameters. The funct field allows for control bits to be embedded directly into the instruction that alter where data is taken from, where it flows to, and subtle semantics about the instruction. This allows a reduction in processor complexity because the decoding stage is much simpler than if bits didn’t map one-to-one with functionality.
rs, rt , and rd are the two source and one destination registers respectively. shamt is the “shift amount”. This is used by shift instructions to determine how many places to shift rt before saving it into rd. If I had to guess at the reason for including shift amount in the R formatted instructions, it’s because in addition to the shift instructions taking a constant to shift by, there are also instructions that take a register that indicates the number of bits to shift by. The encoding for these two sets of instructions differ by exactly 1 bit in the funct parameter which leads me to think that this one bit changes where the processor is retrieving the data from.
I Format Instructions
6 bits 5 5 16
+--------+----+----+-----------+
| opcode | rs | rt | immediate |
+--------+----+----+-----------+I format instructions are used for those operations that require compile-time constants. They are called “immediate” instructions because the data is immediately available inside the instruction. Aside from registers, this is the fastest place to be able to put data. If your constant is in memory, it can require thousands of clock cycles to access instead of effectively 0 once the instruction has been fetched. That’s a huge win! The downside to these instructions is that they only have 16 bits of data to work with but registers are 32 bits wide, which somewhat limits their flexibility. This is where pseudo-instructions come into play.
Pseudo-instructions are instructions you can write in assembly language that are translated by the compiler into two or more real instructions under the hood. There is a special register $at that is reserved for just this purpose. The compiler will use this for any intermediate processing steps to prevent polluting any of the other registers.
Let’s say we wanted to initialize a register to some 32 bit number, say 0xDEADBEEF. We might write li $t0,0xDEADBEEF. The li pseudoinstruction is “load immediate”. However, our constant is too large for just 16 bits so we split up the instruction into 2 instructions.
lui $t0, 0xDEAD
ori $t0, $t0, 0xBEEFThe first instruction is “load upper immediate” which shifts that immediate value over and assigns it to the top 16 bits of the register, leaving the lower 16 bits initialized to 0. That last part is an optimization since we usually use lui when we want to initialize a register. Otherwise we would need 3 instructions with the first setting the register to 0.
The second instruction up there takes the logical OR of the register with the lower 16 bits of our constant. The top 16 bits of the register remain unchanged, and since the lower 16 bits are all 0, the logical OR takes on the value of the constant. And just like that we set a register to a 32 bit constant! From start to finish, this would only take six clock cycles to complete while a read from memory could take hundreds of thousands! Even if the value was in cache, it would still be on the order of tens or hundreds of clock cycles during which the entire instruction pipeline would be stalled.
J Format
J — or Jump — format instructions, are probably the easiest to understand. The goal is to be able to cover as much of the program as possible in any one instruction so we want the payload to be as large as possible
6 bits 26
+--------+---------+
| opcode | address |
+--------+---------+That’s a lot of address bits! In order to squeeze even more range out of that constant, it takes advantage of the fact that all MIPS instructions are exactly 4 bytes long. The address isn’t so much an address as it is an instruction count. The lower two bits of the address are always going to be 0 since we’re always going to be at a multiple of 4. We can squeeze 2 extra bits out of the address argument! The address gets set to the top 4 bits of the current address with the next 28 bits being the address (shifted left by 2, of course). This allows the J format instruction to reach most of the binary. This also works on the assumption that most jumps are going to be to addresses somewhat close to the current instruction. With a healthy stack and heap, this means the entire program could be reached by a single jump instruction. For times where this isn’t possible, there is also a jr instruction that jumps to the contents of a register, which allows all 32 bits to be set at once.
Wrapping Up
That was a whirlwind tour of instruction formats! The only other thing to talk about today is the testing infrastructure. The goal with that is to be able to compare the output of our compiler with a big boy compiler that we trust. In fact, we’re using the biggest boy of compilers, gcc (mostly because it was the easiest to set up for cross-compilation). I’ve got the cross-compiler — which is a compiler that outputs code for an architecture your computer isn’t running, like MIPS on my x86 laptop — all set up and now I just have to tease out the bits of the output I care about. I haven’t settled on the best way to do it yet but with some bit-twiddling it shouldn’t be terribly difficult. I’ll probably also do this in Rust because then I can easily set this up as a suite of unit tests that can be run natively with the rust tooling. Plus the compiler is a library so it could all happen in-process.
This is me signing off! I’ll have some more deep dives coming up relatively soon (but not imminently) about some other neat portions of the MIPS architecture. I’ll try to keep them relevant so they track what we’re actually working on, but no promises. I can tell myself it’s productive because I can reuse much of the material for the Lesson plans and Addenda!
-Peter