LLVM笔记(2) - IR

柔光的暖阳◎ 2022-01-07 06:57 333阅读 0赞

1. 什么是IR  
IR(intermediate representation)是LLVM独创的中间表达式. 经典的compiler架构由前端frontend(读入源代码, 通过词法, 语法与语义分析建立AST), 中端optimizer(优化模块)与backend(通过指令选择, 寄存器分配等阶段最终输出为目标架构的汇编). 其中frontend随语言类型变化而变化, backend随目标架构变化而变化, 而优化部分的实现是不区分语言或架构的. 传统的编译器如gcc将中端与后端耦合在一起, 导致每个架构不光要实现后端功能也要实现中端优化, 类似的对不同语言后端也不能复用. 而在LLVM中通过将前端输出的AST转换为LLVM IR实现了前端与中端的分离, 在中端优化完后再将其转换为汇编, 大大节约了编译器开发的工作量. 更多相关介绍详见http://www.aosabook.org/en/llvm.html  
LLVM IR有三种表现形式: 在编译器内部的IR, 在磁盘中存储的bitcode(用于JIT编译器)以及最常见的易于阅读的LLVM IR汇编. 三种格式的IR是等价的(可互相转化), 因此LLVM IR提供了高效的编译器优化手段的同时又保证了方便调试与定位问题.  
使用IR的优点. 1. 通用, 任意语言都能转换为IR, 同一IR能转换为任意架构汇编. 2. 可移植性好, 容易定位问题, 只要保证IR正确性就能确定问题范围(前端还是后端还是某个优化pass). 3. 支持LTO(link time optimization).  
  
2. 如何生成IR  
在编译时添加选项-emit-llvm即可生成IR, 此时的IR为bitcode格式(默认文件名后缀为bc), 若要生成汇编格式还需添加-S选项(默认文件名后缀为ll). 以test.c为例:

1 [23:13:26] hansy@hansy:~/llvm/llvm (master)$ cat ~/test.c
     2 int test(int a, int b)
     3 {
     4   int c = 0;
     5   if (a) {
     6     c = b;
     7     a = c;
     8   }
     9   return c;
    10 }
    11 [23:13:29] hansy@hansy:~/llvm/llvm (master)$ ../llvm_build/bin/clang ~/test.c -O0 -emit-llvm -S -o ~/test.ll
    12 [23:13:37] hansy@hansy:~/llvm/llvm (master)$ cat ~/test.ll
    13 ; ModuleID = '/home/hansy/test.c'
    14 source_filename = "/home/hansy/test.c"
    15 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
    16 target triple = "x86_64-unknown-linux-gnu"
    17 
    18 ; Function Attrs: noinline nounwind optnone uwtable
    19 define dso_local i32 @test(i32 %a, i32 %b) #0 {
    20 entry:
    21   %a.addr = alloca i32, align 4
    22   %b.addr = alloca i32, align 4
    23   %c = alloca i32, align 4
    24   store i32 %a, i32* %a.addr, align 4
    25   store i32 %b, i32* %b.addr, align 4
    26   store i32 0, i32* %c, align 4
    27   %0 = load i32, i32* %a.addr, align 4
    28   %tobool = icmp ne i32 %0, 0
    29   br i1 %tobool, label %if.then, label %if.end
    30 
    31 if.then:                                          ; preds = %entry
    32   %1 = load i32, i32* %b.addr, align 4
    33   store i32 %1, i32* %c, align 4
    34   %2 = load i32, i32* %c, align 4
    35   store i32 %2, i32* %a.addr, align 4
    36   br label %if.end
    37 
    38 if.end:                                           ; preds = %if.then, %entry
    39   %3 = load i32, i32* %c, align 4
    40   ret i32 %3
    41 }
    42 
    43 attributes #0 = { noinline nounwind optnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
    44 
    45 !llvm.module.flags = !{!0}
    46 !llvm.ident = !{!1}
    47 
    48 !0 = !{i32 1, !"wchar_size", i32 4}
    49 !1 = !{!"clang version 9.0.0 (https://github.com/llvm-mirror/clang.git 8a55120a7d72bed6c93749e0a6dbd0a2fcd873dd) (https://github.com/llvm-mirror/llvm.git ff5f64e4c8e72159f06487684037dcd3eca2cd8e)"}

