感觉新生赛的 reverse 要被橄榄了，于是哥几个合计合计说要加个 OLLVM 混淆，感觉学不完了（悲

简介

提到 LLVM，可能会有一些陌生，但是如果说到另一个编译框架，那可能是个写代码的应该都见过，那就是 GCC ， GCC的编译分为3个模块：前端，优化器和后端。

1664376484373

而 LLVM 其实和 GCC 差不多，也是分为3个模块

1664376517263

此外，我们一般用来编写 C/C++/OC 语言一般会用到 Clang/LLVM 框架，Clang 的作用是把源文件生成中间代码 IR ，然后经由 LLVM 生成后端。

img

单从编译原理上来说，GCC 和 LLVM 好像感觉差不多，但是 LLVM 作为一个新型的编译器框架，其相比于 GCC 的优势还是非常明显的。

模块化

LLVM 是高度模块化设计的，每一个模块都可以从 LLVM 项目中抽离出来单独使用，也就是说如果想开发一门新的语言，那么只需要把前端模块抽离出来进行修改；如果想应用一个新的平台，那么只需要把后端模块抽离出来进行修改，这相比于三个模块耦合在一起的GCC框架来说无疑是更加方便的。

可拓展

LLVM 为开发者提供了丰富的 API ，例如开发者可以通过 LLVM Pass 框架干预中间代码优化过程，并且配备了完善的文档。编写 LLVM Pass 也是我们基于 LLVM 实现代码混淆的一个很重要的手段。而传统 GCC 框架的拓展门槛很高，难度很大，很难对中间代码的生成进行优化。

安装

下载源代码

在 llvm-project 仓库的 Releases界面 下载 LLVM-Core 和 Clang 源代码：

llvm-12.0.1.src.tar.xz

clang-12.0.1.src.tar.xz

在 /home/Programs 文件夹内创建 llvm-project 文件夹，存放我们刚刚下载的源码压缩包并命名为 clang 和 llvm ，然后再新建一个 build 文件夹存放编译后的 LLVM 。

1664377553210

编译LLVM项目

1
2
3
4
5
6
cd build
cmake -G "Unix Makefiles" -DLLVM_ENABLE_PROJECTS="clang" \
-DCMAKE_BUILD_TYPE=Release -DLLVM_TARGETS_TO_BUILD="X86" \
-DBUILD_SHARED_LIBS=On ../llvm
make
make instal

然后就是漫长的等待过程，差不多装了整整一上午，睡了个午觉醒来才装好，编译完成以后 build 文件夹里张这样。

1664377768476

一次简单的LLVM Pass编译（LLVM——Hello World!）

目标

编写一个 LLVM Pass，遍历程序中的所有函数，并输出 “Hello, ”+ 函数名，这里使用 CMake 对 LLVM Pass 进行编译，CMake其实可以理解为一个项目管理器，了解即可。

类型

LLVM 有多种类型的 Pass 可供选择，包括：ModulePass、FunctionPass、CallGraphPass、LoopPass等等。

这里选择 FunctionPass 类型。

FunctionPass

FunctionPass 以函数为单位进行处理。

FunctionPass 的子类必须实现 runOnFunction(Function &F) 函数。

在 FunctionPass 运行时，会对程序中的每个函数执行runOnFunction 函数。

实践

利用 vscode 中的 Remote - ssh 插件远程连接 Linux 虚拟机，用Cmake进行项目创建，具体目录如下：

1664378567216

Build

存放编译后的 LLVM Pass

Test

TestProgram.cpp：一个简单的CTF逆向题，是我们编写 LLVM Pass 对其进行代码混淆的对象，源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include < cstdio > #include < cstring >
char input[100] = {0};
char enc[100] = "\x86\x8a\x7d\x87\x93\x8b\x4d\x81\x80\x8a\
\x43\x7f\x49\x49\x86\x71\x7f\x62\x53\x69\x28\x9d";
void encrypt(unsigned char * dest, char * src) {
        int len = strlen(src);
        for (int i = 0; i < len; i++) {
            dest[i] = (src[i] + (32 - i)) ^ i;
        }
    }
    //flag{s1mpl3_11vm_d3m0}
