IR 竟然是......

When you're programming, it's amazing what a difference the choice of IR can make. I've often found that when something seems too hard, it's because I need to introduce a primary transformation into some form that makes the problem easier. Well, likewise, as we do research, we should think about the medium and tools we are using and make sure they're a good match for our goals. -- nikomatsakis

上面这段话是 nikomatsakis 在 PLWM 2022 上讲的，今天对这段话似乎有了一点理解，记录一下。

其实我对 IR (Intermidiate Representation) 的理解一直是模糊的。

编译器使用一些数据结构来表示它处理的代码，这种形式称为中间表示 -- 《编译器设计（第二版）》

              +----------------------------+
              |                            |
              |                            |
              |  +--------+ IR  +-------+  |
 source code  |  |frontend+---->|backend|  | target code
------------->|  +--------+     +-------+  +------------>
              |                            |
              |                            |
              |                    compiler|
              +----------------------------+

上图也出自《编译器设计（第二版）》，难道 IR 位于前端和后端之间，是一个层级？ dada 中有一个大的组件叫 dada-ir，它包含了非常多的东西，包括 token, syntax expr, syntax tree, validated expr, validated tree。。。我以前一直以为 IR 是一个层级，现在结合定义和 dada 来看，IR 是一个笼统，宽泛的概念，所有在编译过程中帮助表示源代码的数据结构都可以叫做 IR，它并不是一个层级，它可能是一些层级的输出结果。好吧，这还是太抽象了，感觉说的是个屁啊。。。

              +--------+             +--------+                  +-----------+                    +--------+          +-----------+
source code   |        |   tokens    |        |   syntax tree    |           |   validated tree   |        |    bir   |           |  output
------------> | Lexer  | ----------> | Parser |  --------------> | Validator |  ----------------> |Brewery | -------->| Executor  | --------->
              |        |             |        |                  |           |                    |        |          |           |
              +--------+             +--------+                  +-----------+                    +--------+          +-----------+

上图是 dada 编译的流程（其实不准确，dada 编译的数据流向并不是从左到右，参见 Implementing languages for fun and profit 笔记 ），图中的 token，syntax tree，validated tree，bir 都是 IR，它们是对源程序表示的不同形式。好吧，IR 并没有啥神秘的，也没有多高级，只是平时不会把 token，syntax tree 叫做 IR 罢了。

IR 是在编译过程中对源程序的中间表示，没有一个明确的规则或者规范约定如何设计这些数据结构，所以 IR 的设计很大程度依赖于开发者的经验和风格。现在就不难理解 nikomatsakis 所说的，设计合适的 IR 对编译器非常重要，引入某个新的 IR 可能会让问题变得非常简单，今天在看 dada 源码的时候，突然体会到了 dada 在某些 IR 设计上的精妙。Parser 并没有单纯生成树结构的 syntax tree，而是引入一个 Item 的 IR，这个 IR 包含 top-level 的定义，目前只有 class 和 function。引入这个 IR 让 name resolution 的过程变得更简单了，不需要去遍历 syntax tree 就可以得到某个文件定义了哪些 Function，哪些 class。

+----------+
| [Item]   |          +-------------+
|          |          | [Function]  |
| Class    |          |             |
| Function +--------> | name        |
+----------+          | effect      |
                      | parameters  |
                      | body        |
                      +-------------+
← 返回首页