1.. _loop-terminology:
2===========================================
3LLVM Loop Terminology (and Canonical Forms)
4===========================================
5
6.. contents::
7   :local:
8
9Introduction
10============
11
12Loops are a core concept in any optimizer.  This page spells out some
13of the common terminology used within LLVM code to describe loop
14structures.
15
16First, let's start with the basics. In LLVM, a Loop is a maximal set of basic
17blocks that form a strongly connected component (SCC) in the Control
18Flow Graph (CFG) where there exists a dedicated entry/header block that
19dominates all other blocks within the loop. Thus, without leaving the
20loop, one can reach every block in the loop from the header block and
21the header block from every block in the loop.
22
23Note that there are some important implications of this definition:
24
25* Not all SCCs are loops.  There exist SCCs that do not meet the
26  dominance requirement and such are not considered loops.
27
28* Loops can contain non-loop SCCs and non-loop SCCs may contain
29  loops.  Loops may also contain sub-loops.
30
31* A header block is uniquely associated with one loop.  There can be
32  multiple SCC within that loop, but the strongly connected component
33  (SCC) formed from their union must always be unique.
34
35* Given the use of dominance in the definition, all loops are
36  statically reachable from the entry of the function.
37
38* Every loop must have a header block, and some set of predecessors
39  outside the loop.  A loop is allowed to be statically infinite, so
40  there need not be any exiting edges.
41
42* Any two loops are either fully disjoint (no intersecting blocks), or
43  one must be a sub-loop of the other.
44
45A loop may have an arbitrary number of exits, both explicit (via
46control flow) and implicit (via throwing calls which transfer control
47out of the containing function).  There is no special requirement on
48the form or structure of exit blocks (the block outside the loop which
49is branched to).  They may have multiple predecessors, phis, etc...
50
51Key Terminology
52===============
53
54Header Block - The basic block which dominates all other blocks
55contained within the loop.  As such, it is the first one executed if
56the loop executes at all.  Note that a block can be the header of
57two separate loops at the same time, but only if one is a sub-loop
58of the other.
59
60Exiting Block - A basic block contained within a given loop which has
61at least one successor outside of the loop and one successor inside the
62loop.  (The latter is a consequence of the block being contained within
63an SCC which is part of the loop.)  That is, it has a successor which
64is an Exit Block.
65
66Exit Block - A basic block outside of the associated loop which has a
67predecessor inside the loop.  That is, it has a predecessor which is
68an Exiting Block.
69
70Latch Block - A basic block within the loop whose successors include
71the header block of the loop.  Thus, a latch is a source of backedge.
72A loop may have multiple latch blocks.  A latch block may be either
73conditional or unconditional.
74
75Backedge(s) - The edge(s) in the CFG from latch blocks to the header
76block.  Note that there can be multiple such edges, and even multiple
77such edges leaving a single latch block.
78
79Loop Predecessor -  The predecessor blocks of the loop header which
80are not contained by the loop itself.  These are the only blocks
81through which execution can enter the loop.  When used in the
82singular form implies that there is only one such unique block.
83
84Preheader Block - A preheader is a (singular) loop predecessor which
85ends in an unconditional transfer of control to the loop header.  Note
86that not all loops have such blocks.
87
88Backedge Taken Count - The number of times the backedge will execute
89before some interesting event happens.  Commonly used without
90qualification of the event as a shorthand for when some exiting block
91branches to some exit block. May be zero, or not statically computable.
92
93Iteration Count - The number of times the header will execute before
94some interesting event happens.  Commonly used without qualification to
95refer to the iteration count at which the loop exits.  Will always be
96one greater than the backedge taken count.  *Warning*: Preceding
97statement is true in the *integer domain*; if you're dealing with fixed
98width integers (such as LLVM Values or SCEVs), you need to be cautious
99of overflow when converting one to the other.
100
101It's important to note that the same basic block can play multiple
102roles in the same loop, or in different loops at once.  For example, a
103single block can be the header for two nested loops at once, while
104also being an exiting block for the inner one only, and an exit block
105for a sibling loop.  Example:
106
107.. code-block:: C
108
109  while (..) {
110    for (..) {}
111    do {
112      do {
113        // <-- block of interest
114        if (exit) break;
115      } while (..);
116    } while (..)
117  }
118
119LoopInfo
120========
121
122LoopInfo is the core analysis for obtaining information about loops.
123There are few key implications of the definitions given above which
124are important for working successfully with this interface.
125
126* LoopInfo does not contain information about non-loop cycles.  As a
127  result, it is not suitable for any algorithm which requires complete
128  cycle detection for correctness.
129
130* LoopInfo provides an interface for enumerating all top level loops
131  (e.g. those not contained in any other loop).  From there, you may
132  walk the tree of sub-loops rooted in that top level loop.
133
134* Loops which become statically unreachable during optimization *must*
135  be removed from LoopInfo. If this can not be done for some reason,
136  then the optimization is *required* to preserve the static
137  reachability of the loop.
138
139
140Loop Simplify Form
141==================
142
143TBD
144
145
146Loop Closed SSA (LCSSA)
147=======================
148
149TBD
150
151"More Canonical" Loops
152======================
153
154TBD
155