jywhy6's blog
0%

LLVM 编译器前端 Clang AST & API 学习笔记

Posted on Edited on In
Symbols count in article: 5.2k Reading time ≈ 9 mins.

LLVM 是一套编译器基础设施项目，为自由软件，以 C++ 写成，包含一系列模块化的编译器组件和工具链，用来开发编译器前端和后端。它是为了任意一种编程语言而写成的程序，利用虚拟技术创造出编译时期、链接时期、运行时期以及「闲置时期」的最优化。它最早以 C/C++ 为实现对象，而目前它已支持包括 ActionScript、Ada、D 语言、Fortran、GLSL、Haskell、Java 字节码、Objective-C、Swift、Python、Ruby、Crystal、Rust、Scala 以及 C# 等语言。
（摘录自中文维基百科，有改动）

这篇博文是我学习 LLVM 编译器架构的编译器前端 Clang 的笔记。

该笔记的侧重点在如何使用 Clang AST 相关的 API 进行静态源码分析工具的开发，而非如何使用 Clang 系列二进制工具。

参考资料

课程 Slides

Clang AST 相关

RecursiveASTVisitor 相关

ASTMatcher 相关

入门 Clang AST

Clang 是 LLVM 编译器框架的前端部分。Clang 首先运行预处理器以进行宏展开，然后将解析源代码 (词法分析、语法分析等) 并生成 AST (Abstract Syntax Tree，抽象语法树)。与 C/C++ 源代码相比，Clang AST 提供了更加便于分析和操作的程序表示形式，同时还具有便于找到 AST 节点所对应的源代码行列数的特性。事实上，Clang 使用的各种数据结构 (AST、CFG (Control Flow Graph，控制流图) 等) 都能轻易地转换回源代码，因此 Clang 特别适合用于进行静态代码分析、代码重构等工作。

如果需要在源代码层级上进行分析和修改，Clang 是比 LLVM (编译器后端) 更好的选择，因为使用 LLVM 进行分析需要使用与汇编代码类似的 LLVM IR (Intermediate Representation，中间表示)。

通过简单案例学习 Clang AST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
$ cat test.cc
int f(int x) {
  int result = (x / 42);
  return result;
}

# Clang by default is a frontend for many tools; -Xclang is used to pass
# options directly to the C++ frontend.
$ clang -Xclang -ast-dump -fsyntax-only test.cc
TranslationUnitDecl 0x5aea0d0 <<invalid sloc>>
... cutting out internal declarations of clang ...
`-FunctionDecl 0x5aeab50 <test.cc:1:1, line:4:1> f 'int (int)'
  |-ParmVarDecl 0x5aeaa90 <line:1:7, col:11> x 'int'
  `-CompoundStmt 0x5aead88 <col:14, line:4:1>
    |-DeclStmt 0x5aead10 <line:2:3, col:24>
    | `-VarDecl 0x5aeac10 <col:3, col:23> result 'int'
    |   `-ParenExpr 0x5aeacf0 <col:16, col:23> 'int'
    |     `-BinaryOperator 0x5aeacc8 <col:17, col:21> 'int' '/'
    |       |-ImplicitCastExpr 0x5aeacb0 <col:17> 'int' <LValueToRValue>
    |       | `-DeclRefExpr 0x5aeac68 <col:17> 'int' lvalue ParmVar 0x5aeaa90 'x' 'int'
    |       `-IntegerLiteral 0x5aeac90 <col:21> 'int' 42
    `-ReturnStmt 0x5aead68 <line:3:3, col:10>
      `-ImplicitCastExpr 0x5aead50 <col:10> 'int' <LValueToRValue>
        `-DeclRefExpr 0x5aead28 <col:10> 'int' lvalue Var 0x5aeac10 'result' 'int'

可以看出：

  • 一个翻译单元 (Translation Unit) 的顶层节点是 TranslationUnitDecl 。
  • 在这个例子中，第一个来自用户代码的节点是 FunctionDecl 。
  • f 的函数体是一个复合语句 CompoundStmt，其子节点是变量 result 的声明，以及返回语句 ReturnStmt 。

通过课程 Slides 学习 Clang AST

这份 Clang Tutorial Slides 来自 KAIST (韩国科学技术院) 的 Moonzoo Kim 教授的课程 CS492A Automated Software Analysis, Fall 18，内含详细的解释和丰富的图例，非常推荐阅读。

Clang AST 的类型

Clang AST 中大部分类型都可以根据其名称得知其含义。也可以在搜索引擎中搜索 “clang functiondecl” 等，以找到对应类型的详细文档。

核心基本类型

下面是 Clang AST 的三大核心基本类型，以及它们的子类的例子：

  • Decl (声明)
    • FunctionDecl (函数声明)
    • VarDecl (变量声明)
  • Stmt (语句)
    • CompoundStmt (复合语句)
    • BinaryOperator (二元运算符)
    • Expr (表达式)
      • CallExpr (函数调用表达式)
      • CastExpr (类型转换表达式)
  • Type (类型)
    • PointerType (指针类型)