int main() {
    printf("Please input your flag: ");
    scanf("%s", input);
    unsigned char dest[100] = {
        0
    };
    encrypt(dest, input);
    bool result = strlen(input) == 22 && !memcmp(dest, enc, 22);
    if (result) {
        printf("Congratulations~\n");
    } else {
        printf("Sorry try again.\n");
    }
}

Transforms/include

存放整个 LLVM Pass 项目的头文件，暂时还没有用到

Transforms/src

存放整个 LLVM Pass 项目的源代码， 也就是我们的 LLVM —— Hello World

源码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include "llvm/Pass.h"
#include "llvm/IR/Function.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm; //llvm 命名空间

namespace // 我们自己的命名空间
{
    class HelloWorld : public FunctionPass // 继承FunctionPass类
    {
        public:
            static char ID; // 变量
            HelloWorld() : FunctionPass(ID) {} // 构造函数
            bool runOnFunction(Function & F); // runOnFunction函数声明
    };
}
bool HelloWorld::runOnFunction(Function & F) // 函数实现，输出 Hello: 函数名
{
    outs() << "Hello: " << F.getName() << "\n"; // outs获取输出流
}
char HelloWorld::ID = 0; // 初始化ID
static RegisterPass<HelloWorld> X("hlw", "LLVM Hello World"); // 向llvm注册Pass并设定参数 hlw，输入该参数就表示用这个 HelloWorld.cpp Pass进行优化

CMakeLists.txt

整个 CMake 项目的配置文件，内容如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
# 参考官方文档：https://llvm.org/docs/CMake.html#developing-llvm-passes-out-ofsource
project(OLLVM++)
cmake_minimum_required(VERSION 3.13.4)
find_package(LLVM REQUIRED CONFIG)
list(APPEND CMAKE_MODULE_PATH "${LLVM_CMAKE_DIR}")
include(AddLLVM)
include_directories("./include") # 包含 ./include 文件夹中的头文件
separate_arguments(LLVM_DEFINITIONS_LIST NATIVE_COMMAND ${LLVM_DEFINITIONS})
add_definitions(${LLVM_DEFINITIONS_LIST})
include_directories(${LLVM_INCLUDE_DIRS})
add_llvm_library( LLVMObfuscator MODULE
src/HelloWorld.cpp
)

test.sh

编译 LLVM Pass 并对 Test 文件夹中的代码进行测试，内容如下：

1
2
3
4
5
6
7
8
cd ./Build #切换到Build文件夹
cmake ../Transforms
make #对Transforms的项目进行编译
cd ../Test
clang -S -emit-llvm TestProgram.cpp -o TestProgram.ll #用clang将源代码编译为中间代码
opt -load ../Build/LLVMObfuscator.so -hlw -S TestProgram.ll -o TestProgram_hlw.ll #加载so文件并设定参数hlw，-S表示为文本格式的中间代码，输出优化后的IR中间代码
clang TestProgram_hlw.ll -o TestProgram_hlw #优化之后的中间代码编译为可执行文件
./TestProgram_hlw #运行

编译完成后的目录如下：

1664380687580

输入 flag 后，出现 Congratulations 而且出现了 Hello：+函数名的输出，说明代码优化和编译成功。

1664380734605

LLVM IR

前面介绍过，LLVM框架中我们会先把前端代码给转化为一个叫 IR （中间代码的东西）， 我们写 LLVM PASS 所优化的对象就是 LLVM IR，因此可以看出，LLVM IR 是 LLVM 中很重要的一个东西，介绍它的文档就一个， LLVM Language Reference Manual — LLVM 16.0.0git documentation ，很全，但是纯英文（English👴可以看原版，像我这种就只能靠机翻）。

那么 LLVM IR 到底是个啥呢？

LLVM IR 是一门低级编程语言，语法类似于汇编，任何高级编程语言（如C++）都可以用 LLVM IR 表示，基于 LLVM IR 可以很方便地进行代码优化，在 LLVM 中，IR 有三种表示：

  • 第一种是可读的 IR，类似于汇编代码，但其实它介于高等语言和汇编之间，这种表示就是给人看的，磁盘文件后缀为.ll
  • 第二种是不可读的二进制IR，被称作位码（bit code），磁盘文件后缀为.bc
  • 第三种表示是一种内存格式，只保存在内存中，所以谈不上文件格式和文件后缀，这种格式是LLVM之所以编译快的一个原因，它不像gcc，每个阶段结束会生成一些中间过程文件，它编译的中间数据都是这第三种表示的IR。

