Ytt*_*ill 5 algorithm ocaml compiler-theory compiler-optimization graph-algorithm
有没有人知道任何论文讨论内联算法？并且密切相关,父子图与调用图的关系.
背景:我编写了一个编译器,Ocaml其中积极地内联函数,主要是由于这个和其他一些优化,它为我的编程语言生成比许多其他情况(包括偶数C)更快的代码.
问题#1:算法在递归时遇到问题.为此,我的规则只是将子项内联到父项中,以防止无限递归,但这会阻止兄弟函数一次性内联.
问题2:我不知道优化内联操作的简单方法.我的算法对于函数体的可变表示是势在必行的,因为它甚至不可能实现有效的函数内联算法.如果调用图是一棵树,很明显自下而上的内联是最佳的.
技术信息:内联包含许多内联步骤.问题是步骤的顺序.
每个步骤的工作原理如下:
克隆操作使得内联递归函数变得非常困难.保持已经在进行中的列表并且只是检查我们是否已经处理此调用的常用技巧不能以天真的形式工作,因为递归调用现在被转移到调整后的代码中.函数,递归目标可能已更改为克隆的子项.但是,该子进程在调用父进程时仍在调用调用其子进程的原始父进程,现在不会停止展开递归.如上所述,我通过仅允许对孩子进行递归调用来打破此回归,从而防止内联的兄弟递归.
由于需要garbage collect使用未使用的功能,因此内联成本更加复杂.由于内联可能具有指数性,因此这是必不可少的.如果对函数的所有调用都是内联的,那么如果尚未内联函数,我们应该删除该函数,否则我们将浪费时间内联到一个不再使用的函数中.实际上跟踪谁调用极其困难的东西,因为在内联时我们不使用实际的函数表示,而是"解开"的表示:例如,正在按顺序处理指令列表并构建新列表,并且在任何一个时间点可能没有连贯的指令列表.
在他的ML编译器中,Steven Weeks选择使用多次重复应用的小优化,因为这使得优化易于编写且易于控制,但不幸的是,与递归算法相比,这错过了许多优化机会.
问题3:内联函数调用何时安全？
一般来说解释这个问题:在一个懒惰的函数式语言中,参数包含在闭包中,然后我们可以内联一个应用程序; 这是Haskell的标准模型.然而,它也解释了为什么Haskell这么慢.如果参数已知,则不需要闭包,那么参数可以直接替换其出现的参数(这是正常的顺序beta-reduction).
但是,如果已知参数评估不是非终止的,则可以使用急切评估:为参数分配表达式的值一次,然后重复使用.这两种技术的混合使用闭包但将结果缓存在闭包对象中.尽管如此,GHC还没有成功地生成非常高效的代码:显然非常困难,特别是如果你有单独的编译.
在菲利克斯,我采取了相反的方法.通过证明优化保留语义,而不是要求正确性并逐步提高效率,我要求优化定义语义.这保证了优化器的正确操作,但代价是不确定某些代码将如何表现.我们的想法是为程序员提供一些方法,以便在默认优化策略过于激进时强制优化器符合预期的语义.
例如,默认参数传递模式允许编译器选择是将参数包装在闭包中,用参数替换参数,还是将参数赋值给参数.如果程序员想要强制关闭,他们就可以传递一个闭包.如果程序员想要强制进行评估,他们会标记参数var.
这里的复杂性比函数式编程语言要大得多:Felix是一个带变量和指针的过程语言.它还有Haskell风格的类型.这使得内联例程极其复杂,例如,类型类实例尽可能替换抽象函数(由于在调用多态函数时类型特化,在内联时可能会找到一个实例,所以现在我们有了一个新函数可以内联).
为了清楚起见,我必须添加一些注释.
内联和其他一些优化,例如用户定义的术语缩减,类型类实例化,线性数据流检查变量消除,尾部rec优化,都是在给定函数上同时完成的.
排序问题不是应用不同优化的顺序,问题是订购功能.
我使用脑死算法来检测递归:我建立了每个函数直接使用的所有内容的列表,找到闭包,然后检查函数是否在结果中.请注意,在优化过程中,使用集会多次构建,这是一个严重的瓶颈.
函数是否递归可能会发生变化.尾部优化后,递归函数可能变为非递归.但是有一个更难的情况:实例化类型类"虚拟"函数可以使看似非递归的递归.
至于兄弟调用,问题是给定f和g,其中f调用g和g调用f我实际上想要将f内联到g中,并将g内联到f ..一次.我的无限回归停止规则是只允许将f内联到g如果它们是相互递归的,如果f是g的子,则不包括内联兄弟.
基本上我想"尽可能"地"平掉"所有代码.
我意识到你可能已经知道这一切,但是仍然完整地写它似乎很重要,至少为了进一步的参考.
在功能社区,有一些文学作品主要来自GHC人.请注意,他们认为内联作为源语言的转换,而您似乎在较低级别工作.我相信,使用源语言 - 或者是一种相当类似语义的中间语言 - 对简单性和正确性有很大帮助.
对于排序编译器传递的问题,这是非常神秘的.仍处于Haskell设置中的是非严格功能语言博士论文中的转换编译,该论文讨论了不同编译器传递(以及内联)的排序.
还有最近关于Compilation by Equality Saturation的论文提出了一种优化传递排序的新方法.我不确定它是否已经大规模地展示了适用性,但它确实是一个有趣的探索方向.