MIPS Architecture and Procedure Calls

What is a Basic Block?

A basic block is a sequence of instructions with no embedded branches (except at the end) and no branch targets (except at the beginning). A compiler identifies basic blocks for optimization. An advanced processor can accelerate the execution of basic blocks.

Six Steps Involved in Procedure Calling

1. Place parameters in registers.
2. Transfer control to the procedure.
3. Acquire storage resources.
4. Perform the desired operation.
5. Place the result in a register for the caller.
6. Return to the point of origin.

Register Saving Responsibilities

Between the caller and callee, the responsibility for saving registers is as follows:

• Temporary registers ($t*): Can be overwritten by the callee.
• Saved temporary registers ($s*): Saved and restored by the callee.

Caller:

• Places parameters in $a0-3.
• Transfers control using jal.

Callee:

• Acquires storage resources.
• Performs task.
• Places result in caller-accessible registers $v0-$v1.
• Returns control to caller.

Procedure Call and the $ra Register

During a procedure call, jal (jump and link) saves the address of the following instruction (PC+4) in register $ra.

C to MIPS Code Example 1

C code:

int leaf_example (int g, h, i, j) {
  int f;
  f = (g + h) - (i + j);
  return f;
}

MIPS code:

leaf_example:
  addi $sp, $sp, -4      ; Adjust stack for saving
  sw $s0, 0($sp)        ; Save $s0 to stack
  add $t0, $a0, $a1     ; g + h
  add $t1, $a2, $a3     ; i + j
  sub $s0, $t0, $t1     ; (g + h) - (i + j)
  add $v0, $s0, $zero   ; Result in $v0
  lw $s0, 0($sp)        ; Restore $s0
  addi $sp, $sp, 4      ; Adjust stack
  jr $ra                ; Return

C to MIPS Code Example 2

C code (strcpy):

void strcpy (char x[], char y[]) {
    int i;
    i = 0;
    while ((x[i]=y[i])!= '\0')
        i += 1;
}

MIPS code:

strcpy:
  addi $sp, $sp, -4     ; Adjust stack for 1 item
  sw $s0, 0($sp)       ; Save $s0
  add $s0, $zero, $zero  ; i = 0
L1:
  add $t1, $s0, $a1     ; Address of y[i] in $t1
  lbu $t2, 0($t1)      ; $t2 = y[i]
  add $t3, $s0, $a0     ; Address of x[i] in $t3
  sb $t2, 0($t3)       ; x[i] = y[i]
  beq $t2, $zero, L2    ; Exit if y[i] == 0
  addi $s0, $s0, 1      ; i = i + 1
  j L1                 ; Next iteration
L2:
  lw $s0, 0($sp)       ; Restore saved $s0
  addi $sp, $sp, 4     ; Pop 1 item from stack
  jr $ra                ; Return

Handling Long Branches

If beq $s0, $s1, L1 is too far to use L1 as a 16-bit address, the modified code would be:

  bne $s0, $s1, L2
  j L1
L2:
  ...

MIPS Addressing Modes

1. Immediate addressing
2. Register addressing
3. Base addressing
4. PC-relative addressing
5. Pseudodirect addressing

MIPS Synchronization Instructions

MIPS supports synchronization with the following instruction pair:

• Load linked: ll rt, offset(rs)
• Store conditional: sc rt, offset(rs)

Pseudo-instruction 'blt'

Branch if less than (blt) is not a native MIPS instruction, but the MIPS assembler supports the pseudo-instruction blt. The following MIPS code replaces the pseudo-code blt $t0, $t1, L:

  slt $at, $t0, $t1
  bne $at, $zero, L