An elimination algorithm for bidirectional data flow problems using edge placement
- 1 April 1993
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 15 (2) , 312-336
- https://doi.org/10.1145/169701.169684
Abstract
Bidirectional data flow problems, useful in a wide range of optimizing transformations, are conventionally solved using the iterative approach. This paper shows that use of the edge placement technique makes bidirectional data flow problems amenable to efficient solution. An elimination algorithm for bidirectional data flow problems using edge placement is presented, and its complexity is shown to be identical to the complexity of elimination algorithms for unidirectional data flowsKeywords
This publication has 10 references indexed in Scilit:
- A usually linear algorithm for register assignment using edge placement of load and store instructionsComputer Languages, 1990
- Register assignment using code placement techniquesComputer Languages, 1988
- A fast algorithm for code movement optimisationACM SIGPLAN Notices, 1988
- A solution to a problem with Morel and Renvoise's “Global optimization by suppression of partial redundancies”ACM Transactions on Programming Languages and Systems, 1988
- Elimination algorithms for data flow analysisACM Computing Surveys, 1986
- Fast Algorithms for Solving Path ProblemsJournal of the ACM, 1981
- Global optimization by suppression of partial redundanciesCommunications of the ACM, 1979
- A program data flow analysis procedureCommunications of the ACM, 1976
- A Fast and Usually Linear Algorithm for Global Flow AnalysisJournal of the ACM, 1976
- A Simple Algorithm for Global Data Flow Analysis ProblemsSIAM Journal on Computing, 1975