Interprocedural Array Data-Flow Analysis

Thumbnail Image

View/Download File

Persistent link to this item

View Statistics

Journal Title

Journal ISSN

Volume Title


Interprocedural Array Data-Flow Analysis

Published Date






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.



Related to



Series/Report Number

Funding information

Isbn identifier

Doi identifier

Previously Published Citation

Suggested citation

Gu, Junjie. (1997). Interprocedural Array Data-Flow Analysis. Retrieved from the University Digital Conservancy,

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.