bri1987.com

「 编译 」 2023-09-11

SSA全过程记录

阅读次数 26 评论数 0

SSA记录博客

0. 前置准备（可选）

基础知识点

  1. SSA是什么：

    静态单赋值，每次赋值定义一个新的变量，每个变量（包括原始变量和新创建的变量）都只有唯一的一次定义

  2. LLVM中的SSA怎么形成的：

    MemorySSA 通过mem2reg到value SSA

    • 内存：对于每个变量，只要在定义他的时候，为他在内存中划分空间存入，在使用他的时候在取出来，这样就可以达到 SSA 的效果。可以少插入很多不必要的phi函数，对前端生成的速度和难度也是一个考量。

  3. SSA有什么好处：

    • dense分析：要用个容器携带所有变量的信息去遍历所有指令，即便某条指令不关心的变量信息也要携带过去

      sparse分析：变量的信息直接在def与use之间传播，中间不需要遍历其它不相关的指令。

    • 源程序中对同一个变量的不相关的若干次使用，在SSA形式中会转变成对不同变量的使用，因此能消除很多不必要的依赖关系

消除无法到达的基本块

工作表算法

  1. 将entry放入worklist

  2. 每次循环，从worklist中随机拿出一个基本块，将它的visited标记为1

  3. 将被拿出的基本块的true_block和false_block添加进worklist

  4. 将这个被随机拿出的基本块移除worklist

  5. 把visited为0的块都删除

1. 计算支配信息

节点m支配节点n当且仅当从流图入口entry到n的所有路径都经过m，记做：m dom n

在支配树上，如果一个节点n的父节点是m，则称m是n的立即支配节点，记做m=idom(n)

简易版：求交集得dom再往后算idom（略）

  1. 将entry自身加入entry的dom

  2. 将所有会被访问到的基本块加入allNode这个HashSet中

  3. 除了entry外，先默认每一个基本块的dom都是allNode，即放入全集

  4. 除了entry：根据ir顺序遍历所有基本块，对于每一个遍历到的基本块，对于它的所有前驱块：

  5. 将所有前驱块的必经基本块dom求交集，求完之后再并上自己，就是当前块的dom

很显然，支配关系具有自反性，反对称性和传递性，所以支配关系是G上的一个偏序关系

高效版：Lengauer-Tarjan算法得支配树

通过半必经结点定理和必经结点定理构造支配树

时间复杂度为 O(nlogn)

基本思想：

通过DFS构建搜索树，并计算出每个节点的时间戳。

根据半必经点定理，按照时间戳从大到小的顺序计算每个节点的半必经节点。

根据必经点定理，按照时间戳从小到大的顺序，把半必经节点≠必经节点的节点进行修正。

(1) 通过编号得出深度优先生成树

如果在生成树中，a是b的真祖先，则dfnum(a) < dfnum(b)

注意b图标号，一分支右边的标号一定都比左边的大

dfs深度遍历给num即可

(2) 从N最大的block开始

1st. 找每个block的半必经结点

半必经结点：在搜索树T上点y的祖先中，通过非树枝边 可以到达y的深度最小的祖先x其中横叉边的起点永远大与终点编号。

  • 在没有旁路干扰的情况下，n的半必经结点其实就是它的上一级祖先

  • 注意对于第二点“每个祖先”的理解：

    在计算n的半必经结点时（v不是n的祖先时），祖先数组ancestor记录下的只有ancestor[v] = u, ancestor[u] = s，而没有记录到s, ancestor[s] = NULL，而每次while的临界条件是ancetor[x] != NULL，所以在v向上遍历的过程中，只遍历的到u，不会再向上面的祖先s,d,r遍历。

    所以这里计算n的半必经结点时，n的第一个候选是真祖先y，第二个候选是semi(v) = u，第三个候选是semi(u) = s，最终选择s

2nd. 添加bucket, ancestor

将半必经结点相同的block添加到一个bucket中，并加上n和y的ancestor关系

这样做的用意是？（方便找semi信息吧，一个semi block的blocks一起处理，没有细看，TODO 不知道和方便路径压缩有没有关系呢）

3rd. 填充idom
必经结点定理：

