Understanding Code Generation for For Loops in Clang

This post summarizes my experience understanding how code generation for “For” loops works in Clang. This would also be a good introduction to how compiler generates for loop code in general.

The theoretical part

We start from the simplest for loop

#include <stdio.h>

int main()

{

int sum = 0;

for(int i = 0; i < 100; i++){

sum += i;

}

printf(“sum: %d\n”, sum);

return 1;

}

In theory, Page 384 of “Engineering a Compiler” second edition, Keith D. Copper and Linda Torczon, chapter 7.8.2, there should be 5 “steps” to generating a for loop

step 1: Evaluate i

Step 2: if i > 100, go to step 5 (evaluate e2 in the book)

Step 3: Loop Body (sum += i)

Step 4: Evaluate i++ (e3 in the book) , if  i < 100 (e2) then go to Step 3

Step 5: Statement after the loop

With this command

bin/clang ../test_programs/test_for.c  -Xclang -ast-dump -fsyntax-only  -o tf.o

Ignore the internal declarations in Clang, you get the following AST dump, I have added comments to it

`-CompoundStmt 0x7065398 <line:4:1, line:10:1>

|-DeclStmt 0x70650d8 <line:5:3, col:14>

| `-VarDecl 0x7065058 <col:3, col:13> col:7 used sum ‘int’ cinit  (int sum = 0)

|   `-IntegerLiteral 0x70650b8 <col:13> ‘int’ 0

|-ForStmt 0x7065328 <line:6:3, line:8:3>  (the for statement)

| |-DeclStmt 0x7065180 <line:6:7, col:16> (int i = 0) 

| | `-VarDecl 0x7065100 <col:7, col:15> col:11 used i ‘int’ cinit   (induction or iteration variable i)

| |   `-IntegerLiteral 0x7065160 <col:15> ‘int’ 0 (initial value zero)

| |-<<<NULL>>>

| |-BinaryOperator 0x70651f8 <col:18, col:22> ‘int’ ‘<

| | |-ImplicitCastExpr 0x70651e0 <col:18> ‘int’ <LValueToRValue>

| | | `-DeclRefExpr 0x7065198 <col:18> ‘int’ lvalue Var 0x7065100 ‘i’ ‘int’

| | `-IntegerLiteral 0x70651c0 <col:22> ‘int’ 100

| |-UnaryOperator 0x7065248 <col:27, col:28> ‘int’ postfix ‘++‘   (i++)

| | `-DeclRefExpr 0x7065220 <col:27> ‘int’ lvalue Var 0x7065100 ‘i’ ‘int’

| `-CompoundStmt 0x7065308 <col:31, line:8:3>

|   `-CompoundAssignOperator 0x70652d0 <line:7:5, col:12> ‘int’ ‘+=‘  ComputeLHSTy=’int’ ComputeResultTy=’int’ (sum += i)

|     |-DeclRefExpr 0x7065268 <col:5> ‘int’ lvalue Var 0x7065058 ‘sum’ ‘int’

|     `-ImplicitCastExpr 0x70652b8 <col:12> ‘int’ <LValueToRValue>

|       `-DeclRefExpr 0x7065290 <col:12> ‘int’ lvalue Var 0x7065100 ‘i’ ‘int’

|-CallExpr 0x888e4c0 <line:9:3, col:26> ‘int’

| |-ImplicitCastExpr 0x888e4a8 <col:3> ‘int (*)(const char *, …)’ <FunctionToPointerDecay>

| | `-DeclRefExpr 0x888e380 <col:3> ‘int (const char *, …)’ Function 0x887fdc8 ‘printf‘ ‘int (const char *, …)’

| |-ImplicitCastExpr 0x888e510 <col:10> ‘const char *’ <BitCast>

| | `-ImplicitCastExpr 0x888e4f8 <col:10> ‘char *’ <ArrayToPointerDecay>

| |   `-StringLiteral 0x888e428 <col:10> ‘char [9]’ lvalue “sum: %d\n”

| `-ImplicitCastExpr 0x888e528 <col:23> ‘int’ <LValueToRValue>

|   `-DeclRefExpr 0x888e458 <col:23> ‘int’ lvalue Var 0x888e078 ‘sum’ ‘int’

`-ReturnStmt 0x888e560 <line:10:3, col:10>(return 1)

`-IntegerLiteral 0x888e540 <col:10> ‘int’ 1

Some interesting notes:

  1. Operator comes first (++ first, then the var is i)

Next, we will look at the corresponding LLVM IR generated, this is the command

bin/clang ../test_programs/test_for.c  -S -emit-llvm

@.str = private unnamed_addr constant [9 x i8] c”sum: %d\0A\00″, align 1

; Function Attrs: nounwind uwtable

define i32 @main() #0 {

entry:

%retval = alloca i32, align 4

%sum = alloca i32, align 4

%i = alloca i32, align 4

store i32 0, i32* %retval

store i32 0, i32* %sum, align 4  (sum = 0)

store i32 0, i32* %i, align 4 (i = 0) (step 1)

br label %for.cond (step 2)

for.cond:                                         ; preds = %for.inc, %entry  (predecessors of the block)

(i < 100, step 2)

%0 = load i32, i32* %i, align 4

%cmp = icmp slt i32 %0, 100  (this the last iteration variable) 

br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond  

(sum += i ) 

%1 = load i32, i32* %i, align 4

%2 = load i32, i32* %sum, align 4

%add = add nsw i32 %2, %1

store i32 %add, i32* %sum, align 4

br label %for.inc

for.inc:                                          ; preds = %for.body

(i++, step 4)

%3 = load i32, i32* %i, align 4

%inc = add nsw i32 %3, 1

store i32 %inc, i32* %i, align 4

br label %for.cond

for.end:                                          ; preds = %for.cond

(printf(“sum: %d\n”, sum), step 5)

%4 = load i32, i32* %sum, align 4

%call = call i32 (i8*, …) @printf(i8* getelementptr inbounds ([9 x i8], [9 x i8]* @.str, i32 0, i32 0), i32 %4)

ret i32 1

}

declare i32 @printf(i8*, …) #1

Advertisements
This entry was posted in Tools and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s