Interprocedural Array Data-Flow Analysis
1997
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Interprocedural Array Data-Flow Analysis
Alternative title
Authors
Published Date
1997
Publisher
Type
Report
Abstract
Array data-flow analysis is known to be crucial to the success of array privatization, one of
the most important techniques for program parallelization. It is clear that array data-flow
analysis should be performed interprocedurally and symbolically, and that it often needs to
handle the predicates represented by IF conditions.
In this thesis, we first summarize array data-flow approaches for both intra.procedural
analysis and interprocedural analysis. Then our interprocedural. array data-flow analysis
is presented with the intent of supporting array privatization and loop parallelization for
programs that have arbitrary control flow graphs and acyclic call graphs. Our scheme summarizes
array access information using guarded array regions and propagates such regions
over a hierarchical control flow graph. The u~e of guards allows us to use the information
in IF conditions to make our array data-flow analysis more accurate and thereby to handle
difficult cases. The guarded· array regions also retain the simplicity of set operations for
regular array regions (also known as bounded regular sections) in common cases.
To be not only effective but also efficient, such a powerful program analysis should be
carefully designed. This thesis will also discuss our research experiments and experience
in building an efficient array data-flow analyzer. We have made our analyzer effective
and efficient by carefully choosing set representation, delaying set difference, representing
predicates hierarchically, etc. Delaying set difference allows our analyzer to compute the
difference in the right order {e.g. (u - wI) - w2 can be performed by (u - w2) - wl), and
thus helps to avoid unnecessary difference operations during information propagation. This
also simplifies intersection operations. Our experimental results show that our analyzer is
both effective and efficient.
Keywords
Description
Related to
Replaces
License
Series/Report Number
Technical Report; 97-054
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Other identifiers
Suggested citation
Gu, Junjie. (1997). Interprocedural Array Data-Flow Analysis. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/215339.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.