LLVM架构-编译原理

什么是LLVM

LLVM项目是模块化、可重用的编译器以及工具链技术的集合
The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
官网:
美国计算机协会 (ACM) 将其2012 年软件系统奖项颁给了LLVM，之前曾经获得此奖项的软件和技术包括:Java、Apache、 Mosaic、the World Wide Web、Smalltalk、UNIX、Eclipse等等
有些文章把LLVM当做Low Level Virtual Machine(低级虚拟机)的缩写简称，官方描述如下
The name "LLVM" itself is not an acronym; it is the full name of the project.
“LLVM”这个名称本身不是首字母缩略词; 它是项目的全名

传统的编译器架构

image.png

Frontend:前端
词法分析、语法分析、语义分析、生成中间代码
Optimizer:优化器
中间代码优化
Backend:后端
生成机器码

LLVM架构

image.png

不同的前端后端使用统一的中间代码LLVM Intermediate Representation (LLVM IR)
如果需要支持一种新的编程语言，那么只需要实现一个新的前端
如果需要支持一种新的硬件设备，那么只需要实现一个新的后端
优化阶段是一个通用的阶段，它针对的是统一的LLVM IR，不论是支持新的编程语言，还是支持新的硬件设备，都不需要对优化阶段做修改
相比之下，GCC的前端和后端没分得太开，前端后端耦合在了一起。所以GCC为了支持一门新的语言，或者为了支持一个新的目标平台，就变得特别困难

什么是Clang?

LLVM项目的一个子项目
基于LLVM架构的C/C++/Objective-C编译器前端
官网:
相比于GCC，Clang具有如下优点
编译速度快:在某些平台上，Clang的编译速度显著的快过GCC(Debug模式下编译OC速度比GGC快3倍)
占用内存小:Clang生成的AST所占用的内存是GCC的五分之一左右
模块化设计:Clang采用基于库的模块化设计，易于 IDE 集成及其他用途的重用
诊断信息可读性强:在编译过程中，Clang 创建并保留了大量详细的元数据 (metadata)，有利于调试和错误报告
设计清晰简单，容易理解，易于扩展增强

image.png
广义的LLVM
整个LLVM架构
狭义的LLVM
LLVM后端(代码优化、目标代码生成等)

image.png

clang 前端
IR 代表代码层
Pass代表优化

OC源文件的编译过程

一.编译

命令行查看编译的过程:$ clang -ccc-print-phases main.m
下面我们来分析代码

#import <Foundation/Foundation.h>
int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        NSLog(@"Hello, World!");
    }
    return 0;
}

//编译之后的代码
0: input, "main.m", objective-c   //声明 
1: preprocessor, {0}, objective-c-cpp-output // //预处理
2: compiler, {1}, ir //编译生成IR(中间代码)
3: backend, {2}, assembler //汇编器生成汇编代码
4: assembler, {3}, object  //目标代码生成机器码
5: linker, {4}, image  // 静态库,动态库链接
6: bind-arch, "x86_64", {5}, image //可执行文件

编译器前端的工作

编译器前端的任务是进行：语法分析，语义分析，生成中间代码(intermediate representation )。在这个过程中，会进行类型检查，如果发现错误或者警告会标注出来在哪一行。

二.preprocessor(预处理)

#import <Foundation/Foundation.h>
#define AGE 40
int main(int argc, const char * argv[]) {
     int a = 10;
     int b = 10;
     int c = a + b + AGE;
    return 0;
}

preprocessor 预处理的结果

int main(int argc, const char * argv[]) {
     int a = 10;
     int b = 10;
     int c = a + b + 40;
    return 0;
}
//预处理就已经把宏替换了

查看preprocessor(预处理)的结果:$ clang -E main.m

三.词法分析

词法分析，生成Token: $ clang -fmodules -E -Xclang -dump-tokens main.m

 clang -fmodules -E -Xclang -dump-tokens main.m
annot_module_include '#import <Foundation/Foundation.h>

#define AGE 40

