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

Authors

Ron K. Cytron, Washington University in St LouisFollow
Jeanne Ferrante, Washington University in St Louis

Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1993-01-01

Filename

WUCS-93-24.PDF

Technical Report Number

WUCS-93-24

Abstract

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's 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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7K35RVR

Recommended Citation

Cytron, Ron K. and Ferrante, Jeanne, "Efficiently Computing {phi}-Nodes On-The-Fly" Report Number: WUCS-93-24 (1993). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/312