Written by
on September 29, 2017

Llvm编译过程

LLVM编译过程的前端(Clang)处理流程

使用一个简单的程序来简要说明编译过程.

helloworld.c

#include <stdio.h>

int main(int argc, char const *argv[])
{
	printf("hello world!\n");
	return 0;
}

编译过程

source code -> clang or GCC with GrogenEgg -> LLVM IR Linker -> LLVM IR optimizer -> LLVM backend -> assembler -> GCC Linker -> program

前端过程

C, C++, Objective-C 源码 -> 词法分析 -> 语法分析 -> 语义分析 -> LLVM IR 生成器

词法分析

将源码去掉注释,空格,缩进等, 剩下的文本进行拆分成词语和符号(token)

保留关键字和符号都会定义在一个文件中点这里查看

PUNCTUATOR(l_square,            "[")
PUNCTUATOR(r_square,            "]")
PUNCTUATOR(l_paren,             "(")
PUNCTUATOR(r_paren,             ")")
KEYWORD(auto                        , KEYALL)
KEYWORD(break                       , KEYALL)
KEYWORD(case                        , KEYALL)
KEYWORD(char                        , KEYALL)

$ clang -cc1 -dump-tokens helloworld.c

命令可以将源码拆分成对应的语言的关键字和符号,以及每个关键字和符号对应的定义所在文件的起始位置

if 'if'  [StartOfLine] [LeadingSpace] Loc=<min.c:2:3>
l_paren '('  [LeadingSpace] Loc=<min.c:2:6>
identifier 'a'  Loc=<min.c:2:7>
less '<'  [LeadingSpace] Loc=<min.c:2:9>
identifier 'b'  [LeadingSpace] Loc=<min.c:2:11>

错误分析 检查代码中的拼写错误

预编译 在语义分析提取代码的意义之前,会进行预编译处理,它负责将宏展开,引入包含的文件,跳过以#开头的代码

语法分析

将语义分析完成的tokens(拆分成了一个个词和符号)组合在一起，形成表达式、语句和函数体等等.检查组合在一起的tokens是否符合他们排版在一起的意义.但是代码的意思还没有进行分析,这个需要下一步语义分析, 语法分析只要做到像语言分析那样tokens对不对,不需要关心具体的tokens是什么意思.语法分析的结果会输出一个抽象语法树(AST)

clang -fsyntax-only -Xclang -ast-dump helloworld.c

命令查看抽象语法树

TranslationUnitDecl 0x7faef88166d0 <<invalid sloc>> <invalid sloc>
|-TypedefDecl 0x7faef8816c18 <<invalid sloc>> <invalid sloc> implicit __int128_t '__int128'
| `-BuiltinType 0x7faef8816940 '__int128'
|-TypedefDecl 0x7faef8816c78 <<invalid sloc>> <invalid sloc> implicit __uint128_t 'unsigned __int128'
| `-BuiltinType 0x7faef8816960 'unsigned __int128'
...

生成语法书的过程是根据词法分析的结果, 查找其中的token进行对应的Parse方法调用, parse方法在这里, 例如找到了一个token是kw_if,就是我们代码中写的if,那么会调用Parse/ParseStmt.cpp下的ParseIfStatement方法,这里面会对后面的token进行判断,直到查找到所有if条件判断的代码之后,生成一个if的节点,作为这个if判断的根节点,这样循环调用就会生成一个语法树,为后续语义分析做准备.

语义分析

语义分析确保代码不会通过符号表来违反编程语言的类型系统, 符号表存储着每个符号和它的类型,通过遍历AST并从符号表中收集有关类型的信息，从而执行解析.实际语义分析本身没有遍历整个AST, 而是在语法分析生成AST的时候进行类型检查,在DeclContext中保存了所有的Decl节点信息,

$ clang -fsyntax-only -Xclang -print-decl-contexts helloworld.c

命令可以打印出context

[translation unit] 0x7fe35b823cf0
        <typedef> __int128_t
        <typedef> __uint128_t
        <typedef> __NSConstantString
        <typedef> __builtin_ms_va_list
        ...

生成LLVM IR 代码

