as context elements are modified accordingly.For an object hurts the precision,making M-A nearly as precise asA for o that is used in a calling context under A,o is replaced by type-dependent clients,in practice.The key insight behind a representative of [o]H/=(Section 3.5)under M-A. object-sensitivity [29]is to distinguish the side-effects of dif- In other words,if o is merged with some type-consistent ferent receiver objects of an instance method foo()by ana- objects,then its representative is used,instead. lyzing it under multiple calling contexts,one per receiver ob- Type-Sensitivity To trade precision for efficiency,k-type- ject.By merging a set of type-consistent receiver objects for sensitivity is derived from k-object-sensitivity by replacing foo(),we end up achieving a significant performance bene- fit at little precision loss by analyzing foo()under the same every object in a calling context with the class type that contains the corresponding allocation site for the object [39]. context by M-A rather than separately but unnecessarily by A for these receiver objects.For type-dependent clients,this If A is a k-type-sensitive analysis obtained from its corre- sponding k-object-sensitive analysis A',then M-A is simply represents a generalization of object-sensitivity. obtained from M-A'in the same type-sensitive manner. If A is type-sensitive,then M-A is nearly as precise as (sometimes slightly better or worse than)A for type- 3.6.2 Soundness and Precision of M-A over A dependent clients,in practice.Consider an equivalence class The soundness of M-A is easy to establish.If A is sound, [o]={o1,.,on}∈H/≡(Definition2.2)formed then M-A is sound as the MAHJONG heap abstraction is by the MAHJONG heap abstraction.In A,every o;that is coarser than the allocation-site abstraction used in A. used as a context element in a calling context is replaced We discuss some insights below on why merging type- by the class type that contains the allocation site for o:.In consistent objects enables M-.A to maximally preserve the M-A,01,...,on are merged and replaced by the class type precision ofA for type-dependent clients.This is true for all that contains the allocation site for a representative in [o]. Thus,the MAHJONG heap abstraction can be coarser than three types of context-sensitivity as validated later. the allocation-site abstraction for some methods and finer We first describe a rarely occurring subtle case,the null- for some others in partitioning their calling contexts,which field problem,illustrated in Figure 6,due to the imprecision depends on the representatives chosen. of the pre-analysis,causing precision loss for all the three types of MAHJONG-based context-sensitivity. Example 3.1.Suppose of.f and of.f both point to of Class T Class U during the pre-analysis (Figure 6(a))but o and null,re- alloc site1:O∥oo alloc site3yOg∥og‘o spectively,in A (Figure 6(b)).In M-A.of and of are type- alloc site 2:O;//oo Alloc Sites I and 2 Abstracted,Resp.as: consistent and thus merged into of(represented by either of type: Tand T M-ktype:U andT if and are merged as or )M-A is less precise.asofwhich points to nu in A.now points to an object of type X(Figure 6(c)). ▣ Figure 7.Precision of M-ktype over ktype. o. Let us see how the choice of representative for an equiv- alence class affects the precision of M-ktype. >null Example 3.2.In Figure 7,ktype(k-type-sensitive analysis) (a)Pre-Analysis (b)A (c)M-A will represent the allocation sites 1 and 2 by T.Thus,the Figure 6.Illustrating the null-field problem. two allocation sites that are distinguished by kobj(k-object- sensitive analysis)are merged.According to MAHJONG,of and o are type-consistent,falling into the same equivalence If A is call-site-sensitive,M-A is as precise as A for a class.If o happens to be selected as a representative,then type-dependent client if the null-field problem never occurs M-ktype will be able to distinguish the allocation sites 1 in a program analyzed by A.Recall that the pre-analysis and 2 by U and T,respectively.However,if of is selected is no more precise than A.By Definition 2.1,the objects as the representative(not shown in Figure 7),then M-ktype reached from o along the same sequence of field accesses will merge the allocation sites 1,2 and 3 by using T as the must have exactly the same type when o is modeled both context,and become less precise than ktype. context-sensitively underA and context-insensitively under M-A,resulting in the same precision in both cases.In gen- However,the choice of representative for an equivalence eral,M-A is no more precise than A due to the null-field class[o={o1,.,on}∈H/≡does not affect the problem but very close to A as the null-fields are rare. soundness of M-ktype.Regardless of what object is selected, IfA is object-sensitive,then M-A is no more precise than replacing o:in a context used in the corresponding kobj A for type-dependent clients,as some heap objects that are by the containing type of a representative in o]in M-ktype used in distinguishing different contexts in A are merged by always yields a context abstraction that is either identical or MAHJONG if they are type-consistent.However,this hardly coarser,by the definition of type-sensitivity [39]. 283as context elements are modified accordingly. For an object o that is used in a calling context under A, o is replaced by a representative of [o] ∈ H / ≡ (Section 3.5) under M-A. In other words, if o is merged with some type-consistent objects, then its representative is used, instead. Type-Sensitivity To trade precision for efficiency, k-type￾sensitivity is derived from k-object-sensitivity by replacing every object in a calling context with the class type that contains the corresponding allocation site for the object [39]. If A is a k-type-sensitive analysis obtained from its corre￾sponding k-object-sensitive analysis A′ , then M-A is simply obtained from M-A′ in the same type-sensitive manner. 3.6.2 Soundness and Precision of M-A over A The soundness of M-A is easy to establish. If A is sound, then M-A is sound as the MAHJONG heap abstraction is coarser than the allocation-site abstraction used in A. We discuss some insights below on why merging type￾consistent objects enables M-A to maximally preserve the precision of A for type-dependent clients. This is true for all three types of context-sensitivity as validated later. We first describe a rarely occurring subtle case, the null- field problem, illustrated in Figure 6, due to the imprecision of the pre-analysis, causing precision loss for all the three types of MAHJONG-based context-sensitivity. Example 3.1. Suppose o T i .f and o T j .f both point to o X 1 during the pre-analysis (Figure 6(a)) but o X 1 and null, re￾spectively, in A (Figure 6(b)). In M-A, o T i and o T j are type￾consistent and thus merged into o T k (represented by either o T i or o T j ), M-A is less precise, as o T j .f, which points to null in A, now points to an object of type X (Figure 6(c)). (a) Pre-Analysis (b) (c) null f O T i O X 1 f O T j O X 1 O T k M- f O T i O X 1 f O T j f O X 1 Figure 6. Illustrating the null-field problem. If A is call-site-sensitive, M-A is as precise as A for a type-dependent client if the null-field problem never occurs in a program analyzed by A. Recall that the pre-analysis is no more precise than A. By Definition 2.1, the objects reached from o along the same sequence of field accesses must have exactly the same type when o is modeled both context-sensitively under A and context-insensitively under M-A, resulting in the same precision in both cases. In gen￾eral, M-A is no more precise than A due to the null-field problem but very close to A as the null-fields are rare. If A is object-sensitive, then M-A is no more precise than A for type-dependent clients, as some heap objects that are used in distinguishing different contexts in A are merged by MAHJONG if they are type-consistent. However, this hardly hurts the precision, making M-A nearly as precise as A for type-dependent clients, in practice. The key insight behind object-sensitivity [29] is to distinguish the side-effects of dif￾ferent receiver objects of an instance method foo() by ana￾lyzing it under multiple calling contexts, one per receiver ob￾ject. By merging a set of type-consistent receiver objects for foo(), we end up achieving a significant performance bene- fit at little precision loss by analyzing foo() under the same context by M-A rather than separately but unnecessarily by A for these receiver objects. For type-dependent clients, this represents a generalization of object-sensitivity. If A is type-sensitive, then M-A is nearly as precise as (sometimes slightly better or worse than) A for type￾dependent clients, in practice. Consider an equivalence class [o] = {o1, . . . , on} ∈ H / ≡ (Definition 2.2) formed by the MAHJONG heap abstraction. In A, every oi that is used as a context element in a calling context is replaced by the class type that contains the allocation site for oi . In M-A, o1, . . . , on are merged and replaced by the class type that contains the allocation site for a representative in [o]. Thus, the MAHJONG heap abstraction can be coarser than the allocation-site abstraction for some methods and finer for some others in partitioning their calling contexts, which depends on the representatives chosen. Class T alloc site 1: O1 A // O1 A f O4 X O2 A // O2 A f O5 Y Class U O3 A // O3 A f O6 X ktype: alloc site 2: alloc site 3: M-ktype: Alloc Sites 1 and 2 Abstracted, Resp., as: T and T U and T if O1 A and are merged as O3 A O3 A Figure 7. Precision of M-ktype over ktype. Let us see how the choice of representative for an equiv￾alence class affects the precision of M-ktype. Example 3.2. In Figure 7, ktype (k-type-sensitive analysis) will represent the allocation sites 1 and 2 by T. Thus, the two allocation sites that are distinguished by kobj (k-object￾sensitive analysis) are merged. According to MAHJONG, o A 1 and o A 3 are type-consistent, falling into the same equivalence class. If o A 3 happens to be selected as a representative, then M-ktype will be able to distinguish the allocation sites 1 and 2 by U and T, respectively. However, if o A 1 is selected as the representative (not shown in Figure 7), then M-ktype will merge the allocation sites 1, 2 and 3 by using T as the context, and become less precise than ktype. However, the choice of representative for an equivalence class [o] = {o1, . . . , on} ∈ H / ≡ does not affect the soundness of M-ktype. Regardless of what object is selected, replacing oi in a context used in the corresponding kobj by the containing type of a representative in [o] in M-ktype always yields a context abstraction that is either identical or coarser, by the definition of type-sensitivity [39]. 283