1:18 Yue Li,Tian Tan,Anders Moller,and Yannis Smaragdakis Algorithm 4:ZIPPER (Input program) Input OFG (Object Flow Graph for program p) PV (The shared threshold for all programs) Output:Mcs (The methods to be analyzed context-sensitively) 1TH=PV×∑opIpt(o)l /The threshold for program p zMcs←-{h,S←-set of all statements in p 3 foreach class c in p do 4 PFGc+PFGBUILDER(OFG,c,S) PCMc+PCMCOLLECTOR(c,PFGc) 6 ptse=∑mEPCMe∑oem|pt(o)川 7 if#ptsc≤TH then L Mes U=PCMe 9 return Mcs for all the variables in all precision-critical methods for each given class c.Per lines 7-8,only the precision-critical methods that are not efficiency-critical will be analyzed with context sensitivity. As explained in Section 4,it is possible that a method m is involved in precision-loss flows for multiple classes,say c and c2,when collecting their corresponding precision-critical methods.In ZIPPER,if m is identified as efficiency-critical in c but non-efficiency-critical in c2,m will still be analyzed context-sensitively for precision,as reflected in the set union operation of line 8. 6 EVALUATION In this section,we investigate the following research questions for evaluating our selective context- sensitivity techniques. RQ1.Is ZIPPER-guided pointer analysis precise and efficient? (a)How much of the precision of a conventional analysis can ZIPPER preserve? (b)How fast is ZIPPER-guided pointer analysis compared to a conventional analysis? (c)What is the overhead of running ZIPPER? We consider object-sensitive pointer analysis [Milanova et al.2002,2005]as the conventional analysis that applies context sensitivity to all methods.That analysis is well-recognized as the most precise context-sensitivity variant and widely supported by all popular pointer analysis frameworks for Java. RQ2.How does ZIPPER-guided pointer analysis compare to state-of-the-art alternative techniques (specifically,introspective analyses [Smaragdakis et al.2014])that also apply context sensi- tivity for only a subset of the methods,in terms of precision and efficiency? RQ3.What is the effect of each of ZIPPER's precision loss patterns on the analysis results? (a)How many methods does ZIPPER consider precision-critical,and how does each precision loss pattern contribute to this number? (b)How does each of the precision loss patterns affect the precision and efficiency of ZIPPER- guided pointer analysis? RQ4.Is the precision-loss model(introduced in Section 3)general enough to preserve the precision of other mainstream variants of context sensitivity,i.e.,call-site sensitivity [Sharir and Pnueli 1981],type sensitivity [Smaragdakis et al.2011],and hybrid context sensitivity [Kastrinis and Smaragdakis 2013]? RQ5.Is ZIPPERe-guided pointer analysis effective in practice? (a)How does ZIPPERe-guided pointer analysis perform in terms of precision and efficiency? ACM Trans.Program.Lang.Syst.,Vol.1,No.1,Article 1.Publication date:January 2020.1:18 Yue Li, Tian Tan, Anders Møller, and Yannis Smaragdakis Algorithm 4: Zipper𝑒 Input : 𝑝 (Input program) OFG (Object Flow Graph for program 𝑝) PV (The shared threshold for all programs) Output : Mcs (The methods to be analyzed context-sensitively) 1 TH = PV × Í 𝑣∈𝑝 | pt(𝑣) | // The threshold for program 𝑝 2 Mcs ← { }, S ← set of all statements in p 3 foreach class c in p do 4 PFG𝑐 ← PfgBuilder(OFG, c, S) 5 PCM𝑐 ← PcmCollector(c, PFG𝑐 ) 6 #pts𝑐 = Í 𝑚∈PCM𝑐 Í 𝑣∈𝑚 | pt(𝑣) | 7 if #pts𝑐 ≤ TH then 8 Mcs Ð = PCM𝑐 9 return Mcs for all the variables in all precision-critical methods for each given class 𝑐. Per lines 7–8, only the precision-critical methods that are not efficiency-critical will be analyzed with context sensitivity. As explained in Section 4, it is possible that a method 𝑚 is involved in precision-loss flows for multiple classes, say 𝑐1 and 𝑐2, when collecting their corresponding precision-critical methods. In Zipper𝑒 , if 𝑚 is identified as efficiency-critical in 𝑐1 but non-efficiency-critical in 𝑐2, 𝑚 will still be analyzed context-sensitively for precision, as reflected in the set union operation of line 8. 6 EVALUATION In this section, we investigate the following research questions for evaluating our selective context￾sensitivity techniques. RQ1. Is Zipper-guided pointer analysis precise and efficient? (a) How much of the precision of a conventional analysis can Zipper preserve? (b) How fast is Zipper-guided pointer analysis compared to a conventional analysis? (c) What is the overhead of running Zipper? We consider object-sensitive pointer analysis [Milanova et al. 2002, 2005] as the conventional analysis that applies context sensitivity to all methods. That analysis is well-recognized as the most precise context-sensitivity variant and widely supported by all popular pointer analysis frameworks for Java. RQ2. How does Zipper-guided pointer analysis compare to state-of-the-art alternative techniques (specifically, introspective analyses [Smaragdakis et al. 2014]) that also apply context sensi￾tivity for only a subset of the methods, in terms of precision and efficiency? RQ3. What is the effect of each of Zipper’s precision loss patterns on the analysis results? (a) How many methods does Zipper consider precision-critical, and how does each precision loss pattern contribute to this number? (b) How does each of the precision loss patterns affect the precision and efficiency of Zipper￾guided pointer analysis? RQ4. Is the precision-loss model (introduced in Section 3) general enough to preserve the precision of other mainstream variants of context sensitivity, i.e., call-site sensitivity [Sharir and Pnueli 1981], type sensitivity [Smaragdakis et al. 2011], and hybrid context sensitivity [Kastrinis and Smaragdakis 2013]? RQ5. Is Zipper𝑒 -guided pointer analysis effective in practice? (a) How does Zipper𝑒 -guided pointer analysis perform in terms of precision and efficiency? ACM Trans. Program. Lang. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2020