partial evaluation 的第四章 Partial Evaluation for a Flow Chart Language 的笔记.

这一章介绍了一个叫做 Flow Chart 的语言, 是一个以基本块组成的语言. 然后通过这个语言实现了两个二村映射来介绍Partial Evaluation的技巧.

程序和状态

然后就是程序点和程序状态的概念: 程序点就是程序执行的位置, 程序状态指的是程序执行的状态, 具体的状态的值域取决于语义的定义. 这一点和静态分析里的定义是类似的.

程序的状态可能有很多, 但大部分的语言都可以通过 变量 - 值 的映射来表示. 其中对于每个 program point, 变量的值可以分为 static 和 dynamic 分为两类. static 表示变量的值可以在静态确定, 而 dynamic 的值只能在运行时确定. 将每个 program point 的变量区分为 static 和 dynamic 的过程叫做 division.

基于 static 程序状态做 partial evaluation

这就引出了一个概念叫做 poly, 指的是基于输入和已知的程序点的 static 变量的值, 可以最大程度地确认多少程序点的 static 变量? 这个问题的求解结果可以通过一个由 程序点-static value 序对组成的集合来表示 poly. 这些 poly 就对应着 residual program (specialized program) 的 program point.

一个直觉的描述是: 对于 subject program 在每个 program point, 把这个 program point 对应的 basic block 根据不同的 static state “展开"的结果就是 residual program; “展开"之后, static 的属性就"嵌入"到 residual program 中, 成为 residual program 的一部分了, 而不再通过 subject program 的属性来表达.

division

division 指的是在做 partial evaluation 之前, 先把程序变量做一个 Static 和 Dynamic 的区分, 因此这个过程也叫/Binding Time Analysis(BTA)/, 分析一个 value 的"绑定时机”.

BTA 有一个要点是要满足 相合性(congruence),

division 的结果并不一定是唯一的, 只要满足以下 congruence 条件就行:

Any variable that depends on a dynamic variable must itself be dynamic.

也就是标记为 Static 的变量不能依赖于 Dynamic 变量.

这个定义其实有一些抽象. 我们来设想一种场景, 对于一个循环中的变量, 第一次循环的值是确定的, 然后在循环中会通过赋值更新这个变量(这个 Flow Chart 的语言是允许赋值的), 那么这个变量算是什么呢?

首先, 我们先看一下相合性本身的强大, 然后我们再来介绍一些更加高级的 division 方法

Static 变量可能比想象的多

一个变量标记为 Static 并不等于这个变量没有被修改过, 理论上满足相合性的 BTA 可以标记的 Static 变量可能比想象的多.

比如说一个循环的循环次数(假设为 k 次)和对变量更新的值都是可以 static 的, 那么把这个变量标记为 Static 是满足相合性的.

一个简单的验证办法是我们可以把这个循环展开 k 次, 展开后的程序的循环变量显然都是 static 的.

但是如果每次循环对变量更新的值仍然是 static 的, 但是循环的次数可能有无限多次, 这个变量我们应该标记为 static 吗?

对于这种情况, 我们将变量标记为 static 是满足相合性的: 因为给定任意的 k, 我们都能确定这个变量第 k 次循环的值.

但是, 如果把它们当作 Static 的, subject program 的 poly 将会是无限的, 从而导致根本无法有效的计算出一个 residual program (程序都是有限的). 所以, 从计算 residual program 的角度来说, 无限多种的 static variable 是没有意义的.

所以对于这种虽然标记为 Static 满足相合性, 但是会导致在 partial evaluation 的过程中会得到无限多状态的变量, 我们只选择在 BTA 的过程中将他们标记为 Dynamic.

这样我们就得到了一种十分简单且对任何情况都适用的处理方式:
所有麻烦的东西都当成 dynamic 就好了!

即使某些地方这个变量的值是已知的, 为了满足相合性, 我们直接直接将这个变量标记为 Dynamic 的, 这样虽然有一些静态信息我们没有利用, 但基于这样的 division 做 partial evalutaion 仍然是安全且可用的.

但是从 partial evaluation 最基本的直觉出发, 我们标注为 dynamic 的东西越多, 我们能够 specialize 的东西就越少, partial evaluation 所能带来的优化也就更少. 所以, 我们的 division 应该在保证相合性和可计算性的前提下尽可能的让 dynamic 少.

那有没有什么通用的办法, 让我们给出 division 的同时, 还能保证这个 division 的 dynamic 是 最少 的?

很可惜, 这个问题是个 不可判定 问题.

