A general data dependence test for dynamic, pointer-based data structures

Joseph Hummel, Laurie J. Hendren, Alexandru Nicolau

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


Optimizing compilers require accurate dependence testing to enable numerous, performance-enhancing transformations. However, data dependence testing is a difficult problem, particularly in the presence of pointers. Though existing approaches work well for pointers to named memory locations 1994, they are overly conservative in the case of pointers to unnamed memory locations. The latter occurs in the context of dynamic, pointer-based data structures, used in a variety of applications ranging from system software to computational geometry to N-body and circuit simulations. In this paper we present a new technique for performing more accurate data dependence testing in the presence of dynamic, pointer-based data structures. We will demonstrate its effectiveness by breaking false dependences that existing approaches cannot, and provide results which show that removing these dependences enables significant parallelization of a real application.

Original languageEnglish (US)
Pages (from-to)218-229
Number of pages12
JournalACM SIGPLAN Notices
Issue number6
StatePublished - Jan 6 1994

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'A general data dependence test for dynamic, pointer-based data structures'. Together they form a unique fingerprint.

Cite this