LLVM的由来

iOSer都知道LLVM（Low Level Virtual Machine）是Xcode自带的编译器，而在LLVM诞生之前，Apple一直依赖另一个开源编译器GCC。随着Apple收购乔布斯的创业公司NextStep, 面向对象语言Objective-C正式成为Apple官方的开发语言。由于当时GCC社区开发者未能及时支持OC的新语言特性，加上GCC开发者与Apple在编译器支持模块化调用方面的存在分歧，最终让Apple选择分道扬镳，并转头拥抱了另一个开源项目LLVM。
LLVM起源于2000年，是由美国 UIUC 大学的 Chris Lattner 博士发起， Chris Lattner也是后来的Swift之父。在Apple的资助下，LLVM得到了飞速的发展，同时始于2007开发的Clang，因编译快速、占内存少、代码质量高，最终替代笨重的GCC成为LLVM的新前端。LLVM和Clang不断完善功能的同时，也在Apple的MacOS和Xcode IDE中得到工业级的应用和推广，在与Apple的相互成就中，LLVM一跃成为了最领先的开源编译器之一。

LLVM设计理念

与GCC不同，LLVM设计之初注重模块化和可扩展性。比如LLVM的优化器，它支持开发者选择Pass的类型和执行顺序，提供基于模块或库的可组装能力。相对之下，GCC的优化器则是有大量高度耦合的代码组成，很难进行拆分和选择性使用。
模块化的设计理念还体现在LLVM的三段式架构设计中：LLVM通过LIbraries collection完美实现了传统编译器想要的编译前端、编译优化器和编译后端三个核心部件。

编译前端：负责将各种高级语言源代码转换为 LLVM 中间表示（IR）。
编译优化器：对中间表示进行各种优化，以提高代码性能。
编译后端：将优化后的中间表示转换为目标机器的代码。
通过三段式的架构设计，LLVM可以通过灵活切换不同编程语言的前端实现，转化成通用的中间表示，并通过编译后端通过本机编译或者交叉编译适配成目标机器代码，从而实现了高扩展性。LLVM能够快速支持各种新的编程语言，主要得益于三段式架构的高可扩展性。

LLVM架构

传统编译器的三段式架构：

编译前端（Frontend）通过词法、语法、语义一系列分析，构建抽象语法树（AST），AST可以转换成某种中间表示（IR），作为编译优化器（Optimizer）的输入。编译优化器负责对中间代码进行优化，比如无用代码消除、冗余指令合并、函数内联等，以提升代码运行时性能。编译优化器输入IR，最终输出是优化过的IR。经过编译优化器（Optimizer）优化后的IR经过编译后端（Backend）转换成目标平台的机器码。
通过这种组件化的设计，任何编程语言的编译器只要实现了上述3个部件，就能够把对应语言编写的源代码编译成目标平台可运行的机器代码。
但是程序员永远会想着如何提升代码的复用性，何况这些编译器大神们。所以支持多语言多平台的新架构被提出：

上述新架构支持不同的编程语言生成统一的中间表示（IR），新语言只用实现一个新的编译前端（Frontend）,编译优化器（Optimizer）和编译后端（Backend）则可以复用。
在现存的编译器中，JVM、.Net虚拟机提供了定义良好中间表示的字节码，理论上任意语言只要实现编译前端，支持把源代码转成字节码就可以使用JVM或者.Net虚拟机。但是运行时强制JIT编译、GC等并不适合像C这样的编程语言。而另一个新架构的代表GCC, 则因为早期设计中存在的耦合问题比如编译后端（Backend）需要遍历编译前端（Frontend）的AST生成调试信息，编译前端（Frontend）生成编译后端（Backend）的数据结构，以及全局变量和数据结构的滥用，导致三大编译组件耦合，代码复用性较差。
LLVM在实现三段式架构中，汲取了GCC的教训，在设计中采用了模块化设计，整个编译器由一系列可复用的库组成。

LLVM IR

LLVM IR是.ll结尾的文件：

define i32 @add1(i32 %a, i32 %b) {
entry:
  %tmp1 = add i32 %a, %b
  ret i32 %tmp1
}

define i32 @add2(i32 %a, i32 %b) {
entry:
  %tmp1 = icmp eq i32 %a, 0
  br i1 %tmp1, label %done, label %recurse

recurse:
  %tmp2 = sub i32 %a, 1
  %tmp3 = add i32 %b, 1
  %tmp4 = call i32 @add2(i32 %tmp2, i32 %tmp3)
  ret i32 %tmp4

done:
  ret i32 %b
}

对应的C语言代码如下：

unsigned add1(unsigned a, unsigned b) {
  return a+b;
}

// Perhaps not the most efficient way to add two numbers.
unsigned add2(unsigned a, unsigned b) {
  if (a == 0) return b;
  return add2(a-1, b+1);
}

LLVM Optimizer

