CS274: Computer Architecture - From MIPS to Machine Language

Activity Goals

The goals of this activity are:
  1. To translate between MIPS assembly instructions and MIPS 32-bit machine language
  2. To explain that all MIPS assembly instructions are 32 bits in size, regardless of format

Supplemental Reading

Feel free to visit these resources for supplemental background reading material.

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

Model 1: Instruction Formats

R Type opcode rs rt rd shamt function
bits 6 5 5 5 5 6
add $t0, $t1, $t2 0 $t1 = 9 $t2 = 10 $t0 = 8 0 0x20
I Type opcode rs rt immediate
bits 6 5 5 16
addi $s0, $s1, 100 0x8 $s1 = 17 $s0 = 16 100
J type opcode jump-address
bits 6 26
j loop 0x2 10010001101
assuming the address of loop is 0x80001234 (0b10000000000000000001001000110100)
and PC+4 is 0x80000000

Questions

  1. A jump instruction allows 26 bits for the jump address, but addresses are 32 bits in length. Why can't we allow a 32-bit jump address in an instruction, and what do you think is done instead?
  2. Why are all addresses and instructions 32 bits in size?
  3. Where is the "answer" register (rd in an R type instruction, and rt in an I type instruction) typically found in a MIPS assembly instruction, and where is it typically found in the machine code translation?
  4. The shamt field holds the number of bits that a register shifts left or right. In your MIPS reference sheet, look up what instruction would consist of all 0 bits. What might you call this instruction, and what does it do?
  5. How can you tell if an instruction is R type or not? If it is not R type, how can you tell if it is J type or I type?
  6. Why do you think the designers stopped at only 3 instruction formats?
  7. Translate the instruction addi $t1, $t2, $t3 to a MIPS 32 bit machine instruction.
  8. Translate the 32 bit instruction 0x00571020 from hexidecimal to binary, and then to a MIPS assembly instruction. How can you tell just by looking at the hexidecimal that it's an R-type instruction?
  9. What instructions might implement the pseudoinstruction li $t0, 0xabcd5678? Why can't this instruction be represented with a single operation?

Model 2: Practice: Translating and Encoding Instructions

Let's put the formats to work. First, memorize (or bookmark!) the exact bit positions of every field. Bit 31 is the leftmost (most significant) bit and bit 0 is the rightmost:

Format Bits 31-26 Bits 25-21 Bits 20-16 Bits 15-11 Bits 10-6 Bits 5-0
R opcode (6) = 0 rs (5) rt (5) rd (5) shamt (5) funct (6)
I opcode (6) rs (5) rt (5) immediate (16), bits 15-0, sign-extended
J opcode (6) address (26), bits 25-0

Worked Example 1 (encode an R type): sub $s0, $s1, $s2

  1. Format: sub is R type (opcode 0, funct 0x22).
  2. Register numbers: $s0 = 16, $s1 = 17, $s2 = 18.
  3. Assembly order is sub rd, rs, rt, so rd = 16, rs = 17, rt = 18.
  4. Fields in binary at full width: opcode = 000000, rs = 17 = 10001, rt = 18 = 10010, rd = 16 = 10000, shamt = 00000, funct = 0x22 = 34 = 100010.
  5. Concatenate: 000000 10001 10010 10000 00000 100010.
  6. Regroup into fours: 0000 0010 0011 0010 1000 0000 0010 0010.
  7. Hex digit by hex digit: 0x02328022.

Worked Example 2 (encode an I type): addi $t1, $sp, 16

  1. Format: addi is I type with opcode 0x8.
  2. Register numbers: $t1 = 9, $sp = 29.
  3. For I types the destination is rt: rt = $t1 = 9, rs = $sp = 29, immediate = 16.
  4. Fields in binary: opcode = 8 = 001000, rs = 29 = 11101, rt = 9 = 01001, immediate = 16 = 0000000000010000.
  5. Concatenate: 001000 11101 01001 0000000000010000.
  6. Regroup: 0010 0011 1010 1001 0000 0000 0001 0000.
  7. Hex: 0x23A90010.

