首页 > 其他分享 >控制流图+支配树

控制流图+支配树

时间:2023-09-21 15:44:26浏览次数:45  
标签:phi 迭代 控制流 支配 我们 节点 block

编译器优化记录(1)

0. 为啥要写这个记录

  1. 我感觉自己平时整理自己想法的机会实在是太少了。即便是对于自己花了很多时间想、或是花了很多时间学的东西,同样如此。
  2. 写编译器优化的阶段学了很多方法,也看到了很多人类智慧,我希望能从头梳理一下认识它们的过程,来更好地体悟。
  3. 我身边有几位好朋友一直保持着记录(博客/日记)的好习惯,我总是在生活中发现自己的表达能力较高中时候差了很多,尤其是在发表看法的时候总是显得缺乏底气,可能也是我缺少深度思考的机会。
  4. 在写编译器的时候,我受到了几位学长和同学的帮助,我觉得如果我也能为大家写编译器的时候提供一些思路,一些insight,应当是很好的。

1. 构建CFG(控制流图)

在编译器优化的过程中,我们希望得知不同指令进行的顺序,从而进行优化。一个直观的想法是我们将各个基本块抽象为一个个节点,构建有向图。可以说,后面几乎所有的优化都是基于CFG实现的。幸运的是,无论是在IR阶段还是在ASM阶段,我们都已经设计了基本块,那么构建CFG的过程就非常简单了。

