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