Code motion

In computer science, code motion, also known as code hoisting, code sinking, loop-invariant code motion, or code factoring, is the ptocess of moving code within a program for performance or size benefits, and is a common optimization performed in most optimizing compilers.

Code Sinking

Code Sinking is a technique to reduce the latency of a single loop execution, usually by moving code into execution paths where the result is actually used. If an operation is executed before a branch, and only one of the branch paths actually use the result of that operation, then code sinking entails moving that operation into the branch where it will be used.

Code sinking is a form of dead code elimination in the sense that it removes code when it’s results are discarded or unused, but in contrast to dead code elimination, it can remove pointless instructions even if there is a possible use of that instruction’s results in an execution code path.

Code Factoring

Code Factoring is a size-optimization technique which merges common dependencies in branches.

A diagram which demonstrates optimizing for size using code factoring, assuming all operations are not dependent on other operations executing before it.

Loop-invariant Code Motion

Main article: Loop-invariant code motion

A diagram depicting loop-invariant code motion over an execution graph. This assumes that D is invariant between loop executions.

Loop-invariant code motion is the process of moving code which is invariant to the execution of the loop, while inside of the loop, to a position outside of the loop.

Code Hoisting

Code hoisting brings certain operations 'upwards' in executing code, for various reasons. Eg, some compilers use code hoisting to alleviate dependencies in tightly-knit assembly code

Implementations

LLVM

LLVM has a sinking pass in it's single scalar assignment form. LLVM 15.0 will not sink an operation if any of it's code paths include a store instruction, or if it may throw an error. Additionally, LLVM will not sink an instruction into a loop.

GCC

The GNU Compiler Collection implements code motion under the name "code factoring", with the purpose of reducing the size of a compiled program. GCC will move any code upwards or downwards if it "[does not] invalidate any existing dependences nor introduce new ones".

LuaJIT

LuaJIT uses code sinking under the name "Allocation sinking", to reduce the amount of time compiled code spends allocating and collecting temporary objects within a loop. Allocation sinking moves allocations to execution paths where the allocated object may escape the executing code, and will thus require heap allocation. All removed allocations are filled in with load-to-store forwarding.

See also

• Loop-invariant code motion