LLVM 编译器框架与流程分析

百補园的张和

LLVM 编译器框架与流程分析

LLVM 编译器框架
LLVM是Low Level Virtual Machine（低级虚拟机）的简称，是一款编译器框架。但是它本质上并不是虚拟机，核心其实准确点应该是编译器相关支持。主要是支持代码优化、链接、代码生成、机器码生成。当然有的时候内部llc给人感觉确实是类似解释型语言。现在LLVM已经集成非常多的优点，模块化设计让程序员可以绕开繁琐的操作，可以快速实现一个编译器并且运行。
一. 编译器架构
1.0 gcc
先看看编译器结构：


图：传统编译器结构
Frontend:前端，将高级语言的代码转换成编译器所对应的中间代码。其中操作有词法分析、语法分析、语义分析、中间代码生成
Optimizer:中端，对中间代码进行优化。（代码优化其实就是编译器对代码进行简介，整洁等等的操作。）
Backend:后端，对中间代码进行转换成机器码Opcode进行运行。本质上编译器到这里已经结束了。
Linker:链接:后续还要对机器码进行链接操作，本质上就是将机器码的文件进行打包与合并成可执行文件也就是经常所说的EXE与ELF。当然这是链接器的问题了。（其实可以与后端进行合并）


图：编译器架构
但是这种架构的编译器比如GCC有很多缺点：
· 后端太统一
· 不能支持新的语言
· 因为后端，在新设备（处理器架构）需要重新开发后端包括中端
因为GCC前后端都是耦合在一起，想支持新的语言和处理器架构开发起来非常非常困难。
1.1 LLVM
为止LLVM以上问题得到很好解决，而且LLVM编译器使用CLANG作为前端速度是GCC速度的三倍。
LLVM与GCC对比，它统一了LLVM IR（中端），如果需要开发新的处理器架构后端，那么只需要开发后端即可。
LLVM，除了后端模块化，连前端也实现了模块化。开发者可以自定义前端规则等等，开发一门自己的编程语言。
该编译器框架被Apple、FaceBook、Google广泛应用，甚至Apple为该编译器框架开发了Clang。


图：LLVM架构
前端:LLVM前后端实现了模块化，并不进行耦合。这样子，如果需要开发一门编程语言或者把Python从解释型转换成编译型。那么只需要对应Python的前端进行开发，开发出将Python转换成LLVM IR的前端即可。这样子可以让Python的性能超越目前的编程语言。当然由于Python的设计，这种想法还是算了。
后端:这个目前市面上的芯片架构，在LLVM上均可实现运行，如果进行二开也可以通过原有的基础进行二次开发，而且过程并不繁琐，或者如果发明了新的CPU架构，
中端:中端主要是对IR进行代码优化，实现性能上的效率提高。当然可以将IR独立出来，作为解释型来使用。这样子可以实现高性能解释型语言了（滑稽 速度怎样不清楚，但是个人感觉肯定起飞）
LLVM IR/Bitcode:LLVM IR本质上是LLVM可视化的代码形式，而Bitcode是以二进制数据形式的IR代码。IR是LLVM中端的中间代码，是前端到后端的过渡代码，其功能是为了更好实现一个模块化，并且前端转换为统一格式规定的IR，然后IR转换为
1.2 Clang
    Clang本质上是LLVM衍生出来的前端项目，由Apple开发。它是直接支持了C/C++/ObC++作为LLVM前端将其转化为LLVM IR，再从IR转换为后端机器码。这样子可以一个前端实现多个后端支持。（饶了），这个编译器框架我就不多描述。
二. LLVM的编译
    LLVM的编译，其实非常简单。当然LLVM因为非常庞大，我不进行本地编译了，其实就是CMAKE Ninja 一键编译。LLVM可以直接下载，已经编译好的二进制文件更为推荐，要是真的对LLVM进行开刀，那么需要编译，储存需要10G-40G （我编译花了30g）。 编译时间也非常漫长。
当然LLVM-Project默认使用Clang，如果不包含CLang 那么LLVM只有中端与后端。前端需要自己重新编译，一般使用Clang即可。
三. 编译一个Helloworld
首先写一组HelloWorld的C代码


图:Helloworld代码
然后使用Clang前端进行编译，编译成IR代码，不加-S会编译成bc代码。


图：
编译IR代码
使用llvm-as 将IR代码进行转化为bc代码。并且使用llvm-bcanalyzer进行bc代码分析


图：bc代码生成
最后使用lli进行后端运行，这是属于“解释型”的。可以使用llc转换为汇编文件或者对象文件。


图：后端运行
并且使用gcc将对象文件编译成ELF。（因为LLVM链接器并不完善，所以使用gcc可以方便快捷。）
LLVM（一）——编译流程
一、编译型语言 VS 解释型语言
我们程序员编写的源代码是人类语言，我们可以很轻松得理解；但是对于计算机硬件（CPU）而言，这些源代码就好比是天书，它根本无法理解，更无法直接执行。计算机只能够识别某些特定的二进制指令，所以在程序真正运行之前，必须要把源代码转换成计算机可以识别的二进制指令。
所谓的二进制指令，也就是机器码，是CPU能够识别的硬件层面的代码，简陋的硬件（比如古老的单片机）只能使用几十个指令，强大的硬件可以使用成百上千个指令。
然而，究竟在什么时候将源代码转换成二进制指令呢？不同的编程语言有不同的规定：
· 有的编程语言要求必须提前将所有源代码一次性转换成二进制指令，也就是生成可执行程序，比如C、C++、OC、Swift等，这种语言是编译型语言，使用的转换工具是编译器。比如OC的编译器就是Clang。
· 有的编程语言可以一边执行一边转换，需要那些源代码就转换哪些源代码，不会生成可执行程序，比如Python、JS、shell等，这种语言称为解释型语言，使用的工具是解释器。
那么解释型语言和编译型语言各有什么特点呢？它们之间又有什么区别呢？
1，编译型语言
对于编译型语言，需要在开发完成后，将所有的源代码都转换成可执行程序，可执行程序里面包含的就是机器码。只要我们拥有可执行程序，就可以立即执行，不需要再重新编译了，也就是说，“一次编译，多次运行”。
在运行的时候，只需要编译生成的可执行程序，不再需要源代码和编译器，所以说编译型语言可以脱离开发环境运行。
编译型语言一般是不能跨平台的，也就是说，不能在不同的操作系统间随意切换。
编译型语言不能跨平台的表现有两个层面：
1. 可执行程序不能跨平台。这很容易理解，因为不同的操作系统（也可以说是不同的硬件，或者不同的架构）对可执行文件的内部结构有着截然不同的要求，彼此之间也不能兼容，不能跨平台是天经地义。
2. 源代码不能跨平台。不同平台支持的函数、变量、类型等都可能不同，基于某个平台编写的源代码一般不能拿到另一个平台下编译。
2，解释型语言
对于解释型语言而言，每次执行程序都需要一边转换一边执行，用到哪些源代码就将那些源代码转换成机器码，用不到的不进行任何处理。每次执行程序时可能使用不同的功能，这个时候需要转换的源代码也不一样。
因为每次执行程序都需要重新转换源代码，所以解释型语言的执行效率天生就低于编译型语言，甚至存在数量级的差距。
在运行解释型语言的时候，我们始终都会需要源代码和解释器，所以说它无法脱离开发环境。
当我们说“下载一个程序（软件）”的时候，不同类型的语言会有不同的含义：
o 对于编译型语言，我们下载到的是可执行文件，源代码被作者保留，所以编译型语言的程序一般都是闭源的。
o 对于解释型语言，我们下载到的是源代码，因为作者不给源代码就没法运行，所以解释型语言一般都是开源的。
相比于编译型语言，解释型语言几乎都能跨平台，“一份代码，到处运行”是真实存在的。那么，为什么解释型语言就能跨平台呢？这一切都要归功于解释器。
我们所说的跨平台，是指源代码跨平台，并不是解释器跨平台。解释器用来将源代码转换成机器码，它就是一个可执行程序，是绝对不能跨平台的。
官方需要针对不同的平台开发不同的解释器。这些解释器必须要能够遵守同样的语法、识别同样的函数、完成同样的功能，只有这样，同样的代码在不同平台的执行结果才是相同的。
你看，解释型语言之所以能够跨平台，是因为有了解释器这个中间层。在不同的平台下，解释器会将相同的源代码转换成不同的机器码，解释器帮助我们屏蔽了不同平台之间的差异。
JS就是一门解释型语言，它在Android和iOS上的解释器就不一样，我之前写过两篇文章详细介绍过iOS上的js解释器——JSCore，大家可以了解一下：
i. 深入理解JSCore
ii. 深入理解JSCore后续
最后，我将编译型语言和解释型语言的差异总结为下表：

