A framework for generalized control dependence
A framework for generalized control dependence
复制标题
广义控制依赖的框架
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
K. Pingali
中科院分区：
文献类型：
--
作者：
G. Bilardi;K. Pingali
我们通过在控制流图g =（v，e）中的一组路径方面定义广义优势关系来概括主导地位的概念。这个新的定义导致了控制依赖性的广义概念，其中包括标准控制依赖性和弱控制依赖性作为特殊情况。鉴于这棵树，可以通过还原到罗马战车问题来最佳地计算相应的控制依赖关系，这是我们以前为计算标准控制依赖性而开发的。更准确地说，给定的线性预处理时间和空间，我们可以回答所谓的CD，CORDS和CDEEKEEV查询的（广义版本），与查询的输出成正比。为了说明框架的实用性，我们显示如何显示弱控制依赖性可以在O（| e |）预处理空间和时间中最佳计算。这可以改善此问题最佳先前算法所需的O（| V | 3）时间。
We generalize the notion of dominance by defining a generalized dominance relation with respect to a set of paths in the control flow graph G = (V, E). This new definition leads to a generalized notion of control dependence, which includes standard control dependence and weak control dependence as special cases.If the set of paths underlying a generalized dominance relation satisfies some natural closure conditions, that dominance relation is tree-structured. Given this tree, the corresponding control dependence relation can be computed optimally by reduction to the Roman Chariots Problem, which we have developed previously for computing standard control dependence. More precisely, given linear preprocessing time and space, we can answer the (generalized version of the) so called cd, conds, and cdequiv queries in time proportional to the output of the query.To illustrate the utility of the framework, we show how weak control dependence can be computed optimally in O(|E|) preprocessing space and time. This improves the O(|V|3) time required by the best previous algorithm for this problem.