ASTContext

在一个翻译单元中，所有有关 AST 的信息都在类 ASTContext ，包括：

  • 标识符表
  • SourceManager
  • AST 的入口节点: TranslationUnitDecl* getTranslationUnitDecl()

胶水类型 (Glue Classes)

  • DeclContext
    • 包含其他 Decl 的 Decl 需要继承此类。
  • TemplateArgument
    • 模板参数的访问器。
  • NestedNameSpecifier
  • QualType
    • Qual 是 qualifier 的意思，将 C++ 类型中的 const 等拆分出来，避免类型的组合爆炸问题。

访问 AST 的方法

Clang 主要提供了 2 种对 AST 进行访问的类：RecursiveASTVisitor 和 ASTMatcher。

RecursiveASTVisitor

建议结合 How to write RecursiveASTVisitor based ASTFrontendActions. 中的代码样例来学习 RecursiveASTVisitor，并尝试使用 cmake 编译并运行样例程序。

  • 特性
    • 由用户所关心的类型触发 (例如可以访问所有Stmt)。
    • 无法充分利用 AST 的上下文信息 (无法利用节点之间的关系来筛选节点)。
  • 使用方法
    • TraverseDecl(Decl *x) 用于遍历以 x 为根的 AST。它将自动调用 TraverseFoo(Foo *x) ，进而调用 WalkUpFromFoo(x) ，然后递归地以前序或后序的方式深度优先遍历 x 的子节点。 TraverseStmt(Stmt *x) 和 TraverseType(QualType x) 函数的功能类似。
    • WalkUpFromFoo(Foo *x) 并不尝试访问 x 的子节点，而是向上搜索节点 x 的类型层级，直到达到 AST 的核心基本类型之一 (Stmt/Decl/Type) 。它首先调用 WalkUpFromBar(x) (Bar 是 Foo 的直接父类 (如果存在))，然后调用 VisitFoo(x)。
    • VisitFoo(Foo *x) 接受类型为 Foo 的节点 x ，并调用可被用户覆盖的虚函数来访问该节点 (对访问到的具体某类节点的操作逻辑应当写在这个函数里)。
  • 注意事项
    • 在上述三个成员函数中，返回 true 则遍历继续，但若任一函数返回 false ，则整个遍历终止。
    • 上述三个成员函数具有层级关系 (Traverse* > WalkUpFrom* > Visit*) ，可以调用同级函数或低级函数，但不能调用高级函数。
    • 由于 WalkUpFromFoo() 首先调用 WalkUpFromBar(x) ，因此在类型层面上 Visit*() 具有自顶向下的调用顺序 (例：对于 NamespaceDecl 类型的节点，调用顺序是 VisitDecl() -> VisitNamedDecl() -> VisitNamespaceDecl()) 。
    • 遍历 AST 时，默认只访问未实例化的 (而不访问任何隐式或显式实例化的) 模板类和模板函数。可以覆盖虚函数 shouldVisitTemplateInstantiations() ，使它的返回值为 true 来启用对所有已知的隐式、显式实例化的模板类和模板函数的访问。
    • 默认采用先序遍历 AST。可以覆盖虚函数 shouldTraversePostOrder()，使它的返回值为 true 来使用后序遍历。
  • 缺点
    • 需要进行递归遍历，效率较低。

ASTMatcher

建议结合 Tutorial for building tools using LibTooling and LibASTMatchers 中的代码样例来学习 ASTMatcher，并尝试使用 cmake 编译并运行样例程序。

  • 特性
    • 本质上是一种 DSL (Domain Specific Language，领域特定语言)。
    • 由表达式 (expressions) 触发 (用户使用表达式规定触发访问的条件)。
    • 与 AST 上下文信息绑定 (用户可以在表达式中利用上下文信息来筛选节点)。
    • 无需遍历，能直接匹配到表达式对应的节点。
  • 使用方法
    • 直接组合各种 ASTMatcher 来精确表示匹配节点的规则，语义非常清晰，例如 binaryOperator(hasOperatorName("+"), hasLHS(integerLiteral(equals(0)))) 匹配的是左操作数为字面量 0 的加法操作表达式。
    • 可以对任意层级的表示 Clang AST 节点 (而非 LHS、RHS、Type、Operand、 等节点属性) 的 ASTMatcher 使用 .bind("foo") 操作，将该节点与字符串绑定。
    • 可以继承回调类 MatchFinder::MatchCallback ，覆盖虚函数 run(const MatchFinder::MatchResult &Result)，然后使用 Result.Nodes.getNodeAs<clang::FooType>("foo") 来访问此前与字符串绑定的 Clang AST 节点。
  • 注意事项
    • 在 Clang AST 中，对变量的使用被表达为 declRefExpr (declaration reference expressions，声明引用表达式)，例如 declRefExpr(to(varDecl(hasType(isInteger())))) 表示对一个整数类型变量声明的使用 (请注意，不是 C++ 中的引用) 。