类型	原理	优点	缺点
编译型语言	通过专门的编译器，将所有源代码一次性转换成特定平台执行的机器码	一次编译后，脱离编译器也可以运行，并且运行效率高	可移植性差，不够灵活
解释型语言	由专门的解释器，根据需要将源代码临时转换成特定平台的机器码	跨平台特性好，通过不同的解释器，将相同的源代码转换成不同平台下的机器码	一边执行一边转换，效率很低

二、LLVM概述
上面我们了解了什么是编译器，了解了OC语言的编译器就是Clang。那么LLVM是什么？Clang跟LLVM又有什么关系呢？
首先来聊一聊传统编译器的设计。
1，传统编译器设计


1.1 编译器前端（Frontend）
上图中的SourceCode就是源代码，编译器前端的任务是解析源代码。它会进行：词法分析、语法分析、语义分析、检查源代码是否存在错误，然后构建抽象语法树（Abstract Syntax Tree，AST）。
1.2 优化器（Optimizer）
优化器会负责各种优化，改善代码的运行时间，例如消除冗余计算等。对应下面第三章节的2.4、2.5。
1.3 后端（BackGround）/代码生成器（CodeGenerator）
这一步会将代码映射到目标指令集，生成机器语言，并且会执行机器相关的代码优化。对应下面第三章节的3。
2，LLVM的设计
上面讲了传统的编译器设计，接下来我们就来聊聊LLVM。
LLVM是构架编译器（compiler）的框架系统，它是以C++编写而成，用于优化以任意程序语言编写的程序的编译时间（compile-time）、链接时间（link-time）、运行时间（run-time）以及空闲时间（idle-time），对开发者保持开放，并兼容已有脚本。
LLVM计划启动于2000年，最初由美国UIUC大学的Chris Lattner博士主持开展，2006年Chris Lattner加盟苹果公司，并致力于LLVM在Apple开发体系中的应用。Apple也是LLVM计划的主要资助者。
目前LLVM已经被Apple、FaceBook、Google等各大公司采用。
Clang是LLVM项目中的一个子项目，属于LLVM的编译器前端，不过它仅仅是LLVM的众多编译器前端中的一个，它负责编译C/C++/OC语言。针对不同的语言和架构，LLVM的前端是不一样的。比如在iOS架构下，可以使用Objective-C和Swift，Objective-C/C/C++使用的LLVM前端是Clang，Swift使用的LLVM前端是Swift。如下：


LLVM相对于传统的编译器，最重要的一个优化就是，它会使用通用的代码表示形式IR。也就是说，LLVM的前端最终都会生成IR，然后将IR传入优化器，优化器优化之后传给后端的也是IR。当编译器决定支持多种源语言或者多种硬件架构的时候，LLVM的这个特性的优势将会体现得淋漓尽致。比如说我现在需要支持一门新的语言，那么就只需要添加一个编译器前端即可；再比如新出了一个硬件架构，那么只需要开发对应的一个编译器后端即可。所以LLVM可以为任意的编程语言独立编写前端，并且可以为任何硬件架构独立编写后端：


像其他的编译器，比如GCC，毋庸置疑，它是非常成功的，但是由于它是作为整体应用程序设计的，也就是说，会将编译器前端、优化器和后端统一设计成一个应用程序，结果就是只能用于某一个语言和某一个架构，因此它的用途受到了很大程度的限制。
三、编译流程
接下来我们就走一遍Clang的整个编译流程。
首先，使用Xcode新建一个最简单的MacOS命令行工具工程：


创建出来的工程如下：


接下来我打开终端，并cd到main.m所在的目录下。
首先通过如下命令来打印源码编译流程中的各个阶段：
clang -ccc-print-phases main.m


可以看到，一共有7个阶段，它们分别表示的含义如下：
o 0：input，输入源代码文件
o 1：preprocessor，预处理阶段，头文件的导入、宏的替换都是在这个阶段进行处理
o 2：compiler，编译阶段，词法分析、语法分析、语义分析、检查源代码是否存在错误，最后生成IR代码，并交给下面的后端
o 3：backend，后端，这里LLVM 会通过一个一个的pass去优化，每个pass做一些事情，最终生成汇编代码
o 4：assembler，生成object目标文件，也就是我们熟知的.o文件。
o 5：linker，链接，将各个.o文件以及需要的动态库和静态库链接起来，最终生成可执行文件Mach-o
o 6：bind-arch，针对不同的架构，会生成对应的Mach-o可执行文件。
1，预处理阶段
首先main.m中输入一些内容：