三种格式是完全等价的，我们可以在Clang/LLVM工具的参数中指定生成这些文件（默认不生成，对于非编译器开发人员来说，也没必要生成），可以通过llvm-as和llvm-dis来在前两种文件之间做转换。

1665363814724

IR 的结构

一个源代码文件对应 LLVM IR 中的一个模块（Module），下面一层是LLVM IR 中的函数表示源代码中的某个函数（Function），再下面一层是函数中的若干基本块（Basic Block），再下面是组成基本块的各种指令（Instruction）和标签。

Module 的头部信息包含程序的目标平台，如X86、ARM等等，和一些其他信息，全局符号包含全局变量、函数的定义与声明；Function 由若干基本块组成且有一个入口块；基本块在正常情况下，最后一条指令为跳转指令(br 或 switch)，或返回指令(retn)，也叫作终结指令(Terminator Instruction)。

1665363851592

一些具体的IR代码介绍

终结指令（Terminate Instruction）

retn

对应 return 语句

1
2
ret <type> <value>		; 返回特定类型返回值的return指令
ret void			    ; 无返回值的return指令
1
2
3
ret i32 5					; 返回整数 5
ret void 					; 无返回值
ret {i32, i8} {i32 4, i8 2}   ; 返回一个结构体（少用）

br

BranchInst，对应 if 语句。无条件分支指令类似 jmp 指令，条件分支类似于 jnz， je 等条件跳转指令。

1
2
br i1 <code>, label <iftrue>, label <iffalse>	  ; 条件分支
br lable <dest> 								; 无条件分支
1
2
3
4
5
6
7
Test:                               			; 条件跳转判等
	%cond = icmp eq i32 %a, %b
    br i1 %cond, label %IfEQ, label %IFUEQ
IfEQ:
	ret i32 1
IfUEQ:
	ret I32 0

icmp

整数或者指针的比较指令，条件 cond 可以是 eq（相等），ne（不相等），ugt（无符号大于）等

1
<result> = icmp <cond> <ty> <op1>, <op2> ;比较op1和op2是否满足cond
1
2
3
4
5
6
<result> = icmp eq i32 4, 5             ; yields: result=false eq=equal
<result> = icmp ne float* %X, %X	    ; yields: result=false ne=not equal
<result> = icmp ult i16 4, 5		    ; yields: result=true ult=unsigned less than
<result> = icmp sgt i16 4, 5		    ; yields: result=false sgt=signed greater than
<result> = icmp ule i16 -4, 5		    ; yields: result=false ule=unsigned less or equal
<result> = icmp sge i16 4, 5		    ; yields: result=false sge=signed greater or equal

fcmp

浮点数的比较指令，条件 cond 可以是 oeq（ordered and equal）, ueq（unordered or equal）, false（必定不成立）等

1
<result> = fcmp <cond> <ty> <op1>, <op2>   ; 比较两个浮点数是否满足条件cond
1
2
3
4
<result> = fcmp oeq float 4.0, 5.0  		; yields: result=false
<result> = fcmp one float 4.0, 5.0			; yields: result=true
<result> = fcmp olt float 4.0, 5.0 			; yields: result=true
<result> = fcmp ueq double 1.0, 2.0			; yields: result=false

switch

对应 switch - case 指令，是 br 指令的升级版

1
switch <intty> <value>, label <defaultdest> [ <intty> <val>, label <dest> ... ]
1
2
3
4
5
6
7
8
9
10
11
; 与条件跳转等效
%Val = zext i1 %value to i32
switch i32 %Val, label %truedest [ i32 0, label %falsedest ]

; 与非条件跳转等效
switch i32 0, label %dest [ ]

; 拥有三个分支的条件跳转
switch i32 %val, label %otherwise [ i32 0, label %onzero
								 i32 1, label %onone
								 i32 2, label %ontwo ]

二元运算指令 Binary Operations

add

对应 + 操作符

1
<result> = add <type> <op1>, <op2>
1
<result> = add i32 4, %var   ; yields i32:result = 4 + %var

