Cycle elimination for invocation graph-based context-sensitive pointer analysis

Cited 2 time in webofscience Cited 0 time in scopus
  • Hit : 350
  • Download : 0
Context: Pointer analysis is an important building block of optimizing compilers and program analyzers for C language. Various methods with precision and performance trade-offs have been proposed. Among them, cycle elimination has been successfully used to improve the scalability of context-insensitive pointer analyses without losing any precision. Objective: In this article, we present a new method on context-sensitive pointer analysis with an effective application of cycle elimination. Method: To obtain similar benefits of cycle elimination for context-sensitive analysis, we propose a novel constraint-based formulation that uses sets of contexts as annotations. Our method is not based on binary decision diagram (BDD). Instead, we directly use invocation graphs to represent context sets and apply a hash-consing technique to deal with the exponential blow-up of contexts. Result: Experimental results on C programs ranging from 20,000 to 290,000 lines show that applying cycle elimination to our new formulation results in 4.5 xspeedup over the previous BDD-based approach. Conclusion: We showed that cycle elimination is an effective method for improving the scalability of context-sensitive pointer analysis. (C) 2011 Elsevier B.V. All rights reserved.
Publisher
ELSEVIER SCIENCE BV
Issue Date
2011-08
Language
English
Article Type
Article
Citation

INFORMATION AND SOFTWARE TECHNOLOGY, v.53, no.8, pp.818 - 833

ISSN
0950-5849
URI
http://hdl.handle.net/10203/95815
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 2 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0