A small tangent before continuing on with our discussion of Prg5opt.s. After maxOf3 finishes its job, it branches back to main. But it doesn't accomplish this with either a mov, a b, or any variation of the pop command. Instead it uses a command we've seen before, but have not discussed in depth, the bx command.
Question 1
Do a little research and figure out what bx means in the ARM architecture language. You don't need to figure out what it does, just find out the full name.
Answer 1
bx is Branch Exchange Instruction Set.
It's a weird name. But true to it, this instruction will branch to the value given in the register, and begin using either the ARM instruction set or the ###Thumb instruction set###, depending on the bit pattern contained in the instruction.
Most ARM processors can execute instructions from two different sets, a unique feature of ARM processors. first of these two is the basic ARM instruction set you've been working with, and the second being the Thumb instruction set. The Thumb instruction set is a fully fledged ISA containing the most commonly used commands in ARM, but shortened to only 16 bits per instruction.
ARM processors that support this feature contain a separate hardware module whose sole purpose is to interpret these instructions with no performance loss. In fact, the exact opposite happens, a processor running Thumb is faster than a processor running ARM because it takes less time to load the smaller 16 bit instructions.
For an example of the size of the instructions, translating add R0, R0, R1 to HEX in ARM would look like this.
E0800001
While in Thumb, the instruction would look like this.
1840
Instructions in Thumb are not as powerful as their ARM counterparts, and often contain no small amount of limitations placed on them. For example, ldr and str can no longer increment registers they use. add and sub can no longer perform bit shift operations along side their normal function. And The largest restriction of Thumb comes from reducing the bits used to identify registers to 3 bits only.
Question 2
What is the highest register that can be accessed in the Thumb ISA?
Answer 2
So the Thumb instruction set is not only far reduced, but is also far more limited than its larger counterpart.
Question 3
Based on what I just said, why does the Thumb architecture exist?
Answer 3
You might see Thumb instructions pop up sometime in code. These blocks of code are denoted by the .thumb directive at the head of a block of code.
Now back to main.
Much of main is quite similar than the unoptimized version, save the a few minor changes, though they are similar enough that they don't need an explanation. Much of the code up until line 38 is similar and easy to understand.
Then, on line 39 we have something familiar happen. We have another inlined function. But this time, it is maxOf3's turn. This code for maxOf3 is the same as the above code, save for a couple register changes to make sure that the function runs properly. Same as above, there are two inlined max functions, one on lines 39 to 40 and the other on lines 41 to 42.
Question 4
As a quick memory check, what are the outputs for the two max of three functions for this specific inlining of them?
Answer 4
There is a small register change from the original, and that is worth noting.
Question 5
Why did the compiler feel the need to change the registers from the original? Make sure to look over the next couple lines.
Answer 5
mov command, it adjusted the other registers to suit the needs of the later function call.
But this brings up a couple more questions about the compiler and its method of inlining functions. Why is maxOf3 still in the code but max is not, even though both functions are inlined? Both only need registers in order to work, both make no use of the stack, and both do not need the stack to return a value. For all intents and purposes, the compiler should have gotten rid of both functions and only used inlining to reduce size. There is a difference between the functions, though it is not made apparent from the ARM code. Instead, we need to look at the C code to really get the picture of the compilers seemingly sporadic inlining habits.
The answer is the 'static' declaration in the max function. It means that only the file that it was written in is able to call it. And because the compiler knows both of the places that it needs to be called, and knows that it cannot be called elsewhere, it can safely get rid of the ARM declaration of the code. maxOf3, on the other hand, is not static, and can possibly called in other places from other code.
The compiler will can only look at one C file at a time, meaning it does not know if what it is compiling is a single file, or a part of a much larger program. This means that the body of maxOf3 must still exist in the code, otherwise the compiler would have nothing to fall back to in the event of another file calling maxOf3.
In conclusion, the main function in this code is the only block that needs to run, because it contains all needed code through inlining. Now lets move on to the final, much smaller example of SumLoop.s.
For this code, we will do a small exercise.
Question 6
Look over the unoptimized code for sumLoop (sumLoop.s, beginning on line 27) and make one to two optimizations that you think that the compiler might make. Try to avoid simple "Compiler being stupid" errors in favor of more substantial changes.
Answer 6
r1, removing the need for an ldr instruction on line 47.
In truth, the compiler optimization is a far more intelligent beast than the compiler itself. Lets take a look at the optimized version of SumLoop, SumLoopOpt.s.
The first thing you will likely notice is the brevity of the code. This code contains about 80% fewer instructions, only 6 as compared to the unoptimized's 26 lines. The file itself is also less than half the size of the unoptimized version.
Question 7
What is the most startling aspect of this code, one that shows the true intelligence of the optimization algorithms?
Answer 7
This is one of the main reasons that the compiler is so difficult to beat. This is not just clever little optimization, this is very strong and very powerful code that has been honed over decades.