# Code motion

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Code_motion
> Markdown URL: https://mediated.wiki/source/Code_motion.md
> Source: https://en.wikipedia.org/wiki/Code_motion
> Source revision: 1352684029
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Generic term for compiler optimization

In [computer science](/source/Computer_science), **code motion**, which includes code hoisting, code sinking, loop-invariant code motion, and code factoring, is a blanket term for any process that moves code within a program. This is typically done for performance and size benefits, and it is a common [optimization](/source/Optimization) performed in most [optimizing compilers](/source/Optimizing_compilers).

## Uses

Code motion has a variety of uses and benefits, many of which overlap each other in their implementation.

### Removing unused/useless operations

A diagram depicting an optimizing compiler removing a potentially useless call to assembly instruction "b" by sinking it to its point of use

**Code sinking**, also known as **lazy code motion**, is a term for a technique that 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](/source/Dead_code_elimination) in the sense that it removes code when its 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

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

**Code factoring** is a term for a size-optimization technique that merges common dependencies in branches into the branch above it.[2] Just like [factorizing integers](/source/Integer_factorization) 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

Main article: [Instruction scheduling](/source/Instruction_scheduling)

An example of how a compiler might prevent dependency stalls in assembled code with code movement, by observing a [dependency graph](/source/Dependency_graph). Due to [out-of-order execution](/source/Out-of-order_execution) advancements, optimization may not have any benefit on modern CPUs.

**Global code motion**, **local code motion**, **code scheduling**, **[Instruction scheduling](/source/Instruction_scheduling)** and **code hoisting/sinking** are all terms for a technique where instructions are rearranged (or "scheduled") to improve the efficiency of [execution](/source/Out-of-order_execution) within the CPU.[3][4] Modern [CPUs](/source/CPU) are able to schedule five or more instructions per clock cycle. However, a CPU cannot schedule an instruction that relies on data from a currently (or not yet executed) instruction. Compilers will interleave dependencies in a manner that maximizes the amount of instructions a CPU can process at any point in time.[5]

On the defunct [Intel Itanium](/source/Itanium) architecture, the [branch predict](/source/Branch_predictor) (BRP) instruction is manually hoisted above branches by the compiler to enable the branch to be immediately taken by the CPU. Itanium relies on additional code scheduling from the CPU to maximize efficiency in the processor.[6]

## Loop-invariant code motion