以此图为例说明，找n的必经结点：

  • semi(n) = s，在s之下和n之上的生成树路径（y、a、n，注意没有s），我们找到了y，它的semi(y)是d，dfnum最小，所以dfnum(y) != dfnum(n)，n的idom便等于y的idom，即等于d

  • 又比如找y的必经结点，semi(y) = d，在s、y路径上，每个结点半必经结点中最小的半必经结点就是d，即semi(y) = semi(y)，所以idom(y) = semi(y)，就是d

具体代码实现

  • 普通情况：求a的idom，以s --y--a为例，semi(a) = y, ancestor[a] = y, AncestorWithLowestSemi得到的y还是a（第一次相等的不变，ancestor[y] = s还未加入，无法再向上遍历），于是y = v， idom[a] = y

  • 情况1：求y的必经结点，在讨论y时，它的parent是s而不是d，所以在讨论y这一轮不会参加必经结点计算，而需要等到s时，s的p是d，才会一起计算s和y。到s时此处计算y，AncestorWithLowestSemi是s（如果主干直线上还有别的结点，就会一路算完每个结点返回最小semi的结点），semi(s)还是d，于是idom(y) = 此时的p即d

  • 情况2：求n的必经结点。在讨论n时，它的parent是a而不是s，所以在讨论n这一轮不会参加必经结点计算，而需要等到y时，y的p是s，才会计算n。此时，AncestorWithLowestSemi是y，semi[y] != semi[n], semi[y]还没被算出来，但是semi[n] != NULL，于是samedom[n] = y，指n的idom与y的idom相同，但现在y的idom还没算出来，将计算延迟。

    后续：

    在y的idom算出来之后，将y的idom值赋给n的idom

根据idom构造一个支配树

d图比如BMC的iDom都是A，所以这样建支配树

  1. 给每个block初始化一个结构（下为随意举例）

    struct _DomNode{
    BasicBlock *parent;
    BasicBlock *block;
    HashSet *children;  //保存DomNode*,保存直系children
​
    //lsy
    HashSet *all_children;     //以该结点为root的sub-tree的所有孩子
    bool visited;
    bool alpha;             //是不是初始化就加进piggybank中的，如果为true，就是初始化就在的
    bool inphi;
    int level;
};

  2. 从头遍历每个block，每个block的parent是它的iDom，add使得它的iDom的children有block

2. 生成phi函数

0. 前置non-local的semi-pruned SSA

we only insert a f -function for a variable v at the beginning of a block if v is live on entry to that block， 需要先求live set，因为如果是后面没有被用到的变量，根本不需要生成phi

但是它开销大，其实也可能有extra phi会对比如value numbering更好，所以又有了semi-pruned SSA。当然主要是开销大

semi-pruned SSA

有一些value只def和use在同一个基本块中

non-local：在一个block的entry就有的变量

被def过了就不能进Non-local了，non-local就是在该基本块内出现它的def前就被用过了

The non-local set is initialized once; the killed set is reset for each block

优化phi 函数生成：只有non-locals才需要放置phi函数

(1) 算出DF

支配边界Dominance Frontier：

a. 简易遵从定义版

如果是用的简易版本，每个block记录了dom的block：

  1. 将全集添加到allBlocks

  2. 让tempSet内容等于allBlocks

  3. 就用书上x是w的前驱支配节点，但不是w的严格支配节点做：

    举例：5是4的一个前驱（6）的支配节点，但不是4的支配节点；5是5的一个前驱（8）的支配节点，是5的支配节点，但不是5的严格支配节点

    HashSetFirst(allBlocks);
    for(BasicBlock *X = HashSetNext(allBlocks); X != NULL; X = HashSetNext(allBlocks)){
        X->df = HashSetInit();
        HashSetFirst(tempSet);
        for(BasicBlock *Y = HashSetNext(tempSet); Y != NULL; Y = HashSetNext(tempSet)){
            if(HashSetFind(Y->dom,X) && Y->true_block != NULL){
                if(!HashSetFind(Y->true_block->dom,X) || Y->true_block == X){
                    HashSetAdd(X->df,Y->true_block);
                }
            }
            if(HashSetFind(Y->dom,X) && Y->false_block != NULL){
                if(!HashSetFind(Y->false_block->dom,X) || Y->false_block == X){
                    HashSetAdd(X->df,Y->false_block);
                }
            }
        }
    }

b. 遍历必经节点树算DF

这也是一个接近

