phi nodes in linear time

Wed, 22 Feb 1995 12:26:59 GMT

          From comp.compilers

Related articles
phi nodes in linear time (V.C. SREEDHAR) (1995-02-22)
| List of all articles for this month |

Newsgroups: comp.compilers
From: "V.C. SREEDHAR" <>
Keywords: dataflow, FTP, report, available, analysis
Organization: Compilers Central
Date: Wed, 22 Feb 1995 12:26:59 GMT

The following paper is available from our ftp site (

"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.




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.


Post a followup to this message

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