基于 IFCMP_A 的冗余 NULL_CHECK 消除

发表于 更新于

这是一篇水文。

做编译原理课程实验，要求基于 joeq 反编译出的三地址码做 Java 程序中的冗余 NULL_CHECK 消除。我们知道 JVM 在对对象做一些操作前，需要检查它是否为 null（例如：调用虚函数、给数组成员赋值）；但是有的时候，我们可以在编译期确定某个对象在某个时刻一定不是 null，从而可以消除一些 NULL_CHECK 语句。实验要求中提到我们可以内卷可以实现扩展功能，举的例子里提到可以基于 IFCMP_A 来做这件事，我感到很有意思，就做了一做。

IFCMP_A 的作用是比较两个对象（可以是变量 Register，或者字面值 AConst），在结果是相等或不等的情况下，跳到某个基本块，否则就继续执行。所以这条语句有 4 个参数，并且一定位于基本块的末尾，而且有两个后继。

对象与 null 比较

这是比较简单的。前向数据流框架的格可以只包含两个元素：Nullable 和 NotNullable。在这种情况下，一条这样的 IFCMP_A 的两个后继都能得到一条「知识」：从某个前驱来的路径上，某个变量必然是 Nullable 或者必然是 NotNullable。由于代码的组织结构问题，我们没办法修改数据流框架的求解代码，因此只能在处理每个 Quad 的时候，重新检查它的前驱的 out 集合，结合上述知识去修改这条 Quad 的 in 集合：

  • 如果对于某个变量，其所有的前驱或者有一条「知识」表示该变量是 NotNullable，或者 out 集合里该变量是 NotNullable，那么这条 Quad 的 in 集合中该变量也是 NotNullable；
  • 否则该变量就是 Nullable。

这样就可以消除所有显式地与 null 比较过的变量的不确定性。并且所有这些都可以在求解数据流方程之前就预处理出来，求解的时候只要拿来用就好了。

对象与对象比较

当然这个时候也可以直接仿照上面的做法。这个时候，对任意变量 x 而言，「知识」就有四类：

  1. x 一定是 null
  2. x 一定不是 null
  3. x 与 y 相等
  4. x 与 y 不相等

第 3 种知识只在 y 是 NotNullable 而 x 是 Nullable 时才能起到作用（即，这条知识可以 override 数据流方程的结果），而第 4 类知识没有任何作用。

这显然不是我们想要的结果，我们希望第 4 类知识也能起到作用。为了达到我们的目的，我们必须能确定地知道一个变量是否一定是 null。那么，数据流框架的格就必须发生变化；现在，每个变量有 3 种状态：一定是 null、一定不是 null，或者二者皆有可能。我们用 IsNull、IsNotNull 和 Either 代表三种状态。

但是这里立即就出现了一个问题：半格必须要有顶元素，而 IsNull 和 IsNotNull 之间却不应该存在偏序关系，都不是顶元素；Either 又明显是个底。这样一来，我们只能像常量传播时那样，引入一个 Undef 来作为顶元素。在程序入口，我们把所有变量都置为 Undef 而不是 Either。

Undef 是一个很麻烦的东西。从它的意义上来理解，它应该和 Either 扮演完全相同的角色，但我们又希望它是个顶元素，在和 IsNull 或 IsNotNull 交汇的时候变为 IsNull 和 IsNotNull。简而言之，我们不希望在处理「知识」或者检查 NULL_CHECK 冗余性的时候见到这个玩意儿。

幸运的是，有些状态为 Undef 的变量会被 NEW、MOVE_A 和其他语句重新定义，从而变为 IsNull、IsNotNull 或者 Either。至于其他变量则不那么讨喜，会一直保持 Undef 直到某个关键的地方从而引发麻烦。要点在于，我们可以用一次活跃性分析来找到所有这样的变量！只需要找出在程序入口活跃的变量，然后在冗余分析时，把它们的状态从一开始就置为 Either，我们就能保证绝对不会在 IFCMP_A 或者 NULL_CHECK 的时候遇见一个 Undef 的变量。

这样一来，我们就可以完美地解决 Undef 带来的麻烦。上面的第 4 类知识也就能够派上用场：假如 y 一定是 null，那么 x 就一定不是 null。

null 与 null 比较

这种情况过于沙雕，可以在编译期就优化掉一个或一些基本块……

由于我懒得写，也懒得确认字面值 AConst 除了 null 是不是还有其他的可能性，所以就咕了吧……

就这样。