编译原理(6) LLVM IR

2023-08-09 14:53:19 # NJU # 编译原理

LLVM IR

一、LLVM IR 简介

1. LLVM

基础设施而非编译器

目标: 模块化，可重用

包含范围(黄色)
Clang 为 LLVM 子项目，狭义上的 LLVM 并不包含 Clang

2. Clang

# 和 GCC 类似，直接编译为可执行文件
clang .\hello.c -o hello
# -ast-dump 得到抽象语法树
clang -Xclang -ast-dump -c hello.c

3. IR

3.1 IR

IR: Intermediate Representation(中间表示)

LLVM IR: 带有类型的、介于高级程序设计语言与汇编语言之间

组成	解释
Module	IR 的基本单位，每个 Module 对应一个 .c 文件
Function / Global variables	每个 Module 中有若干函数与全局变量
Basic Block	基本块，由若干指令构成。但是除了最后一条指令(返回或跳转到其他基本块)，全部都是顺序执行指令，不能是分支或跳转

3.2 LLVM IR

示例

opt0

factorial0.c

clang -S -emit-llvm factorial0.c -o f0-opt0.ll

-S: 生成的中间表示是人类可阅读的

-emit-llvm: 生成中间代码就可以停止
f0-opt0.ll

语法	解释
;	注释 `;xxx`
optnone	没有优化
declare	声明函数
define	定义函数
@	全局符号(全局变量/函数名) `@main`
%	局部变量 `%`
i32/i8	32位/8位整型, 类型信息, llvm是强类型
*	指针, `i32*`
icmp	整数间的比较
alloca	分配空间，返回的是指针, 如 i32*
align n	n字节对齐, `align 4`
store	存储数据
call	调用函数
zext	扩展

三地址码(TAC: Three-Address Code, 也称三地址指令)

LLVM 所有指令操作数都小于等于3

mul: 两个操作数 + 一个存结果的虚拟寄存器

静态单赋值(SSA: Static Single Assignment)

每一个变量都只允许定义一次

opt1

clang -S -emit-llvm factorial0.c -o f0-opt1.ll -O1 -g0

-o1: 进行优化

-g0: 去掉 debug 相关信息

可以看到 alloca, store 部分代码被删去
- 解释一: 函数参数没有用到
- 解释二: alloca, store 是内存操作(memory), 其他则是虚拟寄存器操作(register), 使用 -o1 往往会将内存操作优化掉

4. SSA

4.1 $\phi$ 函数

上面的例子都是顺序执行代码，如果遇到分支语句如何满足 SSA

$\phi$ 函数在 LLVM IR 中是一种高级的指令(抽象的), 不对应于具体的机器指令(没有机器指令可以实现)

通常通过分配给一个寄存器或存储到一个公共堆栈内存位置来完成

4.2 CFG

系统调用图只显示了函数间的调用关系, 我们也想了解函数内部的控制流信息

使用控制流图

4.3 举例(递归)

opt0

factorial 函数翻译后被分为 4 段(基本块)

即, 每个函数被分为若干基本块

上方代码之所以没有用到 $\phi$ 函数, 是因为使用了 store load 指令

基本块最后一条指令(结束指令)

opt1

优化后不使用 store load 内存操作, 需要使用 $\phi$ 函数

Single-Static Assignment Form and PHI(How to implement it?)

opt3

4.4 举例(循环)

opt0

opt1

这里做了一个优化, 将判断条件取反, 即判断 val 是否小于 2

为了符合 SSA, 需要对 i 与 temp 进行选择, 分别对应 %6 %7

opt3

2023-08-09 14:53:19 # NJU # 编译原理