动手玩 LLVM

作者:戴铭,滴滴出行技术专家。最近正在研究 iOS 编译相关底层技术,用来解决工程优化问题。

介绍

LLVM 资料非常少,接触时难免会有种无从下手的感觉,现在很多相关文章都偏向理论,以前我写了篇《 深入剖析 iOS 编译 Clang / LLVM 》可以作为一个最基础深入前的理论入门,最近在 segmentfault 的一个直播(地址: https://segmentfault.com/l/1500000008514518)对先前文章里静态分析和编译器优化部分做了更加详细的解读。光看不练确实没啥用,本文希望能够通过一些具体的比如如何编译 LLVM 的工具链,使用工具链,熟悉 LLVM 各种接口库等来带大家进入 LLVM 的世界,能成为一名能够熟练运用倚天屠龙剑的屠龙战士。

LLVM 工具链

获取 LLVM

#先下载 LLVM
svn co http://llvm.org/svn/llvm-project/llvm/trunk llvm

#在 LLVM 的 tools 目录下下载 Clang
cd llvm/tools
svn co http://llvm.org/svn/llvm-project/cfe/trunk clang

#在 LLVM 的 projects 目录下下载 compiler-rt,libcxx,libcxxabi
cd ../projects
svn co http://llvm.org/svn/llvm-project/compiler-rt/trunk compiler-rt
svn co http://llvm.org/svn/llvm-project/libcxx/trunk libcxx
svn co http://llvm.org/svn/llvm-project/libcxxabi/trunk libcxxabi

#在 Clang 的 tools 下安装 extra 工具
cd ../tools/clang/tools
svn co http://llvm.org/svn/llvm-project/clang-tools-extra/trunk extra

编译 LLVM

brew install gcc
brew install cmake
mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Release -DBUILD_SHARED_LIBS=ON -DLLVM_TARGETS_TO_BUILD="AArch64;X86" -G "Unix Makefiles" ..
make j8
#安装
make install
#如果找不到标准库,Xcode 需要安装 xcode-select --install

#如果希望是 xcodeproject 方式 build 可以使用 -GXcode
mkdir xcodeBuild
cd xcodeBuild
cmake -GXcode /path/to/llvm/source

在 bin 下存放着工具链,有了这些工具链就能够完成源码编译了。

LLVM 源码工程目录介绍

  • llvm_examples_ - 使用 LLVM IR 和 JIT 的例子。
  • llvm_include_ - 导出的头文件。
  • llvm_lib_ - 主要源文件都在这里。
  • llvm_project_ - 创建自己基于 LLVM 的项目的目录。
  • llvm_test_ - 基于 LLVM 的回归测试,健全检察。
  • llvm_suite_ - 正确性,性能和基准测试套件。
  • llvm_tools_ - 基于 lib 构建的可以执行文件,用户通过这些程序进行交互,-help 可以查看各个工具详细使用。
  • llvm_utils_ - LLVM 源代码的实用工具,比如,查找 LLC 和 LLI 生成代码差异工具, Vim 或 Emacs 的语法高亮工具等。

lib 目录介绍

  • llvm_lib_IR/ - 核心类比如 Instruction 和 BasicBlock。
  • llvm_lib_AsmParser/ - 汇编语言解析器。
  • llvm_lib_Bitcode/ - 读取和写入字节码
  • llvm_lib_Analysis/ - 各种对程序的分析,比如 Call Graphs,Induction Variables,Natural Loop Identification 等等。
  • llvm_lib_Transforms/ - IR-to-IR 程序的变换。
  • llvm_lib_Target/ - 对像 X86 这样机器的描述。
  • llvm_lib_CodeGen/ - 主要是代码生成,指令选择器,指令调度和寄存器分配。
  • llvm_lib_ExecutionEngine/ - 在解释执行和JIT编译场景能够直接在运行时执行字节码的库。

工具链命令介绍

基本命令

  • llvm-as - 汇编器,将 .ll 汇编成字节码。
  • llvm-dis - 反汇编器,将字节码编成可读的 .ll 文件。
  • opt - 字节码优化器。
  • llc - 静态编译器,将字节码编译成汇编代码。
  • lli - 直接执行 LLVM 字节码。
  • llvm-link - 字节码链接器,可以把多个字节码文件链接成一个。
  • llvm-ar - 字节码文件打包器。
  • llvm-lib - LLVM lib.exe 兼容库工具。
  • llvm-nm - 列出字节码和符号表。
  • llvm-config - 打印 LLVM 编译选项。
  • llvm-diff - 对两个进行比较。
  • llvm-cov - 输出 coverage infomation。
  • llvm-profdata - Profile 数据工具。
  • llvm-stress - 生成随机 .ll 文件。
  • llvm-symbolizer - 地址对应源码位置,定位错误。
  • llvm-dwarfdump - 打印 DWARF。

调试工具

  • bugpoint - 自动测试案例工具
  • llvm-extract - 从一个 LLVM 的模块里提取一个函数。
  • llvm-bcanalyzer - LLVM 字节码分析器。

开发工具

  • FileCheck - 灵活的模式匹配文件验证器。
  • tblgen - C++ 代码生成器。
  • lit - LLVM 集成测试器。
  • llvm-build - LLVM 构建工程时需要的工具。
  • llvm-readobj - LLVM Object 结构查看器。

Driver

动手玩的话,特别是想要使用这些工具链之前最好先了解我们和 LLVM 交互的实现。那么这部分就介绍下 LLVM 里的 Driver。

Driver 是 Clang 面对用户的接口,用来解析 Option 设置,判断决定调用的工具链,最终完成整个编译过程。

相关源代码在这里:clang_tools_driver/driver.cpp

整个 Driver 源码的入口函数就是 driver.cpp 里的 main() 函数。从这里可以作为入口看看整个 driver 是如何工作的,这样更利于我们以后轻松动手驾驭 LLVM。

int main(int argc_, const char **argv_) {
  llvm::sys::PrintStackTraceOnErrorSignal(argv_[0]);
  llvm::PrettyStackTraceProgram X(argc_, argv_);
  llvm::llvm_shutdown_obj Y; // Call llvm_shutdown() on exit.

  if (llvm::sys::Process::FixupStandardFileDescriptors())
    return 1;

  SmallVector<const char *, 256> argv;
  llvm::SpecificBumpPtrAllocator<char> ArgAllocator;
  std::error_code EC = llvm::sys::Process::GetArgumentVector(
      argv, llvm::makeArrayRef(argv_, argc_), ArgAllocator);
  if (EC) {
    llvm::errs() << "error: couldn't get arguments: " << EC.message() << '\n';
    return 1;
  }

  llvm::InitializeAllTargets();
  std::string ProgName = argv[0];
  std::pair<std::string, std::string> TargetAndMode =
      ToolChain::getTargetAndModeFromProgramName(ProgName);

  llvm::BumpPtrAllocator A;
  llvm::StringSaver Saver(A);

    //省略
  ...

  // If we have multiple failing commands, we return the result of the first
  // failing command.
  return Res;
}

Driver 的工作流程图

在 driver.cpp 的 main 函数里有 Driver 的初始化。我们来看看和 driver 相关的代码

  Driver TheDriver(Path, llvm::sys::getDefaultTargetTriple(), Diags);
  SetInstallDir(argv, TheDriver, CanonicalPrefixes);

  insertTargetAndModeArgs(TargetAndMode.first, TargetAndMode.second, argv,
                          SavedStrings);

  SetBackdoorDriverOutputsFromEnvVars(TheDriver);

  std::unique_ptr<Compilation> C(TheDriver.BuildCompilation(argv));
  int Res = 0;
  SmallVector<std::pair<int, const Command *>, 4> FailingCommands;
  if (C.get())
    Res = TheDriver.ExecuteCompilation(*C, FailingCommands);

  // Force a crash to test the diagnostics.
  if (::getenv("FORCE_CLANG_DIAGNOSTICS_CRASH")) {
    Diags.Report(diag::err_drv_force_crash) << "FORCE_CLANG_DIAGNOSTICS_CRASH";

    // Pretend that every command failed.
    FailingCommands.clear();
    for (const auto &J : C->getJobs())
      if (const Command *C = dyn_cast<Command>(&J))
        FailingCommands.push_back(std::make_pair(-1, C));
  }

  for (const auto &P : FailingCommands) {
    int CommandRes = P.first;
    const Command *FailingCommand = P.second;
    if (!Res)
      Res = CommandRes;

    // If result status is < 0, then the driver command signalled an error.
    // If result status is 70, then the driver command reported a fatal error.
    // On Windows, abort will return an exit code of 3.  In these cases,
    // generate additional diagnostic information if possible.
    bool DiagnoseCrash = CommandRes < 0 || CommandRes == 70;
#ifdef LLVM_ON_WIN32
    DiagnoseCrash |= CommandRes == 3;
#endif
    if (DiagnoseCrash) {
      TheDriver.generateCompilationDiagnostics(*C, *FailingCommand);
      break;
    }
  }

可以看到初始化 Driver 后 driver 会调用 BuildCompilation 生成 Compilation。Compilation 字面意思是合集的意思,通过 driver.cpp 的 include 可以看到

#include "clang/Driver/Compilation.h"

根据此路径可以细看下 Compilation 这个为了 driver 设置的一组任务的类。通过这个类我们提取里面这个阶段比较关键的几个信息出来

class Compilation {
    /// The original (untranslated) input argument list.
  llvm::opt::InputArgList *Args;

  /// The driver translated arguments. Note that toolchains may perform their
  /// own argument translation.
  llvm::opt::DerivedArgList *TranslatedArgs;
  /// The driver we were created by.
  const Driver &TheDriver;

  /// The default tool chain.
  const ToolChain &DefaultToolChain;
 ...
  /// The list of actions.  This is maintained and modified by consumers, via
  /// getActions().
  ActionList Actions;

  /// The root list of jobs.
  JobList Jobs;
    ...
public:
    ...
  const Driver &getDriver() const { return TheDriver; }

  const ToolChain &getDefaultToolChain() const { return DefaultToolChain; }
    ...
  ActionList &getActions() { return Actions; }
  const ActionList &getActions() const { return Actions; }
    ...
  JobList &getJobs() { return Jobs; }
  const JobList &getJobs() const { return Jobs; }

  void addCommand(std::unique_ptr<Command> C) { Jobs.addJob(std::move(C)); }
    ...
  /// ExecuteCommand - Execute an actual command.
  ///
  /// \param FailingCommand - For non-zero results, this will be set to the
  /// Command which failed, if any.
  /// \return The result code of the subprocess.
  int ExecuteCommand(const Command &C, const Command *&FailingCommand) const;

  /// ExecuteJob - Execute a single job.
  ///
  /// \param FailingCommands - For non-zero results, this will be a vector of
  /// failing commands and their associated result code.
  void ExecuteJobs(
      const JobList &Jobs,
      SmallVectorImpl<std::pair<int, const Command *>> &FailingCommands) const;
    ...
};

通过这些关键定义再结合 BuildCompilation 函数的实现可以看出这个 Driver 的流程是按照 ArgList - Actions - Jobs 来的,完整的图如下:

Parse

看完完整的 Driver 流程后,我们就先从 Parse 开始说起。

Parse 是解析选项,对应的代码在 ParseArgStrings 这个函数里。

下面通过执行一个试试,比如 clang -### main.c -ITheOptionWeAdd

这里的 -I 是 Clang 支持的,在 Clang 里是 Option 类,Clang 会对这些 Option 专门的进行解析,使用一种 DSL 语言将其转成 .tb 文件后使用 table-gen 转成 C++ 语言和其它代码一起进行编译。

Driver 层会解析我们传入的 -I Option 参数。

-x 后加个 c 表示是对 c 语言进行编译,Clang Driver 通过文件的后缀 .c 来自动加上这个 参数的。如果是 c++ 语言,仅仅通过在 -x 后添加 cpp 编译还是会出错的。

clang -x c++ main.cpp

通过报错信息可以看出一些链接错误

因为需要链接 C++ 标准库,所以加上参数 -lc++ 就可以了

clang -x c++ -lc++ main.cpp

那么 clang++ 和 clang 命令的区别就在于会加载 C++ 库,其实 clang++ 最终还是会调用 Clang,那么手动指定加载库就好了何必还要多个 clang++ 命令呢,这主要是为了能够在这个命令里去加载更多的库,除了标准库以外,还有些非 C++ 标准库,辅助库等等。这样只要是 C++ 的程序用 clang++ 够了。

只有加上 -cc1 这个 option 才能进入到 Clang driver 比如 emit-obj 这个 option 就需要先加上 -cc1。

这点可以通过 driver.cpp 源码来看,在 main() 函数里可以看到在做了些多平台的兼容处理后就开始进行对入参判断第一个是不是 -cc1。

if (MarkEOLs && argv.size() > 1 && StringRef(argv[1]).startswith("-cc1"))
    MarkEOLs = false;
  llvm::cl::ExpandResponseFiles(Saver, Tokenizer, argv, MarkEOLs);

  // 处理 -cc1 集成工具
  auto FirstArg = std::find_if(argv.begin() + 1, argv.end(),
                               [](const char *A) { return A != nullptr; });
  if (FirstArg != argv.end() && StringRef(*FirstArg).startswith("-cc1")) {
    // 如果 -cc1 来自 response file, 移除 EOL sentinels
    if (MarkEOLs) {
      auto newEnd = std::remove(argv.begin(), argv.end(), nullptr);
      argv.resize(newEnd - argv.begin());
    }
    return ExecuteCC1Tool(argv, argv[1] + 4);
  }

如果是 -cc1 的话会调用 ExecuteCC1Tool 这个函数,先看看这个函数

static int ExecuteCC1Tool(ArrayRef<const char *> argv, StringRef Tool) {
  void *GetExecutablePathVP = (void *)(intptr_t) GetExecutablePath;
  if (Tool == "")
    return cc1_main(argv.slice(2), argv[0], GetExecutablePathVP);
  if (Tool == "as")
    return cc1as_main(argv.slice(2), argv[0], GetExecutablePathVP);

  // 拒绝未知工具
  llvm::errs() << "error: unknown integrated tool '" << Tool << "'\n";
  return 1;
}

最终的执行会执行 cc1-main 或者 cc1as_main 。这两个函数分别在 driver.cpp 同级目录里的 cc1_main.cpp 和 cc1as_main.cpp 中。

下面看看有哪些解析 Args 的方法

  • ParseAnalyzerArgs - 解析出静态分析器 option
  • ParseMigratorArgs - 解析 Migrator option
  • ParseDependencyOutputArgs - 解析依赖输出 option
  • ParseCommentArgs - 解析注释 option
  • ParseFileSystemArgs - 解析文件系统 option
  • ParseFrontendArgs - 解析前端 option
  • ParseTargetArgs - 解析目标 option
  • ParseCodeGenArgs - 解析 CodeGen 相关的 option
  • ParseHeaderSearchArgs - 解析 HeaderSearch 对象相关初始化相关的 option
  • parseSanitizerKinds - 解析 Sanitizer Kinds
  • ParsePreprocessorArgs - 解析预处理的 option
  • ParsePreprocessorOutputArgs - 解析预处理输出的 option

Pipeline

Pipeline 这里可以添加 -ccc-print-phases 看到进入 Pipeline 以后的事情。

这些如 -ccc-print-phases 这样的 option 在编译时会生成.inc 这样的 C++ TableGen 文件。在 Options.td 可以看到全部的 option 定义。

在 Clang 的 Pipeline 中很多实际行为都有对应的 Action,比如 preprocessor 时提供文件的 InputAction 和用于绑定机器架构的 BindArchAction。

使用 clang main.c -arch i386 -arch x86_64 -o main 然后 file main 能够看到这时 BindArchAction 这个 Action 起到了作用,编译链接了两次同时创建了一个库既能够支持32位也能够支持64位用 lipo 打包。

Action

/// BuildActions - Construct the list of actions to perform for the
  /// given arguments, which are only done for a single architecture.
  ///
  /// \param C - The compilation that is being built.
  /// \param Args - The input arguments.
  /// \param Actions - The list to store the resulting actions onto.
  void BuildActions(Compilation &C, llvm::opt::DerivedArgList &Args,
                    const InputList &Inputs, ActionList &Actions) const;

  /// BuildUniversalActions - Construct the list of actions to perform
  /// for the given arguments, which may require a universal build.
  ///
  /// \param C - The compilation that is being built.
  /// \param TC - The default host tool chain.
  void BuildUniversalActions(Compilation &C, const ToolChain &TC,
                             const InputList &BAInputs) const;

上面两个方法中 BuildUniversalActions 最后也会走 BuildActions。BuildActions 了,进入这个方法

void Driver::BuildActions(Compilation &C, DerivedArgList &Args,
                          const InputList &Inputs, ActionList &Actions) const {
  llvm::PrettyStackTraceString CrashInfo("Building compilation actions");

  if (!SuppressMissingInputWarning && Inputs.empty()) {
    Diag(clang::diag::err_drv_no_input_files);
    return;
  }

  Arg *FinalPhaseArg;
  phases::ID FinalPhase = getFinalPhase(Args, &FinalPhaseArg);

接着跟 getFinalPhase 这个方法。

// -{E,EP,P,M,MM} only run the preprocessor.
  if (CCCIsCPP() || (PhaseArg = DAL.getLastArg(options::OPT_E)) ||
      (PhaseArg = DAL.getLastArg(options::OPT__SLASH_EP)) ||
      (PhaseArg = DAL.getLastArg(options::OPT_M, options::OPT_MM)) ||
      (PhaseArg = DAL.getLastArg(options::OPT__SLASH_P))) {
    FinalPhase = phases::Preprocess;

    // -{fsyntax-only,-analyze,emit-ast} only run up to the compiler.
  } else if ((PhaseArg = DAL.getLastArg(options::OPT_fsyntax_only)) ||
             (PhaseArg = DAL.getLastArg(options::OPT_module_file_info)) ||
             (PhaseArg = DAL.getLastArg(options::OPT_verify_pch)) ||
             (PhaseArg = DAL.getLastArg(options::OPT_rewrite_objc)) ||
             (PhaseArg = DAL.getLastArg(options::OPT_rewrite_legacy_objc)) ||
             (PhaseArg = DAL.getLastArg(options::OPT__migrate)) ||
             (PhaseArg = DAL.getLastArg(options::OPT__analyze,
                                        options::OPT__analyze_auto)) ||
             (PhaseArg = DAL.getLastArg(options::OPT_emit_ast))) {
    FinalPhase = phases::Compile;

    // -S only runs up to the backend.
  } else if ((PhaseArg = DAL.getLastArg(options::OPT_S))) {
    FinalPhase = phases::Backend;

    // -c compilation only runs up to the assembler.
  } else if ((PhaseArg = DAL.getLastArg(options::OPT_c))) {
    FinalPhase = phases::Assemble;

    // Otherwise do everything.
  } else
    FinalPhase = phases::Link;

看完这段代码就会发现其实每次的 option 都会完整的走一遍从预处理,静态分析,backend 再到汇编的过程。

下面列下一些编译器的前端 Action,大家可以一个个用着玩。

  • InitOnlyAction - 只做前端初始化,编译器 option 是 -init-only
  • PreprocessOnlyAction - 只做预处理,不输出,编译器的 option 是 -Eonly
  • PrintPreprocessedAction - 做预处理,子选项还包括-P、-C、-dM、-dD 具体可以查看PreprocessorOutputOptions 这个类,编译器 option 是 -E
  • RewriteIncludesAction - 预处理
  • DumpTokensAction - 打印token,option 是 -dump-tokens
  • DumpRawTokensAction - 输出原始tokens,包括空格符,option 是 -dump-raw-tokens
  • RewriteMacrosAction - 处理并扩展宏定义,对应的 option 是 -rewrite-macros
  • HTMLPrintAction - 生成高亮的代码网页,对应的 option 是 -emit-html
  • DeclContextPrintAction - 打印声明,option 对应的是 -print-decl-contexts
  • ASTDeclListAction - 打印 AST 节点,option 是 -ast-list
  • ASTDumpAction - 打印 AST 详细信息,对应 option 是 -ast-dump
  • ASTViewAction - 生成 AST dot 文件,能够通过 Graphviz 来查看图形语法树。 option 是 -ast-view
  • AnalysisAction - 运行静态分析引擎,option 是 -analyze
  • EmitLLVMAction - 生成可读的 IR 中间语言文件,对应的 option 是 -emit-llvm
  • EmitBCAction - 生成 IR Bitcode 文件,option 是 -emit-llvm-bc
  • MigrateSourceAction - 代码迁移,option 是 -migrate

Bind

Bind 主要是与工具链 ToolChain 交互
根据创建的那些 Action,在 Action 执行时 Bind 来提供使用哪些工具,比如生成汇编时是使用内嵌的还是 GNU 的,还是其它的呢,这个就是由 Bind 来决定的,具体使用的工具有各个架构,平台,系统的 ToolChain 来决定。

通过 clang -ccc-print-bindings main.c -o main 来看看 Bind 的结果

可以看到编译选择的是 clang,链接选择的是 darwin::Linker,但是在链接时前没有汇编器的过程,这个就是 Bind 起了作用,它会根据不同的平台来决定选择什么工具,因为是在 Mac 系统里 Bind 就会决定使用 integrated-as 这个内置汇编器。那么如何在不用内置汇编器呢。可以使用 -fno-integrated-as 这个 option。

Translate

Translate 就是把相关的参数对应到不同平台上不同的工具。

Jobs

从创建 Jobs 的方法

/// BuildJobsForAction - Construct the jobs to perform for the action \p A and
  /// return an InputInfo for the result of running \p A.  Will only construct
  /// jobs for a given (Action, ToolChain, BoundArch, DeviceKind) tuple once.
  InputInfo
  BuildJobsForAction(Compilation &C, const Action *A, const ToolChain *TC,
                     StringRef BoundArch, bool AtTopLevel, bool MultipleArchs,
                     const char *LinkingOutput,
                     std::map<std::pair<const Action *, std::string>, InputInfo>
                         &CachedResults,
                     Action::OffloadKind TargetDeviceOffloadKind) const;

可以看出 Jobs 需要前面的 Compilation,Action,ToolChain 等,那么 Jobs 就是将前面获取的信息进行组合分组给后面的 Execute 做万全准备。

Execute

在 driver.cpp 的 main 函数里的 ExecuteCompilation 方法里可以看到如下代码:

 // Set up response file names for each command, if necessary
  for (auto &Job : C.getJobs())
    setUpResponseFiles(C, Job);

  C.ExecuteJobs(C.getJobs(), FailingCommands);

能够看到 Jobs 准备好了后就要开始 Excute 他们。

Execute 就是执行整个的编译过程的 Jobs。过程执行的内容和耗时可以通过添加 -ftime-report 这个 option 来看到。

使用工具链

编译 c 程序

#include <stdio.h>
int main() {
    int a,b;
    printf(Please input a:);
    scanf(%d,&a);
    printf(Please input b:);
    scanf(%d,&b);
    printf(a is:%d,b is :%d,count equal:%d,a,b,a+b);
}
clang main.c -o main

生成 Bitcode

编译生成 Bitcode,JIT Compiler 运行字节码文件

clang -O3 -emit-llvm main.c -c -o main.bc
lli main.bc

生成可视化 Bitcode

clang -O3 -emit-llvm main.c -S -o main.ll

反汇编字节码

llc main.bc -o main.s
    .section    __TEXT,__text,regular,pure_instructions
    .macosx_version_min 10, 12
    .globl  _main
    .p2align    4, 0x90
_main:                                  ##
    .cfi_startproc
## BB#0:                                ## %entry
    pushq   %rbp
Lcfi0:
    .cfi_def_cfa_offset 16
Lcfi1:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
Lcfi2:
    .cfi_def_cfa_register %rbp
    pushq   %rbx
    pushq   %rax
Lcfi3:
    .cfi_offset %rbx, -24
    leaq    L_.str(%rip), %rdi
    xorl    %eax, %eax
    callq   _printf
    leaq    L_.str.1(%rip), %rbx
    leaq    -16(%rbp), %rsi
    xorl    %eax, %eax
    movq    %rbx, %rdi
    callq   _scanf
    leaq    L_.str.2(%rip), %rdi
    xorl    %eax, %eax
    callq   _printf
    leaq    -12(%rbp), %rsi
    xorl    %eax, %eax
    movq    %rbx, %rdi
    callq   _scanf
    movl    -16(%rbp), %esi
    movl    -12(%rbp), %edx
    leal    (%rdx,%rsi), %ecx
    leaq    L_.str.3(%rip), %rdi
    xorl    %eax, %eax
                                        ## kill: %ESI<def> %ESI<kill> %RSI<kill>
                                        ## kill: %EDX<def> %EDX<kill> %RDX<kill>
    callq   _printf
    xorl    %eax, %eax
    addq    $8, %rsp
    popq    %rbx
    popq    %rbp
    retq
    .cfi_endproc

    .section    __TEXT,__cstring,cstring_literals
L_.str:                                 ## @.str
    .asciz  "Please input a:"

L_.str.1:                               ## @.str.1
    .asciz  "%d"

L_.str.2:                               ## @.str.2
    .asciz  "Please input b:"

L_.str.3:                               ## @.str.3
    .asciz  "a is:%d,b is :%d,count equal:%d"


.subsections_via_symbols

分析可执行文件

前面几行汇编指令

    .section    __TEXT,__text,regular,pure_instructions
    .macosx_version_min 10, 12
    .globl  _main
    .p2align    4, 0x90
  • section - 指令指定接下来是执行哪个段。
  • globl - 指令说明 _main 是一个外部符号,main() 对于系统来说是可调用执行文件的。
  • align - 指出后面代码的对齐方式,16(2^4) 字节对齐, 0x90 补齐。

main 函数头部部分

_main:                                  ##
    .cfi_startproc
## BB#0:                                ## %entry
    pushq   %rbp
Lcfi0:
    .cfi_def_cfa_offset 16
Lcfi1:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
Lcfi2:
    .cfi_def_cfa_register %rbp
    pushq   %rbx
    pushq   %rax
  • _main - 是函数开始的地址。
  • .cfi_startproc 和 .cfi_endproc - 配对出现,前者表示函数的开始,后者表示函数的结束。CFI 是 Call Frame Infomation 的缩写,调用帧信息的意思。
  • pushq %rbp - 汇编代码,指把 rbp 的值 push 到栈中。在 ## BB#0 这个 label 里 ABI 会让 rbp 这个寄存器被保护起来,函数返回时让 rbp 寄存器的值跟以前一样。ABI 它指定函数调用是如何在汇编代码层面上工作。
  • .cfi_def_cfa_offset 16 和 .cfi_offset %rbp, -16 - 输出堆栈和调试信息。
  • movq %rsp, %rbp - 把局部变量放到栈上。

打印部分

    leaq    L_.str(%rip), %rdi
    xorl    %eax, %eax
    callq   _printf
  • leap 会将 L_.str(%rip) 加载到 rax 寄存器里。在 .section TEXT,cstring,cstring_literals 区域可以看到 L_.str,L_.str.1,L_.str.2 等字符串的定义。
  • callq 会调用 print() 函数。

LLVM IR 中间代码

不管编译的语言时 Objective-C 还是 Swift 也不管对应机器是什么,亦或是即时编译,LLVM 里唯一不变的是中间语言 LLVM IR。那么我们就来看看如何玩 LLVM IR。

IR 结构

下面是刚才生成的 main.ll 中间代码文件。

; ModuleID = ‘main.c’
source_filename = “main.c”
target datalayout = “e-m:o-i64:64-f80:128-n8:16:32:64-S128”
target triple = “x86_64-apple-macosx10.12.0”

@.str = private unnamed_addr constant [16 x i8] c”Please input a:\00”, align 1
@.str.1 = private unnamed_addr constant [3 x i8] c”%d\00”, align 1
@.str.2 = private unnamed_addr constant [16 x i8] c”Please input b:\00”, align 1
@.str.3 = private unnamed_addr constant [32 x i8] c”a is:%d,b is :%d,count equal:%d\00”, align 1

; Function Attrs: nounwind ssp uwtable
define i32() #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  %3 = bitcast i32* %1 to i8*
  call void.lifetime.start(i64 4, i8* %3) #3
  %4 = bitcast i32* %2 to i8*
  call void.lifetime.start(i64 4, i8* %4) #3
  %5 = tail call i32 (i8*, …)(i8* getelementptr inbounds ([16 x i8], [16 x i8]* @.str, i64 0, i64 0))
  %6 = call i32 (i8*, …)(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str.1, i64 0, i64 0), i32* nonnull %1)
  %7 = call i32 (i8*, …)(i8* getelementptr inbounds ([16 x i8], [16 x i8]* @.str.2, i64 0, i64 0))
  %8 = call i32 (i8*, …)(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str.1, i64 0, i64 0), i32* nonnull %2)
  %9 = load i32, i32* %1, align 4, !tbaa !2
  %10 = load i32, i32* %2, align 4, !tbaa !2
  %11 = add nsw i32 %10, %9
  %12 = call i32 (i8*, …)(i8* getelementptr inbounds ([32 x i8], [32 x i8]* @.str.3, i64 0, i64 0), i32 %9, i32 %10, i32 %11)
  call void.lifetime.end(i64 4, i8* %4) #3
  call void.lifetime.end(i64 4, i8* %3) #3
  ret i32 0
}

