Y.Li,T.Tan,Y.Zhang,and J.Xue XX:13 Example 4.According to the data-flow facts shown for the program given in Figure 5, the tailored program consists of all the lines except lines 38-40 according to (12). 4.2 SC Extension We make use of the points-to information provided by a pointer analysis to extend a SC to reduce infeasible paths that would otherwise be introduced by SCDFA.Given a statement sequence SE SC,SCEXT will lengthen it recursively by prepending the object allocation sites representing the calling contexts for the method containing its first statement,as demonstrated in Section 3.2.The general algorithm for lengthening a sequence S:L..n is as follows.Suppose that Li resides in a method m invoked at a virtual call site.Let A1,..,Ar be its all r allocation sites for creating the receiver objects on which m is invoked.Then S grows into A1→L1→→Ln,·,Ar→L1→→Ln,and the same process continues. With longer SCs,SCDFA will be less efficient due to more data-flow facts introduced.We will keep a SC extension point if it is embedded in a branch and ignore it otherwise.This way, SCEXT can enable SCDFA to avoid infeasible paths more effectively by exploiting branch correlations.A statement is said to be embedded in a branch if it appears intraprocedurally (directly)or interprocedurally(indirectly)inside a multi-way branching statement or a target method invoked at a polymorphic call site (i.e.,a virtual call site with at least two target methods).Let Stmts be the set of all statements in GIcFG.We use the following function InBranchOrVC:Stmts-boolean to capture formally this branch-embedding relation: true if InIntraBranch(s InBranchOrVC(s)= false else if InMain(s) (13) InInterBranchOrVC(s)otherwise where InIntraBranch(s)determines if s appears directly in a branch or not and InMain(s) tells us whether s appears directly in main()or not.InInterBranchOrVC:Stmts-boolean checks to see whether s is embedded in a branch interprocedurally or not: InInterBranchOrVC(s)=(InBranchOrVC(c)V |Callee(c)l>1) cE Caller(m) (14) where m is the method containing s where Caller(m)returns the set of call sites at which m is invoked.For each call site c,there are two disjuncts.One represents a recursive application of InBranchOrVC defined in(13) to c.The other one,Callee(c)>1,evaluates to true if the call site c is polymorphic. Example 5.For the program in Figure 7,as discussed in Section 3.2,SCEXT starts with SCline 25:line 25,grows it to SCline 25 line 3-line 20-line 11 line 25,and finally settles with ESCline 25:line 20-line 11-line 25.Let us see why a SC extension point is kept or ignored.Line 3 should be ignored since InBranchOrVC(line 3)=InMain(line 3)= false.Line 20 is retained since InInterBranchOrVC(line 20)=InIntraBranch(line 20)= true.Finally,line 11 is also retained because we have InInterBranchOrVC(line 11)= InInterBranchOrVC(line 8)=InInterBranchOrVC(line 5)=|Callee(line 5)>1 true, where the call site at line 5 is polymorphic according to the points-to information provided. In practice,SCDFA does not usually benefit from a SC extension point if it appears in a control-fow cycle (a loop or a recursion cycle)in GICFG.Such cycle-related points are identified and ignored as well.To detect recursion cycles effectively,we apply Tarjan's algorithm [48]to find strongly connected components on the call graph of the program.To detect (natural)loops,we resort to a textbook loop detection algorithm.The statements reachable directly or indirected from a loop are also considered as being part of the loop. EC00P2016Y. Li, T. Tan, Y. Zhang, and J. Xue XX:13 I Example 4. According to the data-flow facts shown for the program given in Figure 5, the tailored program consists of all the lines except lines 38 – 40 according to (12). 4.2 SC Extension We make use of the points-to information provided by a pointer analysis to extend a SC to reduce infeasible paths that would otherwise be introduced by SCDFA. Given a statement sequence S ∈ SC, SCEXT will lengthen it recursively by prepending the object allocation sites representing the calling contexts for the method containing its first statement, as demonstrated in Section 3.2. The general algorithm for lengthening a sequence S : L1→ · · · →Ln is as follows. Suppose that L1 resides in a method m invoked at a virtual call site. Let A1, · · · , Ar be its all r allocation sites for creating the receiver objects on which m is invoked. Then S grows into A1→L1→ · · · →Ln, · · · , Ar→L1→ · · · →Ln, and the same process continues. With longer SCs, SCDFA will be less efficient due to more data-flow facts introduced. We will keep a SC extension point if it is embedded in a branch and ignore it otherwise. This way, SCEXT can enable SCDFA to avoid infeasible paths more effectively by exploiting branch correlations. A statement is said to be embedded in a branch if it appears intraprocedurally (directly) or interprocedurally (indirectly) inside a multi-way branching statement or a target method invoked at a polymorphic call site (i.e., a virtual call site with at least two target methods). Let Stmts be the set of all statements in GICFG. We use the following function InBranchOrVC : Stmts → boolean to capture formally this branch-embedding relation: InBranchOrVC(s) =    true if InIntraBranch(s) false else if InMain(s) InInterBranchOrVC(s) otherwise (13) where InIntraBranch(s) determines if s appears directly in a branch or not and InMain(s) tells us whether s appears directly in main() or not. InInterBranchOrVC : Stmts → boolean checks to see whether s is embedded in a branch interprocedurally or not: InInterBranchOrVC(s) = _ c ∈ Cal ler(m)  InBranchOrVC(c) ∨ |Callee(c)| > 1  where m is the method containing s (14) where Caller(m) returns the set of call sites at which m is invoked. For each call site c, there are two disjuncts. One represents a recursive application of InBranchOrVC defined in (13) to c. The other one, |Callee(c)| > 1, evaluates to true if the call site c is polymorphic. I Example 5. For the program in Figure 7, as discussed in Section 3.2, SCEXT starts with SCline 25: line 25, grows it to SCline 25 : line 3 → line 20 → line 11 → line 25, and finally settles with ESCline 25 : line 20 → line 11 → line 25. Let us see why a SC extension point is kept or ignored. Line 3 should be ignored since InBranchOrVC(line 3) = ¬InMain(line 3) = false. Line 20 is retained since InInterBranchOrVC(line 20) = InIntraBranch(line 20) = true. Finally, line 11 is also retained because we have InInterBranchOrVC(line 11) = InInterBranchOrVC(line 8) = InInterBranchOrVC(line 5) = |Callee(line 5)| > 1 = true, where the call site at line 5 is polymorphic according to the points-to information provided. In practice, SCDFA does not usually benefit from a SC extension point if it appears in a control-flow cycle (a loop or a recursion cycle) in GICFG. Such cycle-related points are identified and ignored as well. To detect recursion cycles effectively, we apply Tarjan’s algorithm [48] to find strongly connected components on the call graph of the program. To detect (natural) loops, we resort to a textbook loop detection algorithm. The statements reachable directly or indirected from a loop are also considered as being part of the loop. E COO P 2 0 1 6