In this segment we'll look at the code for the second and third loops in main.
So, starting with the second loop
for (toTest = 2; toTest < numsToTest; toTest++)
if (checkNum(toTest, primeSet))
totalPrimes++;
Question 1
Identify the instructions that implement this loop. And tell which are the initializer, incrementer, and loop test. Also, at what offset is toTest?
Answer 1
.L4 as the test (comparing toTest at offset -12 to numsToTest at offset -2, and branching back if the result is less-than) to .L6, where the loop body is, and the three lines between .L5 and .L4 are the incrementer.
toTest is the last missing piece of the stack frame, which I'll fill in here in our diagram.
The initializer, test, and incrementer are pretty straightforward by now. But we need to look more closely at the body of the second loop.
if (checkNum(toTest, primeSet))
totalPrimes++;
ldr r2, [fp, #-12]
sub r3, fp, #60
mov r0, r2
mov r1, r3
bl checkNum
mov r3, r0
cmp r3, #0
beq .L5
ldr r3, [fp, #-8]
add r3, r3, #1
str r3, [fp, #-8]
.L5:
The setup for the call of checkNum sets up parameters in r0 and r1, per usual. The r0 parameter is a simple copy from toTest. But the r1 parameter is more complex. Recall that passing an array in C is really passing the address of the array's first element -- a pointer or address value. The sub r3, fp, #60 computation computes that address, to be passed via r1.
Question 2
Reduce those first four lines to just a single ldr and a single mov.
Answer 2
ldr r0, [fp, #-12] mov r1, sp
Question 3
The lines after bl checkNum implement the if-statement based on the result of the checkNum call, which is returned in r0. Explain how they work.
Answer 3
beq .L5 jumps around the next three lines. Otherwise if the result is nonzero (true) those three lines run, and increment totalPrimes.
So, let's move on to the final loop, including the printf just before it.
The next three instructions implement printf("Found %d primes:", totalPrimes), and they are a good reminder of the ldr/str concepts from an earlier topic.
ldr r0, .L10
ldr r1, [fp, #-8]
bl printf
Question 4
The ldr for r1 is obvious; it's just passing totalPrimes as the second parameter. But ldr r0, .L10 is more complex. The printf's first parameter is the string "Found %d primes:", but in C that means we pass the address of the start of the string, as a const char *, a pointer to a non-modifiable char. printf uses that pointer/address to find the rest of the string.
Answer three questions:
ldr r0, .L10 instruction accomplish loading that pointer?
ldr r0, .L10 from a pseudoinstruction into the equivalent real instruction.Review prior lectures on ldr/str and pseudoinstructions if needed.
Answer 4
The third loop is the most complex, but it builds on prior concepts.
for (toTest = 0; toTest < numsToTest; toTest++)
if (primeSet[toTest/bitsPerInt] >> (toTest % bitsPerInt) & 0x1)
printf(" %d", toTest);
Question 5
By now, you should be able to pick out the initializer, incrementer and test pretty easily. So, identify just the instructions that implement the loop body. And, of those instructions, which implement the if-test, and which the if-body?
Answer 5
So, let's start with the if-statement test:
ldr r3, [fp, #-12] mov r3, r3, lsr #5 mov r3, r3, asl #2 sub r2, fp, #4 add r3, r2, r3 ldr r2, [r3, #-56] ldr r3, [fp, #-12] and r3, r3, #31 mov r3, r2, lsr r3 and r3, r3, #1 cmp r3, #0 beq .L8
Much of this is familiar. We saw instructions like it when deciphering setBit (lsr, asl, and), and earlier on in the main itself (offset by -56).
Question 6
Review those discussions if needed, and then comment those instructions, explaining how they implement the test expression. Do this with reference to the C code, without using constants like 12 or 56.
Answer 6
ldr r3, [fp, #-12] @ r3 = toTest mov r3, r3, lsr #5 @ r3 = toTest / bitsPerInt mov r3, r3, asl #2 @ r3 = (toTest/bitsPerInt) * size of an int sub r2, fp, #4 @ r2 points to bottom of locals add r3, r2, r3 @ add array offset to r2 ldr r2, [r3, #-56] @ r2 = primeSet[toTest/bitsPerInt] ldr r3, [fp, #-12] @ r3 = toTest (.again) and r3, r3, #31 @ r3 = toTest % bitsPerInt mov r3, r2, lsr r3 @ r3 = primeSet[toTest/bitsPerInt] >> toTest % bitsPerInt and r3, r3, #1 @ r3 = primeSet[toTest/bitsPerInt] >> toTest % bitsPerInt & 01 cmp r3, #0 @ check if resultant bit is 0 beq .L8 @ branch around the if-body if so
The if-statement body is simpler:
ldr r0, .L10+4
ldr r1, [fp, #-12]
bl printf
But the use of .L10+4 is something new. The label argument in an ldr/str pseudoinstruction may include offset computations, as long as the intended location is still clear. The ldr still translates to a pc-relative load, in this case from the word after .L10, which contains the address .LC1, the location of the "%d" string.
And, finally, lets look at the final instructions of main, shown here in C and assembly form:
printf("\n");
return 0;
mov r0, #10
bl putchar
mov r0, #0
sub sp, fp, #4
ldmfd sp!, {fp, pc}
In the first two instructions the compiler is definitely being clever. Using printf to print a single character like '\n' is inefficient. The putchar function takes a single ASCII character as its only parameter and prints it. The compiler passes 10 (the ASCII code for '\n' to putchar, via r0, and drops the printf entirely. This is an example of the kind of cleverness compilers can exhibit when optimizing, as we'll see in a later topic.
The last three instructions return a 0 via r0, tear down the stack frame, and return to the "caller".
Does main have a caller? Yes, the C compiler provides a bit of assembly that calls main and which has a _start label marking it as the real starting point. This assembly is the real "main program", but you never see it directly.
Question 7
That assembly wrapper code clearly must have a bl main instruction. What two instructions are likely to follow bl main in that wrapper code? You can make a reasonable guess based on the fact that the return value of main is supposed to be the exit code of the entire program.
Answer 7
bl main. Adding the mov and swi instructions ends the program with that exit code.
That wrapper code is a good example of why assembly is essential. There is no C statement that can generate a SWI call. The wrapper code must be written directly in assembly.
Primes.s is a reasonably sophisticated program, and if you can decipher and follow it, you should be able to do so for most compiler-generated code, if it's not optimized. In a later topic, we'll look at compiler optimizations.