使用flex, bison, llvm实现编译器

LLVM 每一个版本的接口都有很大的不同,每个版本使用的C++标准甚至都有差别,为了将已有代码编译通过,需要使用合适的C++标准和 LLVM 版本.

经测试,原始代码使用的C++标准是14, LLVM 版本为 LLVM 9.0.1_4.在 macOS 13.2.1 上,可以通过 brew install llvm@9 来安装这个版本的 LLVM,在安装结束后, brew 会输出安装位置(在这个目录下有 bin, lib, include 等常见目录),在本文中,我们将这个位置称为 LLVM_DIR.例如,在我的系统上, LLVM_DIR 为 /usr/local/Cellar/llvm@9/9.0.1_4.

原始代码中的 Makefile 文件使用 llvm-config 来设置头文件目录和库搜索目录:

  # ...
  LLVMCONFIG = llvm-config
  # ...
  CPPFLAGS = `$(LLVMCONFIG) --cppflags` -std=c++14
  LDFLAGS = `$(LLVMCONFIG) --ldflags` -lz -lncurses
  # ...

关于 llvm-config 的更多资料,参考官方文档.总而言之,这要求我们将 LLVM 9.0.1_4 的 bin 目录放到 PATH 路径最开头,以便 make 能找到合适的 llvm-config.

设置好上述的一切后,在我的系统上, make compile 会输出以下内容:

  bison -d -o parser.cpp parser.y
  clang++ -c `llvm-config --cppflags` -std=c++14 -o parser.o parser.cpp
  clang++ -c `llvm-config --cppflags` -std=c++14 -o codegen.o codegen.cpp
  clang++ -c `llvm-config --cppflags` -std=c++14 -o main.o main.cpp
  flex -o tokens.cpp tokens.l parser.hpp
  clang++ -c `llvm-config --cppflags` -std=c++14 -o tokens.o tokens.cpp
  clang++ -c `llvm-config --cppflags` -std=c++14 -o corefn.o corefn.cpp
  clang++ -c `llvm-config --cppflags` -std=c++14 -o native.o native.cpp
  clang++ -o compiler parser.o codegen.o main.o tokens.o corefn.o native.o  `llvm-config --libs` `llvm-config --ldflags` -lz -lncurses
  ./compiler
  Generating code...
  Generating code for 18NExternDeclaration
  Generating code for 20NFunctionDeclaration
  Creating variable declaration int a
  Generating code for 20NVariableDeclaration
  Creating variable declaration int x
  Creating assignment for x
  Creating binary operation 276
  Creating identifier reference: a
  Creating integer: 5
  Generating code for 16NReturnStatement
  Generating return code for 15NBinaryOperator
  Creating binary operation 274
  Creating identifier reference: x
  Creating integer: 3
  Creating block
  Creating function: do_math
  Generating code for 20NExpressionStatement
  Generating code for 11NMethodCall
  Creating integer: 13
  Creating method call: do_math
  Creating method call: echo
  Generating code for 20NExpressionStatement
  Generating code for 11NMethodCall
  Creating integer: 12
  Creating method call: do_math
  Creating method call: echo
  Generating code for 20NExpressionStatement
  Generating code for 11NMethodCall
  Creating integer: 10
  Creating method call: printi
  Creating block
  ; ModuleID = 'main'
  source_filename = "main"

  @.str = private constant [4 x i8] c"%d\0A\00"

  declare i32 @printf(i8*, ...)

  define internal void @echo(i64 %toPrint) {
  entry:
    %0 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i32 0, i32 0), i64 %toPrint)
    ret void
  }

  define i32 @main() {
  entry:
    %0 = call i64 @do_math(i64 13)
    call void @echo(i64 %0)
    %1 = call i64 @do_math(i64 12)
    call void @echo(i64 %1)
    call void @printi(i64 10)
    ret i32 0
  }

  declare void @printi(i64)

  define internal i64 @do_math(i64 %a1) {
  entry:
    %a = alloca i64
    store i64 %a1, i64* %a
    %x = alloca i64
    %0 = load i64, i64* %a
    %1 = mul i64 %0, 5
    store i64 %1, i64* %x
    %2 = load i64, i64* %x
    %3 = add i64 %2, 3
    ret i64 %3
  }
  Code is generated.
  sleep 1
  llc test/example.bc -o test/example.S
  sleep 1
  clang++ native.cpp test/example.S -o test/example.native

说明编译成功, example.native 已经是一个可以在我的系统上运行的 ELF 文件:

  $ file test/example.native
  test/example.native: Mach-O 64-bit executable x86_64

运行它,输出的结果为:

  $ ./test/example.native
  68
  63
  10

关于 cmake 的基本概念,请参考官方文档.

cmake 相比于手写 Makefile 有以下优点:

