编译器优化记录(死代码消除+“激进的”死代码消除)

编译器,优化,记录,代码,消除,激进 · 浏览次数 : 16

小编点评

**编译器优化记录(3)——死代码消除+”激进的“死代码消除0. 什么是死代码消除?** **1. 死代码消除 (Dead Code Elimination)** * 算法思想:在死代码消除中,我们希望去掉所有不活跃的变量。 * 维护信息: * HashMap<IRRegister> myMap:记录变量定义的信息。 * HashMap<IRRegister, IRBaseInst>> useMap:记录变量的使用信息。 * HashMap<IRRegister, IRBaseInst> defMap:记录变量的定义信息。 * 算法实现: * 遍历所有变量。 * 对于每个变量,检查其定义和使用情况。 * 如果变量不是被使用,将其从所有维护的信息中删除。 **2. 激进的死代码消除 (Aggressive Dead Code Elimination)** * 算法思想:该算法对于死代码的定义不同,它将递归地定义所有调用函数,函数返回,对存储器的操作为有效代码。 * 维护信息: * HashSet<IRBaseInst> live:所有活跃指令。 * HashSet<entity> liveBlock:所有有活跃指令的基本块。 * HashSet<IRRegister, IRBaseInst> useMap:所有活跃指令的变量使用信息。 * HashSet<IRRegister, IRBaseInst> defMap:所有变量定义信息。 * 算法实现: * 循环遍历所有指令。 * 对于每个指令,将其添加到对应的维护信息集合中。 * 遍历指令的依赖块,并将其添加到对应的集合中。 * 处理控制流语句,并将其添加到对应的集合中。 * 最后遍历所有指令,消除不活跃的phi指令和普通指令。

正文

编译器优化记录(3)——死代码消除+”激进的“死代码消除

0. 什么是死代码消除

相信大家在写C++的时候,如果你定义了一个变量但是没有对其使用,大部分IDE都会对这个变量进行灰色的染色。又或者说,当你开了一个空的循环,在里面定义并使用了一堆和输出值/返回值没有关系的变量,这个时候IDE也会提示你这个循环没有用。这背后都是用到了死代码消除的Pass。

1. 死代码消除(Dead Code Elimination)

1.1 算法思想

我们在死代码消除中希望去掉所有不活跃的变量。那么什么是不活跃呢?容易想到这意味着它定义的变量在接下来会被使用到。注意到,我们是在SSA阶段进行的这个优化,这意味着对于每个变量,它的\(def\)是它的每个\(use\)的必经节点。那么我们可以基于工作表算法写出伪代码:

while (存在某个没有使用点的变量v && 定值v的语句没有其他副作用) {
    删除定值v的这条语句
} 

1.2 需要维护的信息

我们使用HashMap<IRRegister> myMap来维护现有的变量,并使用WorkList

同时,我们给出HashMap<IRRegister, HashMap<IRBaseInst>> useMap来记录所有变量的use,用HashMap<IRRegister, IRBaseInst> defMap来记录所有变量的use

另外,我们注意到,函数的入参并不在我们的考量范围内(我们总不能消掉它们的def吧),所以我们需要用一个HashSet来记录当前函数的所有入参。

1.3 算法实现

大致内容如《现代编译原理:C语言描述》的算法19-5所示。

最后,我们只要把所有的无用变量的\(def\)都删除就行了。

1.4 效果总结

其实,对于死代码消除而言,只要我们写的代码中所有\(def\)的变量都被使用,其优化效果应该是比较差的。但是,我们注意到之前\(\text{Mem2Reg}\)阶段对于所有的支配边界都插入了phi指令。事实上,不是每个支配边界块之后都有对该变量的\(use\),自然,也不一定需要这么多的move语句。所以,一般来说,死代码消除消除的基本都是无效的phi指令。

2. 激进的死代码消除(Aggressive Dead Code Elimination)

2.1 算法思想

它的思想和传统的死代码消除最不一样的地方就在于:它对于死代码的定义不同。

它的定义相当于是递归的:初始,我们定义所有调用函数,函数返回,对存储器的操作为有效代码。之后,我们标记一下语句为有效的:

  • 对其他有效语句的\(use\)进行定值的语句
  • 其他有效语句控制依赖于的语句(至于这个是什么,我们待会儿说)

