软件分析课程实验A1-活跃变量分析和迭代求解器

标签：分析活跃 node 变量迭代 A1 基本块 SetFact def

课程主页：https://tai-e.pascal-lab.net/lectures.html

数据流分析

数据流分析指的是一种用来获取有关数据如何沿着程序执行路径流动的相关技术，许多编译优化技术都依赖于数据流分析。

数据流分析有很多经典的应用，比如

到达定值分析
活跃变量分析
可用表达式分析

活跃变量分析原理

活跃变量分析（Live Variable Analysis）是数据流分析的一个经典应用

活跃变量

对于变量\(x\)和程序点\(p\)，如果在程序流图中沿着从\(p\)开始的某条路径会引用变量\(x\)在\(p\)点的值，则称变量\(x\)在点\(p\)是活跃（live）的，否则称变量\(x\)在点\(p\)是不活跃（dead）的

主要用途

删除无用赋值：如果在某点赋值，但是后面又不会用到的话，可以将该点的赋值删除
寄存器分配：如果寄存器都被占用，则当再次申请寄存器的时候，需要替换掉一些占用寄存器的变量。通过活跃变量分析，可以将不活跃变量所占用的寄存器空出来

符号定义

\(def_B, use_B, IN[B], OUT[B]\)

\(def_B\) ： 赋值先于任何使用的变量的集合
\(use_B\)： 使用先于任何赋值的变量的集合
\(IN[B], OUT[B]\)：分别表示在紧靠一个基本块\(B\)之前和之后的点上的活跃变量的集合

比如对于下面\(B_2\) 的基本块中，对于 \(i = i + 1;\) 这条语句可以拆分成\(t = i + 1; i = t;\)两条指令，所以对于变量\(i\)而言，其使用先于任何赋值，所以属于\(use_{B_2}\) 中的变量，不属于\(def_{B_2}\)中的变量。

另一个例子是，对于一个基本块中如果有两条指令：\(v=2; k = v;\) 则变量\(v\)的赋值先于其任何的使用，所以变量\(v\)属于\(def_B\)，而不属于 \(use_B\)。

根据这些定义，\(use_B\)中的任何变量都必然被认为在基本块\(B\)的入口处是活跃的，而\(def_B\)中所有的变量在B的开头一定是不活跃的。

实际上，\(def_b\)中的成员“杀死了”某个变量可能从\(B\)开始成为活跃变量的任何机会

《编译原理第二版》P390

算法原理

\(IN[EXIT] = \emptyset\) ：边界条件，表示程序出口处没有变量是活跃的
然后对所有除了\(EXIT\) 之外的基本块 \(B\) 来说，首先初始化所有\(B\)为空集 \(IN[B] = \emptyset\)，初始化之后对所有的\(B\)执行如下的转移函数
- \(OUT[B] = \cup _{S是B的一个后继} IN[S]\) ：一个变量在离开一个基本块的时候活跃，当且仅当它进入该基本块的某个后继时活跃
- \(IN[B] = use_B \cup(OUT[B] - def_B)\) ：一个变量进入基本块的时候活跃必须保证，要么在基本块中被赋值之前就使用了，要么在离开基本块的时候活跃并且没有对它重新赋值

A1实验分析

实验目标

本次作业需要实现一个活跃变量分析算法，抽象的算法如下图所示，具体而言，需要求出每个基本块的InFact值，里面包含该点所有的活跃变量。本次作业需要填空来完成下图的算法实现

需要注意：

本次作业的每个基本块仅含有一条指令
实验的结果最后存储在参数 DataflowResult<Node, Fact> result中
用到了Java的一些特性
- Optional特性：isPresent() 和 get()的使用
- 泛型特性

step1: 初始化基本块的 InFact和OutFact

