类型化中间语言的实用语义学

Question

编译器的一个趋势是使用类型化中间语言。Haskell的ghc使用其core中间语言（System F-omega的变体）作为该架构的实例[1]。另一个例子是LLVM，其核心是一种类型化的中间语言[2]。采用这种方法的好处在于可以早期检测代码生成器中组成部分的转换中的错误。此外，在优化和代码生成过程中还可以使用类型信息。

为了提高效率，类型化IR需要进行类型检查，而不是通过推断来确定其类型。为了使类型检查快速进行，每个变量和每个绑定器都携带着类型以便进行轻松的类型检查。

然而，编译器流水线中的许多转换可能会引入新的变量。例如，规范化转换K(.)可能会转换应用程序。

M(N)

转换为类似的表达式

let x = K(M) in
let y = K(N) in x(y)

问题. 我想知道编译器如何处理给新引入的变量赋类型的问题。它们是否重新进行类型检查，在上面的示例中 K(M) 和 K(N)？这不是很耗时吗？它是否需要传递环境？它们是否使用从AST节点到类型信息的映射来避免重新运行类型检查？

---

1. S. Marlow, S. Peyton Jones，《Glasgow Haskell Compiler》。

2. LLVM语言参考手册。

- Martin Berger

---

"A-normal form"可能是相关的。 - Basile Starynkevitch

@BasileStarynkevitch 谢谢。A-正常形式很重要，但是有没有一种理论可以有效地对A-正常形式进行类型检查/类型推断呢？ - Martin Berger

我采用的方法是在转换之后重新运行类型推导，而不是忠实地保留所有类型信息。一些转换可能会完全去掉类型（只要它们可以恢复）。在像IR这样简单的东西上进行类型传播远远不是最可能导致性能瓶颈的因素。 - SK-logic

@MartinBerger，我更喜欢将一切保存在可读（且可序列化）的IR中。例如，在类似于LLVM的IR中，我将黏性类型与alloca节点、函数参数和全局变量声明一起保存。其余部分始终可以重建。为了方便，在转换之间，我还将类型附加到GEP节点上，但是如果存在可以引入新GEP的转换，则会重新运行类型传播。 - SK-logic

@MartinBerger，我正在为输入更高级别的IR（例如使用具有唯一变量名称的枚举表达式节点，然后针对这些自由变量解决类型方程）而努力。但是对于高度不稳定的低级别IR，情况有些混乱，很容易引入新的节点或重写现有节点而不更新映射关系。将所有内容保持在单个可读和可序列化的AST中会大有帮助。 - SK-logic

Answer 1

在上面的例子中，他们会重新进行类型检查吗？

K（M）

K

M

K

M

K（M）

K

K（N）

K

N

K（N）

K（M）

x（y）

x

y

x

y

x

x（y）

x

K

这不是非常耗时吗？

它是否需要在环境之间传递？他们是否使用AST节点到类型信息的映射来避免重新运行类型检查？

- Spacewink