Main article: [Loop-invariant code motion](/source/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 loop-invariant code to a position outside the loop, which may reduce the execution time of the loop by preventing some computations from being done twice for the same result.

## Compiler examples

### LLVM

[LLVM](/source/LLVM) has a sinking pass in its single static assignment form. LLVM 15.0 will not sink an operation if any of its code paths include a store instruction, or if it may throw an error.[7] Additionally, LLVM will not sink an instruction *into* a loop.

### GCC

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

### LuaJIT

[LuaJIT](/source/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.[10] Allocation sinking moves allocations to execution paths where the allocated object may escape the executing code, and will thus require [heap allocation](/source/Heap_allocation). All removed allocations are filled in with load-to-store forwarding over their fields.[11]

## See also

- [Loop-invariant code motion](/source/Loop-invariant_code_motion)

- [Instruction scheduling](/source/Instruction_scheduling)

- [Dependency graph](/source/Dependency_graph)

## References

1. **[^](#cite_ref-1)** Craft, Michael; Offut, Jefferson (1994). ["Using compiler optimization techniques to detect equivalent mutants"](https://onlinelibrary.wiley.com/doi/10.1002/stvr.4370040303). *Software Testing, Verification & Reliability*. **4** (3): 131–154. [doi](/source/Doi_(identifier)):[10.1002/stvr.4370040303](https://doi.org/10.1002%2Fstvr.4370040303). [S2CID](/source/S2CID_(identifier)) [35717348](https://api.semanticscholar.org/CorpusID:35717348). Retrieved 25 February 2022.

1. **[^](#cite_ref-2)** Lóki, Gábor, et al. "Code factoring in GCC." Proceedings of the 2004 GCC Developers’ Summit. 2004.

1. **[^](#cite_ref-3)** Fasse, Justus, et al. Code Transformations to Increase Prepass Scheduling Opportunities in CompCert. Diss. Master Thesis of Science. Université Grenoble Alpes. [https://www-verimag](https://www-verimag). imag. fr/~ boulme/CPP_2022/FASSE-Justus-MSc-Thesis_2021. pdf, 2021.

1. **[^](#cite_ref-4)** Gupta, Rajiv (1998). "A code motion framework for global instruction scheduling". *Compiler Construction*. Lecture Notes in Computer Science. Vol. 1383. pp. 219–233. [doi](/source/Doi_(identifier)):[10.1007/BFb0026434](https://doi.org/10.1007%2FBFb0026434). [ISBN](/source/ISBN_(identifier)) [978-3-540-64304-3](https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-64304-3).

1. **[^](#cite_ref-5)** Chang, Pohua P., et al. "The importance of prepass code scheduling for superscalar and superpipelined processors." IEEE Transactions on Computers 44.3 (1995): 353-370.

1. **[^](#cite_ref-6)** Sharangpani, H.; Arora, H. (September 2000). "Itanium processor microarchitecture". *IEEE Micro*. **20** (5): 24–43. [doi](/source/Doi_(identifier)):[10.1109/40.877948](https://doi.org/10.1109%2F40.877948). [ISSN](/source/ISSN_(identifier)) [1937-4143](https://search.worldcat.org/issn/1937-4143).

1. **[^](#cite_ref-7)** ["LLVM: lib/Transforms/Scalar/Sink.cpp Source File"](https://llvm.org/doxygen/Sink_8cpp_source.html). *llvm.org*. Retrieved 25 February 2022.

1. **[^](#cite_ref-8)** ["Code Factoring Optimizations - GNU Project"](https://gcc.gnu.org/projects/cfo.html). *gcc.gnu.org*. Retrieved 25 February 2022.

1. **[^](#cite_ref-9)** ["GCC Developer's Summit 2004 - Code Factoring.pdf"](https://gcc.gnu.org/pub/gcc/summit/2004/Code%20Factoring.pdf) (PDF). *gnu.org*. Retrieved 25 February 2022.

1. **[^](#cite_ref-10)** ["Allocation sinking in git HEAD - luajit - FreeLists"](https://www.freelists.org/post/luajit/Allocation-sinking-in-git-HEAD). *www.freelists.org*. Retrieved 25 February 2022.

1. **[^](#cite_ref-11)** ["Allocation Sinking Optimization"](http://wiki.luajit.org/Allocation-Sinking-Optimization). *wiki.luajit.org*.

v t e Compiler optimizations Basic block Peephole optimization Local value numbering Loop Automatic parallelization Automatic vectorization Induction variable Loop fusion Loop-invariant code motion Loop inversion Loop interchange Loop nest optimization Loop splitting Loop unrolling Loop unswitching Software pipelining Strength reduction Data-flow analysis Available expression Common subexpression elimination Constant folding Dead store elimination Induction variable recognition and elimination Live-variable analysis Upwards exposed uses Use-define chain Reaching definitions SSA-based Global value numbering Sparse conditional constant propagation Code generation Instruction scheduling Instruction selection Register allocation Rematerialization Functional Deforestation Tail-call elimination Global Interprocedural optimization Other Bounds-checking elimination Compile-time function execution Dead-code elimination Expression templates Inline expansion Jump threading Partial evaluation Profile-guided optimization Static analysis Alias analysis Array-access analysis Control-flow analysis Data-flow analysis Dependence analysis Escape analysis Pointer analysis Shape analysis Value range analysis

---
Adapted from the Wikipedia article [Code motion](https://en.wikipedia.org/wiki/Code_motion) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Code_motion?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.