lospre in linear time
lospre in linear time
复制标题
以线性时间开始
DOI：
10.1145/3493229.3493304
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Philipp K. Krause
中科院分区：
文献类型：
--
作者：
Philipp K. Krause
寿命最优推测部分冗余消除（lospre）是目前已知的最先进的冗余消除技术。它包含了许多以前的方法，如公共子表达式消除，全球公共子表达式消除，循环不变的代码运动。以前已知的lospre算法具有高的时间复杂度，更快，但功能不太强大的方法已被使用和进一步开发。我们提出了一个简单的线性时间算法lospre结构化的程序，也可以处理一些更一般的情况下相比，以前的方法。我们证明了我们的方法是最佳的，运行时间是线性的控制流图中的节点数。程序结构化的条件对于许多编程语言都是成立的，而对于其他编程语言（如C），则等价于每个函数的后藤标签数量的限制。在一个主流的C编译器的实现证明了我们的方法，这是基于图结构理论和使用树分解的实际可行性。对于结构化程序，我们还提高了运行时的确定性实现的MC-PRE和MC-SSAPRE算法从O（n3）到O（n2.5）。
Lifetime-optimal speculative partial redundancy elimination (lospre) is the most advanced currently known redundancy elimination technique. It subsumes many previous approaches, such as common subexpression elimination, global common subexpression elimination, and loop-invariant code motion. Previously known lospre algorithms have high time complexity; faster but less powerful approaches have been used and developed further instead. We present a simple linear-time algorithm for lospre for structured programs that can also handle some more general scenarios compared to previous approaches. We prove that our approach is optimal and that the runtime is linear in the number of nodes in the control-flow graph. The condition on programs of being structured is true for many programming languages and for others, such as C, is equivalent to a bound on the number of goto labels per function. An implementation in a mainstream C compiler demonstrates the practical feasibility of our approach, which is based on graph-structure theory and uses tree-decompositions. For structured programs, we also improve the runtime bound of deterministic implementations of the previously known MC-PRE and MC-SSAPRE algorithms from O(n3) to O(n2.5).
登录
查看更多内容
DOI：
10.1093/comjnl/19.1.43
发表时间：
1976
期刊：
Comput. J.
影响因子：
--
作者：
H. Curnow;B. Wichmann
通讯作者：
H. Curnow;B. Wichmann
固定数量寄存器的线性时间寄存器分配
DOI：
--
发表时间：
1998
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
H. Bodlaender;J. Gustedt;J. A. Telle
通讯作者：
J. A. Telle
编译器剖析
DOI：
--
发表时间：
2011
期刊：
影响因子：
--
作者：
Julie Zelenski
通讯作者：
Julie Zelenski
DOI：
--
发表时间：
2004
期刊：
SIGP
影响因子：
--
作者：
Rastislav Bodík;R. Gupta;M. Soffa
通讯作者：
M. Soffa
影响因子：
1
作者：
COURCELLE, B
通讯作者：
COURCELLE, B