NDLI: Exploiting the structure of the constraint graph for efficient points-to analysis

Please wait, while we are loading the content...

Why is your web browser using so much memory?

Memory management for many-core processors with software configurable locality policies

Barriers reconsidered, friendlier still!

Down for the count? Getting reference counting back in the ring

A generalized theory of collaborative caching

The myrmics memory allocator: hierarchical,message-passing allocation for global address spaces

Eliminating read barriers through procrastination and cleanliness

The Collie: a wait-free compacting collector

Exploiting the structure of the constraint graph for efficient points-to analysis

GPUs as an opportunity for offloading garbage collection

Scalable concurrent and parallel mark

new Scala() instance of Java: a comparison of the memory behaviour of Java and Scala programs

Identifying the sources of cache misses in Java programs without relying on hardware counters

Exploiting the structure of the constraint graph for efficient points-to analysis

Content Provider	ACM Digital Library
Author	Nasre, Rupesh
Abstract	Points-to analysis is a key compiler analysis. Several memory related optimizations use points-to information to improve their effectiveness. Points-to analysis is performed by building a constraint graph of pointer variables and dynamically updating it to propagate more and more points-to information across its subset edges. So far, the structure of the constraint graph has been only trivially exploited for efficient propagation of information, e.g., in identifying cyclic components or to propagate information in topological order. We perform a careful study of its structure and propose a new inclusion-based flow-insensitive context-sensitive points-to analysis algorithm based on the notion of dominant pointers. We also propose a new kind of pointer-equivalence based on dominant pointers which provides significantly more opportunities for reducing the number of pointers tracked during the analysis. Based on this hitherto unexplored form of pointer-equivalence, we develop a new context-sensitive flow insensitive points-to analysis algorithm which uses incremental dominator update to efficiently compute points-to information. Using a large suite of programs consisting of SPEC 2000 benchmarks and five large open source programs we show that our points-to analysis is 88% faster than BDD-based Lazy Cycle Detection and 2× faster than Deep Propagation. We argue that our approach of detecting dominator-based pointer-equivalence is a key to improve points-to analysis efficiency.
Starting Page	121
Ending Page	132
Page Count	12
File Format	PDF
ISBN	9781450313506
DOI	10.1145/2258996.2259013
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-06-15
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Points-to analysis Context-sensitivity Dominators Constraint graph
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in