summary of data flow algorithms

lee@cs.rutgers.edu
Fri, 22 May 1992 16:07:36 GMT

          From comp.compilers

Related articles
Data flow analysis lee@cadenza.rutgers.edu (1992-04-14)
summary of data flow algorithms lee@cs.rutgers.edu (1992-05-22)
| List of all articles for this month |

Newsgroups: comp.compilers
From: lee@cs.rutgers.edu
Keywords: optimize, summary, dataflow
Organization: Compilers Central
References: 92-04-057
Date: Fri, 22 May 1992 16:07:36 GMT

Some time ago, I wrote:
>If you have implemented data flow analysis algorithms for your systems
>(for example, compilers), I would like to know any of the following
>methods you used:
>
> 1. iterative algorithms;
> 2. Allen-Cocke interval analysis;
> 3. Tarjan interval analysis;
> 4. Hecht-Ullman T1-T2 analysis;
> 5. Graham-Wegman S1-S2-S3 analysis;
> 6. others, please specify.


According to the responses I have received, I have the following
summary result.




DFA algorithm how many use it
------------- ---------------


iterative 11
Tarjan 2


Graham-Wegman 1
interval * 1


sparse DF ** 2
SSA *** 1


iterative + structural 1
reduction


* it was not indicated that either Allen-Cocke or Tarjan interval
analysis was used.


** sparse data flow evaluation technique by Choi, Cytron and Ferrante.


*** SSA: static single assigement (which is more a program
representation than a data flow analysis algorithm)




Since most responses were from the academia, I am wondering what
algorithms are frequently used in production compilers.


Yong-fong
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.