; Function Attrs: argmemonly nounwind
declare void.lifetime.start(i64, i8* nocapture) #1

; Function Attrs: nounwind
declare i32(i8* nocapture readonly, …) #2

; Function Attrs: nounwind
declare i32(i8* nocapture readonly, …) #2

; Function Attrs: argmemonly nounwind
declare void.lifetime.end(i64, i8* nocapture) #1

attributes #0 = { nounwind ssp uwtable “disable-tail-calls”=“false” “less-precise-fpmad”=“false” “no-frame-pointer-elim”=“true” “no-frame-pointer-elim-non-leaf” “no-infs-fp-math”=“false” “no-nans-fp-math”=“false” “stack-protector-buffer-size”=“8” “target-cpu”=“penryn” “target-features”=“+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3” “unsafe-fp-math”=“false” “use-soft-float”=“false” }
attributes #1 = { argmemonly nounwind }
attributes #2 = { nounwind “disable-tail-calls”=“false” “less-precise-fpmad”=“false” “no-frame-pointer-elim”=“true” “no-frame-pointer-elim-non-leaf” “no-infs-fp-math”=“false” “no-nans-fp-math”=“false” “stack-protector-buffer-size”=“8” “target-cpu”=“penryn” “target-features”=“+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3” “unsafe-fp-math”=“false” “use-soft-float”=“false” }
attributes #3 = { nounwind }

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

!0 = !{i32 1, !”PIC Level”, i32 2}
!1 = !{!”Apple LLVM version 8.0.0 (clang-800.0.42.1)”}
!2 = !{!3, !3, i64 0}
!3 = !{!”int”, !4, i64 0}
!4 = !{!”omnipotent char”, !5, i64 0}
!5 = !{!”Simple C/C++ TBAA”}

LLVM IR 有三种表示格式,第一种是 bitcode 这样的存储格式,以 .bc 做后缀,第二种是可读的以 .ll,第三种是用于开发时操作 LLVM IR 的内存格式。

一个编译的单元即一个文件在 IR 里就是一个 Module,Module 里有 Global Variable 和 Function,在 Function里有 Basic Block,Basic Block 里有 指令 Instructions。

通过下面的 IR 结构图能够更好的理解 IR 的整体结构。

图中可以看出最大的是 Module,里面包含多个 Function,每个 Function 包含多个 BasicBlock,BasicBlock 里含有 Instruction,代码非常清晰,这样如果想开发一个新语言只需要完成语法解析后通过 LLVM 提供的丰富接口在内存中生成 IR 就可以直接运行在各个不同的平台。

IR 语言满足静态单赋值,可以很好的降低数据流分析和控制流分析的复杂度。及只能在定义时赋值,后面不能更改。但是这样就没法写程序了,输入输出都没法弄,所以函数式编程才会有类似 Monad 这样机制的原因。

LLVM IR 优化

使用 O2,O3 这样的优化会调用对应的 Pass 来进行处理,有比如类似死代码清理,内联化,表达式重组,循环变量移动这样的 Pass。可以通过 llvm-opt 调用 LLVM 优化相关的库。

可能直接这么说不太直观,我们可以更改下原 c 代码举个小例子看看这些 Pass 会做哪些优化。当我们加上

int i = 0;
while (i < 10) {
    i++;
    printf("%d",i);
}

对应的 IR 代码是

  %call4 = call i32 (i8*, ...)(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str.1, i64 0, i64 0), i32 1)
  %call4.1 = call i32 (i8*, ...)(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str.1, i64 0, i64 0), i32 2)
  %call4.2 = call i32 (i8*, ...)(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str.1, i64 0, i64 0), i32 3)
  %call4.3 = call i32 (i8*, ...)(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str.1, i64 0, i64 0), i32 4)
  %call4.4 = call i32 (i8*, ...)(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str.1, i64 0, i64 0), i32 5)
  %call4.5 = call i32 (i8*, ...)(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str.1, i64 0, i64 0), i32 6)
  %call4.6 = call i32 (i8*, ...)(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str.1, i64 0, i64 0), i32 7)
  %call4.7 = call i32 (i8*, ...)(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str.1, i64 0, i64 0), i32 8)
  %call4.8 = call i32 (i8*, ...)(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str.1, i64 0, i64 0), i32 9)
  %call4.9 = call i32 (i8*, ...)(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str.1, i64 0, i64 0), i32 10)

可以看出来这个 while 在 IR 中就是重复的打印了10次,那要是我把10改成100是不是会变成打印100次呢?

我们改成100后,再次生成 IR 可以看到 IR 变成了这样:

  br label %while.body

while.body:                                       ; preds = %while.body, %entry
  %i.010 = phi i32 [ 0, %entry ], [ %inc, %while.body ]
  %inc = add nuw nsw i32 %i.010, 1
  %call4 = call i32 (i8*, ...)(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @.str.1, i64 0, i64 0), i32 %inc)
  %exitcond = icmp eq i32 %inc, 100
  br i1 %exitcond, label %while.end, label %while.body

while.end:                                        ; preds = %while.body
  %2 = load i32, i32* %a, align 4, !tbaa !2
  %3 = load i32, i32* %b, align 4, !tbaa !2
  %add = add nsw i32 %3, %2
  %call5 = call i32 (i8*, ...)(i8* getelementptr inbounds ([11 x i8], [11 x i8]* @.str.3, i64 0, i64 0), i32 %add)
  call void.lifetime.end(i64 4, i8* nonnull %1) #3
  call void.lifetime.end(i64 4, i8* nonnull %0) #3
  ret i32 0
}

这里对不同条件生成的不同都是 Pass 优化器做的事情。解读上面这段 IR 需要先了解下 IR 语法关键字,如下:

  • @ - 代表全局变量
  • % - 代表局部变量
  • alloca - 指令在当前执行的函数的堆栈帧中分配内存,当该函数返回到其调用者时,将自动释放内存。
  • i32:- i 是几这个整数就会占几位,i32就是32位4字节
  • align - 对齐,比如一个 int,一个 char 和一个 int。单个 int 占4个字节,为了对齐只占一个字节的 char需要向4对齐占用4字节空间。
  • Load - 读出,store 写入
  • icmp - 两个整数值比较,返回布尔值
  • br - 选择分支,根据 cond 来转向 label,不根据条件跳转的话类似 goto
  • indirectbr - 根据条件间接跳转到一个 label,而这个 label 一般是在一个数组里,所以跳转目标是可变的,由运行时决定的
  • label - 代码标签