例：求DF[5]：

  1. DF local[5]：5的后继6和7都以5为idom，所以这一步无

  2. 需要先求DF[6]和DF[7]和DF[8]（必经结点树中的儿子）

DF[6]：

6的后继4 + 8

无儿子

DF[7]：

7的后继12 + 8

无儿子

DF[8]：

8的后继5 + 13

——>> 5的DF是5，4，12，13

总结一下这个算法，求DF[n]：第一部分DF local是关键，就是看CFG直接的几个后继，如果它的idom不是n，说明肯定有其他路径到它，满足边界含义（按定义推的话：它的前驱n是自反支配的，但是n不是它的必经），它肯定是DF。

第二部分看必经结点树的儿子：递归，因为如果CFG中的结点必经n的儿子，肯定也必经n，如果这个到达DF[儿子]中某一节点不必经n的儿子，则肯定满足DF

潜在的O(N2)复杂度

c. 论文O(n)算IDF：

  1. flowgraph：G = (N, E, START, END)

    • N：set of nodes

    • E：set of edges

    • START：a distinguished start node

    • END：a distinguished end node

    |S|：number of elements in the set

  2. subTree(x)：a dominator sub-tree rooted at x;

  3. x.level：the level number(tree depth) of x

  4. DF(x)：x dominates a predecessor of y, but x does notstrictly dominate y

  5. IDF(S)：DF for a set of nodes S（递增顺序）

  6. D-edges：dominator tree edges

    J-edges：

  7. insert J-edge ：O(E)

  8. properties：

    1. dj图中的边数小于相应流图中的节点数和边数之和

    2. y属于DF(x)，则y.level <= x.level（——>> 在找DF(x)时，只需要看level值<=x的node）

      定理2证明：

    3. y in DF(x) 等价于 （有一个Node z，满足z in SubTree(x) and j-dege( z ---> y )，使得y.level <= x.level）

    Lemma 3.1（核心）：

核心定理证明：

得出的算法：

  1. structure PiggyBank：keep the candidate nodes in the order of their respective levels：

    PiggyBank：an array of list of nodes, with index i storing nodes of level i

    • InsertNode()：在正确的level number insert

    • GetNode()：returns the node whose level number is the maximum of all nodes currently stored

    • visit()：查找相关D-edge和J-edge

最终达成：输入一个或多个结点（visited标志位保证多个结点计算时不会重复计算），可动态计算返回指定的一个或者多个Block的DF集合

详细算法详见论文及自己的实现代码。

(2) 找出所有def ( store )和use( load )语句

  • function的结构中有一个loadSet的map，保留了每个被load的value的loadset(set)，loadSet中装的是这个value的load语句出现的基本块。

  • function的结构中有一个storeSet的map，保留了每个store到的value的storeSet(set)，storeSet中装的是store到value的store语句出现的基本块（defBlock）。

(3) 根据DF插入phi

原理：

  1. 首先不是每个汇合点都需要加phi，汇合点指的是前驱个数超过1个的结点。

    比如这个图4的phi就没必要加，因为a2,a1是一样的

  2. 使用DF可行原因：

具体算法实现：

遍历所有有def的value，拿到每个value对应的storeSet

对于每一个value：

将storeSet的block一个个拿出来并从storeSet中移除，拿出它的df，遍历所有df，在df的每个block上面放置phi函数，并将每个df的block加入storeSet。

插入phi函数的时候，每个phi对应映射一下对应的alloca

结果举例：

DF:

比如在基本块10中有store i32 %12,i32* %5,align 4，则在b6和b36都有%5的phi ir