sub

对应 - 操作符

1
<result> = sub <ty> <op1>, <op2>
1
2
<result> = sub i32 4, %var 			; yields i32:result = 4 - %var
<result> = sub i32 0, %var 			; yields i32:result = -%var

sub

对应 * 操作符

1
<result> = mul <ty> <op1>, <op2>
1
<result> = mul i32 4, %var 			; yields i32:result = 4 * %var

udiv

对应 / 操作符，无符号整数除法指令，如果存在 exact 关键字且 op1 不是 op2 的倍数，就会出现错误。

1
2
<result> = udiv <ty> <op1>, <op2>		 ; yields ty:result
<result> = udiv exact <ty> <op1>, <op2>   ; yields ty:result
1
<result> = udiv i32 4, %var 			; yields i32:result = 4 / %var

sidv

对应 / 操作符，有符号整数除法指令，如果存在 exact 关键字且 op1 不是 op2 的倍数，就会出现错误。

1
2
<result> = sdiv <ty> <op1>, <op2>		 ; yields ty:result
<result> = sdiv exact <ty> <op1>, <op2>   ; yields ty:result
1
<result> = sdiv i32 4, %var 			 ; yields i32:result = 4 / %var

urem

对应 % 操作符

1
<result> = urem <ty> <op1>, <op2>		 ; yields ty:result
1
<result> = urem i32 4, %var 			; yields i32:result = 4 % %var

srem

对应 % 操作符

1
<result> = srem <ty> <op1>, <op2>		 ; yields ty:result
1
<result> = srem i32 4, %var 			; yields i32:result = 4 % %var

按位二元运算 Bitwise Binary Operations

shl

对应 << 运算符，整数左移指令

1
<result> = shl <ty> <op1>, <op2>
1
2
3
4
5
<result> = shl i32 4, %var		; yields i32: 4 << %var
<result> = shl i32 4, 2		    ; yields i32: 16
<result> = shl i32 1, 10		; yields i32: 1024
<result> = shl i32 1, 32		; undefined，因为爆了
<result> = shl <2 x i32> < i32 1, i32 1>, < i32 1, i32 2>		; yields: result=<2 x i32> <i32 2，i32 4>

lshr

对应 >> 操作符，右移以后会在左侧补零。逻辑右移无论是有符号还是无符号，一律当无符号处理。

1
<result> = lshr <ty> <op1>, <op2>
1
2
3
4
5
6
<result> = lshr i324, 1				; yields i32:result = 2
<result> = lshr i32 4, 2 			; yields i32:result = 1
<result> = lshr i8 4, 3				; yields i8:result = 0
<result> = lshr i8 -2, 1 		    ; yields i8:result = 0x7F，把-2右移一位得到0x7f
<result> = lshr i32 1, 32 			; undefined
<result> = lshr <2 x i32> < i32 -2, i32 4>, <i32 1, i32 2>   ; yields: result=<2 x i32><i32 0x7FFFFFF, i32 1>

ashr

整数算术右移指令，右移以后会在左侧补上符号位。

1
<result> = ashr <ty> <op1>, <op2>
1
2
3
4
5
6
<result> = ashr i324, 1				; yields i32:result = 2
<result> = ashr i32 4, 2 			; yields i32:result = 1
<result> = ashr i8 4, 3				; yields i8:result = 0
<result> = ashr i8 -2, 1 		    ; yields i8:result = -1，出现差别
<result> = ashr i32 1, 32 			; undefined
<result> = ashr <2 x i32> < i32 -2, i32 4>, <i32 1, i32 2>   ; yields: result=<2 x i32><i32 -1, i32 0>

and

对应 & 运算符

1
<result> = and <ty> <op1>, <op2>
1
2
3
<result> = and i32 4, %var 			; yields i32:result = 4 & %var
<result> = and i32 15, 40 			; yields i32:result = 8
<result> = and i32 4, 8 			; yields i32:result = 0

or

对应 | 运算符

1
<result> = or <ty> <op1>, <op2>
1
2
3
<result> = or i32 4, %var 			; yields i32:result = 4 | %var
<result> = or i32 15, 40 			; yields i32:result = 47
<result> = or i32 4, 8 				; yields i32:result = 12

xor

