Re: flow analysis and optimization

vugranam@macs.ee.mcgill.ca (Vugranam Chakravarthy Sreedhar) writes:


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


People around here use iterative analysis pretty exclusively. We do
Fortran, so there's always the possiblity of reducibility to be accounted
for. Sure, you can do node splitting, but why bother? In general, the
time to do flow analysis is very small (a few percent), though it would
obviously depend on the exact optimizer.


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


No. I don't know of any benefits (though it would be fun to undo
someone's carefully code Duff's Device!)


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


We do some interprocedural analysis. I can't tell you the cost/benefit
tradeoffs. That's a big research question that will take some years to
answer well. Asymptotic complexities will depend on the level of detail
you're looking for in your analysis. Many papers you can reference for
details, for example


    author="Keith D. Cooper and Ken Kennedy",
    title="Interprocedural Side-Effect Analysis in Linear Time",
    pages="57--66",
    journal=sigplan,
    year=1988,
    month=jul,
    volume=23,
    number=7,
    note=pldi88


and


    author="David Callahan",
    title="The Program Summary Graph and Flow-Sensitive Interprocedural
                                  Data Flow Analysis",
    pages="47--56",
    journal=sigplan,
    year=1988,
    month=jul,
    volume=23,
    number=7,
    note=pldi88


Convex has done interprocedural analysis to support optimization for
several years. I believe IBM's latest incarnation of the xl compiler
series also does interprocedural analysis.


Pointer analysis, of any sort, is an important topic of current research.
One paper is


    author="David R. Chase and Mark Wegman and F. Kenneth Zadeck",
    title="Analysis of Pointers and Structures",
    pages="296--310",
    journal=sigplan,
    year=1990,
    month=jun,
    volume=25,
    number=6,
    note=pldi90


There are others. Check your recent PLDI proceedings, which is usually
the place to start looking for this sort of question.


Preston Briggs
--

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