Context-Sensitive Pointer Analysis Based On Procedural Summaries

Kim, Hong-Seok

Permalink

https://hdl.handle.net/2142/10948 Copy

Description

Title

Context-Sensitive Pointer Analysis Based On Procedural Summaries

Author(s)

Kim, Hong-Seok

Issue Date

2004-12

Keyword(s)

computer science

Abstract

This dissertation addresses the scalability problem of context-sensitive pointer analysis based on Andersen's inclusion-based approach. The key observation is that procedures without any observable effects on callers, roughly termed procedural side effects, are never involved in the generation of spurious interprocedural dataflow. Therefore, by carefully migrating procedural side effects from callees to callers, we can transform a program into a side-effect free form yet with the same overall pointer information. In such a case, the scalability of the overall algorithm is determined by the size of procedural summaries propagated during the bottom-up phase. To reduce the size of procedural summaries, we have developed a number of simplification algorithms that produce an observably equivalent yet smaller procedural summaries. Overall, the accuracy of the proposed context-sensitive analysis is equivalent to that achieved by exhaustively inlining all procedure calls with the exception for recursive calls. On the other hand, thanks to the simplification algorithms, the scalability of the proposed context-sensitive analysis is comparable to that achieved by context-insensitive analysis.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/10948

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections