Precision-Guided Context Sensitivity for Pointer Analysis 141:11 PFG OFG C1.elem Itr.next itr C2.elem added for wrapped flow Fig.8.A partial PFG for class Collection in Figure 4(wrapped flow).C1,C2,and Itr denote the objects of classes Collection and Iterator allocated in lines 24,30,and 8 in Figure 4,respectively. 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 2.5 and illustrated in Section 2.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 node Na to Nol.Here we use the notation [o]to denote the variable that the abstract object o was originally assigned to when created:for example,if o is created at a statement v new ..then [o]is the variable v.These added edges enable tracking wrapped flow as defined in Definition 2.4 and illustrated in Section 2.2.As an example,for the object wrapping this.next obj of line 15 in Figure 4,pt(this)contains an abstract object created at itr new Iterator(e)in line 8,so we add an edge from obj to itr. Note that if(in line 15)instead of adding an edge from Na to Nol we had added an edge from Na to No(mirroring the handling of unwrapped flows),we would miss some flows.Conceptually, according to Definition 2.4,modeling wrapped flow requires tracking the wrapper objects(from where they are created)rather than the variable b in the store operation b.f a(line 13).For example,in the case of Figure 4,consider the store operation this.next obj (line 15)where this (line 15)and itr (line 8)both point to the Iterator object created in line 8.If we added an edge from node Nobj to node Nthis (rather than Nobj to Nitr),the flow tracking from Nthis would not lead to the return statement(line 9)in the Our method,because the wrapped flow flows out through node Nitr in this case.However,it is safe to add an edge to node Nitr instead (as we do in line 15 in Algorithm 1)since the wrapper object is originally assigned to itr,so that the flow of the wrapper object is taken into account as required by Definition 2.4. Through Algorithm 1,we can see that wrapped and unwrapped flows can be naturally expressed in the PFG by handling the store/load operations(lines 10-15)recursively during the graph traversal. In addition,the newly added edges for wrapped and unwrapped flows build new connections with existing OFG edges that model direct flows.As a result,the generated PFG also naturally expresses combinations of all three kinds of flows. Figure 8 shows a partial PFG example for class Collection from Figure 4.The existing OFG is constructed following the rules in Figure 7.In Figure 8,in the three object field nodes(C1.elem, C2.elem,and Itr.next),the abstract objects respectively denoted by C1,C2,and Itr represent the objects of classes Collection and Iterator.Node obj corresponds to Na in line 15 in Algorithm 1; the edge from node obj to node Itr.next corresponds to the store operation this.next obj in line 15 in Figure 4,and also the store operation b.f a in line 13 in Algorithm 1.According to Proc.ACM Program.Lang.,Vol.2,No.OOPSLA,Article 141.Publication date:November 2018.Precision-Guided Context Sensitivity for Pointer Analysis 141:11 item C1.elem C2.elem e obj Itr.next itr OFG PFG added for wrapped flow Fig. 8. A partial PFG for class Collection in Figure 4 (wrapped flow). C1, C2, and Itr denote the objects of classes Collection and Iterator allocated in lines 24, 30, and 8 in Figure 4, respectively. 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 Nb. This allows us to model unwrapped flow, as defined in Definition 2.5 and illustrated in Section 2.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 node Na to N[o] . Here we use the notation [o] to denote the variable that the abstract object o was originally assigned to when created: for example, if o is created at a statement v = new . . . then [o] is the variable v. These added edges enable tracking wrapped flow as defined in Definition 2.4 and illustrated in Section 2.2. As an example, for the object wrapping this.next = obj of line 15 in Figure 4, pt(this) contains an abstract object created at itr = new Iterator(e) in line 8, so we add an edge from obj to itr. Note that if (in line 15) instead of adding an edge from Na to N[o] we had added an edge from Na to Nb (mirroring the handling of unwrapped flows), we would miss some flows. Conceptually, according to Definition 2.4, modeling wrapped flow requires tracking the wrapper objects (from where they are created) rather than the variable b in the store operation b.f = a (line 13). For example, in the case of Figure 4, consider the store operation this.next = obj (line 15) where this (line 15) and itr (line 8) both point to the Iterator object created in line 8. If we added an edge from node Nobj to node Nthis (rather than Nobj to Nitr), the flow tracking from Nthis would not lead to the return statement (line 9) in the Out method, because the wrapped flow flows out through node Nitr in this case. However, it is safe to add an edge to node Nitr instead (as we do in line 15 in Algorithm 1) since the wrapper object is originally assigned to itr, so that the flow of the wrapper object is taken into account as required by Definition 2.4. Through Algorithm 1, we can see that wrapped and unwrapped flows can be naturally expressed in the PFG by handling the store/load operations (lines 10ś15) recursively during the graph traversal. In addition, the newly added edges for wrapped and unwrapped flows build new connections with existing OFG edges that model direct flows. As a result, the generated PFG also naturally expresses combinations of all three kinds of flows. Figure 8 shows a partial PFG example for class Collection from Figure 4. The existing OFG is constructed following the rules in Figure 7. In Figure 8, in the three object field nodes (C1.elem, C2.elem, and Itr.next), the abstract objects respectively denoted by C1, C2, and Itr represent the objects of classes Collection and Iterator. Node obj corresponds to Na in line 15 in Algorithm 1; the edge from node obj to node Itr.next corresponds to the store operation this.next = obj in line 15 in Figure 4, and also the store operation b.f = a in line 13 in Algorithm 1. According to Proc. ACM Program. Lang., Vol. 2, No. OOPSLA, Article 141. Publication date: November 2018