Incremental Points-to Analysis for Java via Edit Propagation

详细信息    查看全文

• 作者：Yuting Chen (15)
  Qiuwei Shi (15) (16)
  Weikai Miao (16)
  
  15. School of Software ; Shanghai Jiao Tong University ; Shanghai ; 200240 ; China
  16. School of Software ; East China Normal University ; Shanghai ; 200062 ; China
  
• 关键词：Constraint solving ; Incremental Points ; to Analysis ; Edit propagation
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：8979
• 期：1
• 页码：164-178
• 全文大小：900 KB
• 参考文献：1. Steensgaard, B Points-to analysis in almost linear time. In: Boehm Jr., HJ, Shackle, GLS eds. (1996) POPL. ACM Press, New York, pp. 32-41
  2. Andersen, L.O.: Program analysis and specialization for the c programming language. Master鈥檚 thesis, University of Copenhagen (1994)
  3. M茅ndez-Lojo, M, Mathew, A, Pingali, K Parallel inclusion-based points-to analysis. In: Cook, WR, Clarke, S, Rinard, MC eds. (2010) OOPSLA. ACM, New York, pp. 428-443
  4. M茅ndez-Lojo, M, Burtscher, M, Pingali, K A gpu implementation of inclusion-based points-to analysis. In: Ramanujam, J, Sadayappan, P eds. (2012) PPOPP. ACM, New Yorkpp. 107
  5. Lhot谩k, O, Smaragdakis, Y, Sridharan, M (2013) Pointer analysis (dagstuhl seminar 13162). Dagstuhl Rep. 3: pp. 91-113
  6. Rountev, A, Kagan, S, Marlowe, T Interprocedural dataflow analysis in the presence of large libraries. In: Mycroft, A, Zeller, A eds. (2006) Compiler Construction. Springer, Heidelberg, pp. 2-16 CrossRef
  7. Chase, DR, Wegman, MN, Zadeck, FK Analysis of pointers and structures. In: Fischer, BN eds. (1990) PLDI. ACM, New York, pp. 296-310
  8. Hardekopf, B., Lin, C.: Flow-sensitive pointer analysis for millions of lines of code. In: IEEE CGO, pp. 289鈥?98 (2011)
  9. Lu, Y, Shang, L, Xie, X, Xue, J An incremental points-to analysis with CFL-reachability. In: Jhala, R, Bosschere, K eds. (2013) Compiler Construction. Springer, Heidelberg, pp. 61-81 CrossRef
  10. Jenista, J, Eom, Y, Demsky, B Using disjoint reachability for parallelization. In: Knoop, J eds. (2011) Compiler Construction. Springer, Heidelberg, pp. 198-224 CrossRef
  11. Vallee-Rai, R., Hendren, L.J.: Jimple: Simplifying java bytecode for analyses and transformations (1998)
  12. Lhot谩k, O, Hendren, L Scaling java points-to analysis using SPARK. In: Hedin, G eds. (2003) Compiler Construction. Springer, Heidelberg, pp. 153-169 CrossRef
  13. Gall, H, Fluri, B, Pinzger, M (2009) Change analysis with evolizer and changedistiller. IEEE Softw. 26: pp. 26-33 CrossRef
  14. Fluri, B, W眉rsch, M, Pinzger, M, Gall, H (2007) Change distilling: tree differencing for fine-grained source code change extraction. IEEE Trans. Softw. Eng. 33: pp. 725-743 CrossRef
  15. Vall茅e-Rai, RCP, Gagnon, E, Hendren, LJ, Lam, P, Sundaresan, V CASCON. In: MacKay, SA, Johnson, JH eds. (1999) Soot-A Java Bytecode Optimization Framework. IBM, San Diegopp. 13
  16. Hardekopf, B, Lin, C The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code. In: Ferrante, J, McKinley, KS eds. (2007) PLDI. ACM, New York, pp. 290-299
  17. Tok, TB, Guyer, SZ, Lin, C Efficient flow-sensitive interprocedural data-flow analysis in the presence of pointers. In: Mycroft, A, Zeller, A eds. (2006) Compiler Construction. Springer, Heidelberg, pp. 17-31 CrossRef
  18. Hardekopf, B, Lin, C Semi-sparse flow-sensitive pointer analysis. In: Shao, Z, Pierce, BC eds. (2009) POPL. ACM, New York, pp. 226-238
  19. Gulwani, S, Srivastava, S, Venkatesan, R Program analysis as constraint solving. In: Gupta, R, Amarasinghe, SP eds. (2008) PLDI. ACM, New York, pp. 281-292 CrossRef
  20. Visser, W, Geldenhuys, J, Dwyer, MB Green: reducing, reusing and recycling constraints in program analysis. In: Tracz, W, Robillard, MP, Bultan, T eds. (2012) SIGSOFT FSE. ACM, New Yorkpp. 58
  21. Allen, JR, Kennedy, K, Porterfield, C, Warren, JD Conversion of control dependence to data dependence. In: Wright, JR, Landweber, L, Demers, AJ, Teitelbaum, T eds. (1983) POPL. ACM, New York, pp. 177-189
  22. Pollock, LL, Soffa, ML (1989) An incremental version of iterative data flow analysis. IEEE Trans. Soft. Eng. 15: pp. 1537-1549 CrossRef
  23. Burke, MG, Ryder, BG (1990) A critical analysis of incremental iterative data flow analysis algorithms. IEEE Trans. Soft. Eng. 16: pp. 723-728 CrossRef
  24. Carroll, S, Polychronopoulos, CD (2004) A framework for incremental extensible compiler construction. Int. J. Parallel Program. 32: pp. 289-316 CrossRef
  25. Carroll, S, Polychronopoulos, CD A framework for incremental extensible compiler construction. In: Banerjee, U, Gallivan, K, Gonz谩lez, A eds. (2003) ICS. ACM, New York, pp. 53-62
  26. Yur, JS, Ryder, BG, Landi, W An incremental flow- and context-sensitive pointer aliasing analysis. In: Boehm, BW, Garlan, D, Kramer, J eds. (1999) ICSE. ACM, New York, pp. 442-451 CrossRef
  27. Vivien, F, Rinard, MC Incrementalized pointer and escape analysis. In: Burke, M, Soffa, ML eds. (2001) PLDI. ACM, New York, pp. 35-46
  28. Saha, D, Ramakrishnan, CR Incremental and demand-driven points-to analysis using logic programming. In: Barahona, P, Felty, AP eds. (2005) PPDP. ACM, New York, pp. 117-128
  29. Kodumal, J, Aiken, A Banshee: a scalable constraint-based analysis toolkit. In: Hankin, C, Siveroni, I eds. (2005) Static Analysis. Springer, Heidelberg, pp. 218-234 CrossRef
  
• 作者单位：Structured Object-Oriented Formal Language and Method
• 丛书名：978-3-319-17403-7
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Points-to analysis is a static analysis technique which computes the relationships between the program variables and the heap references. It has been widely used in program optimization, program understanding, and error detection. Inclusion-based points-to analysis computes the points-to sets in a program by translating the program into a set of inclusion constraints on the points-to sets and then solving them to yield the desired results. Yet the analysis faces a difficulty in that a program can be frequently changed in its development, and great efforts may be exhausted to re-generate the inclusion constraints and re-solve them. In this paper, we extend the inclusion-based points-to analysis to an incremental one called Inc-PTA. The essential idea of Inc-PTA is to sum up the program changes into an editscript of a sequence of successive edits, and then to propagate the edits to the constraints followed by taking a demand-driven points-to analysis of the program. We also discuss about the correctness of Inc-PTA, and believe that Inc-PTA can provide with a cost-effective solution to incremental points-to analysis.