2(id) :@graph=dso_local global [30 x [30 x i32]] zeroinitializer, align 4
1(id) :@store=dso_local global [30 x i32] zeroinitializer, align 4
3(id) :define dso_local i32 @is_clique(i32 %0) #0{
4(id) : %2 = alloca i32,align 4
5(id) : %3 = alloca i32,align 4
6(id) : %4 = alloca i32,align 4
7(id) : %5 = alloca i32,align 4
8(id) : store i32 %0,i32* %3,align 4
9(id) : store i32 1,i32* %4,align 4
11(id) : br label %6
​
12(id) :6:                  ; preds = %32 %0 
0(id) :id 6, val %4
0(id) :id 6, val %5
13(id) : %7 = load i32,i32* %4,align 4
14(id) : %8 = load i32,i32* %3,align 4
15(id) : %9 = icmp slt i32 %7,%8
16(id) : br i1 %9,label %10,label %35
​
17(id) :10:                  ; preds = %6 
18(id) : %11 = load i32,i32* %4,align 4
19(id) : %12= add nsw i32 %11,1
20(id) : store i32 %12,i32* %5,align 4
22(id) : br label %13
​
23(id) :13:                  ; preds = %29 %10 
0(id) :id 13, val %5
24(id) : %14 = load i32,i32* %5,align 4
25(id) : %15 = load i32,i32* %3,align 4
26(id) : %16 = icmp slt i32 %14,%15
27(id) : br i1 %16,label %17,label %32
​
28(id) :17:                  ; preds = %13 
29(id) : %18 = load i32,i32* %4,align 4
30(id) : %19=getelementptr inbounds [30 x i32],[30 x i32]* @store, i32 0,i32 %18
31(id) : %20 = load i32,i32* %19,align 4
32(id) : %21=getelementptr inbounds [30 x [30 x i32]],[30 x [30 x i32]]* @graph, i32 0,i32 %20
33(id) : %22 = load i32,i32* %5,align 4
34(id) : %23=getelementptr inbounds [30 x i32],[30 x i32]* @store, i32 0,i32 %22
35(id) : %24 = load i32,i32* %23,align 4
36(id) : %25=getelementptr inbounds [30 x i32],[30 x i32]* %21, i32 0,i32 %24
37(id) : %26 = load i32,i32* %25,align 4
38(id) : %27 = icmp eq i32 %26,0
39(id) : br i1 %27,label %28,label %29
​
40(id) :28:                  ; preds = %17 
41(id) : store i32 0,i32* %2,align 4
42(id) : br label %36
​
43(id) :29:                  ; preds = %17 
44(id) : %30 = load i32,i32* %5,align 4
45(id) : %31= add nsw i32 %30,1
46(id) : store i32 %31,i32* %5,align 4
47(id) : br label %13
​
48(id) :32:                  ; preds = %13 
49(id) : %33 = load i32,i32* %4,align 4
50(id) : %34= add nsw i32 %33,1
51(id) : store i32 %34,i32* %4,align 4
52(id) : br label %6
​
53(id) :35:                  ; preds = %6 
54(id) : store i32 1,i32* %2,align 4
55(id) : br label %36
​
56(id) :36:                  ; preds = %35 %28 
0(id) :id 36, val %2
0(id) :id 36, val %5
57(id) : %37 = load i32,i32* %2,align 4
58(id) : ret i32 %37
59(id) :}

3. 变量重命名

(1) 遍历一遍第一个基本块，用map装入每个变量和它对应的stack

(2) 重命名

如果没有alloca，就不需要重命名

DFS遍历支配树，对每个根块进行处理后进行重命名（以基本块为单位）

  1. 用一个map计算每个变量和它的定值次数，初值默认为0

  2. 遍历基本块中每个语句：

    • 非phi的每一次使用( load )：用这个变量stack的top替换

    • 变量的每一次定值( store )：将它压入stack，并在该语句中用压入stack的新值替换这个语句中的定值，这个变量的defineTimes++

    • 如果有phi ir（一定在一个基本块最前），%phi = alloca值，则将phi左值也作为定值入栈，definetimes++

  3. 维护该基本块所有的后继基本块中的phi指令 修改对应alloca变量的phi函数中的参数，新建一个pair加入这个phi的pairSet，其中值为该变量栈的top值，注意先判断有没有值，如果没有值的话是undef

  4. DFS遍历支配树的其他块（此时栈内容是继续往下用的）

  5. 将每个变量的栈的所有内容清空了

tips：在重命名时，每次一个block，可以维护一个list记录哪些变量有了def，对于有def的变量，不用每次都压栈，可以直接覆盖（因为下面的值用不到了，但是最初值是不能覆盖的，因为可能后面的Block会用），这也会加快最后弹出栈的速度

*4. pruned-SSA

SSA book的伪代码：

本质上意思还是删除后面没用到的变量的phi

