LLVM IR优化笔记

基本概念

基本块&CFG：用label和jmp分割代码，形成一个basicblock，以jmp结尾的basicblock向以目标label开头的basicblock连一条边，就形成了CFG
局部代码优化：单个基本块内的优化
- 删除局部公共子表达式
- 删除无用代码(复制传播实现)
- 常量合并(编译时计算常量值)
- 代码移动(将循环中不变的表达式移到循环外)
- 强度削弱(加代替乘)
全局代码优化：多个之间的优化，从CFG入手

SSA学习

概念

SSA 形式的 IR 主要特征是每个变量只赋值一次。相比而言，非 SSA 形式的 IR 里一个变量可以赋值多次。为了得到 SSA 形式的 IR，起初的 IR 中的变量会被分割成不同的版本（version），每个定义（definition：静态分析术语，可以理解为赋值）对应着一个版本。在教科书中，通常会在旧的变量名后加上下标构成新的变量名，这也就是各个版本的名字。

典型的SSA：

use-def chain
一个 def 变量，以及它的全部 use 的集合
def-use chain
一个 use 变量，以及它的全部 def 的集合

Phi函数

phi函数作用是

phi插入算法

Dominance

如果每一条从流图的入口结点A到结点C的路径都经过结点B, 我们就说 B 支配（dominate）C，记为 B dom C。
注意，在这个定义下每个结点都支配它自己。
如果B != C 且 B dom C，那么 B sdom(严格支配) C。入口结点支配所有结点。

严格支配：A严格支配（strictly dominate）结点 B 当且仅当结点 A 与 B 并非同一结点，并且到达结点 B 的所有路径都包含结点 A。简单说，在到达结点 B 的时候，结点 A 中的代码都跑了一遍

Dominator Tree

2 dom 6, 因为2可以通过3或4到6，因此3/4都不能dominate 6

Dominance Frontier

定义：Y 是 X 的支配边界，当且仅当 X 支配 Y 的一个前驱结点（CFG）同时 X 并不严格支配 Y。
注意，前驱节点可能是X自身

支配边界确定了 Φ-function 的插入位置。由于每个definition支配对应的uses，所以如果达到了definition所在block的支配边界，就必须考虑其他路径是否有其他相同variable的定义，由于在编译期间无法确定会采用哪一条分支，所以需要放置 Φ-function。

结点 5 支配边界是 4、5、12、13，也就是结点 5 刚好能力所不能及的地方。

计算支配树

通过支配边界即可确定如何插入phi。
但要确定支配边界的话，需要先构造出 dominator tree，然后借助于 dominator tree来得出支配边界。
支配边界算法：

for each node b
  if the number of immediate predecessors of b ≥ 2
    for each p in immediate predecessors of b
      runner := p
      while runner ≠ idom(b)
        add b to runner’s dominance frontier set
        runner := idom(runner)

插入算法
通过支配边界的插入算法见
https://blog.csdn.net/qq_29674357/article/details/78731713

参考

https://blog.csdn.net/qq_29674357/article/details/78731713
https://blog.csdn.net/dashuniuniu/article/details/52224882

Pass实践

Pass基础

Pass分为两类, 一类是分析(analysis)Pass, 负责收集信息供其它Pass使用, 辅助调试或使程序可视化; 另一类是变换(transform)Pass, 改变程序的dataflow / controlflow. LLVM中实现了几十种优化pass, 其中许多pass运行不止一次. analysis pass存放在lib/Analysis下, transform pass存放在lib/Transforms下

直接看这些pass确实很难懂，我们可以通过一些指令来对比每个pass的效果。

// 进行cse优化，并输出优化前后的对比ir，-S输出ll而不是bc
opt -early-cse -print-before-all -print-after-all 2.ll -S 2>22.ll

// 进行O2优化，-mllvm后的参数表示发送给llvm而不是clang，
clang 2.c -O2 -mllvm -print-after-all -mllvm -filter-print-funcs=sigma -S 2>2.ll

