作业 1：活跃变量分析和迭代求解器

南京大学《软件分析》实验一

2025-08-14
SAST Assignments

文章大纲

作业 1：活跃变量分析和迭代求解器
具体的任务链接在这
这里一开始看的蒙蒙的,看了半天Tai-e中我需要了解的类,但是又记不住,我对java项目又是在不熟悉(至今没写过任何java的实际程序(helloworld不算)),各种接口,子类什么的没有能快速的在脑海里构建一个框架出来,遂硬着头皮想着继续往下看,做着哪里不懂再对着查一下

实现活跃变量分析

这是第一个任务,所谓的活跃变量分析
也就是对每一个block里出现的变量,分析它们对这个block有定义的地方,从而可以找出那些后面不会用的变量优化掉,说起来有点拗口,但其实第三节课里有详细的例子帮助理解

需要补全的api

  • SetFact newBoundaryFact(CFG)
  • SetFact newInitialFact()
  • void meetInto(SetFact,SetFact)
  • boolean transferNode(Stmt,SetFact,SetFact)

活跃变量分析的算法伪代码描述在课程笔记中记录了

我们在编写实现的时候需要关注的是:

  • 方向：后向（已经在 isForward() 返回 false）

  • 领域（lattice domain）：变量集合 SetFact<Var>

  • 边界条件（boundary fact）：出口处 OUT = 空集

  • 初始条件（initial fact）：一般也设为空集（供迭代起点）

  • meet 操作：并集

  • transfer 函数（单语句级别）：
    IN(s) = USE(s) ∪ (OUT(s) − DEF(s))
    OUT(s) = 对所有后继的 IN 的并集（由求解器驱动）

可以看到,第一第二个任务设置边界状态和初始状态非常简单只需返回一个空集即可,查阅pascal.taie.analysis.dataflow.fact中的SetFact类可得各种用法

查得

1
2
3
public SetFact() {  
    this(Collections.emptySet());  
}

那么置空只需return new SetFact<>()即可

1
2
3
4
5
6
7
8
9
@Override  
public SetFact<Var> newBoundaryFact(CFG<Stmt> cfg) {    
    return new SetFact<>();  
}  
  
@Override  
public SetFact<Var> newInitialFact() {   
    return new SetFact<>();  
}

而meet操作和transfer理解起来不难

  • meet：并集

  • 含义：如果某变量在任意一条后继路径上是“可能活跃”的，就认为在汇合点也“可能活跃”。

  • 用途：计算一个语句的 OUT 时，要把所有后继的 IN 通过并集合并。

  • transfer：IN = USE ∪ (OUT − DEF)

  • 含义：语句使用到的变量（USE）在执行该语句前必须活跃；该语句定义的变量（DEF）会“杀死”之前的需求（从 OUT 去掉），除非它也在 USE 中被用到

  • 例子：x = y + z; 若 OUT = S，则 IN = (S − {x}) ∪ {y, z}

meet

那么查阅可以发现并集操作也就是union直接调用即可,也就是SetFact里的

1
2
3
4
5
/**  
 * Unions other fact into this fact. * * @return true if this fact changed as a result of the call, otherwise false.  
 */public boolean union(SetFact<E> other) {  
    return set.addAll(other.set);  
}

补充到meetInto方法里就是

1
2
3
4
@Override  
public void meetInto(SetFact<Var> fact, SetFact<Var> target) {  
    target.union(fact);  
}

将第一个操作数fact的变量加到第二个操作数target的变量里

transfer

transfer api的实现关键在于如何取出def和use,这里要回去看看tai-e的pascal.taie.ir.exp.Exp
和pascal.taie.ir.stmt.Stmt

