A linear time algorithm for placing φ-nodes
A linear time algorithm for placing φ-nodes
复制标题
放置 φ 节点的线性时间算法
DOI：
10.1145/199448.199464
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
G. Gao
中科院分区：
文献类型：
--
作者：
V. Sreedhar;G. Gao
基于静态单分配（SSA）形式和稀疏评估图（SEG）的数据流分析框架要求对必须合并数据流信息的程序点的快速计算。用于计算＆fgr;的简单算法，用于在线性时间内运行的任意流程图（可还原或不可还原）。合并”数据流信息。
算法已经实现，结果与Cytron等人的众所周知的算法进行了比较。较高的梯子图并确认了我们算法的线性时间复杂性。
Dataflow analysis framework based on Static Single Assignment (SSA) form and Sparse Evaluation Graphs (SEGs) demand fast computation of program points where data flow information must be merged, the so-called &fgr;-nodes. In this paper, we present a surprisingly simple algorithm for computing &fgr;-nodes for arbitrary flowgraphs (reducible or irreducible) that runs in linear time. We employ a novel program representation—the DJ graph—by augmenting the dominator tree of a flowgraph with edges which may lead to a potential “merge” of dataflow information. In searching for &fgr;-nodes we never visit an edge in the DJ-graph more than once by guiding the search of nodes by their levels in the dominator tree.
The algorithm has been implemented and the results are compared with the well known algorithm due to Cytron et al. A consistent and significant speedup has been observed over a range of 46 Fortran procedures taken from a number of benchmark programs. We also ran experiments on increasingly taller ladder graphs and confirmed the linear time complexity of our algorithm.