自己的pass写完后，需要重新make llvm，然后opt加载使用即可

1	opt -load /LLVMMydce.dylib -mydce -S 1.ll

有的时候想只个Pass作用，需要到bc然后反编译回去，具体原因我也不知

1
2
3

clang -S -emit-llvm -Xclang -disable-O0-optnone 1.c
opt -early-cse 1.ll -o cse.bc
llvm-dis cse.bc -o -

常用Pass：
-early-cse: 消除公共子表达式
-adce: 消除死代码
-sora: sora
-mem2reg: normal to ssa
-reg2mem: ssa to normal

Pass语法&编写

基础知识

下边代码的版本是LLVM 9.0.0, LLVM真版本号大师
写Pass的时候需要继承LLVM内置的Pass类，可继承的类主要有ModulePass, CallGraphSCCPass, FunctionPass, LoopPass, RegionPass, BasicBlockPass。
常用的是ModulePass和FunctionPass，但是接下来的inlinepass也用到了CallGraphSCCPass等。

ModulePass
继承ModulePass表明你的pass将整个program作为一个单元，可以随意引用函数主体，添加和移除函数。由于不知道ModulePass子类的行为，不能作优化。需要重写runOnModule方法。
我的理解，ModulePass会在当前程序范围内进行操作。
FunctionPass
继承FunctionPass处理程序中每个函数，并不依赖其他函数，FunctionPass不需要它们按特定顺序执行，不会修改外部函数。需要重写runOnFunction方法。
FunctionPass不允许：

访问或修改当前Function之外的Function
从当前Module中 add/remove Function
从当前Module中 add/remove 全局变量

BasicBlockPass
处理基本块
LoopPass
处理Loop
CallGraphSCCPass
自底向上遍历整个程序的CFG，对于CFG的操作or优化需要继承这个Pass。
SCC(Strongly connected component)，强连通分量是图论中的概念。图论中，强连通图指每一个顶点皆可以经由该图上的边抵达其他的每一个点的有向图。

mydce

这个继承了FunctionPass，在每个Function中起作用。
这里我改进了一下，通过遍历每一个Instruction，并通过主要的作用函数I.isSafeToRemove()来判断返回值是否被使用来消除死代码。通过读代码可以看出起作用的其实是mayHaveSideEffects && isa

具体见代码注释

myinliner

参考 llvm-9.0.0.src/lib/Transforms/IPO/AlwaysInliner.cpp

Class LegacyInlinerBase:
继承了CallGraphSCCPass，用于执行一些inline操作。MyInliner继承LegacyInlinerBase。
MyInliner::getInlineCost:
继承LegacyInlinerBase的子类必须实现这个方法来判断展开这个方法的cost，如果返回true，则会展开，否则不展开
MyInliner::runOnSCC:
runOnSCC在call graph中调用，这里执行了inlineCalls(SCC);进行inline展开，他会处理每个scc中的函数。

mycfg

https://github.com/bin2415/llvm_CFGPass
https://blog.csdn.net/pang241/article/details/78076623

调试技巧-printf大法

调试指令

Instruction *MyIn = &I;  //MyIn为一条指令
std::string mystr;
raw_string_ostream stream(mystr);
stream << *MyIn;
mystr = stream.str();
outs()<<"name: "<< mystr << "\n";

调试函数
1
2
StringRef oriValue = Funtion.getName(); //Funtion的名字，类型为StringRef
string mystr = oriValue.str();
https://hujun1413.github.io/2017/01/15/OSLab/LLVM/6.LLVM%E7%9A%84%E7%BC%96%E7%A8%8B%E6%8A%80%E5%B7%A7/

参考

LLVM CookBook
https://llvm.org/doxygen/
https://blog.csdn.net/qq_23599965/article/details/88344459 //pass大全
https://blog.csdn.net/wuhui_gdnt/article/details/83652961 //pass对比