有谁知道任何讨论内联算法的论文？和密切相关的是，父子图与调用图的关系。
背景：我编写了一个编译器，Ocaml其中积极地内联函数，主要是由于这个和其他一些优化，它为我的编程语言在许多情况下（包括甚至C）生成比大多数其他语言更快的代码。
问题 #1：该算法在递归方面存在问题。为此，我的规则只是将孩子内联到父母中，以防止无限递归，但这排除了兄弟函数相互内联一次。
问题 #2：我不知道优化内联操作的简单方法。我的算法对于函数体的可变表示是必不可少的，因为似乎根本不可能做出有效的函数内联算法。如果调用图是一棵树，很明显自下而上的内联是最佳的。
技术信息：内联由许多内联步骤组成。问题是步骤的顺序。
每个步骤的工作原理如下：
- 我们通过用实参替换类型参数和值参数来制作要内联和 beta-reduce 的函数的副本。
- 然后，我们将 return 语句替换为对新变量的赋值，然后跳转到函数体的末尾。
- 然后，对该函数的原始调用将被此主体替换。
- 然而我们还没有完成。我们还必须克隆该函数的所有子函数，同时对它们进行 beta 缩减，并将克隆重新作为调用函数的父级。
克隆操作使得内联递归函数变得极其困难。保留已在进行中的内容的列表并仅检查我们是否已经在处理此调用的常用技巧在幼稚的形式中不起作用，因为递归调用现在被移动到被填充到调用中的 beta-reduced 代码函数，并且递归目标可能已更改为克隆的孩子。然而，在调用父级时，子级仍在调用调用其子级的原始父级，现在递归的展开不会停止。如前所述，我打破了这种回归，只允许内联对孩子的递归调用，防止兄弟递归被内联。
由于需要garbage collect未使用的函数，内联的成本变得更加复杂。由于内联可能是指数级的，因此这是必不可少的。如果对一个函数的所有调用都是内联的，如果该函数还没有被内联，我们应该删除它，否则我们将浪费时间内联到一个不再使用的函数。实际上跟踪谁调用了什么是极其困难的，因为当内联时，我们不是在使用实际的函数表示，而是一个“未分解”的表示：例如，指令列表正在按顺序处理并建立一个新列表，并且在任何一个时间点都可能没有一个连贯的指令列表。
在他的 ML 编译器中，Steven Weeks 选择使用一些重复应用的小优化，因为这使得优化易于编写和控制，但不幸的是，与递归算法相比，这错过了很多优化机会。
问题 #3：什么时候内联函数调用是安全的？
笼统地解释这个问题：在惰性函数式语言中，参数被包装在闭包中，然后我们可以内联应用程序；这是 Haskell 的标准模型。然而，它也解释了为什么Haskell这么慢。如果参数已知，则不需要闭包，则可以直接将参数替换为其参数 where is 出现（这是正常顺序beta-reduction）。
但是，如果已知参数评估不是非终止的，则可以使用急切评估：为参数分配一次表达式的值，然后重用。这两种技术的混合是使用闭包，但将结果缓存在闭包对象中。尽管如此，GHC 还没有成功地生成非常高效的代码：这显然非常困难，尤其是在您进行单独编译的情况下。
在菲利克斯，我采取了相反的方法。我不是通过证明优化保留语义来要求正确性并逐渐提高效率，而是要求优化定义语义。这保证了优化器的正确操作，但代价是某些代码将如何表现的不确定性。这个想法是为程序员提供方法来强制优化器在默认优化策略过于激进的情况下符合预期的语义。
例如，默认的参数传递模式允许编译器选择是否将参数包装在闭包中，用参数替换参数，或者将参数分配给参数。如果程序员想要强制闭包，他们可以传入一个闭包。如果程序员想要强制进行急切评估，他们会标记参数var。
这里的复杂性远大于函数式编程语言：Felix 是一种带有变量和指针的过程语言。它也有 Haskell 风格的类型类。这使得内联例程极其复杂，例如，类型类实例尽可能替换抽象函数（由于调用多态函数时的类型特化，可能在内联时找到实例，所以现在我们有了一个新函数可以内联）。
为了清楚起见，我必须添加更多注释。
内联和其他一些优化，例如用户定义的术语减少、类型类实例化、用于变量消除的线性数据流检查、尾部记录优化，都是在给定函数上一次性完成的。
排序问题不是应用不同优化的顺序，问题是对函数进行排序。
我使用一种脑死亡算法来检测递归：我建立一个每个函数直接使用的所有内容的列表，找到闭包，然后检查函数是否在结果中。请注意，在优化过程中会多次建立使用集，这是一个严重的瓶颈。
不幸的是，函数是否递归可能会发生变化。递归函数可能在尾部记录优化后变为非递归函数。但是有一个更难的情况：实例化一个类型类的“虚拟”函数可以使看起来是非递归的递归。
至于兄弟调用，问题是给定 f 和 g 其中 f 调用 g 和 g 调用 f 我实际上想将 f 内联到 g 中，并将 g 内联到 f .. 一次。我的无限回归停止规则是，如果 f 是 g 的孩子，则只允许将 f 内联到 g 中，这不包括内联兄弟。
基本上我想“尽可能地”“扁平化”所有代码。