Decaf 编译器代码生成

记录一下使用 llvm api 实现 Decaf 编译器 codegen 过程中的代码片段以及一些基础语法结构实现过程。

Int 与 Bool

llvm 里面 Bool 类型其实也是一个 Integer，只不过长度为 1bit.
例如如下代码可以判断 xxxx 是否为 bool 变量。

1 2	`if (xxxx->getType()->isIntegerTy() && xxxx->getType()->getIntegerBitWidth() == 1) ...`

变量的定义与初始化

局部变量

1	`llvm::Value * variable = Builder.CreateAlloca(getLLVMType(getType()), 0, getName());`

全局变量

1 2	`new llvm::GlobalVariable(*TheModule, ty, false, llvm::GlobalVariable::CommonLinkage, decafGetInitalizer(ty), Name);`

CreateAlloca 与 GlobalVariable 申请变量，返回的是变量的指针，处理这些变量时，需要用 load 和 store 来将这些变量的值载入或保存。

注意，llvm 中函数的参数 llvm::Argument的类型是真实类型，不是一个指针，不能赋值（store），所以在最好在函数入口时将参数转存到局部变量。

数组的定义与引用

// 定义一个全局数组
llvm::ArrayType * arrayType = llvm::ArrayType::get(ty, field_size->getArraySize());
llvm::Constant  *  initializer = llvm::ConstantAggregateZero::get(arrayType);
llvm::Value * arr = llvm::GlobalVariable(*TheModule, arrayType, false, llvm::GlobalVariable::CommonLinkage, initializer, Name);

// 引用数组
llvm::Value * lvalue = Builder.CreateGEP(arr, {Builder.getInt32(0), idx}, "arr"); //idx's type: llvm::Value *
Builder.CreateStore(Builder.getInt32(0), lvalue); // arr[idx] = 0

CreateGEP 生成的是 getelementptr 指令，这个指令有两个 index，很容易让人误解。这是一个地址计算指令，它不仅能计算数组某元素的偏移，还可以计算结构体中某字段的偏移。

第一个 index 是传入的顶层指针作为数组的 index

第二个 index 是单个数据类型内部的偏移 index

例如下面这段代码

struct S{
int a;
int b;
}

S * p = new S();
p[0].a = 1

p 是一个指针，可以当作数组索引，该索引就是 index1；p 指向的结构体是一个 Struct，内部又可以索引（索引a或b字段），这就是第二个索引。

用 CreateGEP 计算数组中某个元素的地址，只需要将第一个索引设置为0，第二个索引设置为真实下标即可，也就是传入 {Builder.getInt32(0), idx}

函数

llvm 中定义函数签名与定义函数代码的过程是分开的，所以函数签名定义后，并不需要立即实现，并且可以在链接阶段静态链接到其它的库。

声名函数

llvm::Value * codegen() {
		// codegen for method declare
		llvm::Type * returnTy;
		std::vector<llvm::Type *> args;
		list<decafAST *> argumentList;
		for (auto t : argumentList) { // 这个阶段只需要指出函数参数的类型即可
			args.push_back(getLLVMType(t->getType()));
		}
		returnTy = getLLVMType(ReturnType->getType());
		declare = llvm::Function::Create(
			llvm::FunctionType::get(returnTy, args, false),
			llvm::Function::ExternalLinkage,
			Name,
			TheModule);
		// 给参数设置符号名
		unsigned int idx = 0;
		auto arg_iter = argumentList.begin();
		for (auto & arg : declare->args()) {
			VarDefAST * ty = (VarDefAST *) *arg_iter++;
			arg.setName(ty->getName());
		}

		symbol_enter(Name, SYM_FUNCTION, declare);
		return declare;
	}

生成函数代码

