Discussion 4

9/17/02 Tue


Storage

The variables in C are abstraction of storage where values can be assigned or read. In assembly there are two kinds of storage: register and memory. Register is fast storage that can be accessed for arithmetic directly, but has limited number of units depending on the architecture. For example, MIPS has 32 registers. Memory allows to keep much larger storage space than registers, but cannot be used for arithmetic operations directly. In stead, data in the memory is loaded to the registers before the arithmetic operations. Variables have their associated types whereas there are no explicit types for registers and memory. The types are implied in the instruction -- an instruction uses word type or others uses double word.

 

C

Assembly

Storage

int i, n;
int array[100];

Register: $0, $1, ..., $31
Memory: 0 ($s1)

Arithmetic operations and assignments

Arithmetic operations in MIPS assembly takes two source registers and one destination register with the following form:

<Opname>  <dest_reg> , <source_reg1> , <source_reg2> 

For example,

ADD $s1, $s2, $s3        # $s1: a, $s2: b, $s3: c,   a = b + c

When an expression has more than two arithmetic operations, then it can be calculated in multiple instructions possibly with temporary registers.

For a = b + c - d,

ADD $s1, $s2, $s3        # $s1: a, $s2: b, $s3: c, $s4: d

SUB $s1, $s1, $s4

For a = (b + c) - (d + e),

ADD $s1, $s2, $s3        # $s1: a, $s2: b, $s3: c, $s4: d, $s5: e

ADD $t1, $s4, $s5

SUB $s1, $s1, $t1 

Register zero ($0) is hardwired to zero and has always zero value. And memory operations can be expressed with general operations by using register zero.

For a = b,    ADD $s1, $s2, $0   

For a = -b,    SUB $s1, $0, $s2

Instructions that try to modify register zero do nothing because the register zero cannot be modified.

ADD $0, $s1, $0

Load and store instructions

<Opname>  <reg1> , <offset> ( <reg2> )

LW $s1, 4 ($s2)        # load a word to $s1 from the source memory. The source memory is 4-bytes after the location $s2 points to.

SW $s1, 4 ($s2)        # store a word from $s1 to the memory which is 4-bytes after the location $s2 points to.

Immediate value

An immediate value is a constant that is embedded in an instruction. This allows simple integer values can be used for operations without load.

ADDI $s1, $s2, 1    # a = b + 1

Shift operations

SLL $s1, $s2, 4:    shift the value in the register $s2 four bits to the left and write it to the register $s1. This multiplies $s2 with 16.

SRL $s1, $s2, 2:    shift the value in the register $s2 two bits to the right and write it to the register $s1. This divides $s2 by 4.

Shift operations substitutes multiplication and division when an operand is a power of two (2, 4, 8, etc) and faster.

 

Branch operations

Can we write any programs with assembly with the instructions we learned? We need control flow instructions to implement a branch and a loop.

In C, there are several control flow instructions, but all of them can be expressed using if and goto. In MIPS assembly, there are conditional branches (beq/bne) and an unconditional jump  ( j ).

Original constructs Using only if and goto Assembly
if    if (a == b)
       x = y + z; 
   if (a != b) goto L1;
   x = y + z;
L1:
   BNE $s1, $s2, L1
   ADD $t1, $t2, $t3
L1:
if else    if (a == b)
       x = y + z; 
   else
       x = y - z;
   if (a != b) goto L1;
   x = y + z;
   goto L2;
L1:x = y - z;
L2:
   BNE $s1, $s2, L1
   ADD $t1, $t2, $t3
   J   L2
L1:SUB $t1, $t2, $t3
L2:
if else if else    if (a == b)
       x = y + z; 
   else if (c == d)
       x = y - z;
   else
       x = y + 1;
   if (a != b) goto L1;
   x = y + z;
   goto L3;
L1:if (c != d) goto L2;
   x = y - z;
   goto L3;
L2:x = y + 1;
L3:
   BNE $s1, $s2, L1
   ADD $t1, $t2, $t3
   J   L3
L1:BNE $s3, $s4, L2
   SUB $t1, $t2, $t3
   J   L3
L2:ADDI $t1, $t2, 1
L3:
do while    do
      a = a - 1;
   while (a != 0);
L1:a = a - 1;
   if (a != 0) goto L1;
L1:ADDI $s1, $s1, -1
   BNE  $s1, $0, L1
while    while (a != 0)
      a = a - 1; 
L1:if (a == 0) goto L2;
   a = a - 1;
   if (a != 0) goto L1;
L2:
L1:BEQ  $s1, $0, L2
   ADDI $s1, $s1, -1
   BNE  Ss1, $0, L1
L2:

What if we need to evaluate inequality such as <, >, <= or >=?

We can use SLT. 

SLT $t1, $s1, $s2        # $t1 is set to 1 if $s1 < $s2. Otherwise it is set to zero.

Original constructs Assembly
==    if (a == b)
       x = y + z; 
   BNE $s1, $s2, L1
   ADD $t1, $t2, $t3
L1:
!=    if (a != b)
       x = y + z; 
   BEQ $s1, $s2, L1
   ADD $t1, $t2, $t3
L1:
<    if (a < b)
       x = y + z; 
   SLT $t4, $s1, $s2
   BEQ $t4, $0, L1
   ADD $t1, $t2, $t3
L1:
<=    if (a <= b)
       x = y + z; 
   SLT $t4, $s2, $s1
   BNE $t4, $0, L1
   ADD $t1, $t2, $t3
L1:

Short quiz

The following program finds the sum of A[0], A[1], A[2] and A[100]. Complete an assembly code that does the same.

int A[100];
int main(void)
{
	int i, sum;
	fill_the_array(A, 100);

	sum = 0;
	i = 100;
	do {
		i = i - 1;
		sum += A[i];
	} while (i != 0);
	/* The sum is in 'sum' */
}
Intermediate C code
int A[100];
int main(void)
{
	int i, sum;
	fill_the_array(A, 100);

	sum = 0;		/* sum: $s1 */
	i = 100;		/* i: $s2 */
L1:	i = i - 1;
	sum += A[i];		/* A: $s3 */
	if (i != 0) goto L1;
	/* The sum is in 'sum' */
}
Assembly code
	ADD $s1, $0, $0
	ADDI $s2, $0, 100
	ADDI $s3, $s3, 400
L1:	ADDI $s2, $s2, -1
        ___________________

	LW $t1, 0 ($s3)
	ADD $s1, $s1, $t1
	___________________

Back to Top

Revised: 09/15/02 .