官网：作业 4：类层次结构分析与过程间常量传播 | Tai-e

参考：https://www.cnblogs.com/gonghr/p/17984124

-----------------------------------------------------------------------

1 作业导览

• 为 Java 实现一个类层次结构分析（Class Hierarchy Analysis，CHA）。
• 实现过程间常量传播。
• 实现过程间数据流传播的 worklist 求解器。

在本次实验作业中，你将在 Tai-e 的基础之上为 Java 实现一个基于类层次结构（下面简称为 CHA）的调用图（call graph）构造器。接着为了展现它的用处，你需要依靠你实现的调用图实现一个过程间常量传播分析。此外，为了使得你的过程间常量传播能够正常运行，你还需要实现一个 worklist 求解器来支持过程间数据流分析（虽然在软件分析课程中，我们并没有教过你实现过程间分析的具体方法，但是不必担心，通过本次作业，你会掌握相关的知识和实现方法）。

本次作业的分析范围和第二次作业是一致的，也就是说你仍然只需要考虑针对 int 类型变量的常量传播，只不过在本次作业中，你需要更准确地处理方法调用。如果你的实现是正确的，那么在实验的最后你就可以发现：与保守处理方法调用的过程内常量传播相比，过程间常量传播可以达到更好的精度。

idea打开实验作业仓库的 A4/tai-e/，并按【静态分析】软件分析课程实验-前置准备-CSDN博客进行配置。

2 实现类层次结构分析（CHA）

在本次作业中，你需要处理 Java 语言的四种方法调用：invokestatic、invokespecial、invokeinterface 和 invokevirtual（详情见【静态分析】静态分析笔记05 - 过程间分析-CSDN博客）。当然，Java 中的一些新特性会让方法调用的情形更复杂：比如 Java 8 开始允许接口定义非抽象方法（default methods

）；还有从 Java 11 开始，invokeinterface 和 invoke-virtual 可以调用 private 方法了。这都会使我们构建调用图的过程变得更复杂。而简单起见，你并不需要在本次作业中处理这些改动。

2.1 Tai-e 中你需要了解的类

本次作业中，有一些类包含了很多 API。为了减轻你的压力，我们将会介绍一些你可能会用到的相关的类和 API。我们将以自顶到下的方式来介绍这些类，也就是说，我们会首先介绍构建调用图的关键类（DefaultCallGraph），紧接着介绍与它相关的其他类。

• pascal.taie.analysis.graph.callgraph.DefaultCallGraph

  该类代表了程序的调用图。它提供了多样的 API（继承自类 AbstractCallGraph）来获取到调用图的信息。另外，它还提供了一些修改调用图的 API，你可以借此来建立调用图。

  • Stream<Invoke> callSitesIn(JMethod)：返回给定方法 JMethod 中的所有 call sites。
  • boolean contains(JMethod): 返回当前调用图是否含有给定的方法，即给定方法 JMethod 在当前调用图中是否可达。
  • boolean addReachableMethod(JMethod): 向当前调用图中添加方法 JMethod 并将方法标记成可达的。
  • boolean addEdge(Edge<Invoke,JMethod>): 向当前调用图中添加一条调用边。

• pascal.taie.analysis.graph.callgraph.CallKind

  该枚举类型表示调用图中边的种类，包括 INTERFACE、VIRTUAL、SPECIAL 和 STATIC，它对应第 7 讲中介绍过的 Java 的四种调用类型（call kind）。

• pascal.taie.analysis.graph.callgraph.Edge<Invoke,JMethod>

  该类表示调用图中的边。每一条边从调用点（call site，Tai-e 中为 Invoke 类型）出发，指向被调用方法（callee method，类型为 JMethod）。在创建一条边的时候，你需要向构造方法提供调用类型、调用点和被调用方法的信息。

• pascal.taie.ir.stmt.Invoke (subclass of Stmt)

  该类表示程序中的方法调用（举个例子：x = o.m(a1,a2,…)）以及调用图中的调用点。它提供了一些 API 来获取调用点的各种信息。明确一点：你需要使用 getMethodRef() 来获取目标方法的签名信息。

• pascal.taie.ir.proginfo.MethodRef

  Tai-e 中的目标方法引用，如调用点的目标方法。它包含了调用点所调用的目标方法的签名信息。

  • JClass getDeclaringClass()：返回该方法签名的声明类，即声明该方法的类。（也就是class type）；
  • Subsignature getSubsignature()：返回被调用方法的子签名（subsignature）。稍后我们回来介绍子签名类——Subsignature。

  对 MethodRef，在本次作业中你只需要使用上面提到的两个 API。