Worked Example 3 (decode): what is 0xAE1100F0?

  1. Hex to binary: 1010 1110 0001 0001 0000 0000 1111 0000.
  2. opcode = top 6 bits = 101011 = 0x2B. Not zero, so it isn't R type; look up 0x2B: it is sw, an I type.
  3. Slice I type fields: rs = 10000 = 16 = $s0, rt = 10001 = 17 = $s1, immediate = 0000000011110000 = 0xF0 = 240.
  4. For a store, rt is the register being stored and rs is the base address: sw $s1, 240($s0).

Now you try! Ordered from easier to harder; solve on paper first, then check.

Problem 1 (easy): Encode or $t0, $t1, $zero. (or has funct 0x25.)

Solution
  1. R type: opcode = 000000, funct = 0x25 = 100101.
  2. rd = $t0 = 8 = 01000, rs = $t1 = 9 = 01001, rt = $zero = 0 = 00000, shamt = 00000.
  3. Concatenate: 000000 01001 00000 01000 00000 100101 = 0000 0001 0010 0000 0100 0000 0010 0101 = 0x01204025.
  4. Bonus: this is exactly how the assembler implements the pseudoinstruction move $t0, $t1!

Problem 2 (easy-medium): Encode slt $t0, $s3, $s4. (slt has funct 0x2A.)

Solution
  1. R type: opcode = 000000, funct = 0x2A = 101010.
  2. rd = $t0 = 8 = 01000, rs = $s3 = 19 = 10011, rt = $s4 = 20 = 10100, shamt = 00000.
  3. Concatenate: 000000 10011 10100 01000 00000 101010 = 0000 0010 0111 0100 0100 0000 0010 1010 = 0x0274402A.

Problem 3 (medium): Suppose $gp holds 0x10008000. What effective address does lw $s0, 20($gp) read from, and what is its encoding? (lw has opcode 0x23.)

Solution
  1. Effective address = base + offset = 0x10008000 + 20.
  2. 20 in hex is 0x14, so the address is 0x10008014.
  3. Encoding: opcode = 0x23 = 100011, rs = $gp = 28 = 11100, rt = $s0 = 16 = 10000, immediate = 20 = 0000000000010100.
  4. Concatenate: 100011 11100 10000 0000000000010100 = 1000 1111 1001 0000 0000 0000 0001 0100 = 0x8F900014.

Problem 4 (medium): Decode 0x21290001.

Solution
  1. Binary: 0010 0001 0010 1001 0000 0000 0000 0001.
  2. opcode = 001000 = 0x8 = addi (I type).
  3. rs = 01001 = 9 = $t1, rt = 01001 = 9 = $t1, immediate = 1.
  4. Assembly: addi $t1, $t1, 1 -- an increment!

Problem 5 (medium-hard): Decode 0x02114020.

Solution
  1. Binary: 0000 0010 0001 0001 0100 0000 0010 0000.
  2. opcode = 000000, so R type; slice all six fields.
  3. rs = 10000 = 16 = $s0, rt = 10001 = 17 = $s1, rd = 01000 = 8 = $t0, shamt = 00000, funct = 100000 = 0x20 = add.
  4. Assembly (destination first): add $t0, $s0, $s1.

Problem 6 (challenge): Suppose $fp holds 0x7FFFEFFC. What address does sw $t2, -8($fp) write to, and what is its encoding? (sw has opcode 0x2B.)

Solution
  1. Effective address = 0x7FFFEFFC + (-8) = 0x7FFFEFFC - 0x8 = 0x7FFFEFF4.
  2. Encoding: opcode = 0x2B = 101011, rs = $fp = 30 = 11110, rt = $t2 = 10 = 01010.
  3. immediate = -8 in 16-bit two's complement: 8 = 0000000000001000; invert: 1111111111110111; add 1: 1111111111111000 = 0xFFF8.
  4. Concatenate: 101011 11110 01010 1111111111111000 = 1010 1111 1100 1010 1111 1111 1111 1000 = 0xAFCAFFF8.

