Introduction

Let’s see one of the ISA(Instruction Set Architecture), the MIPS.

• Contents
  • Instruction Set
  • MIPS 32 ISA
  • MIPS Arithmetic Instructions
  • MIPS Instruction Fields
  • MIPS Register File
  • MIPS Data Types
  • Dealing with Constants
  • Shift Operations
  • Logical Operation
  • Decision Making
  • Compiling While Loops
  • Switch Statement
  • Procedure and Function
  • The structure of Memory

Instruction Set

Different computers have different instruction sets. But many aspects in common, so many early and modern computers have simple instruction sets. We will see in detail about one of the instruction set, the MIPS, made on Stanford University.

RISC, Reduced Instruction Set Computer, is now used in modern computers, because this is more efficient on compilers. And this is more simple and have small operations than other instruction sets.

MIPS 32 ISA

Now, let’s see in detail about MIPS-32 ISA. This is organized of these instructions:

• Computational
• Load/Store
• Jump and Branch
• Floating Point
• Memory Management
• Special

MIPS-32 ISA has 32-bit register, and has 3 instruction formats. All formats fixed 32-bit wide.

This is satisfied on the four design principles :

• Simplicity favors regularity.
  • fixed size instructions.
  • small number of instruction formats.
  • opcode(operation code) is always the first 6 bits.
• Smaller is faster.
  • limited instruction set.
  • limited number of registers in register file.
  • limited number of addressing modes.
• Make the common case fast.
  • arithmetic operands from the register file (NOT from memory), called load-store machine
  • allow instructions to contain immediate operands.
• Good design demands good compromises.
  • limited “three” instruction formats.

MIPS Arithmetic Instructions

This is MIPS assembly language arithmetic statement.

add $t0, $s1, $s2
sub $t0, $s1, $s2

Each arithmetic instruction performs one operation, and each specifics exactly three operands that are all contained in the datapath’s register file. (e.g. $t0, $s1, $s2)

This assembly language code is put on instruction format like this :

Then, how MIPS can calculate more complex expression like this?

h = (b - c) + d

Assuming variable b is stored in register $s1, c is stored in $s2, and d is stored in $s3 and the result is to be left in $s0. Then the assembly code can be formed like this :

sub $t0, $s1, $s2
add $s0, $t0, $s3

MIPS Instruction Fields

MIPS fields are given names to make them easier to refer to :

• op : opcode that specifies the operation
• rs : register file address of the first source operand
• rt : register file address of the second source operand
• rd : register file address of the result’s destination
• shamt : shift amount (for shift instructions)
• funct : function code augmenting the opcode

Therefore, R-type Instruction format is in total 32-bits.

MIPS Register File

MIPS Register file holds 32-bit register with two read ports and one write port.

Registers’ characteristics are :

• Faster than main memory. Note that register files with more location are slower. For example, a 64 word file could be as much as 50% slower than a 32 word file.
• Easier for a compiler to use register file, compared to stack. For instance, (A x B) - (C x D) - (E x F) can do multiplies in any order in register file, not on stack memory.
• Can hold variables with improved code density. Because register are named using fewer bits than a memory location. In MIPS, 5 bits to locate the position in register file.

Here are the MIPS Register Convention :

But, there are so many variables in running program. How register handle with a lost of variables?

Memory compacted as a large, single-dimensional array. So, an address acts as the index into the memory array.

MIPS has two basic data transfer instructions for accessing memory, load and store.

lw $t0, 4($s3) #load word from memory
sw $t0, 8($s3) #store word to memory

Let’s see how load instruction works. Consider the load-word and store-word instructions.

For data transfer instructions, MIPS use I-type format.

And here are the example for load instruction for lw $t0, 24($s3) :

Note that A 16-bit offset means access is limited to memory locations within a range of +2^13-1 to -2^13 (~8,192) words. In other word, +2^15-1 to -2^15 (~32,768) bytes. (1 word = 4 byte in MIPS. Word is a unit for store single data.)

So, that load instruction works like this :

Note that the memory address is formed by summing the constant portion of the instruction and the contents of the second (base) register.

Let’s see the applied example.

Example 1 : Assuming variable b is stored in $s2 and that the base address of array A is in $s3, what is the MIPS assembly code for the C statement? Assume array A is 4-bytes.

A[8] = A[2] - b

Answer :

lw  $t0, 8($s3) # 8 means address of A[2]
sub $t0, $t0, $s2 # variable b is stored in $s2
sw  $t0, 32($s3) # 32 means address of A[8]

Example 2 : Assuming that the base address of array A is in register $s4, and variable b, c, and i are in $s1, $s2, and $s3, respectively. what is the MIPS assembly code for the C statement? Assume array A is 4-bytes and array A starts on address 0.

c = A[i] - b

Answer :

