In this segment we'll examine the assembly for checkNum from the Primes.c program. We'll continue with the "guided tour" mode, with ILQs asking you to think through the code on your own as much as you can, and comment as you go.
The first 5 lines set up a stack frame. They're pretty standard by now.
stmfd sp!, {fp, lr}
add fp, sp, #4
sub sp, sp, #16
str r0, [fp, #-16]
str r1, [fp, #-20]
Question 1
How much space is reserved for local variables in this frame? What are two of the variables, and where are they stored? Is either at the top of the stack frame?
Answer 1
toTest and primeSet stored at offsets -16 and -20 from the bottom of the frame. The latter is at the top of the stack frame, in the lowest bytes of the 16 bytes reserved. (Remember that fp points to the bottom and lr is immediately above it, followed by the local space, so the TOS is 20 bytes above fp in the stack frame.)
Question 2
How about these two instructions? What do they do, what C variable is involved, and what part of the C program do these instructions implement?
mov r3, #2
str r3, [fp, #-8]
Answer 2
divisor to 2, in preparation for the for-loop. It'll be stored at offset -8, at the bottom of the locals area immediately above lr.
Question 3
OK, so now comment those first seven lines based on the discussion we've had. A reasonable answer is given for you to compare with.
Answer 3
112 stmfd sp!, {fp, lr} @ Store fp and lr at base of new stack frame
113 add fp, sp, #4 @ Point fp to new stack frame base, where old fp is stored
114 sub sp, sp, #16 @ Reserve 4 words (16 bytes) of space for locals
115 str r0, [fp, #-16] @ Store toTest just below TOS
116 str r1, [fp, #-20] @ Store primeSet at TOS
117 mov r3, #2 @ Store 2 into the location for..
118 str r3, [fp, #-8] @ .. divisor
So far, this is pretty routine, but there's something interesting going on at the next line. We've just done the initialization for the for-loop, and we'd expect code for the loop test divisor < toTest && toTest % divisor != 0 to appear next. But instead we have a b .L13 instruction which does an unconditional branch past these next three lines:
b .L13
.L15:
ldr r3, [fp, #-8]
add r3, r3, #1
str r3, [fp, #-8]
.L13:
Question 4
What do those skipped lines do? What C code do they implement?
Answer 4
divisor. They implement to the loop incrementer, not its test.
So we skip over the incrementing code, arriving at the block of code starting at L13
.L13:
ldr r2, [fp, #-8]
ldr r3, [fp, #-16]
cmp r2, r3
bhs .L14
ldr r3, [fp, #-8]
ldr r2, [fp, #-16]
mov r0, r2
mov r1, r3
bl __aeabi_uidivmod
mov r3, r1
cmp r3, #0
bne .L15
This is actually the loop test, implementing divisor < toTest && toTest % divisor != 0. (We'll decipher it in a moment.) If this test is true, then the bne .L15 instruction at its end loops back to the incrementing code, which then leads into the loop test again. The loop incrementor is thus done after the test by virtue of that loopback. We've seen this sort of thing before, and why the compiler did this is something we'll examine in a bit, but first let's decipher the loop test.
Question 5
What does this first part of the loop test do? Two points to remember:
bhs is a "branch if first operand is "higher or same"
.L13:
ldr r2, [fp, #-8]
ldr r3, [fp, #-16]
cmp r2, r3
bhs .L14
Answer 5
divisor (at offset -8) to test toTest (at offset -16), and jumps out of the loop if the test subtraction shows that divisor >= toTest. It's doing the first part of the loop test.
Question 6
This means that the second part of the loop test might be entirely ignored if we make the jump to L14. Is this OK? Why?
Answer 6
So, this leaves us with the second half of the loop test to be executed only if the first half was true.
ldr r3, [fp, #-8]
ldr r2, [fp, #-16]
mov r0, r2
mov r1, r3
bl __aeabi_uidivmod
mov r3, r1
cmp r3, #0
bne .L15
To understand this code, you have to know that _aeabi_uidivmod is a library function supplied by the C compiler to compute both the quotient and modulo of a pair of integers, since the ARM ISA lacks a integer division and modulo operations. It's a lot slower than built-in assembly instructions would be, but it gets the (rarely needed) job done. _aeabi_uidivmod expects its arguments in r0 and r1, and it returns the quotient (r0/r1) in r0 and the modulo or remainder (r0 % r1) in r1.
Question 7
With that information, explain how these lines implement the second part of the loop test. Could you shorten them by three instructions?
Answer 7
divisor and toTest to _aeabi_uidivmod in a roundabout way, first loading them into r3 and r2 and then moving into r0 and r1, and calling the function. We could save two instructions by writing ldr r1, [fp, #-8] ldr r0, [fp, #-16] and dropping lines 131 and 132. The instructions after the call move the modulo divisor % toTest into r3, and compare it with 0, jumping back to repeat the loop if the modulo is not 0. That comparison could simply have been cmp r1, #0, saving another instruction. The net result is that these instructions test toTest % divisor != 0 and repeat the loop if it's true, otherwise they fall through to L14 and exit the loop.
Question 8
Based on all the discussion so far, comment lines 119-136. You don't necessarily need to comment every line if a block of lines does one simple thing.
Answer 8
119 b .L13 @ Skip increment on 1st loop 120 .L15: 121 ldr r3, [fp, #-8] @ Increment divisor 122 add r3, r3, #1 123 str r3, [fp, #-8] 124 .L13: 125 ldr r2, [fp, #-8] @ r2 = divisor 126 ldr r3, [fp, #-16] @ r3 = toTest 127 cmp r2, r3 @ Compare divisor and toTest 128 bhs .L14 @ Exit loop if divisor >= toTest 129 ldr r3, [fp, #-8] @ r3 = divisor 130 ldr r2, [fp, #-16] @ r2 = toTest 131 mov r0, r2 @ Pass toTest as param 1 132 mov r1, r3 @ Pass divisor as param 2 133 bl __aeabi_uidivmod @ Do toTest % divisor 134 mov r3, r1 @ r3 gets result 135 cmp r3, #0 @ If it's nonzero.. 136 bne .L15 @ .. then back to loop increment
Now that we understand how the loop test works, let's look more closely at why the compiler organized the loop code so oddly, putting the incrementer at the top.
It did this to reduce the number of branches. If the loop test were at the top, then a branch decision would be made after the loop test to decide whether to repeat the loop or go on with the rest of the program. And a branch would be needed at the bottom of the loop to return to the top. With the iteration code at the top, each successive loop iteration needs only the one branch at the bottom.
Why reduce the number of branches? Because the ARM processor is pipelined.
We think of an assembly instruction as a single action, but performing an instruction actually takes several steps. The CPU must first load the instruction from memory, then for a register based operation it must fetch operands from the registers, possibly perform a shift and/or an arithmetic operation, and then save the result back to a register. For a load/store it must compute a memory offset, and then read/write a register value from/to that location. Also, branches and other instructions can be qualified with a "ge" "lt" or other condition, as we've seen. So any instruction must first go through a test to see if it should be run at all.
Each step requires different parts of the CPU hardware, so the CPU can work on several instructions at once: e.g. loading one from memory, testing condition for a second, fetching registers for a third, performing arithmetic for a fourth, and saving results for a fourth, almost like a physical assembly line might build cars or computers. Such an approach is called instruction pipelining, and all RISC processors do it. Indeed, the main reason for a "reduced" instruction set is that a simple instruction set is easier to pipeline.
The five stages I just described are merely representative. The particular number of stages in the pipeline varies by the version of the ARM processor. Simpler versions use just three stages; later ones use even more than the five stages I described. Here's a brief look at a diagram from the ARM info center showing a more recent ARM processor's pipeline. You don't need to understand the details; just appreciate that the CPU is running a sophisicated "assembly line" with multiple instructions going at a time, each a a different stage.
Pipelining speeds the CPU up by a factor of 3 or more, but it has one critical limitation. When the program reaches a conditional branch instruction, the CPU can't know whether the branch will happen or not, and might not even know the target address, until the branch instruction has made it part way through the pipeline. But, in the meantime, the instructions after the branch continue to feed into the pipeline and start executing. If the branch occurs, the instructions after it should not have been executed. Now, those mis-loaded instructions don't save their results until the reach the end of the pipeline, so this mistake can be corrected by simply dropping the mis-loaded instructions from the pipeline and instead restarting the pipeline at the branched-to location. But this wastes time. Thus, branch instructions are inherently inefficient because they can disrupt the smooth flow of the CPU pipeline, and compilers for RISC processors try to minimize them.
Let's move on with the rest of checkNum.
The instructions after the for-loop implement the if-statement.
if (divisor == toTest)
setBit(toTest, primeSet);
Question 9
Identify the instructions that implement those two C lines, and explain how they work. Could they be made more efficient?
Answer 9
divisor and toTest, compare them, and jump around the last three instructions if divisor != toTest. So the last three instructions run only if divisor == toTest. Those last three instructions load toTest and primeSet into r0 and r1 as parameters per the calling convention, and call setBit.
If we'd loaded toTest directly into r0 instead of r3 before the cmp, that would let us drop line 142.
.L14
ldr r2, [fp, #-8]
ldr r3, [fp, #-16]
cmp r2, r3
bne .L16
ldr r0, [fp, #-16]
ldr r1, [fp, #-20]
bl setBit
.L16:
The if-statement instructions are straightforward, but those for performing the return divisor == toTest statement need more careful examination.
ldr r2, [fp, #-8]
ldr r3, [fp, #-16]
cmp r2, r3
moveq r3, #1
movne r3, #0
uxtb r3, r3
mov r0, r3
The ultimate goal of these instructions is to compute the true/false (1 or 0) value of divisor == toTest and put that value into r0, which per the calling convention is the expected location of the return value from checkNum.
The first three instructions clearly compare divisor and toTest. But, instead of the usual branch after the cmp instruction, we have a moveq and a movne instruction. We've seen "ne" and "eq" qualifiers on branch instructions, and recall from earlier lecture that any instruction can be qualified this way, and will execute only if the condition codes from a prior cmp or test match its qualification. So, if divisor and toTest are equal (the result of the cmp sets the Z flag) then the moveq instruction runs, otherwise the movne runs. To be exact, the CPU loads both instructions from memory, but the non-matching instruction is not run.
The net result is that r3 gets 1 or 0 depending on the cmp outcome.
Question 10
Rewrite the code to use a conditional branch and simple mov instructions. Is this better?
Answer 10
cmp r2, r3
bne LA
mov r3, #1
b LB
LA:
mov r3, #0
LB:
Clearly not a better solution, since it requires two instructions in either case, and one of them will be a pipeline-disrupting branch.
So, perhaps surprisingly, it can be much more efficient in small if-else cases to run both branches, but qualify the instructions so that one of the branches is ignored. This is especially true for pipelined RISC CPUs, for which branches are highly inefficient.
The uxtb r3, r3 instruction is, unfortunately, just compiler dumbness. This instruction sign-extends the MSB of lowest byte of r3 up through the upper three bytes. Since r3 has either 0 or 1, both nonnegative values, such sign-extension is useless. While we're at it, you may have noticed that 4 of the 16 reserved bytes of local space on the stack frame are never used. (There's no reference to [fp, #-12]) More compiler dumbness. However, we're almost done with this module, and the module on optimized ARM code will show just how smart compilers can be, if they're asked to optimize code.
Question 11
The last three instructions of checkNum are here. Briefly explain what they do.
mov r0, r3
sub sp, fp, #4
ldmfd sp!, {fp, pc}
Answer 11
sub sets sp back to the location of lr, just above where we stored fp. It pops the local storage area off the RTS. The ldmfd loads lr and fp from the stack back into registers, but it puts the lr value into pc, which effectively does a jump to the lr location.
Question 12
Based on all the discussion so far, comment lines 138-154. As before, you don't necessarily need to comment every line if a block of lines does one simple thing. And this is the last in-lecture commenting exercise we'll do. However, you should do this type of commenting on your own when deciphering assembly code in future segments.
Answer 12
138 ldr r2, [fp, #-8] @ r2 = divisor
139 ldr r3, [fp, #-16] @ r3 = toTest
140 cmp r2, r3 @ if divisor != toTest..
141 bne .L16 @ .. jump around setBit call
142 ldr r0, [fp, #-16] @ param 1 is toTest
143 ldr r1, [fp, #-20] @ param 2 is primeSet
144 bl setBit @ call setBit
145 .L16:
146 ldr r2, [fp, #-8] @ r2 = divisor
147 ldr r3, [fp, #-16] @ r3 = toTest
148 cmp r2, r3 @ check to see if equal
149 moveq r3, #1 @ if equal, return value will be 1
150 movne r3, #0 @ if not equal, return value will be 0
151 uxtb r3, r3 @ do needless sign extension
152 mov r0, r3 @ put return value where it should have been
153 sub sp, fp, #4 @ remove local storage
154 ldmfd sp!, {fp, pc} @ pop off fp, and lr, with lr going straight into pc
In the next segment we'll examine the main function for Primes.c.