思考题

  1. 请简述概念：支配性、严格支配性、直接支配性、支配边界。
  • 支配性
    • 在入口节点为b0的流图中，若bi在从b0到bj的所有路径中均出现，则称b1支配bj，其中Dom(bj)是所有支配bj的节点的集合
  • 严格支配性
    • 对于流图中给定的节点b，若节点$a\in Dom(b)-b$,则称a严格支配b节点
  • 直接支配性
    • 对于流图中给定的节点b，严格支配b的节点集合为Dom(b)-b,在该集合中距离b最近的节点直接支配b，记为IDom(b)
  • 支配边界
    • 对于流图中给定的节点b，若节点a满足:(1)b支配a一个前驱q($q\in preds(a),b\in Dom(q)$)(2)b不严格支配a，将具有这种性质的a的集合记为b的支配边界DF(b)
  1. phi节点是SSA的关键特征，请简述phi节点的概念，以及引入phi节点的理由。

phi节点:出现在程序基本块汇合节点的对某一变量x进行一次新的定义，作为程序的一条指令，完成了将来自不同边的x的值进行合并的工作

引入理由:为了满足SSA的静态单赋值形式，沿着流图的不同路径，x的当前值可能被分配了一个唯一的名字，在多条路径的汇合处，不同的静态单赋值形式名必须调整为一个名字，phi节点的作用就是在路径汇合点将同一变量的多个形式名合并为一个名字。

  1. 观察下面给出的cminus程序对应的 LLVM IR，与开启Mem2Reg生成的LLVM IR对比，每条load, store指令发生了变化吗？变化或者没变化的原因是什么？请分类解释。

    int globVar;
int func(int x){
    if(x > 0){
        x = 0;
    }
    return x;
}
int main(void){
    int arr[10];
    int b;
    globVar = 1;
    arr[5] = 999;
    b = 2333;
    func(b);
    func(globVar);
    return 0;
}

    before Mem2Reg：

    @globVar = global i32 zeroinitializer
declare void @neg_idx_except()
define i32 @func(i32 %arg0) {
label_entry:
  %op1 = alloca i32
  store i32 %arg0, i32* %op1
  %op2 = load i32, i32* %op1
  %op3 = icmp sgt i32 %op2, 0
  %op4 = zext i1 %op3 to i32
  %op5 = icmp ne i32 %op4, 0
  br i1 %op5, label %label6, label %label7
label6:                                                ; preds = %label_entry
  store i32 0, i32* %op1
  br label %label7
label7:                                                ; preds = %label_entry, %label6
  %op8 = load i32, i32* %op1
  ret i32 %op8
}
define i32 @main() {
label_entry:
  %op0 = alloca [10 x i32]
  %op1 = alloca i32
  store i32 1, i32* @globVar
  %op2 = icmp slt i32 5, 0
  br i1 %op2, label %label3, label %label4
label3:                                                ; preds = %label_entry
  call void @neg_idx_except()
  ret i32 0
label4:                                                ; preds = %label_entry
  %op5 = getelementptr [10 x i32], [10 x i32]* %op0, i32 0, i32 5
  store i32 999, i32* %op5
  store i32 2333, i32* %op1
  %op6 = load i32, i32* %op1
  %op7 = call i32 @func(i32 %op6)
  %op8 = load i32, i32* @globVar
  %op9 = call i32 @func(i32 %op8)
  ret i32 0
}

    After Mem2Reg：

    @globVar = global i32 zeroinitializer