• pascal.taie.language.classes.JMethod

  该类表示 Tai-e 中的 Java 方法。每个 JMethod 的实例关联着一个方法并包含该方法的各种信息。

  • boolean isAbstract(): 如果该 JMethod 是一个没有方法体的抽象方法，则返回 true，否则返回 false；

• pascal.taie.language.classes.JClass

  该类表示 Tai-e 中的 Java 类。每个 JClass 的实例关联着一个类并包含该类的各种信息。

  • JClass getSuperClass(): 返回该类的父类。如果这个类在类层次结构的顶端（没有父类），比如 java.lang.Object，则返回 null。
  • JMethod getDeclaredMethod(Subsignature): 根据子签名返回该类中声明的对应方法。如果该类中没有该子签名对应的方法，则返回 null。
  • boolean isInterface(): 返回该类是否是一个接口。

• pascal.taie.language.classes.Subsignature

  该类表示 Tai-e 中的子签名。一个方法的子签名只包含它的方法名和方法签名的描述符。举个例子，下面方法 foo 的子签名是：“T foo(P,Q,R)” ，而它的完整签名是：“<C: T foo(P,Q,R)>”。

  class C {
      T foo(P p, Q q, R r) { … }
  }
  

pascal.taie.language.classes.ClassHierarchy

该类提供了类层次结构的相关信息。

• Collection<JClass> getDirectSubclassesOf(JClass): 对于给定类，返回直接继承该类的子类。
• Collection<JClass> getDirectSubinterfacesOf(JClass): 对于一个给定接口，返回直接继承该接口的子接口。
• Collection<JClass> getDirectImplementorsOf(JClass): 对于一个给定接口，返回直接实现了该接口的类。

举个例子，在下面的 class hierarchy 中，I, II, III 是接口，其他均为类：

• 那么

  • getDirectSubclassesOf(A) = [B]
  • getDirectSubinterfacesOf(I) = [II, III]
  • getDirectImplementorsOf(II) = [E]

• pascal.taie.analysis.graph.callgraph.CHABuilder

  这个类通过 CHA 来建立调用图。目前该类是不完整的，你将会在第 2.2 节的讲解和帮助下完成它。

2.2 你的任务 [重点!]

你的第一个任务是完成 CHABuilder 类。你需要完成以下三个 API：

• JMethod dispatch(JClass,Subsignature)

  该方法实现了 Dispatch方法，根据方法调用者的类和方法签名寻找目标方法。

• 

• 特别地，如果找不到满足要求的方法，返回 null。

• 比较显然，是个递归算法。

  递归的终止条件有两个，一个是如果一直找不到相应方法，不断递归到父类，最后递归到 Object 在向上递归就是 null ，Object 没有父类，此时返回空，说明找不到相应方法；另一个是如果当前类的方法中有能匹配方法签名的方法，并且该方法不是抽象方法，说明找到相应方法，返回该方法。

  其他情况向当前类的父类递归。

• Set<JMethod> resolve(Invoke)

  该方法实现了Resolve 方法, 通过类的继承关系确定一个调用点的所有可能的目标方法。

• 提示：

  你可以使用 CallGraphs.getCallKind(Invoke) 来获得调用点的调用类型。

• CallGraph<Invoke, JMethod> buildCallGraph(JMethod)

  该方法实现了 BuildCallGraph 算法, 代码中 DefaultCallGraph 既是个调用图 CG ，也能记录哪些方法访问过，即RM。

• 

我们提供了上述 3 个 API 的代码框架。你的任务是填写所有标有注释 “TODO – finish me” 的部分。

/*
 * Tai-e: A Static Analysis Framework for Java
 *
 * Copyright (C) 2022 Tian Tan <tiantan@nju.edu.cn>
 * Copyright (C) 2022 Yue Li <yueli@nju.edu.cn>
 *
 * This file is part of Tai-e.
 *
 * Tai-e is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation, either version 3
 * of the License, or (at your option) any later version.
 *
 * Tai-e is distributed in the hope that it will be useful,but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
 * Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with Tai-e. If not, see <https://www.gnu.org/licenses/>.
 */

package pascal.taie.analysis.graph.callgraph;

