The Access Region Test

Abstract

Traditional loop-based dependence analysis techniques have limitations when non-ane expressions are used, when interprocedural analysis is required, or when analysis of non-loops is needed. In this work, we return to rst principles to devise a more general parallelism detection strategy, which includes a dependence analysis technique which removes some of these limitations. We show how to do interprocedural dependence testing between arbitrary sections of code as well as loops, using a technique which includes privatization and recognition of induc-tions and reductions. We also present the results of recent experiments that we conducted to test the eectiveness of our algorithm on a variety of actual programs. The results are still preliminary, but are quite encouraging.