• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1# Loop-invariant code motion (LICM)
2
3## Overview
4`LICM` moves instructions outside the body of a loop without affecting the program semantics
5
6## Rationality
7Instructions which have been hoisted out of a loop are executed less often, providing a speedup
8
9## Dependence
10* Loop Analysis;
11* Dominators Tree;
12
13## Algorithm
14`LICM` visits loops from inner to outer, skipping irreducible and OSR loops. In each loop it selects instructions, which can be hoisted:
15* all instruction's inputs should dominate loop's pre-header or they are selected to hoist;
16* instruction must dominate all loop exits;
17
18Then selected instructions are moved to the loop pre-header
19## Pseudocode
20TBD
21## Examples
22```
23BB 0
24prop: start
25   12.i64  Constant                   0x1 -> (v3p, v13, v13, v5)
26    1.i64  Constant                   0xa -> (v4p)
27    2.i64  Constant                   0x14 -> (v10)
28succs: [bb 2]
29
30BB 2  preds: [bb 6, bb 3]
31prop: head, loop 1
32   3p.u64  Phi                        v12(bb6), v7(bb3) -> (v7, v10)
33   4p.u64  Phi                        v1(bb6), v8(bb3) -> (v5, v7, v8)
34    5.b    Compare EQ u64             v4p, v12 -> (v6)
35    6.     IfImm NE b                 v5, 0x0
36succs: [bb 3, bb 4]
37
38BB 3  preds: [bb 2]
39prop: loop 1
40    7.u64  Mul                        v3p, v4p -> (v3p)
41   13.u64  Mul                        v12, v12 -> (v8)
42    8.u64  Sub                        v4p, v13 -> (v4p)
43succs: [bb 2]
44
45
46BB 4  preds: [bb 2]
47   10.u64  Add                        v2, v3p
48   11.     ReturnVoid
49succs: [bb 1]
50```
51`LICM` hoists `13.u64 Mul` instruction:
52
53```
54BB 0
55prop: start
56   12.i64  Constant                   0x1 -> (v3p, v13, v13, v5)
57    1.i64  Constant                   0xa -> (v4p)
58    2.i64  Constant                   0x14 -> (v10)
59succs: [bb 6]
60
61BB 6  preds: [bb 0]
62   13.u64  Mul                        v12, v12 -> (v8)
63succs: [bb 2]
64
65BB 2  preds: [bb 6, bb 3]
66prop: head, loop 1
67   3p.u64  Phi                        v12(bb6), v7(bb3) -> (v7, v10)
68   4p.u64  Phi                        v1(bb6), v8(bb3) -> (v5, v7, v8)
69    5.b    Compare EQ u64             v4p, v12 -> (v6)
70    6.     IfImm NE b                 v5, 0x0
71succs: [bb 3, bb 4]
72
73BB 3  preds: [bb 2]
74prop: loop 1
75    7.u64  Mul                        v3p, v4p -> (v3p)
76    8.u64  Sub                        v4p, v13 -> (v4p)
77succs: [bb 2]
78
79BB 4  preds: [bb 2]
80   10.u64  Add                        v2, v3p
81   11.     ReturnVoid
82succs: [bb 1]
83
84```
85
86## Links
87Source code:
88[licm.cpp](../optimizer/optimizations/licm.cpp)
89[licm.h](../optimizer/optimizations/licm.h)
90
91Tests:
92[licm_test.cpp](../tests/licm_test.cpp)