On loops, dominators, and dominance frontier
On loops, dominators, and dominance frontier
复制标题
关于循环、支配者和支配边界
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Ganesan Ramalingam
中科院分区：
文献类型：
--
作者：
Ganesan Ramalingam
本文以构建图的支配树问题以及计算图中一组顶点的迭代支配前沿问题为导向性应用，探讨了控制流图的循环和循环嵌套森林的概念。本文的贡献包括：（1）对一系列循环嵌套森林进行了公理化特征描述以及构造性特征描述，其中包含了先前已定义的各种特定的循环嵌套森林。（2）定义了一种新的循环嵌套森林，以及一种高效的、近似线性时间的构建该森林的算法。（3）举例说明了在（a）构建图的支配树和（b）计算图中一组顶点的迭代支配前沿这两个问题的情况下，循环嵌套森林如何可用于将任意（可能不可约）的问题实例转换为等价的无环图问题实例，从而为这些问题引出了新的、近似线性时间的算法。
This article explores the concept of loops and loop nesting forests of control-flow graphs, using the problem of constructing the dominator tree of a graph and the problem of computing the iterated dominance frontier of a set of vertices in a graph as guiding applications. The contributions of this article include: (1) An axiomatic characterization, as well as a constructive characterization, of a family of loop nesting forests that includes various specific loop nesting forests that have been previously defined. (2) The definition of a new loop nesting forest, as well as an efficient, almost linear-time, algorithm for constructing this forest. (3) An illustration of how loop nesting forests can be used to transform arbitrary (potentially irreducible) problem instances into equivalent acylic graph problem instances in the case of the two problems of (a) constructing the dominator tree of a graph, and (b) computing the iterated dominance frontier of a set of vertices in a graph, leading to new, almost linear-time, algorithms for these problems.