Tai-e A4&A7

实验手册

Misc

JVM 的 invoke 类型

以下没有考虑一些新的语法特性

• invokestatic

  类的静态方法

  实际调用的方法在编译时可确定

• invokespecial

  构造器、私有实例方法、超类的实例方法（通过 super 关键字）

  实际调用的方法在编译时可确定

• invokeinterface & invokevirtual

  其余所有实例方法

  实际调用的方法在运行时才可确定（多态）

CHA 算法

• CHA 算法只考虑引用的类型，而不是实例的类型

  比如 B b = new A();，考虑的是 B 类型的方法，而不是 A 类型的方法

• 方法

  一个方法由一个方法签名标识。方法签名定义为：类型 + 方法名 name + 描述符 desciptor

  其中，描述符又定义为：返回值类型，参数类型

  在 Tai-e 中，方法的类型由调用 pascal.taie.ir.proginfo.MethodRef.getDeclaringClass() 可得到，它返回一个 JClass 实例，对应方法的声明类型（而不是实例类型！）；方法名和描述符通过 pascal.taie.ir.proginfo.MethodRef.getSubsignature() 得到

• Dispatch($c, m$)

  $c$ 类中定义了与 $m$ 具有相同名字以及相同描述符的非抽象方法 $m'$，那么 Dispatch($c, m$) = $m'$；

  否则，Dispatch($c, m$) = Dispatch($c', m$)，其中 $c'$ 是 $c$ 的超类

• Resolve

  Resolve(cs)
    T = {}
    m = method signature at cs
    if cs is a static call then
      T = { m }
    if cs is a special call then
      c^m = class type of m
      T = { Dispatch(c^m, m) }
    if cs is a virtual call then
      c = declared type of receiver variable at cs
      foreach c' that is a subclass of c or c itself do
        add Dispatch(c', m) to T
  return T

Java 语法回顾

• static 方法不能被继承
• statitc 方法只能调用 static 的方法，这点在自己写测试用例时要注意

Implemention

A4

• 在实现 CHABuilder 时，算法伪代码中的 subclass 如何界定？如果当前 JClass 是一个 Interface，那么它的所有子 Interface 和 Implementation 都应该被视作它的子类
• 在实现 transferReturnEdge 时，小心处理多返回值！复用某个之前实现的函数就可以解决这个问题
• 计算 IN 时只考虑 inEdge 就够了，不能再考虑 predNode！
• 实验文档很重要！实验文档中介绍的 API，如果有没用到的，大概率会出错…用到了实验文档中没有出现的 API，大概率也会出错…

A7

• load 与 store 的处理

  阅读完实验文档后，一个直觉的想法是，处理到一个 load 语句时，找到所有有关的 store 语句，将这些 store 语句的右值进行 meet。同时要考虑到，每处理一个 store 语句时，如果导致字段的值变化，那么需要将相关的 load 语句放入工作表中

  上面的过程，既有 load 语句从 store 语句的 pull，也有store 语句对 load 语句的 push。在许多系统的设计中，不考虑性能的话，push 和 pull 其实只用实现一种就够了（类比下 shardkv 分片的更新逻辑，既可以 push 也可以 pull）。考虑到分析中的 push 是不可少的，那么仅实现 push 即可。具体来说，处理到一个 load 语句时，不是去遍历所有相关的 store 语句，而是直接从一个全局的 Map 中取出值即可；处理到一个 store 语句时，将这个语句的右值与全局的 Map 中的值进行 meet，如果 meet 后的值变更了，那么将所有相关的 load 语句加入工作表，以反映最新的值变化

• 上面提到的「相关」的语句，其实就是具有别名的语句。根据实验文档，如果两个变量 $x$ 与 $y$ 的指针集具有交集，那么 $x.f$ 与 $y.f$ 就可以视作别名。比如在处理 $x.f=3$ 时，一种直观的方法是取出 $x$ 的指针集 $pt(x)$。然后，我们遍历程序中的所有 Var，对于每个 Var $y$，若 $pt(x)$ 与 $pt(y)$ 具有交集，那么 $x.f$ 与 $y.f$ 就视作别名。这种直观但是暴力的做法当然是可行的。不过，结合操作系统反置页表的思想，我们可以设计一个与指针集（Var 到 Set<Obj> 的映射）相反的数据结构，即一个 Obj 到 Set<Var> 的映射。对于 $pt(x)$ 中的每个 $obj$，取出它所映射的 Set<Var>，这个集合中的全部 Var 就是 $x$ 的别名，也包含了它自身

• 数组的处理

  在处理数组的 load 语句时，除了 meet a[const]，还要额外 meet a[NAC]！

• Map 的访问

  用好 getOrDefault

• 模块职责划分的考虑

  实验文档有提到：「InterConstantPropagation 在其字段中持有 InterSolver 的实例，因此你可以在 InterConstantPropagation 中调用 solver 的 API」。但是找了半天还是没找到😢。由于在处理 store 语句时需要往工作表中加入相关的 load 语句，而 worklist 不宜作为 InterSolver 的静态字段暴露出来，于是最终考虑将本次实验新增的代码全部写在了 InterSolver 中

Result

A4

一发 AC 了，预想中这次的 corner cases 应该很多才对…

A7

还剩一两个测试点没通过（重构后反而少过了一个测试点🤣）