Ch 2 — Building LLVM IR

LLVM Essentials — Sarda & Pandey · pages 54–88

Chapter 2. Building LLVM IR A high level programming language facilitates human interaction with the target machine. Most of the popular high level languages today have certain basic elements such as variables, loops, if-else decision making statements, blocks, functions, and so on. A variable holds value of data types; a basic block gives an idea of the scope of the variable. An if-else decision statement helps in selection of a path of code. A function makes a block of code reusable. High level languages may vary in type checking, type casting, variable declarations, complex data types, and so on. However, almost every other language has the basic building blocks listed earlier in this section. A language may have its own parser which tokenizes the statement and extracts meaningful information such as identifier, its data type; a function name, its declaration, definition and calls; a loop condition, and so on. This meaningful information may be stored in a data structure where the flow of the code can be easily retrieved. Abstract Syntax Tree (AST) is a popular tree representation of the source code. The AST’s can be used for further transformation and analysis. A language parser can be written in various ways with various tools such as lex, yacc, and so on, or can even be handwritten. Writing an efficient parser is an art in itself. But this is not what we intend to cover in this chapter. We would like to focus more on LLVM IR and how a high-level language after parsing can be converted to LLVM IR using LLVM libraries. This chapter will cover how to construct basic working LLVM sample code, which includes the following: Creating an LLVM module Emitting a function in a module Adding a block to a function Emitting a global variable Emitting a return statement Emitting function arguments Emitting a simple arithmetic statement in a basic block Emitting if-else condition IR Emitting LLVM IR for loops

Creating an LLVM module In the previous chapter, we got an idea as to how an LLVM IR looks. In LLVM, a module represents a single unit of code that is to be processed together. An LLVM module class is the top-level container for all other LLVM IR objects. The LLVM module contains global variables, functions, data layout, host triples, and so on. Let’s create a simple LLVM module. LLVM provides Module() constructor for creating a module. The first argument is the name of the module. The second argument is LLVMContext. Let’s get these arguments in the main function and create a module as demonstrated here: static LLVMContext &Context = getGlobalContext(); static Module *ModuleOb = new Module("my compiler", Context);

For these functions to work, we need to include certain header files: #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" using namespace llvm; static LLVMContext &Context = getGlobalContext(); static Module *ModuleOb = new Module("my compiler", Context);

