Automatic pool allocation for disjoint data structures
Automatic pool allocation for disjoint data structures
复制标题
不相交数据结构的自动池分配
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
Vikram S. Adve
中科院分区：
文献类型：
--
作者：
Chris Lattner;Vikram S. Adve
本文提出了一种分析技术和一种新的程序转换，可以对整个链接数据结构进行强大的优化。全自动转换将普通程序转换为使用基于堆的数据结构的池(又名区域)分配。该转换依赖于有效的链接时间过程间分析来识别程序中的不相交数据结构，检查这些数据结构是否以类型安全的方式被访问，并构造描述这些结构中的连通性模式的不相交数据结构图。我们给出的初步实验结果表明，数据结构分析和池分配对于Olden基准测试套件中的一组指针密集型程序是有效的。为了说明这些技术可以实现的优化，我们描述了一种新的指针压缩转换，并简要讨论了链接数据结构的其他几种优化可能性。
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.