Common Pitfalls
  • rd vs. rt: the destination is the rd field for R types but the rt field for I types -- and in assembly it is always written first, so its machine-code position moves depending on the format.
  • Register names vs. numbers: $s0 is register 16 and $t0 is register 8; never encode the digit in the name.
  • Sign extension: immediates for addi, lw, sw, beq, and bne are sign-extended 16-bit two's complement values; 0xFFF8 means -8. andi/ori zero-extend instead.
  • Width discipline: pad every field to its exact width (5 or 6 or 16 bits) before concatenating; the total must be exactly 32 bits.
  • Loads/stores read the offset in bytes: lw $s0, 4($sp) means 4 bytes past $sp, which is only one word away.

Questions

  1. Decode a classmate's favorite hex word. What happens if the opcode isn't a legal MIPS opcode?
  2. Why can you decode any 32-bit word uniquely -- that is, why is it impossible for one word to be two different instructions?

Model 3: Translating jump instructions

printf("Hello, world!");

Questions

  1. What do you think this program does?
  2. Suppose the first line of main is instruction address 0x00400024. What is the address of the first instruction at label procedure? What is the binary translation of the jal instruction above?

Model 4: Practice: Branch and Jump Address Calculation

When you write beq $t0, $t1, mylabel, the assembler does not store the address of mylabel in the instruction -- there isn't room! Instead it stores a word offset relative to the instruction after the branch. Here is the recipe:

Branch offset recipe (PC-relative addressing):

  1. Compute the address of the instruction after the branch: PC + 4. (By the time the branch executes, the PC has already moved on.)
  2. Subtract: byte offset = target address - (PC + 4). This can be negative for backward branches!
  3. Divide by 4 to convert bytes to words: word offset = byte offset / 4. (Instructions are word-aligned, so the bottom two bits are always 0 -- why waste them?)
  4. Write the word offset as a 16-bit two's complement immediate.

Worked example: a beq at address 0x00400018 branches back to a loop at 0x00400008.

  1. PC + 4 = 0x00400018 + 4 = 0x0040001C.
  2. byte offset = 0x00400008 - 0x0040001C = -0x14 = -20 bytes.
  3. word offset = -20 / 4 = -5 words.
  4. -5 as a 16-bit two's complement value: 5 = 0000000000000101; invert: 1111111111111010; add 1: 1111111111111011 = 0xFFFB. That is the immediate stored in the instruction.

Jumps work differently: j and jal use pseudo-direct addressing. The 26-bit field holds the target's word address, and the hardware rebuilds the full 32-bit byte address like this:

target = { (PC+4)[31:28] , address field (26 bits) , 00 }
            4 bits          26 bits                  2 bits  = 32 bits

Worked example: a j at address 0x00400030 targets 0x00400020.

  1. The target's bottom two bits are 00 (word aligned), so drop them: 0x00400020 / 4 = 0x00100008. This fits in 26 bits, so it becomes the address field.
  2. Check the top 4 bits: the target 0x00400020 and PC + 4 = 0x00400034 both start with 0000, so the jump is legal (same 256 MB region).
  3. Assemble the word: opcode 000010 followed by the 26-bit field. Numerically: (2 << 26) + 0x00100008 = 0x08000000 + 0x00100008 = 0x08100008.

Now you try!

Problem 1 (forward branch): A beq $t0, $t1, done sits at address 0x00400020, and done is at 0x00400034. What immediate is stored?

Solution
  1. PC + 4 = 0x00400024.
  2. byte offset = 0x00400034 - 0x00400024 = 0x10 = 16 bytes.
  3. word offset = 16 / 4 = 4 words.
  4. immediate = 0x0004.

Problem 2 (backward branch): A bne $t0, $zero, loop sits at 0x0040004C, and loop is at 0x00400038. What immediate is stored?

Solution
  1. PC + 4 = 0x00400050.
  2. byte offset = 0x00400038 - 0x00400050 = -0x18 = -24 bytes.
  3. word offset = -24 / 4 = -6 words.
  4. -6 in 16-bit two's complement: 6 = 0000000000000110; invert: 1111111111111001; add 1: 1111111111111010 = 0xFFFA.

