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 action of moving code within a program, usually for performance or size benefits in the compiled application.
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.[1] 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 Factoring
Code Factoring is a size-optimization technique which merges common dependencies in branches.
Loop-invariant Code Motion
Code Hoisting
Code hoisting brings certain operations 'upwards' in executing code, for various reasons. Eg, some compilers use code hoisting to alleviate
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.[2] 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.[3] GCC will move any code upwards or downwards if it "[does not] invalidate any existing dependences nor introduce new ones".[4]
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.[5] 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.[6]
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.
- ^ "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.