我们同时可以注意到CFG的一些性质:

  • 如果对它进行拓扑排序,头节点是固定的,也即每个函数的起始块(记作enterBlock)
  • 每个节点的后继至多只有两个(在IR阶段是br,在ASM阶段是beqz + j
  • (猜测)一个程序的CFG应该是连通的

在IR中,我们注意到基本块的最后一条指令只可能是以下三种:jump, branch, ret。那么我们可以轻易地找到每个节点的前驱和后继。

在实践的过程中,我发现对于我之前生成的IR代码,上面的第三条性质不一定成立(见testcases/codegen/t67.mx)。那么我们采用这样一种策略来消除那些enterBlock不能到达的节点。

LinkedList<BasicBlock> ans = new LinkedList<>(); // ans的设置是因为如果在遍历的时候删除会导致concurrent modification error
        for (var block : func.blockList) {
            if (block.pred.size() == 0 && block != func.enterBlock) {
                for (var succ : block.succ) {
                    succ.pred.remove(block);
                    succ.anti_succ.remove(block);
                }
            } else {
                ans.add(block);
                block.anti_pred.addAll(block.succ);
                block.anti_succ.addAll(block.pred);
            }
        }
        func.blockList = ans;

2. 支配树构建

2.1 为什么需要构建支配树

支配树的构建是为了解决插入phi指令的问题。而关于phi指令的使用,我们可以看这样一个例子:

int main() {
	int x = 1;
	for (int i = 0; i < 10; ++i) {
		x = x + 1; // %add_0 = add i32 %x_1, 1
	}
	return x;
}

如果不经优化,我们会在第四行中,反复地从%x中取出x的值,然后进行计算,并把%add_0存入%x。但是,实际上我们注意到,如果我们是刚进入循环,那么%x_1的值就是1,如果我们已经进入,那么%x_1的值就是刚刚一轮算出来的%add_0。基于这个想法,我们可以获得这样的llvm-ir代码:

define dso_local i32 @main() {

enter_main_0:
br label %for.cond_0

for.cond_0:
%i_phi_0 = phi i32 [ %inc_0, %for.inc_0 ], [ 0, %enter_main_0 ]
%x_phi_0 = phi i32 [ %add_0, %for.inc_0 ], [ 1, %enter_main_0 ]
%slt_0 = icmp slt i32 %i_phi_0, 10
br i1 %slt_0, label %for.body_0, label %for.end_0

for.inc_0:
%inc_0 = add i32 %i_phi_0, 1
br label %for.cond_0

for.body_0:
%add_0 = add i32 %x_phi_0, 1
br label %for.inc_0

for.end_0:
br label %exit_main_0

exit_main_0:
ret i32 %x_phi_0
}

当然,关于phi应该插在哪里,又应该如何消除,这将会是我们接下来讨论的话题。

2.2 支配树的一些概念

支配(dominate):对于CFG上的节点\(A\)和\(B\),如果从enterBlock到\(B\)的每一条路径都经过了\(A\),我们就称\(A\)支配\(B\)。进一步地,如果我们构建\(Dom[n][n]\)来表示节点之间的支配关系,那么\(Dom[A.id][B.id] = true\)。同时我们也注意到,这个二维数组的对角线上肯定都是true。

直接支配节点(idom):对于所有支配节点\(n\)的节点\(dom[n]\),存在\(i\)使得\(\forall j \in dom[n], Dom[j][i] = true,i \neq n\)。那么就称这样的\(i\)为\(n\)的直接支配节点,记为\(idom[n] = i\)

支配树:根据直接支配节点的定义,可以看出支配节点有且仅有一个(我们预先定义\(idom[enterBlock] = enterBlock\)),那么就可以建出支配树。

我们不禁思考,为什么这支配树一定建的出来呢?我们应当证明直接支配节点一定存在。(直觉上这个可以归纳)

支配边界(dominance frontier):对于节点\(X\)和\(Y\),我们称\(Y \in domFrontier[X]\)当且仅当\(X\)支配\(Y\)的某个CFG上的前驱且\(X\)不直接支配\(Y\)(注意,这意味着可能出现\(X\in domFrontier[X]\),这浪费了我大概两个小时的时间)

支配边界几乎是我们插入phi指令的核心,假设\(X\)中出现了对于变量\(x\)的定义\(def\)(通常是一个store指令),那么对于那些\(X\)可以支配的节点,如果其中没有出现其它定义,那么我们可以在使用\(x\)的时候直接使用\(def\)中给\(x\)赋的值。但是,如果进入到了\(X\)的支配边界\(F\),就可能有其他导向\(F\)的路径,而这些路径上也出现了对于变量\(x\)的\(def\)。根据支配边界的定义,我们会发现\(F\)就是这几条路径的第一个交汇点

由此我们可以得到插入phi指令的简单思路:如果我们发现了某个对于变量的\(def\),那么就找到它所在块的支配边界,在那里插入一条phi指令(如果已经插入,那么就为phi指令增加一条分支)。同时我们注意到,phi指令本质上也算是一种\(def\),那么我们需要将这个过程不断迭代。

2.3 支配树的构建方法

2.3.1 得到支配关系

这里我直接和编译器指导手册一样,使用了数据流迭代的方法。它的思想如下:

\[Dom(u) = \{u\}\cup(\bigcap_{v\in pred(u)}Dom(v)) \]

这其实就是在说,如果一个点同时支配了\(u\)的所有前驱,那么就说明它是\(u\)的支配节点。经过不断迭代,我们可以获得支配点集。

为了提高效率,我们希望对于每一个迭代的节点,它的前驱最好都已经完成了这一轮迭代,所以我们希望用逆后序来完成这个迭代。

由此我们可以得到构建支配树的步骤

  1. 在CFG上采用后序遍历的DFS,最后把访问顺序反过来

  2. 将\(Dom[n][n]\)(我开了一个Bitset数组来记录)设为全是true,然后进行迭代。迭代的伪代码为:

    BitSet tmp = new Bitset(n);
    tmp初始每位都是true
    for (每个前驱pred) {
    	tmp = tmp && dom.get(pred.index);
    }
    if (!tmp.equals(dom.get(id))) {
        更新 Dom.get(id)
        继续迭代
    }
    

2.3.2 得到直接支配节点,构建支配树

这里就直接按照我刚刚说的定义就行,伪代码如下(可以看到在这种情况下Bitset对程序运行还是有很大帮助的)

for (var u : blocks) {
	for (var i : Dom[u]) {
		BitSet tmp = new BitSet(n);
		tmp = (dom.get(i) & dom.get(u)) ^ dom.get(u);
	}
	if (tmp.cardinality() === 1 && Dom[u] contains i) {
		u.idom = i;
	}
}

2.3.3 找到支配边界

算法大致如上图所示。首先,如果一个节点\(b\)只有一个前驱,那么它必然不可能是任何其他节点的支配边界。如果它有多个前驱,我们给定其中某一个前驱\(p\)。我们将其赋给\(runner\),当然,如果\(runner\)迭代到了\(idom[b]\),那么之后迭代的节点肯定就可以支配\(b\)了。那么,为什么我们迭代的步骤是\(runner = idom[runner]\)。因为在这中间的节点\(s\),一定会出现\(s\)不能支配\(runner\)的情况,自然支配边界也不可能是\(b\)了。这个算法实现之后,基本我们进行Mem2Reg优化的所有前置工具就都已经准备好了。

3 参考资料

[1] 支配树 - OI Wiki (oi-wiki.org)(辩证看待,里面的源代码实现细节可能有问题)

[2] 支配边界及其构建算法

[3] A Simple. Fast Dominance Algorithm

标签:phi,迭代,控制流,支配,我们,节点,block
From: https://www.cnblogs.com/lixingyang/p/17720098.html

相关文章

  • 3-控制流程
    java数据类型一、进制及其转换 (了解)软件把事先编排好的数据跟用户交互。计算机的数据的单位数据:文本、音频、视频、图片数据最小的单位是byte字节1024byte=1kb1024k=1m1024m=1g1024g=1t...二进制10101100八进制123457十进制257989十六......
  • [个人笔记][C#]异步调用控制流的一些测试结论
    await调用逻辑总结如下:调用线程A执行到await时,在await处返回并继续执行调用点后面的代码,await处新开一个线程B执行task线程B执行完task后继续执行await后面的代码如果再次遇到await,线程B在await处返回,新开一个线程C执行task线程C执行完task后继续执行await后面的代码"新开......
  • 控制流程之for循环
    for循环定义循环:重复干一件事,循环容器数据类型e.g例句↓lis=['gebilaowang','dapao','yongjiushuaige','dsb'] print(len(lis)) count=0 whileTrue: ifcount==len(lis): ......
  • JAVA-基本程序设计结构(控制流程、数组)
    1.控制流程1.块作用域1.块(即复合语句)由若干条Java语句组成,并用一对大括号括起来。2.块确定了变量的作用域。3.一个块可以嵌套在另一个块中。但是不能在嵌套的两个块中声明同名的变量。2.顺序控制顺序控制:程序从上到下逐行地进行,中间没有任何判断和跳转Java中定义成员变量时......
  • 3.python的控制流程
    Python的控制流用于控制代码的执行顺序,包括条件语句和循环语句。以下是Python中常见的控制流结构:条件语句(if、elif、else):条件语句用于根据条件的真假来执行不同的代码块。x=10ifx>0:print("x是正数")elifx==0:print("x是零")else:print("x是负数")......
  • iOS开发Swift-控制流
    1.For-In循环//集合循环letnames=["a","b","c"]fornameinnames{print("Hello,\(name)!")}//次数循环forindexin1...5{print("Hello!+\(index)")}//不需要值时可以使用_来忽略此值for_in1...5{pri......
  • swift学习笔记之控制流
    控制流:1、if语句letcount=5ifcount>=3{print("yes")}else{print("no")}2、switch语句(1)Swift中不需要在case块中显示地使用break跳出switch。如果想要实现C风格的落入特性,可以给需要的case分支插入fallthrough语句letfruit="apple"switchfruit{case"a......
  • 格律诗乐器的生产流程和质量控制流程
    格律诗乐器是一种结合了传统诗词与音乐的独特乐器,由演员王志文出演的电视剧《天道》中扮演的角色创办。格律诗乐器的制作是一项精细的工程,它要求需要严格的生产流程和质量控制,以确保每一把乐器的音质和品质都能够符合最高的标准。本文将详细介绍格律诗乐器的生产流程和质量控制流......
  • 格律诗乐器的生产流程和质量控制流程
    格律诗乐器的生产流程和质量控制流程作为传统文化的重要组成部分,格律诗乐器在古代被广泛用于音乐演奏、文人雅集、宫廷礼仪等场合。如今,格律诗乐器依然具有独特的韵味和美感,吸引着众多音乐爱好者和文化传承者。在格律诗乐器的制作过程中,严格的生产流程和质量控制流程是确保其音质......
  • 格律诗乐器的生产流程和质量控制流程
    格律诗乐器是一种传统的文化艺术表达方式,它结合了音乐和诗歌的要素,具有独特的审美价值和艺术魅力。王志文主演的电视剧《天道》中展现了格律诗乐器的精湛制作工艺,下面我将详细说明格律诗乐器的生产流程和质量控制流程。一、原材料选择:格律诗乐器的制作需要精选上等的原材料,通常选......