Skip to content

实验三代码生成

Jump to bottom
aySun edited this page Apr 20, 2023 · 5 revisions

SYsU-lang：sysu-generator实验指导

写在前面

这些材料可能会帮助同学们顺利完成本实验：

  • LLVM IR的形式：这部分可以帮助同学们理解 LLVM IR 的具体含义，理解一条 IR 指令的具体意义；同时对自己手动生成 IR 的同学而言，这是一个非常必要的知识。
  • 使用LLVM生成IR，作为一个生成基础 IR 的代码实例，该教程涉及了简单的二元表达式、函数声明（定义）、函数调用以及 if-else 分支的 IR 的生成。
  • 本页面的生成IR章节介绍了使用IRBuilder来生成IR的基本方法。

实验要求

本实验要求同学们根据sysu-parser或clang -cc1 -ast-dump=json生成的语法树生成LLVM IR，为了更加顺利的进行实验，建议同学们以clang -cc1 -O0 -S -emit-llvm生成的IR作为参考。先举个例子。

int main(){
    return 3;
}

上面这段源代码使用clang -cc1 -ast-dump=json生成的json格式的语法树如下。

{
  "id": "0x2356578",
  "kind": "TranslationUnitDecl",
  "loc": {},
  "range": {
    "begin": {},
    "end": {}
  },
  "inner": [
    {
      "id": "0x2395d58",
      "kind": "FunctionDecl",
      "loc": {
        "offset": 187,
        "file": "<stdin>",
        "line": 8,
        "presumedFile": "tester/functional/000_main.sysu.c",
        "presumedLine": 1,
        "col": 5,
        "tokLen": 4
      },
      "range": {
        "begin": {
          "offset": 183,
          "col": 1,
          "tokLen": 3
        },
        "end": {
          "offset": 209,
          "line": 10,
          "presumedLine": 3,
          "col": 1,
          "tokLen": 1
        }
      },
      "name": "main",
      "mangledName": "main",
      "type": {
        "qualType": "int ()"
      },
      "inner": [
        {
          "id": "0x2395e70",
          "kind": "CompoundStmt",
          "range": {
            "begin": {
              "offset": 193,
              "line": 8,
              "presumedLine": 1,
              "col": 11,
              "tokLen": 1
            },
            "end": {
              "offset": 209,
              "line": 10,
              "presumedLine": 3,
              "col": 1,
              "tokLen": 1
            }
          },
          "inner": [
            {
              "id": "0x2395e60",
              "kind": "ReturnStmt",
              "range": {
                "begin": {
                  "offset": 199,
                  "line": 9,
                  "presumedLine": 2,
                  "col": 5,
                  "tokLen": 6
                },
                "end": {
                  "offset": 206,
                  "col": 12,
                  "tokLen": 1
                }
              },
              "inner": [
                {
                  "id": "0x2395e40",
                  "kind": "IntegerLiteral",
                  "range": {
                    "begin": {
                      "offset": 206,
                      "col": 12,
                      "tokLen": 1
                    },
                    "end": {
                      "offset": 206,
                      "col": 12,
                      "tokLen": 1
                    }
                  },
                  "type": {
                    "qualType": "int"
                  },
                  "valueCategory": "rvalue",
                  "value": "3"
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

我们需要从根节点遍历这颗树，然后生成与下面类似的IR。

( export PATH=$HOME/sysu/bin:$PATH   CPATH=$HOME/sysu/include:$CPATH   LIBRARY_PATH=$HOME/sysu/lib:$LIBRARY_PATH   LD_LIBRARY_PATH=$HOME/sysu/lib:$LD_LIBRARY_PATH &&   clang -E tester/functional/000_main.sysu.c |   clang -cc1 -O0 -S -emit-llvm )

; ModuleID = '-'
source_filename = "-"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

; Function Attrs: noinline nounwind optnone
define i32 @main() #0 {
entry:
  %retval = alloca i32, align 4
  store i32 0, i32* %retval, align 4
  ret i32 3
}

attributes #0 = { noinline nounwind optnone "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-features"="+cx8,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{!"Debian clang version 11.0.1-2"}

删除无关的部分，只需要生成类似下面这种IR（评测机会看你代码的返回值是否正确，如果源代码中有类似于printf的输出语句，也会检查printf的输出是否正确）。

; ModuleID = '-'
source_filename = "-"

define i32 @main() {
entry:
  ret i32 3
}

生成IR

  • llvm::LLVMContext TheContext: 是一个不透明的对象，它拥有许多核心 LLVM 数据结构，例如类型和常量值表。我们不需要详细了解它，我们只需要一个实例来传递给需要它的 API。

  • llvm::Module TheModule("-", TheContext): 是一个包含函数和全局变量的 LLVM 结构，我们生成的所有 IR 都会储存在这里。在许多方面，它是 LLVM IR 用来包含代码的顶级结构。

  • llvm::IRBuilder<> Builder(TheContext): 是用于生成IR的对象，提供了统一的API来创建和插入指令到基本块 (basic block) 中。我们可以使用IRBuilder的构造函数来指定IR的插入位置，也可以使用SetInsertPoint方法来修改IR的插入位置。

生成IR需要利用llvm::IRBuilder对象，主要是调用类llvm::IRBuilder中的函数生成LLVM IR指令，具体有哪些函数可以查看llvm::IRBuilder源码，链接在此https://github.com/llvm/llvm-project/blob/llvmorg-11.0.1/llvm/include/llvm/IR/IRBuilder.h。 下面列举一些重要的API。

表达式

Value *CreateSub(Value *LHS, Value *RHS, const Twine &Name = "",
                   bool HasNUW = false, bool HasNSW = false)

创建表达式LHS-RHS的IR。

Value *CreateAdd(Value *LHS, Value *RHS, const Twine &Name = "",
                   bool HasNUW = false, bool HasNSW = false)

创建表达式LHS+RHS的IR。类似的都可以在IRBuilder.h中找到。

类型相关

类型相关的知识可以查看"llvm/IR/Type.h"

几乎所有和 create 相关的 API 都会使用到 llvm::Type* 类型，这里只介绍目前用到的几种类型：

常规int

比如 int32，使用 llvm::Type::getInt32Ty(TheContext)即可获得。

函数类型

使用 llvm::FunctionType::get()即可获得。

数组类型

使用 llvm::ArrayType::get(arr_type, arr_size)获得。

比如 int a[10]的类型 int [10]:

可以如此：

llvm::ArrayType::get(llvm::Type::getInt32Ty(TheContext),10);

常量

可以使用llvm::ConstantInt::get(constant_type, constant_value)获得，例如const int a = 10：

llvm::ConstantInt::get(llvm::IntegerType::getInt32Ty(TheContext), 10)

如果你有一个IRBuilder的话，也可以使用llvm::IRBuilder::getInt32(value)获得：

IRBuilder<> builder(BB);
builder.getInt64(10);

局部变量

有两种方法可以将值存储在 LLVM IR 的局部变量中。第一个：分配给虚拟寄存器。第二种是使用 alloca 指令对堆栈进行动态内存分配。使用 alloca 指令来动态分配比较简单，下面介绍使用 alloca 来完成。

局部变量声明

要使用指令Builder.CreateAlloca()

比如：

// 待生成的 C 代码
int a;
// 
// 使用如下 API
auto a_ptr = Builder.CreateAlloca(llvm::Type::getInt32Ty(TheContext), nullptr, "a");
//
// 生成的 IR
%a = alloca i32, align 4

变量的取值

要使用指令Builder.CreateLoad();

比如：

//
int b;
b = a; 

// 对上面的 a 取值
llvm::Value* a_value = Builder.CreateLoad(a_ptr);


// 生成的IR
%0 = load i32, i32* %a, align 4

变量的赋值

使用指令Builder.CreateStore()

比如：

int b; // 对应生成的位 b_ptr
b = a;

// 对 b 进行赋值
Builder.CreateStore(a_value, b_ptr);

// 生成的IR
store i32 %0, i32* %b, align 4

全局变量

全局变量必须初始化，否则会默认生成 extern 的变量。

使用 API 是：

TheModule.getOrInsertGlobal(globalVarName, globalVarType);
...
llvm::GlobalVariable *globalVar = TheModule.getNamedGlobal(globalVarName); // 找一个全局变量
globalVar->setInitializer(initValue);//初始化

另一种更加简洁的方式：

llvm::GlobalVariable *globalVar = new llvm::GlobalVariable(TheModule, globalVarType, /*isConstant*/ false,
              llvm::GlobalValue::ExternalLinkage, initValue, globalVarName)

对全局变量也是可以通过 load 和 store 来操作：

Builder.CreateLoad(globalVar);
Builder.CreateStore(someVal, globalVar);

函数

函数声明

llvm::Function::Create()创建一个函数签名：包括返回类型，函数名字，函数参数列表。其中 <返回类型，函数参数类型>构成 FunctionType。

llvm::Function::Create(
          llvm::FunctionType::get(llvm::Type::getInt32Ty(TheContext), parms, false),
          llvm::Function::ExternalLinkage, TheName, &TheModule);

函数调用

llvm::Function *TheFunction = TheModule.getFunction(fun_name);//获取对应函数名的函数
Builder.CreateCall(TheFunction, actargs);//调用函数

基本块

auto BB = llvm::BasicBlock::Create(TheContext,"entry",TheFunction);//在函数TheFunction中创建名为entry的基本块

数组

数组的声明（定义）是全局变量和部分变量的一部分，然而，要访问数组的元素却需要另外的 API——GEP

获取元素指针 (GEP) 指令是将指针偏移量应用于基指针并返回结果指针的指令。

LLVM/Builder 上提供很多 GEP 相关的 API，这里推荐一个通用的 API：Builder.CreateInBoundsGEP。

// 源 C 代码
int arr[10];
arr[1] = 5;

// 我们编写的 Generator 代码
// llvm::Value* arr = Builder.CreateAlloca(arrType, nullptr, "a");
// llvm::Value* idx = llvm::ConstantInt::get(TheContext, llvm::APInt(32, 1));
// 注意第三个参数传入一个 vector, vector 第一个元素默认为 0
Builder.CreateInBoundsGEP(arrType, arr, {llvm::ConstantInt::get(TheContext, llvm::APInt(32, 0)), idx});


// 生成的 IR
i32* getelementptr inbounds ([10 x i32], [10 x i32]* @a, i32 0, i32 1), align 4

还可以有更加简单的使用方式，Builder.CreateInBoundsGEP可以不需要传入 arrType，从而免去类型之苦，比如上面的 gep 代码可以直接改为：

Builder.CreateInBoundsGEP(arr, {llvm::ConstantInt::get(TheContext, llvm::APInt(32, 0)), idx});

另外，关于 GEP 理解的一些误区，可以参考官方文档和这篇博客，由于高维数组的GEP操作较为复杂，这里建议将高维数组看作一维数组操作。

太长不看版：

为什么index的第一个元素是0呢？在C语言中“数组”可以看成指针，但LLVM的“数组”是一种类型，不是指针，传给GEP的是指向此“数组”的指针。也就是说对于a[i]的访问，需要使用 (&a)[0][i]的方式来完成，第一个参数自然是0.

If语句和While语句

这部分内容将简要讲述控制流的语句的 IR 生成，喜欢英文以及英文不错的同学可以看看这个：https://releases.llvm.org/11.0.1/docs/tutorial/MyFirstLanguageFrontend/LangImpl05.html

涉及到对基本块 (BasicBlock) 的操作的 API 如下：

  • llvm::BasickBlock* llvm::BasicBlock::Create()： 创建一个基本块，返回此基本块指针；

  • Builder.CreateBr(llvm::BasickBlock* dst): 无条件跳转到 dst基本块；

  • BranchInst *CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False): 条件跳转，根据 Cond （Cond 的类型为 1 bit 的类型）跳转。

  • TheFunction->getBasicBlockList().push_back(BasicBlock* src): 把一个基本块 src 加入到基本块列表末端。

  • Builder.SetInsertPoint(BB):设置插入点，下一条指令插入到基本块BB中。

llvm::json补充

由于要遍历json格式的语法树，这里补充操作json数据的API，可参考https://github.com/llvm/llvm-project/blob/llvmorg-11.0.1/llvm/include/llvm/Support/JSON.h

llvm::json::Object类似于c++中的哈希表，llvm::json::Array类似于c++中的数组vector。

比如如下的json数据

{
  "kind": "TranslationUnitDecl",
  "inner": [
    {
      "kind": "FunctionDecl",
      "name": "main",
      "inner": [
        {
          "kind": "CompoundStmt",
          "inner": [
            {
              "kind": "ReturnStmt",
              "inner": [
                {
                  "kind": "IntegerLiteral",
                  "value": "3"
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

假设这个json格式的语法树存放在llvm::json::Object*O所指向的内存中。

O->get("inner")->getAsArray()和O->getArray("inner")的效果相同，都是得到最外层键inner对应的数组类型数据[...]。

而O->get("kind")->getAsString()->str()可以得到对应的字符串数据"TranslationUnitDecl"。

Clone this wiki locally