基于LLVM的源码级依赖分析方案的设计与实现

点击上方蓝字,关注高德技术！

1.

导读

---

随着业务快速发展，移动客户端技术架构也从单一的工程配置，转向模块化、组件化、动态化方向发展。越来越多的业务模块被拆分成独立组件bundle，进行独立开发、构建、测试、发布、运营，但这也面临着许多挑战：

• 如何保证众多的独立组件bundle能够准确无误快速集成到主工程、打包、提测、发布审核？ 

• 如果删除或更新某个独立组件bundle，将会对剩余的哪些bundle有影响？ 

• 架构或产品优化时，哪些独立组件bundle可以删除/下线？

这就需要确定这些独立组件bundle之间的依赖关系。

2.

依赖分析的定义

---

简单地说，通过某种技术手段获取到某个复杂系统中各个子系统之间相互关系，并将这种关系数据化、图像化处理的过程，即依赖分析。

3.

常见的依赖分析方案

---

3.1 基于Cocoapods的依赖包分析

Cocoapods是iOS业界提供，开源的、事实上的依赖管理标准工具，其Podfile.lock及podspec文件中均有显式的记录各个组件之间的依赖关系，因此只需要分析这些文件即可获取到依赖关系。

3.2 基于#include和#import头文件的依赖分析

众所周知，当某个源码文件A依赖另一个源码文件B时，必定会在A文件头部显式的添加上#include和#importB。因此只需要扫描所有源码文件中的头文件引用关系即可获取到依赖关系。

3.3 基于nm、otool等命令行工具的符号依赖分析

nm和otool常用于分析二进制文件中的符号信息，通过符号建立依赖关系。

3.4 三种符号依赖分析比较

三种方案各有优缺点：

方案	优点	缺点	分析时机	难度
Cocoapods	简单直观，业内基础方案	分析粒度大(以bundle为单位)	编译前	简单
头文件引用	简单直观	分析粒度中(以文件为单位)，存在无效、循环依赖问题	编译前	简单
nm/otool	简单直观	分析粒度细(以符号为单位)，编译混淆或优化(strip)的库查不到符号信息	编译后	简单

本文从编译原理角度，设计一种新的源码级别依赖分析方案。

4.

基于LLVM的依赖分析方案

---

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.

LLVM项目是一系列分模块、可重用的编译工具链。它提供了一种代码编写良好的中间表示(IR)，可以作为多种语言的后端，还可以提供与编程语言无关的优化和针对多种CPU架构的代码生成功能，举个例子来说明整个LLVM的编译过程：

// main.m
#include <stdio.h>
#define kPeer 3
int main(int argc, const char * argv[]) {
    int a = 1;
    int b = 2;
    int c = a + b + kPeer;
    printf("%d",c);
    return 0;
}

// 执行命令 clang -ccc-print-phases main.m 输出
0: input, "main.m", objective-c
1: preprocessor, {0}, objective-c-cpp-output
2: compiler, {1}, ir
3: backend, {2}, assembler
4: assembler, {3}, object
5: linker, {4}, image
6: bind-arch, "x86_64", {5}, image

整体流程如图示：

4.1 预处理(Preprocessor)阶段

预处理包括：条件编译、源文件包含、宏替换、行控制、抛错、杂注和空指令。

clang-E main.m

4.2 词法分析(Lexer)阶段 

行词法分析：将预处理过的代码转化成一个个Token，比如左括号、右括号、等于、字符串等等。

clang-fmodules-fsyntax-only-Xclang-dump-tokens main.m

4.3 语法分析(AST)阶段 

行语法分析：根据当前语言的语法，验证语法是否正确，并将所有节点组合成抽象语法树(AST)。

clang-fmodules-fsyntax-only-Xclang-ast-dump main.m

4.4 中间代码(IR)生成阶段 

CodeGen负责将语法树从顶至下遍历，翻译成中间代码IR，IR是LLVM Frontend的输出，也是LLVM Backerend的输入，桥接前后端。

clang-S-fobjc-arc-emit-llvm main.m-o main.ll

4.5 代码优化(Opt)阶段 

例如Xcode中开启了bitcode，那么苹果后台拿到的就是这种中间代码，苹果可以对 bitcode做进一步的优化。

clang-emit-llvm-c main.m-o main.bc

4.6 代码生成器(CodeGen)阶段

// 生成汇编代码
clang-S-fobjc-arc main.m-o main.s

// 生成目标文件
clang-fmodules-c main.m-o main.o

4.7 链接成可执行文件

clang main.o-o main

其中IR代码生成(CodeGen)阶段，会遍历整个AST语法树，在此处插桩记录下函数名 + 行号 + 文件路径 + 源码hash值等信息，即可生成依赖分析的元数据。

5.

如何进行LLVM插桩

---

针对iOS端的代码编译，LLVM前端使用Clang编译器，要在中间代码(IR)阶段插桩即要进行Clang Plugin开发。 

5.1 准备Clang开发工具链 

可以选择自行编译的Clang开发工具链，如下操作：

#!/bin/sh
cd /opt
sudo mkdir llvm
pushd llvm &&
git clone -b release_80 [e-mail]:llvm-mirror/llvm.git llvm &&
git clone -b release_80 [e-mail]:llvm-mirror/clang.git llvm/tools/clang &&
git clone -b release_80 [e-mail]:llvm-mirror/clang-tools-extra.git llvm/tools/clang/tools/extra &&
git clone -b release_80 [e-mail]:llvm-mirror/compiler-rt.git llvm/projects/compiler-rt &&
popd &&
sudo mkdir -v llvm_build &&
pushd llvm_build &&
cmake -DCMAKE_INSTALL_PREFIX=/opt/llvm_release  \
      -DLLVM_TARGETS_TO_BUILD="X86;ARM;Mips;AArch64;WebAssembly" \
      -DCMAKE_BUILD_TYPE=Release                \
      -DLLVM_ENABLE_FFI=ON                      \
      -DLLVM_ENABLE_RTTI=ON                     \
      -DLLVM_BUILD_TESTS=OFF                    \
      -DLLVM_INCLUDE_TESTS=OFF                  \
      -Wno-dev -G Ninja ../llvm                &&
ninja && ninja install && popd

也可以选择已编译好的Clang开发工具链，下载地址：http://releases.llvm.org/

5.2 编写Clang插件 

Clang插件实际上一个动态链接库，因此使用Xcode创建一个dylib工程，将编译器指定到准备好的Clang工具链上即可开始，如下图示：

Clang Plugin通常的入口点是FrontendAction。FrontendAction是一个接口，它允许用户指定的actions作为编译的一部分来执行。为了在AST clang上运行工具，AST clang提供了方便的接口ASTFrontendAction，它负责执行action。剩下的唯一部分是实现CreateASTConsumer方法，该方法为每个翻译单元返回一个ASTConsumer。继承它们即可实现遍历 AST 语法树的功能：

类	功能
clang::RecursiveASTVisitor	遍历AST语法树的抽象基类
clang::PluginASTAction	基于consumer的AST前端Action抽象基类
clang::ASTConsumer	读取AST的抽象基类

识别AST语法树中的类名、方法名、调用关系，需使用AST中的以下类：

类	功能
clang::ObjCInterfaceDecl	记录Object-C类声明信息
clang::ObjCCategoryDecl	记录Object-C扩展类名信息
clang::ObjCMethodDecl	记录Object-C类方法声明信息
clang::ObjCImplDecl	记录Object-C类方法实现声明信息
clang::ObjCImplementationDecl	记录Object-C类方法实现信息
clang::ObjCPropertyDecl	记录Object-C类的属性声明信息
clang::ObjCProtocolDecl	记录Object-C协议声明信息
clang::ObjCMessageExpr	记录Object-C表达式信息

5.3 加载 Clang 插件 

在编译参数Other C/C++ Flag中添加

-Xclang -load -Xclang /opt/llvm_release/plugins/libXXXPlugin.dylib -Xclang -add-plugin -Xclang XXXPlugin

5.4 举个例子 

以下代码实现遍历AST语法树中的所有C++类名，并打印出来的功能：

#include "clang/AST/ASTConsumer.h"
#include "clang/AST/RecursiveASTVisitor.h"
#include "clang/Frontend/CompilerInstance.h"
#include "clang/Frontend/FrontendAction.h"
#include "clang/Tooling/Tooling.h"

using namespace clang;

class FindNamedClassVisitor
  : public RecursiveASTVisitor<FindNamedClassVisitor> {
public:
  explicit FindNamedClassVisitor(ASTContext *Context)
    : Context(Context) {}

  bool VisitCXXRecordDecl(CXXRecordDecl *Declaration) {
    llvm::outs() << "Found class: " << Declaration->getNameAsString() << "\n";
    return true;
  }

private:
  ASTContext *Context;
};

class FindNamedClassConsumer : public clang::ASTConsumer {
public:
  explicit FindNamedClassConsumer(ASTContext *Context)
    : Visitor(Context) {}

  virtual void HandleTranslationUnit(clang::ASTContext &Context) {
    Visitor.TraverseDecl(Context.getTranslationUnitDecl());
  }
private:
  FindNamedClassVisitor Visitor;
};

class FindNamedClassAction : public clang::ASTFrontendAction {
public:
  virtual std::unique_ptr<clang::ASTConsumer> CreateASTConsumer(
    clang::CompilerInstance &Compiler, llvm::StringRef InFile) {
    return std::unique_ptr<clang::ASTConsumer>(
        new FindNamedClassConsumer(&Compiler.getASTContext()));
  }
};

编译参数可使用LLVM为我们提供的llvm-config工具自动生成，执行

llvm-config --cxxflags --ldflags --system-libs --libs core

其余额外依赖库自行根据功能添加。 

6.

建立依赖关系元数据

---

通过加载定制化开发的Clang Plugin，经过编译即可生成如下面格式的数据结构：

{
    "+[GTMBase64 decodeBytes:length:]": {
        "call": [
            "+[GTMBase64 baseDecode:length:charset:requirePadding:]"
        ],
        "class": "GTMBase64",
        "filename": "/Sources/Internal/Encode/GTMBase64.m",
        "range": "11401-11553",
        "sourceCode": "{return [self baseDecode:bytes length:length charset:kBase64DecodeChars requirePadding:YES];}"
    }
}

其中：

key值	描述
call	标识调用链上的方法列表
class	标识类名
filename	标识编译单元文件名
range	标识方法所在行号
sourceCode	标识方法的实现源码

基于这些依赖元数据，经过后台系统加工处理，就可以准确地知道某个组件bundle与其他组件之间的关系，实现一套基于LLVM的依赖分析方案。

7.

小结

---

本文主要介绍了业内常见的依赖分析方案，并分享了一种基于LLVM的，从细粒度方法级别来实现依赖分析的方案，它能更准确反馈出各个独立组件bundle之间的关系，指导开发人员优化架构设计，可以应对未来“五独”技术进化带来的挑战。

---

往期相关文章：

---

活动推荐

2019杭州·云栖大会就要来了！我们将在9月27日（大会第三天）下午为开发者们呈现由顶级专家所带来，干货满满的高德技术专场，内容涵盖视觉智能、自动驾驶、路线规划、时空数据、亿级流量架构等话题。欢迎大家关注和参加！

点击阅读原文 查看活动详情