AS imple, Fast Dominance Algorithm
AS imple, Fast Dominance Algorithm
复制标题
ASimple，快速优势算法
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
K. Kennedy
中科院分区：
文献类型：
--
作者：
K. Cooper;Timothy J. Harvey;K. Kennedy
在控制流图中寻找支配者的问题在文献中有很长的历史。原来的算法遭受了一个大的渐近复杂性，但很容易理解。随后的工作改进了时限，但总体上牺牲了执行的简单性和容易性。本文返回到一个简单的制定优势作为一个全球性的数据流问题。对自然界占主导地位的一些见解导致O（N 2）算法的实现，在实践中，它比经典的Lengauer-Tarjan算法运行得更快，后者的时间界限为O（E log（N））。我们比较的算法Lengauer-Tarjan，因为它是最有名的和最广泛使用的快速算法的优势。从相同的实现和观察中，我们还重新派生（来自Ferrante等人关于控制依赖的早期工作）一种计算优势前沿的方法，我们表明该方法比Cytron等人的原始算法更快。本文的目的不是提出一种新的算法，而是，基于经验证据提出一个论点，即具有令人沮丧的渐近复杂性的算法在实践中可以比那些更常用的算法更快。我们表明，在某些情况下，精心设计的简单算法可以克服理论上的优势，即使当问题超出现实的大小。此外，我们认为，这里提出的算法是直观的，易于实现，使他们成为优秀的教学工具。
Th ep roblem of finding the dominators in a control-flow graph has a long history in the literature. The original algorithms suffered from a large asymptotic complexity but were easy to understand. Subsequent work improved the time bound, but generally sacrificed both simplicity and ease of implementation. This paper returns to a simple formulation of dominance as a global data-flow problem. Some insights into the natur eo f dominance lead to an implementation of an O(N 2 )a lgorithm that runs faster, in practice, than the classic Lengauer-Tarjan algorithm, which has a timebound of O(E ∗ log(N )). We compare the algorithm to Lengauer-Tarjan because it is the best known and most widely used of the fast algorithms for dominance. Working from the same implementatio ni nsights, we also rederive (from earlier work on control dependence by Ferrante, et al. )a method for calculating dominance frontiers that we show is faster than the original algorithm by Cytron, et al. The aim of this paper is not to present a new algorithm, but, rather, to make an argument based on empirical evidence that algorithms with discouraging asymptotic complexities can be faster in practice than those more commonly employed. We show that, in some cases, careful engineering of simple algorithms can overcome theoretical advantages, even when problems grow beyond realistic sizes. Further, we argue that the algorithms presented herein are intuitive and easily implemented, making them excellent teaching tools.