LLVM 编译原理

LLVM-实现一个简单的编译器

编译

Posted by MetaNetworks on September 23, 2020
本页面总访问量次

教程使用的LLVM版本：LLVM 9.0.1

代码：https://github.com/MetaNetworks/kaleidoscope-llvm-compiler

参考教程：https://github.com/zy445566/llvm-guide-zh

LLVM环境配置

此处使用cmake完成LLVM环境的配置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

cmake_minimum_required(VERSION 3.15)
project(llvm_kaleidoscope)

set(CMAKE_CXX_STANDARD 11)

find_package(LLVM REQUIRED CONFIG)

message(STATUS "Found LLVM ${LLVM_PACKAGE_VERSION}")
message(STATUS "Using LLVMConfig.cmake in: ${LLVM_DIR}")
message(STATUS "Using defs in: ${LLVM_DEFINITIONS}")

# import LLVM
include_directories(${LLVM_INCLUDE_DIRS})
add_definitions(${LLVM_DEFINITIONS})

add_executable(llvm_kaleidoscope main.cpp Lexer.cpp Lexer.h ExprAST.cpp ExprAST.h Parser.cpp Parser.h global.h file_reader_wrapper.h err_helper.h err_helper.cpp global.cpp FileReader.cpp FileReader.h)

# Find the libraries that correspond to the LLVM components
# that we wish to use
llvm_map_components_to_libnames(llvm_libs all)

# Link against LLVM libraries
target_link_libraries(llvm_kaleidoscope ${llvm_libs})

将LLVM导入项目

导包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include "llvm/ADT/APFloat.h"
#include "llvm/ADT/Optional.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/LegacyPassManager.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Support/TargetSelect.h"
#include "llvm/Support/FileSystem.h"
#include "llvm/Support/Host.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/TargetRegistry.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Scalar/GVN.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"

编写自己的词法分析器

此处只是大致流程

定义token

1
2
3
4
5
6
7
8

/// Token类型
enum Token {
    tok_eof = -1, // EOF
    tok_def = -2, // 函数定义
    tok_extern = -3, //调用的标准库函数
    tok_identifier = -4, //标识符
    tok_number = -5 //数字
};

定义文件读取器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

//
// Created by 金韬 on 2020/9/23.
//

#ifndef LLVM_KALEIDOSCOPE_FILEREADER_H
#define LLVM_KALEIDOSCOPE_FILEREADER_H

#include <string>

#include "file_reader_wrapper.h"

class FileReader : public FileReaderWrapper {

    std::string content;
    unsigned int index = 0;

public:
    explicit FileReader(const std::string &path);
		// 获取下一个字符
    char getchar() override;
		// 查看当前字符
    char seek() override;
    unsigned long content_length;
};


#endif //LLVM_KALEIDOSCOPE_FILEREADER_H

定义Lexer词法分析器

  • 仅为参考，可以有多种实现方式
  • 实现代码见仓库
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Lexer {
public:
    std::string identifierStr; //如果是tok_identifier就传入
    double NumVal = INIT_NUM; //如果是tok_number则表示数字
    int currToken; //当前的token

    /// 当前的Token
    FileReader reader;
    /// lexer构造函数：传入代码
    /// params: rawStr 代码全文
    explicit Lexer(FileReader fileReader) : reader(std::move(fileReader)) {}
    /// 获取下一个token
    int getNextToken();

private:
    int _getNextToken();
    char getchar();
    char seek();

};

定义AST语法树

实现内容：

  • 基础结点
  • 数值结点
  • 变量结点
  • 二元操作结点
  • 函数
    • 函数描述结点
    • 函数实现结点

注意：

codegen用于生产LLVM IR代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

/// 基结点
class ExprAST {
public:
    virtual ~ExprAST() = default;

    virtual llvm::Value *codegen() = 0;
};

/// 数值语法结点
class NumberExprAST : public ExprAST {
    double Val;
public:
    explicit NumberExprAST(double val) : Val(val) {}

    /// codegen（）方法表示为该AST节点发出IR及其依赖的所有内容，并且它们都返回一个LLVM Value对象。
    /// “Value”是用于表示 LLVM中的“ 静态单一分配（SSA）寄存器”或“SSA值”的类。
    /// SSA值的最独特之处在于它们的值是在相关指令执行时计算的，并且在指令重新执行之前（以及如果）它不会获得新值。
    /// 换句话说，没有办法“改变”SSA值。
    llvm::Value *codegen() override;
};

/// 变量结点
class VariableExprAST : public ExprAST {
    std::string Name;
public:
    explicit VariableExprAST(std::string &Name) : Name(Name) {}

    llvm::Value *codegen() override;
};

/// 二元操作结点
class BinaryExprAST : public ExprAST {
    // 操作符
    char Oper;
    std::unique_ptr<ExprAST> LEA, REA;
public:
    explicit BinaryExprAST(char oper, std::unique_ptr<ExprAST> LEA, std::unique_ptr<ExprAST> REA) : Oper(oper),
                                                                                                    LEA(std::move(LEA)),
                                                                                                    REA(std::move(
                                                                                                            REA)) {}

    llvm::Value *codegen() override;
};

/// 函数调用结点
class CallExprAST : public ExprAST {
    std::string callName;
    std::vector<std::unique_ptr<ExprAST>> args;

public:
    CallExprAST(std::string callName, std::vector<std::unique_ptr<ExprAST>> args) : callName(std::move(callName)),
                                                                                    args(std::move(args)) {};

    llvm::Value *codegen() override;
};