之后,我们迭代得到所有语句,并把剩下的都删除。那么接下来,我们首先展开控制依赖部分的内容,幸运的是,这一部分和支配树很像。

2.2 控制依赖

我们希望回答的问题是,控制流图上的两个节点\(x,y\)中,\(x\)能否直接控制节点\(y\)的执行?

那么什么是控制执行呢?应该就是节点\(x\)有一个后继\(u\)能直接到达程序的\(exitBlock\)而不经过\(y\)。而它同时也有一个后继\(v\)使得\(v\)\(exitBlock\)的每一条路径都经过\(y\)

那么我们很容易就能得到控制依赖的等价定义。我们考虑CFG对应的反图,则在这张图上,\(x\in domFrontier(y)\)。因为\(x\)的前驱\(v\)\(y\)直接支配,而它又能由\(u\)到达,因而\(x\)\(y\)的支配边界上。

2.3 算法实现

我们需要维护的信息如下:

  1. HashSet<IRBaseInst> live:所有的活跃指令
  2. HashSet<BasicBlock> liveBlock:所有有活跃指令的基本块
  3. HashSet<entity> liveUse :所有活跃指令的\(use\)
  4. HashSet<IRBaseInst> workList:用于迭代的工作表
  5. HashSet<IRRegister, IRBaseInst> defMap:所有变量的\(def\)语句

首先,我们需要建出控制依赖图,这部分参考之前支配树构建的那期。

接下来,我们首先扫描该函数的所有基本块,将所有\(def\)收集到defMap中,同时把所有的store(代表修改全局变量,可能会在其他程序中用到)、所有的call、所有的ret加入workList

然后,我们进行迭代。代码如下:

while (!workList.isEmpty()) {
    IRBaseInst inst = workList.iterator().next();
    workList.remove(inst);
    live.add(inst);
    liveBlock.add(inst.parentBlock);
    liveUse.addAll(inst.uses());
    if (inst instanceof IRPhi irPhi) { // 对于一条phi指令,它的每一个前驱都应当被标注为活跃的
        for (var block : irPhi.blockMap) {
            if (block.terminal != null && !live.contains(block.terminal)) {
                workList.add(block.terminal);
                liveBlock.add(block);
            }
        }
    }
    for (var cdg_pred : inst.parentBlock.cdg_pred) { // 加入该块的所有控制依赖前驱
        if (cdg_pred.terminal != null && !live.contains(cdg_pred.terminal)) {
            workList.add(cdg_pred.terminal); // 注意已经加过的不用加了
        }
    }
    for (var use : inst.uses()) { // 对于其每个use的变量,将其def加入workList
        if (!(use instanceof IRRegister) || use instanceof IRGlobalVar) continue;
        IRBaseInst def = defMap.get(use);
        if (def != null && !live.contains(def)) {
            workList.add(def);
        }
    }
}

最后我们遍历所有指令,消去不活跃的phi指令和普通指令。

这里有一个细节,就是jump/branch这样的terminal的处理。如果一个块的terminal被标记为不活跃的,那么这个块应该跳到哪里呢?自然,它应当跳到它的后继中第一个活跃的块上。我们要在反支配树上寻找(反支配树就是我们根据CFG的反图建出的支配树)。

note: 如果你看了《现代编译原理,C语言描述》,你会发现其中有对CFG加边的操作。但是经笔者实践,不加边并不影响程序的正确性(这很自然),同时也能在整个函数体没用时及时退出。

我们断言,如果一个节点\(x\)是不活跃的,那么说\(x\)\(anti\_dom(x)\)的这些节点一定都不是活跃的如果其中有一个节点是活跃的,那么根据定义,一定能通过若干次\(dominanceFrontier\)的迭代,推出\(x\)是活跃的。那么我们只需要不停地迭代target=target.anti_dom就行了。

2.4 ADCE对程序语义的影响

它的一个弊端在于它会删除不活跃的死循环,从而改变语义(这很明显)。在许多环境下,这被认为是不可接受的。

2.5 ADCE的效果

基本与DCE类似,主要在冗余phi的消除。它的另一个增益在于能消除掉无用的控制流语句。

