Hash Consed Points-To Sets

Barbar, M; Sui, Y

Hash Consed Points-To Sets

Barbar, M Sui, Y

Permalink

Publisher:: Springer International Publishing
Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2021, 12913 LNCS, pp. 25-48
Issue Date:: 2021-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted versionAdobe PDF (5.26 MB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Barbar, M
dc.contributor.author	Sui, Y https://orcid.org/0000-0002-9510-6574
dc.date.accessioned	2022-05-20T14:08:55Z
dc.date.available	2022-05-20T14:08:55Z
dc.date.issued	2021-01-01
dc.identifier.citation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2021, 12913 LNCS, pp. 25-48
dc.identifier.isbn	9783030888053
dc.identifier.issn	0302-9743
dc.identifier.issn	1611-3349
dc.identifier.uri	http://hdl.handle.net/10453/157578
dc.description.abstract	Points-to analysis is a fundamental static analysis, on which many other analyses and optimisations are built. The goal of points-to analysis is to statically approximate the set of abstract objects that a pointer can point to at runtime. Due to the nature of static analysis, points-to analysis introduces much redundancy which can result in duplicate points-to sets and duplicate set union operations, particularly when analysing large programs precisely. To improve performance, there has been extensive effort in mitigating duplication at the algorithmic level through, for example, cycle elimination and variable substitution. Unlike previous approaches which make algorithmic changes to points-to analysis, this work aims to improve the underlying data structure, which is less studied. Inspired by hash consing from the functional programming community, this paper introduces the use of hash consed points-to sets to reduce the effects of this duplication on both space and time without any high-level algorithmic change. Hash consing can effectively handle duplicate points-to set by representing points-to sets once, and referring to such representations through references, and can speed up duplicate union operations through efficient memoisation. We have implemented and evaluated our approach using 16 real-world C/C++ programs (more than 9.5 million lines of LLVM instructions). Our results show that our approach speeds up state-of-the-art Andersen’s analysis by 1.85 × on average (up to 3.21 × ) and staged flow-sensitive analysis (SFS) by 1.69 × on average (up to 2.23 × ). We also observe an average ≥ 4.93 × (up to ≥ 15.52 × ) memory usage reduction for SFS.
dc.language	en
dc.publisher	Springer International Publishing
dc.relation.ispartof	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.relation.isbasedon	10.1007/978-3-030-88806-0_2
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	This is a post-peer-review, pre-copyedit version of an article published in [Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2021, 12913 LNCS, pp. 25-48]. Publication date 01 Jan 2022 The final authenticated version is available online at: [ https://link.springer.com/chapter/10.1007/978-3-030-88806-0_2”
dc.subject.classification	Artificial Intelligence & Image Processing
dc.title	Hash Consed Points-To Sets
dc.type	Conference Proceeding
utslib.citation.volume	12913 LNCS
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	open_access	*
dc.date.updated	2022-05-20T14:08:51Z
pubs.publication-status	Published
pubs.volume	12913 LNCS

Abstract:

Points-to analysis is a fundamental static analysis, on which many other analyses and optimisations are built. The goal of points-to analysis is to statically approximate the set of abstract objects that a pointer can point to at runtime. Due to the nature of static analysis, points-to analysis introduces much redundancy which can result in duplicate points-to sets and duplicate set union operations, particularly when analysing large programs precisely. To improve performance, there has been extensive effort in mitigating duplication at the algorithmic level through, for example, cycle elimination and variable substitution. Unlike previous approaches which make algorithmic changes to points-to analysis, this work aims to improve the underlying data structure, which is less studied. Inspired by hash consing from the functional programming community, this paper introduces the use of hash consed points-to sets to reduce the effects of this duplication on both space and time without any high-level algorithmic change. Hash consing can effectively handle duplicate points-to set by representing points-to sets once, and referring to such representations through references, and can speed up duplicate union operations through efficient memoisation. We have implemented and evaluated our approach using 16 real-world C/C++ programs (more than 9.5 million lines of LLVM instructions). Our results show that our approach speeds up state-of-the-art Andersen’s analysis by 1.85 × on average (up to 3.21 × ) and staged flow-sensitive analysis (SFS) by 1.69 × on average (up to 2.23 × ). We also observe an average ≥ 4.93 × (up to ≥ 15.52 × ) memory usage reduction for SFS.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/157578