Demand-Driven Data-Flow Analysis of
Explicitly Parallel Programs
Universiteit Dortmund, Germany
- Full Paper(.ps version)
Demand-driven data-flow analysis (DD-DFA) has been pioneered
in the context of interprocedural analysis of sequential
programs to accommodate the specific needs of slicing and debugging
tools, but also to compensate for the continuous growth of programs
and program complexity, which make static program analyses more and
more complex and time consuming. Particularly successful in practice
turned out to be a DD-DFA approach based on reverse DFA. Here, we
demonstrate how to generalize this approach to explicitly
parallel programs. We exemplify our approach for the class of
GEN/KILL-problems, which are most important in practice because of
the numerous optimizations based upon them. Moreover, we demonstrate
that our approach can easily be parallelized. For GEN/KILL-problems,
this allows us to compute the information provided by conventional
DFA at the usually much smaller costs of answering a data-flow query.
In practice, this can lead to a substantial speed-up of
analysing and optimizing explicitly parallel programs.
Please contact our
webadmin with any comments or changes.
Unless explicitly stated otherwise, all material is
copyright © The University of Edinburgh.