3. 参考资料

[1] 现代编译原理(C语言实现)Chapter 19.5

与编译器优化记录(死代码消除+“激进的”死代码消除)相似的内容:

编译器优化记录(死代码消除+“激进的”死代码消除)

编译器优化记录(3)——死代码消除+”激进的“死代码消除 0. 什么是死代码消除 相信大家在写C++的时候,如果你定义了一个变量但是没有对其使用,大部分IDE都会对这个变量进行灰色的染色。又或者说,当你开了一个空的循环,在里面定义并使用了一堆和输出值/返回值没有关系的变量,这个时候IDE也会提示你这

编译器优化记录(Mem2Reg+SSA Destruction)

编译器优化记录(2) Mem2Reg+SSA Destruction 写的时候忽然想起来,这部分的内容恰好是在我十八岁生日的前一天完成的。算是自己给自己的一份成长的纪念吧。 0. 哪些东西可以Mem2Reg 顾名思义,Mem2Reg的意思是我们可以通过维护每个函数中局部变量被赋值之后产生的副本来消除

编译器优化记录(控制流图,支配树)

编译器优化记录(1) 0. 为啥要写这个记录 我感觉自己平时整理自己想法的机会实在是太少了。即便是对于自己花了很多时间想、或是花了很多时间学的东西,同样如此。 写编译器优化的阶段学了很多方法,也看到了很多人类智慧,我希望能从头梳理一下认识它们的过程,来更好地体悟。 我身边有几位好朋友一直保持着记录(

[转帖]Linux 性能优化和内核观测 - 文件系统与磁盘I/O篇(一)

文件系统索引节点和目录项为了方便管理,Linux 文件系统为每个文件都分配了两个数据结构,即​​索引节点(index node)​​​和​​目录项(directory entry)​​。它们主要用来记录文件的元信息和目录结构。索引节点(简称 inode):用于记录文件的元数据,比如 inode 编号

[转帖]linux中内核的一个不错的参数somaxconn

最近发现很多内核优化参数都记不住了,写下文章来备记,方便以后查看. 编辑 /etc/sysctl.conf 文件,在里面加入如下内容:(有注释) #设置系统对最大跟踪的TCP连接数的限制(CentOS 5.6无此参数) net.ipv4.ip_conntrack_max = 25000000 #最大

[转帖]编译器优化那些事儿(7):Cache优化

https://bbs.huaweicloud.com/forum/thread-02101103793043210063-1-1.html 引言 软件开发人员往往期望计算机硬件拥有无限容量、零访问延迟、无限带宽以及便宜的内存,但是现实却是内存容量越大,相应的访问时间越长;内存访问速度越快,价格也更

[转帖]编译器优化那些事儿(6):别名分析概述

https://bbs.huaweicloud.com/forum/thread-0211985213969460007-1-1.html 应用性能调优 发表于 2022-09-14 15:03:17298查看 1.简介 别名分析是编译器理论中的一种技术,用于确定存储位置是否可以以多种方式访问。如果

编译器优化丨Cache优化

摘要:本文重点介绍几种通过优化Cache使用提高程序性能的方法。 本文分享自华为云社区《编译器优化那些事儿(7):Cache优化》,作者:毕昇小助手。 引言 软件开发人员往往期望计算机硬件拥有无限容量、零访问延迟、无限带宽以及便宜的内存,但是现实却是内存容量越大,相应的访问时间越长;内存访问速度越快

[转帖]Linux性能优化(十二)——CPU性能调优

Linux性能优化(十二)——CPU性能调优 https://blog.51cto.com/u_9291927/2594259 一、应用程序优化 (1)编译器优化。适当开启编译器优化选项,在编译阶段提升性能。gcc提供优化选项-On会自动对应用程序的代码进行优化。(2)算法优化。使用复杂度更低的算法

XCode汇编调试

汇编调试的意义 了解常用的汇编指令和知识,可以知道经过编译器优化后,最终的代码调用,有可能和源码并不相同,如:设置faster,smallest 代码会更短,最终的汇编执行指令与源码不一样。 可以研究代码在二进制层面的执行流程是否和源码的流程一致,从二进制层面研究方法调用的传参,内部调用,方法返回值