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.

Published:

"Automatic Pool Allocation for Disjoint Data Structures", Chris Lattner & Vikram Adve,
ACM SIGPLAN Workshop on Memory System Performance (MSP), Berlin, Germany, June 2002.

Download:

• Automatic Pool Allocation for Disjoint Data Structures (PS)
• Automatic Pool Allocation for Disjoint Data Structures (PDF)
• Automatic Pool Allocation for Disjoint Data Structures (Powerpoint slides)

BibTeX Entry:

@InProceedings{LattnerAdve:MSP02,
  Author    = "{Chris Lattner and Vikram Adve}",
  Title     = "{Automatic Pool Allocation for Disjoint Data Structures}",
  Booktitle = "{Proc. ACM SIGPLAN Workshop on Memory System Performance}",
  Address   = "{Berlin, Germany}",
  Month     = {Jun},
  Year      = {2002}
}