import pascal.taie.World;
import pascal.taie.ir.proginfo.MethodRef;
import pascal.taie.ir.stmt.Invoke;
import pascal.taie.language.classes.ClassHierarchy;
import pascal.taie.language.classes.JClass;
import pascal.taie.language.classes.JMethod;
import pascal.taie.language.classes.Subsignature;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Set;

import java.util.*;
import java.util.stream.Stream;


/**
 * Implementation of the CHA algorithm.
 */
class CHABuilder implements CGBuilder<Invoke, JMethod> {

    private ClassHierarchy hierarchy;

    @Override
    public CallGraph<Invoke, JMethod> build() {
        hierarchy = World.get().getClassHierarchy();
        return buildCallGraph(World.get().getMainMethod());
    }

    private CallGraph<Invoke, JMethod> buildCallGraph(JMethod entry) {
        DefaultCallGraph callGraph = new DefaultCallGraph();
        callGraph.addEntryMethod(entry);
        // TODO - finish me
        ArrayDeque<JMethod> worklist = new ArrayDeque<>();
        worklist.addLast(entry);
        while (!worklist.isEmpty()) {
            JMethod m = worklist.pollFirst();
            if (!callGraph.contains(m)) {
                callGraph.addReachableMethod(m);
                Stream<Invoke> invokeStream = callGraph.callSitesIn(m);
                invokeStream.forEach(cs -> {
                    for (JMethod targetMethod : resolve(cs)) {
                        if (targetMethod != null) {
                            callGraph.addEdge(new Edge<>(CallGraphs.getCallKind(cs), cs, targetMethod));
                            worklist.addLast(targetMethod);
                        }
                    }
                });
            }
        }
        return callGraph;
    }

    /**
     * Resolves call targets (callees) of a call site via CHA.
     */
    private Set<JMethod> resolve(Invoke callSite) {
        // TODO - finish me
        Set<JMethod> T = new HashSet<JMethod>();  // 调用点的所有可能的目标方法集合
        MethodRef m = callSite.getMethodRef();
        Subsignature subsignature = m.getSubsignature();  // 函数签名
        JClass declaringClass = m.getDeclaringClass();  // 调用点声明类型
        // CallKind - INTERFACE、VIRTUAL、SPECIAL、STATIC
        CallKind callKind = CallGraphs.getCallKind(callSite);  // 函数调用类型

        switch (callKind) {
            case STATIC -> {  // T = {该调用点声明类型的方法}
                T.add(declaringClass.getDeclaredMethod(subsignature));
                break;
            }
            case SPECIAL -> {  // dispatch递归查找父类
                T.add(dispatch(declaringClass, subsignature));
                break;
            }
            case VIRTUAL, INTERFACE -> {  // 根据声明类型，对该类和该类的所有子类dispatch
                ArrayDeque<JClass> subclasses = new ArrayDeque<>();
                HashSet<JClass> set = new HashSet<>();
                subclasses.addLast(declaringClass);
                set.add(declaringClass);
                while (!subclasses.isEmpty()) {
                    JClass subclass = subclasses.pollFirst();
                    T.add(dispatch(subclass, subsignature));
                    for (JClass jClass : (hierarchy.getDirectSubclassesOf(subclass))) {
                        if (!set.contains(jClass)) {
                            set.add(jClass);
                            subclasses.addLast(jClass);
                        }
                    }
                    for (JClass jClass : (hierarchy.getDirectSubinterfacesOf(subclass))) {
                        if (!set.contains(jClass)) {
                            set.add(jClass);
                            subclasses.addLast(jClass);
                        }
                    }
                    for (JClass jClass : (hierarchy.getDirectImplementorsOf(subclass))) {
                        if (!set.contains(jClass)) {
                            set.add(jClass);
                            subclasses.addLast(jClass);
                        }
                    }
                }
                break;
            }
        }
        return T;
    }

    /**
     * Looks up the target method based on given class and method subsignature.
     *
     * @return the dispatched target method, or null if no satisfying method
     * can be found.
     */
    private JMethod dispatch(JClass jclass, Subsignature subsignature) {
        // TODO - finish me
        if (jclass == null) {
            return null;
        }
        if (jclass.getDeclaredMethod(subsignature) != null && !jclass.getDeclaredMethod(subsignature).isAbstract()) {
            return jclass.getDeclaredMethod(subsignature);
        }
        return dispatch(jclass.getSuperClass(), subsignature);
    }
}

3 实现过程间常量传播

3.1 Edge Transfer

