"ci"in Table 2 may already exist and can be reused,(2)the over 2type,respectively.In the case of M-3type/3type, pre-analysis time is relatively small(compared to the analy- these percentages are 0.02%and 0.22%,respectively. sis time of a subsequent M-kA),and (3)the pre-analysis will be used to drive many points-to analyses. Importance of Context-Sensitivity Context-sensitivity is Improved Efficiency MAHJONG is versatile enough in ac- significant for improving the precision of type-dependent clients,measured by #may-fail casts,#poly call sites and celerating all the five points-to analyses with three different types of context-sensitivity.For every program where M-kA #call graph edges,in Table 2.Without context-sensitivity, is scalable,a speedup over k.A is obtained. #may-fail casts,#poly call sites and #call graph edges will MAHJONG is highly effective in boosting performance. be 2027.3122 and 75162,respectively,on average,across For the programs where both kA and M-kA are scalable, all the programs.With context-sensitivity (by using the MAHJONG achieves an average speedup of 15.4X (rang- most precise MAHJONG-based points-to analysis for each ing from 1.03X by M-2obj/2obj for bloat to 168.8X by program,e.g.,M-3obj for antlr and M-2obj for chart), M-3obj/3obj for luindex).Table 2 divides visually the 12 these numbers become substantially smaller:1101,2530 and programs into two groups.For the top six,k.A scales when- 63994.This demonstrates convincingly the necessity of em- ever M-k.A scales.However,M-k.A is faster than kA,achiev- bracing context-sensitivity even for type-dependent clients. ing an average speedup of 22.2X.This is especially signif- 6.2.3 Discussion icantly for the most-precise configuration M-3obj/3obj.For every program in the bottom six,MAHJONG enables using We discuss two observations about some results in Table 2. a more precise points-to analysis that is not scalable if the allocation-site abstraction is used instead. Speedups of M-3obj over 3obj MAHJONG is most impres- sive in scaling 3obj,the most precise baseline used.For the Preserved Precision For every program,as shown in Ta- four programs,antlr,fop,luindex and pmd,where 3objis ble 2.MAHJONG achieves nearly the same precision for ev- scalable,M-3obj is 131X faster,on average,while achieving ery client under every configuration M-kAk.A.Thus,merg- nearly the same precision for all the three clients.For the re- ing type-consistent objects can maximally preserve preci- maining eight,where 3obj is unscalable,M-3obj is scalable sion as discussed in Section 3.6 and validated here. for checkstyle,xalan,lusearch,JPC and fingbugs,by Call-Site-Sensitivity M-2cs is no more precise than 2cs in spending an average of 33.42 minutes only. principle(Section 3.6)but nearly as precise in practice. Why does M-3obj/3obj deliver significantly better For devirtualization,M-2cs is equally as precise as 2cs. speedups than M-2obj/2obj?By using one extra level of For may-fail casting.M-2cs is negligibly worse than 2cs context elements than 2obj,3obj often incurs an exponential (with an average precision loss of 0.04%),by report- growth in the number of contexts used.By merging type- ing only 5 more may-fail casts each in checkstyle consistent objects,which happen to be used as context el- and findbugs.For call graph construction,M-2cs is ements at this extra level in 3obj,M-3obj can drastically also marginally worse(with an average precision loss of reduce the number of contexts used and thus accelerate the 0.006%),by including only a few extra edges in pmd (3). analysis.Consider luindex,where the speedup achieved chart (14),checkstyle (20),and findbugs(17). by M-3obj/3obj is the highest obtained.The number of Object-Sensitivity M-kobj is also no more precise than context-sensitive points-to relations produced under 2obj is kobj in principle (Section 3.6)but nearly as precise in 9,255,034 but grows to 191,160,483 under 3obj,which are practice.For call graph construction,devirtualization and both reduced significantly to 4,256,310 under M-3obj. may-fail casting,M-2obj experiences a small loss of pre- Unscalability of MAHJONG-based Points-to Analyses As cision of 0.02%,0.23%and 0.04%over 2obj.respec- shown in Table 2,M-2cs is unscalable for eclipse and M- tively,on average.For M-3obj over 3obj,these percent- 3obj is unscalable for bloat,chart and eclipse.Why is ages are 0.02%,0.29%and 0.00%,respectively.For may- fail casting,M-2obj is on a par with 2obj if checkstyle M-3obj scalable for some large programs such as findbugs but unscalable for some small ones such as bloat?As is ignored,and M-3obj is equally as precise as 3obj. shown in Figure 8,MAHJONG creates 5233 objects for Type-Sensitivity M-ktype may lose or gain precision com- findbugs but only 3107 objects for bloat. pared with ktype,as discussed in Section 3.6.For may- M-3obj is unscalable for bloat possibly due to its object fail casting,M-ktype is slightly more precise than ktype structure used.Some methods are both invoked on many (ab- in all the programs except antlr.The average precision stract)receiver objects and allocate many objects.Thus,the gains for M-2type/2type and M-3type/3type are 0.91% number of contexts becomes extremely large.To alleviate and 1.11%,respectively.For the other two clients,M- this problem,one solution is to use a coarser relation than ktype is slightly less precise than ktype in every program. given in Definition 2.1 so that more objects can be merged For call graph construction and devirtualization,M-2type together.Another solution is to apply 3obj only selectively experiences a small loss of precision of 0.02%and 0.18% to parts of the program when moving from 2obj to 3obj. 289“ci” in Table 2 may already exist and can be reused, (2) the pre-analysis time is relatively small (compared to the analy￾sis time of a subsequent M-kA), and (3) the pre-analysis will be used to drive many points-to analyses. Improved Efficiency MAHJONG is versatile enough in ac￾celerating all the five points-to analyses with three different types of context-sensitivity. For every program where M-kA is scalable, a speedup over kA is obtained. MAHJONG is highly effective in boosting performance. For the programs where both kA and M-kA are scalable, MAHJONG achieves an average speedup of 15.4X (rang￾ing from 1.03X by M-2obj/2obj for bloat to 168.8X by M-3obj/3obj for luindex). Table 2 divides visually the 12 programs into two groups. For the top six, kA scales when￾ever M-kA scales. However, M-kA is faster than kA, achiev￾ing an average speedup of 22.2X. This is especially signif￾icantly for the most-precise configuration M-3obj/3obj. For every program in the bottom six, MAHJONG enables using a more precise points-to analysis that is not scalable if the allocation-site abstraction is used instead. Preserved Precision For every program, as shown in Ta￾ble 2, MAHJONG achieves nearly the same precision for ev￾ery client under every configuration M-kA/kA. Thus, merg￾ing type-consistent objects can maximally preserve preci￾sion as discussed in Section 3.6 and validated here. Call-Site-Sensitivity M-2cs is no more precise than 2cs in principle (Section 3.6) but nearly as precise in practice. For devirtualization, M-2cs is equally as precise as 2cs. For may-fail casting, M-2cs is negligibly worse than 2cs (with an average precision loss of 0.04%), by report￾ing only 5 more may-fail casts each in checkstyle and findbugs. For call graph construction, M-2cs is also marginally worse (with an average precision loss of 0.006%), by including only a few extra edges in pmd (3), chart (14), checkstyle (20), and findbugs (17). Object-Sensitivity M-kobj is also no more precise than kobj in principle (Section 3.6) but nearly as precise in practice. For call graph construction, devirtualization and may-fail casting, M-2obj experiences a small loss of pre￾cision of 0.02%, 0.23% and 0.04% over 2obj, respec￾tively, on average. For M-3obj over 3obj, these percent￾ages are 0.02%, 0.29% and 0.00%, respectively. For may￾fail casting, M-2obj is on a par with 2obj if checkstyle is ignored, and M-3obj is equally as precise as 3obj. Type-Sensitivity M-ktype may lose or gain precision com￾pared with ktype, as discussed in Section 3.6. For may￾fail casting, M-ktype is slightly more precise than ktype in all the programs except antlr. The average precision gains for M-2type/2type and M-3type/3type are 0.91% and 1.11%, respectively. For the other two clients, M￾ktype is slightly less precise than ktype in every program. For call graph construction and devirtualization, M-2type experiences a small loss of precision of 0.02% and 0.18% over 2type, respectively. In the case of M-3type/3type, these percentages are 0.02% and 0.22%, respectively. Importance of Context-Sensitivity Context-sensitivity is significant for improving the precision of type-dependent clients, measured by #may-fail casts, #poly call sites and #call graph edges, in Table 2. Without context-sensitivity, #may-fail casts, #poly call sites and #call graph edges will be 2027, 3122 and 75162, respectively, on average, across all the programs. With context-sensitivity (by using the most precise MAHJONG-based points-to analysis for each program, e.g., M-3obj for antlr and M-2obj for chart), these numbers become substantially smaller: 1101, 2530 and 63994. This demonstrates convincingly the necessity of em￾bracing context-sensitivity even for type-dependent clients. 6.2.3 Discussion We discuss two observations about some results in Table 2. Speedups of M-3obj over 3obj MAHJONG is most impres￾sive in scaling 3obj, the most precise baseline used. For the four programs, antlr, fop, luindex and pmd, where 3obj is scalable, M-3obj is 131X faster, on average, while achieving nearly the same precision for all the three clients. For the re￾maining eight, where 3obj is unscalable, M-3obj is scalable for checkstyle, xalan, lusearch, JPC and fingbugs, by spending an average of 33.42 minutes only. Why does M-3obj/3obj deliver significantly better speedups than M-2obj/2obj? By using one extra level of context elements than 2obj, 3obj often incurs an exponential growth in the number of contexts used. By merging type￾consistent objects, which happen to be used as context el￾ements at this extra level in 3obj, M-3obj can drastically reduce the number of contexts used and thus accelerate the analysis. Consider luindex, where the speedup achieved by M-3obj/3obj is the highest obtained. The number of context-sensitive points-to relations produced under 2obj is 9,255,034 but grows to 191,160,483 under 3obj, which are both reduced significantly to 4,256,310 under M-3obj. Unscalability of MAHJONG-based Points-to Analyses As shown in Table 2, M-2cs is unscalable for eclipse and M- 3obj is unscalable for bloat, chart and eclipse. Why is M-3obj scalable for some large programs such as findbugs but unscalable for some small ones such as bloat? As shown in Figure 8, MAHJONG creates 5233 objects for findbugs but only 3107 objects for bloat. M-3obj is unscalable for bloat possibly due to its object structure used. Some methods are both invoked on many (ab￾stract) receiver objects and allocate many objects. Thus, the number of contexts becomes extremely large. To alleviate this problem, one solution is to use a coarser relation than ≡ given in Definition 2.1 so that more objects can be merged together. Another solution is to apply 3obj only selectively to parts of the program when moving from 2obj to 3obj. 289