summary of data flow algorithms
Fri, 22 May 1992 16:07:36 GMT

          From comp.compilers

Related articles
Data flow analysis (1992-04-14)
summary of data flow algorithms (1992-05-22)
| List of all articles for this month |

Newsgroups: comp.compilers
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

* 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.


Post a followup to this message

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