过程间常量传播和过程内常量传播很像。它们的主要区别是：过程间常量传播使用了 edge transfer，因此能够更准确地处理方法调用和返回所产生的过程间数据流。

举一个前向分析的例子，在传统的过程内数据流分析中，如果我们想计算一个节点的IN fact，我们可以直接meet该节点的全部前驱的OUT fact：

然而，在过程间数据流分析中，为了计算一个节点的 IN fact，我们需要先对该节点的前驱的 OUT fact 应用 edge transfer，然后把得到结果 meet 进该节点的 IN fact。

举个例子，这是第 7 讲中出现过的一个 ICFG：

为了计算第 4 条语句的 IN fact，也就是方法 addOne() 的 entry 节点的 IN fact，我们需要对 2→4 这条边应用 edge transfer，这样使得第 2 条语句的 OUT fact（a=6）转换为 x=6，并最终 meet 结果 x=6 到第四条语句的 IN fact中。

我们定义了 transferEdge(edge, fact) 函数来实现 edge transfer。它以 ICFG 中的一条边（对应参数 edge）和边的源节点的 OUT fact（对应参数fact）为输入，并输出经transfer计算之后的结果fact。据此，我们把计算IN fact的转换函数调整为：

我们曾在第 7 讲中提到过，在过程间常量传播中，transfer edge 需要处理的边被分为以下四种：

• Normal edge: 这种边一般是与过程间调用无关的边，edge transfer 函数不需要对此进行特殊的处理。这种边上的 fact 经 transfer edge 之后不会有任何改变。换句话说，此时 edge transfer 是一个恒等函数，即 transferEdge(edge, fact) = fact。
• Call-to-return edge: 对于方法调用 x = m(…)，edge transfer 函数会把等号左侧的变量（在这个例子里也就是 x）和它的值从 fact 中 kill 掉。而对于等号左侧没有变量的调用，比如 m(…)，edge transfer 函数的处理方式与对待 normal edge 的一致：不修改 fact，edge transfer 是一个恒等函数。
• Call edge: 对于这种边，edge transfer 函数会将实参（argument）在调用点中的值传递给被调用函数的形参（parameter）。具体来说，edge transfer 首先从调用点的 OUT fact 中获取实参的值，然后返回一个新的 fact，这个 fact 把形参映射到它对应的实参的值。举个例子，在图 1 里，transferEdge(2→4, {a=6}) = {x=6}。此时，edge transfer 函数的返回值应该仅包含被调用函数的形参的值（比如图 1 里，addOne() 的 x）。
• Return edge: edge transfer 函数将被调用方法的返回值传递给调用点等号左侧的变量。具体来说，它从被调用方法的 exit 节点的 OUT fact 中获取返回值（可能有多个，你需要思考一下该怎么处理），然后返回一个将调用点等号左侧的变量映射到返回值的 fact。举个例子，在图1中，transferEdge(6→3, {x=6,y=7}) = {b=7}。此时，edge transfer 函数返回的结果应该仅包含调用点等号左侧变量的值（例如图1在第三条语句处的b）。如果该调用点等号左侧没有变量，那么 edge transfer 函数仅会返回一个空 fact。

在接下来的章节，我们将会向你介绍更多关于如何在 Tai-e 中实现上述这些 edge transfer 函数的信息。

3.2 Tai-e 中你需要了解的类

• pascal.taie.analysis.graph.icfg.ICFGEdge

  该类是一个抽象类，它表示了 ICFG 中的边。而它有四个子类，分别关联着上一节中提到的四种 ICFG 边：Normal Edge、CallToReturnEdge、CallEdge、ReturnEdge：

  • pascal.taie.analysis.graph.icfg.NormalEdge
  • pascal.taie.analysis.graph.icfg.CallToReturnEdge
  • pascal.taie.analysis.graph.icfg.CallEdge
  • pascal.taie.analysis.graph.icfg.ReturnEdge

  这些类都非常简单易懂并且有详尽的注释，请好好阅读源码来认识它们吧。

• pascal.taie.analysis.dataflow.inter.InterDataflowAnalysis

  这是一个过程间数据流分析的接口。它总共有 6 个API。它的前 5 个 API 都与过程内数据流分析 DataflowAnalysis 的相同，所以如果需要，你可以翻看此前的作业手册再次认识它们。而它的最后一个 API 就是 transferEdge()，也就是我们在第 3.1 节中介绍的 edge transfer 函数。这 6 个 API将被过程间数据流分析的求解器调用，而你的任务就是利用这些 API 实现这个求解器。