declare void @neg_idx_except()
define i32 @func(i32 %arg0) {
label_entry:
  %op3 = icmp sgt i32 %arg0, 0
  %op4 = zext i1 %op3 to i32
  %op5 = icmp ne i32 %op4, 0
  br i1 %op5, label %label6, label %label7
label6:                                                ; preds = %label_entry
  br label %label7
label7:                                                ; preds = %label_entry, %label6
  %op9 = phi i32 [ %arg0, %label_entry ], [ 0, %label6 ]
  ret i32 %op9
}
define i32 @main() {
label_entry:
  %op0 = alloca [10 x i32]
  store i32 1, i32* @globVar
  %op2 = icmp slt i32 5, 0
  br i1 %op2, label %label3, label %label4
label3:                                                ; preds = %label_entry
  call void @neg_idx_except()
  ret i32 0
label4:                                                ; preds = %label_entry
  %op5 = getelementptr [10 x i32], [10 x i32]* %op0, i32 0, i32 5
  store i32 999, i32* %op5
  %op7 = call i32 @func(i32 2333)
  %op8 = load i32, i32* @globVar
  %op9 = call i32 @func(i32 %op8)
  ret i32 0
}

    删除的load/store:

    • 第6，7行：程序中对变量x进行了多次赋值，在未开启Mem2Reg的IR中是通过冗余的访存实现的，在load语句前的程序块中已存在x对应的值，在删去该条load后，变量x不会被其他语句load，store语句也被删除，load和store是不必要的。
    • 第13行：此处对x的值进行了存储，但是在该语句之后x并不是活跃变量，x的值不会被调用，因此该处的store是多余的。
    • 第32，33行：程序中对变量b进行了赋值，又将b作为函数参数进行函数调用，函数调用时所用的值实际上就是立即数，是在该程序块中已存在对应的值，因此可以不用load，也无需store指令，此处可以删除load和store指令。

    未变化的load/store:

    • 第23行：此处store对全局变量globVar进行赋值，因为是用立即数更新数据的值，由于Mem2Reg不会对该全局变量进行处理，需要在此处存储变量的值，不存在冗余。
    • 第31行：此处store对数组a中的元素利用立即数进行赋值，由于Mem2Reg不会对数组型元素进行处理，需要在此处存储变量的值，不存在冗余。
    • 第35行：此处load将全局变量globVar的值赋给临时变量，用于后续函数调用作为函数的参数，且此前globVar对应的值在该块中不存在，不存在冗余，不需要删除。

  2. 指出放置phi节点的代码，并解释是如何使用支配树的信息的。（需要给出代码中的成员变量或成员函数名称）

    • 放置伪代码的函数为src\optimization\Mem2Reg.cpp中的Mem2Reg::generate_phi函数。
    • step1：以基本块为单位，逐个遍历函数的所有指令，先找大活跃在多个基本块的变量及其对应的块，存储在live_var_2blocks中
    • step2：对于所有的变量，逐次遍历live_var_2blocks,在对应的dom集合bb_dominance_frontier_bb中依次寻找支配边界，如果在该基本块中未添加phi（bb_has_var_phi中不存在记录）,则插入phi：create_phi,在bb_dominance_frontier_bb中添加该语句，并在bb_has_var_phi中添加记录，防止重复添加。

  3. 算法是如何选择value(变量最新的值)来替换load指令的？（描述清楚对应变量与维护该变量的位置）

  • 选择value来替换load指令的位置在src\optimization\Mem2Reg.cpp中的Mem2Reg::rename()函数。
  • 对全局变量var_val_stack进行以下调用和维护：
    • 第一次遍历基本块的所有指令：phi指令：根据插入的phi指令，将对应变量的最新定值的位置设为该phi语句
    • 第二次遍历基本块中的所有指令：load指令：如果load的变量在var_val_stack中已经存在，则将该语句加入wait_delete，并维护对应的全局变量。store指令：将store存入内存的值作为最新定值
    • 借助get_succ_basic_blocks补充因phi改动的var_val_stack对应的值
    • 第三次遍历基本块中的所有指令：pop出var_val_stack中的最新定值
  • 在第二次遍历中，对于load指令，如果load的变量在var_val_stack中已经存在，则将该语句加入wait_delete，并利用replace_all_use_with函数维护其他指令。最后将wait_delete进行删除，也就是删除load指令。

代码阅读总结

此次实验的主要内容是熟悉代码优化的基础知识，了解SSA格式的IR的相关概念，并阅读了用来优化Lab3生成的IR指令的Mem2Reg相关代码,主要优化了冗余的load，store，alloca指令。主要收获是熟悉了支配节点，支配边界等概念，以及如何将这些概念用于代码优化，如何在程序中维护和利用这些属性来实现代码的优化。

