Level by Level: Making Flow- and Context-Sensitive Pointer Analysis Scalable for Millions of Lines of Code
We present a practical and scalable method for flow- and contextsensitive (FSCS) pointer analysis for C programs. Our method analyzes the pointers in a program level by level in terms of their points-to levels, allowing the points-to relations of the pointers at a particular level to be discovered b...
Main Authors: | , , , , |
---|---|
Other Authors: | |
Format: | Text |
Language: | English |
Subjects: | |
Online Access: | http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.210.3191 http://www.cse.unsw.edu.au/~jingling/papers/cgo10.pdf |
id |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.210.3191 |
---|---|
record_format |
openpolar |
spelling |
ftciteseerx:oai:CiteSeerX.psu:10.1.1.210.3191 2023-05-15T18:32:37+02:00 Level by Level: Making Flow- and Context-Sensitive Pointer Analysis Scalable for Millions of Lines of Code Hongtao Yu Jingling Xue Wei Huo Xiaobing Feng Zhaoqing Zhang The Pennsylvania State University CiteSeerX Archives application/pdf http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.210.3191 http://www.cse.unsw.edu.au/~jingling/papers/cgo10.pdf en eng http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.210.3191 http://www.cse.unsw.edu.au/~jingling/papers/cgo10.pdf Metadata may be used without restrictions as long as the oai identifier remains attached to it. http://www.cse.unsw.edu.au/~jingling/papers/cgo10.pdf Algorithms Languages Performance Pointer Analysis Alias Analysis text ftciteseerx 2016-01-07T17:49:21Z We present a practical and scalable method for flow- and contextsensitive (FSCS) pointer analysis for C programs. Our method analyzes the pointers in a program level by level in terms of their points-to levels, allowing the points-to relations of the pointers at a particular level to be discovered based on the points-to relations of the pointers at this level and higher levels. This level-by-level strategy can enhance the scalability of the FSCS pointer analysis in two fundamental ways, by enabling (1) fast and accurate flowsensitive analysis on full sparse SSA form using a flow-insensitive algorithm and (2) fast and accurate context-sensitive analysis using a full transfer function and a meet function for each procedure. Our level-by-level algorithm, LevPA, gives rises to (1) a precise and compact SSA representation for subsequent program analysis and optimization tasks and (2) a flow- and context-sensitive MAY / MUST mod (modification) set and read set for each procedure. Our preliminary results show that LevPA can analyze some programs with over a million lines of C code in minutes, faster than the state-of-the-art FSCS methods. Text The Pointers Unknown |
institution |
Open Polar |
collection |
Unknown |
op_collection_id |
ftciteseerx |
language |
English |
topic |
Algorithms Languages Performance Pointer Analysis Alias Analysis |
spellingShingle |
Algorithms Languages Performance Pointer Analysis Alias Analysis Hongtao Yu Jingling Xue Wei Huo Xiaobing Feng Zhaoqing Zhang Level by Level: Making Flow- and Context-Sensitive Pointer Analysis Scalable for Millions of Lines of Code |
topic_facet |
Algorithms Languages Performance Pointer Analysis Alias Analysis |
description |
We present a practical and scalable method for flow- and contextsensitive (FSCS) pointer analysis for C programs. Our method analyzes the pointers in a program level by level in terms of their points-to levels, allowing the points-to relations of the pointers at a particular level to be discovered based on the points-to relations of the pointers at this level and higher levels. This level-by-level strategy can enhance the scalability of the FSCS pointer analysis in two fundamental ways, by enabling (1) fast and accurate flowsensitive analysis on full sparse SSA form using a flow-insensitive algorithm and (2) fast and accurate context-sensitive analysis using a full transfer function and a meet function for each procedure. Our level-by-level algorithm, LevPA, gives rises to (1) a precise and compact SSA representation for subsequent program analysis and optimization tasks and (2) a flow- and context-sensitive MAY / MUST mod (modification) set and read set for each procedure. Our preliminary results show that LevPA can analyze some programs with over a million lines of C code in minutes, faster than the state-of-the-art FSCS methods. |
author2 |
The Pennsylvania State University CiteSeerX Archives |
format |
Text |
author |
Hongtao Yu Jingling Xue Wei Huo Xiaobing Feng Zhaoqing Zhang |
author_facet |
Hongtao Yu Jingling Xue Wei Huo Xiaobing Feng Zhaoqing Zhang |
author_sort |
Hongtao Yu |
title |
Level by Level: Making Flow- and Context-Sensitive Pointer Analysis Scalable for Millions of Lines of Code |
title_short |
Level by Level: Making Flow- and Context-Sensitive Pointer Analysis Scalable for Millions of Lines of Code |
title_full |
Level by Level: Making Flow- and Context-Sensitive Pointer Analysis Scalable for Millions of Lines of Code |
title_fullStr |
Level by Level: Making Flow- and Context-Sensitive Pointer Analysis Scalable for Millions of Lines of Code |
title_full_unstemmed |
Level by Level: Making Flow- and Context-Sensitive Pointer Analysis Scalable for Millions of Lines of Code |
title_sort |
level by level: making flow- and context-sensitive pointer analysis scalable for millions of lines of code |
url |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.210.3191 http://www.cse.unsw.edu.au/~jingling/papers/cgo10.pdf |
genre |
The Pointers |
genre_facet |
The Pointers |
op_source |
http://www.cse.unsw.edu.au/~jingling/papers/cgo10.pdf |
op_relation |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.210.3191 http://www.cse.unsw.edu.au/~jingling/papers/cgo10.pdf |
op_rights |
Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
_version_ |
1766216838328352768 |