在经过了语法和语义分析的AST后,ParseAST方法会调用HandleTranslationUnit方法通知客户端使用生成好的AST,如果编译器使用了前端的CodeGenAction命令,客户端就是BackendConsumer,它会遍历AST按照对应的行为生成LLVM IR代码,遍历行为从数顶开始,也就是TranslationUnitDecl节点.

生成LLVM IR代码之后, 就完成了编译器前端的工作,剩下的工作交给LLVM,例如优化IR代码,交给后端去生成目标代码.

IR有三种存储形式:

在内存中存储(Instruction类等)
在磁盘中存储的特殊编码文件(bitcode文件)
在磁盘中存储的可阅读的文本(装配文件)

LLVM IR

生成LLVM IR bitcode文件命令

$ clang helloworld.c -emit-llvm -c -o helloworld.bc

生成LLVM IR 可阅读文本命令

clang helloworld.c -emit-llvm -S -c -o helloworld.ll

我们看一下可阅读的文本

; ModuleID = 'helloworld.c'
source_filename = "helloworld.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 [14 x i8] c"hello world!\0A\00", align 1

; Function Attrs: nounwind ssp uwtable
define i32 @main(i32, i8**) #0 {
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  %5 = alloca i8**, align 8
  store i32 0, i32* %3, align 4
  store i32 %0, i32* %4, align 4
  store i8** %1, i8*** %5, align 8
  %6 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([14 x i8], [14 x i8]* @.str, i32 0, i32 0))
  ret i32 0
}

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

attributes #0 = { nounwind ssp uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "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-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { "correctly-rounded-divide-sqrt-fp-math"="false" "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" "no-signed-zeros-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

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

!0 = !{i32 1, !"PIC Level", i32 2}
!1 = !{!"Apple LLVM version 8.1.0 (clang-802.0.42)"}

LLVM IR代码遵循了SSA 静态单赋值形式,所以所有的符号都只会被赋值一次,方便后续进行查找和处理.

如代码所示,LLVM语言首先定义了一个模块, 模块下面会有一系列的方法, 其中以%开头的是本地符合, @开头的代表全局符合. 方法定义类似C函数define i32 @main(i32, i8**) #0 {}, 其中#0代表着方法的属性,这些属性定义在文件结尾.

另外其实函数内部会被标签分成若干个代码块,上面的函数因为没有跳转,循环等.下面来看下面的int sum(int a, int b)函数的IR码.

define i32 @sum(i32, i32) #0 {
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  store i32 %0, i32* %3, align 4
  store i32 %1, i32* %4, align 4
  %5 = load i32, i32* %3, align 4
  %6 = load i32, i32* %4, align 4
  %7 = icmp ne i32 %5, %6
  br i1 %7, label %8, label %10

; <label>:8:                                      ; preds = %2
  %9 = load i32, i32* %4, align 4
  store i32 %9, i32* %3, align 4
  br label %10

; <label>:10:                                     ; preds = %8, %2
  %11 = load i32, i32* %3, align 4
  %12 = load i32, i32* %4, align 4
  %13 = add nsw i32 %11, %12
  ret i32 %13
}

其中 ; <label>:8:和; <label>:10:就是分支代码.

alloca说明了会在当前函数的栈帧上分配空间,空间大小由i32, i64, i128等大小控制.

使用LLVM汇编语言编写一些小例子来学习LLVM是很方便的,在这里可以找到LLVM汇编语言的语法.

从LLVM IR代码到目标代码/汇编代码过程

LLVM IR代码 -> 编译期和链接期优化 -> Instruction Selection -> Instruction Scheduling -> Register Allocation -> Instruction Scheduling -> Code Emission

Instruction Selection: 将LLVM IR在内存中的代码转换成将三地址结构转换成DAG(有向无环图)节点 ,最终转换为目标机器的节点

Instruction Scheduling: 将一组虚拟寄存器引用转换成目标的寄存器集合

Code Emission: 生成最终的目标机器码或汇编代码

Clang 静态分析器

Clang静态分析会在开发过程中发现问题并报告出来, 不会将可检测的bug带到runtime中,它会在编译之前进行.

← → Top