1
<result> = xor <ty> <op1>, <op2>
1
2
3
4
5
<result> = xor i32 4, %var 			; yields i32:result = 4 ^ %var
<result> = xor i32 15, 40 			; yields i32:result = 39
<result> = xor i32 4, 8 			; yields i32:result = 12
<result> = xor i32 %V, -1 			; yields i32:result = ~%V

内存访问和寻址操作 Memory Access and Addressing Operations

静态单赋值 Static Single Assignment

SSA 是 IR 的一种属性，也就是说：在程序中一个变量仅能有一条赋值语句

下图这个过程中，由于变量 x, y, z 都被赋值了两次，因此不满足SSA

1665376335940

怎样修改才能让它满足 SSA 呢？

1665376402684

我们把它改成这样就可以了，下面再举一个例子：

1
2
3
4
5
6
7
8
9
#include <cstdio>

int main()
{
    for (int i = 0; i < 100; ++i)
    {
        printf("Hello, %d\n", i);
    }
}

这是一个很简单的 for 循环语句，但是有个问题就是变量 i 被赋值了多次，这是不满足 SSA 原则的，那么怎样修改才能让它满足 SSA 呢？

第一种解决方案：

1
2
3
4
5
6
7
8
9
10
#include <cstdio>

int main()
{
    int *i = (int *) malloc(4);
    for (*i = 0; *i < 100; ++(*i))
    {
        printf("Hello, %d\n", *i);
    }
}

把 i 由 int 型变量变成 int 型指针，我们在操作的时候通过指针来操作内存，这样 i 就只被赋值了一次，而后面的操作也没有对变量 i 进行操作，因此这是符合 SSA 的，这种方法也是 LLVM IR 所采用的。

alloca

内存分配指令，在栈中分配一段空间并获取指针（C中的 malloc 是在堆中分配内存）

1
<result> = alloca <type> [, <ty> <NumElements>] [, align <alignment>]		;分配sizeof(type)*NumElements字节的内存，分配的地址与alignment对齐
1
2
3
4
%ptr = alloca i32					  ;分配4字节的内存并返回i32类型的指针
%ptr = alloca i32, i32 4			   ;分配4*4字节的内存并返回i32类型的指针
%ptr = alloca i32, i32 4, align 1024    ;分配4*4字节的内存并返回i32类型的指针，分配的地址与1024对齐
%ptr = alloca i32, align 1024	  	   ;分配4字节的内存并返回i32类型的指针，分配的地址与1024对齐

为数据类型，比如是i32的数据，为数据的数量。align是对齐的意思，也就是说分配的内存空间会与alignment的对齐。例如alignment是1024，那么分配的地址空间一定是1024的倍数。

store

内存存储指令，即向内存中存储数据，类似指针赋值操作

1
store <ty> <value>, <ty>* <pointer>  ; 向特定类型指针指向的内存存储相同类型的数据
1
2
%ptr = alloca i32
store i32 3, i32* %ptr

store 要和 alloca 搭配使用，先分配空间，再对空间进行赋值。

load

内存读取指令，可以从指针指向的内存中读取数据，类似指针引用操作。

1
load <ty> <value>, <ty>* <pointer>  ; 从特定类型指针指向的内存中读取特定类型的数据
1
2
3
%ptr = alloca i32			; yields i32* :ptr
store i32 3, i32* ptr		; yields void
%val = load i32, i32* %ptr	; yields i32:val = i32 3

类型转换操作 Conversion Operations

trunc…to

截断指令，即大类型向小类型的强制转换

1
<result> = trunc <ty> <value> to <ty2>  ; 将ty类型的变量截断为ty2类型的变量
1
2
3
4
%X = trunc i32 257 to i8 						; yields i8:1
%Y = trunc i32 123 to i1 						; yields i1:true
%Z = trunc i32 122 to i1						; yields i1:false
%W = trunc <2 x i16> <i16 8, i16 7> to <2 x i8> ; yields <i8 8, i8 7>

zext…to

零拓展（Zero Extend）指令，将一种类型的变量拓展为另一种类型的变量，高位补0。

