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 bind(绑定：通过不同的架构，生成对应的可执行文件)
前端过程
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中,它会在编译之前进行.
