Fast and Precise Handling of Positive Weight Cycles for Field-Sensitive Pointer Analysis

Lei, Y; Sui, Y

Fast and Precise Handling of Positive Weight Cycles for Field-Sensitive Pointer Analysis

Lei, Y Sui, Y

Permalink

Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2019, 11822 LNCS pp. 27 - 47
Issue Date:: 2019-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript versionAdobe PDF (779.45 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Lei, Y	en_US
dc.contributor.author	Sui, Y https://orcid.org/0000-0002-9510-6574	en_US
dc.date.issued	2019-01-01	en_US
dc.identifier.citation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2019, 11822 LNCS pp. 27 - 47	en_US
dc.identifier.isbn	9783030323035	en_US
dc.identifier.issn	0302-9743	en_US
dc.identifier.uri	http://hdl.handle.net/10453/138550
dc.description.abstract	© Springer Nature Switzerland AG 2019. By distinguishing the fields of an object, Andersen’s field-sensitive pointer analysis yields better precision than its field-insensitive counterpart. A typical field-sensitive solution to inclusion-based pointer analysis for C/C++ is to add positive weights to the edges in Andersen’s constraint graph to model field access. However, the precise modeling is at the cost of introducing a new type of constraint cycles, called positive weight cycles (PWCs). A PWC, which contains at least one positive weight constraint, can cause infinite and redundant field derivations of an object unless the number of its fields is bounded by a pre-defined value. PWCs significantly affect analysis performance when analyzing large C/C++ programs with heavy use of structs and classes.para This paper presents Dea, a fast and precise approach to handling of PWCs that significantly accelerates existing field-sensitive pointer analyses by using a new field collapsing technique that captures the derivation equivalence of fields derived from the same object when resolving a PWC.para Two fields are derivation equivalent in a PWC if they are always pointed to by the same variables (nodes) in this PWC. A stride-based field representation is proposed to identify and collapse derivation equivalent fields into one, avoiding redundant field derivations with significantly fewer field objects during points-to propagation. We have conducted experiments using 11 open-source C/C++ programs. The evaluation shows that Dea is on average 7.1X faster than Pearce et al.’s field-sensitive analysis (Pkh), obtaining the best speedup of 11.0X while maintaining the same precision.	en_US
dc.relation.ispartof	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)	en_US
dc.relation.isbasedon	10.1007/978-3-030-32304-2_3	en_US
dc.rights	info:eu-repo/semantics/openAccess
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	Fast and Precise Handling of Positive Weight Cycles for Field-Sensitive Pointer Analysis	en_US
dc.type	Conference Proceeding
utslib.citation.volume	11822 LNCS	en_US
pubs.embargo.period	Not known	en_US
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/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	open_access	*
pubs.publication-status	Published	en_US
pubs.volume	11822 LNCS	en_US

Abstract:

© Springer Nature Switzerland AG 2019. By distinguishing the fields of an object, Andersen’s field-sensitive pointer analysis yields better precision than its field-insensitive counterpart. A typical field-sensitive solution to inclusion-based pointer analysis for C/C++ is to add positive weights to the edges in Andersen’s constraint graph to model field access. However, the precise modeling is at the cost of introducing a new type of constraint cycles, called positive weight cycles (PWCs). A PWC, which contains at least one positive weight constraint, can cause infinite and redundant field derivations of an object unless the number of its fields is bounded by a pre-defined value. PWCs significantly affect analysis performance when analyzing large C/C++ programs with heavy use of structs and classes.para This paper presents Dea, a fast and precise approach to handling of PWCs that significantly accelerates existing field-sensitive pointer analyses by using a new field collapsing technique that captures the derivation equivalence of fields derived from the same object when resolving a PWC.para Two fields are derivation equivalent in a PWC if they are always pointed to by the same variables (nodes) in this PWC. A stride-based field representation is proposed to identify and collapse derivation equivalent fields into one, avoiding redundant field derivations with significantly fewer field objects during points-to propagation. We have conducted experiments using 11 open-source C/C++ programs. The evaluation shows that Dea is on average 7.1X faster than Pearce et al.’s field-sensitive analysis (Pkh), obtaining the best speedup of 11.0X while maintaining the same precision.

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

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