A Linear Time Algorithm for Placing phi-nodes

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 φ-nodes. In this paper, we present a surprisingly simple algorithm for computing φ-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 φ-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.