• pascal.taie.analysis.dataflow.inter.AbstractInterDataflowAnalysis

  该抽象类实现了 InterDataflowAnalysis，并为 InterDataflowAnalysis 的实现提供了一些基本的功能。说得明白一点，它把 ICFG 中不同的点和边分派给对应 transfer 方法。这样一来，我们的分析的实现就可以分别处理各类的点和边。

• pascal.taie.analysis.dataflow.inter.InterConstantPropagation

  该类继承自 AbstractInterDataflowAnalysis，并且定义了过程间常量传播。但是它还是不完整的。你需要根据第 3.3 节的描述完成它。

• pascal.taie.ir.exp.InvokeExp

  该类表示程序中的方法调用表达式。它包含了被调用的方法引用和传入的各个参数。具体的细节和如何使用，需要你阅读源码和相关注释来了解。

3.3 你的任务 [重点!]

你的第二个任务是完成 InterConstantPropagation 的这些 API：

• boolean transferCallNode(Stmt,CPFact,CPFact)
• boolean transferNonCallNode(Stmt,CPFact,CPFact)
• CPFact transferNormalEdge(NormalEdge,CPFact)
• CPFact transferCallToReturnEdge(CallToReturnEdge,CPFact)
• CPFact transferCallEdge(LocalEdge,CPFact)
• CPFact transferReturnEdge(LocalEdge,CPFact)

InterConstantPropagation 类包含了一个 ConstantPropagation 类的字段：cp，这使得你可以利用过程内常量传播实现的逻辑。但是ConstantPropagation.java 目前还和以前一样没有实现完全，所以，为了防止你的过程间常量分析罢工，你首先需要补全 ConstantPropagation.java。你可以从你此前已经完成的作业中复制代码，并粘贴到本次作业中。

提示：

• 你在实现 transfer*Edge() 方法的时候，不应该修改第二个参数，也就是该边的源节点的 OUT fact。
• 我们在第二次作业中介绍过，你可以从 IR 类中获取方法的参数，且可以使用 API JMethod.getIR() 来获取一个方法的 IR。

/*
 * Tai-e: A Static Analysis Framework for Java
 *
 * Copyright (C) 2022 Tian Tan <tiantan@nju.edu.cn>
 * Copyright (C) 2022 Yue Li <yueli@nju.edu.cn>
 *
 * This file is part of Tai-e.
 *
 * Tai-e is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation, either version 3
 * of the License, or (at your option) any later version.
 *
 * Tai-e is distributed in the hope that it will be useful,but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
 * Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with Tai-e. If not, see <https://www.gnu.org/licenses/>.
 */

package pascal.taie.analysis.dataflow.inter;

import pascal.taie.analysis.dataflow.analysis.constprop.CPFact;
import pascal.taie.analysis.dataflow.analysis.constprop.ConstantPropagation;
import pascal.taie.analysis.graph.cfg.CFG;
import pascal.taie.analysis.graph.cfg.CFGBuilder;
import pascal.taie.analysis.graph.icfg.CallEdge;
import pascal.taie.analysis.graph.icfg.CallToReturnEdge;
import pascal.taie.analysis.graph.icfg.NormalEdge;
import pascal.taie.analysis.graph.icfg.ReturnEdge;
import pascal.taie.config.AnalysisConfig;
import pascal.taie.ir.IR;
import pascal.taie.ir.exp.InvokeExp;
import pascal.taie.ir.exp.Var;
import pascal.taie.ir.stmt.Invoke;
import pascal.taie.ir.stmt.Stmt;
import pascal.taie.language.classes.JMethod;

import pascal.taie.ir.exp.LValue;
import pascal.taie.analysis.dataflow.analysis.constprop.Value;


/**
 * Implementation of interprocedural constant propagation for int values.
 */
