1:4 Yue Li,Tian Tan,Anders Moller,and Yannis Smaragdakis There are two major factors that control the precision of pointer analysis:how to abstract the heap,and how to abstract the call stack.Compared with the few approaches on heap abstraction for Java pointer analysis [Kanvar and Khedker 2016;Lhotak and Hendren 2003;Tan et al.2017], there is ample literature on stack modeling.Among the schemes for modeling the stack,in the past years,context sensitivity has been considered as the most effective approach to improve the analysis precision for Java programs [Lhotak and Hendren 2006]and has thus attracted the most attention from researchers [Bravenboer and Smaragdakis 2009;Hassanshahi et al.2017;Jeon et al. 2019,2018;Jeong et al.2017;Kastrinis and Smaragdakis 2013;Lhotak and Hendren 2006;Li et al. 2018b;Milanova et al.2002,2005;Smaragdakis and Balatsouras 2015;Smaragdakis et al.2011,2014; Sridharan et al.2013;Tan et al.2016,2017;Thakur and Nandivada 2019;Thiessen and Lhotak 2017]. We summarize the research work on context-sensitive pointer analysis into three categories according to(1)the kinds of context elements,(2)the composition of context elements,and (3)the selection of which parts of a given program to analyze with context sensitivity.Interestingly,the techniques in different categories are orthogonal and can thus be combined for producing more sophisticated pointer analyses. Kinds of Context Elements.Many elements in a program,e.g.,call sites,allocation sites,and types, can be considered as context elements in context sensitivity.The earliest type of context elements for Java pointer analysis inherits from the foundational approaches used both for C and for functional languages [Sharir and Pnueli 1981;Shivers 1991]where context elements are call sites.We refer to this style of context sensitivity as call-site sensitivity or call-string sensitivity [Smaragdakis and Balatsouras 2015].Unlike C programs,which often predominantly manipulate values in the stack. Java programs have their inter-procedural data flow primarily through heap objects.Accordingly. Milanova et al.[2005]proposed object sensitivity that uses allocation sites of receiver objects(the program points where these objects are created)as context elements.Generally,object sensitivity is more precise and efficient than call-site sensitivity,and is considered the most effective context- sensitivity variant for producing good precision for Java.This conclusion has been extensively validated in various pointer analysis frameworks [Kastrinis and Smaragdakis 2013;Lhotak and Hendren 2006;Naik et al.2006;Sridharan et al.2013;Tan et al.2016,2017]. Despite being precise,object sensitivity is difficult to scale for large and complex Java programs, which motivated the concept of type sensitivity [Smaragdakis et al.2011].In type sensitivity,the context elements are the types of the classes containing allocation sites(as the latter would appear in object sensitivity).This more coarse-grained choice of context elements enables type sensitivity to run much faster by sacrificing some precision compared to object sensitivity.Today,call-site, object,and type sensitivity are still considered the three mainstream context-sensitivity variants for Java pointer analysis [Jeong et al.2017;Smaragdakis and Balatsouras 2015;Tan et al.2017]. Composition of Context Elements.With context sensitivity,each method can be analyzed in multiple contexts,where a context consists of a list of context elements that model the run-time call stack.For example,in call-string sensitivity [Sharir and Pnueli 1981;Shivers 1991],a context for a method m is composed by the context elements that are listed as [c1,c2,...],where c is m's call site,cz is the call site of the method that contains c,etc.To ensure termination of the analysis,a k-limiting approach is typically followed:only the most recent k context elements are selected,and, for efficiency,k is usually set to a very small value in practice.The call-string sensitivity approach has been adopted in virtually all context-sensitive pointer analyses [Smaragdakis and Balatsouras 2015;Sridharan et al.2013].However,Tan et al.[2016]found that this conventional approach leads to many context elements that are not useful for improving precision while occupying the limited slots of context elements determined by k.To address this problem,Tan et al.[2016]presented an approach to identify such redundant context elements.By skipping those elements,a resulting ACM Trans.Program.Lang.Syst.,Vol.1,No.1,Article 1.Publication date:January 2020.1:4 Yue Li, Tian Tan, Anders Møller, and Yannis Smaragdakis There are two major factors that control the precision of pointer analysis: how to abstract the heap, and how to abstract the call stack. Compared with the few approaches on heap abstraction for Java pointer analysis [Kanvar and Khedker 2016; Lhoták and Hendren 2003; Tan et al. 2017], there is ample literature on stack modeling. Among the schemes for modeling the stack, in the past years, context sensitivity has been considered as the most effective approach to improve the analysis precision for Java programs [Lhoták and Hendren 2006] and has thus attracted the most attention from researchers [Bravenboer and Smaragdakis 2009; Hassanshahi et al. 2017; Jeon et al. 2019, 2018; Jeong et al. 2017; Kastrinis and Smaragdakis 2013; Lhoták and Hendren 2006; Li et al. 2018b; Milanova et al. 2002, 2005; Smaragdakis and Balatsouras 2015; Smaragdakis et al. 2011, 2014; Sridharan et al. 2013; Tan et al. 2016, 2017; Thakur and Nandivada 2019; Thiessen and Lhoták 2017]. We summarize the research work on context-sensitive pointer analysis into three categories according to (1) the kinds of context elements, (2) the composition of context elements, and (3) the selection of which parts of a given program to analyze with context sensitivity. Interestingly, the techniques in different categories are orthogonal and can thus be combined for producing more sophisticated pointer analyses. Kinds of Context Elements. Many elements in a program, e.g., call sites, allocation sites, and types, can be considered as context elements in context sensitivity. The earliest type of context elements for Java pointer analysis inherits from the foundational approaches used both for C and for functional languages [Sharir and Pnueli 1981; Shivers 1991] where context elements are call sites. We refer to this style of context sensitivity as call-site sensitivity or call-string sensitivity [Smaragdakis and Balatsouras 2015]. Unlike C programs, which often predominantly manipulate values in the stack, Java programs have their inter-procedural data flow primarily through heap objects. Accordingly, Milanova et al. [2005] proposed object sensitivity that uses allocation sites of receiver objects (the program points where these objects are created) as context elements. Generally, object sensitivity is more precise and efficient than call-site sensitivity, and is considered the most effective context￾sensitivity variant for producing good precision for Java. This conclusion has been extensively validated in various pointer analysis frameworks [Kastrinis and Smaragdakis 2013; Lhoták and Hendren 2006; Naik et al. 2006; Sridharan et al. 2013; Tan et al. 2016, 2017]. Despite being precise, object sensitivity is difficult to scale for large and complex Java programs, which motivated the concept of type sensitivity [Smaragdakis et al. 2011]. In type sensitivity, the context elements are the types of the classes containing allocation sites (as the latter would appear in object sensitivity). This more coarse-grained choice of context elements enables type sensitivity to run much faster by sacrificing some precision compared to object sensitivity. Today, call-site, object, and type sensitivity are still considered the three mainstream context-sensitivity variants for Java pointer analysis [Jeong et al. 2017; Smaragdakis and Balatsouras 2015; Tan et al. 2017]. Composition of Context Elements. With context sensitivity, each method can be analyzed in multiple contexts, where a context consists of a list of context elements that model the run-time call stack. For example, in call-string sensitivity [Sharir and Pnueli 1981; Shivers 1991], a context for a method 𝑚 is composed by the context elements that are listed as [𝑐1, 𝑐2, . . . ], where 𝑐1 is 𝑚’s call site, 𝑐2 is the call site of the method that contains 𝑐1, etc. To ensure termination of the analysis, a 𝑘-limiting approach is typically followed: only the most recent 𝑘 context elements are selected, and, for efficiency, 𝑘 is usually set to a very small value in practice. The call-string sensitivity approach has been adopted in virtually all context-sensitive pointer analyses [Smaragdakis and Balatsouras 2015; Sridharan et al. 2013]. However, Tan et al. [2016] found that this conventional approach leads to many context elements that are not useful for improving precision while occupying the limited slots of context elements determined by 𝑘. To address this problem, Tan et al. [2016] presented an approach to identify such redundant context elements. By skipping those elements, a resulting ACM Trans. Program. Lang. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2020