How to create Loop object on the LLVM?

Question

I wonder how LLVM can create Loop object.

There are a lot of objects related to Loop such as LoopInfo, LoopBase, Loop, etc.

But I can't find the location of LLVM source code where they create those objects.

I want to know how they track the back-edge, and how to identify that is a Loop.

So to speak, I want to learn whole principles about detecting and analyzing Loop information on the LLVM

Answer 1

There are two ways you can go about implementing a conventional loop. One does not use the phi instruction and one does, however, both use the br operator.

Take a look at the following code:

#include <stdio.h>

int main () {

   for(int i = 0; i < 10; i++) {
      printf("Test.\n");
   }

   return 0;
}

Here, I have generated an example using Clang with command clang -S loop.c -emit-llvm, causing it to implement the first option:

@.str = private unnamed_addr constant [7 x i8] c"Test.\0A\00", align 1

; Function Attrs: nounwind
define i32 @main() #0 {
entry:
  %retval = alloca i32, align 4
  %i = alloca i32, align 4
  store i32 0, i32* %retval
  store i32 0, i32* %i, align 4
  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry
  %0 = load i32* %i, align 4
  %cmp = icmp slt i32 %0, 10
  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond
  %call = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([7 x i8]* @.str, i32 0, i32 0)) #1
  br label %for.inc

for.inc:                                          ; preds = %for.body
  %1 = load i32* %i, align 4
  %inc = add nsw i32 %1, 1
  store i32 %inc, i32* %i, align 4
  br label %for.cond

for.end:                                          ; preds = %for.cond
  ret i32 0
}

; Function Attrs: nounwind
declare i32 @printf(i8*, ...) #0

First, we create identifiers to represent our i and return value variables and then set them each to 0. It goes to the first label and begins the loop, starting with calculating a boolean value resulting from the icmp <cond> <ty> <op1>, <op2> instruction, where slt = "signed less than". If %i is less than 10, true will be stored in %cmp, else, false will be stored. The overloaded syntax of the br instruction that follows, br i1 <cond>, label <iftrue>, label <iffalse> defines that if %cmp is true, the program will jump to the iftrue label, in this case, %for.body, otherwise, it will jump to the iffalse label, in this case, %for.end. Summarized, this instruction will enter the loop body if %i is still less than 10, and if it reaches 10, it will exit the loop. With this final knowledge of the br instruction, the behavior of the rest of the program should be obvious.

Now, while the second method is much shorter, it is slightly more complicated. I generated this code using Clang with command clang -S loop.c -emit-llvm -O1, i.e., tagging on the level 1 optimization flag, causing it to implement the second option:

@.str = private unnamed_addr constant [7 x i8] c"Test.\0A\00", align 1
@str = private unnamed_addr constant [6 x i8] c"Test.\00"

; Function Attrs: nounwind
define i32 @main() #0 {
entry:
  br label %for.body

for.body:                                         ; preds = %for.body, %entry
  %i.02 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
  %puts = tail call i32 @puts(i8* getelementptr inbounds ([6 x i8]* @str, i32 0, i32 0))
  %inc = add nuw nsw i32 %i.02, 1
  %exitcond = icmp eq i32 %inc, 10
  br i1 %exitcond, label %for.end, label %for.body

for.end:                                          ; preds = %for.body
  ret i32 0
}

; Function Attrs: nounwind
declare i32 @puts(i8* nocapture readonly) #1

Ignore the funny syntax of the increment technique %inc = add nuw nsw i32 %i.02, 1, it is simply integer math overflow error handling. We are focused on the phi instruction Here is the description from the manual:

At runtime, the ‘phi‘ instruction logically takes on the value specified by the pair corresponding to the predecessor basic block that executed just prior to the current block.

So, let's bring the code in question to our attention again:

for.body:
          %i.02 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
          %puts = tail call i32 @puts(i8* getelementptr inbounds ([6 x i8]* @str, i32 0, i32 0))
          %inc = add nuw nsw i32 %i.02, 1
          %exitcond = icmp eq i32 %inc, 10
          br i1 %exitcond, label %for.end, label %for.body

When we first come across %i.02, the last label we passed was entry. Therefore, we are instructed to set %i.02 to 0. Even though we have already passed the for.body label, the last predecessor block where a command was executed was in the entry block, making entry the last label. Next, we call our console print function. Then, we declare a variable %inc and set it to our 'i' variable + 1, and with this being the first increment, it would become 0. Lastly, we have a boolean comparison checking whether our 'i' value is less than 10, and in this case, it is, to which the br instruction sends us back to the top. Now is the tricky part: phi can tell that code was last executed in the for.body label. This means that we are still in the for.body predecessor block and %inc is still in our symbol table, which is why we can set %i.02 to %inc. %inc will continue to be incremented until it is equal to 10, to which the br instruction will jump to the %for.end label, thereby exiting the loop.

For more information on all the instructions mentioned, visit the LLVM Language Reference Manual.