add $t1, $s3, $s3  # array index i is in $s3
add $t1, $t1, $t1  # temp reg $t1 holds 4*i
add $t1, $t1, $s4  # address of A[i] now in $t1
lw  $t0, 0($t1)    # load A[i]
sub $s2, $t0, $s1  # A[i] - b

MIPS DATA TYPES

Basically, there are some types to explain the architecture :

• 4 bits is a nibble
• 8 bits is a byte
• 16 bits is a half-word
• 32 bits is a word
• 64 bits is a double-word

MIPS use byte type(8 bits) to store data, use ASCII to decoded to character, and use 2’s complement to represent integer.

Also, MIPS aligned data as word type(32 bits).

And, MIPS use Big Endian to store data as byte. Big Endian store data from lower address to higher address, and Little Endian store data from higher address to lower address.

Loading and Storing data as byte in the instruction field, MIPS use I format to operate it.

When a byte(8 bits) get loaded and stored,

• load byte places one byte from memory to the rightmost 8 bits of the destination register.

  If other bits remain in the register, zero-extends it and loads it into the register. As MIPS use 2’s complement, sign-extends to remaining bits for minus integer.

• Store byte takes one byte from the rightmost 8 bits of a register and writes it to a byte in memory.

  If other bits remain in the memory word, store byte leaves the other bits in the memory word intact.(leaving the other bytes in the memory word unchanged)

When a half word(16 bits) get loaded and stored,

• Load byte process is same when a byte get loaded, only difference is 8 bits to 16 bits.
• Store byte is too.

Dealing with Constants

Small constants are used quite frequently in a common programs. May 50% of operands in many common programs.

A = A + 5;
B = B + 1;
C = C - 18;

There are some solutions to solve this issue :

1. Put “typical constants” in memory and load them.
2. Create hard-wired registers (like $zero) for constants like 1, 2, 4, 10, …
3. Include constants inside arithmetic instructions.

What is the best solution?

1. Load data from memory is slow, so solution 1 is not good.
2. Load data from register is faster than memory. So solution 2 might be good. But…
3. It is the fastest way to operate arithmetic instructions, because instruction has constant so load process isn’t needed.

So, MIPS architecture select solution 3 to solve this issue. Therefore, MIPS offer immediate instructions for solution 3 :

addi $s3, $s3, 4   #$s3 = $s3 + 4
slti $t0, $s2, 15
# "Set less than" command.
# $t0 = 1 if $s2 < 15

But, how about larger constants? When there are 32 bit constant to load into a register, we must use two instructions (lui + ori).

• lui : “load upper immediate” instruction to store higher order bits.

  lui $t0, 1111111111111111
  

• Then, must get the lower order bits right, use ori instruction.

  ori $t0, $t0, 0000000000000000
  

  Finally, we can get 1111111111111111 0000000000000000 within a register.

Shift Operations

There are shamt(shift amount) section in R-type format. What does it?

Shift operation is used for packing and unpacking 8-bit char/number/data into 32-bit words.

• Below is the logical operation commands.

Note that the empty bit space after shift operation is filled with zero.

• An arithmetic shift(sra) maintain the arithmetic correctness of the shifted value. A shifted right one bit should be 1/2 of tis original value, and a number shifted left should be 2 times its original value.

  sra uses the most significant bit (sign bit) as the bit shifted in. There is no need for a sla, because sll works for arithmetic left shifts.

Logical Operation

• There are a number of bit-wise logical operations in the MIPS ISA.

• AND operation is used to mask bits in a word.

  It select some bits and clear others to 0 for mask.

  

• OR operation is used to include bits in a word.

  It set some bits to 1, leave others unchanged.

  

• NOT operation is sued to invert bits in a word. Also, NOT operation is used to implement NOR. Note that there are NOR operation in MIPS instead of NOT.

  

Decision Making

It is alternative of the control flow like if statement.

Note that opposite condition is used in assembly language. if you check equal for some variable, you should bne(branch not equal) keyword to make the decision.

bne/beq uses I format instruction.

offset field is used to various uses,

• Memory address offset for lw & sw
• Immediate constant value(which is contained in instruction itself)
• Branch offset for target (branch distance)

Also, these 3 cases are used for sign extension.

In this case, it is used with the register and add its value with 16-bit offset (branch distance).

The register is named as Instruction Address Register(i.e., PC register), its use is automatically implied by instruction. PC gets updated (PC+4) during the fetch cycle so that it holds the address of the next instruction.

The branch distance has limit between -2^15 to 2^15+1 instructions (word, not byte!!) from the branch instruction. It is made by concatenating two low-order zeros to make it a word address, and then sign-extending with those 18 bits.

However, is it necessary for concatenating two lower order zeros? Why not just store the word offset in the 16 bit immediate field? If two low order zeros does not to be concatenated, would limit the branch distance to -2^13 to 2^13+1, so it is necessary to extend more branch distance size. Also, it doesn’t make more complex for its circuit.

