LLVM Loop Terminology (and Canonical Forms)

Introduction

Loops are a core concept in any optimizer. This page spells out someof the common terminology used within LLVM code to describe loopstructures.

First, let’s start with the basics. In LLVM, a Loop is a maximal set of basicblocks that form a strongly connected component (SCC) in the ControlFlow Graph (CFG) where there exists a dedicated entry/header block thatdominates all other blocks within the loop. Thus, without leaving theloop, one can reach every block in the loop from the header block andthe header block from every block in the loop.

Note that there are some important implications of this definition:

  • Not all SCCs are loops. There exist SCCs that do not meet thedominance requirement and such are not considered loops.
  • Loops can contain non-loop SCCs and non-loop SCCs may containloops. Loops may also contain sub-loops.
  • A header block is uniquely associated with one loop. There can bemultiple SCC within that loop, but the strongly connected component(SCC) formed from their union must always be unique.
  • Given the use of dominance in the definition, all loops arestatically reachable from the entry of the function.
  • Every loop must have a header block, and some set of predecessorsoutside the loop. A loop is allowed to be statically infinite, sothere need not be any exiting edges.
  • Any two loops are either fully disjoint (no intersecting blocks), orone must be a sub-loop of the other.
  • Loops in a function form a forest. One implication of this factis that a loop either has no parent or a single parent.

A loop may have an arbitrary number of exits, both explicit (viacontrol flow) and implicit (via throwing calls which transfer controlout of the containing function). There is no special requirement onthe form or structure of exit blocks (the block outside the loop whichis branched to). They may have multiple predecessors, phis, etc…

Key Terminology

Header Block - The basic block which dominates all other blockscontained within the loop. As such, it is the first one executed ifthe loop executes at all. Note that a block can be the header oftwo separate loops at the same time, but only if one is a sub-loopof the other.

Exiting Block - A basic block contained within a given loop which hasat least one successor outside of the loop and one successor inside theloop. (The latter is a consequence of the block being contained withinan SCC which is part of the loop.) That is, it has a successor whichis an Exit Block.

Exit Block - A basic block outside of the associated loop which has apredecessor inside the loop. That is, it has a predecessor which isan Exiting Block.

Latch Block - A basic block within the loop whose successors includethe header block of the loop. Thus, a latch is a source of backedge.A loop may have multiple latch blocks. A latch block may be eitherconditional or unconditional.

Backedge(s) - The edge(s) in the CFG from latch blocks to the headerblock. Note that there can be multiple such edges, and even multiplesuch edges leaving a single latch block.

Loop Predecessor - The predecessor blocks of the loop header whichare not contained by the loop itself. These are the only blocksthrough which execution can enter the loop. When used in thesingular form implies that there is only one such unique block.

Preheader Block - A preheader is a (singular) loop predecessor whichends in an unconditional transfer of control to the loop header. Notethat not all loops have such blocks.

Backedge Taken Count - The number of times the backedge will executebefore some interesting event happens. Commonly used withoutqualification of the event as a shorthand for when some exiting blockbranches to some exit block. May be zero, or not statically computable.

Iteration Count - The number of times the header will execute beforesome interesting event happens. Commonly used without qualification torefer to the iteration count at which the loop exits. Will always beone greater than the backedge taken count. Warning: Precedingstatement is true in the integer domain; if you’re dealing with fixedwidth integers (such as LLVM Values or SCEVs), you need to be cautiousof overflow when converting one to the other.

It’s important to note that the same basic block can play multipleroles in the same loop, or in different loops at once. For example, asingle block can be the header for two nested loops at once, whilealso being an exiting block for the inner one only, and an exit blockfor a sibling loop. Example:

  1. while (..) {
  2.   for (..) {}
  3.   do {
  4.     do {
  5.       // <-- block of interest
  6.       if (exit) break;
  7.     } while (..);
  8.   } while (..)
  9. }

LoopInfo

LoopInfo is the core analysis for obtaining information about loops.There are few key implications of the definitions given above whichare important for working successfully with this interface.

  • LoopInfo does not contain information about non-loop cycles. As aresult, it is not suitable for any algorithm which requires completecycle detection for correctness.
  • LoopInfo provides an interface for enumerating all top level loops(e.g. those not contained in any other loop). From there, you maywalk the tree of sub-loops rooted in that top level loop.
  • Loops which become statically unreachable during optimization must_be removed from LoopInfo. If this can not be done for some reason,then the optimization is _required to preserve the staticreachability of the loop.

Loop Simplify Form

The Loop Simplify Form is a canonical form that makesseveral analyses and transformations simpler and more effective.It is ensured by the LoopSimplify(-loop-simplify) pass and is automaticallyadded by the pass managers when scheduling a LoopPass.This pass is implemented inLoopSimplify.h.When it is successful, the loop has:

  • A preheader.
  • A single backedge (which implies that there is a single latch).
  • Dedicated exits. That is, no exit block for the loophas a predecessor that is outside the loop. This impliesthat all exit blocks are dominated by the loop header.

Loop Closed SSA (LCSSA)

TBD

“More Canonical” Loops

Rotated Loops

Loops are rotated by the LoopRotate (loop-rotate)pass, which converts loops into do/while style loops and isimplemented inLoopRotation.h. Example:

  1. void test(int n) {
  2.   for (int i = 0; i < n; i += 1)
  3.     // Loop body
  4. }