Problem 3 (decode an offset): A branch instruction at address 0x00400008 has immediate 0x000A. Where does it branch to if taken?

Solution
  1. immediate = 0x000A = 10 words = 40 bytes.
  2. PC + 4 = 0x0040000C.
  3. target = 0x0040000C + 40 = 0x0040000C + 0x28 = 0x00400034.

Problem 4 (jump encode): Encode j to the target 0x00403100 (assume the PC is nearby in the same region).

Solution
  1. Drop the bottom two bits: 0x00403100 / 4 = 0x00100C40.
  2. Opcode for j is 2: word = (2 << 26) + 0x00100C40 = 0x08000000 + 0x00100C40 = 0x08100C40.

Problem 5 (jump decode): Decode 0x0C100020, assuming the upper 4 bits of PC + 4 are 0000. What does the instruction do?

Solution
  1. Binary: 0000 1100 0001 0000 0000 0000 0010 0000; opcode = 000011 = 3 = jal.
  2. address field = the low 26 bits = 0x0100020.
  3. target = field × 4 = 0x0400080; prepend PC's top 4 bits (0000): 0x00400080.
  4. So this is jal 0x00400080: it sets $ra to PC + 4 and jumps to 0x00400080 -- a procedure call.

Questions

  1. A branch immediate is 16 bits of words. How many bytes forward and backward can a branch reach? What should the assembler do if the target is farther away?
  2. Why does the branch recipe use PC + 4 rather than PC?

Model 5: Key Formulas and Concepts Recap

A one-page summary of machine language translation. Keep it next to your green sheet!

The three instruction formats:

bit:  31    26 25  21 20  16 15  11 10   6 5     0
R:   | opcode | rs   | rt   | rd   | shamt | funct |     opcode = 0; funct picks the operation
I:   | opcode | rs   | rt   |      immediate       |     16-bit immediate, sign-extended
J:   | opcode |             address                |     26-bit word address

Key formulas:

Formula Micro-example
Load/store effective address = Reg[rs] + sign-extended immediate lw $s0, 8($sp) with sp = 0x7FFFEFF0 reads 0x7FFFEFF8
Branch immediate = (target - (PC + 4)) / 4, stored as 16-bit two's complement branch at 0x00400018 to 0x00400008: -20 bytes = -5 words = 0xFFFB
Branch target = (PC + 4) + (immediate × 4) immediate 0x0004 at 0x00400020 targets 0x00400024 + 16 = 0x00400034
Jump target = { (PC+4)[31:28], 26-bit field, 00 } field 0x0100008 with PC top bits 0000 targets 0x00400020
Two's complement negation: invert all bits, then add 1 -5 in 16 bits: 0000000000000101 → 1111111111111010 → 0xFFFB
Format test: opcode 0 → R type; opcode 2 or 3 → J type; anything else → I type 0x02328022 starts 000000, so R type

Glossary:

Term One-line definition
opcode Bits 31-26 of every instruction; identifies the operation or, for R types, defers to funct.
funct Bits 5-0 of an R type; selects which ALU operation (add = 0x20, sub = 0x22, ...).
rs, rt, rd 5-bit register numbers: two sources and a destination (rd for R types; rt doubles as the I type destination).
shamt 5-bit shift amount used by sll/srl; 0 for everything else.
Sign extension Copying bit 15 of a 16-bit immediate into bits 31-16 so its value is preserved in 32 bits.
PC-relative addressing Branch targets stored as a word offset from PC + 4 rather than as an absolute address.
Pseudo-direct addressing Jump targets stored as a 26-bit word address, completed by the top 4 bits of PC + 4.
Word alignment Instructions and words live at addresses divisible by 4, so their bottom two bits are always 00.
Two's complement The binary representation of signed numbers; the top bit indicates negative values.

Submission

I encourage you to submit your answers to the questions (and ask your own questions!) using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section. You can find the link to the class notebook on the syllabus.