Show simple item record

dc.contributor.authorZhao, Jisheng
Burke, Michael G.
Sarkar, Vivek
dc.date.accessioned 2017-08-02T22:03:16Z
dc.date.available 2017-08-02T22:03:16Z
dc.date.issued 2017-02-01
dc.identifier.urihttps://hdl.handle.net/1911/96420
dc.description.abstract Points-to analysis is a fundamental requirement for many program analyses, optimizations, and debugging/verification tools. However, finding an effective balance between performance, scalability and precision in points-to analysis remains a major challenge. Many flow-sensitive algorithms achieve a desirable level of precision, but are impractical for use on large software. Likewise, many flow-insensitive algorithms scale to large software, but do so with major limitations on precision. Further, given the recent multicore hardware trends, more attention needs to be paid to the use of parallelism for improved performance. In this paper, we introduce a new pointer analysis based on Pointer SSA form (an extension of Array SSA form,) which is flow-sensitive, memory efficient, and can readily be parallelized. It decomposes the points-to analysis into fine-grained units of work that can be easily implemented in an asynchronous task-parallel programming model. More specifically, our contributions are as follows: 1. A Pointer SSA (PSSA)-based scalable interprocedural flow-sensitive context-insensitive pointer analysis (PSSAPT) that produces both points-to and heap def-use information, and supports the task parallel programming model; 2. a preliminary evaluation, including scalability and precision, of the implementation of parallel PSSAPT using a lightweight task-parallel library. Our experimental results with 6 real world applications (including the 2.2MLOC Tizen OS framework) on a 12-core machine show an average speedup of 4.45 and maximum speedup of 7.35. Our evaluation also includes precision results for an inlinable indirect call analysis.
dc.format.extent 11 pp
dc.language.iso eng
dc.rights You are granted permission for the noncommercial reproduction, distribution, display, and performance of this technical report in any format, but this permission is only for a period of forty-five (45) days from the most recent time that you verified that this technical report is still available from the Computer Science Department of Rice University under terms that include this permission. All other rights are reserved by the author(s).
dc.title Parallel Flow-Sensitive Points-to Analysis
dc.type Technical report
dc.date.note February 1, 2017
dc.identifier.digital TR17-01
dc.type.dcmi Text
dc.identifier.citation Zhao, Jisheng, Burke, Michael G. and Sarkar, Vivek. "Parallel Flow-Sensitive Points-to Analysis." (2017) https://hdl.handle.net/1911/96420.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record