不过书上说他们之后会给个办法给一个可接受的解(前面提到了, 合理的 division 并不唯一).

更加高级的 division

除了全程序共用一个 division, 也有很多更加高级的 division 方式, 这又根据其目的分了不同的情况, 有的是为了利用更多的静态信息, 有的是为了生成更高质量的 residual program. 不过基本思想都是把 division 进行"参数化”, 以表达更复杂的计算上下文中的 static value. (这点和程序分析中的上下文敏感很相似)

Point-wise Division

除了全程序共用一个 division 的方法, 还可以点对点(Point-wise)的设置 division. 在这种 division 下, 每个程序点的 division 可以是不同的.

可以通过一个程序来说明 pointwise 的含义(书中的例子):

read(X, Y);
init: X := X + 1
      Y := Y - 1
cont: Y := 3
next: ...

如果程序的输入 (X, Y) 的 init division 是 (S, D), 如果使用 uniform division(全程序共用一个 division)的话, 那么即使在 next 处 Y 的值明显是已知的, 也不能把他标记为 Static 的.

Polyvariant Division

Polyvariant 的 Division 指的是: 一个 division 不仅仅和程序点有关, 还和程序如何执行到这个程序点有关. 对于一个变量, 有的执行路径下把它标注为 Static, 有的路径标注为 Dynamic. 这种 division 就可以很灵活了, 此时, division 可以由一个 flow -> division 的映射表示.

此时, 一个程序点可能对应多个 division(之前的 point-wise division 是每个点对应 1 个), 所以叫 poly variant division(每个程序点对应 1 个的叫 mono variant division)

疑问: 那可不可以再更加灵活一点呢? 比如说通过 flow -> state -> division 表示, state 是上一个程序点的状态.

Live and Dead Division

目前的 division 只包含变量关于 Static 和 Dynamic 的划分. 但是有的时候, 这个变量在某个 program point 的值是 static 的, 但是这个变量在这个点没有被用到过(dead), 那我们可以在 residual program 的 program point 安全的抹去这些变量的值.

因此 Live and Dead Division 也可以看作是一种 pointwise division, 前述的 pointwise division 是每个 program point 的 static value 可以不同, Live and Dead Division 是每个 program point 包含的 static value 也可以不同.

Transition Compression

路径压缩的目的是简化生成的 residual program 的质量, 消灭掉一些没有意义的跳转, 比如说生成的程序包含从一个基本块 x := 1 到基本块 y := 1 的跳转, 那么可以把这两个基本块直接合并成一个基本块. 其本身不会对生成程序的正确性和性能造成影响(这里的性能指的是抽象机中的性能, 真实的程序由于 cache locality, 跳转的数量和距离都会对性能有影响).

需要注意的是, Transition Compression 是有可能带来代码重复的. 比如说, 有两个基本块都跳转到统一个基本块, 但是我们把两个跳转都压缩了, 这就会带来代码重复. 需要谨慎的选择需要压缩的 transition 以避免代码爆炸的问题.

Mix 算法

Partial Evaluation 一般要做以下几件事情:

  1. 根据输入, 确定变量的 division; 也就是把变量区分为 static 和 dynamic 两类. 这一步有的是和计算 residual program 的过程是合在一起的(online)
  2. 基于 division 计算 poly, 也就是 specialized program 的 program points. 前面提到了, poly 也有很多种不同的方式
  3. 根据 poly, 生成 specialized program
  4. (optional) transition compression
  5. (optional) relabel the program

书中展示了一个完整的 mixer 程序, 做了上面的 5 件事情:

虽然上面的所有事情这个 mix 程序都做了, 只是有一些操作是隐式的. 比如说 transition compression, 没有一个过程叫做"transition compression", 当遇到 goto l 的时候, 直接把要插入的 basic block 更新成 l 对应的基本块就可以了.

第一二村映射

如 Partial Evaluation 中的描述, 第一二村映射指的是将一个 interpreter 在 interpreter 的输入程序上进行 specialize, 将会得到一个可执行程序.

一个解释器的完整定义如下:

一个简单的程序可以被该解释器解释的程序:

传入 mix 后, 将得到一个 specialized 的解释器

Program point of target 和 (Program point, static variable) of interpreter 之间的对应关系:

第二二村映射

mix 程序可以把 program specialize 到 program 的静态可确定的程序状态 vs_0. 但是 mix 程序本身不也是程序吗? 它的输入是 program, division 和 vs_0.

那么 mix 可不可以把 program 参数 specialize 到某个程序呢?

