Hybrid incremental alias algorithms

Two scalar variables are said to be aliases, if, at some time during program execution, they both may refer to the same storage location. Two structured variables (arrays, records, etc.) are aliased, if at some point during execution their contents overlap. The need for precise interprocedural alias information, especially for arrays, has prevented compilers for parallel hardware from extracting much of the parallelism that actually is present in scientific programs. Despite the utility of static analysis information, the cost of keeping it consistent with the current state of an evolving program must be shown reasonable to ensure its use in practice. Incremental data flow algorithms are designed to efficiently update data flow information after changes, rather than exhaustively recalculate solutions. The authors offer algorithms for scalar aliasing which have efficient and precise incremental versions and show promise of extensibility to more precise array aliasing techniques, which will aid in compiling for parallel. These analysis algorithms can be performed in parallel, and can be used to aid the analysis of separately compiled modules. The authors also discuss first steps in adapting the algorithm for incremental array aliasing, and possible applications to constant or range propagation