int main(int argc, char *argv[]) { ModuleOb->dump(); return 0;

Put this code in a file, let’s say toy.cpp and compile it: $ clang++ -O3 toy.cpp `llvm-config --cxxflags --ldflags --system-libs -- libs core` -o toy $ ./toy

The output will be as follows: ; ModuleID = 'my compiler'

Emitting a function in a module Now that we have created a module, the next step is to emit a function. LLVM has an IRBuilder class that is used to generate LLVM IR and print it using the dump function of the Module object. LLVM provides the class llvm::Function to create a function and llvm::FunctionType() to associate a return type for the function. Let’s assume that our foo() function returns an integer type.

Function *createFunc(IRBuilder<> &Builder, std::string Name) { FunctionType *funcType = llvm::FunctionType::get(Builder.getInt32Ty(), false); Function *fooFunc = llvm::Function::Create( funcType, llvm::Function::ExternalLinkage, Name, ModuleOb); return fooFunc;

Finally, call function verifyFunction() on fooFunc. This function performs a variety of consistency checks on the generated code, to determine if our compiler is doing everything right. int main(int argc, char *argv[]) { static IRBuilder<> Builder(Context); Function *fooFunc = createFunc(Builder, "foo"); verifyFunction(*fooFunc); ModuleOb->dump(); return 0;

Add the IR/IRBuilder.h, IR/DerivedTypes.h and IR/Verifier.h file in include section. The overall code is as follows: #include "llvm/IR/IRBuilder.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" #include "llvm/IR/Verifier.h" #include <vector> using namespace llvm;

static LLVMContext &Context = getGlobalContext(); static Module *ModuleOb = new Module("my compiler", Context);

int main(int argc, char *argv[]) { static IRBuilder<> Builder(Context); Function *fooFunc = createFunc(Builder, "foo"); verifyFunction(*fooFunc);

    ModuleOb->dump();
    return 0;

Compile the toy.cpp with the same options as stated earlier: $ clang++ -O3 toy.cpp `llvm-config --cxxflags --ldflags --system-libs -- libs core` -o toy

The output will be as follows: $ ./toy ; ModuleID = 'my compiler'

declare i32 @foo()

Adding a block to a function A function consists of basic blocks. A basic block has an entry point. A basic block consists of a number of IR instructions, the last instruction being a terminator instruction. It has single exit point. LLVM provides the BasicBlock class to create and handle basic blocks. A basic block might have an entry point as its label, which indicates where to insert the next instructions. We can use the IRBuilder object to hold these new basic block IR. BasicBlock *createBB(Function *fooFunc, std::string Name) { return BasicBlock::Create(Context, Name, fooFunc);

The overall code is as follows: #include "llvm/IR/IRBuilder.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" #include "llvm/IR/Verifier.h" #include <vector> using namespace llvm;

static LLVMContext &Context = getGlobalContext(); static Module *ModuleOb = new Module("my compiler", Context);

BasicBlock *createBB(Function *fooFunc, std::string Name) { return BasicBlock::Create(Context, Name, fooFunc);

int main(int argc, char *argv[]) { static IRBuilder<> Builder(Context); Function *fooFunc = createFunc(Builder, "foo"); BasicBlock *entry = createBB(fooFunc, "entry"); Builder.SetInsertPoint(entry); verifyFunction(*fooFunc); ModuleOb->dump(); return 0;

Compile the toy.cpp file: $ clang++ -O3 toy.cpp `llvm-config --cxxflags --ldflags --system-libs -- libs core` -o toy

The output will be as follows: ; ModuleID = 'my compiler'

define i32 @foo() { entry:

Emitting a global variable Global variables have visibility of all the functions within a given module. LLVM provides the GlobalVariable class to create global variables and set its properties such as linkage type, alignment, and so on. The Module class has the method getOrInsertGlobal() to create a global variable. It takes two arguments—the first is the name of the variable and the second is the data type of the variable. As global variables are part of a module, we create global variables after creating the module. Insert the following code just after creating the module in toy.cpp: GlobalVariable *createGlob(IRBuilder<> &Builder, std::string Name) { ModuleOb->getOrInsertGlobal(Name, Builder.getInt32Ty()); GlobalVariable *gVar = ModuleOb->getNamedGlobal(Name); gVar->setLinkage(GlobalValue::CommonLinkage); gVar->setAlignment(4); return gVar;

Linkage is what determines if multiple declarations of the same object refer to the same object, or to separate ones. The LLVM reference manual cites the following types of Linkages:

ExternalLinkage Externally visible function.

AvailableExternallyLinkage Available for inspection, not emission.

LinkOnceAnyLinkage Keep one copy of function when linking (inline)

LinkOnceODRLinkage Same, but only replaced by something equivalent.

WeakAnyLinkage Keep one copy of named function when linking (weak)

WeakODRLinkage Same, but only replaced by something equivalent.

AppendingLinkage Special purpose, only applies to global arrays.

InternalLinkage Rename collisions when linking (static functions).

PrivateLinkage Like internal, but omit from symbol table.

ExternalWeakLinkage ExternalWeak linkage description.

CommonLinkage Tentative definitions

Alignment gives information about address alignment. An alignment must be a power of 2. If not specified explicitly, it is set by the target. The maximum alignment is 1 << 29.

The overall code is as follows: #include "llvm/IR/IRBuilder.h" #include "llvm/IR/LLVMContext.h"

#include "llvm/IR/Module.h" #include "llvm/IR/Verifier.h" #include <vector> using namespace llvm;

static LLVMContext &Context = getGlobalContext(); static Module *ModuleOb = new Module("my compiler", Context);

BasicBlock *createBB(Function *fooFunc, std::string Name) { return BasicBlock::Create(Context, Name, fooFunc);

GlobalVariable *createGlob(IRBuilder<> &Builder, std::string Name) { ModuleOb->getOrInsertGlobal(Name, Builder.getInt32Ty()); GlobalVariable *gVar = ModuleOb->getNamedGlobal(Name); gVar->setLinkage(GlobalValue::CommonLinkage); gVar->setAlignment(4); return gVar;

int main(int argc, char *argv[]) { static IRBuilder<> Builder(Context); GlobalVariable *gVar = createGlob(Builder, "x"); Function *fooFunc = createFunc(Builder, "foo"); BasicBlock *entry = createBB(fooFunc, "entry"); Builder.SetInsertPoint(entry); verifyFunction(*fooFunc); ModuleOb->dump(); return 0;

Compile the toy.cpp: $ clang++ -O3 toy.cpp `llvm-config --cxxflags --ldflags --system-libs -- libs core` -o toy

The output will be as follows: ; ModuleID = 'my compiler'

@x = common global i32, align 4

define i32 @foo() { entry:

Emitting a return statement A function might return a value or it may return void. Here in our example, we have defined that our function returns an integer. Let’s assume that our function returns 0. The first step is to get a 0 value, which can be done using the Constant class. Builder.CreateRet(Builder.getInt32(0));

The overall code is as follows: #include "llvm/IR/IRBuilder.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" #include "llvm/IR/Verifier.h" #include <vector> using namespace llvm;

static LLVMContext &Context = getGlobalContext(); static Module *ModuleOb = new Module("my compiler", Context);

BasicBlock *createBB(Function *fooFunc, std::string Name) { return BasicBlock::Create(Context, Name, fooFunc);

int main(int argc, char *argv[]) { static IRBuilder<> Builder(Context); GlobalVariable *gVar = createGlob(Builder, "x"); Function *fooFunc = createFunc(Builder, "foo"); BasicBlock *entry = createBB(fooFunc, "entry"); Builder.SetInsertPoint(entry); Builder.CreateRet(Builder.getInt32(0)); verifyFunction(*fooFunc); ModuleOb->dump(); return 0;

Compile toy.cpp file $ clang++ -O3 toy.cpp `llvm-config --cxxflags --ldflags --system-libs --

libs core` -o toy

The output will be as follows: ; ModuleID = 'my compiler'

@x = common global i32, align 4

define i32 @foo() { entry: ret i32 0

Emitting function arguments A function takes arguments that have their own data type. For simplification, assume that our function has all the arguments of i32 type (integer 32 bit). For example, we will consider that two arguments, a and b, are passed to the function. We will store these two arguments in a vector: static std::vector <std::string> FunArgs; FunArgs.push_back("a"); FunArgs.push_back("b");

The next step is to specify that the function will have two arguments. This can be done by passing the Integer argument to the functiontype. Function *createFunc(IRBuilder<> &Builder, std::string Name) { std::vector<Type *> Integers(FunArgs.size(), Type::getInt32Ty(Context)); FunctionType *funcType = llvm::FunctionType::get(Builder.getInt32Ty(), Integers, false); Function *fooFunc = llvm::Function::Create( funcType, llvm::Function::ExternalLinkage, Name, ModuleOb); return fooFunc;

The last step is to set the names of the function arguments. This can be done by Function argument iterator in a loop, as shown: void setFuncArgs(Function *fooFunc, std::vector<std::string> FunArgs) { unsigned Idx = 0; Function::arg_iterator AI, AE; for (AI = fooFunc->arg_begin(), AE = fooFunc->arg_end(); AI != AE; ++AI, ++Idx) AI->setName(FunArgs[Idx]);

The overall code is as follows: #include "llvm/IR/IRBuilder.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" #include "llvm/IR/Verifier.h" #include <vector> using namespace llvm;

static LLVMContext &Context = getGlobalContext(); static Module *ModuleOb = new Module("my compiler", Context); static std::vector<std::string> FunArgs;

Function *createFunc(IRBuilder<> &Builder, std::string Name) { std::vector<Type *> Integers(FunArgs.size(), Type::getInt32Ty(Context)); FunctionType *funcType = llvm::FunctionType::get(Builder.getInt32Ty(), Integers, false); Function *fooFunc = llvm::Function::Create( funcType, llvm::Function::ExternalLinkage, Name, ModuleOb); return fooFunc;

void setFuncArgs(Function *fooFunc, std::vector<std::string> FunArgs) { unsigned Idx = 0; Function::arg_iterator AI, AE; for (AI = fooFunc->arg_begin(), AE = fooFunc->arg_end(); AI != AE; ++AI, ++Idx) AI->setName(FunArgs[Idx]);

BasicBlock *createBB(Function *fooFunc, std::string Name) { return BasicBlock::Create(Context, Name, fooFunc);

int main(int argc, char *argv[]) { FunArgs.push_back("a"); FunArgs.push_back("b"); static IRBuilder<> Builder(Context); GlobalVariable *gVar = createGlob(Builder, "x"); Function *fooFunc = createFunc(Builder, "foo"); setFuncArgs(fooFunc, FunArgs); BasicBlock *entry = createBB(fooFunc, "entry"); Builder.SetInsertPoint(entry); Builder.CreateRet(Builder.getInt32(0)); verifyFunction(*fooFunc); ModuleOb->dump(); return 0;

Compile the toy.cpp file: $ clang++ -O3 toy.cpp `llvm-config --cxxflags --ldflags --system-libs -- libs core` -o toy

The output will be as follows: ; ModuleID = 'my compiler'

@x = common global i32, align 4

define i32 @foo(i32 %a, i32 %b) { entry: ret i32 0

Emitting a simple arithmetic statement in a basic block A basic block consists of a list of instructions. For example, an instruction can be a simple statement performing tasks based on some simple arithmetic instruction. We will see how the LLVM API can be used to emit arithmetic instructions. For example, if we want to multiply first argument a with integer value 16, we will create a constant integer value 16 with the following API: Value *constant = Builder.getInt32(16);

We already have a from the function argument list: Value *Arg1 = fooFunc->arg_begin();

LLVM provides a rich list of API’s to create binary operations. You can go through the include/llvm/IR/IRBuild.h file for more details on the APIs.

Value *createArith(IRBuilder<> &Builder, Value *L, Value *R) { return Builder.CreateMul(L, R, "multmp");

Note Note that for demo purposes, the preceding function returns multiplication. We leave it to the readers to make this function more flexible to return any binary operations. You can explore more binary operations in include/llvm/IR/IRBuild.h. The whole code now looks as follows: #include "llvm/IR/IRBuilder.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" #include "llvm/IR/Verifier.h" #include <vector> using namespace llvm;

static LLVMContext &Context = getGlobalContext(); static Module *ModuleOb = new Module("my compiler", Context); static std::vector<std::string> FunArgs;

void setFuncArgs(Function *fooFunc, std::vector<std::string> FunArgs) {

    unsigned Idx = 0;
    Function::arg_iterator AI, AE;
    for (AI = fooFunc->arg_begin(), AE = fooFunc->arg_end(); AI != AE;
         ++AI, ++Idx)
      AI->setName(FunArgs[Idx]);

BasicBlock *createBB(Function *fooFunc, std::string Name) { return BasicBlock::Create(Context, Name, fooFunc);

Value *createArith(IRBuilder<> &Builder, Value *L, Value *R) { return Builder.CreateMul(L, R, "multmp");

int main(int argc, char *argv[]) { FunArgs.push_back("a"); FunArgs.push_back("b"); static IRBuilder<> Builder(Context); GlobalVariable *gVar = createGlob(Builder, "x"); Function *fooFunc = createFunc(Builder, "foo"); setFuncArgs(fooFunc, FunArgs); BasicBlock *entry = createBB(fooFunc, "entry"); Builder.SetInsertPoint(entry); Value *Arg1 = fooFunc->arg_begin(); Value *constant = Builder.getInt32(16); Value *val = createArith(Builder, Arg1, constant); Builder.CreateRet(val); verifyFunction(*fooFunc); ModuleOb->dump(); return 0;

Compile the following program: $ clang++ -O3 toy.cpp `llvm-config --cxxflags --ldflags --system-libs -- libs core` -o toy

The output will be as follows: ; ModuleID = 'my compiler'

@x = common global i32, align 4

define i32 @foo(i32 %a, i32 %b) { entry: %multmp = mul i32 %a, 16 ret i32 %multmp

Did you notice the return value? We returned the multiplication instead of constant 0.

Emitting if-else condition IR An if-else statement has a condition expression and two code paths to execute, depending on the condition evaluating to true or false. The condition expression is generally a comparison statement. Let’s emit a condition statement at the start of the block. For example, let the condition be like a<100. Value *val2 = Builder.getInt32(100); Value *Compare = Builder.CreateICmpULT(val, val2, "cmptmp");

On compilation, we get following output: ; ModuleID = 'my compiler'

@x = common global i32, align 4

define i32 @foo(i32 %a, i32 %b) { entry: %multmp = mul i32 %a, 16 %cmptmp = icmp ult i32 %multmp, 100

    ret i32 %multmp

The next step is to define the then and else block expressions, which will be executed depending on the result of condition expression “booltmp“. Here, an important concept of PHI instruction comes into picture. A phi instruction takes various values coming from different basic blocks and decides which value to assign depending on the condition expression. Two separate basic blocks “ThenBB” and “ElseBB” will be created. Let’s say that the then expression is ‘add 1 to a’ and else expression is ‘add 2 to a’. A third block will represent the merge block, which contains the instructions to be executed at the merging of the then and else blocks. These blocks need to be pushed into the function foo(). For reusability, we create BasicBlock and Value containers as follows: typedef SmallVector<BasicBlock *, 16> BBList; typedef SmallVector<Value *, 16> ValList;

Note Note that SmallVector<> is vector container wrapper provided by LLVM for simplicity. We also push some of the values in a Value* list to process them in the if-else block, as follows: Value *Condtn = Builder.CreateICmpNE(Compare, Builder.getInt32(0), "ifcond"); ValList VL; VL.push_back(Condtn); VL.push_back(Arg1);

We create three basic blocks and push them in container, as follows:
    BasicBlock *ThenBB = createBB(fooFunc, "then");
    BasicBlock *ElseBB = createBB(fooFunc, "else");
    BasicBlock *MergeBB = createBB(fooFunc, "ifcont");
    BBList List;
    List.push_back(ThenBB);
    List.push_back(ElseBB);
    List.push_back(MergeBB);

We finally create a function to emit the if-else block: Value *createIfElse(IRBuilder<> &Builder, BBList List, ValList VL) { Value *Condtn = VL[0]; Value *Arg1 = VL[1]; BasicBlock *ThenBB = List[0]; BasicBlock *ElseBB = List[1]; BasicBlock *MergeBB = List[2]; Builder.CreateCondBr(Condtn, ThenBB, ElseBB);

Builder.SetInsertPoint(ThenBB); Value *ThenVal = Builder.CreateAdd(Arg1, Builder.getInt32(1), "thenaddtmp"); Builder.CreateBr(MergeBB);

Builder.SetInsertPoint(ElseBB); Value *ElseVal = Builder.CreateAdd(Arg1, Builder.getInt32(2), "elseaddtmp"); Builder.CreateBr(MergeBB);

unsigned PhiBBSize = List.size() - 1; Builder.SetInsertPoint(MergeBB); PHINode *Phi = Builder.CreatePHI(Type::getInt32Ty(getGlobalContext()), PhiBBSize, "iftmp"); Phi->addIncoming(ThenVal, ThenBB); Phi->addIncoming(ElseVal, ElseBB);

    return Phi;

Overall code: #include "llvm/IR/IRBuilder.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" #include "llvm/IR/Verifier.h" #include <vector> using namespace llvm;

static LLVMContext &Context = getGlobalContext(); static Module *ModuleOb = new Module("my compiler", Context); static std::vector<std::string> FunArgs; typedef SmallVector<BasicBlock *, 16> BBList; typedef SmallVector<Value *, 16> ValList;

Function *createFunc(IRBuilder<> &Builder, std::string Name) { std::vector<Type *> Integers(FunArgs.size(), Type::getInt32Ty(Context));

    FunctionType *funcType =
        llvm::FunctionType::get(Builder.getInt32Ty(), Integers, false);
    Function *fooFunc = llvm::Function::Create(
        funcType, llvm::Function::ExternalLinkage, Name, ModuleOb);
    return fooFunc;

void setFuncArgs(Function *fooFunc, std::vector<std::string> FunArgs) {

    unsigned Idx = 0;
    Function::arg_iterator AI, AE;
    for (AI = fooFunc->arg_begin(), AE = fooFunc->arg_end(); AI != AE;
         ++AI, ++Idx)
      AI->setName(FunArgs[Idx]);

BasicBlock *createBB(Function *fooFunc, std::string Name) { return BasicBlock::Create(Context, Name, fooFunc);

Value *createArith(IRBuilder<> &Builder, Value *L, Value *R) { return Builder.CreateMul(L, R, "multmp");

Value *createIfElse(IRBuilder<> &Builder, BBList List, ValList VL) { Value *Condtn = VL[0]; Value *Arg1 = VL[1]; BasicBlock *ThenBB = List[0]; BasicBlock *ElseBB = List[1]; BasicBlock *MergeBB = List[2]; Builder.CreateCondBr(Condtn, ThenBB, ElseBB);

Builder.SetInsertPoint(ThenBB); Value *ThenVal = Builder.CreateAdd(Arg1, Builder.getInt32(1), "thenaddtmp"); Builder.CreateBr(MergeBB);

Builder.SetInsertPoint(ElseBB); Value *ElseVal = Builder.CreateAdd(Arg1, Builder.getInt32(2), "elseaddtmp"); Builder.CreateBr(MergeBB);

unsigned PhiBBSize = List.size() - 1; Builder.SetInsertPoint(MergeBB); PHINode *Phi = Builder.CreatePHI(Type::getInt32Ty(getGlobalContext()), PhiBBSize, "iftmp"); PhiBBSize, "iftmp"); Phi->addIncoming(ThenVal, ThenBB);

    Phi->addIncoming(ElseVal, ElseBB);

    return Phi;

int main(int argc, char *argv[]) { FunArgs.push_back("a"); FunArgs.push_back("b"); static IRBuilder<> Builder(Context); GlobalVariable *gVar = createGlob(Builder, "x"); Function *fooFunc = createFunc(Builder, "foo"); setFuncArgs(fooFunc, FunArgs); BasicBlock *entry = createBB(fooFunc, "entry"); Builder.SetInsertPoint(entry); Value *Arg1 = fooFunc->arg_begin(); Value *constant = Builder.getInt32(16); Value *val = createArith(Builder, Arg1, constant);

Value *val2 = Builder.getInt32(100); Value *Compare = Builder.CreateICmpULT(val, val2, "cmptmp"); Value *Condtn = Builder.CreateICmpNE(Compare, Builder.getInt32(0), "ifcond");

    ValList VL;
    VL.push_back(Condtn);
    VL.push_back(Arg1);

    BasicBlock *ThenBB = createBB(fooFunc, "then");
    BasicBlock *ElseBB = createBB(fooFunc, "else");
    BasicBlock *MergeBB = createBB(fooFunc, "ifcont");
    BBList List;
    List.push_back(ThenBB);
    List.push_back(ElseBB);
    List.push_back(MergeBB);

    Value *v = createIfElse(Builder, List, VL);

    Builder.CreateRet(v);
    verifyFunction(*fooFunc);
    ModuleOb->dump();
    return 0;

After compiling, the output looks like the following: ; ModuleID = 'my compiler'

@x = common global i32, align 4

define i32 @foo(i32 %a, i32 %b) { entry: %multmp = mul i32 %a, 16 %cmptmp = icmp ult i32 %multmp, 100 %ifcond = icmp ne i1 %cmptmp, i32 0 br i1 %ifcond, label %then, label %else

then: ; preds = %entry %thenaddtmp = add i32 %a, 1 br label %ifcont

else: ; preds = %entry %elseaddtmp = add i32 %a, 2 br label %ifcont

ifcont: ; preds = %else, %then %iftmp = phi i32 [ %thenaddtmp, %then ], [ %elseaddtmp, %else ] ret i32 %iftmp

Emitting LLVM IR for loop Similar to the if-else statement, loops can also be emitted using LLVM API’s, with slight modification of the code. For example, we want to have LLVM IR for the following Loops: for(i=1; i< b; i++) {body}

The loop has induction variable i, which has some initial value that updates after each iteration. The induction variable is updated after each iteration by a step value that is 1 in the preceding example. Then there is a loop ending condition. In the preceding example, ‘i=1‘ is the initial value, ‘i<b‘ is the end condition of the loop, and ‘i++‘ is the step value by which the induction variable ‘i‘ is incremented after every iteration of the loop. Before writing a function to create a loop, some Value and BasicBlock need to be pushed into a list, as follows: Function::arg_iterator AI = fooFunc->arg_begin(); Value *Arg1 = AI++; Value *Arg2 = AI; Value *constant = Builder.getInt32(16); Value *val = createArith(Builder, Arg1, constant); ValList VL; VL.push_back(Arg1);

BBList List; BasicBlock *LoopBB = createBB(fooFunc, "loop"); BasicBlock *AfterBB = createBB(fooFunc, "afterloop"); List.push_back(LoopBB); List.push_back(AfterBB);

Value *StartVal = Builder.getInt32(1);

Let’s create a function for the emitting loop: PHINode *createLoop(IRBuilder<> &Builder, BBList List, ValList VL, Value *StartVal, Value *EndVal) { BasicBlock *PreheaderBB = Builder.GetInsertBlock(); Value *val = VL[0]; BasicBlock *LoopBB = List[0]; Builder.CreateBr(LoopBB); Builder.SetInsertPoint(LoopBB); PHINode *IndVar = Builder.CreatePHI(Type::getInt32Ty(Context), 2, "i"); IndVar->addIncoming(StartVal, PreheaderBB); Builder.CreateAdd(val, Builder.getInt32(5), "addtmp"); Value *StepVal = Builder.getInt32(1); Value *NextVal = Builder.CreateAdd(IndVar, StepVal, "nextval"); Value *EndCond = Builder.CreateICmpULT(IndVar, EndVal, "endcond"); EndCond = Builder.CreateICmpNE(EndCond, Builder.getInt32(0), "loopcond"); BasicBlock *LoopEndBB = Builder.GetInsertBlock(); BasicBlock *AfterBB = List[1]; Builder.CreateCondBr(EndCond, LoopBB, AfterBB); Builder.SetInsertPoint(AfterBB); IndVar->addIncoming(NextVal, LoopEndBB);

    return IndVar;

Consider the following lines of code: IndVar->addIncoming(StartVal, PreheaderBB);… IndVar->addIncoming(NextVal, LoopEndBB);

IndVar is a PHI node, which has two incoming values from two blocks—startval from the Preheader block (i=1), and Nextval from the LoopEnd block. The overall code is as follows: #include "llvm/IR/IRBuilder.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" #include "llvm/IR/Verifier.h" #include <vector> using namespace llvm;

typedef SmallVector<BasicBlock *, 16> BBList; typedef SmallVector<Value *, 16> ValList;

static LLVMContext &Context = getGlobalContext(); static Module *ModuleOb = new Module("my compiler", Context); static std::vector<std::string> FunArgs;

void setFuncArgs(Function *fooFunc, std::vector<std::string> FunArgs) {

    unsigned Idx = 0;
    Function::arg_iterator AI, AE;
    for (AI = fooFunc->arg_begin(), AE = fooFunc->arg_end(); AI != AE;
         ++AI, ++Idx)
      AI->setName(FunArgs[Idx]);

BasicBlock *createBB(Function *fooFunc, std::string Name) { return BasicBlock::Create(Context, Name, fooFunc);

Value *createArith(IRBuilder<> &Builder, Value *L, Value *R) { return Builder.CreateMul(L, R, "multmp");

Value *createLoop(IRBuilder<> &Builder, BBList List, ValList VL, Value *StartVal, Value *EndVal) { BasicBlock *PreheaderBB = Builder.GetInsertBlock(); Value *val = VL[0]; BasicBlock *LoopBB = List[0]; Builder.CreateBr(LoopBB); Builder.SetInsertPoint(LoopBB); PHINode *IndVar = Builder.CreatePHI(Type::getInt32Ty(Context), 2, "i"); IndVar->addIncoming(StartVal, PreheaderBB); Value *Add = Builder.CreateAdd(val, Builder.getInt32(5), "addtmp"); Value *StepVal = Builder.getInt32(1); Value *NextVal = Builder.CreateAdd(IndVar, StepVal, "nextval"); Value *EndCond = Builder.CreateICmpULT(IndVar, EndVal, "endcond"); EndCond = Builder.CreateICmpNE(EndCond, Builder.getInt32(0), "loopcond"); BasicBlock *LoopEndBB = Builder.GetInsertBlock(); BasicBlock *AfterBB = List[1]; Builder.CreateCondBr(EndCond, LoopBB, AfterBB); Builder.SetInsertPoint(AfterBB); IndVar->addIncoming(NextVal, LoopEndBB); return Add;

int main(int argc, char *argv[]) { FunArgs.push_back("a"); FunArgs.push_back("b"); static IRBuilder<> Builder(Context); GlobalVariable *gVar = createGlob(Builder, "x"); Function *fooFunc = createFunc(Builder, "foo"); setFuncArgs(fooFunc, FunArgs); BasicBlock *entry = createBB(fooFunc, "entry"); Builder.SetInsertPoint(entry); Function::arg_iterator AI = fooFunc->arg_begin(); Value *Arg1 = AI++; Value *Arg2 = AI; Value *constant = Builder.getInt32(16); Value *val = createArith(Builder, Arg1, constant); ValList VL; VL.push_back(Arg1);

BBList List; BasicBlock *LoopBB = createBB(fooFunc, "loop"); BasicBlock *AfterBB = createBB(fooFunc, "afterloop"); List.push_back(LoopBB); List.push_back(AfterBB);

Value *StartVal = Builder.getInt32(1); Value *Res = createLoop(Builder, List, VL, StartVal, Arg2);

Builder.CreateRet(Res); verifyFunction(*fooFunc); ModuleOb->dump(); return 0;

After compiling the program, we get the following output: ; ModuleID = 'my compiler'

@x = common global i32, align 4

define i32 @foo(i32 %a, i32 %b) { entry: %multmp = mul i32 %a, 16 br label %loop

loop: ; preds = %loop, %entry %i = phi i32 [ 1, %entry ], [ %nextval, %loop ] %addtmp = add i32 %a, 5 %nextval = add i32 %i, 1 %endcond = icmp ult i32 %i, %b %loopcond = icmp ne i1 %endcond, i32 0 br i1 %loopcond, label %loop, label %afterloop

afterloop: ; preds = %loop ret i32 %addtmp

Summary In this chapter, you learned how to create simple LLVM IR using rich libraries provided by LLVM. Remember that LLVM IR is an intermediate representation. The high-level programming languages are converted to LLVM IR using the custom parser, which breaks down the code into atomic pieces such as variables, functions, function return type, function arguments, if-else conditions, loops, pointers, array, and so on. These atomic elements can be stored into custom data structures and then those data structures can be used to emit LLVM IR, as demonstrated in this chapter. In the parser phase, syntactic analysis can be done, while lexical analysis and type checking can be done in an intermediate stage after parsing and before emitting IR. In practical usage, one would hardly find the IR being emitted in a hard-coded way as demonstrated in this chapter. Instead, a language is parsed and represented in an Abstract Syntax Tree. The tree is then used to emit LLVM IR with the help of the LLVM library, as shown earlier. The LLVM community has provided an excellent tutorial for writing a parser and emitting LLVM IR. You can visit http://llvm.org/docs/tutorial/ for the same. In the next chapter, we will see how to emit some complex data structures such as array, pointers. Also, we will go through some examples from Clang, the frontend for C/C++, and understand how semantic Analysis is done.

← / → change chapter. Esc returns to the main menu. Click a figure to zoom.