存活性分析（Liveness Analysis）

写于2022年1月23日。最后更新于2022年2月7日。

存活性分析主要计算出在MIR的各个位置处有哪些借用源（Origin）存活，用于下一阶段的借债分析。

输入

1. 普通变量的定义、使用、丢弃情况。

.decl var_defined_at(Variable, Point)
.decl var_used_at   (Variable, Point)
.decl var_dropped_at(Variable, Point)

.input var_defined_at
.input var_used_at
.input var_dropped_at

2. 对于引用变量而言，需要输入变量所关联的借用源。

如下

let a: i32 = 0;
let b: &'b i32 = &a;

其中b变量将关联到借用源'b。

另外还有丢弃时关联借用源（详见思考3）。

.decl drop_of_var_derefs_origin(Variable, Origin)
.decl use_of_var_derefs_origin (Variable, Origin)

.input drop_of_var_derefs_origin
.input use_of_var_derefs_origin

推导

1. 变量存活情况

对于每一个变量，从每个使用的位置处，沿CFG 逆边向前追溯到变量定义处，都视为存活。

var_live_on_entry(Variable, Point) :-
    var_used_at(Variable, Point).

var_live_on_entry(Variable, SourcePoint) :-
    var_live_on_entry(Variable, Targetpoint),
    cfg_edge(SourcePoint, TargetPoint),
    !var_defined(Variable, SourcePoint).

2. 将变量的半初始化状态沿CFG传播。

var_maybe_partly_initialized_on_entry(Variable, TargetPoint) :-
    var_maybe_partly_initialized_on_exit(Variable, SourcePoint),
    cfg_edge(SourcePoint, TargetPoint).

3. 变量的丢弃前存活情况

对于每一个变量，在其 半初始化 的范围内，从每个丢弃处开始，沿CFG 逆边向前追溯到变量定义处，都视为 丢弃前存活（drop-live）。

var_drop_live_on_entry(Variable, Point) :-
    var_dropped_at(Variable, Point),
    var_maybe_partly_initialized_on_entry(Variable, Point).

var_drop_live_on_entry(Variable, SourcePoint) :-
    var_drop_live_on_entry(Variable, TargetPoint),
    cfg_edge(SourcePoint, TargetPoint),
    !var_defined_at(Variable SourcePoint),
    var_maybe_partly_initialized_on_exit(Variable, SourcePoint).

4. 借用源存活状态

对每处的存活引用变量，都标记其关联的借用源为存活。

origin_live_on_entry(Origin, Point) :-
    var_live_on_entry(Variable, Point),
    use_of_var_derefs_origin(Variable, Origin).

同样地，对于丢弃前存活的引用变量，也标记其相关联的丢弃时借用源为存活。

origin_live_on_entry(Origin, Point) :-
    var_drop_live_on_entry(Variable, Point),
    drop_of_var_derefs_origin(Variable, Origin).

思考（部份内容来自 Zulip的讨论）

1. 既然已经有基于路径的一些输入事实（如`path_assigned_at`、`path_accessed_at`、`path_moved_at`等），并且也有`path_is_var`能与变量对应起来，为什么还需要基于变量的输入事实呢（如`var_used_at`、`var_dropped_at`、`var_defined_at`等）？

第一阶段的初始化分析，与具体的字段相关；而第二阶段的存活性分析与第三阶段的借债分析都只与变量相关。对存活性分析而言，变量相关的输入事实是必须的、而字段相关的输入信息是可选的，后续可能移除字段相关的输入，但变量相关的输入不会变。

具体的区别有：

(1) path_assigned_at与var_defined_at

path_assigned_at与var_defined_at的最大区别是：
- 在MIR的每一条赋值语句中，var_defined_at一定发生在当前语句中间（Mid）；
- 而path_assigned_at可能发生在当前赋值语句中间（Mid），或下一条语句之前（Start），
  - 若当前语句不需要unwind，则path_assigned_at在当前赋值语句中间；
  - 若当前语句需要unwind，则path_assigned_at在执行成功的分支中下一条语句之前。
var_defined_at还包含StorageLive与StorageDead信息，及变量被赋值的信息。
path_assigned_at还包含进入函数时，对入参的初始化赋值。