答案是可以的, 也就是 mix 程序具有 应用到自己(self-application) 能力!

把 mix 本身作为 mix 待 specilize 的程序, 然后把 mix 在解释器程序上 specialize 后就可以得到一个编译器, 这就是 第二二村映射.

在 Mix 中利用更加高级的 division

为了简单起见, 刚刚提到 mix 算法采用的是 offline partial evaluation, 也就是先 通过 binding time analysis 算出 division(可以看到 mix 有一个 division 参数), 然后通过这个 divison 计算 residual program, 这个 division 在整个程序中是始终不变的.

想要使用刚刚提到的更加高级的 division, 我们需要对 mix 程序进行一些修改.

在 mix 中使用 point-wise division

在 mix 中使用 point-wise division 只需要把原来的 division 表示 改成一个记录了每个 point 的 division 的表就可以了. 每次需要知道某个 program point pp 的 division 的时候 lookup(pp, division) 就可以了.

有了 point-wise division, live and dead 就十分简单了, 还是给每个让每个 program point 的 division 不同, 刚刚提到的 point-wise division 指的是对于每个 program point, “哪些变量是 Static, 哪些变量是 Dynamic"这一信息是不同的; live and dead division 指的是对于每个 program point, “需要考虑哪些变量是 Static 或 Dynamic"这一信息不同.

在 mix 中使用 polyvariant division

想要在 mix 算法中应用 polyvariant 有两种思路:

  1. 在 mix 中加入 polyvariant division 的使用逻辑, 书中的做法是给原有的由 (pp, vs) (subject program point 和 static value 组成的列表) 所表示的 specialized program point 再加上一个 division component – (pp, vs, div), 以表示这个 program point 是根据具体 哪个 来 division 来 specialize 的. 不仅如此, 如何选取 specialized program point 也有讲究, 不能直接像初版的 mix 一样直接把一个 program point 的后继加入到 pending 里了, 要根据当前点的 divison 来决定后继节点和后继节点相应的 divisions.
  2. 通过 polyvariant division 先对程序进行一次变换, 得到一个有 monovariant division 的程序.

Self-Application 成功的关键

刚刚提到了 mix 程序是具有通过 self-application 得到编译器的能力的, 但是如果我们简单的把写好的 mix 传给 mix 我们是得不到刚刚图示的编译器的, 虽然可以得到一个"正确"的编译器(只要 mix 程序的实现是正确的, 那么二村映射的含义也一定是正确的), 但这个编译器会有很多的问题, 图示的 mix 函数在背后把这些问题"偷偷"解决了, 只把最直观优雅的东西写了出来, 比如说以下内容, 图示算法没有显式的考虑:

  1. 假设 division 已知, 而对于 mix 这样一个复杂的程序, division 的分析并不容易.
  2. 一些 base function 有些过于强大了, 它们到底是什么? 我们应该把哪些东西作为 base function, 把哪些东西自己把实现写到 subject program 中.
  3. 简单的 binding time analysis 所得到的 static variable 太少; 仅仅由相合性得到的 division, 有很多静态信息没有利用到.
  4. (pp, static value)序对有很多, 这会在 residual program 中生成超多的跳转标签(远多余图示的生成的编译器).

这里仅仅介绍个人觉得比较有趣的第 3 点, 如何通过 Bound Static Variation 更多的静态信息(相比与仅满足相合性的程序而言).

对于其他技巧, 请参考 Partial Evaluation教材 的 4.8 The tricks under the carpet.

Bound Static Variation(“The Trick”)

我们在 specialize 一个程序的时候, 通常会遇到一个问题: 程序中一个变量的值依赖于动态的输入, 但是其范围是已知的.

比如说如下程序:

x = input()
array = [1,2,3]
t = mod(x, 3)
y = array[t]

我们希望对其进行 specialization, x 的值显然是 Dynamic, array 的值显然是 Static, 那 t 的值依赖于 x, 所以按照相合性, t 必须被标记为 dynamic.

但是与一般的 Dynamic 不同, 我们并不是完全不知道 y 的取值的, 这里 y 只能取 1,2,3 三种值.

对于这种 值无法确定(Static), 但是取值范围可以确定(Static) 的值, 我们可以通过一个程序变换, 在变换中直接将这个值消除掉, 从而利用 取值范围有限 这一静态信息.

x = input()
array = [1,2,3]
y = case t of
  | 1 -> array[1]
  | 2 -> array[2]
  | 3 -> array[3]

(其实也就是为每个可能的取值生成一个 case 啦)