Loops

1Learning Outcomes¶

• Implement a for loop in assembly.

We’ll cover the for loop implementation in detail below, then leave the other loops for you to reference later.

2C code¶

The below C loop adds up 20 integers in an array arr and stores the result in sum.

1
2
3
4
5
6
7
int arr[20];
... // fill arr with data
int sum = 0;
for (int i=0; i<20; i++) {
    sum += arr[i];
}
// ...

Implementing loops in assembly is similar to writing loops with goto syntax. Click to show how we can rewrite the loop above with goto and labels.

1
2
3
4
5
6
7
8
9
      int arr[20];
      …
      int sum = 0;
      int i = 0;
Loop: if(i >= 20) goto End
      sum += arr[i];
      i++;
      goto Loop
End:  // …

3RISC-V translation¶

Here is the full assembly translation of the original C code.

    add   x9  x8  x0
    add  x10  x0  x0
    add  x11  x0  x0
    addi x13  x0  20
Loop:
    bge  x11 x13 End
    lw   x12  0(x9)
    add  x10 x10 x12
    addi  x9  x9   4
    addi x11 x11   1
    j Loop
End:
    ...

3.1Register Assignments¶

3.2Line-by-Line¶

The assembly again, now commented. Hover to reference the original C code.

1
2
3
4
5
6
7
8
9
10
11
12
13
    add   x9  x8  x0 # &arr[0]
    add  x10  x0  x0 # sum = 0
    add  x11  x0  x0 # i=0
    addi x13  x0  20
Loop:
    bge  x11 x13 End # if i >= 20, then branch
    lw   x12  0(x9)
    add  x10 x10 x12 # sum += arr[i]
    addi  x9  x9   4 # &arr[i+1]
    addi x11 x11   1 # i++
    j Loop
End:
    ...

Line 1. add x9 x8 x0. Put the first (zero-th) element in register x9.

Line 2. add x10 x0 x0. Initialize the sum to zero in register x10.

Line 3: add x11 x0 x0. Initialize the loop variable i to zero in register x11.

Line 4: addi x13 x0 20 (li x13 20). Put the value 20 in register x13 to use for the branch instruction.

Line 5-6: bge x11 x13 End. If the current loop variable is greater than or equal to zero, branch to the End instruction in Line 13.

• bge exits loop if R[x11] >= R[x13] is true.

• Otherwise if false, then i < 20, so continue in the loop.

• Note that the labels Loop and End are not instructions; rather, they are bound to instruction addresses (i.e., Loop is the address of the bge instruction).

Line 7: lw x12 0(x9). Get the value of arr[i] and put it in register x12.

Line 8: add x10 x10 x12. Add arr[i] to the current sum in register x10; write the result back to register x10.

Line 9: addi x9 x9 4. Get the address of the next element, &arr[i+1]. Update the byte address in register x9 by adding 4 (sizeof(int) is 4).

Line 10: addi x11 x11 1. Increment i by one. This is needed for the branch instruction comparison.

Line 11: j Loop Jump to the branch instruction.

Line 12: If we reached this instruction, we have exited the loop.

3.3Run Demo¶

You can run the below demo in a RISC-V simulator like Venus.

.data
output: .word   1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

.text
    # `output` is a pointer to an int array
    # set x8 to `output`
    la    x8 output

    add   x9  x8  x0
    add  x10  x0  x0
    add  x11  x0  x0
    addi x13  x0  20
Loop:
    bge  x11 x13 End
    lw   x12  0(x9)
    add  x10 x10 x12
    addi  x9  x9   4
    addi x11 x11   1
    j Loop
End:
    mv a0 x10
    jal print_int

    # passing 10 to ecall will terminate the program
    li a0 10
    ecall

# prints out one integer
# input values: a0: the integer to print
# does not return anything
print_int:
    # to print an integer, we need to make an ecall with a0 set to 1
    # the thing that will be printed is stored in register a1
    # this line copies the integer to be printed into a1
    mv a1 a0
    # set register a0 to 1 so that the ecall will print
    li a0 1
    # print the integer
    ecall
    # return to the calling function
    jr ra

4Control Structure Reductions¶

We describe “go-to” (heh) ways of reducing common loops to structures that are more directly translatable into assembly.

4.1if conditional¶

Consider the below C code. The code reduction uses the idea leveraged in Example 1 and Example 2 to flip the conditional with a goto statement.

if(cond) {
    line1;
    line2;
}
line3;

if(!cond) goto AfterIf;
line1;
line2;

AfterIf:
    line3;

4.2while loop¶

while(cond) {
    line1;
    line2;
} 
line3;

Loop:
    if(!cond) goto AfterLoop;
    line1;
    line2;
    goto Loop;

AfterLoop:
    line3;

4.3while loop with break¶

In the below code, break reduces to a goto statement:

while(true) {
    line;
    break;
}
line;

while(true) {
    line;
    goto AfterWhile;
}
AfterWhile:
    line;

4.4for loop¶

for(startline;cond;incline) {
    line1;
    line2;
} 
line3;

We recommend first translating for loops into the equivalent while loop:

startline;
while(cond) {
    line1;
    line2;
    incline;
} 
line3;

Finally, reduce with goto.

startline;

Loop:
    if(!cond) goto AfterLoop
    line1;
    line2;
    incline;
    goto Loop

AfterLoop:
    line3;

4.5do-while loop¶

The C code:

do {
    line1;
    line2;
} while(cond)
line3;

Loop:
    line1;
    line2;
    if(cond) goto Loop;
 
line3;

5Appendix: goto¶

In C, the goto Label; statement sets the next line to execute to be the line labeled with Label. This labeled line can be anywhere else in the program.

Nevertheless, we share a few goto examples in C, for those of you who want more practice writing code more amicable to direct assembly translation. We encourage you to take these examples with a grain of salt.

5.1malloc example¶

Consider the below code. We would like to rewrite this code in case any malloc call fails and returns NULL.

int* a = malloc(sizeof(int)*1000);
int* b = malloc(sizeof(int)*1000000);
int* c = malloc(sizeof(int)*1000000000);
FILE* d = fopen(filename);

The below code is one attempt, though it fails to free previous malloc blocks.

int* a = malloc(sizeof(int)*1000);
if(a == NULL) allocation_failed();
int* b = malloc(sizeof(int)*1000000);
if(b == NULL) allocation_failed();
int* c = malloc(sizeof(int)*1000000000);
if(c == NULL) allocation_failed();
FILE* d = fopen(filename);
if(d == NULL) allocation_failed();

The final code uses goto to free previously allocated blocks upon any single failure.

int* a = malloc(sizeof(int)*1000);
if(a == NULL) goto ErrorA;
int* b = malloc(sizeof(int)*1000000);
if(b == NULL) goto ErrorB;
int* c = malloc(sizeof(int)*1000000000);
if(c == NULL) goto ErrorC;
FILE* d = fopen(filename);
if(d == NULL) {
           free(c);
ErrorC:    free(b);
ErrorB:    free(a);
ErrorA:    allocation_failed();
}