Homework — Programming in Assembler (solution)
Load a 32-bit value into a register
Questions 1 & 2
The aim of these two question is to load an arbitrary 32-bit value A (\(a_{31},a_{30},\ldots,a_1,a_0\)) into a register.
Two instructions are used: ADDI and LUI.
LUI takes a 20-bit immediate B (\(b_{19},b_{18},\ldots,b_1,b_0\)), left shifts it by 12 bits (i.e. multiplies it by \(2^{12}\)) and stores the result into the destination register.
So if \(B = (a_{31},a_{30},\ldots,a_{13},a_{12})\), the destination register will contain the 32-bit value \((a_{31},a_{30},\ldots,a_{13},a_{12},0,\ldots,0)\).
ADDI takes a 12-bit immediate C (\(c_{11},c_{10},\ldots,c_1,c_0\)) and adds it to the content of a source register and stores the result into the destination register.
So if \(C = (a_{11},a_{10},\ldots,a_{1},a_{0})\) and if we the destination register of LUI as the source register for the ADDI, we should have in the destination register the value (\(a_{31},a_{30},\ldots,a_1,a_0\)).
However there is a catch.
ADDI considers that it operands are signed. So the operation in our case is:
\((-a_{31} \cdot 2^{31} + a_{30} \cdot 2^{30} + \cdots + a_{13} \cdot 2^{13} + a_{12} \cdot 2^{12} + 0 \cdot 2^{11} + \cdots + 0 \cdot 2^{0}) + (-a_{11} \cdot 2^{11} + a_{10} \cdot 2^{10} + \cdots + a_{0} \cdot 2^{0})\) \( = -a_{31} \cdot 2^{31} + a_{30} \cdot 2^{30} + \cdots + a_{13} \cdot 2^{13} + a_{12} \cdot 2^{12} - a_{11} \cdot 2^{11} + a_{10} \cdot 2^{10} + \cdots + a_{0} \cdot 2^{0}\)
If \(a_{11} = 0\), it is equal to :
\(-a_{31} \cdot 2^{31} + a_{30} \cdot 2^{30} + \cdots + a_{13} \cdot 2^{13} + a_{12} \cdot 2^{12} - 0 \cdot 2^{11} + a_{10} \cdot 2^{10} + \cdots + a_{0} \cdot 2^{0}\) \( = -a_{31} \cdot 2^{31} + a_{30} \cdot 2^{30} + \cdots + a_{13} \cdot 2^{13} + a_{12} \cdot 2^{12} + 0 \cdot 2^{11} + a_{10} \cdot 2^{10} + \cdots + a_{0} \cdot 2^{0}\)
which is represented as \(a_{31},a_{30},\ldots,a_{12},0,a_{10},\ldots,a_{0}\) in the destination register which is what we want.
If \(a_{11} = 1\), we have an issue.
In this case, instead of using the value \((a_{31},a_{30},\ldots,a_{13},a_{12})\) as the operand of LUI, we use \((a_{31},a_{30},\ldots,a_{13},a_{12}) + 1\).
The destination register of LUI will contains the value \(-a_{31} \cdot 2^{31} + a_{30} \cdot 2^{30} + \cdots + a_{13} \cdot 2^{13} + a_{12} \cdot 2^{12} + 1 \cdot 2^{12}\).
So result of the ADDI will be:
\((-a_{31} \cdot 2^{31} + a_{30} \cdot 2^{30} + \cdots + a_{13} \cdot 2^{13} + a_{12} \cdot 2^{12} + 2^{12}) + (-a_{11} \cdot 2^{11} + a_{10} \cdot 2^{10} + \cdots + a_{0} \cdot 2^{0})\) \( = -a_{31} \cdot 2^{31} + a_{30} \cdot 2^{30} + \cdots + a_{13} \cdot 2^{13} + a_{12} \cdot 2^{12} + 2^{12} - 2^{11} + a_{10} \cdot 2^{10} + \cdots + a_{0} \cdot 2^{0}\) \( = -a_{31} \cdot 2^{31} + a_{30} \cdot 2^{30} + \cdots + a_{13} \cdot 2^{13} + a_{12} \cdot 2^{12} + 2^{11} + a_{10} \cdot 2^{10} + \cdots + a_{0} \cdot 2^{0}\) \( = -a_{31} \cdot 2^{31} + a_{30} \cdot 2^{30} + \cdots + a_{13} \cdot 2^{13} + a_{12} \cdot 2^{12} + 1 \cdot 2^{11} + a_{10} \cdot 2^{10} + \cdots + a_{0} \cdot 2^{0}\)
which is represented as \(a_{31},a_{30},\ldots,a_{12},1,a_{10},\ldots,a_{0}\) in the destination register which is what we want.
Summary
To load a 32-bit constant to a register, if bit 11 is 0, we use LUI with an immediate containing the 20 most-significant bits of the constant to load them to a register and ADDI with this register as source and an immediate with 12 least-significant bits of the constant.
If bit 11 is 1, we use LUI with an immediate containing the 20 most-significant bits of the constant plus one and ADDI with this register as source and an immediate with 12 least-significant bits of the constant.
Examples:
# We want to load 0x12345678 (0001 0010 0011 0100 0101 | 0110 0111 1000) bit 11 = 0
lui x1, 0x12345 # 20 most-significant bits of the constant
# The destination register contains 0x12345000
addi x1, x1, 0x678 # 12 least-significant bits of the constant
# The destination register contains 0x12345678
# We want to load 0x12345F78 (0001 0010 0011 0100 0101 | 1111 0111 1000) bit 11 = 1
lui x1, 0x12346 # 20 most-significant bits of the constant + 1
# The destination register contains 0x12346000
addi x1, x1, 0xF78 # 12 least-significant bits of the constant
# The destination register contains 0x12345678
Use of variables
Question 3
# Fist we load the address of the variable i in register x1 (see previous question)
lui x1, 0x1000 # x1 contains 0x10000000 (no need for the ADDI here with this particular constant)
# Next we perform a read from memory to retrieve the value of i and stores it in register x2
lw x2, 0(x1) # The instruction computes an address: content of x1 + 0 = 0x1000000
# and reads the content of the memory at this address and stores it in x2
# So x2 contains the value of variable i
# Next we perfom the addition
addi x2, x2, 1 # x2 = x2 + 1 = i + 1
#Finaly we stores the result in memory
sw x2, 0(x1)
If/then/else constructions
If/then
Question 4
# Loads the content of variable i in x2
lui x1, 0x1000
lw x2, 0(x1)
# Tests if i != 0 and if so, jumps after the body of the if
# (we remember that x0 is always equals to 0)
bne x2, x0, after
# If branch (i = 1)
lw x2, 0(x1)
addi x2, x0, 1 # x2 = 0 + 1 = 1
sw x2, 0(x1)
# After the if (i = i + 1)
after:
lw x2, 0(x1)
addi x2, x2, 1 # x2 = x2 + 1 = i + 1
sw x2, 0(x1)
A compiler will certainly optimize the code shown above. Except in certain circumstances, it is not necessary to load the value of the variable i each time. It is also not necessary to store its value in memory inside of the if branch because it will be stored again later.
So a more optimized version is:
# Loads the content of variable i in x2
lui x1, 0x1000
lw x2, 0(x1)
# Tests if i != 0 and if so, jumps after the body of the if
# (we remember that x0 is always equals to 0)
bne x2, x0, after
# If branch (i = 1)
addi x2, x0, 1 # x2 = 0 + 1 = 1
# After the if (i = i + 1)
after:
addi x2, x2, 1 # x2 = x2 + 1 = i + 1
sw x2, 0(x1)
If/then/else
Question 5
Optimized version:
# Loads the content of variable i in x2
lui x1, 0x1000
lw x2, 0(x1)
# Tests if i != 0 and if so, jumps to the else branch
bne x2, x0, else
# If branch (i = 1)
addi x2, x0, 1 # x2 = 0 + 1 = 1
jal x0, after # Jumps to after (skip the else branch)
# Else branch (i = -i)
else:
sub x2, x0, x2 # x2 = 0 - x2 = -x2 = -i
# After the if (i = i + 1)
after:
addi x2, x2, 1 # x2 = x2 + 1 = i + 1
sw x2, 0(x1)
For loops
Question 6
# Loads the address of i in x1
lui x1, 0x1000
# The loop index (j) will be stored in x2
addi x2, x0, 0 # x2 = 0 + 0 = 0
# Stores 10 in x3 (used in the exit condition of the loop
addi x3, x0, 0 # x3 = 10
# Tests if x2 (j) >= x3 (10) and if so, jumps after the loop
loop:
bge x2, x3, after
# Inside the loop
lw x4, 0(x1) # x4 = i
addi x4, x4, 10 # x4 = x4 + 10 = i + 10
sw x4, 0(x1) # i = x4
addi x2, x2, 1 # j = j + 1
jal x0, loop # Jumps to loop
# After the loop
after:
# ...
Squaring a number
Question 7
# Loads the address of n in x1
lui x1, 0x1000
# Loads the value of n in x2
lw x2, 0(x1)
# Jumps to after_if if x2 (n) >= 0
bgt x2, x0, after_if
# n = -n
sub x2, x0, x2
after_if:
# s is stored in x3 and initialized to 0
addi x3, x0, 0
# k is stored in x4 and initialized to 1
addi x4, x0, 1
# i is stored in x5 and initialized to 0
addi x5, x0, 0
loop:
# Jumps to after_loop if x5 (i) >= x2 (n)
bgt x5, x2, after_loop
# s = s + k
add x3, x3, x4
# k = k + 2
addi x4, x4, 2
# i++
addi x5, x5, 1
jal x0, loop
after_loop:
# Store x3 (s) at the address x1 + 4 (0x10000004)
sw x3, 4(x1)