logo

SCIENCE CHINA Information Sciences, Volume 59, Issue 5: 052104(2016) https://doi.org/10.1007/s11432-015-5418-3

A new method to encode calling contexts with recursions

More info
  • ReceivedJan 10, 2015
  • AcceptedJun 8, 2015
  • PublishedApr 12, 2016

Abstract

Calling context encoding (CCE) uses some integers to represent the current context of any execution point, and is valuable in a wide range of applications. Existing studies already ensure accurate results of CCE, but they use stack to store the encoding when recursive calls happen. This may cost much for cyclic call graphs with deep recursive calls. This paper presents a novel approach (called RCCE) to address this problem. With a modified strategy for encoding, it requires less frequent access of the stack and gives more succinct representation of contexts on deep recursion. Experimental results show that compared to Precise Calling Context Encoding, RCCE is more practical and efficient on calling contexts with recursions.


Acknowledgment

Acknowledgments

This work was supported partially by National Natural Science Foundation of China (Grant No. 61402103), and Jiangsu Natural Science Foundation (Grant Nos. BK20130633, BK20140644).


References

[1] Sumner W N, Zheng Y, Weeratunge D, et al. Precise calling context encoding. In: Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering (ICSE), Cape Town, 2010. 525-534. Google Scholar

[2] Sumner W N, Zheng Y, Weeratunge D, et al. IEEE Trans Softw Eng, 2012, 38: 1160-1177 Google Scholar

[3] Ball T, Larus J R. Efficient path profiling. In: Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture (MICRO), Paris, 1996. 46-57. Google Scholar

[4] Li B, Wang L, Leung H, et al. J Syst Softw, 2012, 85: 1558-1576 Google Scholar

[5] Vaswani K, Nori A V, Chilimbi T M. Preferential path profiling: compactly numbering interesting paths. In: Proceedings of the 34th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), Nice, 2007. 351-362. Google Scholar

[6] Apiwattanapong T, Harrold M J. Selective path profiling. In: Proceedings of the 2002 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis For Software Tools and Engineering (PASTE), Charleston, 2002. 35-42. Google Scholar

[7] Bond M D, McKinley K S. Practical path profiling for dynamic optimizers. In: Proceedings of the 3rd IEEE/ACM International Symposium on Code Generation and Optimization (CGO), San Jose, 2005. 205-216. Google Scholar

[8] Tallam S, Zhang X, Gupta R. Extending path profiling across loop backedges and procedure boundaries. In: Proceedings of the 2nd IEEE/ACM International Symposium on Code Generation and Optimization (CGO), San Jose, 2004. 251-264. Google Scholar

[9] Roy S, Srikant Y N. Profiling k-iteration paths: a generalization of the Ball-Larus profiling algorithm. In: Proceedings of the 7th International Symposium on Code Generation and Optimization (CGO), Seattle, 2009. 70-80. Google Scholar

[10] Joshi R, Bond M D, Zilles C. Targeted path profiling: lower overhead path profiling for staged dynamic optimization systems. In: Proceedings of the 2nd IEEE/ACM International Symposium on Code Generation and Optimization (CGO), San Jose, 2004. 239-250. Google Scholar

[11] Zhuang X, Serrano M J, Cain H W. Accurate, efficient, and adaptive calling context profiling. In: Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), Ottawa, 2006. 263-271. Google Scholar

[12] Ammons G, Ball T, Larus J R. Exploiting hardware performance counters with flow and context sensitive profiling. In: Proceedings of the ACM SIGPLAN'97 Conference on Programming Language Design and Implementation (PLDI), Las Vegas, 1997. 85-96. Google Scholar

[13] Nethercote N, Seward J. Valgrind: a framework for heavyweight dynamic binary instrumentation. In: Proceedings of the ACM SIGPLAN 2007 Conference on Programming Language Design and Implementation, San Diego, 2007. 89-100. Google Scholar

[14] Spivey J M. Softw Pract Exper, 2004, 34: 249-264 Google Scholar

[15] Villazon A, Binder W, Moret P. Flexible calling context reification for aspect-oriented programming. In: Proceedings of the 8th International Conference on Aspect-Oriented Software Development (AOSD), Charlottesville, 2009. 63-74. Google Scholar

[16] Bernat A R, Miller B P. Concurr Comput Pract Exper, 2007, 19: 1533-1547 Google Scholar

[17] Bond M D, McKinley K S. Probabilistic calling context. In: Proceedings of the 22nd Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), Montreal, 2007. 97-111. Google Scholar

[18] Mytkowicz T, Coughlin D, Diwan A. Inferred call path profiling. In: Proceedings of the 24th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), Orlando, 2009. 175-189. Google Scholar

[19] Zeng Q, Rhee J, Zhang H, et al. DeltaPath: precise and scalable calling context encoding. In: Proceedings of the 12th IEEE/ACM International Symposium on Code Generation and Optimization (CGO), Orlando, 2014. 109-119. Google Scholar

[20] Li J J, Wang Z J, Wu C G, et al. Dynamic and adaptive calling context encoding. In: Proceedings of the 12th IEEE/ACM International Symposium on Code Generation and Optimization (CGO), Orlando, 2014. 120-131. Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1