Terminology¶

The definition of a loop comes with some additional terminology:

• Anentering block (orloop predecessor) is a non-loop nodethat has an edge into the loop (necessarily the header). If there isonly one entering block, and its only edge is to theheader, it is also called the loop’spreheader. The preheaderdominates the loop without itself being part of the loop.

• Alatch is a loop node that has an edge to the header.

• Abackedge is an edge from a latch to the header.

• Anexiting edge is an edge from inside the loop to a node outsideof the loop. The source of such an edge is called anexiting block, itstarget is anexit block.

Important Notes¶

This loop definition has some noteworthy consequences:

• A node can be the header of at most one loop. As such, a loop can beidentified by its header. Due to the header being the only entry intoa loop, it can be called a Single-Entry-Multiple-Exits (SEME) region.

• For basic blocks that are not reachable from the function’s entry, theconcept of loops is undefined. This follows from the concept ofdominance being undefined as well.

• The smallest loop consists of a single basic block that branches toitself. In this case that block is the header, latch (and exitingblock if it has another edge to a different block) at the same time.A single block that has no branch to itself is not considered a loop,even though it is trivially strongly connected.

In this case, the role of header, exiting block and latch fall to thesame node.LoopInfo reports this as:

$optinput.ll-passes='print<loops>'Loop at depth 1 containing: %for.body<header><latch><exiting>

• Loops can be nested inside each other. That is, a loop’s node set canbe a subset of another loop with a different loop header. The loophierarchy in a function forms a forest: Each top-level loop is theroot of the tree of the loops nested inside it.

• It is not possible that two loops share only a few of their nodes.Two loops are either disjoint or one is nested inside the other. Inthe example below the left and right subsets both violate themaximality condition. Only the merge of both sets is considered a loop.

• It is also possible that two logical loops share a header, but areconsidered a single loop by LLVM:

for(inti=0;i<128;++i)for(intj=0;j<128;++j)body(i,j);

which might be represented in LLVM-IR as follows. Note that there isonly a single header and hence just a single loop.

TheLoopSimplify pass willdetect the loop and ensure separate headers for the outer and inner loop.

• A cycle in the CFG does not imply there is a loop. The example belowshows such a CFG, where there is no header node that dominates allother nodes in the cycle. This is calledirreducible control-flow.

The term reducible results from the ability to collapse the CFG into asingle node by successively replacing one of three base structures witha single node: A sequential execution of basic blocks, acyclic conditionalbranches (or switches), and a basic block looping on itself.Wikipediahas a more formal definition, which basically says that every cycle hasa dominating header.

• Irreducible control-flow can occur at any level of the loop nesting.That is, a loop that itself does not contain any loops can still havecyclic control flow in its body; a loop that is not nested insideanother loop can still be part of an outer cycle; and there can beadditional cycles between any two loops where one is contained in the other.However, an LLVMcycle covers both, loops andirreducible control flow.

• TheFixIrreduciblepass can transform irreducible control flow into loops by insertingnew loop headers. It is not included in any default optimization passpipeline, but is required for some back-end targets.

• Exiting edges are not the only way to break out of a loop. Otherpossibilities are unreachable terminators, [[noreturn]] functions,exceptions, signals, and your computer’s power button.

• A basic block “inside” the loop that does not have a path back to theloop (i.e. to a latch or header) is not considered part of the loop.This is illustrated by the following code.

for(unsignedi=0;i<=n;++i){if(c1){// When reaching this block, we will have exited the loop.do_something();break;}if(c2){// abort(), never returns, so we have exited the loop.abort();}if(c3){// The unreachable allows the compiler to assume that this will not rejoin the loop.do_something();__builtin_unreachable();}if(c4){// This statically infinite loop is not nested because control-flow will not continue with the for-loop.while(true){do_something();}}}

• There is no requirement for the control flow to eventually leave theloop, i.e. a loop can be infinite. Astatically infinite loop is aloop that has no exiting edges. Adynamically infinite loop hasexiting edges, but it is possible to be never taken. This may happenonly under some circumstances, such as when n == UINT_MAX in the codebelow.

for(unsignedi=0;i<=n;++i)body(i);

It is possible for the optimizer to turn a dynamically infinite loopinto a statically infinite loop, for instance when it can prove that theexiting condition is always false. Because the exiting edge is nevertaken, the optimizer can change the conditional branch into anunconditional one.

If a is loop is annotated withllvm.loop.mustprogress metadata,the compiler is allowed to assume that it will eventually terminate, evenif it cannot prove it. For instance, it may remove a mustprogress-loopthat does not have any side-effect in its body even though the programcould be stuck in that loop forever. Languages such as C andC++ have suchforward-progress guarantees for some loops. Also see themustprogress andwillreturn function attributes, as well asthe olderllvm.sideeffect intrinsic.

• The number of executions of the loop header before leaving the loop istheloop trip count (oriteration count). If the loop shouldnot be executed at all, aloop guard must skip the entire loop:

Since the first thing a loop header might do is to check whether thereis another execution and if not, immediately exit without doing any work(also seeRotated Loops), loop trip count is notthe best measure of a loop’s number of iterations. For instance, thenumber of header executions of the code below for a non-positive n(before loop rotation) is 1, even though the loop body is not executedat all.

for(inti=0;i<n;++i)body(i);

A better measure is thebackedge-taken count, which is the number oftimes any of the backedges is taken before the loop. It is one less thanthe trip count for executions that enter the header.

Rotated Loops¶

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

voidtest(intn){for(inti=0;i<n;i+=1)// Loop body}

is transformed to:

voidtest(intn){inti=0;do{// Loop bodyi+=1;}while(i<n);}

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:

voidtest(intn){inti=0;if(n>0){do{// Loop bodyi+=1;}while(i<n);}}

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 theview-cfg pass.

The initialfor loop could be translated to:

define void @test(i32 %n) {entry:  br label %for.headerfor.header:  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]  %cond = icmp slt i32 %i, %n  br i1 %cond, label %body, label %exitbody:  ; Loop body  br label %latchlatch:  %i.next = add nsw i32 %i, 1  br label %for.headerexit:  ret void}

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

define void @test(i32 %n) {entry:  br label %bodybody:  %i = phi i32 [ 0, %entry ], [ %i.next, %latch ]  ; Loop body  br label %latchlatch:  %i.next = add nsw i32 %i, 1  %cond = icmp slt i32 %i.next, %n  br i1 %cond, label %body, label %exitexit:  ret void}

Note 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:

define void @test(i32 %n) {entry:  %guard_cond = icmp slt i32 0, %n  br i1 %guard_cond, label %loop.preheader, label %exitloop.preheader:  br label %bodybody:  %i2 = phi i32 [ 0, %loop.preheader ], [ %i.next, %latch ]  br label %latchlatch:  %i.next = add nsw i32 %i2, 1  %cond = icmp slt i32 %i.next, %n  br i1 %cond, label %body, label %loop.exitloop.exit:  br label %exitexit:  ret void}

The 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:

for(inti=0;i<n;++i){autov=*p;use(v);}

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:

autov=*p;for(inti=0;i<n;++i){use(v);}

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:

if(n>0){// loop guardautov=*p;for(inti=0;i<n;++i){use(v);}}

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:

if(0<n){autov=*p;do{use(v);++i;}while(i<n);}

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