public class InterConstantPropagation extends
        AbstractInterDataflowAnalysis<JMethod, Stmt, CPFact> {

    public static final String ID = "inter-constprop";

    private final ConstantPropagation cp;

    public InterConstantPropagation(AnalysisConfig config) {
        super(config);
        cp = new ConstantPropagation(new AnalysisConfig(ConstantPropagation.ID));
    }

    @Override
    public boolean isForward() {
        return cp.isForward();
    }

    @Override
    public CPFact newBoundaryFact(Stmt boundary) {
        IR ir = icfg.getContainingMethodOf(boundary).getIR();
        return cp.newBoundaryFact(ir.getResult(CFGBuilder.ID));
    }

    @Override
    public CPFact newInitialFact() {
        return cp.newInitialFact();
    }

    @Override
    public void meetInto(CPFact fact, CPFact target) {
        cp.meetInto(fact, target);
    }

    @Override
    protected boolean transferCallNode(Stmt stmt, CPFact in, CPFact out) {
        // TODO - finish me
        return out.copyFrom(in);
    }

    @Override
    protected boolean transferNonCallNode(Stmt stmt, CPFact in, CPFact out) {
        // TODO - finish me
        return cp.transferNode(stmt, in, out);
    }

    @Override
    protected CPFact transferNormalEdge(NormalEdge<Stmt> edge, CPFact out) {
        // TODO - finish me
        return out;
    }

    @Override
    protected CPFact transferCallToReturnEdge(CallToReturnEdge<Stmt> edge, CPFact out) {
        // TODO - finish me
        CPFact copy = out.copy();
        if (edge.getSource().getDef().isPresent()) {  // 检查edge.getSource()中是否有变量被定义
            LValue lValue = edge.getSource().getDef().get();
            if (lValue instanceof Var lVar) {
                copy.remove(lVar);
            }
        }
        return copy;
    }

    @Override
    protected CPFact transferCallEdge(CallEdge<Stmt> edge, CPFact callSiteOut) {
        // TODO - finish me
        CPFact newCPFact = newInitialFact();
        JMethod callee = edge.getCallee();  // 被调用方法
        Stmt source = edge.getSource();
        if (source instanceof Invoke invoke) {  // 检查source是否是一个方法调用
            InvokeExp invokeExp = invoke.getRValue();
            for (int i = 0; i < invokeExp.getArgCount(); i++) {
                Var actual = invokeExp.getArg(i);  // 获取实参变量
                Value value = callSiteOut.get(actual);  // 获取实参值
                Var formal = callee.getIR().getParam(i);  // 获取形参变量
                newCPFact.update(formal, value);
            }
        }
        return newCPFact;
    }

    @Override
    protected CPFact transferReturnEdge(ReturnEdge<Stmt> edge, CPFact returnOut) {
        // TODO - finish me
        CPFact newCPFact = newInitialFact();
        Stmt callSite = edge.getCallSite();
        if (callSite.getDef().isPresent()) {
            Value value = Value.getUndef();  // 累积从方法返回的所有可能值
            for (Var returnVar : edge.getReturnVars()) {  // 遍历所有返回变量
                value = cp.meetValue(value, returnOut.get(returnVar));
            }
            LValue lValue = callSite.getDef().get();
            if (lValue instanceof Var lVar) {
                newCPFact.update(lVar, value);
            }
        }
        return newCPFact;
    }
}

4 实现过程间 Worklist 求解器

4.1 算法

过程间 worklist 求解器所使用的算法和你在第二次作业中实现的过程内worklist求解器的算法大体上是一样的。它们仅有两处不同：

1. 在第 3.1 节介绍过，在计算一个节点的 IN fact 时，过程间求解器需要对传入的 edge 和前驱们的 OUT facts 应用 edge transfer 函数（transferEdge）。
2. 在初始化的过程中，过程间求解器需要初始化程序中所有的 IN/OUT fact，也就是 ICFG 的全部节点。但你仅需要对 ICFG 的 entry 方法（比如 main 方法）的 entry 节点设置 boundary fact。这意味着其他方法的 entry 节点和非 entry 节点的初始 fact 是一样的。

4.2 Tai-e 中你需要了解的类

• pascal.taie.analysis.dataflow.fact.DataflowResult

  你已经在此前的作业中见过这个类了。在本次作业中，你将会使用一个 DataflowResult 对象来管理 ICFG 中所有节点的 fact。通过使用该类中的 API，你可以获取或设置 ICFG 中各个节点的 IN/OUT fact。

• pascal.taie.analysis.graph.icfg.ICFG

该类代表的是程序的过程间控制流图。与 CFG 相似，它也是可迭代的（iterable），所以你可以利用 for 循环来迭代 ICFG 的所有节点：

ICFG icfg = ...;
for (Node node : icfg) {
    ...
}

• 关于 ICFG 的更多信息，请阅读源码和有关注释。

