Gu, Junjie2020-09-022020-09-021997https://hdl.handle.net/11299/215339Array 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.en-USReport