# How is sll implemented in MIPS?

I don't understand how MIPS would implement the sll (shift left logical) instruction using the hardware present in its ALU as shown in the diagrams below. Would anyone be able to clarify what would be happening in it when it's executing an sll command? I originally posted this question on Stack Overflow but I was told that I should probably post it here as well. Thanks

Source: MIPS ALU

• It could shift left via the carry chain. The Add operation in another comment would be one way to do that May 26 at 10:59

A commercial MIPS CPU will have a barrel shifter, which takes more / different gates than shown here, letting it shift by any amount in constant time.

As @devnull pointed out, those slides are showing a toy ALU for teaching purposes, supporting only add/sub/compare and some bitwise ops, not left or right shifts. Also not including other MIPS instructions, like xor or sltu (unsigned compare).

A chain of full-adders like that can do left shift by 1 as addu dst, same,same. In a toy CPU (or old real-world CPUs like 8086) you could do that iteratively, shifting 1 count per clock cycle. You could hypothetically do that for a toy MIPS implementation, too, if you're prepared to have the rest of a multi-cycle design pause its sequence while the ALU iterates. But only for left shifts, unless you also have a separate 1-bit right shifter.

But for counts other than 0 or 1, iterative shifting is incompatible with a real MIPS pipeline which requires single-cycle latency for any shift count, so the instruction can leave the EX stage after 1 cycle. The MIPS instruction set has sll $rd,$rt, shamt (funct=0) and sllv $rd,$rt, \$rs (funct=04), as well as right shifts (both logical and arithmetic). So counts other than 1 are encodeable, as are variable counts from a register.

The very name of the ISA is Microprocessor without Interlocked Pipeline Stages. Taking multiple cycles for shift counts other than x << 1 = x+x would require a way to stall previous instructions, but a design goal for MIPS I was to avoid needing that. (Except for mul/div, and cache misses.)

(That's why it has load delay slots. Although in MIPS II they added HW detection and stall for that hazard, so those slots didn't have to be filled by NOPs or independent work. They couldn't change the branch-delay slot, though, since existing binaries depended on executing the instruction there. So in MIPS II and later, the name didn't really fit anymore. :P)

I think the normal way to build a barrel shifter into the ALU would be to mux its output with the output of the configurable full-adder chain that you've shown. It handles everything else, where carry propagates from low to high (or not at all for bitwise). You'd still have that chain of full adders, but only use the outputs for funct codes that aren't shifts.

• Ah right, so something like this (i.stack.imgur.com/7MKFU.png) but going left? May 27 at 2:13
• @kene02: Yes, sure, something along those lines. The wikipedia article mentions a few implementation strategies trading space vs. gate-delays. A classic MIPS I like R2000 or R3000 probably had time in a clock cycle for a fairly significant number of gate delays, given that their L1d and L1i cache access had to be single-cycle as well! (No store buffer or load buffer.) May 27 at 2:22

The answer seems to be in the next slide after the one posted in the question:

This is not the MIPS ALU. It is a step by step approach taken in this class material to show the implementation of the operations above.

• How would you be able to do sll with those operations though? May 26 at 10:40
• You wouldn't. This isn't covered in these slides (note the word shift doesn't appear in the whole document). May 26 at 10:42
• I'm not an expert in this area, but isn't a left-shift at least the same as add r, r? May 26 at 10:49
• @kene02: With a barrel shifter, which takes more / different gates than shown here. Real MIPS CPUs were pipelined and expected to run 1 instruction per clock. Variable latency shifts would not be acceptable, given the very name of the CPU: Microprocessor without Interlocked Pipeline Stages. Taking multiple cycles for shift counts other than 1 would require a way to stall previous instructions. May 26 at 18:01
• @xiver77: sll rd, rs, 1 could be encoded as addu rd, rs, rs, but not any other immediate count, and not variable-count. See my previous comment; real-world pipelined MIPS needs fixed-latency shifts, therefore a barrel shifter. May 26 at 18:03