15
$\begingroup$

I'm confused as to why the MIPS designers would include 5 bits dedicated to shifting and have separate opcode and function bits.

Because MIPS is so RISC I assume that only shifting would be done in a few instructions, so those 5 bits seem like they're wasting space when they could be put in the immediate. I assume that opcodes and funct are seperate for distinguishing R- and I- type instructions, but this could be done by extending the opcode by 1 bit. With both of these R-type instructions could be 22 bits long. This won't work if the I-type and J-type instructions want to keep their immediate and address, but both seem unnecessary.

$\endgroup$
10
$\begingroup$

There are a few different trade-offs going on here.

First, we want the instructions to be fixed width (32-bits). This guarantees that instructions are cache-block and page aligned which simplifies cache and page presence and permission checks.

Second we want the various instruction fields (opcode/source regs/immediates) to be fixed width and fixed position. This makes them faster/less logic to decode and they are needed in the early stages of the pipeline. (The destination register isn't needed until the end of the pipeline, so it can be in different places in R and I instructions.) The position and width of the function field matters a little less because that needs to control the function of the ALU, but that's in the third pipeline stage, so you have a little time to work with it if needed.

But now we have a tension between number of possible instructions and the sizes of the immediates. We want the immediates in the I and J instructions to be long as possible. This is a 32-bit architecture, and the J instruction has only a 26-bit address. It gets two zero low-order bits added to it (another benefit of fixed width instructions) but you can still only jump a maximum distance of $2^{28}$ bytes, which makes life difficult for the linker. (A call of a procedure that is more than $2^{28}$ bytes distant needs to be done with a triple instruction: load-upper-immediate, add-immediate, jump-and-link-register, instead of just a jump-and-link.) The 16-bit immediate in I instructions is also nice for compiler/linker writers. (On the SPARC, where the immediate field was only 12 bits they had to add an entire special load-high instruction class with a 20 bit immediate.)

So we really don't want to make the opcode 7 bits (because it will cut into immediates) but with 6-bits we only have $2^6=64$ possible different instructions, which is way too few. The compromise is: there are exactly two type J instructions (jump and jump-and-link), and only one or two type R instructions, with the remaining 60-or-so opcodes being used for I instructions.

But that leaves some wiggle room with the R instructions. Aside from the 6-bit opcode, these only need 15 additional bits for register specification, which leaves 11 bits for the extended opcode and/or shift-amount.

You should think of the function field as being an extended opcode for the R instruction. There's only one R instruction opcode, but there are 64 different functions that the R instruction can perform.

Okay. We have 60 different I instructions and 64 different R instructions, so where should we put the shift-immediate instructions?

Well, not only are there fewer I instructions, but there are way more things we want to do with I instructions. Recall that all the branch instructions need to be I instructions because they have a relative (immediate) offset. Also all the load and store instructions are I format on MIPS. And finally we need the load-upper-immediate instruction to be an I instruction. Not only that, but the R instructions still have 5 additional unused bits, (which is what we need for the immediate of a shift-immediate on this architecture), so this gives further incentive to making the shift-immediates into special (weird) R instructions.

A lot of these decisions are more art than science, but there is an underlying logic that can be discerned. The key goal is not to make the number of instructions as small as possible, it is to make a high-performance pipeline fit on a single chip (so that tiny companies, like MIPS and Sun were in the 1980s, could compete with IBM and DEC). (The name RISC, invented by David Patterson, is somewhat unfortunate. It caught on because it was cute, not because "reduced instructions" is an accurate description of what the MIPS and SPARC architectures were really trying to do.) So you want the instructions fixed width (and relatively small so that you get better I-cache behavior) to make fetch, paging and decode simpler and faster. You want the parts of the instruction that need to be decoded early (the opcode, the two source registers, and the sign-extended immediate) to be a fixed width and in a fixed position. You want immediates to be as long as possible, and you want as many different kinds of instructions as will fit, given all those other constraints.

$\endgroup$
  • $\begingroup$ Thank you for your informative response, especially the part about the goals of the architecture designers. I find it interesting to compare MIPS to the MOS 6502, because if I understand it correctly the 6502 never had shamt (I'm still trying to understand the instruction formats). $\endgroup$ – qwr Jul 1 '14 at 20:39
  • 1
    $\begingroup$ The 6502 was a first generation microprocessor design (pre-CISC), although it did anticipate pipelining, in that it could do register writeback at the same time that it was loading the next instruction. The 6502 had byte opcodes, like most 8-bit micros. Another architecture to consider is the ARM, which was designed by a bunch of higher-level electronic engineers who read the Berkeley RISC papers and visited the MOS factory and decided "hey, we can do that". $\endgroup$ – Pseudonym Jul 2 '14 at 1:03
  • $\begingroup$ I wonder what the implications would have been if there were a shamt bit pattern which meant "don't execute the following instruction, but use the 32 bits which have been fetched for it as the source operand for this instruction"? Alternatively or in addition, I wonder if it would have been practical to have a fair chunk of opcode space dedicated to pairs of simple uninterruptable instructions--a concept somewhat like Thumb, but freely interspersable with 32-bit instructions, and without the ability to jump directly to the second instruction of a word? $\endgroup$ – supercat Feb 8 '15 at 23:37
5
$\begingroup$

To understand the MIPS I instruction formats, you need to understand the MIPS pipeline and also think back to CPU implementation technology circa 1985. If you look at the diagram (you know the one), you'll see that register file reading is in the ID stage, right after IF.

For the purpose of an R-type instruction, the ID stage needs to do the following tasks:

  1. Determine that it actually is an R-type instruction.
  2. If so, tell the register file to load values from registers.

For the purpose of this discussion, it's the first task that you have to think about. If there's a lot of instruction decoding work that you have to do to even work out if you need any values from registers, this increases the delay before you can start the register reads. It also increases the complexity of the ID stage. By reserving a single opcode for all R-type instructions, you keep the complexity to a minimum.

It does seem a little strange that you dedicate five bits just to shifting. I can think of a few possible explanations. One is that it simplifies the routing (those five bits are ALWAYS fed straight into the register file, those five bits are ALWAYS fed into the barrel shifter, those six bits are ALWAYS routed through to the ALU to determine which function to perform).

They may have been thinking of introducing combined shift-left-and-add instructions in the future. This would presumably be of the form:

$d = $s + ($t << shamt)

This is a surprisingly useful instruction to have around, as any x86 assembly programmer can tell you. You can use it to implement fast multiplications by $2^s+1$ for various values of $s$, or you can use it to index arrays where the size of an element is a power of two (which is a very common case). But it's still RISC enough that you could implement it without significant penalty.

Today, we probably wouldn't think twice about having a more complex decoding stage, especially since register file accesses tend to happen later in the pipeline of a typical superscalar CPU. Many modern CPUs even do some coarse instruction decoding at the time an instruction is inserted in the L1 cache. You make the I-cache lines a few bits wider to store the extra information (thanks to Moore's Law, you have lots of transistors to waste) to make "proper" instruction decoding simpler and faster.

One reason why they probably wanted to keep the opcode field as small as possible is so that it didn't penalise J-type instructions unduly. As you probably know, J-type instructions use pseudo-direct addressing. For the benefit of anyone playing along at home, I'll briefly explain it.

The address field of a J-type instruction is 26 bits. Because instructions are always 4-byte aligned, you don't need to store the least significant two bits, which means you effectively have 28 bits of address. However, the address space in MIPS I is 32-bits. So the top four bits of the jump location is taken from the program counter.

This means that you can't directly jump to a location where the most significant four bits of the PC location are different. You would have to do a more expensive three-instruction jump through a scratch register instead:

lui $r,target >> 16
    ori $r,$r,target & 0xFFFF
    jr $r

That's not too bad today, but in 1985, it's a lot of clock cycles.

Stealing a bit from the address field would reduce the effective range of a direct jump even further. You can see how this might be too high a price to pay.

$\endgroup$
  • $\begingroup$ "combined shift-left-and-add instructions" of the type later seen in ARM? $\endgroup$ – Damian Yerrick Feb 6 '15 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.