系列文章目录
LLVM系列第一章：编译LLVM源码 LLVM系列第二章：模块Module LLVM系列第三章：函数Function LLVM系列第四章：逻辑代码块Block LLVM系列第五章：全局变量Global Variable LLVM系列第六章：函数返回值Return LLVM系列第七章：函数参数Function Arguments LLVM系列第八章：算术运算语句Arithmetic Statement LLVM系列第九章：控制流语句if-else LLVM系列第十章：控制流语句if-else-phi LLVM系列第十一章：写一个Hello World LLVM系列第十二章：写一个简单的词法分析器Lexer LLVM系列第十三章：写一个简单的语法分析器Parser LLVM系列第十四章：写一个简单的语义分析器Semantic Analyzer LLVM系列第十五章：写一个简单的中间代码生成器IR Generator LLVM系列第十六章：写一个简单的编译器 LLVM系列第十七章：for循环 LLVM系列第十八章：写一个简单的IR处理流程Pass LLVM系列第十九章：写一个简单的Module Pass LLVM系列第二十章：写一个简单的Function Pass LLVM系列第二十一章：写一个简单的Loop Pass LLVM系列第二十二章：写一个简单的编译时函数调用统计器(Pass) LLVM系列第二十三章：写一个简单的运行时函数调用统计器(Pass) LLVM系列第二十四章：用Xcode编译调试LLVM源码 LLVM系列第二十五章：简单统计一下LLVM源码行数 LLVM系列第二十六章：理解LLVMContext LLVM系列第二十七章：理解IRBuilder LLVM系列第二十八章：写一个JIT Hello World LLVM系列第二十九章：写一个简单的常量加法“消除”工具(Pass)
flex&bison系列
在此记录下，基于LLVM写一个简单的中间代码生成器（Simple IR Generator）的过程，以备查阅。
开发环境的配置请参考 《LLVM系列第一章：编译LLVM源码 》。
我们再来简单复习一下，编译器前端的流程：
词法分析Lexical
语法分析Syntax
语义分析Semantic
中间代码IR
更多关于编译器前端的介绍，请参看《LLVM系列第三章：写一个简单的词法分析器Lexer 》。
本章内容仅与中间代码的生成(Intermediate Code Generation)有关，是一个简单的示例而已。其它与词法分析(Lexical Analysis)、语法分析(Syntax Analysis)以及语义分析(Semantic Analysis)相关的文章，请参看前面的章节。
为了方便起见，我们自己定义一种很简单的语言（名为SimpleLang）如下（示例）：
calc : ("with" ident ("," ident)* ":")? expr ;
expr: term(("+"|"-")term)* ;
term : factor (( "*" | "/") factor)* ;
factor : ident | number | "(" expr ")" ;
ident : ([a-zAZ])+ ;
number : ([0-9])+ ;
这也是我们在前面章节中用到的语言。
我们把这个简单的项目命名为SimpleSemanticAnalyzer。项目组织结构与前几章的项目类似，具体如下（示例）：
% tree -I "build|build-xcode"
.
├── CMakeLists.txt
├── README.md
└── src
├── AST.h
├── CMakeLists.txt
├── IRGenerator.cpp
├── IRGenerator.h
├── IRGeneratorPlayer.cpp
├── Lexer.cpp
├── Lexer.h
├── Parser.cpp
├── Parser.h
├── SemanticAnalyzer.cpp
└── SemanticAnalyzer.h
各文件的内容大体如下：
AST.h，SimpleLang语言的抽象语法树(AST)的定义及实现代码。
Lexer.h和Lexer.cpp，SimpleLang语言的词法分析器(Lexer)的定义及实现代码。
Parser.h和Parser.cpp，SimpleLang语言的语法分析器(Parser)的定义及实现代码。
SemanticAnalyzer.h和SemanticAnalyzer.cpp，SimpleLang语言的语义分析器(Semantic Analyzer)的定义及实现代码。
IRGenerator.h和IRGenerator.cpp，中间代码(Intermediate Representation，即IR)生成器的定义及实现代码。这是本章的重点。
IRGeneratorPlayer.cpp，main函数，即IRGenerator的测试代码。
这个简单的项目只包含了一个模块：
SimpleSemanticAnalyzer，一个可执行程序文件 以下是跟项目组织结构相关的部分CMake脚本，与前一章的CMake脚本类似。
(1) 项目根目录（示例）：
# CMakeLists.txt
...
project ("SimpleIRGenerator")
...
add_subdirectory ("src")
这里创建了一个项目(project)，并把src目录下的子项目加入进来。
(2) src目录（示例）：
# src/CMakeLists.txt
...
add_executable(SimpleIRGenerator ...)
...
这是src目录下的子项目，用来构建SimpleIRGenerator程序。
我们需要做一些与LLVM相关的配置，才能顺利地使用LLVM，具体做法请参看前面章节。
词法、语法、语义分析的相关代码已在前面章节介绍，本章的重点在中间代码的生成上：
src/SimpleIRGeneratorPlayer.cpp，包含了main函数，即测试代码
src/SimpleIRGenerator.h，src/SimpleIRGenerator.cpp，包含了中间代码生成器的定义及实现代码
main函数（示例）：
#include "IRGenerator.h"
...
static llvm::cl::opt<std::string> input(llvm::cl::Positional, llvm::cl::desc("<input expression>"), llvm::cl::init(""));
int main(int argc, const char** argv)
{
llvm::InitLLVM llvmInitializer(argc, argv);
llvm::cl::ParseCommandLineOptions(argc, argv, "SimpleParser - a simple code parser\n");
llvm::outs() << "Input: \"" << input << "\"\n\n";
Lexer lexer(input);
Parser parser(lexer);
AST* tree = parser.Parse();
...
SemanticAnalyzer semanticAnalyzer;
semanticAnalyzer.Analysis(tree)
...
IRGenerator irGenerator;
irGenerator.Generate(tree);
...
}
我们看到以上代码调用了IRGenerator来生成IR代码。IRGenerator的定义如下（示例）：
class IRGenerator
{
public:
void Generate(AST* Tree);
};
定义是很简单的，实现如下（示例）：
namespace
{
class IRGeneratorImplementation : public ASTVisitor
{
Module* module;
IRBuilder<> builder;
Type* voidType;
Type* int32Type;
Type* int8PtrType;
Type* int8PtrPtrType;
Constant* int32Zero;
Value* value;
StringMap<Value*> nameMap;
public:
IRGeneratorImplementation(Module* inModule) :
module(inModule),
builder(inModule->getContext())
{
voidType = Type::getVoidTy(module->getContext());
int32Type = Type::getInt32Ty(module->getContext());
int8PtrType = Type::getInt8PtrTy(module->getContext());
int8PtrPtrType = int8PtrType->getPointerTo();
int32Zero = ConstantInt::get(int32Type, 0, true);
}
void Generate(AST* tree)
{
FunctionType* mainFunctionType = FunctionType::get(int32Type, {int32Type, int8PtrPtrType}, false);
Function* mainFunction = Function::Create(mainFunctionType, GlobalValue::ExternalLinkage, "main", module);
BasicBlock* basicBlock = BasicBlock::Create(module->getContext(), "entry", mainFunction);
builder.SetInsertPoint(basicBlock);
tree->Accept(*this);
FunctionType* calculatorWriteFunctionType = FunctionType::get(voidType, {int32Type}, false);
Function* calculatorWriteFunction =
Function::Create(calculatorWriteFunctionType, GlobalValue::ExternalLinkage, "calc_write", module);
builder.CreateCall(calculatorWriteFunctionType, calculatorWriteFunction, {value});
builder.CreateRet(int32Zero);
}
void Visit(Factor& node) override
{
if (node.GetType() == Factor::kIdent)
{
value = nameMap[node.GetValue()];
}
else
{
int intValue;
node.GetValue().getAsInteger(10, intValue);
value = ConstantInt::get(int32Type, intValue, true);
}
};
void Visit(BinaryOp& node) override
{
node.GetLeft()->Accept(*this);
Value* left = value;
node.GetRight()->Accept(*this);
Value* right = value;
switch (node.GetOperator())
{
case BinaryOp::kPlus:
value = builder.CreateNSWAdd(left, right);
break;
case BinaryOp::kMinus:
value = builder.CreateNSWSub(left, right);
break;
case BinaryOp::kMultiple:
value = builder.CreateNSWMul(left, right);
break;
case BinaryOp::kDivide:
value = builder.CreateSDiv(left, right);
break;
}
};
void Visit(WithDeclaration& node) override
{
FunctionType* calculatorReadFunctionType = FunctionType::get(int32Type, {int8PtrType}, false);
Function* calculatorReadFunction =
Function::Create(calculatorReadFunctionType, GlobalValue::ExternalLinkage, "calc_read", module);
for (const auto& variable : node)
{
// Create call to calc_read function
Constant* strText = ConstantDataArray::getString(module->getContext(), variable);
GlobalVariable* str = new GlobalVariable(*module,
strText->getType(),
/*isConstant=*/true,
GlobalValue::PrivateLinkage,
strText,
Twine(variable).concat(".str"));
Value* ptr = builder.CreateInBoundsGEP(str, {int32Zero, int32Zero}, "ptr");
CallInst* call = builder.CreateCall(calculatorReadFunctionType, calculatorReadFunction, {ptr});
nameMap[variable] = call;
}
node.GetExpr()->Accept(*this);
};
};
} // namespace
void IRGenerator::Generate(AST* tree)
{
LLVMContext context;
Module* module = new Module("calc.expr", context);
IRGeneratorImplementation generator(module);
generator.Generate(tree);
module->print(outs(), nullptr);
}
注意到，与前几章相比，我在这里调用了比较多的LLVM API。虽然这只是个示例程序而已，但是牵涉的LLVM相关的API已经不少了。
首先IRGenerator是AST的子类，关于抽象语法树(AST)的定义及实现请参考前面章节。这个示例中，IRGenerator需要遍历AST的节点，并为每个节点生成相应的IR代码。而具体的遍历及IR的生成工作，我们交给了IRGeneratorImplementation来做：
ASTVisitor
+Visit(AST&)
+Visit(Expr&)
+Visit(Factor&)
+Visit(BinaryOp&)
+Visit(WithDeclaration&)
IRGeneratorImplementation
+Visit(Factor&)
+Visit(BinaryOp&)
+Visit(WithDeclaration&)
IRGenerator首先创建了llvm::Module，这是IR代码组织结构中很重要基本的组成单元。Module中可以包含函数定义及实现，而函数中则包含了基本代码块BasicBlock，而BasicBlock则包含了一行行的代码，比如变量赋值、数学运算表达式、函数调用、函数返回等等。当然，所有这些都是可以用IR代码表达出来。
用CMake生成项目文件（示例）：
mkdir build
cd build
cmake -G Ninja -DCMAKE_BUILD_TYPE=Debug ..
输出log如下（示例）：
-- The C compiler identification is AppleClang 13.0.0.13000029
-- The CXX compiler identification is AppleClang 13.0.0.13000029
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/cc - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/c++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Found ZLIB: /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX12.1.sdk/usr/lib/libz.tbd (found version "1.2.11")
-- Found LibXml2: /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX12.1.sdk/usr/lib/libxml2.tbd (found version "2.9.4")
Found LLVM 12.0.1, build type Release
-- Configuring done
-- Generating done
-- Build files have been written to: .../SimpleIRGenerator/build
如果要生成Xcode项目文件，我们稍微改一下cmake命令的参数即可（示例）：
mkdir build-xcode
cd build-xcode
cmake -G Xcode -DCMAKE_BUILD_TYPE=Debug ..
在编译之前，我们可以用clang-format工具把代码美化一下（示例）:
cd /path/to/SimpleIRGenerator
clang-format -i src/*.cpp src/*.h
用ninja进行编译（示例）：
cd /path/to/SimpleIRGenerator/build
ninja
输出log如下（示例）：
[6/6] Linking CXX executable src/SimpleIRGenerator
运行SimpleIRGenerator（示例）：
src/SimpleIRGenerator "with abc,xyz: (abc+xyz)*3 - 10/abc"
我们用于测试的SimpleLang程序代码，就这么简单的一句而已with abc,xyz: (abc+xyz)*3 - 10/abc。输出结果如下（示例）：
Input: "with abc,xyz: (abc+xyz)*3 - 10/abc"
; ModuleID = 'calc.expr'
source_filename = "calc.expr"
@abc.str = private constant [4 x i8] c"abc\00"
@xyz.str = private constant [4 x i8] c"xyz\00"
define i32 @main(i32 %0, i8** %1) {
entry:
%2 = call i32 @calc_read(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @abc.str, i32 0, i32 0))
%3 = call i32 @calc_read(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @xyz.str, i32 0, i32 0))
%4 = add nsw i32 %2, %3
%5 = mul nsw i32 %4, 3
%6 = sdiv i32 10, %2
%7 = sub nsw i32 %5, %6
call void @calc_write(i32 %7)
ret i32 0
}
declare i32 @calc_read(i8*)
declare void @calc_write(i32)
可以看到，中间代码生成器可以为我们的SimpleLang语言生成LLVM IR代码了。
我们主要基于LLVM提供的API，用C++写了一个很简单的中间代码(IR)生成器。完整源码示例请参看：https://github.com/wuzhanglin/llvm-simple-IR-generator