ll文件与bc文件同样能作为源文件被被编译, 编译ll/bc文件时无需特殊选项. 由于这个特性我们可以方便对比不同语言/不同架构的ll来确认问题.  
  
3. IR的特点  
引用官方文档对IR的描述: LLVM is a Static Single Assignment (SSA) based representation that provides type safety, low-level operations, flexibility, and the capability of representing ‘all’ high-level languages cleanly. 作为一门语言IR有如下特点: 基于SSA, 类型安全, 提供低层级操作与支持所有高级语言.  
  
3.1. 什么是SSA. SSA(static single assignment), 静态单赋值, 是指变量必须在使用前被定义(static)且指赋值一次(single assignment). 举个简单的例子:  
  
x = 0;  
x = 1;  
y = 2 \* x;  
  
编译器如何确定y值的来源? 通过引入冗余变量使每个赋值都有对应变量名.  
  
x1 = 0;  
x2 = 1;  
y = 2 \* x2;  
  
在SSA模式下可以方便的定义def-use chain. 然而对于y值来源不确定的情况则需要特殊处理. 以上文程序为例, 局部变量c可能为0(a = 0)或b, 那么在程序返回的节点c的来源可能有两个, 类似的a可能为0(a = 0或a = b)或b.  
  
a1 = a;  
c1 = 0;  
if (a1) \{  
c2 = b;  
a2 = c2;  
\}  
a = phi(a, a2)  
c = phi(c1, c2)  
  
为了解决这个问题SSA引入了phi函数, phi表示该值的来源于多个前驱节点. 关于phi节点的表述在后文中分析.  
  
3.2. 类型系统. LLVM IR是强类型语言, 由于类型系统的支持, LLVM可以无需额外分析即可实现部分转化. LLVM支持的类型如下:  
void type - 无返回值, 无大小  
integer type - 基础类型(simple type), 表示为iN, 其中N为指定位宽, 大小为指定长度位的整型, 注意是无符号整型  
floating point type - 浮点类型, 对应为IEEE754标准浮点数类型  
pointer type - 指针类型, 指向某个内存对象, 注意没有void \*, 而使用i8 \*代替  
array type - 数组类型, 包含元素类型与个数  
label type - 标识代码块, 类似于汇编的label  
token type - 与指令相关的特殊值类型, 比如phi / select等  
struct type -  
aggregate type -  
metadata type -  
x86\_mmx type -  
function type -  
first class type -  
single value type -  
  
4. IR语法简介  
关于IR的reference manual请参考docs/LangRef中完整介绍, 本节的目标是介绍最基础的IR语法.  
  
4.1. 标识符  
LLVM中包含两类标识符: 全局类型与局部类型. 全局类型(函数, 全局变量)以@为起始字符, 局部类型(寄存器名, 类型)以%为标识. 一共有三类标识符, 分别为: 有名变量, 以%或@为起始字符, 后接字符串; 匿名变量以%或@为起始字符, 后接数字; 常量, 后文介绍. 其中有名变量通常源于代码中的变量, 匿名变量来自于LLVM中的临时变量, 寄存器等. 注意匿名变量是LLVM在输出ll时自动顺序命名的(编译过程中并不存在同名的变量, 后文会讲述), 因此必须顺序连续排列(比如将以上代码中%2修改为%3会导致编译不通过).  
4.2. 常量  
与类型系统对应, LLVM提供各类型(bool, int, float, pointer, token)以及复杂类型的常量. 注意两个特殊的常量: zeroinitializer(用于指定内存对象的零初始化)与metadata node(无类型常量).  
4.3. metadata  
metadata是LLVM提供的一种附加信息到某个指令的手段. 有两类metadata原语: metadata node与metadata string. 所有的metadata均以!起始. metadata string是以双引号包含的字符串, metadata node类以于结构体常量的表现方式(用逗号分割的元素列表).  
4.4. Instruction  
//TODO  
4.5. Intrinsic  
//TODO

转载于:https://www.cnblogs.com/Five100Miles/p/10686743.html