# flow analysis and optimization

## vugranam@macs.ee.mcgill.ca (Vugranam Chakravarthy Sreedhar)Thu, 4 Nov 1993 23:18:01 GMT

From comp.compilers

Related articles
flow analysis and optimization vugranam@macs.ee.mcgill.ca (1993-11-04)
Re: flow analysis and optimization preston@dawn.cs.rice.edu (1993-11-09)
Re: flow analysis and optimization cliffc@rice.edu (1993-11-09)
Re: flow analysis and optimization paco@legia.cs.rice.edu (1993-11-09)
Re: flow analysis and optimization bwilson@shasta.Stanford.EDU (1993-11-14)
| List of all articles for this month |

 Newsgroups: comp.compilers From: vugranam@macs.ee.mcgill.ca (Vugranam Chakravarthy Sreedhar) Keywords: optimize, question Organization: Compilers Central Date: Thu, 4 Nov 1993 23:18:01 GMT

Hello

In dragon book 3 methods are described for doing flow
analyses and optimizations.
1. Syntax directed approach
-- very elegant for structured programs (with break/continue)
2. Interval method
-- for reducible graphs.
3. (general) iterative method.
-- any arbitrary graph

One could transform any graphs to reducible graphs and use interval method
(instead of iterative method).

Or one can restructure any programs (with goto) and use the syntax
directed method. (Ah! I have seen enough discussion on eliminating gotos
to produce structured programs. Hope I don't trigger yet another
discussion on this topic ;-) )

Given that we have three approaches for performing flow analyses. I have
the following questions.

1. I would like to know which method you use in your compiler. (I would
appreciate guys from MIPS, SUN, IBM, Rice, Stanford, Illinois, etc.
working on optimizations would input their experiences.)

2. Do you transform your program to a reducible graph and then do your
analyses? What benefits do you get for taking this approach? I would like
to know practical reasons rather than theoretical ones.

3. Do you perform interprocedural optimizations? What is the complexity
(space/time) of doing interprocedural analysis? What benefits do you get
(in terms of speedup and efficiency of the code generated)? (C/C++ guys
how do handle pointer analysis, especially in presence of heap allocation,
pointer arithmetic, type-casting, etc.?) Is it really worth doing
interprocedural analysis (especially for C/C++)? (I am not aware of any
production compiler doing interprocedural analyses.)

4. I was reading one article (can't remember the exact reference) where
the author mentions that they use a combination of interval analysis and
iterative method for doing flow analyses. Can anybody enlighten me on
this? I beleive they identify sections of code that are reducible and
apply iterval analysis for these sections.

Sreedhar
--

Post a followup to this message