枯鱼之泣的博客

LLVM Cookbook读书笔记

LLVM Cookbook读书笔记

题记：

​ 对底层技术的向往一直都是我的追求，编译原理就像是一座高山，一直矗立在那里，等到真正攀登的时候，才发现这座山真的是让人望而却步，所以这篇笔记略有粗浅。

​ 在之前的一家公司，发了很多京东卡，在一次618活动的时候，买了很多计算机的经典巨著，其中一本就是《编译原理》了，此外每次提到编译原理，就想到程序员流传的一张图，上面写着：抱歉，懂编译原理真的是可以为所欲为的。买了书之后只草草的翻了下，那时还没有读《深入理解计算机系统》，C/C++的开发经验也比较少，所以一直没啥进展，但了解编译原理的念头在心中一直萦绕不去，这段时间在图书馆翻到了这本书，感觉挺适合入门的，便快速读完了；

准备工作

​ 安装工具链：LLVM、cmake等，在Mac上使用brew安装即可，我的电脑是M1芯片的，但跑起来没有遇到什么问题：

brew install llvm

​ 安装成功后路径为：/opt/homebrew/Cellar/llvm/15.0.3，在bin路径下有很多工具会用到，比如：llvm-link、clang、opt、lli等；后面会列出他们具体是做什么的。

​ 安装之后可以将LLVM配置好环境变量：

export PATH="/opt/homebrew/Cellar/llvm/15.0.3/bin:$PATH"

一、LLVM基础

1.将C语言转换为LLVM IR：

使用vim写一段C程序：

int mult(){
    int a = 5;
    int b =3;
    int c = a * b;
    return c;
}

执行：

$clang -emit-llvm -S multiply.c -o multiply.ll
2.通过cc1生成IR
$clang -cc1 -emit-llvm multiply.c -o multiply.ll

原理：

将C语言代码编译成LLVM IR的过程从词法分析开始，将C语言源码分解成Token流，每个token表示标识符、字面量、运算符；toke流会传递给语法分析器，语法分析器会在语言的CFG（Context Free Grammar，上下文无关文法）的指导下将token流组织成AST（抽象语法树）；然后分析语义正确性，然后生成IR；

3.将LLVM IR转换为bitcode

LLVM bitecode（字节码-bytecode）

$llvm-as test.ll -o test.bc

.bc文件是位流格式，可以使用hexdump工具查看。

为了将LLVM IR转为bitecode，引入了区块（block）和记录（record）的概念。区块表示位流的区域，例如一个函数体、符号表等；每个区块的内容都对呀一个特定的ID；

4.将LLVM bitcode转换为目标平台汇编码：
// 将LLVM bytecode转为汇编码：
llc test.bc -o test.s
// 通过clang前端从bitecode文件格式生成汇编码clang -S test.bc -o test.s -fomit-frame-pointer

通过-march=archtechture参数，可以生成目标架构的汇编码；

5.将LLVM bitcode转回为LLVM汇编码：
$llvm-dis test.bc -o test.ll

llvm-dis命令即是LLVM反汇编器；

6.转换LLVM IR：

使用opt工具将IR转换为其他形式’=，以及对IR代码实施的多个优化；

$clang -emit-llvm -S multiply.c -o multiply.ll
$opt -mem2reg -S multiply.ll -o multiply1.ll

opt工具是LLVM的优化和分析工具，采用input.ll文件做输入，按照passname执行pass，输出到output.ll文件，如果opt工具传入-analyze参数，会在输入源码上执行不同的分析，并且在标准输出流或者错误流打印分析结果。

opt一些重要的转换：

.adce：入侵式无用代码删除
.bb-vectorize：基本块向量化
.dce：无用代码消除
.deadargelim：无用参数消除
.globaldce：无用全局变量消除
.globalopt：全局变量优化
.inline：函数内联
.instcombine：冗余指令合并
.licm：循环常量代码外提
.sink：代码提升
.tailcallelim：尾调用消除

在将C代码转换为IR之后，运行mem2redPass，帮助了解C指令是如何映射到IR指令的。

7.链接LLVM bitcode：

得到两个LLVM bitcode文件：

$clang -emit-llvm -S test1.c -o test1.ll
$clang -emit-llvm -S test2.c -o test2.ll
$llvm-as test1.ll -o test1.bc
$llvm-as test2.ll -o test2.bc

链接两个LLVM bitcode文件：

$llvm-link test1.bc test2.bc -o output.bc
8.执行LLVM bitcode
$lli output.bc
9.打印抽象语法树，clang作为c前端
$clang -cc1 test.c -ast-dump

-cc1参数保证了只运行编译器前端，而不是编译器驱动。

clang可以作为预处理器、编译器驱动、前端以及代码生成器使用，主要取决于制指定的参数。

