@inproceedings{3c600b67dc394724915805ecbfa1d961,
title = "Automatic pool allocation for disjoint data structures",
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.",
author = "Chris Lattner and Vikram Adve",
note = "*This work is sponsored by an NSF CAREER award, grant number EIA-0093426, and supported in part by the NSF Operating Systems and Compilers program under grant number CCR-9988482 and by an equipment donation from Hewlett Packard.; 2002 Workshop on Memory System Performance, MSP 2002 ; Conference date: 16-06-2002",
year = "2002",
month = jun,
day = "16",
doi = "10.1145/773146.773041",
language = "English (US)",
series = "Proceedings of the 2002 Workshop on Memory System Performance, MSP 2002",
publisher = "Association for Computing Machinery",
pages = "13--24",
booktitle = "Proceedings of the 2002 Workshop on Memory System Performance, MSP 2002",
address = "United States",
}