• pascal.taie.analysis.dataflow.inter.InterSolver

  该类是过程间数据流分析的求解器。它目前是不完整的，需要你根据第 4.3 节的说明来完成它。

4.3 你的任务 [重点!]

终于，这是你最后的任务了——完成 InterSolver 的两个 API：

• void initialize()
• void doSolve()

同样，你只需要实现前向分析的求解器，因为过程间常量分析就是前向的。你需要在 initialize() 中初始化 ICFG 节点的 IN/OUT fact，还需要在 doSolve() 中实现 worklist 算法的主要部分。

提示：

我们已经为待求解的分析、程序的 ICFG 和管理 fact 的 DataflowResult 创建了对象，并且把它们分别存在了 InterSolver 类的 analysis、icfg 和 result 字段里。这样，你可以很轻易地访问和操作这些对象。

/*
 * Tai-e: A Static Analysis Framework for Java
 *
 * Copyright (C) 2022 Tian Tan <tiantan@nju.edu.cn>
 * Copyright (C) 2022 Yue Li <yueli@nju.edu.cn>
 *
 * This file is part of Tai-e.
 *
 * Tai-e is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License
 * as published by the Free Software Foundation, either version 3
 * of the License, or (at your option) any later version.
 *
 * Tai-e is distributed in the hope that it will be useful,but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
 * Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with Tai-e. If not, see <https://www.gnu.org/licenses/>.
 */

package pascal.taie.analysis.dataflow.inter;

import pascal.taie.analysis.dataflow.fact.DataflowResult;
import pascal.taie.analysis.graph.icfg.ICFG;
import pascal.taie.util.collection.SetQueue;

import java.util.Queue;
import java.util.Set;
import java.util.stream.Collectors;

import pascal.taie.analysis.graph.icfg.*;
import java.util.*;


/**
 * Solver for inter-procedural data-flow analysis.
 * The workload of inter-procedural analysis is heavy, thus we always
 * adopt work-list algorithm for efficiency.
 */
class InterSolver<Method, Node, Fact> {

    private final InterDataflowAnalysis<Node, Fact> analysis;

    private final ICFG<Method, Node> icfg;

    private DataflowResult<Node, Fact> result;

    private Queue<Node> workList;

    InterSolver(InterDataflowAnalysis<Node, Fact> analysis,
                ICFG<Method, Node> icfg) {
        this.analysis = analysis;
        this.icfg = icfg;
    }

    DataflowResult<Node, Fact> solve() {
        result = new DataflowResult<>();
        initialize();
        doSolve();
        return result;
    }

    private void initialize() {
        // TODO - finish me
        for (Node node : icfg) {
            result.setInFact(node, analysis.newInitialFact());
            result.setOutFact(node, analysis.newInitialFact());
        }
        icfg.entryMethods().forEach(method -> {
            Node entryOf = icfg.getEntryOf(method);
            result.setOutFact(entryOf, analysis.newBoundaryFact(entryOf));
            result.setInFact(entryOf, analysis.newBoundaryFact(entryOf));
        });
    }

    private void doSolve() {
        // TODO - finish me
        workList = new ArrayDeque<>();
        for (Node node : icfg) {
            workList.add(node);
        }
        while (!workList.isEmpty()) {
            Node node = workList.poll();
            for (ICFGEdge<Node> nodeICFGEdge : icfg.getInEdgesOf(node)) {  // 对于当前节点的每一条入边
                // fact - analysis.transferEdge(nodeICFGEdge, result.getOutFact(nodeICFGEdge.getSource()))
                // target - result.getInFact(node)
                analysis.meetInto(analysis.transferEdge(nodeICFGEdge, result.getOutFact(nodeICFGEdge.getSource())), result.getInFact(node));
            }
            boolean f = analysis.transferNode(node, result.getInFact(node), result.getOutFact(node));
            if (f) {
                workList.addAll(icfg.getSuccsOf(node));
            }
        }
    }
}

5 运行与测试

你可以用 Tai-e 框架（教学版）配置指南 中介绍的方法来运行分析算法。本次作业中，Tai-e 首先运行 CHA 来创建程序的调用图，然后根据调用图构建 ICFG，最后在 ICFG 上运行过程间常量传播分析。为了方便调试，Tai-e 会将 CHA 和过程间常量分析的结果都输出到控制台。

#reachable methods: 0

----------Reachable methods:----------

#call graph edges: 0

----------Call graph edges:----------

----------------------------------------

--------------------<Example: void <init>()> (inter-constprop)--------------------

