ABSTRACT
Calling contexts are very important for a wide range of applications such as profiling, debugging, and event logging. Most applications perform expensive stack walking to recover contexts. The resulting contexts are often explicitly represented as a sequence of call sites and hence bulky. We propose a technique to encode the current calling context of any point during an execution. In particular, an acyclic call path is encoded into one number through only integer additions. Recursive call paths are divided into acyclic subsequences and encoded independently. We leverage stack depth in a safe way to optimize encoding: if a calling context can be safely and uniquely identified by its stack depth, we do not perform encoding. We propose an algorithm to seamlessly fuse encoding and stack depth based identification. The algorithm is safe because different contexts are guaranteed to have different IDs. It also ensures contexts can be faithfully decoded. Our experiments show that our technique incurs negligible overhead (1.89% on average). For most medium-sized programs, it can encode all contexts with just one number. For large programs, we are able to encode most calling contexts to a few numbers.
- http://www.cs.purdue.edu/~wsumner/research/cc.Google Scholar
- A. Aho, R. Sethi, and J. Ullman. Compilers: Princiles, Techniques, and Tools. Addison-Wesley, 1986. Google ScholarDigital Library
- G. Ammons, T. Ball, and J. Larus. Exploiting hardware performance counters with flow and context sensitive profiling. In PLDI'97. Google ScholarDigital Library
- T. Ball and J. Larus. Efficient path profiling. In MICRO-29, December 1996. Google ScholarDigital Library
- M. D. Bond and K. S. McKinley. Probabilistic calling context. In OOPSLA'07. Google ScholarDigital Library
- T. M. Chilimbi, B. Liblit, K. Mehra, A. V. Nori, and K. Vaswani. Holmes: Effective statistical debugging via efficient path profiling. In ICSE'09. Google ScholarDigital Library
- R. Jones and C. Ryder. A study of java object demographics. In ISMM'08. Google ScholarDigital Library
- R. Joshi, M. D. Bond, and C. Zilles. Targeted path profiling: Lower overhead path profiling for staged dynamic optimization systems. In CGO'04. Google ScholarDigital Library
- Z. Lai, S. C. Cheung, and W. K. Chan. Inter-context control-flow and data-flow test adequacy criteria for nesc applications. In FSE'08. Google ScholarDigital Library
- James R. Larus. Whole program paths. In PLDI'99. Google ScholarDigital Library
- Z. Lin, X. Jiang, D. Xu, and X. Zhang. Automatic protocol format reverse engineering through context-aware monitored execution. In NDSS'08.Google Scholar
- D. Melski and T. Reps. Interprocedural path profiling. In CC'99. Google ScholarDigital Library
- T. Mytkowicz, D. Coughlin, and A. Diwan. Inferred call path profiling. In OOPSLA'09. Google ScholarDigital Library
- G. C. Necula, S. McPeak, S. P. Rahul, and W. Weimer. Cil: Intermediate language and tools for analysis and transformation of c programs. In CC'02. Google ScholarDigital Library
- N. Nethercote and J. Seward. Valgrind: A framework for heavyweight dynamic binary instrumentation. In PLDI'07. Google ScholarDigital Library
- T. Reps, T. Ball, M. Das, and J. Larus. The use of program profiling for software maintenance with applications to the year 2000 problem. In FSE'97. Google ScholarDigital Library
- J. M. Spivey. Fast, accurate call graph profiling. Softw. Pract. Exper., 34(3):249--264, 2004. Google ScholarDigital Library
- K. Vaswani, A. V. Nori, and T. M. Chilimbi. Preferential path profiling: compactly numbering interesting paths. In POPL'07. Google ScholarDigital Library
- A. Villazon, W. Binder, and P. Moret. Flexible calling context reification for aspect-oriented programming. In AOSD'09. Google ScholarDigital Library
- B. Wiedermann. Know your place: Selectively executing statements based on context. Technical Report TR-07-38, University of Texas at Austin, 2007.Google Scholar
- X. Zhang, A. Navabi, and S. Jagannathan. Alchemist: A transparent dependence distance profiling infrastructure. In CGO'09. Google ScholarDigital Library
- X. Zhang, S. Tallam, and R. Gupta. Dynamic slicing long running programs through execution fast forwarding. In FSE'06. Google ScholarDigital Library
- X. Zhuang, M. Serrano, H. Cain, and J. Choi. Accurate, efficient, and adaptive calling context profiling. In PLDI'06. Google ScholarDigital Library
Recommendations
DeltaPath: Precise and Scalable Calling Context Encoding
CGO '14: Proceedings of Annual IEEE/ACM International Symposium on Code Generation and OptimizationCalling context provides important information for a large range of applications, such as event logging, profiling, debugging, anomaly detection, and performance optimization. While some techniques have been proposed to track calling context efficiently,...
Valence: variable length calling context encoding
CC 2019: Proceedings of the 28th International Conference on Compiler ConstructionMany applications, including program optimizations, debugging tools, and event loggers, rely on calling context to gain additional insight about how a program behaves during execution. One common strategy for determining calling contexts is to use ...
Probabilistic calling context
Proceedings of the 2007 OOPSLA conferenceCalling context enhances program understanding and dynamic analyses by providing a rich representation of program location. Compared to imperative programs, object-oriented programs use more interprocedural and less intraprocedural control flow, ...
Comments