From now, we have learned beq, bne, but what about other kinds of branches(e.g., branch-if-less-than)? For this, we need another instruction, slt.

There are alternative versions of slt.

• Since constant operands are popular in comparisons, MIPS also has slti.

  

• We can use slt, beq, bne and the fixed value of 0 in register $zero to create other conditions. Note that blt, ble, bgt, bge is pseudo-branch instruction, not the real instruction.

  

  blt, ble, bgt, bge are not included in the ISA, because its too complicated. It would stretch the clock cycle time or it would take extra clock cycles per instruction.

MIPS also has an unconditional branch instruction or jump instruction, j.

j, jump instruction use J format. How is the jump destination address specified?

1. concatenating 00 as the 2 low-order bits to make it a word address.
2. concatenating the upper 4 bits of the currently updated PC(i.e., PC+4) to 32-bits address.

And, if the branch destination is further away than can be captured within 16 bits in I format, you can solve this by using J format unconditional branch, so branching can be much more far away.

For example,

Compiling While Loops

Compile the C while loop to the assembly code, that is the combination of instructions what we’ve learned.

Consider that where i is in $s0, j is in $s1, and k is in $s2. and C code is this :

Another example. Consider that where i is in $s3, k is in $s5, and the base address of the array save is in &s6.

Switch Statement

Then, how about the switch-case statement in C? MIPS ISA is ready for that by prepared jr instruction.

jr $t1  #jump to register. go to address in $t1

Consider this example. Assuming that k is in $s2 and three sequential words in memory starting at the address $t4 have the addresses of the labels L0, L1, and L2. Switch this C code to assembly code.

Procedure and Function

Through this long article, we’ve learned how MIPS ISA converts C code to this own assembly code. Finally, we will see how the MIPS change C function to assembly code.

Procedures (a.k.a. subroutines, functions) allow the programmer to structure programs. It makes easier to understand and debug, and allows code to be reused. Procedures also allow the programmer to concentrate on one portion of the code at a time. And, procedure parameters act as barriers between the procedure and the rest of the program and data.

So, how MIPS makes procedure and function in assembly code? There are six steps in execution of procedure.

1. Caller places parameters in a place where the callee can access them.
   • $a0 - $a3 : four argument registers.
2. Caller transfers the control to the callee.
3. Callee acquires the storage resources needed.
4. Callee performs the desired task.
5. Callee places the result value in a place where the caller can access it.
   • $v0 - $v1 : two value registers for result values
6. Callee returns the control to the caller.
   • $ra : one return address register to return to the point of origin.

As Caller and callee concept are showed, we need to see MIPS registers again to solve the question : what “Preserved on call” means?

If “Preserved on call” is no, that means MIPS does not have to save the previous value. If caller need the value after calling, the caller has to save that register. (So “caller-saved” is said as otherword.)

If “Preserved on call” is yes, that means MIPS saves the value after calling. So, if callee want to use that registers during calling, the callee has to save the register. (So “callee-saved” is said as otherword.)

So, how can we write assembly code for use procedure and function? We can use jal instruction for that.

jal ProcedureAddress #jump and link.

jal instruction do saves PC+4 in register $ra to have a link to the next instruction for the procedure return, and jumps to ProcedureAddress.

And if the procedure ends inside the procedure, use jr instruction to return, like return command in C.

Let’s see the example. Assume that there are gcd(i, j) function, and we need to implement and use it as assembly code. How can we do this?

1. Prepare argument. The caller puts the i and j in $a0 and $a1 and issues

   jal gcd ## jump to routine gcd
   

2. Then, the callee computes the GCD, puts the result in $v0, and returns control to the caller using jr.

   gcd: ....  #code to compute gcd
   	jr $ra #return
   

But you may still have the question : what if the callee needs to use more arguments or return value? For this, callee uses a stack memory, a last-in-first-out queue.

One of the general registers, $sp($29), is used to address the stack(which grows from high address to low address.)

• Add data onto the stack - push
  • $sp = $sp - 4
  • Push data on stack at new $sp.
• Remove data from the stack - pop
  • Pop data from stack at $sp
  • $sp = $sp + 4

But, this method use memory instead of only registers, so if the number of parameters is increased, execution time is also increased.

The structure of Memory

Finally, we will end this long journey by understand the structure of MIPS memory. Did you have the question about how the data and your source code can be saved at one space? Here are the answer :

MIPS memory has 3 types of memory : stack, heap, and static.

• Stack memory saves variables and procedures. For example, variables, array, functions, etc.
• Heap memory saves dynamic data. For example, dynamic array, linked list, etc.
• Static memory saves static data, a special space that can access from everywhere during runtime. It is same as static keyword in C.