DetailAST(Row 3)and the other that contains one single Allocation-Site Abstraction ☑MAHJONG object with null fields(Row 6). 15000 1433 6.2 RO2:MAHJONG-based Points-to Analysis 1088811181 Mainstream points-to analyses for Java programs rely on 10000 414 810 the allocation-site-based abstraction to model the heap [20- 22,39.40,42,48].We demonstrate experimentally that MAHJONG is a better alternative for type-dependent clients. Concretely,we show that MAHJONG can achieve the fol- lowing goal in the real world.Suppose a software developer intends to apply a points-to analysis to a program under a given time budget.MAHJONG opens up new opportunities for the developer to either accelerate the chosen points-to Figure 8.Number of abstract objects created by the allocation-site abstraction and MAHJONG. analysis or replace it with a more precise but more expen- sive points-to analysis under still the same budget. 6.2.1 Baselines and Metrics 40961,3769 1024 We consider three types of context-sensitive points-to anal- 256 ,73,59) yses:call-site-sensitivity (cs),object-sensitivity (obj)and 6 type-sensitivity (type).Specifically,five points-to analyses T03， in DOop [14]are selected as baselines:2cs (2-call-site- 1 sensitive).2obj(2-object-sensitive).3obj(3-object-sensitive). .16 64 256 1024 Equivalence Class(Sizes) 2type (2-type-sensitive),and 3type (3-type-sensitive).In principle,2cs is not compatible with the others,3.A is no Figure 9.Object merging in checkstyle. less precise than 2.A,and kobj is no less precise than ktype. As for 1.A,it has been demonstrated that its precision is significantly less than that of kA,where k>1 [20,39]. Equiv.Class Total No. As a result,1.A is not used in the recent points-to analysis Rank Type Size Remarks of Objects literature [15,40,48]and is thus omitted in our baselines. java.lang.StringBuilder 1303 1303 chart Currently,each baseline k.A uses the allocation-site ab- 2 java.lang.Object] 690 1353 String straction.M-k.A denotes the version of k.A that uses the heap 12 antlr.ASTPair 108 109 DetailAST abstraction provided by MAHJONG.Thus,there are also five 55 java.lang.Object[] 2 1353 Integer MAHJONG-based points-to analyses altogether. 65 java.lang.Object 9 1353 OName The three type-dependent clients,call graph construction, 260 antlr.ASTPair 109 null devirtualization and may-fail casting,are widely used in the literature [20,22,39,40,48].We consider the following Table 1.Some equivalence classes in checkstyle. metrics:the number of call graph edges(#call graph edges), the number of casting operations that may fail (#may-fail casts),and the number of virtual call sites that cannot be along any field access path)and thus merged.This is the disambiguated into mono-calls (#poly call sites). largest equivalence class,corresponding to the right-most The time budget for each analysis is set to 5 hours. point marked by (1303,1)in Figure 9. For some other types like Object[](Rows 2,4 and 6.2.2 Efficiency and Precision 5),blindly merging all its objects would be imprecise Table 2 presents our results,showing clearly the effective- (Section 2.1).In contrast,MAHJONG merges only type- ness of MAHJONG in boosting existing points-to analyses consistent objects in order to maximally preserve preci- while maintaining their precision for type-dependent clients. sion for type-dependent clients.Thus,MAHJONG ends up For each program,five metrics are considered:"analysis with different equivalent classes containing objects of type time”,“speedup”,“#may-fail casts'”,“poly call sites'”and Object [for storing objects of different types,such as “#call graph edges'”.In all cases except“speedup”,smaller String(Row 2),Integer(Row 4),and QName(Row 5). is better.With"speedup"ignored,Table 2 contains 480 con- Finally,we show that MAHJONG can also distinguish crete results (=4 metrics x 12 programs x 10 points-to anal- null from other objects,because null may affect preci- yses (including the 5 baselines and 5 MAHJONG variants)). sion as explained in Section 3.6.MAHJONG partitions 109 In computing the speedup of M-kA over kA for a pro objects of ASTPair into two equivalence classes,with one gram,the pre-analysis time on the program is ignored.There containing 108 objects whose fields point to objects of type are three reasons:(1)the points-to information produced by 287Figure 8. Number of abstract objects created by the allocation-site abstraction and MAHJONG. (1, 3769) (2, 72) (3, 59) (1303, 1) 1 4 16 64 256 1024 4096 1 4 16 64 256 1024 No. of Equivalence Classes Equivalence Class (Sizes) Figure 9. Object merging in checkstyle. Equiv. Class Total No. Rank Type Size of Objects Remarks 1 java.lang.StringBuilder 1303 1303 char[] 2 java.lang.Object[] 690 1353 String 12 antlr.ASTPair 108 109 DetailAST 55 java.lang.Object[] 12 1353 Integer 65 java.lang.Object[] 9 1353 QName 260 antlr.ASTPair 1 109 null Table 1. Some equivalence classes in checkstyle. along any field access path) and thus merged. This is the largest equivalence class, corresponding to the right-most point marked by (1303, 1) in Figure 9. For some other types like Object[] (Rows 2, 4 and 5), blindly merging all its objects would be imprecise (Section 2.1). In contrast, MAHJONG merges only type￾consistent objects in order to maximally preserve preci￾sion for type-dependent clients. Thus, MAHJONG ends up with different equivalent classes containing objects of type Object[] for storing objects of different types, such as String (Row 2), Integer (Row 4), and QName (Row 5). Finally, we show that MAHJONG can also distinguish null from other objects, because null may affect preci￾sion as explained in Section 3.6. MAHJONG partitions 109 objects of ASTPair into two equivalence classes, with one containing 108 objects whose fields point to objects of type DetailAST (Row 3) and the other that contains one single object with null fields (Row 6). 6.2 RQ2: MAHJONG-based Points-to Analysis Mainstream points-to analyses for Java programs rely on the allocation-site-based abstraction to model the heap [20– 22, 39, 40, 42, 48]. We demonstrate experimentally that MAHJONG is a better alternative for type-dependent clients. Concretely, we show that MAHJONG can achieve the fol￾lowing goal in the real world. Suppose a software developer intends to apply a points-to analysis to a program under a given time budget. MAHJONG opens up new opportunities for the developer to either accelerate the chosen points-to analysis or replace it with a more precise but more expen￾sive points-to analysis under still the same budget. 6.2.1 Baselines and Metrics We consider three types of context-sensitive points-to anal￾yses: call-site-sensitivity (cs), object-sensitivity (obj) and type-sensitivity (type). Specifically, five points-to analyses in DOOP [14] are selected as baselines: 2cs (2-call-site￾sensitive), 2obj (2-object-sensitive), 3obj (3-object-sensitive), 2type (2-type-sensitive), and 3type (3-type-sensitive). In principle, 2cs is not compatible with the others, 3A is no less precise than 2A, and kobj is no less precise than ktype. As for 1A, it has been demonstrated that its precision is significantly less than that of kA, where k > 1 [20, 39]. As a result, 1A is not used in the recent points-to analysis literature [15, 40, 48] and is thus omitted in our baselines. Currently, each baseline kA uses the allocation-site ab￾straction. M-kA denotes the version of kA that uses the heap abstraction provided by MAHJONG. Thus, there are also five MAHJONG-based points-to analyses altogether. The three type-dependent clients, call graph construction, devirtualization and may-fail casting, are widely used in the literature [20, 22, 39, 40, 48]. We consider the following metrics: the number of call graph edges (#call graph edges), the number of casting operations that may fail (#may-fail casts), and the number of virtual call sites that cannot be disambiguated into mono-calls (#poly call sites). The time budget for each analysis is set to 5 hours. 6.2.2 Efficiency and Precision Table 2 presents our results, showing clearly the effective￾ness of MAHJONG in boosting existing points-to analyses while maintaining their precision for type-dependent clients. For each program, five metrics are considered: “analysis time”, “speedup”, “#may-fail casts”, “#poly call sites” and “#call graph edges”. In all cases except “speedup”, smaller is better. With “speedup” ignored, Table 2 contains 480 con￾crete results (= 4 metrics × 12 programs × 10 points-to anal￾yses (including the 5 baselines and 5 MAHJONG variants)). In computing the speedup of M-kA over kA for a pro￾gram, the pre-analysis time on the program is ignored. There are three reasons: (1) the points-to information produced by 287