Making Pointer Analysis More Precise by Unleashing the Power of Selective Context Sensitivity 147:11 variables x,y∈V heap objects 0i,0j∈0(obj) methods m E M fields f∈R types TT(type) program locations i,jL(call) context elements oi,T,jB=OUTUL... kinds of context elements kK=[obj,type,call,.... contexts c∈C=E0UB1UB2. context-sensitivity variants cs=Ik∈CS=N×K pt:C×V→P(C×O) fpt: C×0xF→P(C×O) gencs C×0×C×L→C contextsOf:M→P(C) selectCS:M→Cs Fig.5.Domain and notations. object.This is a bit different from some existing literature [Jeon et al.2018;Milanova et al.2005; Smaragdakis and Balatsouras 2015;Sridharan et al.2013],which derives the heap context from the method context-e.g.,allowing to cut out part of the method context,as the heap context may be shorter.We omit this general treatment in the formal model,for simplicity of illustration purposes. Our implementation supports the more general,full choice in selecting heap contexts. In [CALL],function dispatch(oi,g)is applied to resolve the virtual dispatch of g on receiver object oi to the callee m'. Without loss of generality,we model the results of each selective context-sensitivity approach as a function selectCS,which is invoked to select a proper context-sensitivity variant cs for m'. Actually,traditional context sensitivity can be seen as a special case of selectCS,which returns the same cs for all methods. Each context-sensitivity variant cs corresponds to a function genes(see Figure 5),which generates contexts for target methods based on the information available at the call site.For generality,as shown in Figure 5,gencs accepts four arguments:the heap context(c')of the receiver object (oi), the context of caller m'(c),and the call site (j),so that it can generate contexts for different context- sensitivity variants,including object,type,and call-site sensitivity.The generated context for the target method is denoted c'. We use msto represent the this pseudo-variable of method m',mto represent the k-th parameter of m',and define for every m'a variable mer holding all its return values.The rest of [CALL]propagates arguments and return values between caller in context c and callee in context c. 4.3 Unity We formalize Unity by defining its C.S.selector(Figure 1),i.e.,selectCS in Figure 6.Based on a set of input selective approaches S,Unity selects the most precise context-sensitivity variant for each method.We define <a binary relation of precision between two context-sensitivity variants.If cs is less precise than (or as precise as)cs',we write cs cs'. The precision of different context-sensitivity variants can be compared based on their lengths and kinds of context elements.The impact of length on precision is well understood,i.e.,longer length has better precision (e.g.,2obj<3obj). Are context-sensitivity variants with different kinds of elements comparable in terms of precision? The answer is yes,but not always.Here,we say two variants are comparable means that one of them Proc.ACM Program.Lang.,Vol.5,No.OOPSLA,Article 147.Publication date:October 2021.Making Pointer Analysis More Precise by Unleashing the Power of Selective Context Sensitivity 147:11 variables 𝑥, 𝑦 ∈ V heap objects 𝑜𝑖 , 𝑜 𝑗 ∈ O (obj) methods 𝑚 ∈ M fields 𝑓 ∈ F types 𝑇 ∈ T (type) program locations 𝑖, 𝑗 ∈ L (call) context elements 𝑜𝑖 ,𝑇 , 𝑗 ∈ E = O ∪ T ∪ L... kinds of context elements 𝑘 ∈ K = {obj, type, call, ...} contexts 𝑐 ∈ C = E 0 ∪ E 1 ∪ E 2 ... context-sensitivity variants 𝑐𝑠 = 𝑙𝑘 ∈ CS = N × K pt : C × V → P (C × O) fpt : C × O × F → P (C × O) gen𝑐𝑠 : C × O × C × L → C contextsOf : M → P (C) selectCS : M → CS Fig. 5. Domain and notations. object. This is a bit different from some existing literature [Jeon et al. 2018; Milanova et al. 2005; Smaragdakis and Balatsouras 2015; Sridharan et al. 2013], which derives the heap context from the method contextÐe.g., allowing to cut out part of the method context, as the heap context may be shorter. We omit this general treatment in the formal model, for simplicity of illustration purposes. Our implementation supports the more general, full choice in selecting heap contexts. In [Call], function dispatch(𝑜𝑖 , 𝑔) is applied to resolve the virtual dispatch of 𝑔 on receiver object 𝑜𝑖 to the callee 𝑚′ . Without loss of generality, we model the results of each selective context-sensitivity approach as a function selectCS, which is invoked to select a proper context-sensitivity variant 𝑐𝑠 for 𝑚′ . Actually, traditional context sensitivity can be seen as a special case of selectCS, which returns the same 𝑐𝑠 for all methods. Each context-sensitivity variant𝑐𝑠 corresponds to a function gen𝑐𝑠 (see Figure 5), which generates contexts for target methods based on the information available at the call site. For generality, as shown in Figure 5, gen𝑐𝑠 accepts four arguments: the heap context (𝑐 ′ ) of the receiver object (𝑜𝑖 ), the context of caller 𝑚′ (𝑐), and the call site (𝑗), so that it can generate contexts for different context￾sensitivity variants, including object, type, and call-site sensitivity. The generated context for the target method is denoted 𝑐 𝑡 . We use 𝑚′ 𝑡ℎ𝑖𝑠 to represent the this pseudo-variable of method 𝑚′ , 𝑚′ 𝑝𝑘 to represent the 𝑘-th parameter of 𝑚′ , and define for every 𝑚′ a variable 𝑚′ 𝑟𝑒𝑡 holding all its return values. The rest of [Call] propagates arguments and return values between caller in context 𝑐 and callee in context 𝑐 𝑡 . 4.3 Unity We formalize Unity by defining its C.S. selector (Figure 1), i.e., selectCS in Figure 6. Based on a set of input selective approaches 𝑆, Unity selects the most precise context-sensitivity variant for each method. We define ⪯, a binary relation of precision between two context-sensitivity variants. If 𝑐𝑠 is less precise than (or as precise as) 𝑐𝑠′ , we write 𝑐𝑠 ⪯ 𝑐𝑠′ . The precision of different context-sensitivity variants can be compared based on their lengths and kinds of context elements. The impact of length on precision is well understood, i.e., longer length has better precision (e.g., 2obj ⪯ 3obj). Are context-sensitivity variants with different kinds of elements comparable in terms of precision? The answer is yes, but not always. Here, we say two variants are comparable means that one of them Proc. ACM Program. Lang., Vol. 5, No. OOPSLA, Article 147. Publication date: October 2021