二、优化：

LLVM IR是基于SSA形式的，意味着对每个变量的赋值都会产生一个新的变量，或者说变量是不可变的。

LLVM Pass：Pass的作用是优化LLVM IR。Pass作用于LLVM IR，处理IR，分析IR，寻找优化的机会并修改IR产生的代码。命令行工具opt就是用来在LLVM IR上运行各种优化Pass的。

cmake示例：

cmake_minimum_required(VERSION 3.21)
project(chapter2)

set(CMAKE_CXX_STANDARD 14)

# Add header file
set(LLVM_H /opt/homebrew/Cellar/llvm/15.0.3/include)
include_directories({LLVM_H})

#Add target link
set(LLVM_LINK /opt/homebrew/Cellar/llvm/15.0.3/lib/libLLVM.dylib)
link_libraries({LLVM_LINK})

add_executable(chapter2 main.cpp ch2_toy.cpp)
1.多级优化：

从0~3（也有s通常用作空间悠哈），优化级别越高，代码得到的优化越多

$opt -o0 -S example.ll

优化级别（递增）：-o0 -o1 -o2 -o3

2.自定义LLVM Pass

LLVM实现了一系列的分析和转换的pass，所有的LLVM Pass都是pass类的子类。

创建FunctionBlockCount.cpp文件

#include "llvm/pass.h"
#include "llvm/IR/Function.h"
#include "llvm/Support/raw_iostream.h"

using namepsace llvm;

必须实现的函数：

virtual bool runOnFunction(Function &F) = 0;

使用opt工具运行自定义Pass

$clang -o0 -S -emit--llvm sample.c -o sample.ll
$opt -load (path_to.so_file)/FunctionBlockCount.so -functionblockcount sample.ll

opt工具会动态加载动态链接库，以运行pass。

3.Pass间调用：

一个Pass可能会需要其它Pass以得到分析数据、启发或类似信息来指导自己的行为。比如：内存依赖性的分析、需要修改过的IR。

pass调试选项，可以看到Pass使用了哪些分析和优化：

$opt -load (path_to.so_file)/FunctionBlockCount.so -functionblockcount sample.ll -disable-output -debug-pass=Structure
4.独立运行Pass：

使用cmake编译llvm，Pass管理器会在opt命令行工具的Pass流水线中包含新加入的Pass，然后可以独立运行：

$opt -funcblockcount sample.ll
5.实现一个别名分析Pass：

指针别名分析（Alias Analysis）用于判断是否存在两个指针指向同一个地方啊， 即是否存在一个地址被不同的指针使用。

6.无用代码消除Pass：

入侵式无用代码消除，假定所有的代码都是无用的，然后证明它们是有用的。

7.循环常量提升（Loop-Invariant Code Motion-LICM）技术：

循环删除：消除对返回值没有副作用的普通循环（循环次数对循环结果无影响、非死循环）；

8.IR向量化：

向量化代码，在多个数据集上同时执行一条指令。如果后端架构支持向量寄存器，那么一个很宽范围的数据就能存储于这些向量寄存器中，而特殊的向量指令可以操作这些寄存器；

LLVM中有两种类型的向量化，一种是超字并行（Superword Level Parallelism-SLP），另一种是循环向量化（loop vectorization）。循环向量化针对循环，而SLP则把基本块中的线性代码向量化。

三、平台无关

1.LLVM IR指令的生命周期：
  1. C代码到LLVM IR；
  2. IR优化；
  3. LLVM IR转为SelectionDAG；
  4. 合法化SelectionDAG：LLVM IR转化的SelectionDAG节点未必会被目标架构全部支持，因此还需要对DAG节点做出一点修改以适应目标平台，这个过程叫做合法化，不被支持的节点被认为是不合法的；两种合法化：类型合法化和指令合法化。比如：1）如果目标平台只支持32位的整数数据类型，那么DAG中的8位或16位整数的小数据类型需要提升到32位整数类型来表达；2）如果目标架构不支持向量，那么可以把IR中向量的每一个元素抽取成标量形式。
  5. 从平台无关DAG转换为机器DAG：机器指令由一个通用的基于表的.td文件描述，之后这些问价通过tablegen工具转为.inc文件，在.inc文件中用枚举类型描述了目标平台的寄存器、指令集等信息，并且可以直接被C++代码调用（通过include来引入）；
  6. 指令调度，基于SelectionDAG的指令调度，调度器负责安排DAG中指令的执行顺序；
  7. 寄存器分配：LLVM采用贪心算法来进行寄存器分配，即活动周期越长的变量先分配寄存器，生存周期短的变量则填补可用寄存器的时间间隙，减少溢出权重。溢出是由于没有足够的寄存器分配而发生的加载存储操作，溢出权重是溢出的操作开销。在寄存器分配之前指令都是SSA形式的，而在现实世界中SSA形式并不存在，因为不会存在具有无限寄存器的机器；1）寄存器分配旨在最大化分配给虚拟寄存器的物理寄存器数量；2）对于具有相物理位置的寄存器架构来说，可以查看这个架构的RegisterInfo.td文件来了解别名信息；
  8. 代码发射：LLVM中代码发射有两种方式，一种是JIT，直接把代码发射到内存，另一种使用MC框架，对所有的后端目标平台来说，都可以发射汇编和目标文件。