PART2 实验要求

本次实验要完成的目标是在lab4.1 SSA IR的基础上，根据实验框架完成对SSA IR基于数据流分析完成的GVN优化。

实验难点

  • 根据LLVM IR的指令类型设计Expression子类的类型，并通过递归定义的方法定义值表达式，完成Value Expr
  • 处理phi指令，构思设计copy stmt部分和intersect,ValuePhiFunc函数

实验设计

实验思路

ValueNumber

GVN的核心就是建立全局值编号，本次实验中使用valueexpr作为值编号，每个等价类的valueexpr是唯一的。

为了解决可能存在的valueexpr相互依赖导致的无限递归的问题，将等价类运算符重载部分定义为：

bool CongruenceClass::operator==(const CongruenceClass &other) const {
    auto v1=value_expr_;
    auto v2=other.value_expr_;
    if(v2==nullptr&&v1==nullptr)
    return true;
    else if(v1==nullptr||v2==nullptr)
    return false;
   if(members_==other.members_)
    return true;
    return false;
}

即，算法收敛的判断依据是根据等价类成员不再改变，而不是根据valueexpr的值不再改变，这样就可以避开valueexpr无限递归的情况。

为了获取一个变量的valueexpr，将getVN定义如下：

其中如果ve的表达式为SingleExpression的类型时，是在valueexpr寻找参数对应的值表达式时建立的Expression。

shared_ptr<Expression> GVN::getVN(const partitions &pout, shared_ptr<Expression> ve) {  if(ve==nullptr)   return nullptr;   
    auto sve=std::dynamic_pointer_cast<SingleExpression>(ve);
    if(sve!=nullptr)
    { 
        auto num=dynamic_cast<Constant*>(sve->va());
        if(num!=nullptr)
        return ConstantExpression::create(num);
    for(auto &cc:pout)
    {
        if(cc->index_==0)
        return nullptr;
        for(auto &mem:cc->members_)
            if(mem==sve->va())
                return cc->value_expr_ ;
    }
    for(auto &cc:pout)
    {
        if(cc->index_==0)
        return nullptr;
        if(*ve==*cc->value_expr_)
        return cc->value_expr_;
    }
    return nullptr;
}

valueexpr

在Expression中新建若干子类，并完善对应的内部变量和创建，比较，打印等函数

  • Single Expression，存放非纯函数，load/store指令的value
  • Constant Expression，常数
  • Binary Expression，二元指令的操作数和类型
  • Phi Expression，phi指令的操作数
  • Call Expression，函数调用指令的函数类型和和函数参数，仅考虑纯函数
  • Gep Expression，存gep指令的操作数
  • Cmp Expression，类型为icmp的指令的指令类型（cmp_op)和操作数
  • Fcmp Expression，类型为fcmp的指令的指令类型（cmp_op)和操作数
  • Trans Expression，类型转换的指令类型和操作数

根据指令类型的不同分别处理：

  • phi指令：将在intersect中和transfer中处理，此处不会处理
  • void类型指令：此类指令不会被处理
  • call指令：若属于纯函数，找到参数的值表达式并建立CallExpression，否则新建一个SingleExpression类型的ve
  • gep指令：类似于纯函数，找到各个参数对应的值表达式并建立GepExpression
  • cmp,fcmp,binary,fp2si,si2fp,zext指令：找到参数对应的值表达式，进行常量传播，并建立对应的expression：CmpExpression,FcmpExpression,BinaryExpression,TransExpression
  • 其他语句，新建SingleExpression作为值表达式

处理Phi

由于Phi指令要作为Copy stmt加入每个基本块的前驱中，为了方便，可以在每个基本块指令遍历完后，遍历并处理该基本块后继中出现的phi指令，将后继块中的phi指令加入该基本块的等价类中。

Phi指令为四元指令，指令操作数依次为[op,label;op,label],此处可以通过get_name()获取label和bb的名字进行比对，如果相同，则借助transferFunction在该块等价类中添加该条语句。

