Recitation 5
Please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.mit.edu) to authenticate, and then you will be redirected back to this page.
Table of Contents
1) Problem 1
Write a simple assembly program that computes the sum of two numbers (i.e. \text{sum}(x, y) = x + y) and follows the RISC-V calling convention.
unsigned sum(unsigned x, unsigned y) {
unsigned z = x + y;
return z;
}
2) Problem 2 (optional)
Write a simple assembly program that computes the product of two numbers (i.e. \text{mult}(x, y) = x \cdot y) and follows the RISC-V calling convention.
unsigned mult(unsigned x, unsigned y) {
unsigned z = x * y;
return z;
}
3) Problem 3
Write an assembly program that computes the square of the sum of two numbers
(i.e. \text{squareSum}(x, y) = (x + y)^2) and follows the RISC-V calling convention.
Note that in your assembly code, you have to call assembly procedures for
mult and sum. They are not provided to you, but they are fully functional
and obey the calling convention.
/* Compute square sum of args. */
unsigned squareSum(unsigned x, unsigned y) {
unsigned z = sum(x, y);
return mult(z, z);
}
4) Problem 4
Below is C code for a recursive implementation of binary search, which finds the index at which an element should be inserted into a sorted array to ensure that the array is still sorted after the insertion.
unsigned binary_search(int* arr, uint32_t start, uint32_t end, int element) {
if (start == end) {
return end;
}
mid = (start + end) / 2;
if (element < arr[mid]) {
end = mid;
} else {
start = mid + 1;
}
return binary_search(arr, start, end, element);
}
Below is a not so elegant, but valid, implementation of the function using RISC-V assembly.
binary_search: addi sp, sp, -8
sw ra, 4(sp)
sw s0, 0(sp)
mv s0, a2
beq a1, a2, done
add t0, a1, a2
srli t0, t0, 1
slli t1, t0, 2
add t1, a0, t1
lw t1, 0(t1)
if: bge _____________
mv a2, t0
j recurse
else: addi t0, t0, 1
mv a1, t0
recurse: call binary_search
mv s0, a0
done: mv a0, s0
lw s0, 0(sp)
lw ra, 4(sp)
L1: addi sp, sp, 8
ret
4.1) Problem 4.1
if to make the assembly implementation match the C code? Include bge in your answer.
4.2) Problem 4.2
binary_search?
The program's initial call to function binary_search occurs outside of the
function definition via the instruction call binary_search. The program is
interrupted during a recursive call to binary_search, just prior to the
execution of addi sp, sp, 8 at label L1. The diagram below shows the
contents of a region of memory. All addresses and data values are shown in hex.
The current value in the sp register is 0xEB0 and points to the location
shown in the diagram.
| Address | Data | |
| 0xEA4 | 0x0 | |
| 0xEA8 | 0x5 | |
| 0xEAC | 0xC4 | |
| SP → | 0xEB0 | 0x6 |
| 0xEB4 | 0xC4 | |
| 0xEB8 | 0x6 | |
| 0xEBC | 0xC4 | |
| 0xEC0 | 0xA | |
| 0xEC4 | 0xC4 | |
| 0xEC8 | 0x3E | |
| 0xECC | 0xCA4 | |
| 0xED0 | 0xCED |
4.3) Problem 4.3
arr at the beginning of the initial call to binary_search? Write CAN'T TELL if you cannot tell the value of the argument from the stack provided.
end at the beginning of the initial call to binary_search? Write CAN'T TELL if you cannot tell the value of the argument from the stack provided.
4.4) Problem 4.4
s0 right when the execution of binary_search is interrupted? Write CAN'T TELL if you cannot tell.
ra right when the execution of binary_search is interrupted? Write CAN'T TELL if you cannot tell.
4.5) Problem 4.5
call binary_search instruction that made the initial call to binary_search?
4.6) Problem 4.6
ret instruction?
5) Problem 5 (optional)
The following C program counts the minimum number of bits required to express a number. The
assembly code for the procedure is also shown after the program, along with a
stack trace showing the execution of countBits(10). The execution has been halted
just as it's about to execute the instruction labeled rtn:. The SP label on
the stack shows where the SP is pointing to when execution halted.
/* Counts the minimum numnber of bits required to express a number */
int countBits(unsigned x) {
unsigned y;
if (x == 0) return 0;
else {
/* Shifts x right by 1 bit. */
y = x >> 1;
return countBits(y) + 1;
}
}
countBits:
beqz a0, rtn
addi sp, sp, -8
sw s0, 4(sp)
sw ra, 0(sp)
srli s0, a0, 1
mv a0, s0
jal ra, countBits
addi a0, a0, 1
lw ra, 0(sp)
lw s0, 4(sp)
addi sp, sp, 8
rtn: jr ra
| 0x93 | |
| 0x240 | |
| 0x1 | |
A |
|
B |
|
| SP → | 0x240 |
| 0x5 | |
| 0x1108 | |
| 0x37 |
5.1) Problem 5.1 (optional)
A?
B?
5.2) Problem 5.2 (optional)
a0 at the time execution was halted? Please express the value in hex or write "CAN'T TELL".
s0 at the time execution was halted? Please express the value in hex or write "CAN'T TELL".
sp at the time execution was halted? Please express the value in hex or write "CAN'T TELL".
pc at the time execution was halted? Please express the value in hex or write "CAN'T TELL".
5.3) Problem 5.3 (optional)
countBits(10) function call?
6) Problem 6 (optional)
For each RISC-V instruction sequence below, provide the hex values of the
specified registers after each sequence has been executed. Assume that all
registers are initialized to 0 prior to each instruction sequence. Each
instruction sequence begins with the line (. = 0x0) which indicates that the
first instruction of each sequence is at address 0. Assume that each sequence
execution ends when it reaches the unimp instruction.
6.1) Problem 6.1 (optional)
. = 0x0
jal x5, L1
jal x6, end
L1: j L2
jal x6, end
L2:
jr x5
end: unimp
L1? 0x
L2? 0x
x5? 0x
x6? 0x
6.2) Problem 6.2 (optional)
. = 0x0
li x7, 0x600
mv x8, x7
loop: addi x8, x8, 4
lw x9, 0(x8)
sw x9, -4(x8)
blez x9, loop
lw x7, 0(x7)
end: unimp
The code above refers to certain locations in memory. Assume that the first 4
memory locations starting from address 0x600 have been initialized with the
following 4 words.
. = 0x600
# First 4 words at address 0x600
.word 0x60046004
.word 0x87654321
.word 0x12345678
.word 0x00000001
x7? 0x
x8? 0x
x9? 0x
7) Problem 7 (optional)
For each of the following code snippets, provide the value left in each register
after executing the entire code snippet (i.e. when the processor reaches the
instruction at the end label), or specify CAN'T TELL if it is impossible
to tell the value of a particular register. The code snippets are independent
of each other.
7.1) Problem 7.1 (optional)
code_start:
li x1, 0x26
lui x2, 0x24
blt x2, x1, L1
addi x1, x1, 1
L1:
add x1, x1, zero
end:
pc? 0x
x2? 0x
x1? 0x
7.2) Problem 7.2 (optional)
. = 0x100
li x4, 0x6
addi x5, zero, 0xC00
slli x4, x4, 8
or x6, x4, x5
end:
pc? 0x
x4? 0x
x5? 0x
x6? 0x
7.3) Problem 7.3 (optional)
. = 0x100
addi x7, zero, 0x204
li x8, 3
lw x9, -4(x7)
sw x8, 4(x7)
end:
. = 0x200
.word 0x01010101
.word 0xAAAAAAAA
.word 0x77777777
x9? 0x
8) Problem 8 (optional)
For the following C functions, does the corresponding RISC-V assembly obey the RISC-V calling conventions?
8.1) Problem 8.1 (optional)
int function_A(int a, int b) {
some_other_function();
return a + b;
}
function_A:
addi sp, sp, -8
sw a0, 8(sp)
sw a1, 4(sp)
sw ra, 0(sp)
jal some_other_function
lw a0, 8(sp)
lw a1, 4(sp)
add a0, a0, a1
lw ra, 0(sp)
addi sp, sp, 8
ret
8.2) Problem 8.2 (optional)
int function_B(int a, int b) {
int i = foo((a + b) ^ (a - b));
return (i + 1) ^ i;
}
function_B:
addi sp, sp, -4
sw ra, 0(sp)
add t0, a0, a1
sub a0, a0, a1
xor a0, t0, a0
jal foo
addi t0, a0, 1
xor a0, t0, a0
lw ra, 0(sp)
addi sp, sp, 4
ret
8.3) Problem 8.3 (optional)
int function_C(int x) {
foo(1, x);
bar(2, x);
baz(3, x);
return 0;
}
function_C:
addi sp, sp, -4
sw ra, 0(sp)
mv a1, a0
li a0, 1
jal foo
li a0, 2
jal bar
li a0, 3
jal baz
li a0, 0
lw ra, 0(sp)
addi sp, sp, 4
ret
8.4) Problem 8.4 (optional)
int function_D(int x, int y) {
int i = foo(1, 2);
return i + x + y;
}
function_D:
addi sp, sp, -4
sw ra, 0(sp)
mv s0, a0
mv s1, a1
li a0, 1
li a1, 2
jal foo
add a0, a0, s0
add a0, a0, s1
lw ra, 0(sp)
addi sp, sp, 4
ret