PATCH---a new algorithm for rapid incremental dependence analysis
Bill Appelbe, Kevin Smith, Kurt Stirewalt · 1991
Dependenceanalysis is critical to tools for parallel programming such as compilers, parallelizers, and performance analyzers.Conventional algorithms and data structures for dependence analysis are complex and time consuming, requiring multiple passes.In addition, these algorithms cannot easily be adapted to incrementally recompute dependence after program modifications.In this paper we present a new approach to dependence analysis which computes dependence in linear time (no backtracking) with a low space overhead.The algorithm handles arbitrary, unstructured control flow and calls to subprograms whose dependence have not been analyzed, and can be extended to allow very rapid incremental dependence recomputation.The algorithms are currently being implemented in PAT, a portable parallelization tool.