auto succ=bb.get_succ_basic_blocks();
if(succ.size()>0)
    for(auto s:succ)
        for(auto &sinst:s->get_instructions())
            if(sinst.is_phi())
            {
                auto op0=sinst.get_operand(0);
                //op1/2/3=...
                if(op1->get_name()==bb.get_name())
                    pouts=GVN::transferFunction(&sinst,op0,pouts);
                if(op3->get_name()==bb.get_name())
                    pouts=GVN::transferFunction(&sinst,op2,pouts);
            }

为了处理存在了两个前驱块的基本块的pin，需要设计Join和intersect函数。

其中，Top块设计为只含有一个等价类，且等价类的索引为0的集合;Join函数遇到Top块时，规定Join(P, Top) = P = Join(Top, P)，否则逐个遍历等价类并调用intersect函数。

而对于Intersect函数，对于其他非phi语句，若members_存在交集，则必然有该两个等价类的值表达式一致，进行合并即可，否则合并得到的Ck为空；对于将出现在下一个基本块的（在上文中添加）的phi语句，就会存在members不为空且valueexpr不相等的情况，此时在Ck中根据Phi新建valueexpr和valuePhi语句，即可完成对Phi语句的处理。

for(auto i :Ci->members_)
    if(Cj->members_.find(i)!=Cj->members_.end())
    {
        Ck->members_.insert(i);
        if(Ck->leader_==nullptr)
            Ck->leader_=i;
    }
if(Ci->value_expr_==Cj->value_expr_)
{
    Ck->value_expr_=Ci->value_expr_;
    Ck->value_phi_=Ci->value_phi_;
    Ck->leader_=Ci->leader_;
}
else if(Ck->members_.size()!=0)
{
    Ck->value_phi_=PhiExpression::create(Ci->value_expr_,Cj->value_expr_);
    Ck->value_expr_=PhiExpression::create(Ci->value_expr_,Cj->value_expr_);
}

此外，在valuePhiFunc函数中需要识别phi函数之间存在的冗余，函数思路如下：

  • 只需要处理binary函数中的phi语句存在的冗余，并且该binary指令的lhs和rhs均为Phi类型，根据指令的值表达式即可进行上述类型判断，指令格式为bin(phi(vi1,vj1),phi(vi2,vj2))
  • 根据vi1,vi2,vj1,vj2(此时均为值表达式)创建新的二元表达式：c1=bin(vi1,vi2),c2=bin(vj1,vj2)
  • 在该基本块的前驱块中找到c1,c2对应的值表达式，借助getVN实现，如果未找到对应的值表达式，则递归查找该前驱块的valuePhiFunc
  • 如果找到对应的值表达式，借助两个值表达式新建phi指令并返回，否则返回nullptr

transferFunction

transferFunction函数的主要思路：

  • 在已有等价类中判断该指令是否已存在，如果存在则删除，如果该指令在对应的等价类中作为leader出现，将重新指定leader
  • 找到e对应的值表达式（getVN），如果找到，将x添加到对应的等价类集合中，（处理后继块phi语句的情况下可能会执行该步骤），返回pout
  • 如果e为常数类，因为上文中未找到对应的等价类，将新建等价类，value_expr_即为该常数对应的常数表达式，添加到pout中并返回
  • 调用valueexpr和valuePhifunc函数，找到对应的ve和vpf，并遍历已有等价类，如果已有等价类中存在该ve或vpf，即可在等价类中添加该成员，否则以该条指令为leader新建等价类，返回pout

detectEquivalences

在上述框架的基础上，完善detectequivalences函数：

  • 不断深度优先遍历基本块，直到每个基本块的等价类集合不再改变

  • 在label_entry位置处理函数参数，全局变量，对于这类参数直接新建等价类即可

  • 对于每个基本块，如果包含多个前驱，调用join获取pin，否则直接将前驱块的等价类作为pin

  • 遍历每条指令并调用transferFunction函数更改当前基本块等价类成员

  • 访问当前基本块的后继基本块，处理phi函数

    具体代码思路如下所示

