Automatic pool allocation for disjoint data structures

Chris Lattner, Vikram Adve

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

Abstract

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
Pages13-24
Number of pages12
ISBN (Electronic)1581134789, 9781581134780
DOIs
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

Other

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

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Hardware and Architecture

Fingerprint

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

Cite this