论文标题
线性时间
lospre in linear time
论文作者
论文摘要
终生最佳的投机性部分冗余消除（Lospre）是当前最先进的冗余消除技术。它涵盖了许多先前已知的方法，例如常见的子表达消除，全局常见的子表达消除和循环不变的代码运动。但是，以前已知的散鼠算法具有较高的时间复杂性。更快但强大的方法已被使用并进一步开发。我们为结构化程序提供了一种简单的线性时间算法，该算法与以前的方法相比也可以处理一些更一般的方案。我们证明我们的方法是最佳的，并且运行时在控制流图中的节点数中是线性的。对于许多编程语言而言，构造程序的条件自动呈正确，例如C，等同于a限制的每个功能的Goto标签数量。主流C编译器中的实施证明了我们方法的实际可行性。我们的方法基于图形结构理论，并使用树分解。我们还表明，对于结构化程序，可以通过$ O（n^{2.5}）$界定先前已知的MC-PRE和MC-SSAPRE算法的确定性实现时间，从而改善了$ O（N^3）$的先前范围。
Lifetime-optimal speculative partial redundancy elimination (lospre) is the most advanced currently known redundancy elimination technique. It subsumes many previously known approaches, such as common subexpression elimination, global common subexpression elimination, and loop-invariant code motion. However, 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 automatically 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. Our approach is based on graph-structure theory and uses tree-decompositions. We also show that, for structured programs, the runtime of deterministic implementations of the previously known MC-PRE and MC-SSAPRE algorithms can be bounded by $O(n^{2.5})$, improving the previous bounds of $O(n^3)$.