[0@L1] invokespecial %this.<java.lang.Object: void <init>()>(); null

[1@L1] return; null

--------------------<Example: void main(java.lang.String[])> (inter-constprop)--------------------

[0@L5] a = 6; null

[1@L6] temp$1 = invokestatic <Example: int addOne(int)>(a); null

[2@L6] b = temp$1; null

[3@L7] %intconst0 = 3; null

[4@L7] c = b - %intconst0; null

[5@L8] temp$3 = invokestatic <Example: int ten()>(); null

[6@L8] b = temp$3; null

[7@L9] c = a * b; null

[8@L9] return; null

--------------------<Example: int addOne(int)> (inter-constprop)--------------------

[0@L13] %intconst0 = 1; null

[1@L13] y = x + %intconst0; null

[2@L14] return y; null

--------------------<Example: int ten()> (inter-constprop)--------------------

[0@L17] temp$0 = 10; null

[1@L18] return temp$0; null

上面的例子已经在第 7 讲中介绍过。因为当前你还没有实现作业要求完成分析，所以此时该分析的调用图为空（没有任何的可达方法）并且 OUT fact 均为 null。

而当你完成了这些分析之后，输出应当形如：

#reachable methods: 3

----------Reachable methods:----------

<Example: int addOne(int)>

<Example: int ten()>

<Example: void main(java.lang.String[])>

#call graph edges: 2

----------Call graph edges:----------

<Example: void main(java.lang.String[])>[1@L6] temp$1 = invokestatic <Example: int addOne(int)>(a); -> [<Example: int addOne(int)>]

<Example: void main(java.lang.String[])>[5@L8] temp$3 = invokestatic <Example: int ten()>(); -> [<Example: int ten()>]

----------------------------------------

--------------------<Example: void main(java.lang.String[])> (inter-constprop)--------------------

[0@L5] a = 6; {a=6}

[1@L6] temp$1 = invokestatic <Example: int addOne(int)>(a); {a=6}

[2@L6] b = temp$1; {a=6, b=7, temp$1=7}

[3@L7] %intconst0 = 3; {%intconst0=3, a=6, b=7, temp$1=7}

[4@L7] c = b - %intconst0; {%intconst0=3, a=6, b=7, c=4, temp$1=7}

[5@L8] temp$3 = invokestatic <Example: int ten()>(); {%intconst0=3, a=6, b=7, c=4, temp$1=7}

[6@L8] b = temp$3; {%intconst0=3, a=6, b=10, c=4, temp$1=7, temp$3=10}

[7@L9] c = a * b; {%intconst0=3, a=6, b=10, c=60, temp$1=7, temp$3=10}

[8@L9] return; {%intconst0=3, a=6, b=10, c=60, temp$1=7, temp$3=10}

--------------------<Example: int addOne(int)> (inter-constprop)--------------------

[0@L13] %intconst0 = 1; {%intconst0=1, x=6}

[1@L13] y = x + %intconst0; {%intconst0=1, x=6, y=7}

[2@L14] return y; {%intconst0=1, x=6, y=7}

--------------------<Example: int ten()> (inter-constprop)--------------------

[0@L17] temp$0 = 10; {temp$0=10}

[1@L18] return temp$0; {temp$0=10}

另外，Tai-e 会将它所分析程序的 ICFG 输出到目录 output/ 下。ICFG 被保存为可以使用 Graphviz 可视化的 .dot 格式。

使用 dot -Tpng xxx.dot -O 命令即可将.dot 文件转换为 png 来查看

注意，每个 ICFG 都是基于一个调用图构建的，所以一旦你修改了 CHABuilder，那么即使分析同一个程序，Tai-e 也可能会输出不同的 ICFG。

我们已经提供了 pascal.taie.analysis.graph.callgraph.cha.CHATest 和 pascal.taie.analysis.dataflow.analysis.constprop.InterCPTest 作为 CHA 和过程间常量传播的测试驱动类。如 Tai-e 框架（教学版）配置指南 所介绍，你可以使用它们来测试你代码的正确性。

 在本次作业中，你实现的分析是过程间分析。过程间分析会从入口方法来分析整个程序，也就是 main 方法。所以，请确保被分析的类有一个 main 方法：public static void main(String[])。

设置入口方法文件：Tai-e-assignments-main\A4\tai-e\src\main\java\pascal\taie\analysis\graph\callgraph\CHABuilder.java