Importance of heap specialization in pointer analysis

Erik M. Nystrom, Hong Seok Kim, Wen-Mei W Hwu

Research output: Contribution to conferencePaper

Abstract

Specialization of heap objects is critical for pointer analysis to effectively analyze complex memory activity. This paper discusses heap specialization with respect to call chains. Due to the sheer number of distinct call chains, exhaustive specialization can be cumbersome. On the other hand, insufficient specialization can miss valuable opportunities to prevent spurious data flow, which results in not only reduced accuracy but also increased overhead. In determining whether further specialization will be fruitful, an object's escape information can be exploited. From empirical study, we found that restriction based on escape information is often, but not always, sufficient at prohibiting the explosive nature of specialization. For in-depth case study, four representative benchmarks are selected. For each benchmark, we vary the degree of heap specialization and examine its impact on analysis results and time. To provide better visibility into the impact, we present the points-to set and pointed-to-by set sizes in the form of histograms.

Original languageEnglish (US)
Pages43-48
Number of pages6
StatePublished - Sep 29 2004
EventProceedings of the 2004 ACM SIGPLAN/SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE'04 - Washington, DC, United States
Duration: Jun 7 2004Jun 8 2004

Other

OtherProceedings of the 2004 ACM SIGPLAN/SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE'04
CountryUnited States
CityWashington, DC
Period6/7/046/8/04

Fingerprint

Visibility
Data storage equipment

Keywords

  • Context sensitivity
  • Heap specialization
  • Pointer analysis

ASJC Scopus subject areas

  • Software

Cite this

Nystrom, E. M., Kim, H. S., & Hwu, W-M. W. (2004). Importance of heap specialization in pointer analysis. 43-48. Paper presented at Proceedings of the 2004 ACM SIGPLAN/SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE'04, Washington, DC, United States.

Importance of heap specialization in pointer analysis. / Nystrom, Erik M.; Kim, Hong Seok; Hwu, Wen-Mei W.

2004. 43-48 Paper presented at Proceedings of the 2004 ACM SIGPLAN/SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE'04, Washington, DC, United States.

Research output: Contribution to conferencePaper

Nystrom, EM, Kim, HS & Hwu, W-MW 2004, 'Importance of heap specialization in pointer analysis' Paper presented at Proceedings of the 2004 ACM SIGPLAN/SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE'04, Washington, DC, United States, 6/7/04 - 6/8/04, pp. 43-48.
Nystrom EM, Kim HS, Hwu W-MW. Importance of heap specialization in pointer analysis. 2004. Paper presented at Proceedings of the 2004 ACM SIGPLAN/SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE'04, Washington, DC, United States.
Nystrom, Erik M. ; Kim, Hong Seok ; Hwu, Wen-Mei W. / Importance of heap specialization in pointer analysis. Paper presented at Proceedings of the 2004 ACM SIGPLAN/SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE'04, Washington, DC, United States.6 p.
@conference{1c3bb884a88a432bb342e5883148c07c,
title = "Importance of heap specialization in pointer analysis",
abstract = "Specialization of heap objects is critical for pointer analysis to effectively analyze complex memory activity. This paper discusses heap specialization with respect to call chains. Due to the sheer number of distinct call chains, exhaustive specialization can be cumbersome. On the other hand, insufficient specialization can miss valuable opportunities to prevent spurious data flow, which results in not only reduced accuracy but also increased overhead. In determining whether further specialization will be fruitful, an object's escape information can be exploited. From empirical study, we found that restriction based on escape information is often, but not always, sufficient at prohibiting the explosive nature of specialization. For in-depth case study, four representative benchmarks are selected. For each benchmark, we vary the degree of heap specialization and examine its impact on analysis results and time. To provide better visibility into the impact, we present the points-to set and pointed-to-by set sizes in the form of histograms.",
keywords = "Context sensitivity, Heap specialization, Pointer analysis",
author = "Nystrom, {Erik M.} and Kim, {Hong Seok} and Hwu, {Wen-Mei W}",
year = "2004",
month = "9",
day = "29",
language = "English (US)",
pages = "43--48",
note = "Proceedings of the 2004 ACM SIGPLAN/SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE'04 ; Conference date: 07-06-2004 Through 08-06-2004",

}

TY - CONF

T1 - Importance of heap specialization in pointer analysis

AU - Nystrom, Erik M.

AU - Kim, Hong Seok

AU - Hwu, Wen-Mei W

PY - 2004/9/29

Y1 - 2004/9/29

N2 - Specialization of heap objects is critical for pointer analysis to effectively analyze complex memory activity. This paper discusses heap specialization with respect to call chains. Due to the sheer number of distinct call chains, exhaustive specialization can be cumbersome. On the other hand, insufficient specialization can miss valuable opportunities to prevent spurious data flow, which results in not only reduced accuracy but also increased overhead. In determining whether further specialization will be fruitful, an object's escape information can be exploited. From empirical study, we found that restriction based on escape information is often, but not always, sufficient at prohibiting the explosive nature of specialization. For in-depth case study, four representative benchmarks are selected. For each benchmark, we vary the degree of heap specialization and examine its impact on analysis results and time. To provide better visibility into the impact, we present the points-to set and pointed-to-by set sizes in the form of histograms.

AB - Specialization of heap objects is critical for pointer analysis to effectively analyze complex memory activity. This paper discusses heap specialization with respect to call chains. Due to the sheer number of distinct call chains, exhaustive specialization can be cumbersome. On the other hand, insufficient specialization can miss valuable opportunities to prevent spurious data flow, which results in not only reduced accuracy but also increased overhead. In determining whether further specialization will be fruitful, an object's escape information can be exploited. From empirical study, we found that restriction based on escape information is often, but not always, sufficient at prohibiting the explosive nature of specialization. For in-depth case study, four representative benchmarks are selected. For each benchmark, we vary the degree of heap specialization and examine its impact on analysis results and time. To provide better visibility into the impact, we present the points-to set and pointed-to-by set sizes in the form of histograms.

KW - Context sensitivity

KW - Heap specialization

KW - Pointer analysis

UR - http://www.scopus.com/inward/record.url?scp=4544366942&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=4544366942&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:4544366942

SP - 43

EP - 48

ER -