HIGH-LEVEL CONTROL STATEMENTS
• How do we translate other high-level control statements (while, do, for)?
• We can first express the C statement using C if and goto statements.
• After that, we can translate using MIPS unconditional jumps, comparisons, and
conditional branches.
TRANSLATING A FOR STATEMENT
• Consider the following source code:
sum = 0;
for(i=0; i<100; i++)
sum += a[i];
• First, we replace the for statement using an if and goto statements.
sum = 0;
i = 0;
goto test;
loop: sum += a[i];
i++;
test: if (i < 100) goto loop;
TRANSLATING A FOR STATEMENT
• Now for the MIPS instructions. Assume sum, i and the starting address of a are
associated with $t2, $t3, and $t4 respectively and that $t5 is available.
li $t2, 0 # sum = 0
move $t3, $zero # i = 0
j test
loop: sll $t5,$t3,2 # temp = i * 4
addu $t5,$t5,$t4 # temp = temp + &a
lw $t5,0($t5) # load a[i] into temp
addu $t2,$t2,$t5 # sum += temp
addiu $t3,$t3,1 # i++
test: slti $t5,$t3,100 # test i < 100
bne $t5,$zero,loop # if true, goto loop
MIPS Instruction Set
Arithmetic Instructions
Instruction Example Meaning Comments
add add $1,$2,$3 $1=$2+$3
subtract sub $1,$2,$3 $1=$2-$3
add immediate addi $1,$2,100 $1=$2+100 "Immediate" means a constant
number
add unsigned addu $1,$2,$3 $1=$2+$3 Values are treated as unsigned
integers,
not two's complement integers
subtract unsigned subu $1,$2,$3 $1=$2-$3 Values are treated as unsigned
integers,
not two's complement integers
add immediate addiu $1=$2+100 Values are treated as unsigned
unsigned $1,$2,100 integers,
not two's complement integers
Multiply (without mul $1,$2,$3 $1=$2*$3 Result is only 32 bits!
overflow)
Multiply mult $2,$3 $hi,$low=$2*$3 Upper 32 bits stored in special
register hi
Lower 32 bits stored in special
register lo
Divide div $2,$3 $hi,$low=$2/$3 Remainder stored in special
register hi
Quotient stored in special registerlo
1
MIPS Instruction Set
Logical
Instruction Example Meaning Comments
and and $1,$2,$3 $1=$2&$3 Bitwise AND
or or $1,$2,$3 $1=$2|$3 Bitwise OR
and immediate andi $1,$2,100 $1=$2&100 Bitwise AND with immediate value
or immediate or $1,$2,100 $1=$2|100 Bitwise OR with immediate value
shift left logical sll $1,$2,10 $1=$2<<10 Shift left by constant number of bits
shift right logical srl $1,$2,10 $1=$2>>10 Shift right by constant number of bits
Data Transfer
Instruction Example Meaning Comments
load word lw $1=Memory[$2+100] Copy from memory to register
$1,100($2)
store word sw Memory[$2+100]=$1 Copy from register to memory
$1,100($2)
load upper lui $1,100 $1=100x2^16 Load constant into upper 16 bits.
immediate Lower 16 bits are set to zero.
load address la $1,label $1=Address of label Pseudo-instruction (provided by
assembler, not processor!)
Loads computed address of label (not its
contents) into register
load immediate li $1,100 $1=100 Pseudo-instruction (provided by
assembler, not processor!)
Loads immediate value into register
2
MIPS Instruction Set
move from hi mfhi $2 $2=hi Copy from special register hi to general
register
move from lo mflo $2 $2=lo Copy from special register lo to general
register
move move $1,$2 $1=$2 Pseudo-instruction (provided by
assembler, not processor!)
Copy from register to register.
Conditional Branch
Instruction Example Meaning Comments
branch on equal beq if($1==$2) go to Test if registers are equal
$1,$2,100 PC+4+100
branch on not equal bne if($1!=$2) go to Test if registers are not
$1,$2,100 PC+4+100 equal
branch on greater than bgt if($1>$2) go to Pseduo-instruction
$1,$2,100 PC+4+100
branch on greater than or bge if($1>=$2) go to Pseduo-instruction
equal $1,$2,100 PC+4+100
branch on less than blt if($1<$2) go to Pseduo-instruction
$1,$2,100 PC+4+100
branch on less than or ble if($1<=$2) go to Pseduo-instruction
equal $1,$2,100 PC+4+100
3
MIPS Instruction Set
Comparison
Instruction Example Meaning Comments
set on less than slt $1,$2,$3 if($2<$3)$1=1; Test if less than.
else $1=0 If true, set $1 to 1. Otherwise, set $1
to 0.
set on less than slti if($2<100)$1=1; Test if less than.
immediate $1,$2,100 else $1=0 If true, set $1 to 1. Otherwise, set $1
to 0.
Unconditional Jump
Instruction Example Meaning Comments
jump j 1000 go to address 1000 Jump to target address
jump register jr $1 go to address stored in $1 For switch, procedure return
jump and link jal 1000 $ra=PC+4; go to address 1000 Use when making procedure call.
This saves the return address in $ra
System Calls
Service Operation Code Arguments Results
(in
$v0)
print_int Print integer number (32 bit) 1 $a0 = integer to be None
printed
print_float Print floating-point number (32 bit) 2 $f12 = float to be None
printed
print_double Print floating-point number (64 bit) 3 $f12 = double to be None
printed
4
MIPS Instruction Set
print_string Print null-terminated character string 4 $a0 = address of None
string in memory
read_int Read integer number from user 5 None Integer
returned in
$v0
read_float Read floating-point number from user 6 None Float
returned in
$f0
read_double Read double floating-point number from 7 None Double
user returned in
$f0
read_string Works the same as Standard C 8 $a0 = memory None
Library fgets() function. address of string
input buffer
$a1 = length of string
buffer (n)
sbrk Returns the address to a block of 9 $a0 = amount address in
memory containing n additional bytes. $v0
(Useful for dynamic memory allocation)
exit Stop program from running 10 None None
print_char Print character 11 $a0 = character to be None
printed
read_char Read character from user 12 None Char
returned in
$v0
exit2 Stops program from running and returns 17 $a0 = result (integer None
an integer number)
Assembler Directives
Directive Result
.word w1, ..., wn Store n 32-bit values in successive memory words
.half h1, ..., hn Store n 16-bit values in successive memory words
.byte b1, ..., bn Store n 8-bit values in successive memory words
5
MIPS Instruction Set
.ascii str Store the ASCII string str in memory.
Strings are in double-quotes, i.e. "Computer Science"
.asciiz str Store the ASCII string str in memory and null-terminate it
Strings are in double-quotes, i.e. "Computer Science"
.space n Leave an empty n-byte region of memory for later use
.align n Align the next datum on a 2^n byte boundary.
For example, .align 2 aligns the next value on a word boundary
Registers
Register Register Description
Number Name
0 $zero The value 0
2-3 $v0 - $v1 (values) from expression evaluation and function results
4-7 $a0 - $a3 (arguments) First four parameters for subroutine
8-15, 24-25 $t0 - $t9 Temporary variables
16-23 $s0 - $s7 Saved values representing final computed results
31 $ra Return address
6
Translating C code to MIPS
why do it
C is relatively simple, close to the machine
C can act as pseudocode for assembler program
gives some insight into what compiler needs to do
what's under the hood
do you need to know how the carburetor works to drive your car?
does your mechanic need to know?
Register conventions
register conventions and mnemonics
Number Name Use
0 $zero hardwired 0 value
1 $at used by assembler (pseudo-instructions)
2-3 $v0-1 subroutine return value
4-7 $a0-3 arguments: subroutine parameter value
8-15 $t0-7 temp: can be used by subroutine without saving
16-23 $s0-7 saved: must be saved and restored by subroutine
24-25 $t8-9 temp
26-27 $k0-1 kernel: interrupt/trap handler
28 $gp global pointer (static or extern variables)
29 $sp stack pointer
30 $fp frame pointer
31 $ra return address for subroutine
Hi, Lo used in multiplication (provide 64 bits for result)
hidden registers
PC, the program counter, which stores the current address of the instruction
being executed
IR, which stores the instruction being executed
Arithmetic expression
simple arithmetic expression, assignment
int f, g, h, i, j; $s0 (g + h) - (i + j)
f = (g + h) - (i + j); $s1 i + j
$s2 h
$s3 i
$s4 j
assume variables are assigned to $s0, $s1, $s2, $s3, $s4 respectively
add $s0, $s1, $s2 # $s0 = g + h
add $s1, $s3, $s4 # $s1 = i + j
sub $s0, $s0, $s1 # f = (g + h) - (i + j)
Conditional: if
simple if statement
if ( i == j ) $s1 i
i++ ; $s2 j
j-- ;
in C: if condition is true, we "fall through" to execute the statement
if false, jump to next
in assembly, we jump if condition is true
need to negate the condition
assuming $s1 stores i and $s2 stores j:
bne $s1, $s2, L1 # branch if !( i == j )
addi $s1, $s1, 1 # i++
L1: addi $s2, $s2, -1 # j--
Conditional: if-else
if-else
if ( i == j ) $s1 i
i++ ; $s2 j
else
j-- ;
j += i ;
As before, if the condition is false, we want to jump.
bne $s1, $s2, ELSE # branch if !( i == j )
addi $s1, $s1, 1 # i++
ELSE: addi $s2, $s2, -1 # else j--
add $s2, $s2, $s1 # j += i
What's wrong with this picture?
Once we've done the if-body, we need to jump over the else-body
bne $s1, $s2, ELSE # branch if !( i == j )
addi $s1, $s1, 1 # i++
j NEXT # jump over else
ELSE: addi $s2, $s2, -1 # else j--
NEXT: add $s2, $s2, $s1 # j += i
Conditional: compound condition
if-else with compound AND condition: short-circuiting
if ( i == j && i == k ) // if ( <cond1> && <cond2> )
i++ ; // if body
else $s1 i
j-- ; // else body $s2 j
j = i + k ; $s3 k
Let <cond1> stand for (i == j) and <cond2> stand for (i == k).
Short-circuiting occurs when <cond1> evaluates to false.
The control flow then jumps over <cond2> and the if-body.
If <cond1> evaluates to true, we also want to check <cond2>.
If <cond2> evaluates false, we again jump, this time over the if-body,
and to the else-body.
If <cond2> is true, we fall-through to the if-body.
bne $s1, $s2, ELSE # cond1: branch if !( i == j )
bne $s1, $s3, ELSE # cond2: branch if !( i == k )
addi $s1, $s1, 1 # if-body: i++
j NEXT # jump over else
ELSE: addi $s2, $s2, -1 # else-body: j--
NEXT: add $s2, $s1, $s3 # j = i + k
Conditional: compound condition
if-else with compound OR condition: short-circuiting
use <cond1> to stand for (i == j) and <cond2> to stand for (i == k).
if ( <cond1> || <cond2> )
i++ ; // if-body $s1 i
else $s2 j
j-- ; // else-body $s3 k
j = i + k ;
Short-circuiting occurs when <cond1> evaluates to true
If <cond1> is false, we also want to check <cond2>
If <cond2> is false, we now jump to the else-body.
If <cond2> is true, we fall through to the if-body.
beq $s1, $s2, IF # cond1: branch if ( i == j )
# Notice branch on TRUE
bne $s1, $s3, ELSE # cond2: branch if ! ( i == k )
IF: addi $s1, $s1, 1 # if-body: i++
j NEXT # jump over else
ELSE: addi $s2, $s2, -1 # else-body: j--
NEXT: add $s2, $s1, $s3 # j = i + k
Conditional: switch
switch( i ) {
case 1: i++ ; // falls through
case 2: i += 2 ; $s1 i
break; $s4 temp
case 3: i += 3 ;
}
addi $s4, $zero, 1 # case 1: set temp to 1
bne $s1, $s4, C2_COND # false: branch to case 2 cond
j C1_BODY # true: branch to case 1 body
C2_COND: addi $s4, $zero, 2 # case 2: set temp to 2
bne $s1, $s4, C3_COND # false: branch to case 3 cond
j C2_BODY # true: branch to case 2 body
C3_COND: addi $s4, $zero, 3 # case 3: set temp to 3
bne $s1, $s4, EXIT # false: branch to exit
j C3_BODY # true: branch to case 3 body
C1_BODY: addi $s1, $s1, 1 # case 1 body: i++
C2_BODY: addi $s1, $s1, 2 # case 2 body: i += 2
j EXIT # break
C3_BODY: addi $s1, $s1, 3 # case 3 body: i += 3
EXIT:
Loops: while
$s1 i
If statement uses branch instruction. $s2 j
What about loops? $s3 k
Example:
while ( <cond> ) { L1: if ( <cond> ) {
<while-body> <while-body>
} goto L1 ;
}
If condition is true, execute body and go back, otherwise do next statement.
while ( i < j ) { L1: if ( i < j ) {
k++ ; k++ ;
i = i * 2 ; i = i * 2 ;
} goto L1 ;
}
L1: bge $s1, $s2, DONE # branch if ! ( i < j )
addi $s3, $s3, 1 # k++
add $s1, $s1, $s1 # i = i * 2
j L1 # jump back to top of loop
DONE:
Loops: for
for ( <init> ; <cond> ; <update> ) {
<for-body>
}
Equivalent while loop:
<init>; <init>;
while ( <cond> ) { L1: if ( <cond> ) {
<for-body> <for-body>
<update> <update>
} goto L1 ;
}
DONE:
Array: C
Problem: Given an array of int, calculate the sum of:
all the elements in the array
all the positive elements in the array
all the negative elements in the array
main () {
int i, size = 10, sum, pos, neg;
int arr[10] = {12, -1, 8, 0, 6, 85, -74, 23, 99, -30};
sum = 0; pos = 0; neg = 0;
for (i = 0; i < size; i++) {
sum += arr[i];
if (arr[i] > 0)
pos += arr[i];
if (arr[i] < 0)
neg += arr[i];
}
return 0;
}
Array: assembler
.text
.globl main
main:
la $s0, size # initialize registers
lw $s1, 0($s0) # $s1 = size
ori $s2, $0, 0 # $s2 = sum
ori $s3, $0, 0 # $s3 = pos
ori $s4, $0, 0 # $s4 = neg
# <init>
ori $s5, $0, 0 # $s5 = i
la $s6, arr # $s6 = &arr
# if (<cond>)
L1: bge $s5, $s1, DONE
# <for-body>
lw $s7, 0($s6) # $s7 = arr[i]
addu $s2, $s2, $s7 # sum += arr[i]
blez $s7, NEG # if ! (arr[i] > 0)
addu $s3, $s3, $s7 # pos += arr[i];
j UPDATE # goto UPDATE
NEG: bgez $s7, UPDATE # if ! (arr[i] < 0)
addu $s4, $s4, $s7 # neg += arr[i];
UPDATE: # <update>
addi $s5, $s5, 1 # i++
addi $s6, $s6, 4 # move array pointer
j L1 # goto L1
DONE:
# initialize data
.data
size: .word 10
arr: .word 12, -1, 8, 0, 6, 85, -74, 23, 99, -30