for(auto &bb:func_->get_basic_blocks())
    if(&bb==entry) continue;
    else pout_[&bb]=clone(top);
do 
    next_value_number_=1;
    changed=false;
    for (auto &bb : func_->get_basic_blocks()) 
        partitions pouts={};
        if(&bb!=entry)
            if( bb.get_pre_basic_blocks().size()>1)
            //use join() to deal with
            else  for(auto s:predecessors) 
                pouts=clone(pout_[s]);
        else 
            //deal with func args and global var
        for(auto &inst:bb.get_instructions())
            if(!inst.is_void()&&!inst.is_phi())
                pouts=GVN::transferFunction(&inst,&inst,pouts);
        //deal with phi instr
        if(pouts!=pout_[&bb])
            changed=true;  
        pout_[&bb]=std::move(pouts);
while (changed);

常量传播

常量传播/常量折叠是为了在编译时进行计算程序中存在的常数，如二元计算，cmp，类型转换指令，以便提供更多可优化的表达式，提高运行效率。只需要在两个地方处理：valueexpr部分和valuephifunc部分。

valueexpr部分：对binary，cmp，trans语句均进行常量传播：

//二元
if(expr1->get_expr_type()==Expression::e_constant&&expr2->get_expr_type()==Expression:: e_constant)
{
    auto e1=std::dynamic_pointer_cast<ConstantExpression>(expr1);
    auto e2=std::dynamic_pointer_cast<ConstantExpression>(expr2);
    auto expr=folder_->compute(instr,e1->get_c(),e2->get_c());
    return ConstantExpression::create(expr);
}
//一元
 if(ve->get_expr_type()==Expression::e_constant)
 {
     auto e=std::dynamic_pointer_cast<ConstantExpression>(ve);
     auto expr=folder_->compute(instr,e->get_c());
     return ConstantExpression::create(expr);
 }

在valuePhiFunc中，只需处理对binary指令的常量传播，为了方便计算，在ConstFolder类中添加对compute的重载（参数为Instruction::opID,Constant,Constant\)

 auto e1=std::dynamic_pointer_cast<ConstantExpression>(vi1);
auto e2=std::dynamic_pointer_cast<ConstantExpression>(vi2);
auto e=folder_->compute(opid,e1->get_c(),e2->get_c());
c1=ConstantExpression::create(e);

举例

以bin.cminus为例，未开启代码优化时，生成的LLVM 代码如下：

define i32 @main() {
label_entry:
  %op0 = call i32 @input()
  %op1 = call i32 @input()
  %op2 = icmp sgt i32 %op0, %op1
  %op3 = zext i1 %op2 to i32
  %op4 = icmp ne i32 %op3, 0
  br i1 %op4, label %label5, label %label14
label5:                                                ; preds = %label_entry
  %op6 = add i32 33, 33
  %op7 = add i32 44, 44
  %op8 = add i32 %op6, %op7
  br label %label9
label9:                                                ; preds = %label5, %label14
  %op10 = phi i32 [ %op8, %label5 ], [ %op17, %label14 ]
  %op11 = phi i32 [ %op7, %label5 ], [ %op16, %label14 ]
  %op12 = phi i32 [ %op6, %label5 ], [ %op15, %label14 ]
  call void @output(i32 %op10)
  %op13 = add i32 %op12, %op11
  call void @output(i32 %op13)
  ret i32 0
label14:                                                ; preds = %label_entry
  %op15 = add i32 55, 55
  %op16 = add i32 66, 66
  %op17 = add i32 %op15, %op16
  br label %label9
}

开启代码优化后，最终生成的代码；


