高效的指针分析与二进制类型恢复

基于《FULCRA POINTER ANALYSIS FRAMEWORK》，迁移到retypd（《Polymorphic Type Inference for Machine Code》）上

总体架构

算法的主要思想是，基于调用图自底向上遍历，并生成描述副作用的摘要。通过实例化摘要，不断将“副作用”从callee提升到caller。当所有的函数调用都没有副作用时，上下文非敏感的分析结果将会等价于上下文敏感的分析结果。

算法的主要特点有： - 基于Solution Preview的思想，不断迭代结果，不断复用，而不是重新计算。

算法主要分为两个阶段： 1. 不断拓展Solution Preview，不断发现新的调用边，完善调用图 2. 基于调用图自底向上summarization总结每个函数。创建summary的同时，实例化到Caller中，并再次尝试推理指针分析。 1. COMPACT分析（第86页），用于简化和压缩约束 1. holding, opacity, and criticality分析（第84页）

Criticality（第43页, 3.2.1）

Caller调用Callee的时候，可能出现指针的传递与访问，从而改变Caller中变量的值（包括指针变量的指向关系）。典型的情况就是，传了一些值到Callee里，然后有一个关键的（Critical）赋值，然后相关的值被传递回Caller上面。

三个重要概念：

Criticality：导致副作用的赋值
Holding：表示某个变量可能会存放外来的值。比如一开始的时候，参数都是holding的。然后Holding的值会被进一步传递到其他变量。
- 对于语句*u = v如果v和u都是holding的，那么这个赋值语句是critical的。
Opaque：如果没有调用上下文，数据流传递关系不确定的变量，就是不透明的。
- 所有外部定义的变量是不透明的（opaque）。
- 一个局部变量的地址被放到了外部定义的变量时，别的外部指针变量的store可能会存到局部变量里，此时该局部变量也变成不透明的。

如下是相关的传递规则：

从holding变量中加载得到的值是holding的：对于u:=*v，如果v可能指向外部变量（Holding），那么u也可能指向外部变量（Holding）。对应约束图中，holding属性可能沿着.load边逆向传递。
被holding变量赋值的变量是holding的：对于u:=v，如果v可能指向外部变量（Holding），那么u也可能指向外部变量（Holding）。对应约束图中，holding属性可能沿着子类型边（数据流）传递。
某局部变量的地址被存入holding变量，则该局部变量是不透明的：如果u可能指向外部变量（Holding），*u = &w，那么w变量是不透明的（opaque）。对应约束图中，如果一个变量的地址被存入了外部的地址中，则该变量是不透明的。
某局部变量的地址被赋值给holding变量，则该局部变量是不透明的：对于u:=&v，如果u可能指向外部变量（Holding），那么v变量是不透明的（opaque）。对应约束图中，如果一个变量的地址被赋值给不透明变量，则该变量是不透明的（opaque）。（TODO，为什么）
不透明的参数可能指向外部变量：如果u是参数，且u是不透明的，那么，u可能指向外部变量（Holding）。
不透明变量的地址是不透明的：如果v是不透明的，且u:=&v，即v的地址被赋值给了变量u，则u是不透明的（opaque）

Critical规则：

赋值给holding变量的赋值是可能产生副作用的（critical）。
赋值给不透明变量的赋值是可能产生副作用的（critical）。无论是加载出来的值，还是取地址的值。

这意味着