2)m is a direct or indirect caller of a()or contains s e6 main() s9:d(): e7 (as is the case when sa is replaced by s). s10:e(j9 Then Connect(s1,s2)comprises the two call-chains,one from m to b()and one from m to a(),both computed d(){ e(){ :889 el e2 by BFS.In Figure 8(c),m is found to be cO).So 9 Connect(s1,s2)={c0→a0,c0→b0} Common(s1,s2)is s1 if m contains s1 or is the call a(){ statement in m that calls (directly or indirectly)a method e3 s1:p.f=; e5 that contains s1.In Figure 8(c),Common(s1,s2)=s3. c(){ b(){ (If we modify the example by replacing s3 by s1,then e4 s4:x=b(); g2·y=白.1： Common(s1,s2）=s1.) s3:return y } In theory,Connect(s1,s2)is not the smallest.In practice. however,Connecr(s1,s2)is nearly so due to BFS used,as all (a)Call graph the reflection-related statements are typically used together. e2 Algorithm 1:Call Graph Reduction. d( Input A reflective call site R Output:GR 1 Function BuildSubgraph() a() e5 e3 2 G ={the method containing R): foreach s1→s2∈DRdo visited(s1 s2):=false; foreach s→R∈DRdo b() RECBUILD(⊥，s→R): return GR 8 Procedure RECBUILD(u,s1 s2) (b)Incorrect G宽 (C)GR 9 visited(s1=s2):=true; 10 if s1=s2 spans two distinct methods then Fig.9:Construction of incorrect and correct GR 11 ifu==⊥then u=s2; 2 Gs1→u=Connect(s1,g G.G does not contain a sequence of method calls that 13 GR=GRUG1→u: allows the du-chain s1→s2→s3→s4 to be established.. 14 Ca1→u=Common(s1,u: Figure 9(c)gives the subgraph GR constructed by our 15 foreach s3→s1∈DRdo if !visited(s3=s1)then algorithm.We first compute Gss=-Connect(s3,s4)= 16 17 |RECBUILD(Cg1→u,s3→s1月 fe4}and ca354 Common(s3,s4)=s4.We then com- pute Gs1→s4=Connecr(s1,sa）={e1,e3}and ca1→84= 18 return; Common(s1,s4)=s5.By construction,the following two facts are true.(1)In Gs4 reaches the method b()that Let us now describe BuildSubGraph(),in Algorithm 1,that contains s3.(2)In G,51 can reach s4.As s2s3 is builds GR for a reflective call R.We tag a du-pair as visited intraprocedural,s2 and s3 reside in the same method.Thus, in the standard manner to deal with dependence cycles.One in GR,s can reach b()that contains also s2.By computing simple-minded but incorrect approach would compute: Connect(s1,s4)instead of Connect(s1,s2),s1 s2 is also G咒-= U respected.As shown,d()can trigger a sequence of method Connect(s1,s2） (2) calls,s5 a(),s6:c()and s:=b0,so that the du-chain Dx is interprocedural s1→s2÷s3→s4 holds. While G contains the statements in D.some du-chains Example 1.Da2 is given in Equation (1),which contains two may no longer be preserved,as some caller-callee relations interprocedural du-pairs.12=17 and 17=35.By apply- are missing.Consider Figure 9.The program's call graph is given in Figure 9(a).where s4 symbolizes R.Suppose ing Algorithm 1,we obtain Connect(17,35)=e1,e2,e3} and Common(17,35)=(12}.Finally,Connect(17,35)= Dr={s1→s2,s2→s3,s3→s4}.For the du-chain s1→ te1,e2,e3}is the subgraph Gr obtained in Figure 3. s2→s3→s4,s1→s2ands3→s4 are interprocedural and s2=s3 is intraprocedural.Due to the recursive nature of our B.Path-based Slicing algorithm,it suffices to use this du-chain to explain how our Given D that contains the du-chains for a reflective call algorithm works and argue for its correctness. R,we generate its path-based slices in three steps. G=Connect(s1:s2)UConnect(s3;sA)={e2,es}ufes} 1)Partitioning DR:We partition DR into du-chain groups given in Figure 9(b)is incorrect.As e()cannot reach c()in so that in one group,every variable has exactly one definition, 172) m is a direct or indirect caller of a() or contains s1 (as is the case when s3 is replaced by s1). Then Connect(s1, s2) comprises the two call-chains, one from m to b() and one from m to a(), both computed by BFS. In Figure 8(c), m is found to be c(). So Connect(s1, s2) = {c() → a(), c() → b()}. Common(s1, s2) is s1 if m contains s1 or is the call statement in m that calls (directly or indirectly) a method that contains s1. In Figure 8(c), Common(s1, s2) = s3. (If we modify the example by replacing s3 by s1, then Common(s1, s2) = s1.) In theory, Connect(s1, s2) is not the smallest. In practice, however, Connect(s1, s2) is nearly so due to BFS used, as all the reflection-related statements are typically used together. Algorithm 1: Call Graph Reduction. Input : A reflective call site R Output: GR 1 Function BuildSubgraph() 2 GR := {the method containing R}; 3 foreach s1 ⇒ s2 ∈ DR do 4 visited(s1 ⇒ s2) := false; 5 foreach s ⇒R∈ DR do 6 RECBUILD(⊥, s ⇒ R); 7 return GR 8 Procedure RECBUILD(u, s1 ⇒ s2) 9 visited(s1 ⇒ s2) := true; 10 if s1 ⇒ s2 spans two distinct methods then 11 if u == ⊥ then u := s2; 12 Gs1⇒u = Connect(s1, u); 13 GR = GR ∪ Gs1⇒u; 14 cs1⇒u = Common(s1, u); 15 foreach s3 ⇒ s1 ∈ DR do 16 if !visited(s3 ⇒ s1) then 17 RECBUILD(cs1⇒u, s3 ⇒ s1); 18 return; Let us now describe BuildSubGraph(), in Algorithm 1, that builds GR for a reflective call R. We tag a du-pair as visited in the standard manner to deal with dependence cycles. One simple-minded but incorrect approach would compute: Gerr R = s1⇒s2∈DR is interprocedural Connect(s1, s2) (2) While Gerr R contains the statements in DR, some du-chains may no longer be preserved, as some caller-callee relations are missing. Consider Figure 9. The program’s call graph is given in Figure 9(a), where s4 symbolizes R. Suppose DR = {s1 ⇒ s2, s2 ⇒ s3, s3 ⇒ s4}. For the du-chain s1 ⇒ s2 ⇒ s3 ⇒ s4, s1 ⇒ s2 and s3 ⇒ s4 are interprocedural and s2 ⇒ s3 is intraprocedural. Due to the recursive nature of our algorithm, it suffices to use this du-chain to explain how our algorithm works and argue for its correctness. Gerr R = Connect(s1, s2)∪Connect(s3, s4) = {e2, e5}∪{e4} given in Figure 9(b) is incorrect. As e() cannot reach c() in d(){ s5: s6: a(); c(); } a(){ s1: p.f } = …; c(){ s4: b(); } b(){ s2: s3: y return } = q.f; x = y; e1 e2 e3 e5 e4 e(){ s7: s8: a(); b(); } main(){ s9: s10: d(); e(); } e6 e7 (a) Call graph c() e2 e5 e4 b() a() e() c() e4 b() a() d() e3 e1 (b) Incorrect Gerr R (c) GR Fig. 9: Construction of incorrect and correct GR. Gerr R , Gerr R does not contain a sequence of method calls that allows the du-chain s1 ⇒ s2 ⇒ s3 ⇒ s4 to be established. Figure 9(c) gives the subgraph GR constructed by our algorithm. We first compute Gs3⇒s4 = Connect(s3, s4) = {e4} and cs3⇒s4 = Common(s3, s4) = s4. We then com￾pute Gs1⇒s4 = Connect(s1, s4) = {e1, e3} and cs1⇒s4 = Common(s1, s4) = s5. By construction, the following two facts are true. (1) In Gs3⇒s4 , s4 reaches the method b() that contains s3. (2) In Gs1⇒s4 , s1 can reach s4. As s2 ⇒ s3 is intraprocedural, s2 and s3 reside in the same method. Thus, in GR, s1 can reach b() that contains also s2. By computing Connect(s1, s4) instead of Connect(s1, s2), s1 ⇒ s2 is also respected. As shown, d() can trigger a sequence of method calls, s5 : a(), s6 : c() and s4 : x = b(), so that the du-chain s1 ⇒ s2 ⇒ s3 ⇒ s4 holds. Example 1. D42 is given in Equation (1), which contains two interprocedural du-pairs, 12 ⇒ 17 and 17 ⇒ 35. By apply￾ing Algorithm 1, we obtain Connect(17, 35) = {e1, e2, e3} and Common(17, 35) = {12}. Finally, Connect(17, 35) = {e1, e2, e3} is the subgraph GR obtained in Figure 3. B. Path-based Slicing Given DR that contains the du-chains for a reflective call R, we generate its path-based slices in three steps. 1) Partitioning DR: We partition DR into du-chain groups so that in one group, every variable has exactly one definition, 17