Re: Global Data flow analysis

bar@advtech.uswest.com (Bala Ramakrishnan) writes:
>While local (function level) data flow analysis is fairly well defined,
>does anyone have any info on techniques/problems associated with global
>data flow. Can you suggest any papers/books on this subject?


and the moderator writes:
>[Other than the practical issues involved with separate compilation or
>the lack thereof, are there any issues peculiar to global dataflow? -John]


Sure. First though, let's follow tradition and say "interprocedural
analysis", since global analysis (traditionally!) means analysis
encompassing an entire routine.


Major differences include


Definition of the problems and interpretation of the results.
Typical interesting questions include: what variables _might_
be referenced during this call, what variables _will_ be
referenced during this call, what variables are live at the
end of this procedure, what paramters are constant at upon
invocation of this procedure, ...


Asymptotic complexity. The difference between "might be
referenced" and "will be referenced" is considerable.


Construction of the call (multi)graph, particularly in the
presence of recursion, parameter aliasing, global variables,
function-valued parameters and functions, multiple
inheritence, ... The more features you add, the more
interesting it gets.


And of course, the recompilation issue is significant.
We can reasonably expect that individual procedures might have
some maximum size, say 1000 statements. It makes less sense
to limit the size of programs!


There's a lot of interesting literature out there. Here's a bunch of
papers in the area. The '86 TOPLAS paper might be the best starting
point. Be sure to check the bibliographies for further references.


Preston Briggs


------------------------------------------------------------------------------


title="Efficient Computation of Flow Insensitive Interprocedural
                                  Summary Information",
author="Keith D. Cooper and Ken Kennedy",
pages="247--258",
journal=sigplan,
year=1984,
month=jun,
volume=19,
number=6,
note=pldi84


title="Analyzing Aliases of Reference Formal Parameters",
author="Keith D. Cooper",
booktitle=popl12,
year=1985,
month=jan,
pages="281--290"


title="Interprocedural Optimization: Eliminating Unnecessary Recompilation",
author="Keith D. Cooper and Ken Kennedy and Linda Torczon",
journal=sigplan,
year=1986,
month=jul,
volume=21,
number=7,
note=pldi86,
pages="58--67"


title="Interprocedural Constant Propagation",
author="David Callahan and Keith D. Cooper and Ken Kennedy and
                Linda Torczon",
journal=sigplan,
year=1986,
month=jul,
volume=21,
number=7,
note=pldi86,
pages="152--161"


title="The Impact of Interprocedural Analysis and Optimization in
                                  the Rn Programming Environment",
author="Keith D. Cooper and Ken Kennedy and Linda Torczon",
pages="491--523",
journal=toplas,
year=1986,
month=oct,
volume=8,
number=4


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


title="Fast Interprocedural Alias Analysis",
author="Keith D. Cooper and Ken Kennedy",
booktitle=popl16,
year=1989,
month=jan,
pages="49--59"


title="Constructing the Procedure Call Multigraph",
author="David Callahan and Alan Carle and Mary W. Hall and Ken Kennedy",
journal=ieeese,
volume=16,
number=4,
month=apr,
year=1990,


where ieeese = IEEE Transactions on Software Engineering
            toplas = Transactions on Programming Languages and Systems
            popl = conference proceedings of Principles of Programming Languages
            pldi = conference proceedings of Programming Language Design
and Implementation
--

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