Making Pointer Analysis More Precise by Unleashing the Power of Selective Context Sensitivity 147:15 Scalability.Relay-02 is the last line of defense of Unity-Relay:given a set of selective ap- proaches S,we can expect Relay-02 to scale as long as VSiE S:PA-Si scales.With conventional approaches,when context-sensitively analyzing a set of scalability-threat methods,(1)the size of context-sensitive points-to relations may become large(thus needing much more time to handle in every analysis iteration),and(2)the analysis may need many more iterations to reach a fixed point.The simultaneous effects of(1)and(2)make the analysis complexity blow up,becoming unscalable.However,for Relay-02,in each pass the context-sensitivity variant selected is the same as that of PA-S;for every method,and due to the filtering mechanism,the points-to set for every variable is never larger than the one in PA-S;(note that this holds regardless of the pass ordering in Relay-o2):therefore,in Relay-02,there will be no more data propagated in each iteration and no more iterations until convergence.Thus Relay-02 scalability is ensured,as long as each PA-Si scales.The only extra cost introduced in Relay-02 is its filtering process and its essence is querying whether an element (object)belongs to a set(points-to set),which can be implemented efficiently, and unlike(1)and(2)described above,it is not a key factor in making a pointer analysis unscalable. The experimental results in Section 6.2 further validate the scalability of Relay. Other Context Abstractions for Selective Context Sensitivity.Our current formalism only focuses on the widely-used method-level selective approaches,i.e.,it assumes that the input selective approaches choose context based on the target method(m in selectCS(m)).Still,the idea of Unity-Relay also applies to other context abstractions for selective context sensitivity.For example, introspective analysis [Smaragdakis et al.2014]selects context based on call sites(i.e.,different context-sensitivity variants for different call sites).To support such a selective approach,we only need to change the input domain of selectCS to further include call sites,and the context selection policy of Unity-Relay remains the same.As another alternative,Lu and Xue [2019]select context on a per-variable basis.The Unity-Relay idea applies seamlessly,but at the granularity of variables, not methods,i.e.,one should see the circles in Figures 2 and 3 as selected variables. 5 BATON As a proof-of-concept,we introduce BAroN,an instantiation of the Unity-Relay framework.Given plenty of existing selective context sensitivity approaches [Hassanshahi et al.2017:Jeon et al.2019; Jeong et al.2017;Li et al.2018a,b,2020;Lu and Xue 2019;Minseok Jeon and Oh 2020;Oh et al.2014, 2015;Smaragdakis et al.2014;Wei and Ryder 2015],the design space of Unity-Relay is large.For more precision improvement,the chosen approaches should be diverse so that they could cover precision-useful methods from different perspectives;and they should exhibit good scalability,as explained in Section 3.3.Accordingly,BAToN considers three such approaches as inputs:one ad-hoc approach based on expert experience,called CoLLECTIoN [WALA 2018],and two state-of-the-art approaches,called ZIPPER [Li et al.2020]and SCALER [Li et al.2018b]. Collection(or container)methods are important to pointer analysis,as a huge amount of objects may flow to and are merged in them,if the collection is not being analyzed context-sensitively. Thus,in pointer analysis frameworks such as WALA [WALA 2018],the experts provide an option to analyze only collection methods(in JDK)context-sensitively for good precision(with also good scalability).Inspired by [WALA 2018],in CoLLECTION,we apply 3obj to the collection methods whose declaring classes implement interfaces java.util.Collection and java.util.Map in both application and library code. ZIPPERe(short for ZIPPER express)[Li et al.2020]is a variant of a selective approach called ZIPPER [Li et al.2018a]which identifies precision-useful methods based on principled precision-loss patterns [Li et al.2020].By exploiting the patterns,ZIPPERe adopts simple but effective heuristics to further exclude the scalability-threat methods.As a result,by applying 2obj only to the finally 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:15 Scalability. Relay-o2 is the last line of defense of Unity-Relay: given a set of selective ap￾proaches 𝑆, we can expect Relay-o2 to scale as long as ∀𝑆𝑖 ∈ 𝑆 : PA-𝑆𝑖 scales. With conventional approaches, when context-sensitively analyzing a set of scalability-threat methods, (1) the size of context-sensitive points-to relations may become large (thus needing much more time to handle in every analysis iteration), and (2) the analysis may need many more iterations to reach a fixed point. The simultaneous effects of (1) and (2) make the analysis complexity blow up, becoming unscalable. However, for Relay-o2, in each pass the context-sensitivity variant selected is the same as that of PA-𝑆𝑖 for every method, and due to the filtering mechanism, the points-to set for every variable is never larger than the one in PA-𝑆𝑖 (note that this holds regardless of the pass ordering in Relay-o2); therefore, in Relay-o2, there will be no more data propagated in each iteration and no more iterations until convergence. Thus Relay-o2 scalability is ensured, as long as each PA-𝑆𝑖 scales. The only extra cost introduced in Relay-o2 is its filtering process and its essence is querying whether an element (object) belongs to a set (points-to set), which can be implemented efficiently, and unlike (1) and (2) described above, it is not a key factor in making a pointer analysis unscalable. The experimental results in Section 6.2 further validate the scalability of Relay. Other Context Abstractions for Selective Context Sensitivity. Our current formalism only focuses on the widely-used method-level selective approaches, i.e., it assumes that the input selective approaches choose context based on the target method (𝑚 in 𝑠𝑒𝑙𝑒𝑐𝑡𝐶𝑆 (𝑚)). Still, the idea of Unity-Relay also applies to other context abstractions for selective context sensitivity. For example, introspective analysis [Smaragdakis et al. 2014] selects context based on call sites (i.e., different context-sensitivity variants for different call sites). To support such a selective approach, we only need to change the input domain of 𝑠𝑒𝑙𝑒𝑐𝑡𝐶𝑆 to further include call sites, and the context selection policy of Unity-Relay remains the same. As another alternative, Lu and Xue [2019] select context on a per-variable basis. The Unity-Relay idea applies seamlessly, but at the granularity of variables, not methods, i.e., one should see the circles in Figures 2 and 3 as selected variables. 5 BATON As a proof-of-concept, we introduce Baton, an instantiation of the Unity-Relay framework. Given plenty of existing selective context sensitivity approaches [Hassanshahi et al. 2017; Jeon et al. 2019; Jeong et al. 2017; Li et al. 2018a,b, 2020; Lu and Xue 2019; Minseok Jeon and Oh 2020; Oh et al. 2014, 2015; Smaragdakis et al. 2014; Wei and Ryder 2015], the design space of Unity-Relay is large. For more precision improvement, the chosen approaches should be diverse so that they could cover precision-useful methods from different perspectives; and they should exhibit good scalability, as explained in Section 3.3. Accordingly, Baton considers three such approaches as inputs: one ad-hoc approach based on expert experience, called Collection [WALA 2018], and two state-of-the-art approaches, called Zipper𝑒 [Li et al. 2020] and Scaler [Li et al. 2018b]. Collection (or container) methods are important to pointer analysis, as a huge amount of objects may flow to and are merged in them, if the collection is not being analyzed context-sensitively. Thus, in pointer analysis frameworks such as Wala [WALA 2018], the experts provide an option to analyze only collection methods (in JDK) context-sensitively for good precision (with also good scalability). Inspired by [WALA 2018], in Collection, we apply 3obj to the collection methods whose declaring classes implement interfaces java.util.Collection and java.util.Map in both application and library code. Zipper𝑒 (short for Zipper express) [Li et al. 2020] is a variant of a selective approach called Zipper [Li et al. 2018a] which identifies precision-useful methods based on principled precision-loss patterns [Li et al. 2020]. By exploiting the patterns, Zipper𝑒 adopts simple but effective heuristics to further exclude the scalability-threat methods. As a result, by applying 2obj only to the finally Proc. ACM Program. Lang., Vol. 5, No. OOPSLA, Article 147. Publication date: October 2021