A Principled Approach to Selective Context Sensitivity for Pointer Analysis 1:13 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←-{h,VisitedNodes←-{}，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) if NE VisitedNodes then return 9 add N to VisitedNodes 10 if N is a variable node Na then foreach b a.f es do /Handling unwrapped flow Ladd Na一→to WUEdges 13 foreach b.f aeS do /Handling wrapped flow foreach o∈pt(b)do L add Na NIo]to WUEdges 16 foreach N→N'∈OFGU WUEdges do addN→N'to PFGc DEs(N) 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 3),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 DEs(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 direct flows(from the OFG)and wrapped/unwrapped flows(from WUEdges)via the statements in lines 16-17.Now let us see the details of handling wrapped and unwrapped flows. Recall that each OFG node represents either a variable or a field of an abstract object.If node N in line 10 is a variable node Na,then for every load operation (b=a.f in line 11)that may load the(unwrapped)objects(which are stored in a field of an object pointed to by a)to variable b, we add an edge from node Na to node No.This allows us to model unwrapped flow,as defined in Definition 3.5 and illustrated in Section 3.3. The most intricate part of the algorithm is lines 13-15,which handle wrapped flows.If node N in line 10 is a variable node Na,then for every store operation(b.f a in line 13)that can store the objects(pointed to by a)in wrapper objects o pointed to by b(line 14),we add an edge from ACM Trans.Program.Lang.Syst.,Vol.1,No.1,Article 1.Publication date:January 2020.A Principled Approach to Selective Context Sensitivity for Pointer Analysis 1:13 Algorithm 1: PfgBuilder Input : OFG (Object Flow Graph) 𝑐 (Input class) S (Set of statements in the program) Output : PFG𝑐 (Precision Flow Graph for class 𝑐) 1 PFG𝑐 ← { }, VisitedNodes ← { }, WUEdges ← { } 2 foreach m ∈ In𝑐 do 3 foreach parameter p of m do 4 Dfs(N𝑝 ) where N𝑝 is the OFG node for 𝑝 5 return PFG𝑐 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 PFG𝑐 18 Dfs(N ′ ) 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 3), the algorithm starts by iterating through those methods (lines 2–3, where In𝑐 denotes the set of In methods of the input class 𝑐). Function Dfs (line 6) traverses the input OFG and adds the edges for wrapped and unwrapped flows. As a result, the returned PFG𝑐 (line 5) includes all the nodes that can be reached from each parameter of In methods of 𝑐, 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 direct flows (from the OFG) and wrapped/unwrapped flows (from WUEdges) via the statements in lines 16–17. Now let us see the details of handling wrapped and unwrapped flows. Recall that each OFG node represents either a variable or a field of an abstract object. If node 𝑁 in line 10 is a variable node 𝑁a, then for every load operation (b = a.f in line 11) that may load the (unwrapped) objects (which are stored in a field of an object pointed to by a) to variable b, we add an edge from node 𝑁a to node 𝑁b. This allows us to model unwrapped flow, as defined in Definition 3.5 and illustrated in Section 3.3. The most intricate part of the algorithm is lines 13–15, which handle wrapped flows. If node 𝑁 in line 10 is a variable node 𝑁a, then for every store operation (b.f = a in line 13) that can store the objects (pointed to by a) in wrapper objects o pointed to by b (line 14), we add an edge from ACM Trans. Program. Lang. Syst., Vol. 1, No. 1, Article 1. Publication date: January 2020