Automatic pool allocation for disjoint data structures

Chris Lattner, Vikram Adve

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 to 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)
Title of host publicationProceedings of the 2002 Workshop on Memory System Performance, MSP 2002
PublisherAssociation for Computing Machinery
Number of pages12
ISBN (Electronic)1581134789, 9781581134780
StatePublished - Jun 16 2002
Event2002 Workshop on Memory System Performance, MSP 2002 - Berlin, Germany
Duration: Jun 16 2002 → …

Publication series

NameProceedings of the 2002 Workshop on Memory System Performance, MSP 2002


Other2002 Workshop on Memory System Performance, MSP 2002
Period6/16/02 → …

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Hardware and Architecture


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

Cite this