A Framework for Data Dependence Testing in the Presence of Pointers

In the presence of pointers, data dependence testing is a difficult and increasingly common problem. Existing approaches work well for pointers to named memory locations (i.e. other variables), but are overly conservative given pointers to unnamed memory locations. In this paper we present a new framework for performing more accurate data dependence testing in the latter case, which occurs in the context of dynamic, pointer-based data structures. We will demonstrate the effectiveness of our approach by breaking false dependences that existing approaches cannot, and provide results which show that removing such dependences can enable significant paralleltzation.