llvm::Value * codegen_body() {
    // codegen for method body..
    llvm::BasicBlock * BB = llvm::BasicBlock::Create(TheContext, "entry", declare);
    Builder.SetInsertPoint(BB);

    // 将参数插入到符号表中
    scope_enter();
    for (auto & Arg : declare->args()) {
        llvm::Value * va_arg = &Arg;
        llvm::Value * alloc = Builder.CreateAlloca(va_arg->getType(), 0, va_arg->getName());
        Builder.CreateStore(va_arg, alloc);
        symbol_enter(Arg.getName().str(), SYM_VAR, alloc);
    }
    
    // 生成函数块的代码
    Block->codegen();
    
    // 检查函数基本块是否正常返回
    for (auto & bb : declare->getBasicBlockList()) {
        llvm::Instruction *Terminator = bb.getTerminator();
        if (!Terminator) {
            llvm::Type * ty = declare->getReturnType();
            Builder.SetInsertPoint(&bb);
            if (ty->isVoidTy()){
                Builder.CreateRetVoid();
            }else if(ty->isIntegerTy()) {
                if(ty->getIntegerBitWidth() == 1)
                    Builder.CreateRet(Builder.getInt1(0));
                else
                    Builder.CreateRet(Builder.getInt32(0));
            }
        }
    }
    
    scope_leave();
    llvm::verifyFunction(*declare);
    return nullptr;
}

布尔表达式短路

a && b

若 a 为 false，则不执行 b，返回 a 的值，否则返回 b 的值。

a || b

若 a 为 false，则执行 b，返回 b 的值，否则返回 a 的值。

这种实现需要手动插入基本块和 PHI 节点，如下为 && 的实现代码。

llvm::BasicBlock * bbori = Builder.GetInsertBlock();
llvm::Function   * func  = bbori->getParent();
llvm::BasicBlock * bb1   = llvm::BasicBlock::Create(TheContext, "And1", func);
llvm::BasicBlock * bb2   = llvm::BasicBlock::Create(TheContext, "AndEnd", func);
llvm::BasicBlock * bbcur = nullptr;
Builder.CreateCondBr(value1, bb1, bb2);
Builder.SetInsertPoint(bb1);
value2 = RightExpr->codegen();
bbcur  = Builder.GetInsertBlock(); // The RHS may create new BBs. 
Builder.CreateBr(bb2);
Builder.SetInsertPoint(bb2);

llvm::PHINode * node = Builder.CreatePHI(getLLVMType(boolTy), 2, "phiAnd");
node->addIncoming(value1, bbori);   // from original bb.
node->addIncoming(value2, bbcur);   // from and 2 bb.
return node;

如下为 || 的实现代码

llvm::BasicBlock * bbori = Builder.GetInsertBlock();
llvm::Function   * func  = bbori->getParent();
llvm::BasicBlock * bb1   = llvm::BasicBlock::Create(TheContext, "Or1", func);
llvm::BasicBlock * bb2   = llvm::BasicBlock::Create(TheContext, "OrEnd", func);
llvm::BasicBlock * bbcur = nullptr;

Builder.CreateCondBr(value1, bb2, bb1);
Builder.SetInsertPoint(bb1);
value2 = RightExpr->codegen();
bbcur  = Builder.GetInsertBlock(); // The RHS may create new BBs. 
Builder.CreateBr(bb2);
Builder.SetInsertPoint(bb2);

llvm::PHINode * node = Builder.CreatePHI(getLLVMType(boolTy), 2, "phiOR");
node->addIncoming(value1, bbori); // from original bb.
node->addIncoming(value2, bbcur); // from and 2 bb.

return node;

调试过程中发现一个问题，即 a && b || c 这样的表达式会出现问题，这是因为先计算 a，创建新的BB（bb1）来放计算 b || c 的代码，而 b || c 又会创建新的BB，addIncoming( , bb1) 这样写就会出问题，因为当前Basic Block 已经不是 bb1 。所以，我在生成 && / ||运算符右侧表达式后重新获取当前 BB 。

If 语句

If 语句的实现要创建3个基本块，ifTrue, ifFalse, ifCont 。 ifCont 就是其余两个基本块的交汇基本块。

llvm::Value * codegen() {
    llvm::Value      * cond = ConditionExpr->codegen();
    llvm::BasicBlock * BBoriginal = Builder.GetInsertBlock();
    llvm::Function   * func    = BBoriginal->getParent();
    llvm::BasicBlock * BBTrue  = llvm::BasicBlock::Create(TheContext, "IfTrue", func);
    llvm::BasicBlock * BBFalse = llvm::BasicBlock::Create(TheContext, "IfFalse", func);
    llvm::BasicBlock * BBCont  = llvm::BasicBlock::Create(TheContext, "IfCont", func);
    Builder.CreateCondBr(cond, BBTrue, BBFalse);
    Builder.SetInsertPoint(BBTrue);
    IfBlock->codegen();
    
    // 检查基本块是否有 ret 指令，如果没有才创建 br 跳转到交汇基本块；如果有 ret，则 br 是 unreachable ，没有意义，而且还会导致 llvm 变量序号计算出错.
    if(!Builder.GetInsertBlock()->getTerminator())
        Builder.CreateBr(BBCont);

    Builder.SetInsertPoint(BBFalse);
    if (ElseBlock) ElseBlock->codegen();
	
    // 同上
    if(!Builder.GetInsertBlock()->getTerminator())
        Builder.CreateBr(BBCont);

    Builder.SetInsertPoint(BBCont);
    return nullptr;
}