stack is used to store useful and unprocessed variables defined by φ-functions.

  1. 第一次遍历支配树每个块：

    • phi ir：默认左值的useless为true

    • 其他ir：lhs，rhs如果是Phi的左值，将这个Value的Useless设置为false，并将它入栈

  2. 遍历栈，在栈里的都是用过但还未处理的phi左值

    一个个拿出左值的pairSet，如果define也是phi左值并且之前标志为了useless = true，将它改为false，并继续入栈

  3. 第二次遍历（对整个函数的一条条ir），将左值useless为true的phi ir删掉

5. phi函数消除

a set of phi-related variables (source and destination) as a phi-web

最简单的方法： split all critical edges, and then replace φ-functions by copies at the end of predecessor basic blocks（在基本块的末尾进行copy operation）

(1) 边分割

从图b到图c就是边分割的过程

不做的话可能出现Lost copy problem

实现：

按ir顺序遍历每一个Block：

  • 这个Block没有phi ir，直接进入copy环节

  • 这个block有Phi ir，检测边分割：

    如果它的前驱有true和false 2个后继，则就是critical edge，

    • 加Block,然后调整块之间的关系

    • 调整phiInfo里面的前驱块信息

(2) copy

和上面的边分割在一次循环里进行

遍历这个块的所有phi ir，如果phi里面的define value不等于phi左值（不是自引用情况），就insertCopy

insertCopy：block为phi的pair的from，dest为phi ir的左值，src为pair的define value，插入到pair的from的块中

// 针对的是需要拷贝回原来的
void insertCopies(BasicBlock *block,Value *dest,Value *src){
    //有可能是最后一个基本块我们需要判断是branch语句或者jump语句前面
    InstNode *tailIns = block->tail_node;
    while(tailIns->inst->Opcode != br && tailIns->inst->Opcode != br_i1){
        tailIns = get_prev_inst(tailIns);
    }
    //assert(tailIns != NULL);
    InstNode *copyIns = newCopyOperation(src);
    //assert(copyIns != NULL);
    copyIns->inst->Parent = block;
    Value *insValue = ins_get_dest(copyIns->inst);
    insValue->alias = dest;
​
    //应该不会超过10位数
    // 针对这个情况好像没什么用
    insValue->name = (char*)malloc(sizeof(char) * 10);
    strcpy(insValue->name,"%copy");
    ins_insert_before(copyIns,tailIns);
​
    // 由于是CopyOperation 所以phi的type我们已经是设置好了的
}

(3) sequentialize copies

什么时候需要这一步？？感觉没有必要（swap problem）

一个基本块内有多个CopyOperation的话，如果出现b = a, c = b这种情况，需要处理

举例：

int main()
{
    int a=getint(),b=getint();
    while(1){
        int x = a;
        a = b;
        b = x;
​
        if(a > 2*b)
            break;
    }
    return b + a;
}

如果不加这步：

27(id) :9:                  ; preds = %3 
41(id) : %4(%3) = %5
44(id) : %5(%2) = %4
28(id) : br label %3

加之后：

27(id) :9:                  ; preds = %3 
47(id) : %temp(%temp) = %5
48(id) : %5(%3) = %4
49(id) : %4(%2) = %temp
28(id) : br label %3

实现：

  1. 一个block一个block处理

  2. 对CopyOperation，先将src和dest组成一个CopyPair类型的元素加入pCopy这个hashSet，然后删掉这条ir，再seq的时候再加入

  3. 检测在这个block中，有没有CopyOperation的dest成了其他CopyOperation的src，将没有的先进入seq队列，并从pCopy删去。

  4. 将剩下的在pCopy中的pair按照else的做

  5. 将seq中的pair恢复成一条条的CopyOperation

资料引用：

  1. 虎书18-19章（《现代编译原理C语言描述》）

  2. Tarjan算法理解：https://zhuanlan.zhihu.com/p/542396192

  3. CSDN mem2reg源码解读：https://blog.csdn.net/a173373310/category_11246019.html

  4. IDF相关论文：

    • 算法：Vugranam C. Sreedhar and Guang R. Gao. A Linear Time Algorithm for Placing φ-Nodes

    • 理论相关证明：Vugranam C. Sreedhar and Guang R. Gao. Computing φ-nodes in linear time using DJ-graphs.

  5. semi-pruned与pruned SSA，与lost copy, swap problem：

    论文：Practical Improvements to the Construction and Destruction of Static Single Assignment Form

  6. SSA book三四章

bri1987

love chess and music

目录

0%