141:12 Yue Li,Tian Tan,Anders Moller,and Yannis Smaragdakis Algorithm 2:PCMCOLLECTOR Input (Input class) PFG(Precision Flow Graph for class c) Output:PCMc(Precision-Critical Methods for class c) 1 FlowNodes←-{h,PCMc←-{} 2 foreach m∈OUT do foreach return variable r of m do LFlowNodes U=NODESCANREACH(N.PFG) /Backward graph reachability s foreach NE FlowNodes do if N is a variable node Na and a is declared in m then add m to PCMe if N is an object field node No.f and o is allocated in m then 9 add m to PCMe 10 return PCMc line 15 in Algorithm 1,an edge that enables tracking the wrapped flow is added in Figure 8 from node obj to node itr,since [Itr]is the variable itr. Graph Reachability on Precision Flow Graphs.We now explain how ZIPPER extracts the precision- critical methods based on the PFGs.Generally,ZIPPER first computes all the nodes that are involved in the three kinds of flows by solving a simple graph reachability problem on the PFG,and then collects the methods that contain the nodes as the precision-critical methods. Given a class c,each flow in the precision loss patterns corresponds to a path from a parameter node of an IN method of c to a return variable node of an Our method of c in PFGe.Therefore, obtaining the statements that are involved in the flows is equivalent to computing which nodes are reachable from a parameter of an IN method and can also reach a return variable of an OuT method in PFGe.Since ZIPPER builds PFGe starting from the parameters of the IN methods(lines 2-3 in Algorithm 1),all nodes in PFGe are reachable from the IN methods.Therefore,we only need to find out which nodes in PFGe can reach the return variables of Our methods of class c. Algorithm 2(PCMCoLLECTOR)defines the collection of precision-critical methods for an input class c based on PFGc.In line 1,two sets are initialized to empty:FlowNodes denotes the set of nodes that are involved in the flows from IN methods to Our methods of class c,and PCMc denotes the set of precision-critical methods for class c,i.e.,the methods that contain the nodes in FlowNodes. In lines 2-4,PCMCOLLECTOR fills FlowNodes by iterating through the return variables of all Our methods of c(denoted by OUTe)and collecting all nodes that can reach the return variables in PFGe. The function NoDESCANREACH used in line 4 is a standard backward graph reachability algorithm which traverses the PFGe starting from N,and returns all nodes that can reach N,on PFGe. In lines 5-9,PCMCoLLECTOR fills PCMe.There are two kinds of nodes in PFGe that are handled differently.For a variable node Na,PCMCoLLECToR adds the method where the variable a is declared to PCMc(lines 6-7).For an object field node No.f,PCMCoLLECTOR adds the method where the abstract object o is allocated to PCMe(lines 8-9). As a result,the algorithm collects the precision-critical methods for each class in a given pro- gram.With this information,ZIPPER can guide context-sensitive pointer analyses to apply context sensitivity only for the precision-critical methods. The precise statements of Algorithms 1 and 2 capture the design choices of ZIPpER.Inferences on flow patterns are made on a per-class basis,and context sensitivity is applied on a per-method basis.It is easy to imagine applying context sensitivity at a finer granularity.That is,we could Proc.ACM Program.Lang.,Vol.2,No.OOPSLA,Article 141.Publication date:November 2018.141:12 Yue Li, Tian Tan, Anders Mùller, and Yannis Smaragdakis Algorithm 2: PcmCollector Input : c (Input class) PFGc (Precision Flow Graph for class c) Output : PCMc (Precision-Critical Methods for class c) 1 FlowNodes ← { }, PCMc ← { } 2 foreach m ∈ Outc do 3 foreach return variable r of m do 4 FlowNodes Ð = NodesCanReach(Nr , PFGc ) // Backward graph reachability 5 foreach N ∈ FlowNodes do 6 if N is a variable node Na and a is declared in m then 7 add m to PCMc 8 if N is an object field node No.f and o is allocated in m then 9 add m to PCMc 10 return PCMc line 15 in Algorithm 1, an edge that enables tracking the wrapped flow is added in Figure 8 from node obj to node itr, since [Itr] is the variable itr. Graph Reachability on Precision Flow Graphs. We now explain how Zipper extracts the precision￾critical methods based on the PFGs. Generally, Zipper first computes all the nodes that are involved in the three kinds of flows by solving a simple graph reachability problem on the PFG, and then collects the methods that contain the nodes as the precision-critical methods. Given a class c, each flow in the precision loss patterns corresponds to a path from a parameter node of an In method of c to a return variable node of an Out method of c in PFGc . Therefore, obtaining the statements that are involved in the flows is equivalent to computing which nodes are reachable from a parameter of an In method and can also reach a return variable of an Out method in PFGc . Since Zipper builds PFGc starting from the parameters of the In methods (lines 2ś3 in Algorithm 1), all nodes in PFGc are reachable from the In methods. Therefore, we only need to find out which nodes in PFGc can reach the return variables of Out methods of class c. Algorithm 2 (PcmCollector) defines the collection of precision-critical methods for an input classc based on PFGc . In line 1, two sets are initialized to empty: FlowNodes denotes the set of nodes that are involved in the flows from In methods to Out methods of class c, and PCMc denotes the set of precision-critical methods for class c, i.e., the methods that contain the nodes in FlowNodes. In lines 2ś4, PcmCollector fills FlowNodes by iterating through the return variables of all Out methods ofc (denoted by Outc ) and collecting all nodes that can reach the return variables in PFGc . The function NodesCanReach used in line 4 is a standard backward graph reachability algorithm which traverses the PFGc starting from Nr and returns all nodes that can reach Nr on PFGc . In lines 5ś9, PcmCollector fills PCMc . There are two kinds of nodes in PFGc that are handled differently. For a variable node Na, PcmCollector adds the method where the variable a is declared to PCMc (lines 6ś7). For an object field node No.f , PcmCollector adds the method where the abstract object o is allocated to PCMc (lines 8ś9). As a result, the algorithm collects the precision-critical methods for each class in a given pro￾gram. With this information, Zipper can guide context-sensitive pointer analyses to apply context sensitivity only for the precision-critical methods. The precise statements of Algorithms 1 and 2 capture the design choices of Zipper. Inferences on flow patterns are made on a per-class basis, and context sensitivity is applied on a per-method basis. It is easy to imagine applying context sensitivity at a finer granularity. That is, we could Proc. ACM Program. Lang., Vol. 2, No. OOPSLA, Article 141. Publication date: November 2018