141:10 Yue Li,Tian Tan,Anders Moller,and Yannis Smaragdakis Algorithm 1:PFGBUILDER OFG (Object Flow Graph) Input c (Input class) (Set of statements in the program) Output:PFGe (Precision Flow Graph for class c) 1PFGc←-{}，VisitedNodes←{h,WUEdges←-{} 2 foreach m∈INe do foreach parameter p of m do LDFs(Np)where Np is the OFG node for p 5 return PFGc 6 Function DFs(N) 1 if NE VisitedNodes then 8 return 9 add N to VisitedNodes 10 if N is a variable node Na then 11 foreach b a.fes do /Handling unwrapped flow 12 Ladd Na一to WUEdges 13 foreach b.f aes do /Handling wrapped flow 14 foreach o∈pt(b)do 15 Ladd N No]to WUEdges 16 foreach N→N'∈OFGU WUEdges do 17 addN→W'to PFGc DEs(N) 3.3 Precision Flow Graphs and Graph Reachability We first explain how to construct precision flow graphs(PFGs)and then how to identify precision- critical methods by performing graph reachability on each PFG. Precision Flow Graph Construction.As explained in Section 3.2,one OFG is built for the entire program.Since the PFGs serve to express the three kinds of precision loss patterns,which are all defined relative to a class,as explained in Section 2,we construct one PFG for each class in the program.As the OFG can already describe direct flow(Section 3.2),the task of building the PFG is to add edges that can express the other two kinds of flows:wrapped and unwrapped flows. Algorithm 1(PFGBUILDER)shows how to build PFGe for a given class c.For simplicity,we represent the PFG and the OFG by their sets of graph edges,and the graph nodes are implicitly those that appear in the edge sets. Three sets are initialized to empty sets in line 1:the PFG edges,the set of visited nodes,and WUEdges,which denotes a set of extra edges for wrapped and unwrapped flows.As all three kinds of flows begin from the parameters of an IN method(see Section 2),the algorithm starts by iterating through those methods(lines 2-3,where INe denotes the set of IN methods of the input class c). Function DFs(line 6)traverses the input OFG and adds the edges for wrapped and unwrapped flows.As a result,the returned PFGe(line 5)includes all the nodes that can be reached from each parameter of IN methods of c,through direct,wrapped,and unwrapped flows,or combinations of these.Specifically,unwrapped and wrapped flows are handled in lines 11-12 and lines 13-15, respectively,by adding the corresponding edges to WUEdges.Finally,the generated PFG includes Proc.ACM Program.Lang.,Vol.2,No.OOPSLA,Article 141.Publication date:November 2018.141:10 Yue Li, Tian Tan, Anders Mùller, and Yannis Smaragdakis Algorithm 1: PfgBuilder Input : OFG (Object Flow Graph) c (Input class) S (Set of statements in the program) Output : PFGc (Precision Flow Graph for class c) 1 PFGc ← { }, VisitedNodes ← { }, WUEdges ← { } 2 foreach m ∈ Inc do 3 foreach parameter p of m do 4 Dfs(Np ) where Np is the OFG node for p 5 return PFGc 6 Function Dfs(N) 7 if N ∈ VisitedNodes then 8 return 9 add N to VisitedNodes 10 if N is a variable node Na then 11 foreach b = a.f ∈ S do // Handling unwrapped flow 12 add Na → Nb to WUEdges 13 foreach b.f = a ∈ S do // Handling wrapped flow 14 foreach o ∈ pt(b) do 15 add Na → N[o] to WUEdges 16 foreach N → N ′ ∈ OFG ∪ WUEdges do 17 add N → N ′ to PFGc 18 Dfs(N ′ ) 3.3 Precision Flow Graphs and Graph Reachability We first explain how to construct precision flow graphs (PFGs) and then how to identify precision￾critical methods by performing graph reachability on each PFG. Precision Flow Graph Construction. As explained in Section 3.2, one OFG is built for the entire program. Since the PFGs serve to express the three kinds of precision loss patterns, which are all defined relative to a class, as explained in Section 2, we construct one PFG for each class in the program. As the OFG can already describe direct flow (Section 3.2), the task of building the PFG is to add edges that can express the other two kinds of flows: wrapped and unwrapped flows. Algorithm 1 (PfgBuilder) shows how to build PFGc for a given classc. For simplicity, we represent the PFG and the OFG by their sets of graph edges, and the graph nodes are implicitly those that appear in the edge sets. Three sets are initialized to empty sets in line 1: the PFG edges, the set of visited nodes, and WUEdges, which denotes a set of extra edges for wrapped and unwrapped flows. As all three kinds of flows begin from the parameters of an In method (see Section 2), the algorithm starts by iterating through those methods (lines 2ś3, where Inc denotes the set of In methods of the input class c). Function Dfs (line 6) traverses the input OFG and adds the edges for wrapped and unwrapped flows. As a result, the returned PFGc (line 5) includes all the nodes that can be reached from each parameter of In methods of c, through direct, wrapped, and unwrapped flows, or combinations of these. Specifically, unwrapped and wrapped flows are handled in lines 11ś12 and lines 13ś15, respectively, by adding the corresponding edges to WUEdges. Finally, the generated PFG includes Proc. ACM Program. Lang., Vol. 2, No. OOPSLA, Article 141. Publication date: November 2018