algorithm - 内联算法

Question

有谁知道任何论文讨论内联算法？和密切相关的，父子图与调用图的关系。

背景:我有一个用 Ocaml 编写的编译器它积极地内联函数，主要是由于这一点和其他一些优化，它在许多情况下为我的编程语言生成比大多数其他语言更快的代码(甚至包括 C )。

问题#1:该算法在递归方面存在问题。为此，我的规则只是将子项内联到父项中，以防止无限递归，但这排除了兄弟函数相互内联一次。

问题#2:我不知道优化内联操作的简单方法。我的算法对于函数体的可变表示是必不可少的，因为它似乎甚至不可能制定有效的函数内联算法。如果调用图是一棵树，很明显自下而上的内联是最佳的。

技术资料:内联由许多内联步骤组成。问题是步骤的顺序。

每个步骤的工作原理如下:

我们制作了一个要内联和 beta-reduce 的函数的副本
用参数替换类型参数和值参数。

然后我们用对新变量的赋值替换 return 语句
然后跳转到函数体的末尾。

然后，对该函数的原始调用被此主体替换。

然而我们还没有完成。我们还必须克隆所有的 child
函数，也减少了它们，并将克隆重新设置为
调用函数。

克隆操作使得内联递归函数变得极其困难。保留已经在进行中的内容的列表并只是检查我们是否已经在处理这个调用的常用技巧并不能以天真的形式工作，因为递归调用现在被移到了被填充到调用中的减少测试版的代码中函数，并且递归目标可能已更改为克隆子对象。然而，在调用父级时，该子级仍在调用调用其子级的原始父级，现在递归的展开不会停止。如前所述，我通过只允许内联对子级的递归调用来打破这种回归，防止内联同级递归。

由于需要 garbage collect，内联的成本进一步复杂化。未使用的功能。由于内联可能是指数级的，因此这是必不可少的。如果对一个函数的所有调用都被内联了，那么如果该函数还没有被内联，我们应该删除它，否则我们将浪费时间内联到一个不再使用的函数中。实际上跟踪谁调用了什么是极其困难的，因为内联时我们不是在处理实际的函数表示，而是在“解开”的表示:例如，指令列表正在按顺序处理并建立一个新列表，并且在任何一个时间点都可能没有一致的指令列表。

在他的 ML 编译器 Steven Weeks 中，选择使用一些重复应用的小优化，因为这使得优化易于编写和控制，但不幸的是，与递归算法相比，这错过了很多优化机会。

问题 #3:什么时候内联函数调用是安全的？

笼统地解释这个问题:在惰性函数式语言中，参数被包装在闭包中，然后我们可以内联应用程序；这是 Haskell 的标准模型。然而它也解释了为什么 Haskell太慢了。如果参数已知，则不需要闭包，然后可以直接用它的参数替换该参数，其中 is 出现(这是正常顺序 beta-reduction )。

但是，如果知道参数评估不是非终止的，则可以使用预先评估:参数被分配一次表达式的值，然后重用。这两种技术的混合是使用闭包但将结果缓存在闭包对象中。尽管如此，GHC 还没有成功地生成非常高效的代码:这显然非常困难，尤其是在您进行单独编译的情况下。

在 Felix，我采取了相反的方法。我没有通过证明优化保留语义来要求正确性和逐步提高效率，而是要求优化 定义 语义。这保证了优化器的正确操作，但代价是某些代码将如何表现的不确定性。这个想法是为程序员提供方法，如果默认优化策略过于激进，则可以强制优化器符合预期的语义。

例如，默认的参数传递模式允许编译器选择是将参数包装在闭包中，用参数替换参数，还是将参数分配给参数。如果程序员想要强制关闭，他们可以只传入一个关闭。如果程序员想强制急切求值，他们会标记参数 var .

这里的复杂性远大于函数式编程语言:Felix 是一种带有变量和指针的过程语言。它还具有 Haskell 风格的类型类。这使得内联例程极其复杂，例如，类型类实例尽可能替换抽象函数(由于调用多态函数时的类型特化，内联时可能会找到一个实例，所以现在我们有了一个新函数可以内联)。

为了清楚起见，我必须添加更多注释。

内联和其他一些优化，例如用户定义的术语缩减、类型类实例化、用于变量消除的线性数据流检查、尾部记录优化，都是在给定函数上一次性完成的。

排序问题不是应用不同优化的顺序，问题是对函数进行排序。

我使用脑死算法来检测递归:我建立一个由 each 函数直接使用的所有内容的列表，找到闭包，然后检查该函数是否在结果中。请注意，在优化过程中多次建立使用集，这是一个严重的瓶颈。

不幸的是，函数是否是递归的可能会发生变化。递归函数可能在尾 rec 优化后变为非递归函数。但是有一个更困难的情况:实例化一个类型类的“虚拟”函数可以使看起来是非递归的递归。

至于兄弟调用，问题是给定 f 和 g 其中 f 调用 g 和 g 调用 f 我实际上想将 f 内联到 g 中，将 g 内联到 f .. 一次。我的无限回归停止规则是，如果 f 是 g 的子级，则仅允许将 f 内联到 g 中，如果它们相互递归，则不包括内联 sibling 。

基本上我想“尽可能地”“扁平化”所有代码。

Answer 1

我意识到您可能已经知道所有这些，但仍然完整地写它似乎很重要，至少是为了进一步引用。

在功能社区中，有一些文献主要来自 GHC 人。请注意，他们将内联视为源语言中的一种转换，而您似乎在较低级别上工作。我相信，使用源语言或语义相当相似的中间语言对简单性和正确性有很大帮助。

GHC Wiki : Inlining (包含引用书目)

Secrets of the Glasgow Haskell inliner

对于排序编译器传递的问题，这很神秘。仍然在 Haskell 设置中，还有 Compilation by Transformation in a Non-strict Functional Language博士论文讨论了不同编译器传递(以及内联)的顺序。

还有一篇关于 Compilation by Equality Saturation 的最新论文。它提出了一种优化传递排序的新方法。我不确定它是否已经证明了大规模的适用性，但它肯定是一个有趣的探索方向。