{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T00:48:34Z","timestamp":1772498914178,"version":"3.50.1"},"reference-count":75,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:00:00Z","timestamp":1605225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"crossref","award":["406377\/2018-9"],"award-info":[{"award-number":["406377\/2018-9"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2020,11,13]]},"abstract":"<jats:p>\n            Academia has spent much effort into making context-sensitive\n            <jats:italic>analyses<\/jats:italic>\n            practical, with great profit. However, the implementation of context-sensitive\n            <jats:italic>optimizations<\/jats:italic>\n            , in contrast to analyses, is still not practical, due to code-size explosion. This growth happens because current technology requires the cloning of full paths in the Calling Context Tree. In this paper, we present a solution to this problem. We combine finite state machines and dynamic dispatching to allow fully context-sensitive specialization while cloning only functions that are effectively optimized. This technique makes it possible to apply very liberal optimizations, such as context-sensitive constant propagation, in large programs\u2014something that could not have been easily done before. We demonstrate the viability of our idea by formalizing it in Prolog, and implementing it in LLVM. As a proof of concept, we have used our state machines to implement context-sensitive constant propagation in LLVM. The binaries produced by traditional full cloning are 2.63 times larger than the binaries that we generate with our state machines. When applied on Mozilla Firefox, our optimization increases binary size from 7.2MB to 9.2MB. Full cloning, in contrast, yields a binary of 34MB.\n          <\/jats:p>","DOI":"10.1145\/3428235","type":"journal-article","created":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T23:40:14Z","timestamp":1606261214000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Dynamic dispatch of context-sensitive optimizations"],"prefix":"10.1145","volume":"4","author":[{"given":"Gabriel","family":"Poesia","sequence":"first","affiliation":[{"name":"Stanford University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0375-1657","authenticated-orcid":false,"given":"Fernando Magno Quint\u00e3o","family":"Pereira","sequence":"additional","affiliation":[{"name":"Federal University of Minas Gerais, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,11,13]]},"reference":[{"key":"e_1_2_2_1_1","first-page":"589","article-title":"Runtime Pointer Disambiguation. In OOPSLA. ACM, New York","author":"Alves P\u00e9ricles","year":"2015","journal-title":"NY, USA"},{"key":"e_1_2_2_2_1","volume-title":"Damien Octeau, and Patrick McDaniel.","author":"Arzt Steven","year":"2014"},{"key":"e_1_2_2_3_1","first-page":"867","article-title":"k-Calling Context Profiling. In OOPSLA. ACM, New York","author":"Ausiello Giorgio","year":"2012","journal-title":"NY, USA"},{"key":"e_1_2_2_4_1","first-page":"46","article-title":"Eficient Path Profiling","author":"Ball Thomas","year":"1996","journal-title":"MICRO. IEEE Computer Society, USA"},{"key":"e_1_2_2_5_1","volume-title":"Guyer","author":"Bond Michael D.","year":"2010"},{"key":"e_1_2_2_6_1","first-page":"97","article-title":"Probabilistic Calling Context. In OOPSLA. ACM, New York","author":"Bond Michael D.","year":"2007","journal-title":"NY, USA"},{"key":"e_1_2_2_7_1","volume-title":"Proc. ACM Program. Lang. 2, POPL (Dec. 2017 ), 14 : 1-14 : 28","author":"Brown Matt","year":"2017"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3185768.3185771"},{"key":"e_1_2_2_9_1","doi-asserted-by":"crossref","unstructured":"Keith D Cooper Mary W Hall and Ken Kennedy. 1993. A Methodology for Procedure Cloning. Comput. Lang. 19 2 ( 1993 ) 105-117.  Keith D Cooper Mary W Hall and Ken Kennedy. 1993. A Methodology for Procedure Cloning. Comput. Lang. 19 2 ( 1993 ) 105-117.","DOI":"10.1016\/0096-0551(93)90005-L"},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","unstructured":"Dibyendu Das. 2003. Function inlining versus function cloning. ACM SIGPLAN Notices 38 6 ( 2003 ) 23-29.  Dibyendu Das. 2003. Function inlining versus function cloning. ACM SIGPLAN Notices 38 6 ( 2003 ) 23-29.","DOI":"10.1145\/885638.885645"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/207110.207119"},{"key":"e_1_2_2_12_1","volume-title":"Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis","author":"Dean Jefrey"},{"key":"e_1_2_2_13_1","first-page":"42","article-title":"Compiling Generics Through User-directed Type Specialization. In ICOOOLPS. ACM, New York","author":"Dragos Iulian","year":"2009","journal-title":"NY, USA"},{"key":"e_1_2_2_14_1","first-page":"242","article-title":"Context-sensitive Interprocedural Points-to Analysis in the Presence of Function Pointers. In PLDI. ACM, New York","author":"Emami Maryam","year":"1994","journal-title":"NY, USA"},{"key":"e_1_2_2_15_1","first-page":"253","article-title":"Scalable Context-sensitive Flow Analysis Using Instantiation Constraints. In PLDI. ACM, New York","author":"F\u00e4hndrich Manuel","year":"2000","journal-title":"NY, USA"},{"key":"e_1_2_2_16_1","volume-title":"Apposcopy: Semantics-based Detection of Android Malware Through Static Analysis. In FSE","author":"Feng Yu","year":"2014"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428288"},{"key":"e_1_2_2_18_1","first-page":"465","article-title":"Trace-based Just-in-time Type Specialization for Dynamic Languages. In PLDI. ACM, New York","author":"Gal Andreas","year":"2009","journal-title":"NY, USA"},{"key":"e_1_2_2_19_1","first-page":"1","article-title":"Is It a Tree, a DAG, or a Cyclic Graph? A Shape Analysis for Heap-directed Pointers in C. In POPL. ACM, New York","author":"Ghiya Rakesh","year":"1996","journal-title":"NY, USA"},{"key":"e_1_2_2_20_1","volume-title":"JavaTM Just-in-Time Compiler and Virtual Machine Improvements for Server and Middleware Applications","author":"Grcevski Nikola"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/263698.264352"},{"key":"e_1_2_2_22_1","volume-title":"Modern Compiler Design","author":"Grune Dick","edition":"2"},{"key":"e_1_2_2_23_1","first-page":"239","article-title":"Fast and Precise Hybrid Type Inference for JavaScript. In PLDI. ACM, New York","author":"Hackett Brian","year":"2012","journal-title":"NY, USA"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/325478.325519"},{"key":"e_1_2_2_26_1","doi-asserted-by":"crossref","volume-title":"Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches","author":"H\u00f6lzle Urs","DOI":"10.1007\/BFb0057013"},{"key":"e_1_2_2_27_1","first-page":"53","article-title":"Eficient Context Sensitivity for Dynamic Analyses via Calling Context Uptrees and Customized Memory Management. In OOPSLA. ACM, New York","author":"Huang Jipeng","year":"2013","journal-title":"NY, USA"},{"key":"e_1_2_2_28_1","first-page":"246","article-title":"A Trace-Based Java JIT Compiler Retrofitted from a Method-Based Compiler","author":"Inoue Hiroshi","year":"2011","journal-title":"CGO. IEEE Computer Society, USA"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133924"},{"key":"e_1_2_2_30_1","volume-title":"Allen","author":"Kennedy Ken","year":"2002"},{"key":"e_1_2_2_31_1","volume-title":"Data Flow Analysis: Theory and Practice","author":"Khedker Uday","edition":"1"},{"key":"e_1_2_2_32_1","doi-asserted-by":"crossref","unstructured":"Anton Korobeynikov. 2007. Improving Switch Lowering for the LLVM Compiler System. In SYRCoSE. RAS Innopolis Russia A.I-A.V.  Anton Korobeynikov. 2007. Improving Switch Lowering for the LLVM Compiler System. In SYRCoSE. RAS Innopolis Russia A.I-A.V.","DOI":"10.15514\/SYRCOSE-2007-1-2"},{"key":"e_1_2_2_33_1","volume-title":"Adve","author":"Lattner Chris","year":"2004"},{"key":"e_1_2_2_34_1","first-page":"278","article-title":"Making Context-sensitive Points-to Analysis with Heap Cloning Practical for the Real World. In PLDI. ACM, New York","author":"Lattner Chris","year":"2007","journal-title":"NY, USA"},{"key":"e_1_2_2_35_1","first-page":"126","article-title":"Dominance-based Duplication Simulation (DBDS): Code Duplication to Enable Compiler Optimizations. In CGO. ACM, New York","author":"Leopoldseder David","year":"2018","journal-title":"NY, USA"},{"key":"e_1_2_2_36_1","doi-asserted-by":"crossref","volume-title":"Context-Sensitive Points-to Analysis: Is It Worth It?","author":"Lhot\u00e1k Ond\u0159ej","DOI":"10.1007\/11688839_5"},{"key":"e_1_2_2_37_1","first-page":"85","article-title":"Precise and Scalable Context-sensitive Pointer Analysis via Value Flow Graph. In ISMM. ACM, New York","author":"Li Lian","year":"2013","journal-title":"NY, USA"},{"key":"e_1_2_2_38_1","doi-asserted-by":"crossref","unstructured":"Yue Li Tian Tan Anders Moller and Yannis Smaragdakis. 2020. A Principled Approach to Selective Context Sensitivityfor Pointer Analysis. TOPLAS To-Appear 1 ( 2020 ) 1-40.  Yue Li Tian Tan Anders Moller and Yannis Smaragdakis. 2020. A Principled Approach to Selective Context Sensitivityfor Pointer Analysis. TOPLAS To-Appear 1 ( 2020 ) 1-40.","DOI":"10.1145\/3381915"},{"key":"e_1_2_2_39_1","doi-asserted-by":"crossref","unstructured":"Caio Lima Junio Cezar R. da Silva Guilherme V. Leobas Erven Rohou and Fernando Magno Quint\u00e3o Pereira. 2020. Guided just-in-time specialization. Sci. Comput. Program. 185 Article 2 ( 2020 ) 39 pages.  Caio Lima Junio Cezar R. da Silva Guilherme V. Leobas Erven Rohou and Fernando Magno Quint\u00e3o Pereira. 2020. Guided just-in-time specialization. Sci. Comput. Program. 185 Article 2 ( 2020 ) 39 pages.","DOI":"10.1016\/j.scico.2019.102318"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/176454.176526"},{"key":"e_1_2_2_41_1","first-page":"305","article-title":"Resolving and Exploiting the k-CFA Paradox: Illuminating Functional vs. Object-oriented Program Analysis. In PLDI. ACM, New York","author":"Might Matthew","year":"2010","journal-title":"NY, USA"},{"key":"e_1_2_2_42_1","first-page":"25","article-title":"Light Context-sensitive Points-to Analysis for Java. In PASTE. ACM, New York","author":"Milanova Ana","year":"2007","journal-title":"NY, USA"},{"key":"e_1_2_2_43_1","first-page":"99","article-title":"CFL-reachability and Context-sensitive Integrity Types. In PPPJ. ACM, New York","author":"Milanova Ana","year":"2014","journal-title":"NY, USA"},{"key":"e_1_2_2_44_1","volume-title":"Ryder","author":"Milanova Ana","year":"2004"},{"key":"e_1_2_2_45_1","volume-title":"Principles of Program Analysis","author":"Nielson Flemming"},{"key":"e_1_2_2_46_1","first-page":"475","article-title":"Selective Context-sensitivity Guided by Impact Pre-analysis. In PLDI. ACM, New York","author":"Oh Hakjoo","year":"2014","journal-title":"NY, USA"},{"key":"e_1_2_2_47_1","first-page":"394","article-title":"Call Graphs for Languages with Parametric Polymorphism. In OOPSLA. ACM, New York","author":"Petrashko Dmitry","year":"2016","journal-title":"NY, USA"},{"key":"e_1_2_2_48_1","volume-title":"Dispatch of Context-Sensitive Optimizations. Master's thesis","author":"Poesia Gabriel"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133874"},{"key":"e_1_2_2_50_1","volume-title":"Program Analysis via Graph Reachability","author":"Reps Thomas"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/345099.345137"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/514191.514229"},{"key":"e_1_2_2_53_1","first-page":"11","article-title":"Lightweight Generics in Embedded Systems Through Static Analysis. In LCTES. ACM, New York","author":"Sallenave Olivier","year":"2012","journal-title":"NY, USA"},{"key":"e_1_2_2_54_1","first-page":"13","article-title":"Adaptive Input-aware Compilation for Graphics Engines. In PLDI. ACM, New York","author":"Samadi Mehrzad","year":"2012","journal-title":"NY, USA"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2013.6495006"},{"key":"e_1_2_2_56_1","first-page":"164","article-title":"Control Flow Analysis in Scheme. In PLDI. ACM, New York","author":"Shivers O.","year":"1988","journal-title":"NY, USA"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19861-8_2"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290361"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ECOOP.2016.22"},{"key":"e_1_2_2_60_1","first-page":"163","article-title":"Restrictification of Function Arguments. In CC. ACM, New York","author":"Sperle Campos Victor Hugo","year":"2016","journal-title":"NY, USA"},{"key":"e_1_2_2_61_1","first-page":"387","article-title":"Refinement-based Context-sensitive Points-to Analysis for Java. In PLDI. ACM, New York","author":"Sridharan Manu","year":"2006","journal-title":"NY, USA"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2989225.2989236"},{"key":"e_1_2_2_63_1","first-page":"1","article-title":"Bridging Islands of Specialized Code Using Macros and Reified Types. In SCALA. ACM, New York","volume":"10","author":"Stucki Nicolas","year":"2013","journal-title":"NY, USA"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806799.1806875"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2011.70"},{"key":"e_1_2_2_66_1","first-page":"135","article-title":"Compare Less, Defer More: Scaling Value-Contexts Based Whole-Program Heap Analyses. In Compiler Construction. ACM, New York","author":"Thakur Manas","year":"2019","journal-title":"NY, USA"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3377555.3377902"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3140587.3062359"},{"key":"e_1_2_2_69_1","first-page":"445","article-title":"A Step Towards Transparent Integration of Input-consciousness into Dynamic Program Optimizations. In OOPSLA. ACM, New York","author":"Tian Kai","year":"2011","journal-title":"NY, USA"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3237009.3237018"},{"key":"e_1_2_2_71_1","first-page":"295","article-title":"Optimizing R VM: Allocation Removal and Path Length Reduction via Interpreter-level Specialization. In CGO. ACM, New York","volume":"295","author":"Wang Haichuan","year":"2014","journal-title":"NY, USA"},{"key":"e_1_2_2_72_1","volume-title":"Ryder","author":"Wei Shiyi","year":"2015"},{"key":"e_1_2_2_73_1","first-page":"131","article-title":"Cloning-based Context-sensitive Pointer Alias Analysis Using Binary Decision Diagrams. In PLDI. ACM, New York","author":"Whaley John","year":"2004","journal-title":"NY, USA"},{"key":"e_1_2_2_74_1","first-page":"1","article-title":"Eficient Context-sensitive Pointer Analysis for C Programs. In PLDI. ACM, New York","author":"Wilson Robert P.","year":"1995","journal-title":"NY, USA"},{"key":"e_1_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772954.1772985"},{"key":"e_1_2_2_76_1","first-page":"145","article-title":"Symbolic Pointer Analysis Revisited. In PLDI. ACM, New York","author":"Zhu Jianwen","year":"2004","journal-title":"NY, USA"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428235","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428235","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:57Z","timestamp":1750197777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428235"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,13]]},"references-count":75,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2020,11,13]]}},"alternative-id":["10.1145\/3428235"],"URL":"https:\/\/doi.org\/10.1145\/3428235","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,13]]},"assertion":[{"value":"2020-11-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}