2.SelectionDAG经历的阶段：
  1. 由LLVM IR创建SelectionDAG；
  2. SelectionDAG节点合法化；
  3. DAG合并优化；
  4. 针对目标指令的指令选择；
  5. 调度并发射机器指令；
  6. 寄存器分配-SSA解构、寄存器赋值、寄存器溢出；
  7. 发射机器码；
3.虚拟寄存器映射到物理寄存器

1）直接映射：使用TargetRegisterInfo和MachineOperand类，在这种方式下，开发者需要加载和存储指令的插入位置，以获得和存储内存中的值；

2）间接映射：使用VirtRegMap类来插入加载和存储指令，以获得和存储内存中的值。

4.插入头尾代码：

插入头尾（prologue-epilogue）代码包括栈展开、完成函数布局、保存被调用者保存（calee-saved）寄存器、发射头尾代。除此之外，它也会把抽象栈帧索引替换为适当的引用。

5.代码发射

代码发射阶段把代码生成器的抽象层（如MachineFunction、MachineInstr类）降低为机器码抽象层（如MCInst、MCStreamer类）

四、机器码优化

1.消除机器码的公共子表达式：

CSE算法，用于消除如下的冗余计算，a = b * c + g; d = b * c + e;这里b * c计算两次，优化为tmp = b * c;

2.尾调用优化：

尾调用优化指的是被调函数不创建新的栈帧，而是重用主调函数的栈空间，因此减少栈空间的使用，也减少了相互递归函数返回的开销；

3.兄弟调用优化：

兄弟调用（sibling call）优化，兄弟调用优化是尾调用优化的特例，当被调用者和调用者函数签名函数相似的时候，即返回值类型和函数参数相匹配，就能进行兄弟调用优化；

五、其它

1.LLVM异常原理

当异常被抛出，运行时（runtime）会查找异常处理器，它会查找抛出异常的那个函数对应的异常帧，而这个异常处理器与异常帧相关联，并且包含异常表的引用，而异常表中则包含异常处理的具体实现，即如果编程语言支持异常处理，抛出异常时如何处理；如果语言不支持异常处理，那么关于如何展开当前活动记录和还原前一个活动记录的状态的相关信息则会在异常帧中；

2.使用sanitizer
 $clang -fsanitize=address example.c

工作原理是将代码仪表化，代码仪表化的工作由LLVM Pass完成，由命令行参数fsanitize=address唤起，检查每一条指令，运行时库则把代码中的malloc和free函数替换为自己定义的代码。

虚拟地址空间如何氛围两个独立的类：一块是主应用内存，由常规的应用代码使用；另一块是shadow内存，包含shadow值（元数据）。

sanitizer使用的malloc函数分配的地址称之为污染过的，free函数释放的地址放在隔离区，也是污染过的。

3.使用LLVM编写垃圾回收器

llvm.gcwrite函数是写屏障（write barrier），意味着使用了垃圾回收的程序把一个指针写到堆对象的字段中，因此会通知垃圾回收器；

六、名词解释：

1.LLVM IR（Intermediate Representation）是一种中间语言表示，作为编译器前端和后端的分水岭。 LLVM 编译器的前端——Clang 负责产生IR，而其后端负责消费IR。 编译器IR 的设计体现了 权衡 的计算思维。

2.静态单赋值：一种特殊形式的中间码，每个变量仅被赋值一次。

3.LLVM IR支持各种各样的工具，比如：JIT-即时编译；

4.寄存器溢出：寄存器溢出和栈溢出（stack overflow）不是同一个概念，在基于寄存器的执行模型中，寄存器溢出是由于机器的寄存器数量限制，导致部分变量无法分配于寄存器，因此需要将之溢出到主存中，在使用之前加载到寄存器中，之后再存回主存；

5.代码发射到内存：JIT跳过了可执行文件，直接将代码放到低内存中指定的位置来执行，以达到动态执行的效果；

6.活动变量和活动周期分析，活动周期指的是一个变量的活动范围，即变量的第一次定义到最后一次使用的范围；

6.栈帧lowering（从高级抽象到低级抽象），包括发射函数调用的头尾代码；

kuyuzhiqi

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注