In any programming language, executing a statement based on certain conditions gives a very powerful advantage to the language. The if/then/else constructs provide the capability to alter the control flow of a program, based on certain conditions. The condition is present in an if construct. If the condition is true, the expression following the then construct is executed. If it is false, the expression following the else construct is executed. This recipe demonstrates a basic infrastructure to parse and generate code for the if/then/else construct.
The TOY language for if/then/else can be defined as:
if x < 2 then x + y else x - y
For checking a condition, a comparison operator is required. A simple less than operator, <, will serve the purpose. To handle <, precedence needs to be defined in the init_precedence() function, as shown here:
static void init_precedence() {
Operator_Precedence['<'] = 0;
…
…
}Also, the codegen() function for binary expressions needs to be included for <:
Value* BinaryAST::Codegen() {
…
…
…
case '<' :
L = Builder.CreateICmpULT(L, R, "cmptmp");
return Builder.CreateZExt(L, Type::getInt32Ty(getGlobalContext()),
"booltmp");…
…
}Now, the LLVM IR will generate a comparison instruction and a Boolean instruction as a result of the comparison, which will be used to determine where the control of the program will flow. It's time to handle the if/then/else paradigm now.
Do the following steps:
- The lexer in the
toy.cppfile has to be extended to handle theif/then/elseconstructs. This can be done by appending a token for this in theenumof tokens:enum Token_Type{ … … IF_TOKEN, THEN_TOKEN, ELSE_TOKEN } - The next step is to append the entries for these tokens in the
get_token()function, where we match strings and return the appropriate tokens:static int get_token() { … … … if (Identifier_string == "def") return DEF_TOKEN; if(Identifier_string == "if") return IF_TOKEN; if(Identifier_string == "then") return THEN_TOKEN; if(Identifier_string == "else") return ELSE_TOKEN; … … } - Then we define an AST node in the
toy.cppfile:class ExprIfAST : public BaseAST { BaseAST *Cond, *Then, *Else; public: ExprIfAST(BaseAST *cond, BaseAST *then, BaseAST * else_st) : Cond(cond), Then(then), Else(else_st) {} Value *Codegen() override; }; - The next step is to define the parsing logic for the
if/then/elseconstructs:static BaseAST *If_parser() { next_token(); BaseAST *Cond = expression_parser(); if (!Cond) return 0; if (Current_token != THEN_TOKEN) return 0; next_token(); BaseAST *Then = expression_parser(); if (Then == 0) return 0; if (Current_token != ELSE_TOKEN) return 0; next_token(); BaseAST *Else = expression_parser(); if (!Else) return 0; return new ExprIfAST(Cond, Then, Else); }The parser logic is simple: first, the
iftoken is searched for and the expression following it is parsed for the condition. After that, thethentoken is identified and the true condition expression is parsed. Then theelsetoken is searched for and the false condition expression is parsed. - Next we hook up the previously defined function with
Base_Parser():static BaseAST* Base_Parser() { switch(Current_token) { … … … case IF_TOKEN : return If_parser(); … } - Now that the AST of
if/then/elseis filled with the expression by the parser, it's time to generate the LLVM IR for the conditional paradigm. Let's define theCodegen()function:Value *ExprIfAST::Codegen() { Value *Condtn = Cond->Codegen(); if (Condtn == 0) return 0; Condtn = Builder.CreateICmpNE( Condtn, Builder.getInt32(0), "ifcond"); Function *TheFunc = Builder.GetInsertBlock()->getParent(); BasicBlock *ThenBB = BasicBlock::Create(getGlobalContext(), "then", TheFunc); BasicBlock *ElseBB = BasicBlock::Create(getGlobalContext(), "else"); BasicBlock *MergeBB = BasicBlock::Create(getGlobalContext(), "ifcont"); Builder.CreateCondBr(Condtn, ThenBB, ElseBB); Builder.SetInsertPoint(ThenBB); Value *ThenVal = Then->Codegen(); if (ThenVal == 0) return 0; Builder.CreateBr(MergeBB); ThenBB = Builder.GetInsertBlock(); TheFunc->getBasicBlockList().push_back(ElseBB); Builder.SetInsertPoint(ElseBB); Value *ElseVal = Else->Codegen(); if (ElseVal == 0) return 0; Builder.CreateBr(MergeBB); ElseBB = Builder.GetInsertBlock(); TheFunc->getBasicBlockList().push_back(MergeBB); Builder.SetInsertPoint(MergeBB); PHINode *Phi = Builder.CreatePHI(Type::getInt32Ty(getGlobalContext()), 2, "iftmp"); Phi->addIncoming(ThenVal, ThenBB); Phi->addIncoming(ElseVal, ElseBB); return Phi; }
Now that we are ready with the code, let's compile and run it on a sample program containing the if/then/else constructs.
Do the following steps:
- Compile the
toy.cppfile:$ g++ -g toy.cpp `llvm-config --cxxflags --ldflags --system-libs --libs core ` -O3 -o toy - Open an example file:
$ vi example - Write the following
if/then/elsecode in the example file:def fib(x) if x < 3 then 1 Else fib(x-1)+fib(x-2); - Compile the example file with the TOY compiler:
$ ./toy example
The LLVM IR generated for the if/then/else code will look like this:
; ModuleID = 'my compiler'
target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128"
define i32 @fib(i32 %x) {
entry:
%cmptmp = icmp ult i32 %x, 3
br i1 %cmptmp, label %ifcont, label %else
else: ; preds = %entry
%subtmp = add i32 %x, -1
%calltmp = call i32 @fib(i32 %subtmp)
%subtmp1 = add i32 %x, -2
%calltmp2 = call i32 @fib(i32 %subtmp1)
%addtmp = add i32 %calltmp2, %calltmp
br label %ifcont
ifcont: ; preds = %entry, %else
%iftmp = phi i32 [ %addtmp, %else ], [ 1, %entry ]
ret i32 %iftmp
}Here's what the output looks like:
The parser identifies the if/then/else constructs and the statements that are to be executed in true and false conditions, and stores them in the AST. The code generator then converts the AST into LLVM IR, where the condition statement is generated. IR is generated for true as well as false conditions. Depending on the state of the condition variable, the appropriate statement is executed at runtime.
- For a detailed example on how an
if elsestatement is handled in C++ by Clang, refer to http://clang.llvm.org/doxygen/classclang_1_1IfStmt.html.