is transformed to:

  1. void test(int n) {
  2.   int i = 0;
  3.   do {
  4.     // Loop body
  5.     i += 1;
  6.   } while (i < n);
  7. }

Warning: This transformation is valid only if the compilercan prove that the loop body will be executed at least once. Otherwise,it has to insert a guard which will test it at runtime. In the exampleabove, that would be:

  1. void test(int n) {
  2.   int i = 0;
  3.   if (n > 0) {
  4.     do {
  5.       // Loop body
  6.       i += 1;
  7.     } while (i < n);
  8.   }
  9. }

It’s important to understand the effect of loop rotationat the LLVM IR level. We follow with the previous examplesin LLVM IR while also providing a graphical representationof the control-flow graphs (CFG). You can get the same graphicalresults by utilizing the view-cfg pass.

The initial for loop could be translated to:

  1. define void @test(i32 %n) {
  2. entry:
  3.   br label %for.header
  4.  
  5. for.header:
  6.   %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
  7.   %cond = icmp slt i32 %i, %n
  8.   br i1 %cond, label %body, label %exit
  9.  
  10. body:
  11.   ; Loop body
  12.   br label %latch
  13.  
  14. latch:
  15.   %i.next = add nsw i32 %i, 1
  16.   br label %for.header
  17.  
  18. exit:
  19.   ret void
  20. }

_images/loop-terminology-initial-loop.pngBefore we explain how LoopRotate will actuallytransform this loop, here’s how we could convertit (by hand) to a do-while style loop.

  1. define void @test(i32 %n) {
  2. entry:
  3.   br label %body
  4.  
  5. body:
  6.   %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]
  7.   ; Loop body
  8.   br label %latch
  9.  
  10. latch:
  11.   %i.next = add nsw i32 %i, 1
  12.   %cond = icmp slt i32 %i.next, %n
  13.   br i1 %cond, label %body, label %exit
  14.  
  15. exit:
  16.   ret void
  17. }

_images/loop-terminology-rotated-loop.pngNote two things:

  • The condition check was moved to the “bottom” of the loop, i.e.the latch. This is something that LoopRotate does by copying the headerof the loop to the latch.
  • The compiler in this case can’t deduce that the loop willdefinitely execute at least once so the above transformationis not valid. As mentioned above, a guard has to be inserted,which is something that LoopRotate will do.

This is how LoopRotate transforms this loop:

  1. define void @test(i32 %n) {
  2. entry:
  3.   %guard_cond = icmp slt i32 0, %n
  4.   br i1 %guard_cond, label %loop.preheader, label %exit
  5.  
  6. loop.preheader:
  7.   br label %body
  8.  
  9. body:
  10.   %i2 = phi i32 [ 0, %loop.preheader ], [ %i.next, %latch ]
  11.   br label %latch
  12.  
  13. latch:
  14.   %i.next = add nsw i32 %i2, 1
  15.   %cond = icmp slt i32 %i.next, %n
  16.   br i1 %cond, label %body, label %loop.exit
  17.  
  18. loop.exit:
  19.   br label %exit
  20.  
  21. exit:
  22.   ret void
  23. }

_images/loop-terminology-guarded-loop.pngThe result is a little bit more complicated than we may expectbecause LoopRotate ensures that the loop is inLoop Simplify Formafter rotation.In this case, it inserted the %loop.preheader basic block sothat the loop has a preheader and it introduced the %loop.exitbasic block so that the loop has dedicated exits(otherwise, %exit would be jumped from both %latch and %entry,but %entry is not contained in the loop).Note that a loop has to be in Loop Simplify Form beforehandtoo for LoopRotate to be applied successfully.

The main advantage of this form is that it allows hoistinginvariant instructions, especially loads, into the preheader.That could be done in non-rotated loops as well but withsome disadvantages. Let’s illustrate them with an example:

  1. for (int i = 0; i < n; ++i) {
  2.   auto v = *p;
  3.   use(v);
  4. }

We assume that loading from p is invariant and use(v) is somestatement that uses v.If we wanted to execute the load only once we could move it“out” of the loop body, resulting in this:

  1. auto v = *p;
  2. for (int i = 0; i < n; ++i) {
  3.   use(v);
  4. }

However, now, in the case that n <= 0, in the initial form,the loop body would never execute, and so, the load wouldnever execute. This is a problem mainly for semantic reasons.Consider the case in which n <= 0 and loading from p is invalid.In the initial program there would be no error. However, with thistransformation we would introduce one, effectively breakingthe initial semantics.

To avoid both of these problems, we can insert a guard:

  1. if (n > 0) {  // loop guard
  2.   auto v = *p;
  3.   for (int i = 0; i < n; ++i) {
  4.     use(v);
  5.   }
  6. }

This is certainly better but it could be improved slightly. Noticethat the check for whether n is bigger than 0 is executed twice (andn does not change in between). Once when we check the guard conditionand once in the first execution of the loop. To avoid that, we coulddo an unconditional first execution and insert the loop conditionin the end. This effectively means transforming the loop into a do-while loop:

  1. if (0 < n) {
  2.   auto v = *p;
  3.   do {
  4.     use(v);
  5.     ++i;
  6.   } while (i < n);
  7. }

Note that LoopRotate does not generally do suchhoisting. Rather, it is an enabling transformation for otherpasses like Loop-Invariant Code Motion (-licm).