br label %while.body

如上面表述,br 会选择跳向 while.body 定义的这个标签。这个标签里可以看到

%exitcond = icmp eq i32 %inc, 100
  br i1 %exitcond, label %while.end, label %while.body

这段,icmp 会比较当前的 %inc 和定义的临界值 100,根据返回的布尔值来决定 br 跳转到那个代码标签,真就跳转到 while.end 标签,否就在进入 while.body 标签。这就是 while 的逻辑。通过br 跳转和 label 这种标签的概念使得 IR 语言能够成为更低级兼容性更高更方便转向更低级语言的语言。

SSA

LLVM IR 是 SSA 形式的,维护双向 def-use 信息,use-def 是通过普通指针实现信息维护,def-use 是通过内存跳表和链表来实现的,便于 forward dataflow analysis 和 backward dataflow analysis。可以通过 ADCE 这个 Pass 来了解下 backward dataflow,这个pass 的源文件在 lib_Transforms_Scalar/ADCE.cpp 中,ADCE 实现了 Aggressive Dead Code Elimination Pass。这个 Pass 乐观地假设所有 instructions 都是 Dead 直到证明是否定的,允许它消除其他 DCE Pass 的 Dead 计算 catch,特别是涉及循环计算。其它 DCE 相关的 Pass 可以查看同级目录下的 BDCE.cpp 和 DCE.cpp,目录下其它的 Pass 都是和数据流相关的分析包含了各种分析算法和思路。