LLVM优化器提供一系列Pass进行代码优化，这些Pass一般由C++编写，被编译成.o文件集成在.a库中。Pass可以通过PassManager进行创建和添加，方便开发者自由选择Pass进行组合和编排，同时LLVM也支持自定义Pass。以冗余指令合并Pass（InstructionCombine.cpp源码实现）为例：

#include "llvm/Pass.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/Support/raw_ostream.h"
 
using namespace llvm;
 
namespace {
struct MergeInstructions : public FunctionPass {
    static char ID;
 
    MergeInstructions() : FunctionPass(ID) {}
 
    bool runOnFunction(Function &F) override {
        bool Changed = false;
        for (BasicBlock &BB : F) {
            for (Instruction &I : BB) {
                // 这里可以添加合并指令的逻辑
                // 例如，如果发现两个相同的指令，就尝试合并它们
                // 如果成功合并，设置Changed为true
            }
        }
        return Changed;
    }
};
}
 
char MergeInstructions::ID = 0;
static RegisterPass<MergeInstructions> X("mergeinst", "Merge Instructions Pass");

常见的Pass列表：

InstructionCombining：合并简单的指令，以生成更高效的代码。
GVN (Global Value Numbering)：全局值编号，用于消除冗余的计算。
Reassociate：重新关联算术表达式，以优化代码布局。
SCCP (Sparse Conditional Constant Propagation)：稀疏条件常量传播，用于优化条件分支。
SimplifyCFG：简化控制流图，减少不必要的分支和跳转。
LoopUnroll：循环展开，通过减少循环次数来提高执行速度。
LoopIdiomRecognize：识别并优化常见的循环模式。
MemCpyOptimizer：优化内存复制操作。
TailCallElim：消除尾调用，优化函数调用开销。
ConstantPropagation：常量传播，将常量值直接替换到使用它的地方。
DeadStoreElimination：消除死存储，即那些从未被读取的存储操作。
Adce：自动死代码消除，删除无法到达的代码。
PromoteMemoryToRegister：将内存访问提升为寄存器访问，减少内存访问开销。
SimplifyLibCalls：简化库函数调用，将其替换为更高效的代码。
JumpThreading：线程化跳转，通过预测跳转目标来优化控制流。
CorrelatedPropagation：相关传播，用于消除冗余的计算和存储。
IndVarSimplify：归纳变量简化，优化循环中的归纳变量。
LICM (Loop-Invariant Code Motion)：循环不变代码移动，将循环外的代码移到循环内。
BlockPlacement：块放置，优化基本块在函数中的布局。
InlineFunction：内联函数，将小函数的代码直接插入到调用它的地方。

LLVM代码生成

X86平台代码生成过程：

LLVM提供DSL语言对目标平台进行一组.tb文件的特性描述，最终通过tblgen进行处理，生成特定平台的代码。
LLVM还提供链接时和安装时代码优化：

链接时优化

安装时优化

LLVM工具链

Talk is cheap, show me the code.
下面通过简单的C语言代码示例，来看看C源码是怎么被LLVM编译器一步步处理的:
C实现一个简单的加法：

int add() {
    int a = 1;
    int b = 2;
    int c = a + b;
    return c;
}

通过clang把C源码转换成llvm IR：

1	clang -emit-llvm -S Test.c -o Test.ll

通过cat Test.ll打印.ll文件内容：

; ModuleID = 'Test.c'
source_filename = "Test.c"
target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128"
target triple = "arm64-apple-macosx10.12.0"
; Function Attrs: noinline nounwind optnone ssp uwtable(sync)
define i32 @add() #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  %3 = alloca i32, align 4
  store i32 1, ptr %1, align 4
  store i32 2, ptr %2, align 4
  %4 = load i32, ptr %1, align 4
  %5 = load i32, ptr %2, align 4
  %6 = add nsw i32 %4, %5
  store i32 %6, ptr %3, align 4
  %7 = load i32, ptr %3, align 4
  ret i32 %7
}

使用冗余指令合并Pass优化IR：

1	opt -instcombine -S Test.ll -o Output.ll

将LLVM IR转换成bitcode:

1	llvm-as Test.ll -o Test.bc

将bitcode转换成目标平台汇编：

1	llc Test.bc -o Test.s

打印汇编文件内容：

	.section	__TEXT,__text,regular,pure_instructions
	.build_version macos, 10, 0
	.globl	_add                            ; -- Begin function add
	.p2align	2
_add:                                   ; @add
	.cfi_startproc
; %bb.0:
	sub	sp, sp, #16
	.cfi_def_cfa_offset 16
	mov	w8, #1                          ; =0x1
	str	w8, [sp, #12]
	mov	w8, #2                          ; =0x2
	str	w8, [sp, #8]
	ldr	w8, [sp, #12]
	ldr	w9, [sp, #8]
	add	w8, w8, w9
	str	w8, [sp, #4]
	ldr	w0, [sp, #4]
	add	sp, sp, #16
	ret
	.cfi_endproc
                                        ; -- End function

使用即时编译器（JIT）执行bitcode代码：

1	lli Test.bc

LLVM探究

Contents