What does "code motion" mean for "loop-invariant code motion"?

Question

In compilers, the phrase "loop-invariant code motion" describes expressions or statements of code in a loop that don't change from iteration to iteration and hence can be moved outside of the loop to be computed once.

I understand the "loop-invariant" piece of the phrase, but what does the "code motion" mean?

Answer 1

The "code motion" just means that the code is moved out of the loop as it won't have any difference if it is performed inside the loop repeatedly or outside the loop once. The compiler is taking the code that doesn't need to be in the loop and moving it outside of it for optimization purposes.

Here an example:

for ( int x=0; x < string.length(); x++) {
    //other code here
}

If the compiler knows that nothing in the loop changes the length of the string, it can just hard-code the length of the string into the program instead of inserting an actual call to the method length() on the appropriate string, because the method call will always return the same result and just waste memory and processor time. The code for the method call is moved before the loop instead of remaining inside it. The article calls this 'code motion', although I'd just call it plain old optimization, as most optimization involves moving code. :D

Answer 2

Seems as though it means from the Wikipedia article that the loop-invariant code is actually moved outside the loop as an optimization step.

Answer 3

The term "code motion" can be used for any situation, where some code is moved somewhere else, and the semantic of the program is unchanged. For sure, the compiler expects some kind of benefit, such as register pressure reduction, code size reduction, less computation, and so on. It is a very general optimization, easy to describe, but very hard to be implemented "well". The case of loop invariant code motion is a trivial example, where a lot of computations are just removed, but for other situations, it is usually much harder to say what is the best approach for a certain input. The difficulty is at both what are all the legal code motions, and which will be best, sub-optimal, or at least beneficial.