| 代码优化与LLVM IR pass | 您所在的位置：网站首页 › 优化指令 › 代码优化与LLVM IR pass |
|
简介
LLVM IR(Intermediate Representation) 是LLVM的一种中间表示，也可以将它视为中间代码。
中间代码 的生成是为了便于更好的 代码优化。 LLVM Pass 是LLVM代码优化（optimization）中的一个重要组成部分。为便于理解，我们可以将Pass看作一个又一个的模块，各个Pass可以通过IR获取信息为下一个Pass做好准备，又或者直接对中间代码进行优化。代码优化的实质：分析(Analysis)+转换(Transformation) CSCD70是多伦多大学涉及代码优化的一门课程，配套 github上的课件与作业注：本文所设计到的代码优化类型并不全面，仅记录下笔者所学的类型。 1. 基础知识基本块（BasicBlock） 基本块是满足下列条件的 最大 的 连续 中间表示指令序列 控制流只能从基本块的 第一个指令 进入该块。也就是说，没有跳转到基本块中间的或末尾指令的转移指令 除了基本块的最后一个指令，控制流在离开基本块之前不会跳转或停机流图（FlowGraghs） 流图的结点是一些 基本块 从基本块B到基本块C的之前有一条边，当且仅当 基本块C的第一个指令 可能 紧跟在B的最后一条指令之后执行。此时称，B是C的 前驱 (predecessor)，C是B的 后继 (successor) 确认该边的方式 有一个 从B的结尾跳转到C的开头 的条件或无条件跳转语句 按照原来的中间代码序列的顺序，C紧跟在之B后，且B的结尾不存在无条件跳转语句常用的代码优化方法 删除公共子表达式如果表达式x op y先前已被计算过，并且从先前的计算到现在，x op y中的变量值没有改变，则x op y的这次出现就称为公共子表达式（common subexpression） 删除无用代码无用代码(Dead-code)：其计算结果永远不会被使用的语句 常量合并如果在编译时刻推导出一个表达式的值是常量，就可以使用该常量来替代这个表达式。该技术被称为 常量合并 代码移动这个转换的结果是那些 不管循环多少次都得到相同结果的表达式（即循环不变计算，loop-invariant computation），在进入循环之前就对它们进行求值。 强度削弱用较快的操作代替较慢的操作，如用 加 代替 乘 。（例：2*x ⇒ x+x） 删除归纳变量对于一个变量x ，如果存在一个正的或负的常数c使得每次x被赋值时它的值总增加c ，那么x就称为归纳变量(Induction Variable)。在沿着循环运行时，如果有一组归纳变量的值的变化保持步调一致，常常可以将这组变量删除为只剩一个 2. IR语法初探测试代码如下： 123456789101112131415int g;int test(int x){ if(x < 0) x = 2; int val1 = x + 0; int kkk = val1 + 3; int val2 = 2 * x; int val3_1 = x + 1; int val3_2 = val3_1 - 1; return val1 + val2 + val3_1 + val3_2;}将上文中的C++代码用clang编译后生成的IR如下 注意： 用clang编译时，需要设置-O0 -disable-O0-optnone这两项flag，以取消clang自身的代码优化 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162; 一个文件一个模块（Module）; ModuleID = './tests/algebra.bc'source_filename = "./tests/algebra.c"target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"target triple = "x86_64-pc-linux-gnu"; 带有'@'的即为全局符号@g = common dso_local global i32 0, align 4; Function Attrs: noinline nounwind uwtabledefine dso_local i32 @test(i32) #0 { ; 所需的栈空间。align用于对齐内存 %2 = alloca i32, align 4 %3 = alloca i32, align 4 %4 = alloca i32, align 4 %5 = alloca i32, align 4 %6 = alloca i32, align 4 %7 = alloca i32, align 4 ; %0 即函数的第一个参数 store i32 %0, i32* %2, align 4 %8 = load i32, i32* %2, align 4 %9 = icmp slt i32 %8, 0 br i1 %9, label %10, label %11 ; 分支跳转10: ; preds = %1 store i32 2, i32* %2, align 4 br label %1111: ; preds = %10, %1 %12 = load i32, i32* %2, align 4 %13 = add nsw i32 %12, 0 store i32 %13, i32* %3, align 4 %14 = load i32, i32* %3, align 4 %15 = add nsw i32 %14, 3 store i32 %15, i32* %4, align 4 %16 = load i32, i32* %2, align 4 %17 = mul nsw i32 2, %16 store i32 %17, i32* %5, align 4 %18 = load i32, i32* %2, align 4 %19 = add nsw i32 %18, 1 store i32 %19, i32* %6, align 4 %20 = load i32, i32* %6, align 4 %21 = sub nsw i32 %20, 1 store i32 %21, i32* %7, align 4 %22 = load i32, i32* %3, align 4 %23 = load i32, i32* %5, align 4 %24 = add nsw i32 %22, %23 %25 = load i32, i32* %6, align 4 %26 = add nsw i32 %24, %25 %27 = load i32, i32* %7, align 4 %28 = add nsw i32 %26, %27 ret i32 %28}attributes #0 = { noinline nounwind 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"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }!llvm.module.flags = !{!0}!llvm.ident = !{!1}!0 = !{i32 1, !"wchar_size", i32 4}!1 = !{!"clang version 8.0.1-7 (tags/RELEASE_801/final)"} 3. Pass初探LLVM 的pass框架是LLVM系统的一个很重要的部分。LLVM的优化和转换工作就是由多个pass来一起完成的。类似流水线操作一样，每个pass完成特定的优化工作。 要想真正发挥LLVM的威力，掌握pass是不可或缺的一环。 LLVM中pass架构的可重用性和可控制性都非常好，这允许用户自己开发pass或者关闭一些默认提供的pass。 总的来说，所有的pass大致可以分为两类： 分析(analysis)和转换分析类的pass以提供信息为主 转换类(transform)的pass优化中间代码下文是一个简单的pass（CSCD70课程-Assignment1-FunctionInfo） 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include "llvm-9/llvm/Pass.h"#include "llvm-9/llvm/IR/Module.h"#include "llvm-9/llvm/Support/raw_ostream.h"using namespace llvm;namespace {// 继承自ModulePassclass FunctionInfo final : public ModulePass{public: static char ID; FunctionInfo() : ModulePass(ID) {} virtual ~FunctionInfo() override {} // We don't modify the program, so we preserve all analysis. virtual void getAnalysisUsage(AnalysisUsage & AU) const override { AU.setPreservesAll(); } virtual bool runOnModule(Module & M) override { outs() funcEntryBlock -> ... -> funcExitBlock -> EXIT ibv = BC(); // BC 边界条件 else ibv = MeetOp(basicBlock); // 利用fB=fsn⋅…⋅fs2⋅fs1公式，遍历Instruction，计算出当前基础块的OUT集合 for(const Instruction& inst : InstTraversalOrder(basicBlock)) { // 对_inst_bv_map的修改在TransferFunc内 // 传入旧的obv，判断是否修改out集。 obv = _inst_bv_map[&inst]; // TransferFunc的第三个参数感觉有点多余 transform |= TransferFunc(inst, ibv, obv); // 计算出的inst_out集合，是下一次transfer的in集合，所以需要赋值 ibv = obv; } } return transform;}LLVM示例代码 - github c. 静态单一赋值 1). 简介静态单一赋值（static single assignment，SSA），可以归纳成如下语句： SSA是一种，每个变量在程序文本中最多分配一个值，的IR 也就是说，非SSA形式的IR里一个变量可以赋值多次。 SSA 简化了程序中变量的特性。 为了得到SSA形式的 IR，初始 IR 中的变量会被分割成不同的版本（version），其中每个定义（definition）对应着一个版本。通常会在旧的变量名后加上下标构成新的变量名，这也就是各个版本的名字。 显然，在 SSA 形式中，UD 链（Use-Define Chain）是十分明确的。也就是说，变量的每一个使用（use）点只有唯一一个定义可以到达。 SSA的优点： 因为SSA使得每个变量都有唯一的定义，因此数据流分析和优化算法可以更加简单 使用-定义关系链所消耗空间从指数增长降低为线性增长。若一个变量有N个使用和M个定义，若不采用SSA，则存在M×N个使用-定义关系。 SSA中因为使用和定义的关系更加的精确，能简化构建干扰图的算法 源程序中对同一个变量的不相关的若干次使用，在SSA形式中会转变成对不同变量的使用，因此能消除很多不必要的依赖关系。 因为SSA使得依赖分析更加简单、精确，而且PHI节点中的变量不可能同时活跃。因此在SSA形式能协助完成寄存器分配。 2). PhiΦ(Phi) 根据程序的执行流来确定赋的值是什么。请看如下IR代码 LLVM IR 指令 phi 用于实现SSA中的PHI节点。在运行时，phi 指令根据“在当前 block 之前执行的是哪一个 predecessor(前驱节点) block”来得到相应的值。 语法： = phi [fast-math-flags] [ , ], … 在一个基本块中，Phi指令前不允许出现非Phi指令。 123456789101112 %2 = icmp slt i32 %0, 0 br i1 %2, label %3, label %43: ; preds = %1 br label %54: ; preds = %1 br label %55: ; preds = %4, %3 ; 如果执行流通过%3分支，则x = 2; 否则如果;执行流通过%4分支，则x = 0 %.0 = phi i32 [ 2, %3 ], [ 0, %4 ]注：此函数并不是一条实际的指令，需要编译器后端对其做相应的处理，从而得到正确的汇编代码。此过程名为resolution。 若需要启用SSA，则必须在opt命令中添加参数-mem2reg。 mem2reg Pass中的算法会使 alloca 这个仅仅作为 load 和 stores 的用途的指令使用迭代 dominator 边界转换成 PHI 节点，然后通过使用深度优先函数排序重写 loads 和 stores。 这种算法叫做 iterated dominance frontier算法，具体实现方法可以参看 PromoteMemToReg 函数的实现。 3). 如何生成SSA以下述代码为例，程序在函数体结尾会将x的值赋给y。 12345if(x < 0) x = 2;else x = 0;int y = x;那么在代码优化时，我们并不知道赋值于y的值是多少。所以引进了 Φ(Phi) 函数，并重命名了变量 123456// 注：其中的x1，x2的数字都是下标。其本质上还是xif(x < 0) x1 = 2;else x2 = 0;int y = Φ(x1, x2);总结：三步走战略 找出各个内含变量定值的基础块，以及这些基础块所对应的 支配边界什么是支配边界？请阅读本文中 6. 流图中的循环 —— a. 支配结点与回边 的相关内容。 插入PHI节点： PHI节点要插在控制流图的汇聚点处（joint point), 只要在汇聚点之前的分支中有针对某个变量的修改， 就需要在该汇聚点插入针对该变量的PHI节点。 PHI节点的操作数是分支路径中重新定义的变量。 变量重命名： 在插入PHI节点后，SSA中所有针对变量的定义就具备了，接下来就依次在定义处重命名变量，并替换对应的变量使用处。我们需要将 Φ 函数正确插入至代码块中。所以最关键的问题是 —— 插入至何处？ 插入至 各个变量定值所在的基础块集合 的 所有支配边界 。详见下面的算法。 4). Φ(Phi)插入点算法伪代码如下 1234567891011121314151617181920212223242526272829303132333435// @input defsite内含某个变量赋值的所有基础块、DominanceFrontier某基础块的所有支配边界// @output Phi_list 插入点位置// @brief 将Phi节点插入在各个变量定值基础块的所有支配边界上list getPhiList(defsite_list defsite, DominanceFrontier_List dominanceFrontier, var_list vars){ // 初始状态下，Phi_list为空 Phi_list.empty(); // 遍历所有变量 for(var v in vars) { Worklist work_list; // 用内含该变量定值的基础块，对work_list初始化 work_list.initial(defsite[v]); // 如果work_list不是空的，那就继续循环 while(work_list.no_empty()) { Work w = work_list.pop(); // 遍历内含该变量赋值的基础块，其所有支配边界 for(DominanceFrontier df in dominanceFrontier[w]) { // 如果该支配边界并没有被phi插入 if(df not in Phi_list) { // 插入phi Phi_list.push(df); // 如果插入失败（即，当前插入点既不在phi_list，也不在defsite中） if(df not in union_of_sets(defsite[v], Phi_list)) // 将该支配边界添加回work_list work_list.push(df); } } } } return Phi_list;} 5) 参考 编译器后端寄存器分配算法SSA LLVM SSA介绍 LLVM ‘phi’ Instruction 构造Dominator Tree以及Dominator Frontier 6. 流图中的循环 a. 支配结点与回边支配（Dominance）：如果每一条从流图的入口结点到结点 B 的路径都经过结点 A, 我们就说 A 支配（dominate） B，记为 A dom B。 其中，A和B都为 支配节点(Dominator) 换言之， 如果A 支配 B，那么不可能不经过A就可以从入口处到达B。 一个基础块永远 支配自己（ 严格支配 排除支配自己这种情况） 直接支配节点(Immediate Dominator)： 从入口处节点到达节点n的所有路径上，结点n的 最后一个支配节点 称为 直接支配节点。 支配边界（Dominance Frontier）：如果A支配了B的 任何 一个前驱基础块，但A并不 严格支配 B，那么B就是A的支配边界 支配边界确定了 Φ-function 的插入位置。由于每个definition支配对应的uses，所以如果达到了definition所在block的支配边界，就必须考虑其他路径是否有其他相同variable的定义，由于在编译期间无法确定会采用哪一条分支，所以需要放置 Φ-function 下面的图给出了一个示例，给出了图中的支配结点以及支配边界关系。 一旦有了支配边界，我们便可以计算出 Φ 函数正确的插入位置。 LLVM获取支配边界的示例代码 12345678910111213141516171819202122232425262728293031virtual void getAnalysisUsage(AnalysisUsage & AU) const{ // Require that `DominanceFrontier` pass to run first before the // current pass (-> Tutorial 2 Example 2 Pass Manager). AU.addRequired < DominanceFrontierWrapperPass > (); AU.setPreservesAll();}virtual bool runOnModule(Module& M){ /* ....... */ BasicBlock B = .....; Function F = ......; /* ...... */ DominanceFrontier & dom_frontier = getAnalysis (F).getDominanceFrontier(); // DominanceFrontier::iterator指向了数据结构map /* using DomSetMapType = std::map; // Dom set map DomSetMapType Frontiers; */ DominanceFrontier::iterator dom_frontier_iter = dom_frontier.find(&B); for (auto df_set_iter = dom_frontier_iter->second.begin(); df_set_iter != dom_frontier_iter->second.end(); ++df_set_iter) { (*df_set_iter)->printAsOperand(outs(), false); outs() d，那么这条边称为回边。 例子： 7. 消除冗余 a. 基本知识冗余：如果在通向位置p的每条代码路径上，表达式e都已经进行过求值，那么表达式e在位置p处是冗余的。 部分冗余：如果表达式e在到达位置p的部分（而非全部）代码路径上是冗余的，则表达式eee在位置p处是部分冗余的。 为了在很多执行路径中减少表达式被求值的次数，并保证不增加任何路径中的求值次数。我们可以通过移动各个对x op y求值的位置，并在必要时把求值结果保存在临时变量中，来完成这个目的。 在流图中x op y被求值的 位置 可能增多,但只要对表达式求值的 次数 减少即可。 我们期望所使用的部分冗余消除算法进行优化而得到的程序具有如下性质 消除所有不复制代码就可消除的表达式冗余。 不应该执行任何在未优化时不执行的指令。否则可能造成 非预期错误 表达式的计算时刻尽量靠后尽量靠后表达式的计算时刻可以降低该值的生命周期，降低使用寄存器的时间。 b. 懒惰代码移动 1). 介绍 以尽可能延迟计算为目标的部分冗余消除优化称为 懒惰代码运动（Lazy Code Motion） 流图的 关键边（Critical Edge）: 所有从一个具有多个后继节点到达另一个具有多个前驱节点的边。通过在关键边上引入新的基本块，我们总是可以找到一个基本块作为放置表达式的适当位置来健减少冗余。 仅靠增加基本块可能不足以消除所有的冗余计算，必要时需要复制代码，以便于将具有冗余特性的路径隔开。 2). 相关概念 预期执行表达式：（Anticipated expression）如果从程序点p出发的所有路径最终都会计算表达式b+c的值，并且b和c在那时的值就是它们在点p上的值，则一个表达式b+c在程序点p上被 预期执行。一个表达式的各个拷贝所放置的程序点必须 预期执行 此表达式 可用表达式（Will-be-Available Expressions）：一个表达式的多个拷贝会被分别放置到该表达式首次被预期执行的程序点上。如果原来的程序中所有到达程序点p的路径都预期执行这个表达式，则现在这个表达式在点p上可用。这个分析的实质是活跃性分析（对表达式）。 可后延表达式（Postponable Expression）：在所有从程序入口结点到达p的路径中都会碰到一个位置较前的x+y，并且在最后一个这样的位置到p直接没有对x+y的使用，那么表达式x+y就可后延到程序点p上。 被使用表达式(used expression) : 如果在基本块B的出口点被使用的表达式不在B的最后放置（latest）集合中，那么它也是一个在B入口点处被使用的表达式。 部分冗余消除中的四个数据流分析过程 3). 算法前提条件：已经计算出e_gen和e_kill集合 程序块的信息收集 注：下文中的英文名全部指代某个特定集合。 使用e_gen、e_kill集合，计算预期执行表达式集合anticipated预期执行表达式分析（逆向数据流分析）确定一个表达式是否在某个程序点之后的所有路径中被使用。 使用anticipated、e_kill集合，计算可用表达式集合available可用表达式分析（前向数据流分析）计算了一个表达式是否在所有路径中都在该点之前被预期执行。 并通过anticipated、available表达式集合来计算出基本块B的所有最早放置位置集合earliest。一个表达式的最前放置位置就是该表达式在其上被 预期执行 但 不可用 的程序点。 使用earliest、e_use集合，计算可后延表达式集合Postponable可后延表达式是通过前向数据流分析技术找出。 根据earliest、Postponable、e_use集合计算出基本块B的所有最后放置位置集合latest一个表达式的最后放置位置就是该表达式在其上 不可再后延 的程序点。 根据latest、e_use集合，计算出被使用表达式集合used除非一个临时赋值语句被其后的某条路径使用，否则该赋值语句可以被消除。被使用表达式是通过逆向数据流分析技术找出。 利用从数据流计算推导出的知识重写代码 详细算法较为复杂，若有兴趣请移步《编译原理》 4). 参考 编译器优化–6–代码移动 《编译原理》 c. 循环不变量代码移动循环不变量代码移动指的是把循环中的所有重复执行替换为循环外的单次计算,从而优化程序。 具体操作就是将那些，所有操作数不在循环中改变的表达式，从循环内部移动到循环的前置首结点，避免重复计算。 前置首结点(preheader): 循环不变计算将被移至首结点之前，会创建一个称为前置首结点的新块。前置首结点的唯一后继是首结点，并且原来从循环L外到达L首结点的边都改成进入前置首结点。从循环L里面到达首结点的边不变 循环不变量的判定条件： 某个变量如果其表达式的所有操作数都是常量，或者是循环外部的变量，或者是循环内部已经被标定为循环不变量的变量，那么这条表达式被称为循环不变量。 循环不变语句s: x = y + z移动的条件 s所在的基本块是循环所有出口结点(有后继结点在循环外的结点)的支配结点意味着控制流无论流向何处，都一定会执行语句s 循环中没有其它语句对x赋值 循环中对x的引用仅由s到达如何处理嵌套循环 先处理内部循环。之后再处理外部循环，但此时只处理属于外部但不属于内部循环的表达式 在处理外部循环时，此时就可以进一部处理内部循环所外提的表达式了。计算循环不变计算的LLVM检测算法 123456789101112131415161718192021222324252627282930313233343536// 检查当前指令是否是循环不变量bool isInvariant(Instruction * I, Loop* loop){ bool is_invariant = true; // 遍历操作数 for(auto iter = I->op_begin(); is_invariant && iter != I->op_end(); ++iter) { Value* val = dyn_cast(*iter); assert(val != NULL); // 如果当前操作数不是一个常量，那可能是被标定为循环不变量或者其他 // 如果是函数参数则可以视为循环体之外的不变量 // 注意：这里的函数参数，指的是当前循环所在函数的函数参数，不是循环内部调用函数传入的参数 if(!isa (val) && !isa(val)) { if(Instruction* inst = dyn_cast(val)) { // 如果既不是循环不变量指令，也不是循环外的指令 if(FOUND(markedAsInvariant, inst) && loop->contains(inst->getParent())) // 那么该操作数就不是循环不变量 is_invariant = false; } else { // 不是所有遍历到的操作数都是指令、常量和函数参数，可能也有基本块的Label等等 // 其他情况下设置成false肯定没错 is_invariant = false; } } } return isSafeToSpeculativelyExecute(I) // 检查未定义错误，例如除以0。 // 这一条指令可以帮助过滤PHI和跳转指令 && !I->mayReadFromMemory() // 修改读取内存的指令，可能会导致结果值的改变，所以不予处理 && !isa < LandingPadInst > (I) // 异常处理相关的指令，必须在循环内部 && is_invariant;}对于循环不变量提取的代码优化，循环结构do-while可以非常完美的工作，不需要修改CFG 原因是在消除冗余操作中，不应该执行任何在未优化时不执行的指令。 而do-while语句保证了其循环体至少执行一次。这样优化代码时就可以不受此条件的限制。 至于那些LICM无法直接处理的循环结构，为了保证循环结构中的循环不变表达式可以被优化，编译器通常将循环结构转化为do-while结构。例如：while ⇒ if & do-while LLVM示例代码 - github |
| CopyRight 2018-2019 实验室设备网 版权所有 |