Sea-of-nodes 论文阅读笔记

Posted on Sep 13, 2022

A Simple Graph-Based Intermediate Representation 论文地址。这是 Sea-of-nodes IR 提出者 Cliff Click 的论文,之前“意识流学” V8 的时候,一直搞不明白 sea of nodes 的思想是什么,也尝试的找了很多资料想学习,但是感觉确实是没看明白。今天,我们通过看论文来学习。论文不难懂,很建议看看论文学习,这篇文章只是我自己的简单总结。

注:下面的图片都是截取自论文

目前我看到 C++ 实现一章之前,之后我有打算把 Sea-of-nodes 生成整合到我的 toy 编译器上,但是现在只是为了阐明 IR 的设计,我们先不考虑那么多具体的实现。

在我看来,Sea-of-nodes IR 是一个单向图。这样做的主要特点就是去除了传统 IR 的 CFG 和 Basic Blocks 两层,将 IR 成一层单独的图,可以使优化变得更容易:修改 IR 只要添加/减少节点,添加/减少边的连接就可以了。同时 IR 中的边是“unlabelled”的,也就是说每条边的本质只是一根指向后继的指针,这样也可以大幅增加分析时的性能(用作者原话就是 “fit in L1 cache”)。构建出的图,也可以(隐式地)一分为二成控制流图和数据流图。

同时我还认为,Sea-of-nodes 的目的是用一种更有利于优化的数据结构来表示程序的控制流和数据流信息。所以在之后可以看到,IR 的设计都是为了既满足简单,即所有的边都是 unlabelled 的,又能够拥有传统 IR 的表达能力的(甚至可能在某些方面有更强的表达能力)。

图的设计

首先 Sea-of-nodes 是 SSA 形式的。IR 的图是一个有向图,图中的节点称为 Nodes,节点是有 label 的,对于原语类操作,比如加法原语,就会带一个 $Add$ label。我们用 node.opcode 来表示这个 $Add$ 操作。

每个节点的输入是有序的,输出是无序的,很好理解:比如对于减法操作,减数和被减数自然不能混淆方向,输入需要有序。而由于 IR 是 SSA 的,输出是一个可以被任何 nodes 使用的 value(也可能不是 value,而是 CONTROL 等别的信息),不需要有顺序。同时每个节点的输入数量都是固定的,而输出的数量则不限。而且在实现时,对于每个 node 其实只会维护输入,不会维护自身的输出。输入使用一个指针数组即可维护,比如对于上图中的 $b$,作为 $a$ 的第一个输入,就可以记作 $a[0]$。也就是 $a[0] \equiv b,\ a[1] \equiv c, \ a.opcode \equiv Add$ 。

Region Node

在 Sea-of-nodes 中,丢失了传统 IR 的 CFG + Basic Blocks 的双层表示。在原来的双层表示下,CFG 用来描述控制流,Basic Blocks 用来描述数据流。为了在 Sea-of-nodes 下也有同样的能力,在 IR 中添加了 Region Node 这样特殊的 nodes,

Region Node 会接受带有 CONTROL 信息的入边,并且将 CONTROL 信息传出。注意到图中 Add 节点接受了一个 Region Node 发出的 CONTROL 边,代表这个原语操作处于这个基本块中。不过实际上这条 CONTROL 边不是必须的(考虑到 IR 是 SSA 的,Add 接受的输入必然是正确的 b 和 c 的值,所以 Add 只要在 input 节点后执行就行了,并不是一定要在 Region node 这个基本块中执行),将这条边移除可以进行更多的全局优化,但是也会给之后序列化执行流造成难度。这类可以去除的边在论文配图中用虚线来表示。

Phi Node

SSA 形式的 IR 一般都需要用 $\phi$-functions 来处理一些特殊情况,比如

int a;
if (some-condition) {
	a = 1;
} else {
	a = 0;
}

这种时候在 if 后就会出现两个不同的值汇聚到一个标识符的情况,SSA 不允许重复赋值,就需要引入 $\phi$-functions 来代表标识符会从多个可能的值中选出一个。在 Sea-of-nodes 中,Phi Node 就承担了 $\phi$-functions 的功能。不过我们可以看到,$\phi$-functions 不仅仅需要将数据作为输入,还需要对应的控制流来选择正确的数据,这样就需要将 Phi Node 的输入边设计成 CONTROL 和 value 信息的 pair 了,这样破坏掉 IR 的简单性。所以我们选择使用 Region Node 来辅助 Phi Node,如下图

