phi nodes in linear time

The following paper is available from our ftp site
wally.cs.mcgill.ca (132.206.3.30):pub/doc/papers/POPL95.ps.gz


"A Linear Time Algorithm for Placing Phi-Nodes"
      by Vugranam Sreedhar and Guang Gao


This paper was presented at the ACM Symposium on Principles
of Programming Languanges, 1995.


Sreedhar


============


Abstract:


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 {\bf $\phi$-nodes}.
In this paper, we present a surprisingly simple algorithm for
computing $\phi$-nodes for arbitrary flowgraphs (reducible
or irreducible) that runs in {\em linear} time. We employ
a novel program representation --- the {\bf 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 \mbox{$\phi$-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.~\cite{CytronEtAl91}. 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.




--

Return to the comp.compilers page.
Search the comp.compilers archives again.