Bots, Bureaucrats, Interface administrators, smwadministrator, smwcurator, smweditor, Administrators
2,502
edits
Code Sinking: Difference between revisions
Jump to navigation
Jump to search
no edit summary
No edit summary |
Timo.stripf (talk | contribs) No edit summary |
||
| Line 1: | Line 1: | ||
Code sinking is | '''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.<ref>[https://en.wikipedia.org/wiki/Code_motion Wikipedia – Code Motion]</ref> | ||
The technique also applies to loops: when a value changes on every iteration, moving the computation from outside a loop into the loop body reduces redundant work and ensures the result is produced exactly when needed.<ref>[https://www.geeksforgeeks.org/compiler-design/global-code-scheduling-in-compiler-design/ GeeksforGeeks – Global Code Scheduling]</ref> | |||
By executing computations only when their results are required, code sinking can reduce the instruction 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.<ref>[https://en.wikipedia.org/wiki/Code_motion Wikipedia – Code Motion]</ref> | |||
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.<ref>[https://llvm.org/docs/Passes.html#sink-code-sinking LLVM Pass Documentation – Sink]</ref> | |||
==Code Sinking Transformation in emmtrix Studio== | == Code Sinking Transformation in emmtrix Studio == | ||
emmtrix Studio can | 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. | ||
=== Typical Usage and Benefits === | === 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 | 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. | ||
{| class="wikitable" | |||
|- | |||
! Before Transformation !! After Transformation | |||
|- | |||
| <syntaxhighlight lang="c"> | |||
// Original code: both x and y are computed on every iteration. | |||
#include <stdio.h> | #include <stdio.h> | ||
| Line 23: | Line 36: | ||
z = y; | z = y; | ||
} | } | ||
printf( | printf("%d\n", z); | ||
} | |||
} | |||
</syntaxhighlight> | |||
| <syntaxhighlight lang="c"> | |||
// 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); | |||
} | } | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
|} | |||
== Parameters == | |||
{| class="wikitable" | {| class="wikitable" | ||
! Id !! Default Value !! Description | |||
!Id | |||
!Default Value | |||
!Description | |||
|- | |- | ||
|<code>threshold</code> | | <code>threshold</code> || 1.45 || Defines the factor by which the number of executions must be reduced for an expression to be moved. | ||
|1.45 | |||
| | |||
|- | |- | ||
|<code>conditional</code> | | <code>conditional</code> || false || Adds additional <code>if</code> blocks when needed to enable legal code movement. | ||
|false | |||
| | |||
|- | |- | ||
|<code>expected_moved_exprs</code> | | <code>expected_moved_exprs</code> || −1 || Used for test validation. If set ≥ 0, the transformation will verify the number of moved expressions. | ||
| | |||
| | |||
|} | |} | ||
=== | == Notes == | ||
* To move functions from <code>math.h</code>, 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. | |||
== References == | |||
<references/> | |||
[[Category:Code Transformation]] | [[Category:Code Transformation]] | ||