Techniques Used in Loop Optimization: Analysis and Loop Invariant Code Motion

I sometimes find it very difficult to learn about new programming techniques because there are often no explanations of what’s actually going on behind the scenes. I remember when I started my first Arduino project I had to send UDP (user datagram protocol) packets from my Arduino to an Internet of Things device. There were lots of mid level tutorials for sending UDP packets, but none that told me which ports I had to use for sending and receiving or how to determine which IP address to send to. In the end, it turned out to be quite simple, but it me a long time to figure out how things worked with no explanation. Compiler loop optimizations can also be shrouded in mystery for the uninitiated. I’m sure you know that compilers analyze your code, but what exactly are they looking for when they do it? They’re looking to implement optimizations like loop invariant code motion, or hoisting, a fairly straightforward way to increase the performance of your program. However, there’s always a tradeoff involved in compiler optimizations, so you should know when and where hoisting will actually benefit you.

Your compiler studies your code so you don’t have to.

Interprocedural Analysis

Have you ever seen someone try to fix something without knowing how it works? They usually end up doing more damage than good. Interprocedural analysis (IPA) helps ensure that your compiler applies the right optimizations at the right places in your program. Once your compiler studies your code as a whole, it can then apply a variety of transformations to make it more efficient.

In the distant past, program analysis and optimization were sometimes reviled. Now, though, they are much more highly regarded. During IPA your work is scrutinized as a whole, instead of in individual pieces. This allows your compiler to divide the overall intention of your code, rather than the purposes of specific parts. It also lets compilers do things like assign variables to registers or RAM (random access memory), but that’s a blog for another day. One of the more important benefits that come from IPA is loop transformation.

Transformation comes in a variety of flavors namely: loop unrolling, loop inlining which is similar to function inlining, and loop invariant code motion. These three optimizations can help you increase the speed of your code at the cost of program size. Performance can be critical when working with advanced driver assistance system (ADAS) enabled vehicles, as features must operate on time in order to avoid collisions.

Loop Invariant Code Motion

Enough about analysis, let’s get down to the basics, what is code hoisting? Loop invariant code motion is an optimization where operations inside loops are moved outside loops. This will give your code a boost, but will also increase its size.

Code hoisting is fairly simple. Sometimes you’ll write a loop with operations inside of it that don’t need to be there. These kinds of operations are ones that aren’t affected by loop iteration. When these operations are inside the loop they’re being calculated with each repetition, even though their values don’t change. This may not seem like much, but if your loop is, say, parsing data and running continuously, it can add up. When you move these actions outside of the loop, they are only performed once and speed up your process.

The common tradeoff between size and speed rears its ugly head again with this optimization. Every invariant piece of code that is hoisted out of the loop adds another line to your program. On a small scale this may not matter, but in a large program, it can be significant.

Loop invariant code motion hoists pieces of your code right out of their loops.

When to Hoist Code

It seems like you would always want to use this optimization, but occasionally it can slow down your program. This can happen when the hoisted code forces your board to start moving things into memory.

Remember when I said analysis can show your compiler which variables should be put into registers or memory? You want to put as many values into registers as possible because they can be called without having to read from or write to storage. Well, sometimes hoisted code can create variables. If there’s a lot of invariant code being moved out of loops, it can generate an excessive number of variables that will overflow the registers. Then your program has to start writing things into memory, which takes time. So, if you move out too many operations, the time you saved may be spent moving things in and out of storage. This is why compiler analysis is key for loop invariant code motion, so it knows which parts and how much of your code should be optimized.

This about wraps it up for loop optimizations. After going through IPA your compiler should know which loops it can unroll and inline, and which pieces it can hoist out. Loop invariant code motion can save you some time, but will always cost you space. It may end up slowing down your code as well if it generates too many variables and causes register spilling.

Hopefully this article helped you better understand one of the more simple loop optimizations. Now you’re ready to move on to writing programs for ADAS cars. If you’re looking for a compiler that can perform optimizations like this one, check out TASKING. Their compilers are specifically designed to optimize code for cars. They also have other tools like standalone debuggers that can help you optimize your development time.

Have more questions about compiler optimizations? Call an expert at TASKING.