Code motion
 | This article, Code motion, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.
Reviewer tools: Inform author |
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. It can be difficult to differentiate between different types of code motion, due to the inconsistent meaning of the terms surrounding it.
Uses
Removing unused/useless operations
Code Sinking is a term for a technique which reduces wasted instructions by moving instructions to branches in which they are used:[1] If an operation is executed before a branch, and only one of the branch paths use the result of that operation, then code sinking entails moving that operation into the branch where it will be used.
This technique 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.
Reducing the size of the program
Code Factoring is a term for a size-optimization technique which merges common dependencies in branches into the branch above it.[2] Just like factorizing integers decomposes a number into its smallest possible forms (as factors), code factorization transforms the code into the smallest possible form, by merging common "factors" until no duplicates remain.
Reducing dependency stalls
Global code motion, local code motion, code scheduling, and code hoisting/sinking are all terms for a technique where instructions are spaced out (or "scheduled") to reduce the impact of dependency stalls in generated assembly code.[3]
Loop-invariant Code Motion
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.
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.[4] 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.[5] GCC will move any code upwards or downwards if it "[does not] invalidate any existing dependences nor introduce new ones".[6]
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.[7] 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 over their fields.[8]
See also
References
- ^ Craft, Michael; Offut, Jefferson (1994). "Using compiler optimization techniques to detect equivalent mutants". Software: Testing, Verification, and Reliability. 4 (3): 131–154. Retrieved 25 February 2022.
- ^ Lóki, Gábor, et al. "Code factoring in GCC." Proceedings of the 2004 GCC Developers’ Summit. 2004.
- ^ Gupta, Rajiv (1998). "A code motion framework for global instruction scheduling". Compiler Construction: 219–233.
- ^ "LLVM: lib/Transforms/Scalar/Sink.cpp Source File". llvm.org. Retrieved 25 February 2022.
- ^ "Code Factoring Optimizations - GNU Project". gcc.gnu.org. Retrieved 25 February 2022.
- ^ "GCC Developer's Summit 2004 - Code Factoring.pdf" (PDF). gnu.org. Retrieved 25 February 2022.
- ^ "Allocation sinking in git HEAD - luajit - FreeLists". www.freelists.org. Retrieved 25 February 2022.
- ^ "Allocation Sinking Optimization". wiki.luajit.org.