pascal/taie/analysis/dataflow/analysis/LiveVariableAnalysis.java

 @Override
    public SetFact<Var> newBoundaryFact(CFG<Stmt> cfg) {
        // TODO - finish me
        // 返回边界节点的向量，backwards的边界节点是 exit节点
        return new SetFact<Var>();
    }

    @Override
    public SetFact<Var> newInitialFact() {  // 返回值就是 SetFact<Var>
        // TODO - finish me
        // 除了exit节点的其他节点初始化为空
        return new SetFact<Var>();
    }

    @Override
    public void meetInto(SetFact<Var> fact, SetFact<Var> target) { // 注意这里提示了，使用的是SetFact<Var>， 所以前面用的也都是Var
        // TODO - finish me
        // 并起来
        target.union(fact);
    }

pascal/taie/analysis/dataflow/solver/Solver.java

    protected void initializeBackward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
        // TODO - finish me
        // step1 将 exit节点的InFact置为空集
        result.setInFact(cfg.getExit(), analysis.newBoundaryFact(cfg));
        // step2 将 除了exit节点之外的其他节点的InFact和OutFact置为空集
        for (Node node : cfg.getNodes()) {
            if (cfg.isExit(node)) continue;
            result.setInFact(node, analysis.newInitialFact());
            // 将OutFact也置为空集
            result.setOutFact(node, analysis.newInitialFact());
        }
    }

step2: 实现迭代求解器

pascal/taie/analysis/dataflow/solver/IterativeSolver.java

    @Override
    protected void doSolveBackward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {
        // TODO - finish me
        boolean changed = true;

        while (changed) {
            changed = false;

            for (Node node : cfg.getNodes()) {
                // 除了exit的Node，因为exitNode没有outFact
                if (cfg.isExit(node)) continue;
                // 求出OutFact
                for (Node succNode : cfg.getSuccsOf(node)) {
                    analysis.meetInto(result.getInFact(succNode), result.getOutFact(node));
                }
                // 使用outfact做转换，得到infact
                // 并且查看是否这个block的状态是否改变了
                if (analysis.transferNode(node, result.getInFact(node), result.getOutFact(node))) changed = true;
            }
        }
    }

step3: 实现转换函数

pascal/taie/analysis/dataflow/analysis/LiveVariableAnalysis.java

    @Override
    public boolean transferNode(Stmt stmt, SetFact<Var> in, SetFact<Var> out) {
        // TODO - finish me
        // 复制outFact，求出新的inFact
        SetFact<Var> newInFact = new SetFact<>();
        newInFact.union(out);
        // 求出新的inFact
        // outFact - def
        if (stmt.getDef().isPresent()) { // 先用isPresent再用get是optional的典型用法
            LValue def = stmt.getDef().get();
            if (def instanceof Var) {
                newInFact.remove((Var) def);
            }
        }
        // (outFact - def ) + use
        for (RValue use : stmt.getUses()) {
            if (use instanceof  Var) {
                newInFact.add((Var) use);
            }
        }
        // 判断inFact是否改变，并返回Boolean表示
        if (!newInFact.equals(in)) {
            in.set(newInFact);
            return true;
        }
        return false;
    }

参考资料

【编译原理，第二版】（龙书）

【超棒的博客，这个人是搞编译器的，他的博客可以看看】https://leiblog.wang/编译高级教程｜学习笔记/#

【这个人的博客写了很多关于编译器优化的总结】https://www.jianshu.com/p/ebc1c72b881c

【活跃变量分析 & 常用表达式分析】https://liuyehcf.github.io/2017/11/24/编译原理-代码优化3/

【编译原理-哈工大，上面博客的课件都来自于此】https://www.bilibili.com/video/BV1zW411t7YE/?vd_source=ee07a5a150ae217eba28dd2c4bd5549b

【数据流分析应用总结】https://blog.csdn.net/weixin_43258309/article/details/104512206

标签：分析,活跃,node,变量,迭代,A1,基本块,SetFact,def
From： https://www.cnblogs.com/VanHa0101/p/16916233.html