那么看看加法这个操作的相关的 IR 代码

%2 = load i32, i32* %a, align 4, !tbaa !2
%3 = load i32, i32* %b, align 4, !tbaa !2
%add = add nsw i32 %3, %2

加法对应的指令是

BinaryOperator::CreateAdd(Value *V1, Value *V2, const Twine &Name)

两个输入 V1 和 V2 的 def-use 是如何的呢,看看如下代码

class Value {
  void addUse(Use &U) { U.addToList(&UseList); }

  // ...
};

class Use {
  Value *Val;
  Use *Next;
  PointerIntPair<Use **, 2, PrevPtrTag> Prev;

  // ...
};

void Use::set(Value *V) {
  if (Val) removeFromList();
  Val = V;
  if (V) V->addUse(*this);
}

Value *Use::operator=(Value *RHS) {
  set(RHS);
  return RHS;
}

class User : public Value {
  template <int Idx, typename U> static Use &OpFrom(const U *that) {
    return Idx < 0
      ? OperandTraits<U>::op_end(const_cast<U*>(that))[Idx]
      : OperandTraits<U>::op_begin(const_cast<U*>(that))[Idx];
  }
  template <int Idx> Use &Op() {
    return OpFrom<Idx>(this);
  }
  template <int Idx> const Use &Op() const {
    return OpFrom<Idx>(this);
  }

  // ...
};

class Instruction : public User,
                    public ilist_node_with_parent<Instruction, BasicBlock> {
  // ...
};

class BinaryOperator : public Instruction {
  /// Construct a binary instruction, given the opcode and the two
  /// operands.  Optionally (if InstBefore is specified) insert the instruction
  /// into a BasicBlock right before the specified instruction.  The specified
  /// Instruction is allowed to be a dereferenced end iterator.
  ///
  static BinaryOperator *Create(BinaryOps Op, Value *S1, Value *S2,
                                const Twine &Name = Twine(),
                                Instruction *InsertBefore = nullptr);

  // ...
};

BinaryOperator::BinaryOperator(BinaryOps iType, Value *S1, Value *S2,
                               Type *Ty, const Twine &Name,
                               Instruction *InsertBefore)
  : Instruction(Ty, iType,
                OperandTraits<BinaryOperator>::op_begin(this),
                OperandTraits<BinaryOperator>::operands(this),
                InsertBefore) {
  Op<0>() = S1;
  Op<1>() = S2;
  init(iType);
  setName(Name);
}

BinaryOperator *BinaryOperator::Create(BinaryOps Op, Value *S1, Value *S2,
                                       const Twine &Name,
                                       Instruction *InsertBefore) {
  assert(S1->getType() == S2->getType() &&
         "Cannot create binary operator with two operands of differing type!");
  return new BinaryOperator(Op, S1, S2, S1->getType(), Name, InsertBefore);
}

从代码里可以看出是使用了 Use 对象来把 use 和 def 联系起来的。

LLVM IR 通过 mem2reg 这个 Pass 来把局部变量成 SSA 形式。这个 Pass 的代码在 lib_Transforms_Utils_Mem2Reg.cpp 里。LLVM通过 mem2reg Pass 能够识别 alloca 模式,将其设置 SSA value。这时就不在需要 alloca,load和store了。mem2reg 是对 PromoteMemToReg 函数调用的一个简单包装,真正的算法实现是在 PromoteMemToReg 函数里,这个函数在 lib_Transforms_Utils_PromoteMemoryToRegister.cpp 这个文件里。

这个算法会使 alloca 这个仅仅作为 load 和 stores 的用途的指令使用迭代 dominator 边界转换成 PHI 节点,然后通过使用深度优先函数排序重写 loads 和 stores。这种算法叫做 iterated dominance frontier算法,具体实现方法可以参看 PromoteMemToReg 函数的实现。

当然把多个字节码 .bc 合成一个文件,链接时还会优化,IR 结构在优化后会有变化,这样还能够在变化后的 IR 的结构上再进行更多的优化。