1
<result> = zext <ty> <value> to <ty2>  ; 将ty类型的变量拓展为ty2类型的变量
1
2
3
%X = zext i32 257 to i64 						; yields i64:257
%Y = zext i1 true to i32 						; yields i32:1
%Z = zext <2 x i16> <i16 8, i16 7> to <2 x i32> ; yields <i32 8, i32 7>

sext…to

符号位拓展（Sign Extend）指令，通过复制符号位（最高位）将一种类型的变量拓展为另一种类型的变量。

1
<result> = sext <ty> <value> to <ty2>  ; 将ty类型的变量拓展为ty2类型的变量
1
2
3
%X = sext i8 -1 to i16 							; yields i16:-1
%Y = sext i1 true to i32 						; yields i32:-1
%Z = sext <2 x i16> <i16 8, i16 7> to <2 x i32> ; yields <i32 8, i32 7>

其他操作 Other Operations

phi 指令

如下图，从两个条件分支跳转过来的 y1 和 y2 是不一样的，那么我们应该如何才能知道应该用 y1 还是 y2 呢？

1665403300737

这时候要引入 PHI 指令，$\Phi$函数的运算结果由前驱块而定，如果我们的程序从左边执行下来，那么φ的运算结果就是 y1，右边执行下来结果就是 y2。

1
<result> = phi <ty> [<val0>, <label0>], ... ;如果前驱块为label0，则result=val0 ...

首先得定义 phi 运算的结果的类型 ty ，然后定义了一系列的值以及对应的标签。如果 phi 指令对应的前驱块是 label0，那 phi 的运算结果就是 val0。 

1
2
3
4
Loop: ; Infinite loop that counts from 0 on up. . .
	%indvar = phi i32 [ 0, %LoopHeader ]， [ %nextindvar, %Loop ]
	%nextindvar = add i32 %indvar, 1
	br label %Loop

select

类似于三元运算符

1
<result> = select i1 <cond>, <ty> <val1>, <ty> <val2> ;如果条件cond 成立，result=val1，否则result=val2
1
%X = select i1 true, i8 17, i8 42; yields i8:17

call

调用某个函数

1
<result> = call <ty>|<fnty> <fnptrval>(<function args>)	;调用函数
1
2
%retval = call i32 @test( i32 %argc) 			; 调用test函数，参数为i32类型，返回值为i32类型
call i32 (i8*, ...)* @printf( i8* %msg, i32 12，i8 42) ; 调用printf函数，参数可变

第一个 LLVM Pass —— LLVM Hello World

相当于一个 LLVM Pass 的模板，这里只实现了一个简单的操作：在 runOnFunction 函数中输出 Hello + 函数名。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include "llvm/Pass.h"
#include "llvm/IR/Function.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm; //llvm 命名空间

namespace // 我们自己的命名空间
{
    class HelloWorld : public FunctionPass // 继承FunctionPass类
    {
        public:
            static char ID; // 变量
            HelloWorld() : FunctionPass(ID) {} // 构造函数
            bool runOnFunction(Function & F); // runOnFunction函数声明
    };
}
bool HelloWorld::runOnFunction(Function & F) // 函数实现，输出 Hello: 函数名
{
    outs() << "Hello: " << F.getName() << "\n";   // outs获取输出流
}
char HelloWorld::ID = 0; // 初始化ID
static RegisterPass<HelloWorld> X("hlw", "LLVM Hello World"); // 向llvm注册Pass并设定参数 hlw，输入该参数就表示用这个 HelloWorld.cpp Pass进行优化

我们把这个项目编译到 LLVM 中并优化 TestProgram 的中间代码

1
2
3
4
5
6
7
8
9
cd ./Build #切换到Build文件夹
cmake ../Transforms
make #对Transforms的项目进行编译
cd ../Test
echo "---------------------Hello World-----------------------------"
clang -S -emit-llvm TestProgram.cpp -o IR/TestProgram.ll #用clang将源代码编译为中间代码
opt -load ../Build/LLVMObfuscator.so -hlw -S IR/TestProgram.ll -o IR/TestProgram_hlw.ll #加载so文件并设定参数hlw，-S表示为文本格式的中间代码，输出优化后的IR中间代码
clang IR/TestProgram_hlw.ll -o Bin/TestProgram_hlw #优化之后的中间代码编译为可执行文件
./Bin/TestProgram_hlw flag{s1mpl3_11vm_d3m0} #运行

