2020-Pointer Analysis (Andersen-Style & Steensgaard-Style)

[skyleaworlder]

https://sites.cs.ucsb.edu/~yufeiding/cs293s/slides/293S_11_point-to-analysis.pdf Yufei Ding
https://www.cs.cmu.edu/~aldrich/courses/15-819O-13sp/resources/pointer.pdf Jonathan Aldrich [email protected]

from google

[skyleaworlder]

class Base {}

class A : Base() {
  abstract fun hello()
}

class Aplus : A() {
  override fun hello() = println("This is Aplus")
}

class Another : A() {
  override fun hello() = println("This is Another")
}

class B : Base() {}
class Bplus : B() {}
class Bnother : B() {}

fun foo(A a, B b) {
  var c: A? = null
  var d: B? = null

  val res: Base = if (isOK(a)) {
    c = a; a
  } else {
    d = b; b
  }
}

[skyleaworlder]

Andersen-Style 和 Steensgaard-Style 都是 flow-insensitive 指针分析算法，通过为四种指针运算定义规则完成指向关系图的构建，这两种算法都不在乎以下两种顺序：

• 指令执行顺序：因为是 flow-insensitive 的，并且四种规则定义的都是集合间的约束关系（元素属于集合，集合间的包含），并非 flow-sensitive 的逐条指令增加 edge；
• 约束选取顺序：因为在实现上通常使用 worklist 算法以期望将指向集们迭代到一个稳定值，收敛的过程是递增的，所以指针 load 与 store 规则对应的包含关系，其选取顺序也是不重要的，反正最后都会收敛。下为 Anderson-Style：

这里提到的 base and simple constraints 指的是 "p = &q" 与 "p = q" 这两类，因为：

• p = &q 是四种关系中唯一的 “元素属于集合”，能够确定某 location 的 object 一定在某指针的指向集中；
• p = q 是四种关系中唯一一个不需要 dereference / address-of 关系的，所以在指向关系图尚不明朗时依旧可以根据 p = q 填好的元素进一步有效 (sound & efficient) 填充各指针的指向集。

[skyleaworlder]

Andersen-Style 时间复杂度是 O(n^3) 的原因：

• n 条语句最多设计 n 个变量，所以最多有 n 个节点；
• $p \supseteq q$ 这个约束最多只会带来 n 条新边，所以往 worklist 里面最多只会加 n 个变量，在循环中最多可能被拿出来 n 次；
• $p \supseteq *q$ 和 $*p \supseteq q$ 这两种约束由于存在 $*p$ 或 $*q$，在上面的算法中是先取出 worklist 中的 node 其指向集中的所有 node，然后把 $p \supseteq *v$ 和 $*v \supseteq q$ 这两种约束中涉及的所有 node 都掏出来。这里建立的边是 n^2 的。（个人感觉可以理解成：本来 p 和 q 最后最多可能有 n 个变量，而 *p 和 *q 更是最多可能牵扯 n^2 个变量，这就导致 $p \supseteq *q$ 和 $*p \supseteq q$ 这两种约束它最多在迭代中被拿出来 n^2 次）