In this segment we'll examine the assembly for setBit from the Primes.c program. In this and the following segments we'll move to a "guided tour" mode, asking you to think through the code on your own as much as you can. To this end there will be many ILQs asking you to analyze and comment segments of the assembly listing Primes.s. Please get a copy of this, and comment it as you view/read the lecture.
The assembly for setBit is at the bottom of Primes.s. The first five instructions set up a stack frame. But, there are some differences from earlier examples.
setBit:
str fp, [sp, #-4]!
add fp, sp, #0
sub sp, sp, #12
str r0, [fp, #-8]
str r1, [fp, #-12]
Question 1
What is not being saved in this stack frame that was saved in all earlier examples? Extra credit if you can guess why it isn't being saved this time. (A hint: setBit doesn't call any other functions.)
Answer 1
setBit doesn't save the lr register. We don't need to because setBit makes no other function calls to overwrite lr, so lr won't change during the setBit call.
So setBit stores just the old fp, and then moves fp to point to the bottom of the new frame.
Question 2
Can you rewrite add fp, sp, #0 more simply?
Answer 2
In earlier stack frame examples this instruction was add fp, sp, #4 but the lack of lr storage makes it add fp, sp, #0 here, which should really be a mov instruction. Compilers are sometimes just dumb.
Question 3
How many words are reserved for local variables and parameters? Where are parameters prime and primeSet stored relative to the TOS? Are all the local words used?
Answer 3
prime at one word below TOS, and primeSet at TOS. Not all three words are used as there is no reference to [fp, #-4] in the setBit code. Again, sometimes compilers are just dumb.
Question 4
OK, so now comment those first five lines based on the discussion we've had. A reasonable answer will be given for you to compare with.
Answer 4
setBit:
str fp, [sp, #-4]! @ Push the old fp onto the stack to start a frame
add fp, sp, #0 @ Point fp to the base of the new stack frame
sub sp, sp, #12 @ Reserve 3 words of local/parameter space
str r0, [fp, #-8] @ Write 'prime' into the middle word
str r1, [fp, #-12] @ Write 'primeSet' into the top word
The next 5 lines compute the location of the desired primeSet element. And they introduce shift operations in ARM assembly. Before examining them, think about the relationship between primeSet, which is a pointer (contains the address of) the first int in the array, and the address of the desired element. What is the difference between those two? For instance, if prime is 87, then the desired bit is in index 2, and that element is 8 bytes into the array.
Question 5
How many bytes are between the start of the array and the start of the desired element at index prime/bitsPerInt. Concretely, how many bytes if prime is 31, 32, 127, 128, 1020, 4088? Do the computation for each of those values until you come up with a consistent rule, e.g. "divide by this and multiply by that" to compute the byte offset for the right array element within primeSet. If your rule includes a division, what should be done with any remainder? Drop it? Round to the nearest int? Don't forget that each element of the array occupies four bytes.
Answer 5
This sort of computation is what a compiler does any time you use an array element: it figures out the index, and multiplies by the size of the array elements to get a byte offset from the start of the array.
Now let's look at those next five lines of code.
ldr r3, [fp, #-8]
mov r3, r3, lsr #5
mov r3, r3, asl #2
ldr r2, [fp, #-12]
add r3, r2, r3
The second and third lines in that group introduce something new. Many ARM instructions, including mov, add and sub (though not ldr and str) let you add a shift specification to the last operand. This takes the form of a three-letter shift type, and a shift amount. lsr #5 for instance specifies a logical shift to the right by 5 bits. (Recall the difference between logical and arithmetic right shift -- a logical shift won't sign-extend.). asl #2 specifies an arithmetic shift to the left by 2 bits, though arithmetic vs logical is irrelevant in left shifting, so an lsl #2 would do the same thing. The shift amount can be a constant, as in these two instructions, or it can come from a register. For instance, if r1 contains 4, then lsr r1 shifts right by 4 bits.
Shift specifications will not shift by more than 31 bits. The CPU circuitry that performs shifts is designed only for this maximum shift amount, and trying to shift e.g. by 32 bits results either in an assembler error if you use a constant, or in surprise behavior if you use a register. (In the latter case you'll get a shift by zero instead of by 32.) This issue arises sometimes when coding shift operations in C. Shifting by 32 or more is a bit useless anyway, since the result will always be either zero, or possibly -1 in the case of arithmetic right shifting.
Question 6
Think about those two bit-shifts, and what we learned about the mathematics of bit-shifting in earlier lectures. Based on that, explain what the first three lines of the block of code do. What value is loaded into r3 initially on line 166? What value will be in r3 after line 168?
Answer 6
prime into r3. Line 167 divides by 32 dropping any fraction, and line 168 multiplies by 4. They compute the byte offset of the primeSet element containing the desired bit, and that's what's left in r3
Note, by the way, that just left-shifting by 3 wouldn't accomplish the same thing since we wouldn't get the truncation of the fraction when dividing by 32.
Question 7
What do the final two instructions (the ldr and add) accomplish? What is the value in r3 after line 170?
Answer 7
primeSet, the address of the start of the array, and add it to the byte offset in r3, so r3 now has the direct address (not just an offset) of primeSet[prime/bitsPerInt].
And, the next five lines do exactly the same thing, but for r2 instead of r3! So r2 and r3 will both contain the address of the relevant array element. That sort of redundancy will be corrected when we look at the optimized version of this code in a later module.
ldr r2, [fp, #-8]
mov r2, r2, lsr #5
mov r2, r2, asl #2
ldr r1, [fp, #-12]
add r2, r1, r2
Question 8
Now comment lines 166-170 (and by default lines 171-175) based on the discussion we've had. A reasonable answer will be given for you to compare with
Answer 8
ldr r3, [fp, #-8] @ Load prime into r3
mov r3, r3, lsr #5 @ Divide prime by 32, rounding down, to get desired index
mov r3, r3, asl #2 @ Multiply by 4 to get byte offset of that index
ldr r2, [fp, #-12] @ Load base address of primeSet array
add r3, r2, r3 @ Add to byte offset to get location of desired index
Question 9
Line 176 is deceptively simple: ldr r2, [r2]. Think carefully about it, and describe what it does, given r2's current contents. Add a comment describing that.
Answer 9
The next 5 instructions deal with setting the correct bit in the word just loaded
ldr r1, [fp, #-8]
and r1, r1, #31
mov r0, #1
mov r1, r0, asl r1
orr r2, r2, r1
In other words, they compute this C expression, which we discussed in the prior segment.
primeSet[prime/bitsPerInt] | (1 << prime % bitsPerInt)
The instruction and r1, r1, #31 performs a bitwise-and operation on the contents of r1, and the constant value 31, putting the result back into r1. Recall prior discussion on what bitwise-and does.
Here's an example of the instruction at work, assuming the contents of r1 is currently 42:
00000000000000000000000000101010 r1 00000000000000000000000000011111 31 ------------------------------------ 00000000000000000000000000001010 r1 bitwise-anded with 31
The bit-pattern for 31 has 1's in the bottom 5 bits, so those are the only bits that could be 1 after the bitwise-and operation is done. In effect, the operation keeps whatever the bottom 5 bits of r1 were, and zeros out all the rest.
So, what is the mathematical significance of that? There are two good ways to look at it. First, the eliminated bits are all divisible by 32 (32, 64, 128, etc) and the preserved bits are all nondivisible by 32. So, this operation preserves the non-divisible-by-32 part of r1's value, or in other words, it computes r1 % 32.
A second way to look at it is that shifting r1 right by 5 bits divides by 32, as already discussed, and the five bits being preserved by the bitwise-and are exactly the remainder that is lost by that right shift. So, again r1 & 31 is the same as r1 % 32.
In general, we can accomplish a modulo by 2^x via a bitwise-and with 2^x-1. And bitwise-and is much faster than performing a division. The compiler knows this, and uses bitwise-and when possible. So, sometimes compilers are smart after all.
Question 10
Now that we understand what the and instruction does, decipher the other 4 instructions and comment all 5.
Answer 10
ldr r1, [fp, #-8] @ Load prime into r3
and r1, r1, #31 @ r1 = prime % 32
mov r0, #1 @ r0 = 1
mov r1, r0, asl r1 @ r1 = 1 << (prime % 32)
orr r2, r2, r1 @ r2 = primeSet[prime/bitsPerInt] | (1 << prime % 32)
Now r2 has the desired bit pattern, with an extra 1-bit or'ed in.
Question 11
Comment line 182, recalling what's in r3 from earlier instructions. str r2, [r3]
Answer 11
We're left with just the final three lines
sub sp, fp, #0
ldr fp, [sp], #4
bx lr
Question 12
You should be able to correctly comment these from earlier examples. Please do so.
Answer 12
sub sp, fp, #0 @ Remove local space, returning sp to fp location
ldr fp, [sp], #4 @ Load old fp, and move sp back to top of prior frame
bx lr @ Return to caller via lr which hasn't changed during this call.
That concludes the commenting work for setBit. In the next segment we'll do checkNum.