后面的 LLVM Pass 的编写也将基于这个模板来实现。

基本块分割——Split Basic Block

原理

把每个没有 PHI 指令的基本块分割为若干块，我们对每个基本块的每一条指令进行遍历，在我们需要分割的地方调用 splitBasicBlock方法把当前指令和其之前的基本块分开。

为什么要避开 PHI 指令呢？

因为 PHI 指令的结果由前驱决定， 而基本块分割会改变其前驱，因此我们选择跳过有 PHI 指令的基本块。

在执行分割函数之前，我们需要先用一个 vector 把原先的基本块给存起来。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include "llvm/Pass.h"
#include "llvm/IR/Function.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/IR/Instructions.h"
#include "SplitBasicBlock.h"
#include "llvm/Support/CommandLine.h"
#include <vector>
using std::vector;
using namespace llvm; //llvm 命名空间

// 可选的参数，指定一个基本块会被分裂成几个基本块，默认值为 2
static cl::opt<int> splitNum("split_num", cl::init(2), cl::desc("Split<split_num> time(s) each BB"));

namespace // 我们自己的命名空间
{
    class SplitBasicBlock : public FunctionPass // 继承FunctionPass类
    {
        public:
            static char ID; // 变量
            
            SplitBasicBlock() : FunctionPass(ID) {} // 构造函数
            bool runOnFunction(Function & F); // runOnFunction函数声明
            bool containsPHI(BasicBlock *BB); // 判断基本块有无PHI指令
            void split(BasicBlock *BB); // 对基本块进行分裂
    };
}

bool SplitBasicBlock::containsPHI(BasicBlock *BB)
{
    for(Instruction &I : *BB) // foreach循环遍历传入基本块的所有指令
    {
        if(isa<PHINode>(&I)) return true; //isa<>()判断类型
    }
    return false;
}

void SplitBasicBlock::split(BasicBlock *BB)
{
    int splitSize = (BB->size() + splitNum - 1) / splitNum; //向上取整计算出分裂后的基本块大小
    BasicBlock *curBB = BB; //由于分裂后基本块发生变化，先把基本块存下来
    for(int i = 1; i < splitNum; i++) //分裂splitNum - 1次
    {
        int cnt = 0; // 指令计数器
        for(Instruction &I : *curBB) //遍历所有指令
        {
            if(cnt++ == splitSize) //到达splitSize进行分裂
            {  
                curBB = curBB->splitBasicBlock(&I); //把当前指令和之前的分开，curBB进入到后面的基本快中
                break;
            }
        }
    }
}

bool SplitBasicBlock::runOnFunction(Function & F) 
{
    vector<BasicBlock*> orgBB; // 先把F函数中的基本块给存起来
    for(BasicBlock &BB : F)
    {
        orgBB.push_back(&BB);
    }
    for(BasicBlock *BB : orgBB) // 遍历vector中的基本块
    {
        if(!containsPHI(BB)) // 如果不包含PHI指令，则进行分裂
        {
            split(BB);
        }
    }
    return true;
}

FunctionPass* llvm::createSplitBasicBlockPass() //在 SplitBasicBlock.cpp 中实现 llvm::createSplitBasicBlock 函数：
{
    return new SplitBasicBlock();
}

char SplitBasicBlock::ID = 0;
static RegisterPass<SplitBasicBlock> X("split", "Split a basic block into multiple basic blocks.");

我们还可以在 include 文件夹里注册 SplitBasicBlock Pass 方便写其他 LLVM Pass 的时候直接调用

1
2
3
4
5
6
7
8
9
10
11
12
13
#ifndef _SPLIT_BASIC_BLOCK_H_
#define _SPLIT_BASIC_BLOCK_H_
#include "llvm/IR/Function.h"
#include "llvm/Pass.h"

namespace llvm 
{
    FunctionPass* createSplitBasicBlockPass();
}
#endif
// 在llvm命名空间里添加一个新函数
//这个函数将在 SplitBasicBlock.cpp 里实现
//这样的话其他 LLVM Pass 就可以通过引入头文件 SplitBasicBlock.h ，调用createSplitBasicBlockPass 函数来创建一个 SplitBasicBlock Pass，完成基本块的分割。