论文标题
快速计算强控制依赖性
Fast Computation of Strong Control Dependencies
论文作者
论文摘要
我们介绍了用于计算非终止敏感控制依赖性（NTSCD）和决定性顺序依赖性（DOD）的新算法。控制流程图上的这些关系具有许多应用程序，包括程序切片和编译器优化。我们的算法比当前的算法更快。我们还表明，用于计算NTSCD和DOD的原始算法可能会产生不正确的结果。我们实施了NTSCD和DOD的原始算法的新版本和固定版本，并通过实验比较了它们的性能和结果。我们的算法极大地胜过原始算法。
We introduce new algorithms for computing non-termination sensitive control dependence (NTSCD) and decisive order dependence (DOD). These relations on control flow graph vertices have many applications including program slicing and compiler optimizations. Our algorithms are asymptotically faster than the current algorithms. We also show that the original algorithms for computing NTSCD and DOD may produce incorrect results. We implemented the new as well as fixed versions of the original algorithms for the computation of NTSCD and DOD and we experimentally compare their performance and outcome. Our algorithms dramatically outperform the original ones.