/// 函数描述结点
/// 用于描述函数名字，参数名称，参数个数
class PrototypeAST : public ExprAST {
    std::string name;
    std::vector<std::string> args;

public:
    PrototypeAST(std::string name, std::vector<std::string> args) : name(std::move(name)), args(std::move(args)) {}

    llvm::Function *codegen() override;

    const std::string &getName() const;
};

/// 函数结点
class FunctionAST : public ExprAST {
    std::unique_ptr<PrototypeAST> Proto;
    std::unique_ptr<ExprAST> Body;
public:
    FunctionAST(std::unique_ptr<PrototypeAST> Proto, std::unique_ptr<ExprAST> Body) : Proto(std::move(Proto)),
                                                                                      Body(std::move(Body)) {}

    llvm::Function *codegen() override;
};

定义语法分析器

要点：

  • 实现解析函数
    • 数字
    • 标识符
    • 函数定义
    • 表达式
  • 实现二元操作优先级比较
  • [可选]编写test()函数测试语法分析器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

/// 语法分析器
class Parser {
public:
    Parser(Lexer lexer);

    // 词法分析器
    Lexer _lexer;

    // 解析数字
    std::unique_ptr<ExprAST> parseNumberExpr();

    // 解析标识符
    std::unique_ptr<ExprAST> parseIdentifierExpr();

    // 解析表达式
    std::unique_ptr<ExprAST> parseExpression();

    // 封装的处理方法
    std::unique_ptr<ExprAST> parsePrimary();

    // 处理带有括号的表达式
    std::unique_ptr<ExprAST> parseParentExpr();

    // 处理函数定义
    std::unique_ptr<PrototypeAST> parsePrototypeExpr();

    // 处理函数def
    std::unique_ptr<FunctionAST> parseDefinition();

    // 处理extern
    std::unique_ptr<PrototypeAST> parseExtern();

    // 测试函数：输入任意表达式进行测试
    std::unique_ptr<FunctionAST> parseTopLevelExpr();

    // 测试
    void test();

private:
    std::map<char, int> binOpPriority;

    std::unique_ptr<ExprAST> parseBinOpRHS(int priority, std::unique_ptr<ExprAST> &&uniquePtr);

    // 获取token优先级
    int getTokenPriority();

    void HandleDefinition();

    void HandleExtern();

    void HandleTopLevelExpression();
};

创建测试代码

  • 源文件
1

def average(x y) (x+y)/2;

  • 编译器main函数

    • 词法、语法分析

      • 1
2
3
4
5

          TheModule = llvm::make_unique<Module>("MetaNetworks' jit", TheContext);
      FileReader reader("/Users/MetaNetworks/CLionProjects/llvm-kaleidoscope/test.kl");
      Lexer lexer(reader);
      Parser parser(lexer);
      parser.test();

    • 生成目标代码

      • LLVM支持交叉编译，可以在tarrgetTriple里定义其他目标系统以生成其他架构的代码

      • 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

          // 生成目标代码
      InitializeAllTargetInfos();
      InitializeAllTargets();
      InitializeAllTargetMCs();
      InitializeAllAsmParsers();
      InitializeAllAsmPrinters();
            
      auto TargetTriple = sys::getDefaultTargetTriple();
      TheModule->setTargetTriple(TargetTriple);
            
      std::string Error;
      auto Target = TargetRegistry::lookupTarget(TargetTriple, Error);
            
      // Print an error and exit if we couldn't find the requested target.
      // This generally occurs if we've forgotten to initialise the
      // TargetRegistry or we have a bogus target triple.
      if (!Target) {
          errs() << Error;
          return 1;
      }
            
      auto CPU = "generic";
      auto Features = "";
            
      TargetOptions opt;
      auto RM = Optional<Reloc::Model>();
      auto TheTargetMachine =
              Target->createTargetMachine(TargetTriple, CPU, Features, opt, RM);
            
      TheModule->setDataLayout(TheTargetMachine->createDataLayout());
            
      auto Filename = "output.o";
      std::error_code EC;
      raw_fd_ostream dest(Filename, EC, sys::fs::F_None);
            
      if (EC) {
          errs() << "Could not open file: " << EC.message();
          return 1;
      }
            
      legacy::PassManager pass;
      auto FileType = TargetMachine::CGFT_ObjectFile;
            
      if (TheTargetMachine->addPassesToEmitFile(pass, dest, nullptr, FileType)) {
          errs() << "TheTargetMachine can't emit a file of this type";
          return 1;
      }
            
      pass.run(*TheModule);
      dest.flush();
            
      outs() << "Wrote " << Filename << "\n";

最终效果

为了能实现输出，此处使用C++，调用自定义语言中定义的average函数 (def average(x y) (x+y)/2;)，算出平均值。先编译出.o文件与main.cpp进行链接。

main.cpp：

1
2
3
4
5
6
7
8
9
10
11
12
13

#include <iostream>

extern "C" {
    double average(double,double);
}

int main() {
    double a,b;
    std::cout<<"average number calculator"<<std::endl;
    std::cout<<"input a,b:";
    std::cin >> a >> b;
    std::cout << "average:" << average(a,b) << std::endl;
}

反编译结果：

编译指令：g++ main.cpp output.o -o main

运行效果：

CATALOG
    FEATURED TAGS
    OMPi小组会议 Linux Android 人工智能 操作系统 汇编语言 算法 Git Python 数学建模 编译原理 计算机网络 Flutter Matlab C++ English MySQL OMPi知识 Qt Shell 安卓 数据库原理 计算机组成原理 MCM python 信息安全 电子技术基础 Docker LLVM PHP React Rust SQL Server linux
    伙伴链接
    我的Links