可以知道只需使用stmt的getDef()和getUses()即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
@Override  
public boolean transferNode(Stmt stmt, SetFact<Var> in, SetFact<Var> out) {  
    // 初始时创建一个临时变量inTmp,类型与in,out一直,合并out后,后续就对这个临时变量进行操作即可(主播一开始直接对out进行操作了)
    SetFact<Var> inTmp = new SetFact<>()();  
    inTmp.union(out);  
    stmt.getDef().ifPresent(lv -> {  
        if (lv instanceof Var) {  
            inTmp.remove((Var)lv);  
        }  
    });  
  
    for (RValue rv : stmt.getUses()) {  
        if (rv instanceof Var) {  
            inTmp.add((Var)rv);  
        }  
    };  
    if (in.equals(inTmp)) {  
        return false;  
    }else{
	    in.set(inTmp);  
        return true;  
    }  
}

实现起来也并不难,由于是由out求in,所以只需要将out赋给新的in(新的In初始化,然后并上out),然后根据transfer的算法,将stmt的def变量取出,remove掉,然后将stmt的use的变量加进去,就得到了新的in,如果与旧的in一致,说明这里达到不动点了;如果不一致就将in设为新的in

迭代求解器

第二个任务是实现 Solver 类的两个方法：

  • Solver.initializeBackward(CFG, DataflowResult)：初始化每个结点的 IN/OUT，设置边界条件

  • IterativeSolver.doSolveBackward(CFG, DataflowResult)：经典迭代：用后继的 IN 求当前结点的 OUT（做 meet），再用 transfer 从 OUT 推 IN，直到稳定

截屏2025-08-06 22.42.20.png
第一个补全的地方实现的是前三行,也就是初始化普通节点和边界节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
protected void initializeBackward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {  
    // getOutFact,setInFact,  
    for (Node node : cfg.getNodes()) {  
  
        if (cfg.isExit(node)) {  
  
            result.setInFact(node, analysis.newInitialFact());  
            result.setOutFact(node, analysis.newBoundaryFact(cfg));  
        } else {  
            result.setInFact(node, analysis.newInitialFact());  
            result.setOutFact(node, analysis.newInitialFact());  
        }  
    }  
}

主播以前从来没做过算法题,这里这么简单的一个边界设空,其余初始化(其实也是空)的逻辑,因为各种参数的类型和api没有一下子理清楚(英文理解能力有点差,一部份注释都没读明白),硬控了好久.实际后来看也是太啰嗦了我写的,实际可以直接全初始化,然后单拿出exit节点setOutFact为空即可

后面做doSolveBackward就没花那么久了,因为对各种api熟了,其实只要再跟着上课演示的那个流程例子,每一轮是怎么做的,人是怎么想的会了之后,你需要的只是把这个方法抽象成代码语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
@Override  
protected void doSolveBackward(CFG<Node> cfg, DataflowResult<Node, Fact> result) {    
    boolean changed = true;  
    while (changed) {  
        changed = false;  
        for (Node node : cfg.getNodes()) {  
            Fact newOut = analysis.newInitialFact();  
  
            for (Node succ : cfg.getSuccsOf(node)) {  
                Fact succIn = result.getInFact(succ);   
                analysis.meetInto(succIn, newOut);  
            }  
            Fact oldOut = result.getOutFact(node);  
            if (!newOut.equals(oldOut)) {  
                result.setOutFact(node, newOut);  
                changed = true;  
            }  
            Fact inFact = result.getInFact(node);  
            Fact outFact = result.getOutFact(node);  
            boolean inChanged = analysis.transferNode(node, inFact, outFact);  
            changed |= inChanged;  
        }  
  
        }  
  
    }  
}

实际在做的就是对每一轮：

  • 对每个结点 node，先把它的 OUT(node) 用所有后继结点的 IN(succ) 做 meet（本题是并集），得到新的 newOut。

  • 如果 newOut 和旧的 OUT(node) 不同，就更新之，并把本轮标记为“发生变化”。

  • 然后用 transfer（本题公式：IN = USE ∪ (OUT − DEF)）把 OUT(node) 推成 IN(node)；如果 IN(node) 内容被改，也把本轮标记为“发生变化”