while 语句

for/while，有两种语法很蛋疼，分别是 break 和 continue

为了实现这两种语法的功能，我们需要将循环开始（条件判断）、循环结束的基本块都添加到符号表中，方便索引。要实现嵌套循环，在 while/for 循环代码生成阶段，我不得不在符号表中创建一个新的 scope。

llvm::Value * codegen() {
		llvm::BasicBlock * BBori = Builder.GetInsertBlock();
		llvm::Function   * func = BBori->getParent();
		llvm::BasicBlock * BBwhileStart = llvm::BasicBlock::Create(TheContext, "whileStart", func); // Create a BB for 'continue'
		llvm::BasicBlock * BBwhileBody  = llvm::BasicBlock::Create(TheContext, "whileBody" , func);
		llvm::BasicBlock * BBwhileEnd   = llvm::BasicBlock::Create(TheContext, "whileEnd"  , func);
		
    	scope_enter(); // 创建新的 scope
		symbol_enter("LoopStart", SYM_BB, BBwhileStart);  //  continue;
		symbol_enter("LoopEnd",   SYM_BB, BBwhileEnd); // break;
    	Builder.CreateBr(BBwhileStart); 
    	// step 1 条件验证
		Builder.SetInsertPoint(BBwhileStart); //BBori -> BBwhileStart
		llvm::Value * cond = ConditionExpr->codegen();
		Builder.CreateCondBr(cond, BBwhileBody, BBwhileEnd);
    
    	// step 2 循环体代码生成
		Builder.SetInsertPoint(BBwhileBody);
		WhileBlock->codegen();
		Builder.CreateBr(BBwhileStart);
		Builder.SetInsertPoint(BBwhileEnd); 
		scope_leave(); // 退出当前 scope，当前循环的 LoopStart 和 LoopEnd 符号删除..
		return nullptr;
}

for 循环

for 循环稍微麻烦一点，大致可以分为 4 个阶段

第一个阶段，初始化变量

第二个阶段，循环条件验证

第三个阶段，循环体代码生成

第四个阶段，自增代码生成

llvm::Value * codegen() {
    llvm::Function * func = Builder.GetInsertBlock()->getParent();
    llvm::BasicBlock * BBForCond = llvm::BasicBlock::Create(TheContext, "BBForCond", func);
    llvm::BasicBlock * BBForLA   = llvm::BasicBlock::Create(TheContext, "BBForLA", func);
    llvm::BasicBlock * BBForBody = llvm::BasicBlock::Create(TheContext, "BBForBody", func);
    llvm::BasicBlock * BBForEnd  = llvm::BasicBlock::Create(TheContext, "BBForEnd", func);
    
    scope_enter();
    symbol_enter("LoopStart", SYM_BB, BBForLA); // continue
    symbol_enter("LoopEnd", SYM_BB, BBForEnd); // break
    // step 1
    PreAssignList->codegen();
    Builder.CreateBr(BBForCond);
    
    // step 2
    Builder.SetInsertPoint(BBForCond);
    llvm::Value * cond = Condition->codegen();
    Builder.CreateCondBr(cond, BBForBody, BBForEnd);
    
    // step 3
    Builder.SetInsertPoint(BBForBody);
    ForBlock->codegen();
    if(!Builder.GetInsertBlock()->getTerminator())
        Builder.CreateBr(BBForLA);
    
    // step 4
    Builder.SetInsertPoint(BBForLA);
    LoopAssignList->codegen();
    Builder.CreateBr(BBForCond);
    Builder.SetInsertPoint(BBForEnd);
    
    scope_leave();
    return nullptr;
}

debug

llvm ir 的 api 每个类有一个成员函数 dump() , 可以输出当前对象代表的 ir 文本..

compiler

homework llvm

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

o-llvm: Control Flow Flattening Previous

Exercise:Recognize hand-written digits Next

Decaf codegen based on LLVM