docs/LoopTerminology.rst

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