Code Sinking
Code sinking, sometimes referred to as lazy code motion, is a compiler optimization that moves computations into less frequently executed regions of code. If an operation is executed before a branch and only one branch uses its result, code sinking delays the computation and places it inside the branch so the operation is executed only on the path where it is needed.[1] By executing computations only when their results are required, code sinking can reduce the instruction's execution count, lower register pressure, and sometimes decrease code size. Unlike dead code elimination, which removes instructions only if their results are never used, code sinking removes or moves instructions even when there is a possible use on some execution path, as long as redundant executions are avoided.[1] Modern compilers implement sinking as part of their code-motion passes; for example, LLVM’s sink pass moves instructions into successor blocks so they aren’t executed on paths where their results aren’t needed.[2]
Code Sinking Transformation in emmtrix Studio
In emmtrix Studio, the Code Sinking Transformation can be applied using a #pragma directive or via the graphical user interface. The transformation analyzes control flow and data dependencies to relocate computations to later points in the code (e.g., into conditional branches or deeper inside loops), while preserving program semantics. Expressions whose results are used only in specific branches are moved into those branches, reducing the workload on frequently executed paths. The transformation uses the execution counts determined by emmtrix Performance Estimator to decide if it is profitable to sink an expressions.
Typical Usage and Benefits
- Reducing redundant computations: moves expressions into the branches or loops where they are actually used.
- Improving cache and memory performance: fewer instructions on hot paths improve cache utilization and lower power usage.
- Lowering register pressure: delays computation to free up registers earlier in execution.
- Enabling further optimizations: simplification of control flow and data dependencies can enable more aggressive compiler transformations.
Example
The following example shows how expressions x and y are originally computed unconditionally, even though only one of them is used depending on the condition. After code sinking, each computation is moved into its corresponding branch.
| Before Transformation | After Transformation |
|---|---|
Original code: both x and y are computed on every iteration.#include <stdio.h>
#pragma EMX_TRANSFORMATION CodeSinking
int main(void) {
int n = 10;
for (int i = 0; i < 2; ++i) {
int x = n * n;
int y = n * n * n;
int z;
if (i == 0) {
z = x;
} else {
z = y;
}
printf("%d\n", z);
}
}
|
After code sinking: the computations are moved into the appropriate branch.#include <stdio.h>
int main(void) {
int n = 10;
for (int i = 0; i < 2; ++i) {
int z;
if (i == 0) {
int x = n * n;
z = x;
} else {
int y = n * n * n;
z = y;
}
printf("%d\n", z);
}
}
|
Parameters
| Id | Default Value | Description |
|---|---|---|
threshold |
1.45 | Defines the factor by which the number of executions must be reduced for an expression to be moved. |
conditional |
false | Adds additional if blocks when needed to enable legal code movement.
|
Notes
- To move functions from
math.h, use the Idiom Recognizer transformation to identify the functions and apply the code sinking transformation afterwards. - Code sinking can be used in combination with other optimizations such as loop-invariant code motion.