void main(String args) any():/Co/1 ICo/1] p1.addEaployee(new Enplo e(O):∥Ep/ (Emp/1 56- obj[/1 pany(): Co/a 1Co/2 Eap/2 Emp/2 9 即1 oyee ep2 comp2.getEaployee(0) 10 class Employee (... 11C1a55C0mpan节 Context-sensitive fields points-to private rrayList emps: (b) graph by 2obj+h new ArrayList():/AL/1 15 emps.add(emp); Co/ JCon1 e) mps-get(i): 18】 Co/1 emps AL/1 elems (Emp/1 19 class ArrayList [ele ICo/21 ICo/2] List(elems nev Obiect[10]:}/Obj/1 Co/2emp elems (AL/1 (Ob0/1 arr Emp/2 23 void add(Object e){elems[size++]-e;} Object get(int i){return elens[i]; (c) Context-sensitive fields points-to (a)Program graph by BEAN Fig.2:Heap contexts for 2o6j+h and BEAN. for a method context and 1 for a heap context in 2obj+h.Therefore,redundant context elements,such as B/1 in [B/1,C/1]in Fig.1(b)and AL/1 in [AL/1]in Fig.2(b),should be avoided since they waste precious space in a context yet contribute nothing in separating the concrete calling contexts for a call site. This paper aims to address this problem in k-obj by excluding redundant elements from its contexts so that their limited context positions can be more profitably exploited to achieve better precision,as shown in Figs.1(c)and 2(c). 3 Methodology We introduce a new approach,BEAN, as illustrated in Fig.3,to improving Pownts-To the precision of a k-object-sensitive Pre-analysis OAG Set Construction pointer analysis,k-obj.The basic idea k-object-sensitive Selected Context is to refine k-obj by avoiding its re- pointer analysis (k-obj) Contexts Selection dundant context elements while main- taining still a k-limiting context ab- straction.An element e in a context Fig.3:Overview of BEAN c for a call or allocation site is redun- dant if c with e removed does not change the context represented by c.For example,B/1 in B/1,C/1]in Fig.1(b)and AL/1 in [AL/1]in Fig.2(b)are re- dundant. BEAN proceeds in two stages.In Stage 1,we aim to identify redundant con- text elements used in k-obj.To do so,we first perform usually a fast but im- precise pre-analysis,e.g.,a context-insensitive Andersen's pointer analysis on a program to obtain its points-to information.Based on the points-to informationObj[]/1 AL/1
Co/1 Co/1 AL/1 emps elems elems Emp/1 1 void main(String[] args) { 2 Company comp1 = new Company(); // Co/1 3 comp1.addEmployee(new Employee()); // Emp/1 4 Employee emp1 = comp1.getEmployee(0); 5 6 Company comp2 = new Company(); // Co/2 7 comp2.addEmployee(new Employee()); // Emp/2 8 Employee emp2 = comp2.getEmployee(0); 9 } 10 class Employee {...} 11 class Company { 12 private ArrayList emps; 13 Company() { emps = new ArrayList(); } // AL/1 14 void addEmployee(Employee emp) { emps.add(emp); } 15 Employee getEmployee(int i) { 16 return (Employee) emps.get(i); 17 } 18 } 19 class ArrayList { 20 private Object[] elems; 21 private int size = 0; 22 ArrayList() { elems = new Object[10]; } // Obj[]/1 23 void add(Object e) { elems[size++] = e; } 24 Object get(int i) { return elems[i]; } 25 }
Co/2 Co/2 AL/1 emps Emp/2 arr arr


Co/1 Co/1 AL/1 emps
Co/2 Co/2 AL/1 emps elems Obj[]/1 elems Obj[]/1 Co/1 Co/2 arr arr Emp/1 Emp/2

(b) Context-sensitive fields points-to graph by 2obj+h (c) Context-sensitive fields points-to (a) Program graph by BEAN Fig. 2: Heap contexts for 2obj+h and Bean. for a method context and 1 for a heap context in 2obj+h. Therefore, redundant context elements, such as B/1 in [B/1,C/1] in Fig. 1(b) and AL/1 in [AL/1] in Fig. 2(b), should be avoided since they waste precious space in a context yet contribute nothing in separating the concrete calling contexts for a call site. This paper aims to address this problem in k-obj by excluding redundant elements from its contexts so that their limited context positions can be more profitably exploited to achieve better precision, as shown in Figs. 1(c) and 2(c). 3 Methodology Points-To OAG Construction Pre-analysis Context Selection Selected Set Contexts k-object-sensitive pointer analysis (k-obj) Fig. 3: Overview of Bean. We introduce a new approach, Bean, as illustrated in Fig. 3, to improving the precision of a k-object-sensitive pointer analysis, k-obj. The basic idea is to refine k-obj by avoiding its re￾dundant context elements while main￾taining still a k-limiting context ab￾straction. An element e in a context c for a call or allocation site is redun￾dant if c with e removed does not change the context represented by c. For example, B/1 in [B/1,C/1] in Fig. 1(b) and AL/1 in [AL/1] in Fig. 2(b) are re￾dundant. Bean proceeds in two stages. In Stage 1, we aim to identify redundant con￾text elements used in k-obj. To do so, we first perform usually a fast but im￾precise pre-analysis, e.g., a context-insensitive Andersen’s pointer analysis on a program to obtain its points-to information. Based on the points-to information