Automatic pool allocation for disjoint data structures

Chris Lattner, Vikram Adve

Research output: Contribution to journalArticlepeer-review


This paper presents an analysis technique and a novel program transformation that can enable powerful optimizations for entire linked data structures. The fully automatic transformation converts ordinary programs to use pool (aka region) allocation for heap-based data structures. The transformation relies on an efficient link-time interprocedural analysis is identify disjoint data structures in the program, to check whether these data structures are accessed in a type-safe manner, and to construct a Disjoint Data Structure Graph that describes the connectivity pattern within such structures. We present preliminary experimental results showing that the data structure analysis and pool allocation are effective for a set of pointer intensive programs in the Olden benchmark suite. To illustrate the optimizations that can be enabled by these techniques, we describe a novel pointer compression transformation and briefly discuss several other optimization possibilities for linked data structures.

Original languageEnglish (US)
Pages (from-to)13-24
Number of pages12
JournalACM SIGPLAN Notices
Issue number2 SUPPL.
StatePublished - Feb 2003

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Automatic pool allocation for disjoint data structures'. Together they form a unique fingerprint.

Cite this