1. 跨平台支持: cmake 可以生成不同平台下的 Makefile 或IDE项目,可以方便地在不同的操作系统上编译,构建和安装.
2. 自动依赖管理: cmake 能够自动地管理项目中的依赖,包括库文件和头文件等,减少了手动编写 Makefile 的繁琐过程.
3. 更简洁的语法:相比于 Makefile , cmake 的语法更为简洁,易于理解和维护.
4. 多配置支持: cmake 支持多配置构建,可以在一个项目中同时支持Debug和Release等多种构建模式.
5. IDE集成支持: cmake 可以生成各种主流IDE所需的项目文件,如Visual Studio,Xcode,Clion等,方便开发者在自己喜欢的IDE中开发项目.

总的来说, cmake 可以帮助开发者更轻松地管理和构建项目,提高开发效率,减少出错概率,具有良好的可移植性和可扩展性.

使用 cmake 的方式是为项目编写一个 CMakeLists.txt 文件.

以下是一个可以编译本项目的 CMakeLists.txt 文件内容:

  cmake_minimum_required(VERSION 3.10)
  project(toy-compiler)

  set(CMAKE_CXX_STANDARD 14)

  file(GLOB CPPS ${CMAKE_SOURCE_DIR}/*.cpp)

  # Find Flex and Bison packages
  find_package(FLEX REQUIRED)
  find_package(BISON REQUIRED)

  # Define the Flex and Bison input and output files
  flex_target(Scanner tokens.l ${CMAKE_SOURCE_DIR}/tokens.cpp)
  bison_target(Parser parser.y ${CMAKE_SOURCE_DIR}/parser.cpp)
  add_flex_bison_dependency(Scanner Parser)

  # Use customized LLVM
  find_package(Clang REQUIRED CONFIG HINTS ${LLVM_DIR} NO_DEFAULT_PATH)

  include_directories(${LLVM_INCLUDE_DIRS} ${CLANG_INCLUDE_DIRS} SYSTEM)
  link_directories(${LLVM_LIBRARY_DIRS})

  # Add the executable
  add_executable(compiler
          ${CPPS}
          ${BISON_Parser_OUTPUTS}
          ${FLEX_Scanner_OUTPUTS}
          )

  target_link_libraries(compiler
          LLVMX86AsmParser
          LLVMX86CodeGen
          LLVMAsmParser
          LLVMBitWriter
          LLVMRuntimeDyld
          LLVMExecutionEngine
          LLVMMCJIT
          z
          ncurses
          )

cmake 提供了一些宏来方便 flex 和 bison 的使用,这些宏包括: flex_target, bison_target, add_flex_bison_dependency 等,具体情况请参考官方文档.

因为在编写编译器的过程中用到了 LLVM 的许多功能,自然要把 LLVM 的库找到,并将他们链接到最后的二进制文件中,具体代码如下:

# Use customized LLVM
find_package(Clang REQUIRED CONFIG HINTS ${LLVM_DIR} NO_DEFAULT_PATH)

include_directories(${LLVM_INCLUDE_DIRS} ${CLANG_INCLUDE_DIRS} SYSTEM)
link_directories(${LLVM_LIBRARY_DIRS})

find_package 用来从 ${LLVM_DIR} 这个路径中寻找 Clang 相关的库路径,头文件路径等, include_directories 用来将找到的库路径,头文件路径添加到搜索路径中,使得在编译和链接时能找到相应的文件.

target_link_libraries 用于指定生成的二进制程序需要链接上哪些外部库.

给项目中添加了上述 CMakeLists.txt 文件后,项目可以正常编译运行.

find_package() 是 cmake 中的一个命令,用于在系统上查找已安装的软件包,并设置相关变量.这个命令主要用于在 cmake 构建系统中引入第三方库。

当使用 find_package() 命令查找软件包时, cmake 会在系统路径下查找该软件包，并设置相关变量,例如该软件包 的头文件路径,库文件路径,链接库等信息.一旦成功找到软件包,就可以将其与项目链接起来,使您的项目能够使用该软件 包提供的功能.

通常，使用 find_package() 命令需要执行以下步骤：

1. 在 CMakeLists.txt 文件中加入 find_package() 命令，例如： find_package(PackageName REQUIRED),这里

的 PackageName 是要查找的软件包名称,如果该软件包不存在或未安装, cmake 将会在输出中报告错误.如果软件包 存在, cmake 会设置相关变量,例如包含路径,库文件路径等

1. 在 CMakeLists.txt 文件中使用 include_directories() 命令或 target_include_directories() 命令将包>含路径添加到项目中

2. 使用 add_library() 或 add_executable() 命令将源文件与该软件包链接起来,例如:

   add_executable(MyApp main.cpp)
   target_link_libraries(MyApp PackageName)

   这里的 PackageName 是要使用的软件包名称

默认情况下, find_package 会从以下几个地方查找包：

1. CMAKE_PREFIX_PATH :这是一个用分号分隔的路径列表, cmake 会在这些路径中查找安装的包
2. 环境变量:如果在 CMAKE_PREFIX_PATH 中找不到包, cmake 会检查环境变量，例如在 linux 上, cmake 会>检查 PKG_CONFIG_PATH 变量
3. cmake 内置模块: cmake 附带了许多内置模块,用于查找常见的包,比如我们上面使用的 flex 和 bison
4. 模块路径: cmake 允许开发人员编写自己的模块并在 cmake 脚本中使用它们.如果包不在 CMAKE_PREFIX_PATH 或内置模块中,则 cmake 会查找用户定义的模块路径

find_package 会设置一些变量,以便用户在 CMakeLists.txt 文件中使用.这些变量包括:

1. <PackageName>_FOUND:用于指示是否找到了包
2. <PackageName>_INCLUDE_DIRS:用于包含头文件的路径
3. <PackageName>_LIBRARIES:用于链接库的路径
4. <PackageName>_DEFINITIONS:用于包含预定义宏的定义
5. <PackageName>_VERSION:包的版本号

这些变量可以在 CMakeLists.txt 文件中使用,以便正确地包含头文件,链接库等.

原始项目中,使用的是C++ 14的语法,但是 LLVM 16.0.0 使用了更新的C++标准,经过测试,C++ 20是可以编译通过的,所以我选择了C++20.

原始版本使用的是 LLVM 9.0.1_4 的接口,迁移到 LLVM 16.0.0 后,只需要将编译无法通过的接口适配一下既可.

原始项目产生的编译器会将源文件编译为 BitCode 文件,接着要么使用 llc 和 clang 将 BitCode 编译为可运行的二进制程序,要么使用 lli 解释执行 BitCode 文件.借鉴Kaleidoscope第八章,我们其实可以直接生成 .o 文件,后续再想办法将 .o 文件链接为可执行的二进制程序.

这一部分的代码直接参考了 Kaleidoscope,改动不是特别大.

1. 这个小项目目前还不支持分支等很多语法,需要陆续添加
2. 需要支持类型系统
3. 借鉴Kaleidoscope第四章 4.4. Adding a JIT Compiler 一节的最后一部分,使用现有的C库扩充函数
4. 加入一些函数式编程的语法
5. 优化内存管理

1. 编译器目前只支持生成 .o 文件,之后需要支持生成可执行的二进制文件,能跨平台更好了 事实上,这个功能是由链接器提供的,不过一般的编译器前端(本文也只是通过 flex 和 bison 实现了一个编译器前端)会调用 LLVM lld 的接口,来将生成的目标文件链接为可执行文件.

   例如,只需要将如下代码加在生成目标文件的代码之后,就可以将目标文件和标准库一起链接为一个二进制程序:

     const char *must_args[] = {
       "-demangle",
       "-lto_library",
       "/Applications/Xcode.app/Contents/Developer/Toolchains/"
       "XcodeDefault.xctoolchain/usr/lib/libLTO.dylib",
       "-no_deduplicate",
       "-dynamic",
       "-arch",
       "x86_64",
       "-platform_version",
       "macos",
       "13.0.0",
       "13.1",
       "-syslibroot",
       "/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/"
       "Developer/SDKs/MacOSX.sdk",
       "-o",
       "a.out",
       "-L/usr/local/lib",
       "-lSystem",
       "/Applications/Xcode.app/Contents/Developer/Toolchains/"
       "XcodeDefault.xctoolchain/usr/lib/clang/14.0.0/lib/darwin/"
       "libclang_rt.osx.a"
     };
     std::vector<const char *> args;
     args.push_back("placeholder");
     for (auto arg: must_args) {
       args.push_back(arg);
      }
     args.push_back("path/to/file1");
     args.push_back("path/to/file2");
     // ...
     return lld::macho::link(args, llvm::outs(), llvm::errs(), false, false);

   如何获取参数列表: 调用 lld::ARCH::link 最重要的步骤就是获取参数列表 args,我是通过实现了一个链接器桩来获取到这些参数,当然这些参数也不确保对所有的代码都适用.链接器桩代码如下:

     #include <stdio.h>
   
     int main(int argc, char **argv) {
       for (int i = 0; i < argc; i++) {
         printf("%s\n", argv[i]);
       }
   
       return 0;
     }

   这段代码只是把所有的参数打印出来,将这段代码编译为 myld,接着在使用 clang 或者 gcc 编译代码时,只要添加 -fuse-ld=/path/to/myld 参数,就能将编译器传递给链接器的所有参数打印出来.

   以上的参数列表只针对 macOS 平台,在不同平台上编译不同文件时, clang 或者 gcc 生成的参数列表可能都是不一样的,具体是如何获取这些参数的,就得看 clang 的实现了.

   关于跨平台的写法,可以参考 LLVM源码 中的 lld/tools/lld/lld.cpp 文件,这个工具的作用就是调用 LLVM 的链接器接口实现 lld 这个链接器.

2. 使用 LLVM 的 JIT 加入解释器的功能 因为还有更重要的事情,这条搁浅了