在初始化分析中，当某些函数调用发生了panic时，其返回值不会被初始化，因此path_assigned_at发生在执行成功后下一条语句之前。

但存活性分析及后续的借债分析，并不在意在发生panic后变量是否处于未初始化状态。

对于var_live_on_entry而言，在某条赋值语句（如_3 = may_panic() [return -> bb1; unwind -> bb2]）发生panic后，其「清理」路径（从bb2开始，依次丢弃已初始化的变量）并不会使用到该变量（_3），也不会产生相应的var_defined_at事实，因此即使发生了panic，产生的var_defined_at在unwind过程中并不会产生var_live_on_entry事实，所以此处的var_defined_at不需要像path_assigned_at那样，必须发生在非unwind分支的入口处。
对于var_drop_live_on_entry而言，具体由于unwind过程中可能产生var_dropped_at事实，因此有可能影响到var_drop_live_on_entry，所以具体情况有待进一步实验验证。

(2) path_accessed_at与var_used_at

var_userd_at等于path_accessed_at加上返回值的访问信息。

(3) path_moved_at与var_dropped_at

path_moved_at只能追踪到其赋值与移动。而变量在超出其作用域后，还会被丢弃，无法通过路径的移动信息推导出变量的丢弃信息。

2. 为什么`var_defined_at`中包含`StorageLive`和`StorageDead`？

StorageLive与StorageDead主要用于LLVM栈空间分配。见MIR相关文档。

StorageLive(_1)表明变量_1存活，也即其可能在稍后使用——直到StorageDead(_1)语句出现，即_1将不再使用。StorageLive与StoraageDead语句用于LLVM中的栈空间分配。

在StorageLive之后，变量才开始使用，此处的var_defined_at可以阻止存活性分析中的var_live_on_entry追溯到早于StorageLive的地方（因为这些地方变量未被使用到）。

StorageDead不太必要，因为在StorageDead后，将不再可能出现变量被访问的情形。

3. 为什么要区分`drop_of_var_derefs_origin`与`use_of_var_derefs_origin`？

由于rfc#1327的缘故，变量在丢弃时的使用情况状态与正常使用时的使用情况有所不同。

drop_of_var_derefs_origin的含义是，变量在丢弃时，由于其drop函数中可能访问其包含的引用，因此需要将其视作存活，除非显式指明#[may_dangle]。

例如：

fn main() {
    let mut v = [1, 2, 3];
    let p: Wrapped<& /* R4 */ usize> = Wrapped { value: &v[0] };
    if true {
        drop(*p.value);
    } else {
        v[0] += 1; //~ ERROR cannot assign to `v[_]` because it is borrowed
    }

    v[0] += 1; //~ ERROR cannot assign to `v[_]` because it is borrowed
}

struct Wrapped<T> {
    value: T
}

impl<T> Drop for Wrapped<T> {
    fn drop(&mut self) { }
}

由于在Wrapped::drop中可能访问到value字段（无显式访问，但在丢弃其字段时会隐式访问到），因此需要drop_of_var_derefs_origin输入事实，表明p.value借用的变量&v[0]直到p被丢弃时（main函数结束前），一直处于存活状态。

若将impl<T> Drop for Wrapped<T>改为

unsafe impl<#[may_dangle] T> Drop for Wrapped<T> {
    fn drop(&mut self) { }
}

则不产生drop_of_var_derefs_origin事实，因而后面v[0] += 1也视为合法。

4. 为什么`var_drop_live_on_entry`要包含`var_maybe_partly_initialized_on_entry`的信息？

即使变量出作用域时已被移动，而原始的MIR中仍然包含相应的drop语句。Polonius引擎（包括此前的借用检查引擎）手动过滤了所有的「移动后丢弃」语句。但变量变量在部份移动后，开始处于「丢弃前存活」的状态，且部份丢弃的变量不会产生var_dropped_at事实，因此需要var_maybe_partly_initialized_on_exit来补上变量的部份移动信息。

Rust中文博客

思考（部份内容来自Zulip的讨论）

思考（部份内容来自 Zulip的讨论）