1 void main(Object[]args){ 23 A al nev A()/A/1 A/1 A/1,B1] Object v1 a1.foo(nev Object());/0/1 A.foo0 B.bar( 4 B/1,C11 A a2 ney A(:/A/2 main0 A/2] 1A2,B/1 C.identity( Object v2 a2.foo(nev Object());/0/2 7) Afoo0 B.bar() 8 class A Object foo(Object v） Bb B() /B/1 (b)Context-sensitive call graph by 2obj+h return b.bar(v）; 131 14 class B AM] A/1,B/1 A/1,C/1 Object bar(Object v){ cc nev C();/C/1 A.foo() B.bar0 Cidentity0 17 return c.identity(v); 1 A/2 A2,B1] A2,C/1 191 20 class C{ A.foo() B.bar0 C.identity 21 Object identity(Object v)return v;} 22 (a)Program (c)Context-sensitive call graph by BEAN Fig.1:Method contexts for 2objth and BEAN. 2.2 Redundant Elements in Heap Contexts We now use an example in Fig.2 to illustrate how 2obj+h analyses it imprecisely due to its use of a redundant element in heap contexts and how BEAN avoids the imprecision by avoiding this redundancy.Our may-alias client now issues an alias query for variables emp1 and emp2.In Fig.2(a),we identify again its six allocation sites by their labels given at their end-of-line comments(in green). Fig.2(b)shows the context-sensitive field points-to graph computed by 2obj+h, where each node represents an abstract heap object created under the corre- sponding context,denoted [...],(in red),and each edge represents a field points- to relation with the corresponding field name being labeled on the edge.An array object is analysed with its elements collapsed to one pseudo-field,denoted arr Hence,x[i]=y (y x[i])is handled as x.arr y (y x.arr). In this example,two companies,Co/1 and Co/2,maintain their employee information by using two different ArrayLists,with each implemented internally by a distinct array of type Object [at line 22.However,2obj+h has modelled the two array objects imprecisely by using one abstract object Obj[]/1 under [AL/1].Note that AL/1 is redundant since adding it to [makes no difference to the handling of Obj[]/1.As a result,emp1 and emp2 will both point to Emp/1 and Emp/2,causing may-alias to regard both as aliases conservatively. Fig.2(c)shows the context-sensitive field points-to graph computed by BEAN. This time,the Object [arrays used by two companies Co/1 and Co/2 are dis- tinguished under two distinct heap contexts Co/1 and Co/2.As a result,our may-alias client will no longer report emp1 and emp2 to be aliases. 2.3 Discussion As illustrated above,k-obj selects blindly a sequence of k-most-recent allocation sites as a context.To analyse large-scale software scalably,k is small,which is 2A/1 main() A.foo() A.foo() B.bar() B.bar() C.identity()
A/2 A/1, B/1 A/2, B/1 B/1, C/1 A/1 main() A.foo() A.foo() B.bar() B.bar() A/2 A/1, B/1 A/2, B/1 C.identity() A/1, C/1 C.identity() A/2, C/1 (a) (b) (c) Context-sensitive call graph by 2obj+h Program Context-sensitive call graph by BEAN 1 void main(Object[] args) { 2 A a1 = new A(); // A/1 3 Object v1 = a1.foo(new Object()); // O/1 4 5 A a2 = new A(); // A/2 6 Object v2 = a2.foo(new Object()); // O/2 7 } 8 class A { 9 Object foo(Object v) { 10 Bb= new B(); // B/1 11 return b.bar(v); 12 } 13 } 14 class B { 15 Object bar(Object v) { 16 Cc= new C(); // C/1 17 return c.identity(v); 18 } 19 } 20 class C { 21 Object identity(Object v) { return v; } 22 } Fig. 1: Method contexts for 2obj+h and Bean. 2.2 Redundant Elements in Heap Contexts We now use an example in Fig. 2 to illustrate how 2obj+h analyses it imprecisely due to its use of a redundant element in heap contexts and how Bean avoids the imprecision by avoiding this redundancy. Our may-alias client now issues an alias query for variables emp1 and emp2. In Fig. 2(a), we identify again its six allocation sites by their labels given at their end-of-line comments (in green). Fig. 2(b) shows the context-sensitive field points-to graph computed by 2obj+h, where each node represents an abstract heap object created under the corre￾sponding context, denoted [...], (in red), and each edge represents a field points￾to relation with the corresponding field name being labeled on the edge. An array object is analysed with its elements collapsed to one pseudo-field, denoted arr. Hence, x[i] = y (y = x[i]) is handled as x.arr = y (y = x.arr). In this example, two companies, Co/1 and Co/2, maintain their employee information by using two different ArrayLists, with each implemented internally by a distinct array of type Object[] at line 22. However, 2obj+h has modelled the two array objects imprecisely by using one abstract object Obj[]/1 under [AL/1]. Note that AL/1 is redundant since adding it to [ ] makes no difference to the handling of Obj[]/1. As a result, emp1 and emp2 will both point to Emp/1 and Emp/2, causing may-alias to regard both as aliases conservatively. Fig. 2(c) shows the context-sensitive field points-to graph computed by Bean. This time, the Object[] arrays used by two companies Co/1 and Co/2 are dis￾tinguished under two distinct heap contexts [Co/1] and [Co/2]. As a result, our may-alias client will no longer report emp1 and emp2 to be aliases. 2.3 Discussion As illustrated above, k-obj selects blindly a sequence of k-most-recent allocation sites as a context. To analyse large-scale software scalably, k is small, which is 2