A data dependence test based on the projection of paths over shape graphs

We propose a data dependence detection test based on a new conflict analysis algorithm for C codes which make intensive use of recursive data structures dynamically allocated in the heap. This algorithm requires two pieces of information from the code section under analysis (a loop or a recursive function): (i) abstract shape graphs that represent the state of the heap at the code section; and (ii) path expressions that collect the traversing information for each statement. Our algorithm projects the path expressions on the shape graphs and checks over the graphs to ascertain whether one of the sites reached by a write statement matches one of the sites reached by another statement on a different loop iteration (or on a different call instance in a recursive function), in which case a conflict between the two statements is reported. Although our algorithm presents exponential complexity, we have found that in practice the parameters that dominate the computational cost have very low values, and to the best of our knowledge, all the other related studies involve higher costs. In fact, our experimental results show reductions in the data dependence analysis times of one or two orders of magnitude in some of the studied benchmarks when compared to a previous data dependence algorithm. Thanks to the information on uncovered data dependences, we have manually parallelized these codes, achieving speedups of 2.19 to 3.99 in four cores.

► Presents a new dependence test for C codes based on recursive data structures.
► Uncovers parallelism that could not be efficiently detected up to the present.
► Outlines a conflict analysis driven by the projection of paths over shape graphs.
► Incorporates a pruning stage that further reduces the analysis time.