{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T16:41:03Z","timestamp":1761324063192,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,8,22]],"date-time":"2016-08-22T00:00:00Z","timestamp":1471824000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Early Career Scheme of the Research Grants Council of Hong Kong","award":["11200015, 11201114, 111313, 125113 and 123512"],"award-info":[{"award-number":["11200015, 11201114, 111313, 125113 and 123512"]}]},{"name":"General Research Fund"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Softw. Eng. Methodol."],"published-print":{"date-parts":[[2016,8,22]]},"abstract":"<jats:p>\n            <jats:italic>Complete dynamic control flow<\/jats:italic>\n            is a fundamental kind of execution profile about program executions with a wide range of applications. Tracing the dynamic control flow of program executions for a brief period easily generates a trace consisting of billions of control flow events. The number of events in such a trace is large, making both path tracing and path querying to incur significant slowdowns. A major class of path tracing techniques is to design novel trace representations that can be generated efficiently, and encode the inputted sequences of such events so that the inputted sequences are still derivable from the encoded and smaller representations. The control flow semantics in such representations have, however, become obscure, which makes implementing path queries on such a representation inefficient and the design of such queries complicated. We propose a novel two-phase path tracing framework\u2014\n            <jats:italic>Hierarchical Program Path<\/jats:italic>\n            (HPP)\u2014to model the\n            <jats:italic>complete<\/jats:italic>\n            dynamic control flow of an arbitrary number of executions of a program. In Phase 1, HPP monitors each execution, and efficiently generates a stream of events, namely HPPTree, representing a novel tree-based representation of control flow for each thread of control in the execution. In Phase 2, given a set of such event streams, HPP identifies all the equivalent instances of the same exercised\n            <jats:italic>interprocedural<\/jats:italic>\n            path in all the corresponding HPPTree instances, and represents each such equivalent set of paths with a single subgraph, resulting in our compositional graph-based trace representation, namely, HPPDAG. Thus, an HPPDAG instance has the potential to be significantly smaller in size than the corresponding HPPTree instances, and still completely preserves the control flow semantics of the traced executions. Control flow queries over all the traced executions can also be directly performed on the single HPPDAG instance instead of separately processing the trace representation of each execution followed by aggregating their results. We validate HPP using the SPLASH2 and SPECint 2006 benchmarks. Compared to the existing technique, named BLPT (Ball-Larus-based Path Tracing), HPP generates significantly smaller trace representations and incurs fewer slowdowns to the native executions in online tracing of Phase 1. The HPPDAG instances generated in Phase 2 are significantly smaller than their corresponding BLPT and HPPTree traces. We show that HPPDAG supports efficient backtrace querying, which is a representative path query based on complete control flow trace. Finally, we illustrate the ease of use of HPPDAG by building a novel and highly efficient path profiling technique to demonstrate the applicability of HPPDAG.\n          <\/jats:p>","DOI":"10.1145\/2963094","type":"journal-article","created":{"date-parts":[[2016,8,26]],"date-time":"2016-08-26T12:25:39Z","timestamp":1472214339000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Hierarchical Program Paths"],"prefix":"10.1145","volume":"25","author":[{"given":"Chunbai","family":"Yang","sequence":"first","affiliation":[{"name":"City University of Hong Kong, Kowloon Tong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shangru","family":"Wu","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Kowloon Tong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"W. K.","family":"Chan","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Kowloon Tong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,8,22]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/93542.93576"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/1629575.1629594"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/1065010.1065035"},{"volume-title":"Proceedings of the 29th Annual ACM\/IEEE International Symposium on Microarchitecture (MICRO29)","author":"Ball Thomas","unstructured":"Thomas Ball and James R. Larus . 1996. Efficient path profiling . In Proceedings of the 29th Annual ACM\/IEEE International Symposium on Microarchitecture (MICRO29) . IEEE Computer Society, Washington, DC, 46--57. Thomas Ball and James R. Larus. 1996. Efficient path profiling. In Proceedings of the 29th Annual ACM\/IEEE International Symposium on Microarchitecture (MICRO29). IEEE Computer Society, Washington, DC, 46--57.","key":"e_1_2_1_4_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1145\/1012888.1005708"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1109\/TC.2005.186"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1109\/TSE.2014.2301725"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1109\/ICSE.2009.5070506"},{"unstructured":"CLANG 3.5. 2015. http:\/\/clang.llvm.org\/.  CLANG 3.5. 2015. http:\/\/clang.llvm.org\/.","key":"e_1_2_1_9_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/2509136.2509521"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/378993.379241"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1145\/1543135.1542490"},{"key":"e_1_2_1_13_1","volume-title":"The GNU Project Debugger. Retrieved","author":"GDB","year":"2015","unstructured":"GDB : The GNU Project Debugger. Retrieved May 2015 from http:\/\/www.gnu.org\/software\/gdb\/. GDB: The GNU Project Debugger. Retrieved May 2015 from http:\/\/www.gnu.org\/software\/gdb\/."},{"key":"e_1_2_1_14_1","volume-title":"GNU gzip v1.4","author":"GZIP","year":"2010","unstructured":"GZIP : GNU gzip v1.4 . 2010 . Retrieved May 2015 from http:\/\/www.gnu.org\/software\/gzip\/. GZIP: GNU gzip v1.4. 2010. Retrieved May 2015 from http:\/\/www.gnu.org\/software\/gzip\/."},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/2483760.2483769"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/781498.781530"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1145\/1186736.1186737"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1145\/2491956.2462167"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1145\/778553.778554"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1145\/1356058.1356071"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1145\/301618.301678"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.5555\/977395.977673"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.5555\/776816.776854"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1016\/j.jss.2012.01.046"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1016\/j.jss.2006.06.007"},{"volume-title":"Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS\u201999 (CC\u201999)","author":"Melski David","unstructured":"David Melski and Thomas W. Reps . 1999. Interprocedural path profiling . In Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS\u201999 (CC\u201999) , Stefan J\u00e4hnichen (Ed.). Springer-Verlag, London, UK, 47--62. David Melski and Thomas W. Reps. 1999. Interprocedural path profiling. In Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS\u201999 (CC\u201999), Stefan J\u00e4hnichen (Ed.). Springer-Verlag, London, UK, 47--62.","key":"e_1_2_1_26_1"},{"volume-title":"Proceedings of the Conference on Data Compression (DCC\u201997)","author":"Craig","unstructured":"Craig G. Nevill-Manning and Ian H. Witten. 1997. Linear-time, incremental hierarchy inference for compression . In Proceedings of the Conference on Data Compression (DCC\u201997) . IEEE Computer Society, Washington, DC, 3--11. Craig G. Nevill-Manning and Ian H. Witten. 1997. Linear-time, incremental hierarchy inference for compression. In Proceedings of the Conference on Data Compression (DCC\u201997). IEEE Computer Society, Washington, DC, 3--11.","key":"e_1_2_1_27_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1109\/ASE.2013.6693096"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1145\/2025113.2025206"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1145\/1081706.1081721"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1109\/CGO.2009.11"},{"doi-asserted-by":"publisher","key":"e_1_2_1_32_1","DOI":"10.5555\/645989.674305"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1145\/1806799.1806875"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.5555\/977395.977659"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1109\/PACT.2005.22"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1145\/1273463.1273494"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1109\/MC.1984.1659158"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1145\/223982.223990"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1145\/1375581.1375611"},{"doi-asserted-by":"publisher","key":"e_1_2_1_40_1","DOI":"10.1145\/2560047"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1109\/MICRO.2004.37"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.1145\/378795.378835"},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.1145\/1152154.1152180"}],"container-title":["ACM Transactions on Software Engineering and Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2963094","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2963094","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:04Z","timestamp":1750222444000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2963094"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,22]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,8,22]]}},"alternative-id":["10.1145\/2963094"],"URL":"https:\/\/doi.org\/10.1145\/2963094","relation":{},"ISSN":["1049-331X","1557-7392"],"issn-type":[{"type":"print","value":"1049-331X"},{"type":"electronic","value":"1557-7392"}],"subject":[],"published":{"date-parts":[[2016,8,22]]},"assertion":[{"value":"2015-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}