int main(int argc, const char * argv[]) {
    
    int a = 10;
    int b = 10;
    in'     Loc=<main.m:9:1> //第9行的第1个字符
int 'int'    [StartOfLine]  Loc=<main.m:13:1> //第13行的第一个1字符
identifier 'main'    [LeadingSpace] Loc=<main.m:13:5>
l_paren '('     Loc=<main.m:13:9>
int 'int'       Loc=<main.m:13:10>
identifier 'argc'    [LeadingSpace] Loc=<main.m:13:14>
comma ','       Loc=<main.m:13:18>
const 'const'    [LeadingSpace] Loc=<main.m:13:20>
char 'char'  [LeadingSpace] Loc=<main.m:13:26>
star '*'     [LeadingSpace] Loc=<main.m:13:31>
identifier 'argv'    [LeadingSpace] Loc=<main.m:13:33>
l_square '['        Loc=<main.m:13:37>
r_square ']'        Loc=<main.m:13:38>
r_paren ')'     Loc=<main.m:13:39>
l_brace '{'  [LeadingSpace] Loc=<main.m:13:41>
int 'int'    [StartOfLine] [LeadingSpace]   Loc=<main.m:15:5>
identifier 'a'   [LeadingSpace] Loc=<main.m:15:9>
equal '='    [LeadingSpace] Loc=<main.m:15:11>
numeric_constant '10'    [LeadingSpace] Loc=<main.m:15:13>
semi ';'        Loc=<main.m:15:15>
int 'int'    [StartOfLine] [LeadingSpace]   Loc=<main.m:16:5>
identifier 'b'   [LeadingSpace] Loc=<main.m:16:9>
equal '='    [LeadingSpace] Loc=<main.m:16:11>
numeric_constant '10'    [LeadingSpace] Loc=<main.m:16:13>
semi ';'        Loc=<main.m:16:15>
int 'int'    [StartOfLine] [LeadingSpace]   Loc=<main.m:17:5>
identifier 'c'   [LeadingSpace] Loc=<main.m:17:9>
equal '='    [LeadingSpace] Loc=<main.m:17:11>
identifier 'a'   [LeadingSpace] Loc=<main.m:17:13>
plus '+'     [LeadingSpace] Loc=<main.m:17:15>
identifier 'b'   [LeadingSpace] Loc=<main.m:17:17>
plus '+'     [LeadingSpace] Loc=<main.m:17:19>
numeric_constant '40'    [LeadingSpace] Loc=<main.m:17:21 <Spelling=main.m:11:13>>
semi ';'        Loc=<main.m:17:24>
return 'return'  [StartOfLine] [LeadingSpace]   Loc=<main.m:18:5>
numeric_constant '0'     [LeadingSpace] Loc=<main.m:18:12>
semi ';'        Loc=<main.m:18:13>
r_brace '}'  [StartOfLine]  Loc=<main.m:20:1>
eof ''      Loc=<main.m:20:2>

将代码分成一段一段的token

五.语法树-AST

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

//源代码
void test(int a, int b){
    int c = a + b -3;
}

//转换为语法树之后
-FunctionDecl 0x7fa7f0184300 <line:22:1, line:24:1> line:22:6 test 'void (int, int)' //
| |-ParmVarDecl 0x7fa7f0184180 <col:11, col:15> col:15 used a 'int'
| |-ParmVarDecl 0x7fa7f01841f8 <col:18, col:22> col:22 used b 'int'
| `-CompoundStmt 0x7fa7f0184540 <col:24, line:24:1>
|   `-DeclStmt 0x7fa7f0184528 <line:23:5, col:21>
|     `-VarDecl 0x7fa7f01843d8 <col:5, col:20> col:9 c 'int' cinit
|       `-BinaryOperator 0x7fa7f0184500 <col:13, col:20> 'int' '-'
|         |-BinaryOperator 0x7fa7f01844b8 <col:13, col:17> 'int' '+'
|         | |-ImplicitCastExpr 0x7fa7f0184488 <col:13> 'int' <LValueToRValue>
|         | | `-DeclRefExpr 0x7fa7f0184438 <col:13> 'int' lvalue ParmVar 0x7fa7f0184180 'a' 'int'
|         | `-ImplicitCastExpr 0x7fa7f01844a0 <col:17> 'int' <LValueToRValue>
|         |   `-DeclRefExpr 0x7fa7f0184460 <col:17> 'int' lvalue ParmVar 0x7fa7f01841f8 'b' 'int'
|         `-IntegerLiteral 0x7fa7f01844e0 <col:20> 'int' 3

FunctionDecl下有三个节点 ParmVarDecl, ParmVarDecl, CompoundStmt
FunctionDecl test函数
ParmVarDecl 参数a
ParmVarDecl 参数b
CompoundStmt 语句(也就是具体的代码)
VarDecl 符合的声明

  `-BinaryOperator 0x7fa7f0184500 <col:13, col:20> 'int' '-'
|         |-BinaryOperator 0x7fa7f01844b8 <col:13, col:17> 'int' '+'
|         | |-ImplicitCastExpr 0x7fa7f0184488 <col:13> 'int' <LValueToRValue>
|         | | `-DeclRefExpr 0x7fa7f0184438 <col:13> 'int' lvalue ParmVar 0x7fa7f0184180 'a' 'int'
|         | `-ImplicitCastExpr 0x7fa7f01844a0 <col:17> 'int' <LValueToRValue>
|         |   `-DeclRefExpr 0x7fa7f0184460 <col:17> 'int' lvalue ParmVar 0x7fa7f01841f8 'b' 'int'
|         `-IntegerLiteral 0x7fa7f01844e0 <col:20> 'int' 3

单独分析一下这段代码

//-  13-20里面装着 - 号
-BinaryOperator 0x7fa7f0184500 <col:13, col:20> 'int' '-'

//减号前面是3
`-IntegerLiteral 0x7fa7f01844e0 <col:20> 'int' 3

//13-17里面是+
|-BinaryOperator 0x7fa7f01844b8 <col:13, col:17> 'int' '+'

//13 是a
`-DeclRefExpr 0x7fa7f0184438 <col:13> 'int' lvalue ParmVar 0x7fa7f0184180 'a' 'int'

//17是b
`-DeclRefExpr 0x7fa7f0184460 <col:17> 'int' lvalue ParmVar 0x7fa7f01841f8 'b' 'int'

整合一起就是a+b-3

image.png

前端代码已经完成(就会生成中间代码IR)

中间代码IR

LLVM IR

LLVM IR有3种表示形式(但本质是等价的，就好比水可以有气体、液体、固体3种形态)
text:便于阅读的文本格式，类似于汇编语言，拓展名.ll， $ clang -S -emit-llvm main.m
memory:内存格式
bitcode:二进制格式，拓展名.bc， $ clang -c -emit-llvm main.m

; Function Attrs: noinline nounwind optnone ssp uwtable
define void @test(i32, i32) #0 { //(int a, int b)
  %3 = alloca i32, align 4 // int a
  %4 = alloca i32, align 4 // int d
  %5 = alloca i32, align 4 // int e
  store i32 %0, i32* %3, align 4 // c = a
  store i32 %1, i32* %4, align 4 // d = b
  %6 = load i32, i32* %3, align 4 //a
  %7 = load i32, i32* %4, align 4 //b
  %8 = add nsw i32 %6, %7  // a+b
  %9 = sub nsw i32 %8, 3    //a+b -3
  store i32 %9, i32* %5, align 4  //e = a+b-3  
  ret void
}
}

IR基本语法

官方参考文档
注释以分号 ; 开头
全局标识符以@开头，局部标识符以%开头
alloca，在当前函数栈帧中分配内存
i32，32bit，4个字节的意思
align，内存对齐
store，写入数据
load，读取数据
add, 相加
sub, 减
每一步分析我都写在注释上了

LLVM源码下载

git clone

未完待续......

全部频道

LLVM架构-编译原理

什么是LLVM

传统的编译器架构

LLVM架构

什么是Clang?

OC源文件的编译过程

一.编译

二.preprocessor(预处理)

三.词法分析

五.语法树-AST

中间代码IR