Efficiently Computing {phi}-Nodes On-The-Fly

Recently, Static Single Assignment Form and Sparse Evaluation Graphs have been advanced for the efficient solution of program optimization problems. Each method is provided with an initial set of flow graph nodes that inherently affect a problem\u27s solution. Other relevant nodes are those where potentially disparate solutions must combine. Previously, these so-called {phi}-nodes were found by computing the iterated dominance frontiers of the initial set of nodes, a process that could take worst case quadratic time with respect to the input flow graph. In this paper we present an almost-linear algorithm for detemining exactly the same set of {phi}-nodes