{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T02:11:30Z","timestamp":1775873490458,"version":"3.50.1"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T00:00:00Z","timestamp":1641945600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2022,1,16]]},"abstract":"<jats:p>\n            Profile-guided optimization (PGO) is an important component in modern compilers. By allowing the compiler to leverage the program\u2019s dynamic behavior, it can often generate substantially faster binaries. Sampling-based profiling is the state-of-the-art technique for collecting execution profiles in data-center environments. However, the lowered profile accuracy caused by sampling fully optimized binary often hurts the benefits of PGO; thus, an important problem is to overcome the inaccuracy in a profile after it is collected. In this paper we tackle the problem, which is also known as\n            <jats:italic>profile inference<\/jats:italic>\n            and\n            <jats:italic>profile rectification<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>We investigate the classical approach for profile inference, based on computing minimum-cost maximum flows in a control-flow graph, and develop an extended model capturing the desired properties of real-world profiles. Next we provide a solid theoretical foundation of the corresponding optimization problem by studying its algorithmic aspects. We then describe a new efficient algorithm for the problem along with its implementation in an open-source compiler. An extensive evaluation of the algorithm and existing profile inference techniques on a variety of applications, including Facebook production workloads and SPEC CPU benchmarks, indicates that the new method outperforms its competitors by significantly improving the accuracy of profile data and the performance of generated binaries.<\/jats:p>","DOI":"10.1145\/3498714","type":"journal-article","created":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T17:03:12Z","timestamp":1642006992000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Profile inference revisited"],"prefix":"10.1145","volume":"6","author":[{"given":"Wenlei","family":"He","sequence":"first","affiliation":[{"name":"Facebook, USA"}]},{"given":"Juli\u00e1n","family":"Mestre","sequence":"additional","affiliation":[{"name":"Facebook, USA \/ University of Sydney, Australia"}]},{"given":"Sergey","family":"Pupyrev","sequence":"additional","affiliation":[{"name":"Facebook, USA"}]},{"given":"Lei","family":"Wang","sequence":"additional","affiliation":[{"name":"Facebook, USA"}]},{"given":"Hongtao","family":"Yu","sequence":"additional","affiliation":[{"name":"Facebook, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,1,12]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja Ravindra K","year":"1993","unstructured":"Ravindra K Ahuja , Thomas L Magnanti , and James B Orlin . 1993 . Network Flows: Theory, Algorithms, and Applications . Prentice-Hall, Inc. , USA. Ravindra K Ahuja, Thomas L Magnanti, and James B Orlin. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc., USA."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/183432.183527"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/102435"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/239912.239923"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290366"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2854038.2854044"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2011.233"},{"key":"e_1_2_2_8_1","volume-title":"An Introduction to Probability Theory and Its Applications","author":"Feller William","unstructured":"William Feller . 1968. An Introduction to Probability Theory and Its Applications . Wiley . William Feller. 1968. An Introduction to Probability Theory and Its Applications. Wiley."},{"key":"e_1_2_2_9_1","volume-title":"Network Flow Theory","author":"Ford L. R.","unstructured":"L. R. Ford . 1956. Network Flow Theory . RAND Corporation , Santa Monica, CA . L. R. Ford. 1956. Network Flow Theory. RAND Corporation, Santa Monica, CA."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76368"},{"key":"e_1_2_2_12_1","unstructured":"Wenlei He and Hongtao Yu. 2020. [llvm-dev] [RFC] Context-sensitive Sample PGO with Pseudo-Instrumentation. https:\/\/lists.llvm.org\/pipermail\/llvm-dev\/2020-August\/144101.html  Wenlei He and Hongtao Yu. 2020. [llvm-dev] [RFC] Context-sensitive Sample PGO with Pseudo-Instrumentation. https:\/\/lists.llvm.org\/pipermail\/llvm-dev\/2020-August\/144101.html"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2004.1281665"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840806"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1214\/18-BA1110"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77560-7_20"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.12783\/dtcse\/aics2016\/8220"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-86838-3_5"},{"key":"e_1_2_2_19_1","volume-title":"Proc. of the 32st International Symposium on Algorithms and Computation.","author":"Mestre Juli\u00e1n","year":"2021","unstructured":"Juli\u00e1n Mestre , Sergey Pupyrev , and Seeun William Umboh . 2021 . On the Extended TSP Problem . In Proc. of the 32st International Symposium on Algorithms and Computation. Juli\u00e1n Mestre, Sergey Pupyrev, and Seeun William Umboh. 2021. On the Extended TSP Problem. In Proc. of the 32st International Symposium on Algorithms and Computation."},{"key":"e_1_2_2_20_1","volume-title":"Proceedings of the International Symposium on the Theory of Switching. Harvard Annals","author":"Moore Edward F.","year":"1959","unstructured":"Edward F. Moore . 1959 . The shortest path through a maze . In Proceedings of the International Symposium on the Theory of Switching. Harvard Annals , Harvard University. 285\u2013292. Edward F. Moore. 1959. The shortest path through a maze. In Proceedings of the International Symposium on the Theory of Switching. Harvard Annals, Harvard University. 285\u2013292."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2020.2982888"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/LLVM-HPC.2014.8"},{"key":"e_1_2_2_23_1","volume-title":"USENIX Annual Technical Conference. USENIX Association, 541\u2013548","author":"Nowak Andrzej","year":"2015","unstructured":"Andrzej Nowak , Ahmad Yasin , Avi Mendelson , and Willy Zwaenepoel . 2015 . Establishing a base of trust with performance counters for enterprise workloads . In USENIX Annual Technical Conference. USENIX Association, 541\u2013548 . Andrzej Nowak, Ahmad Yasin, Avi Mendelson, and Willy Zwaenepoel. 2015. Establishing a base of trust with performance counters for enterprise workloads. In USENIX Annual Technical Conference. USENIX Association, 541\u2013548."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62249"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192374"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO51591.2021.9370314"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2019.8661201"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-006-0008-z"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1982.234772"},{"key":"e_1_2_2_30_1","volume-title":"Proceedings of GCC Summit","author":"Ramasamy Vinodha","year":"2008","unstructured":"Vinodha Ramasamy , Paul Yuan , Dehao Chen , and Robert Hundt . 2008 . Feedback-directed optimizations in GCC with estimated edge profiles from hardware event sampling . In Proceedings of GCC Summit 2008. 87\u2013102. Vinodha Ramasamy, Paul Yuan, Dehao Chen, and Robert Hundt. 2008. Feedback-directed optimizations in GCC with estimated edge profiles from hardware event sampling. In Proceedings of GCC Summit 2008. 87\u2013102."},{"key":"e_1_2_2_31_1","unstructured":"Ching-Yen Shih Drake Svoboda Siao-Jie Su and Wei-Chung Liao. 2021. Static branch prediction for LLVM using machine learning. https:\/\/drakesvoboda.com\/public\/StaticBranchPrediction.pdf  Ching-Yen Shih Drake Svoboda Siao-Jie Su and Wei-Chung Liao. 2021. Static branch prediction for LLVM using machine learning. https:\/\/drakesvoboda.com\/public\/StaticBranchPrediction.pdf"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1971.10"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2697"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/140978296"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39038-8_27"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/192724.192725"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3330345.3330371"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409963.3410490"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851502"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498714","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3498714","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:28Z","timestamp":1750188628000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3498714"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,12]]},"references-count":39,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2022,1,16]]}},"alternative-id":["10.1145\/3498714"],"URL":"https:\/\/doi.org\/10.1145\/3498714","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,12]]},"assertion":[{"value":"2022-01-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}