使用如下指令，来对main.m进行预编译，并将预编译的结果重定向到main_pre.m文件中：
clang -E main.m >> main_pre.m
然后相同路径下就会生成一个main_pre.m文件：


我们点开main_pre.m文件查看：


可以看到将近600行代码，而源代码当中也就20行而已。为什么一下子多出来这么多东西？原因就是在预处理阶段将头文件中的相关内容都导入了进来，并且将宏进行了替换。
接下来我再加一行typedef代码：


然后预编译，并将预编译的结果重定向到main_pre.m文件中，结果如下：


可以看到，NormanInt并没有被替换为int，这说明typedef命令并没有在预处理阶段进行处理，也就是说，typedef并不属于预处理指令，它只是给一个类型取别名，类似于Swift中的typealias。
实际上，所有前面加了#的命令都是属于编译阶段预处理的指令，只有这些指令才会在预处理阶段处理。
2，编译阶段
2.1 词法分析
预处理完成之后就会进行词法分析，这里会把代码切成一个个的Token。
我们执行如下指令，就会对源代码进行词法分析：
clang -fmodules -fsyntax-only -Xclang -dump-tokens main.m
结果如下：


可以看到，词法分析就是将代码都拆解成一个一个的Token。比如int a = 1;这行代码，就是被拆解成了int、a、=、1、;这五个Token。
需要注意的是，注释掉的代码不会被编译的哦~
2.2 语法分析
词法分析结束之后就是语法分析，它的任务就是验证语法是否正确。
我们在词法分析中只是将源代码拆解成一个一个的Token，此时并不会验证Token间的组合是否正确，而语法分析的目的就是验证各个Token间的组合关系是否有问题。我们写的代码的语法是否正确，就是在这个阶段检测出来的。
语法分析会在词法分析的基础上，将单词序列组合成各类语法短语，如“程序”、“语句”、“表达式”等等，然后将所有节点组成抽象语法树（Abstract Syntax Tree，AST）。语法分析程序会判断源程序在结构上是否正确。
终端执行如下命令：
clang -fmodules -fsyntax-only -Xclang -ast-dump main.m
之后会生成语法树的结构：


可以看到，这个结构像一棵树-枝-干-叶，所以称之为语法树。我在上图中也做了简单地分析标注，大家可以对比下面的源代码，看看位置是否符合：


实际上，语法树是给机器看的，我们程序员不会闲着没事看这个，我上面也只是做了个简单的解析而已，方便诸位理解语法树到底是个什么东西。
我们知道，当代码的语法有问题的时候，Xcode会报错，比如下面：


此时我执行词法分析的命令，不会有任何问题，因为词法分析只是将源代码拆解成一个一个的Token，它并不会验证Token间的组合是否正确。
但是但我执行语法的命令的时候，就报错了，如下：


通过红框内的信息我们知道，第19行第37个字符上了一个分号，这与Xcode中的报错是一致的。
所以说，我们在写代码的时候，如果语法有错误，那么Xcode会报出警告，这个错误的检查就是在语法分析阶段完成的。
另外还有一点需要说明，如果你需要编译的目标文件中有导入UIKit框架或者Foundation框架下的内容，那么这些头文件可能会找不到，此时，你需要做的是指定SDK：
clang -isysroot /Applications/Xcode.app/Contents/Developer/Platforms/iPhoneSimulator.platform/Developer/SDKs/iPhoneSimulator12.2.sdk   SDK(注意，这里替换成自己的SDK路径)    -fmodules -fsyntax-only -Xclang -ast-dump main.m
注意哦，/Applications/Xcode.app/Contents/Developer/Platforms/iPhoneSimulator.platform/Developer/SDKs/iPhoneSimulator12.2.sdk   SDK是SKD的路径，需要你根据具体情况替换成自己电脑上的SDK路径。并且这里是12.2的版本，但是你的版本要根据你自己电脑上装的SDK版本来。
2.3 生成中间的IR代码
完成了上面的语法分析之后，代码生成器（Code Generation）会将语法树自顶而下进行遍历并逐步翻译成LLVM IR。通过下面的命令可以生成.ll文本文件，.ll文本文件里面就是IR代码。
clang -S -fobjc-arc -emit-llvm main.m
执行之后就会在相同路径下看到，多了一个main.ll文件：


IR的基本语法如下：
o ;  注释
@ 全局标识
o % 局部标识
o alloca 开辟空间
o  align 内存对齐
o i32 32个bit
o  store 写入内存
o  load 读取数据
o  call  调用函数
o ret 返回
接下来我们就来分析一下。
首先将源代码稍微修改一下：


