TY - GEN
T1 - Automatic pool allocation for disjoint data structures
AU - Lattner, Chris
AU - Adve, Vikram
N1 - Funding Information:
*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.
Publisher Copyright:
Copyright 2002 ACM.
PY - 2002/6/16
Y1 - 2002/6/16
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=38849102988&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=38849102988&partnerID=8YFLogxK
U2 - 10.1145/773146.773041
DO - 10.1145/773146.773041
M3 - Conference contribution
AN - SCOPUS:38849102988
T3 - Proceedings of the 2002 Workshop on Memory System Performance, MSP 2002
SP - 13
EP - 24
BT - Proceedings of the 2002 Workshop on Memory System Performance, MSP 2002
PB - Association for Computing Machinery, Inc
T2 - 2002 Workshop on Memory System Performance, MSP 2002
Y2 - 16 June 2002
ER -