# phi nodes in linear time

## "V.C. SREEDHAR" <sreedhar@bluebeard.cs.mcgill.ca>Wed, 22 Feb 1995 12:26:59 GMT

From comp.compilers

Related articles
phi nodes in linear time sreedhar@bluebeard.cs.mcgill.ca (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
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.

--

Post a followup to this message