然后调用指令生成一份IR文件，查看该IR文件如下：


2.4 优化
接下来重点分析一下test函数：


经过分析，我们可以知道，这里面做的事情是：
将test函数的参数a0和a1传递给临时变量a3和a4，再将a3和a4传递给临时变量a5和a6，然后计算a5和a6的和并传给a7，然后计算a7和3的和传给a8，最后返回a8。
函数test的功能无非就是计算传入的两参数的和，再加上一个常数3，用得着像上面那样搞那么多中间变量吗？我要是在业务开发中写出这样冗余的代码，恐怕早被打死了。
其实，这样冗余的代码实际上是通过语法树遍历逐步生成的IR代码，这是无可厚非的。那么这样的冗余代码可以被优化吗？答案是可以的。
在Build Settings的code generation里面，有一个优化级别的选项：


可以看到，Debug模式下默认是不优化的，Release模式下才会优化。
再来看一下优化级别的选项：


可以看到，最小的是O0，即不进行任何优化。
接下来我们在llvm指令中修改一下优化级别：
clang -Os -S -fobjc-arc -emit-llvm main.m -o main.ll
执行之后再来看一下IR代码：


再比较一下优化之前的IR代码，可以很明显的地感觉到，冗余代码少了！
这就是LLVM的优化！
接下来聊一聊LLVM优化过程中的节点——pass。pass是很重要的一个概念，他不属于Clang前端，而是属于LLVM后端。
pass是LLVM优化过程中的一个节点，LLVM在优化代码的时候是一个节点一个节点去优化的，每一个节点去做一些优化的事情，最后加起来构成优化的转化，所以说LLVM的优化是由多个pass节点组成的。
我们可以通过自己写pass来改变LLVM的优化，比如可以通过自定义pass节点来使代码的逻辑变得更加复杂（增加一些中间变量、增加一些中间函数的调用），这样做的目的是什么呢？目的就是为了代码混淆。
2.5 bitCode优化
Xcode7之后，如果开启BitCode，那么苹果会在IR代码的基础上做更进一步的优化，最后生成.bc中间代码。
命令如下：
·  clang -emit-llvm -c main.ll -o main.bc
3，生成汇编代码
上一阶段最终生成的.bc或者.ll代码，在这里会生成汇编代码，命令如下：
clang -S -fobjc-arc main.bc -o main.s clang -S -fobjc-arc main.ll -o main.s
前面我们提到，在编译阶段，可以通过调整优化级别参数以及bitcode优化，这里的优化是优化器负责的各种优化。需要注意的是，由IR代码或者bc代码转成汇编的过程中，也可以进行优化，这里的优化是由后端Backend负责的机器相关的代码优化，如下：
clang -Os -S -fobjc-arc main.bc -o main.s clang -Os -S -fobjc-arc main.ll -o main.s
当然，我们也可以不通过前面的步骤，直接通过main.m来生成汇编代码：
clang -Os -S -fobjc-arc main.m -o main.s
其中，-Os是优化级别参数，加上了就会优化，不加就不会优化。
4，生成目标文件
目标文件的生成，是汇编器以汇编代码作为输入，将汇编代码转换为机器代码，最后输出目标文件（object File）。
clang -fmodules -c main.s -o main.o
5，生成可执行文件（Mach-O）
链接器是把编译产生的一堆.o文件和.dylib/.a文件的集合进行链接，最后生成一个mach-o可执行文件。
clang main.o -o main
我们先使用nm命令来查看一下链接之前的main.o文件中的符号：
$xcrun nm -nm main.o


然后对main.o进行链接生成main，之后使用nm命令来查看链接之后的可执行文件main文件中的符号：


可以看到，在_printf函数后面会多出一个(from libSystem)来显示其来源，这就是链接的作用。
当可执行文件main要被执行的时候，main.o内部有一个来自外部的符号，如果要调用该函数，那么就需要dyld在加载的时候进行绑定，那么绑定什么呢？(from libSystem)就告诉dyld需要绑定libSystem库。
我们要执行可执行文件可以使用如下命令：
./main
要查看可执行文件的详情呢，可以使用如下命令：
file main
输出结果如下：
main: Mach-O 64-bit executable x86_64
以上。
参考文献链接
https://mp.weixin.qq.com/s/-f0r2qzt5xq_A6J9nYL20A
https://mp.weixin.qq.com/s/W7pmD9GtN3jtiyujH9bBvw