#ARMOptimized:bigEx:A#

Transcript A

Concepts

      1. setBit
2. Loop Unrolling

    

Overview

Overall, these next few lectures will be more unraveling of assembly code, but they will also illustrate a few concepts of programming that will be useful outside of simply understanding what the assembly code is doing.

setBit Function

This function is a tight 7 lines of code, and introduces a few new ARM talking points. First, remember when the setBit function is called, r0 contains prime , and r1 contains the address of primeSet[0]. These are useful to remember as the compiler does not deem it necessary to save these values on the stack, as instructions ldr and str are costly and the compiler avoids them whenever possible.

The first instruction is something we've seen before, it divides prime by 32 in order to get the correct index of primeSet where that number's bit is located. Next, we'll move '1' into ip, also known as r12. ip, or the Intra Procedure register, has a special meaning for function calls, but its use in that functionality is past what this course covers. Here, after its special use for when a function is called, it is available for use as a scratch register. This 1 will be used later in the code.

The next line contains three separate instructions all bundled into one. First, this instruction shifts the contents of r2 left by 2 bits, simulating a '*4' operation. Then, it adds that value to r1. It does this non destructively, preserving the initial value in r1. Finally, this instruction loads the value at that address into r3.

Up next is the and instruction that we've seen before, it simulates a % 32. orr is another compound instruction, but one that is easily unraveled. First, remember that three lines above, we moved 1 into ip, which we finally use on this instruction. We shift the '1' into the bit location that corresponds to prime in the bit pattern contained in primeSet[i], then or that with the original bit pattern, effectively inserting it into primeSet[i].

Finally, the str instruction that we already deciphered from earlier comes back and saves the modified bit pattern back into the address for primeSet[i].

Before we move onto the CheckNum function, it is important to go over an optimization algorithm that compilers often use, one that we touched upon in the previous lecture.

Loop Unrolling

For much of the checkNum function, the compiler uses a technique called Loop Unrolling. Loop unrolling is the compiler transforming a loop from doing single iterations in the loop body to doing multiple iterations. This allows the loop to perform multiple steps without performing costly branch statements. Coupled with other algorithms, the loop can also be reduced or simplified beyond this point.

For a concrete example, let's look at the program sumLoop from the previous lecture. The normal loop looks like this:

         while (toSum != 0) {
      total = total + toSum;
      toSum--;
   }

    

If we were to do two iterations in a single loop, as if we wanted to unroll this loop, it would look like this:

         while (toSum != 0) {
      total = total + toSum;
      toSum--;
      total = total + toSum;
      toSum--;
   }

    

This iteration adds two numbers to total, doing two steps of the loop in a single go. But the important step is when the compiler did 5 iterations in a single loop. This version of the loop now looks like this:

         while (toSum != 0) {
      total = total + toSum;
      toSum--;
      total = total + toSum;
      toSum--;
      total = total + toSum;
      toSum--;
      total = total + toSum;
      toSum--;
      total = total + toSum;
      toSum--;
   }

    

In this example, we have all of the iterations of this loop done in a single loop body. Now, the compiler substitutes known values for variables into the array. For example, because we set toSum to 5 and total to 0 just above the loop, and we don't change them at any point before the loop, the compiler is able to know the exact values of these variables. So an unrolled loop with the variables replaced looks like this:

         while (toSum != 0) {
      // decrement taken out for simplicity.
      total = 0 + 5;
      total = 5 + 4;
      total = 9 + 3;
      total = 12 + 2;
      total = 14 + 1;
      // total == 15;
   }

    

Now the compiler can reduce these lines even further by simplifying the mathematical equations, like this:

         while (toSum != 0) {
      total = 5;
      total = 9;
      total = 12;
      total = 14;
      total = 15;
      // total == 15;
   }

    

Now, with the help of loop unrolling, the compiler knows that no matter how many times this program is called, total always come out to 15. Thus, the optimized code reflects this, and simply prints out '15'.

But what might happen if there is unknown variable in a loop? take for example the following code:

      int toSum = 5, total;
   
scanf("%d", total);
   
while (toSum != 0) {
   total = total + toSum--;
}

    

In this code, we have an unknown variable, total, but it is still possible to perform a loop unrolling algorithm on this and come out with far more simplified code. Let's see what this loop looks like unrolled to its fullest extent as well as replace toSum with the values it would represent.

         while (toSum != 0) {
      total = total + 5;
      total = total + 4;
      total = total + 3;
      total = total + 2;
      total = total + 1;
   }

    

In order to simplify it, we can take all of the constant values and add them all together, simply because it does not matter what order we add them in. Doing this, we get the number '15'. And because total isn't changing past adding fifteen to it, we can simplify the code to this:

         
   int toSum = 5, total;
   
   scanf("%d", total);
   
   total = total + 15;

    

        
int toSum = 1, total = 0, offset;
scanf("%d", offset);
for (toSum <= 5) 
   total = total + offset + toSum++;

      

This is the simplified version of loop unrolling and it does come in far more complex forms, as we will see in the rest of this program.

In the next lecture, we will work on the checkNum function.