For the purpose of understanding what this function is doing, we'll walk through the code assuming a couple different values for toTest. This makes it a little clearer as to what is happening and naturally leads into some discussions about exactly how this code is being optimized. The first condition being if toTest is equal to '2'.
The first few instructions of checkNum are a little out of order, so we will ignore the first instruction for now. The second instruction is far more interesting anyways.
stmfd sp!, {r3, r4, r5, r6, r7, lr} is an instruction that we have seen before, but this time it is pushing far more registers than we normally do. Why only these registers? Why not all of them? The reason lies in how how the compiler treats registers when it is optimizing code.
In code that is optimized, there is a much greater focus on use of registers. Instead of simply using all of them for scratch space like unoptimized code, the compiler will often use some of them for variable storage as well. These values inside the registers must be maintained through any number of function calls.
Why are we only pushing these registers? Why not all of them, why any?
Answer 1
This push of the registers saves their values, freeing them for use as scratch space. Then, we pop them off on return, maintaining data integrity for the parent function.
Next, two move instructions copy toTest and primeSet[0] to another set of registers to use later, r5 and r7 r. Now we come to the line that cmp r0, #2 makes sense for. Here we are comparing the number '2' with toTest, and branch if the number is less than or the same as '2'. Because of our earlier assumption of toTest being '2', the code takes this branch to '.L32'.
At .L32 the only thing that is done is a mov r6, #2. This is the initialization of divisor for the loop on line 31 in the C code. Afterward, we branch to '.L28'.
Here, the code compares toTest (remember the move command mov r5, r0 at the beginning) to the value in r6, a value that currently is '2', but may change in later cases. If the value is '2', we drop down into some familiar looking code. This is the inlined setBit code, though with some aspects slightly rearranged. This means that at '.L28', we are at C code line 34, 'if (divisor == toTest)'.
But hold on, we haven't seen any sort of loop yet, so why are we already at the 'if' statement at line 34? It seemed like we just skipped the loop statement at line 31 after initializing 'divisor'.
And yes, in fact, we did. This weird branching about the compiler did was caused by loop unrolling. The compiler noticed that if toTest was any number 2 or below, it would immediately fail the loop's boolean checks, and therefore skip the entire loop. So instead of moving those numbers through two boolean checks, it simply skipped them by doing one.
So then why are we checking if toTest is equal to '2' on lines 134 and 135 of the ARM code?
Answer 2
setBit if it is.
Finally we return true, or '1', if r6 == r5, which is 'divisor == toTest' in the C code, otherwise return '0', or false in C. We will return '0' if the number is less than '2'.
Now we move back to the top of checkNum and try a different value, lets say toTest = '4'.
First, we fall through the branch on line 117, and on line 118, we see a new command.
tst performs a bitwise and between the two given operands and sets bits in the cpsr based on the results, just like a cmp would. In this case, we and r0, currently '4', and '1'. In the next line, we branch if the result is equal. In this case, 'equal' would mean the result of the and is all '0's.
Question 3
What is this result looking for in toTest? Think about what that single '1' is doing.
Answer 3
lsb is '1', which would indicate an odd number.
It jumps over the loop and setBit if statement if the toTest is even, because an even number fails the loop immediately. We also know, because it is not '2', that it fails the if statement to call setBit. This was discovered through loop unrolling, It is smart enough to recognize simple patterns like this one.
Now, after branching to '.L29' and moving '2' into r6, we branch to '.L31', or the return statement for the function. We know that r5 will never equal '2', so the 'mov' is just to make sure that the return expression returns false or '0'.
So now, we have any number 2 or below covered for, as well as any even number covered by the two checks and branches. The final branch is only executed if we have an odd number greater than two. Lets assume 'toTest' = '5'.
The first two branches are skipped, as '5' fails both condition checks. Before branching to '.L30', we load a '2' into r4 to use as divisor.
At '.L30', we start by incrementing r4, then compare r4 to r5, which contains the value for toTest.
Why do we increment divisor to 3 before checking to see if it matches toTest?
Answer 4
toTest being '2'.
Some may think that the optimizer should just make r4 equal '3' from the start, but this cause other instructions to shift around and, overall, would make the loop body a little to slow. This method, the optimizer recognized is faster.
Next are three move instructions that cleverly pull double duty, and are useful if the branch is taken or fallen through. If the branch is taken, the first two moves prepare for a modulo operation on line 123. Otherwise, the last move prepares the second comparison at '.L28'. In each case, the other move instructions are vestigial.
If the branch to '.L36' is taken, the modulo operation in the second part of the 'for' loop is performed and checked. If the result of the 'mod' operation is '0', then it jumps to '.L28', which performs the check for if (divisor == toTest). If not, the code falls back through to the first check of the 'for' loop. This is the main body of the 'for' loop in checkNum.
If the branch on line 132 is fallen through, we end up at the 'if' check for divisor and toTest again. If they are not equal, the code branches to the return statement. Otherwise, the inlined code for setBit runs, setting the specific bit in the pattern that corresponds to toTest, then moves onto the return statement.
This mostly convoluted code represents the entirety of the checkNum function, so lets move onto main.
This function starts out with mostly standard code that we've seen before. Pushing registers that are needed for scratch space as well as lr, then creating '11' spaces on the stack. This is the space for the primeSet array and one extra space that is unused. Next, we have four move instructions that prepare different variables for upcoming calculations. It will be clearer about what each represents later in the code.
The next ten lines of code are very similar, and seem copy, pasted and edited slightly. What is the corresponding C code here? Why would the compiler write code like this?
Answer 5
primeSet. In this case r3 is simply used as a scratch register to hold '0', which is then used to prepare all of the values of the array. It was done this way because a loop would have ended up taking far longer, though would have been less instructions.
Up next, after .L6, we have the start of some familiar looking code. This is the inlined checkNum function. Moving through much of the code, we will find it very similar to the other versions of checkNum and setBit. There are some instructions in different orders in the code for this inlining of them, but it does not warrant a full dive into them to discover the changes. Just be aware that there are changes between the two.
After '.L3', where the return statement was in the other version of checkMum, is where we begin to have different code. instead of looping back to the top, we increment some of our variables, in this case, r5 or toTest, then check to see if toTest is equal to '320'. If not, then we branch back to the top. If yes, then we fall down and print "Found %d primes:", and prepare for the print loop, starting at '.L8'.
The print loop itself is fairly straight forward, and is a lot of code we have seen before.
Starting at '.L8' and executing four instructions to line 83's ldr r8, [r3, #-40]. What is now loaded into r2?
Answer 6
r2 would contain the value at 'primeSet[1]';
The next three instructions check if the number in question is a prime. If yes, we move 'toTest' in to r1 and load the address of the string into r0, then call our 'printf' function.
We then increment 'toTest' just after the print statement and branch back to '.L8' or fall through if we have reached the end of the loop ('toTest' as reached '320'). If the number in question is not a prime, we branch to '.L7', where we also increment 'toTest and also check for end of loop.
At '.L24' we have another clever compiler trick. In the C code, 'print("\n")' is the last line that is executed before the return statement from main. Here we prepare this function call as normal, loading r0 with the value '10', or '\n' in ascii, in order to be printed. Next, we do something a little out of order. That is, we destroys the current stack frame, and return all values to their respective registers.
This doesn't really make too much sense, because we have not called our last print statement. By branching to putchar, aren't we overwriting our last link back to the function that called main?
Explain why the compiler can get away with calling 'putchar' without saving lr.
Answer 7
lr because we do not use a bl command that will load lr with a value. Instead, lr will contain the address of the instruction after main was branched to. So we use 'putchar's bx lr command to branch back to the function that called main.
The b putchar is the last thing that is executed for prg6.s.