这里可以进行 lli 解释执行 LLVM IR。

llc 编译器是专门编译 LLVM IR 的编译器用来生成汇编文件。

调用系统汇编器比如 GNU 的 as 来编译生成 .o Object 文件,接下来就是用链接器链接相关库和 .o 文件一起生成可执行的 .out 或者 exe 文件了。

llvm-mc 还可以直接生成 object 文件。

Clang CFE

动手玩肯定不能少了 Clang 的前端组件及库,熟悉这些库以后就能够自己动手用这些库编写自己的程序了。下面我就对这些库做些介绍,然后再着重说说 libclang 库,以及如何用它来写工具。

  • LLVM Support Library - LLVM libSupport 库提供了许多底层库和数据结构,包括命令行 option 处理,各种容器和系统抽象层,用于文件系统访问。
  • The Clang “Basic” Library - 提供了跟踪和操纵 source buffers,source buffers 的位置,diagnostics,tokens,抽象目标以及编译语言子集信息的 low-level 实用程序。还有部分可以用在其他的非 c 语言比如 SourceLocation,SourceManager,Diagnositics,FileManager 等。其中 Diagnositics 这个子系统是编译器和普通写代码人交流的主要组成部分,它会诊断当前代码哪些不正确,按照严重程度而产生 WARNING 或 ERROR,每个诊断会有唯一 ID , SourceLocation 会负责管理。
  • The Driver Library - 和 Driver 相关的库,上面已经对其做了详细的介绍。
  • Precompiled Headers - Clang 支持预编译 headers 的两个实现。
  • The Frontend Library - 这个库里包含了在 Clang 库之上构建的功能,比如输出 diagnositics 的几种方法。
  • The Lexer and Preprocessor Library - 词法分析和预处理的库,包含了 Token,Annotation Tokens,TokenLexer,Lexer 等词法类,还有 Parser Library 和 AST 语法树相关的比如 Type,ASTContext,QualType,DeclarationName,DeclContext 以及 CFG 类。
  • The Sema Library - 解析器调用此库时,会对输入进行语义分析。 对于有效的程序,Sema 为解析构造一个 AST。
  • The CodeGen Library - CodeGen 用 AST 作为输入,并从中生成 LLVM IR 代码。

libclang

libclang 会让你觉得 clang 不仅仅只是一个伟大的编译器。下面从解析源码来说下

先写个 libclang 的程序来解析源码

int main(int argc, char *argv[]) {
    CXIndex Index = clang_createIndex(0, 0);
    CXTranslationUnit TU = clang_parseTranslationUnit(Index, 0,
                                                      argv, argc, 0, 0, CXTranslationUnit_None); for (unsigned I = 0, N = clang_getNumDiagnostics(TU); I != N; ++I) {
        CXDiagnostic Diag = clang_getDiagnostic(TU, I);
        CXString String = clang_formatDiagnostic(Diag,clang_defaultDiagnosticDisplayOptions());
        fprintf(stderr, "%s\n", clang_getCString(String));
        clang_disposeString(String);
    }
    clang_disposeTranslationUnit(TU);
    clang_disposeIndex(Index);
    return 0;
}

再写个有问题的 c 程序

struct List { /**/ };int sum(union List *L) { /* ... */ }

运行了语法检查后会出现提示信息

list.c:2:9: error: use of 'List' with tag type that does not match
      previous declaration
int sum(union List *Node) {
^~~~~
struct
list.c:1:8: note: previous use is here
struct List {
^

下面我们看看诊断过程,显示几个核心诊断方法诊断出问题

  • enum CXDiagnosticSeverity clang_getDiagnosticSeverity(CXDiagnostic Diag);
  • CXSourceLocation clang_getDiagnosticLocation(CXDiagnostic Diag);
  • CXString clang_getDiagnosticSpelling(CXDiagnostic Diag);

接着进行高亮显示,最后提供两个提示修复的方法

  • unsigned clang_getDiagnosticNumFixIts(CXDiagnostic Diag);* CXString clang_getDiagnosticFixIt(CXDiagnostic Diag, unsigned FixIt,CXSourceRange *ReplacementRange);

我们先遍历语法树的节点。源 c 程序如下

struct List {
    int Data;
    struct List *Next;
};
int sum(struct List *Node) {
    int result = 0;
    for (; Node; Node = Node->Next)
        result = result + Node->Data;
    return result;
}

先找出所有的声明,比如 List,Data,Next,sum,Node 以及 result 等。再找出引用,比如 struct List *Next 里的 List。还有声明和表达式,比如 int result = 0; 还有 for 语句等。还有宏定义和实例化等。

CXCursor 会统一 AST 的节点,规范包含的信息

  • 代码所在位置和长度
  • 名字和符号解析
  • 类型
  • 子节点

举个 CXCursor 分析例子

struct List {
    int Data;
    struct List *Next;
};

CXCursor 的处理过程如下

//Top-level cursor C
clang_getCursorKind(C) == CXCursor_StructDecl
clang_getCursorSpelling(C) == "List" //获取名字字符串
clang_getCursorLocation(C) //位置
clang_getCursorExtent(C) //长度
clang_visitChildren(C, ...); //访问子节点

//Reference cursor R
clang_getCursorKind(R) == CXCursor_TypeRef 
clang_getCursorSpelling(R) == "List"
clang_getCursorLocation(R)
clang_getCursorExtent(R)
clang_getCursorReferenced(R) == C //指向C
© 著作权归作者所有
这个作品真棒,我要支持一下!
本专栏文章由 @故胤道长、@一缕殇流化隐半边冰霜、@没故事的卓同学、@Onetaway 编辑。关于这本书的任何的意...
2条评论

后半部分讲的有点水

编译那里,推荐用release模式,并且正确编译指令为
cmake -DCMAKE_BUILD_TYPE=Release -DBUILD_SHARED_LIBS=ON -DLLVM_TARGETS_TO_BUILD="AArch64;X86" -G "Unix Makefiles" ../llvm

后面有个./llvm

top Created with Sketch.