(-,o）∈pt(--) [OAG-NODE] o:∈N Oroot∈N [OAG-DUMMYNODE] (,oi）∈pt(-,nthis）m∈M oj is allocated in m [OAG-EDGE] 0i→0∈E oiE N o:oroot oi does not have any incoming edge [OAG-DUMMYEDGE 0root→oi∈E Fig.6:Rules for building the OAG,G=(N,E),for a program based on a pre-analysis. Ezample 1.Figure 4 gives the OAGs for the two programs in Figs.1 and 2.For reasons of symmetry,let us apply the rules in Fig.6 to build the OAG in Fig.4(a) only.Suppose we perform a context-insensitive Andersen's pointer analysis as the pre-analysis on the program in Fig.1.The points-to sets are:pt(v1)=pt(v2)= {0/1,0/2},pt(a1)={A/1},pt(a2)={A/2},pt(b)={B/1},and pt(c)= {C/1}.By [OAG-NODE]and [OAG-DUMMIYNODE],N [oroot,A/1,A/2,B/1,C/1,0/1, 0/2}.By [OAG-Enc,we add A/1→B/1,A/2→B/1andB/1→C/1,since B/1 is allocated in foo()with the receiver objects being A/1 and A/2 and C/1 is allocated in bar()on the receiver object B/1.By [OAG-DUMMYEDGE],we add 0root→A/1,Oroot→A/2,0root→0/1 and Oroot+0/2. ▣ Due to recursion,an OAG may have cycles including self-loops.This means that an abstract heap object may be a direct or indirect allocator object of another heap object,and conversely (with both being possibly the same). 4.3 Context Selection Figure 7 establishes some basic relations in an OAG,G=(N,E),with possibly cycles.By [REACH-REFLEXIVE]and [REACH-TRANSITIvE],we speak of graph reachability in the standard manner.In [CoNFLUENCE),Yoi identifies a conventional confluence point.In [DIVERGENCE],0iot states that oi is a divergence point,with at least two outgoing paths reaching ot,implying that either o:is a confluence point or at least one confluence point exists earlier on the two paths. oi∈N 0:→0∈E0j0k [REACH-REFLEXIVE] REACH-TRANSITIVE] 0540 0i+0k 0→0i∈E0k→o:∈E05≠0k [【CONFLUENCE Yoi 0,→0；∈EO:→ok∈E0≠oeO)00kO:DIVERGENCE国 0i<0t Fig.7:Rules for basic relations in an OAG,G=(N,E).h , oii ∈ pt( , ) oi ∈ N [OAG-Node] oroot ∈ N [OAG-DummyNode] h , oii ∈ pt( , mthis) m ∈ M oj is allocated in m oi → oj ∈ E [OAG-Edge] oi ∈ N oi 6= oroot oi does not have any incoming edge oroot → oi ∈ E [OAG-DummyEdge] Fig. 6: Rules for building the OAG, G = (N, E), for a program based on a pre-analysis. Example 1. Figure 4 gives the OAGs for the two programs in Figs. 1 and 2. For reasons of symmetry, let us apply the rules in Fig. 6 to build the OAG in Fig. 4(a) only. Suppose we perform a context-insensitive Andersen’s pointer analysis as the pre-analysis on the program in Fig. 1. The points-to sets are: pt(v1) = pt(v2) = {O/1, O/2}, pt(a1) = {A/1}, pt(a2) = {A/2}, pt(b) = {B/1}, and pt(c) = {C/1}. By [OAG-Node] and [OAG-DummyNode], N = {oroot, A/1, A/2, B/1, C/1, O/1, O/2}. By [OAG-Edge], we add A/1 → B/1, A/2 → B/1 and B/1 → C/1, since B/1 is allocated in foo() with the receiver objects being A/1 and A/2 and C/1 is allocated in bar() on the receiver object B/1. By [OAG-DummyEdge], we add oroot → A/1, oroot → A/2, oroot → O/1 and oroot → O/2. ut Due to recursion, an OAG may have cycles including self-loops. This means that an abstract heap object may be a direct or indirect allocator object of another heap object, and conversely (with both being possibly the same). 4.3 Context Selection Figure 7 establishes some basic relations in an OAG, G = (N, E), with possibly cycles. By [Reach-Reflexive] and [Reach-Transitive], we speak of graph reachability in the standard manner. In [Confluence], goi identifies a conventional confluence point. In [Divergence], oi ≺ ot states that oi is a divergence point, with at least two outgoing paths reaching ot, implying that either ot is a confluence point or at least one confluence point exists earlier on the two paths. oi ∈ N oi oi [Reach-Reflexive] oi → oj ∈ E oj ok oi ok [Reach-Transitive] oj → oi ∈ E ok → oi ∈ E oj 6= ok goi [Confluence] oi → oj ∈ E oi → ok ∈ E oj 6= ok oj ot ok ot oi ≺ot [Divergence] Fig. 7: Rules for basic relations in an OAG, G = (N, E)