Region Node 有和 Phi Node 对齐的输入,而 Region Node 会根据 B1 和 B2 的 CONTROL 输入而输出对应的 CONTROL 信息,这样 Phi Node 就可以选出正确的输入,从而输出正确的值。

和传统 SSA IR 一样,Phi Nodes 只存在于 IR 中,并不会生成对应的 machine code。

If Node and Projections

在 Sea-of-nodes 中,if 条件分支被替换成了 If 节点,他会接受 CONTROL 输入和 predicate,也就是判断的谓词(语法我一点都不懂,所谓谓词其实就是一个判断,类似于 a == b 这样)。实际上这里应该是接受 predicate 求解后的值。如果值为 True 就输出 True,否则输出 False 给后继的 Region Node,让一个新的“基本块”得以执行。

不过很重要的是,我们看到上面的 If Node 的 output edge 是带 True 和 False 的信息的,也就是 labeled 的。If 只会输出 True 和 False 两种信息,但是还有很多操作会输出多种信息,比如子方法调用,会有更多的不同种类的输出,如果对这些 node 都加上 label 来辨明是什么类型的输出的话,就会对性能和简单性有很大的负面影响。所以我们会让每一条 output edge 都带有同样的信息,也就是带有同样的 tuple,包含了所有输出结果。然后通过一个 projection node 来选出我们想要的特定信息,也就是下图所表示的。

记 If 的输出为 {true : 0, false : 1} 这样的 tuple,Projection True node 只会从 If 的输出中裁出 true 的 0,Projection False node 只会裁出 false 的 1,然后传到 Region Node 中。

Memory and I/O

对于 Memory 操作,其实只有两种,Store 和 Load,Store 操作向内存中写入,Load 操作从内存中读取。在 IR 中,内存相关的操作也就是由 Store Node 和 Load Node 两种节点完成的。

思考 Store 和 Load 的操作的顺序应当如何组织,在最开始,为了简单,我们把 Memory 当作一个特殊的 Value,和其他的寄存器这样的值一样(也就是把两个实际上写入区域不重叠的 Store 操作当作是重叠的)

  • 对于 Store-Load-Store 这样的操作,两个 Store 的顺序不能调换,不然就会影响 Load 出来的值的准确性
  • 对于 Store-Load-Load 这样的操作,两个 Load 的顺序并不重要
  • 对于 Load-Store-Load 这样的操作,两个 Load 的顺序不能替换

所以最后的设计就是每个 Store Node 会产生一个 STORE 输出,每个 Load Node 都需要以一个 STORE 和一个地址作为输入。每个 Store Node 都需要以一个 STORE 和一个地址作为输入,同时以 STORE 作为输出。(这里的 STORE 可以理解为类似于 Region Node 的 CONTROL 的“信号”)

对于 I/O,如果是 memory-mapped I/O,那么就和 memory 的处理一样。否则就需要进行子方法调用。

上面说到的对 memory 抽象为一整块的 Value,过于粗粒度,更好的设计是将 Store 操作划为互不相关的 Store Node。

Execution Model

执行时,总体就是根据 CONTROL 信息的传递,来执行对应的“基本块”,或者说被 Region Node 围起来的子图。

下面是一个循环的 IR 表示

C++ Implementation

这里我只简述一下,论文中写的非常详细了

  • 每种 Node 都是一个独立的类,超基类是一个统一的 Node class,通过虚函数来实现不同的 node.opcode
  • 每种 Node 都可以继承自与自己相似的别的 Node 来实现代码复用,比如 AddNode -> IntAddNode 这样的继承关系
  • 在前面所说到的边,都是 $Def \rightarrow Use$,但是每个 Node 都是输入有限(并且往往可以提前预知)而输出无限(可能会在优化时随时增减)。所以实际实现时使用的是 $Use \rightarrow Def$ 边。也就是只维护 input,不维护 output。