define i32 @main() {
label_entry:
  %op0 = call i32 @input()
  %op1 = call i32 @input()
  %op2 = icmp sgt i32 %op0, %op1
  %op3 = zext i1 %op2 to i32
  %op4 = icmp ne i32 %op3, 0
  br i1 %op4, label %label5, label %label14
label5:                                                ; preds = %label_entry
  %op6 = add i32 33, 33
  %op7 = add i32 44, 44
  %op8 = add i32 %op6, %op7
  br label %label9
label9:                                                ; preds = %label5, %label14
  %op10 = phi i32 [ %op8, %label5 ], [ %op17, %label14 ]
  call void @output(i32 %op10)
  call void @output(i32 %op10)
  ret i32 0
label14:                                                ; preds = %label_entry
  %op15 = add i32 55, 55
  %op16 = add i32 66, 66
  %op17 = add i32 %op15, %op16
  br label %label9
}

其中，op13和op10等价，经过死代码删除，将删除计算op13与op11，op12的语句。

上述例子各个基本块的等价类如下所示：

"label_entry": [["%op0", ], ["%op1", ], ["%op2", ], ["%op3", ], ["%op4", ], ],
"label5": [["%op0", ], ["%op1", ], ["%op2", ], ["%op3", ], ["%op4", ], ["%op6", "%op12", ], ["%op7", "%op11", ], ["%op8", "%op10", ],  ],
"label9": [["%op0", ], ["%op1", ], ["%op2", ], ["%op3", ], ["%op4", ], , ["%op13", "%op10", ], ["%op11", ], ["%op12", ], ],
"label14": [["%op0", ], ["%op1", ], ["%op2", ], ["%op3", ], ["%op4", ], ["%op15", "%op12", ], ["%op16", "%op11", ], ["%op17", "%op10", ],, ],}},]

思考题

1.请简要分析你的算法复杂度

仅对程序的主要部分以指令为单位进行讨论，实验完成部分的代码由run()函数逐个分析每个函数，并进入detectEquivalences()函数，在detectEquivalences()函数中，对函数中的基本块不断进行遍历分析得到每个基本块的pin和pout等价类，直到pout收敛，代表该函数分析完成，一般来说，遍历的次数为一个较小的数（通常小于10），视为常数；而对于每个基本块，要依次遍历基本块中的指令，在transferfunction中完成对每个指令的分析，同时在等价类中遍历寻找值表达式或对应的值。

综上分析，对于一个程序，本实验算法的时间复杂度大约为$T(n)=O(n^2)$,其中n为指令条数

2.std::shared_ptr如果存在环形引用，则无法正确释放内存，你的 Expression 类是否存在 circular reference?

不存在。Expression的各个子类是递归定义的，其子类以及的构成方法如下：

  • Single Expression，由一个Value *组成，用来处理特殊指令，如非纯函数，load,store指令等
  • Constant Expression，由一个Constant *组成
  • Binary Expression，由两个Expression和指令类型组成
  • Phi Expression，由两个Expression组成
  • Call Expression，由几个Expression和Function*组成
  • Gep Expression，由几个Expression组成
  • Cmp Expression，由两个Expression和指令类型组成
  • Fcmp Expression，由两个Expression和指令类型组成
  • Trans Expression，由一个Expression和指令类型组成

所有递归定义的Expression最终都会归结到Single Expression以及Constant Expression指令上，不会出现环形引用

3.尽管本次实验已经写了很多代码，但是在算法上和工程上仍然可以对 GVN 进行改进，请简述你的 GVN 实现可以改进的地方

  • 本次实验ValuePhiFunc对Phi指令冗余的检测仅仅检测了Binaray指令的冗余情况，实际上可以扩大检测范围，并且增加检测冗余的形式，如检测phi(0, c+d)与 phi(0,c)+phi(0,d)，实现思路类似。
  • 效率较低，对于规模较大的代码，GVN分析的效率会变慢，可以通过减少代码中不必要的遍历操作提高算法效率。

实验总结

  • 本次实验基于论文《Detection of Redundant Expressions: A Complete and Polynomial-Time Algorithm in SSA 》基于数据流分析完成了SSA IR的GVN优化，通过动手实现和设计具体的算法，让我对数据流分析有了更清楚地认识
  • 本次实验作为代码优化部分与前几次实验共同完成了Cminus的Compiler，对《编译原理与技术》一课的课程内容有了更清晰的整体认识。