LLVM: Control Flow and Phi Node¶

LLVM provides a set of APIs for you to emit the platform dependent IR, and helps to optimize the generated IR and finally produces the low level executable code.

When writing a compiler, we first need to parse the high level source code into the AST. And then, after processing the modules and type checks, it's time to start to interact with LLVM to emit the LLVM IR.

This blog records my misunderstanding during learning llvm control flow and phi node.

SSA and Phi Node Concept¶

Basic SSA¶

SSA(Single Static Assignment) is a kind of format used in LLVM IR. It is a naming convention for storage locations (variables) in low-level representations of computer programs. A simple example reveals the case:

Pseudo CodeSSA Representation

x = 1;
y = x + 1;
x = 2;
z = x + 1;

x_1 = 1;
y = x_1 + 1;
x_2 = 2;
z = x_2 + 1;

Every variable will be represented with a unique identifier name, even in the case that hold a lot of branches.

How SSA Represents If-Then-Else¶

Now, we start to see the SSA in branches:

For example, the code above has the respective SSA format:

Because each branch creates a new variable(\(y_1\) and \(y_2\)), the merge point doesn't know which variable to apply. As a result, the \(\phi\)-function is introduced to express the picking up.

The behavior of the \(\phi\)-function is to select dynamically the value of the parameter associated with the actually executed control-flow path. This parameter value is assigned to the fresh variable name, on the left-hand side of the \(\phi\)-function.

Such pseudo-functions are required to maintain the SSA property of unique variable definitions, in the presence of branching control flow. Hence, in the above example, \(y_3\) is set to \(y_1\) if control flows from basic block A, and set to \(y_2\) if it flows from basic block B.

Note about \(\phi\)-function

One thing to note here is that the \(\phi\)-function mentioned here is still an API layer, and we don't dive deep to learn how it really works in details. If you want to know, please read this book.

Phi Node Usages in The Real World¶

Clang Representation¶

In the real world, the \(\phi\)-function works a bit different. After reading the introduction above, it sounds that the \(\phi\) is compulsory otherwise the program cannot work correctly. However, it's indeed optional and will be generated by the compiler when the optimizers are enabled.

The clang, which utilizes llvm backend to generate low level code, provides the option to emit the llvm IR:

# -o - means print the output into stdout
clang -cc1 -disable-O0-optnone foo.c -emit-llvm -O0

One thing to note is if the XClang flag -disable-O0-optnone is not provided, clang will emit the attribute of optnone which thwarts the following llvm IR optimization.

The code below is used to emit llvm the llvm IR.

void use(int); 
int f1();
int f2();
void test(int i) { 
    int x; 
    if (i) x = f1(); else x = f2();
    use(x); 
}

There is an interesting fact, because if you provide a simple function that returns a fixed value, the clang will optimize it when you want to see the \(\phi\) node. When I tried to use stdio.h, clang complains it cannot find. Hence, add an attribute for a single function is a good idea.

int r2() __attribute__((optnone)){
    return 1;
}

However, this is could be achieved by omitting the implementation but declaring function only. Then we call clang with different optimization level:

O0O1

Generated by command clang -cc1 -disable-O0-optnone foo.c -emit-llvm -O0:

; Function Attrs: noinline nounwind
define void @test(i32 noundef %i) #0 {
entry:
%i.addr = alloca i32, align 4
%x = alloca i32, align 4
store i32 %i, ptr %i.addr, align 4
%0 = load i32, ptr %i.addr, align 4
%tobool = icmp ne i32 %0, 0
br i1 %tobool, label %if.then, label %if.else

if.then:                                          ; preds = %entry
%call = call i32 @f1()
store i32 %call, ptr %x, align 4
br label %if.end

if.else:                                          ; preds = %entry
%call1 = call i32 @f2()
store i32 %call1, ptr %x, align 4
br label %if.end

if.end:                                           ; preds = %if.else, %if.then
%1 = load i32, ptr %x, align 4
call void @use(i32 noundef %1)
ret void
}

Generated by command clang -cc1 foo.c -emit-llvm -O1 -o -:

define void @test(i32 noundef %i) local_unnamed_addr #0 {
entry:
%tobool.not = icmp eq i32 %i, 0
br i1 %tobool.not, label %if.else, label %if.then

if.then:                                          ; preds = %entry
%call = tail call i32 @f1() #2
br label %if.end

if.else:                                          ; preds = %entry
%call1 = tail call i32 @f2() #2
br label %if.end

if.end:                                           ; preds = %if.else, %if.then
%x.0 = phi i32 [ %call, %if.then ], [ %call1, %if.else ]
tail call void @use(i32 noundef %x.0) #2
ret void
}

The \(\phi\)-function indeed is a optimization result interpreted by the compiler, and by default the compiler won't generate because it requires additional work to compiler.

Who Is Responsible for Optimizing Phi?¶

Short answer is both frontend and llvm optimizer could help to generate \(\phi\) node. The \(\phi\) nodes are typically generated by the LLVM IR compiler (clang or another frontend) when it translates high-level language constructs into LLVM IR. However, it doesn't mean only the compiler frontend could generate \(phi\)-function, indeed, the LLVM IR optimizer could help to generate the \(\phi\) as well.

We use opt to optimize the llvm IR code:

$ opt --version
Homebrew LLVM version 16.0.6
  Optimized build.
  Default target: arm64-apple-darwin21.2.0
  Host CPU: apple-m1
# the -enable-new-pm flag is needed,
# as in my local the new pass manager doesnt work
$ opt -mem2reg --basic-aa -enable-new-pm=0 -S foo.ll -o opted_foo.ll

The output carries the \(\phi\) node, which verifies the llvm IR optimizer could generate \(\phi\) node.

; Function Attrs: noinline nounwind
define void @test(i32 noundef %i) #0 {
entry:
  %tobool = icmp ne i32 %i, 0
  br i1 %tobool, label %if.then, label %if.else

if.then:                                          ; preds = %entry
  %call = call i32 @f1()
  br label %if.end

if.else:                                          ; preds = %entry
  %call1 = call i32 @f2()
  br label %if.end

if.end:                                           ; preds = %if.else, %if.then
  %x.0 = phi i32 [ %call, %if.then ], [ %call1, %if.else ]
  call void @use(i32 noundef %x.0)
  ret void
}

Conclusion¶

The original motivation of this blog was raised because the kaleidoscope creates a \(\phi\) node for its if-then-else condition but the pivot-lang which currently I'm working on doesn't. This inconsistency confused me and urged me to figure it out.

After exploring, I feel it's the compilers' decisions whether generating \(\phi\) in the frontend. For a relative primitive compiler, it could fully rely on the LLVM IR optimizer to generate \(\phi\).