List of Figures 2 1 Notations...················· 11 2.2 Context-sensitive points-to analysis...···..····.····· 12 3.1 Method contexts for 2-obj and BEAN.................. 21 3.2 Heap contexts for2-obj and BEAN..·......·.....·... 23 3.3 Overview of BEAN...······.················· 25 3.4 The OAGs for the two motivating programs in Figures 3.1 and 3.2. 26 3.5 Notations for object allocation graph.................. 29 3.6 Rules for building the OAG,G=(N,E),for a program based on a 30 3.7 Rules for basic relations in an OAG,G=(N,E).·,···.···· 31 3.8 Rules for context selection in an OAG,G=(N,E).········ 32 3.9 An OAG...······ 33 3.10 Three Cases marked for [Hcrx-DIv]and [Hcrx-Cyc]in Figure 3.8... 35 3.11 A real--world application for using java.util.HaseSet...,···. 44 3.l2 Part of OAG related to HS,/1 and HS/2.....··.·.·..···. 45 4.1 An example program illustrating object merging...·..····.· 53 4.2 Field points-to graph rooted at of and o2............... 55 4.3 Illustrating Condition 2 in Definition 1................. 57 ixList of Figures 2.1 Notations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Context-sensitive points-to analysis. . . . . . . . . . . . . . . . . . . 12 3.1 Method contexts for 2-obj and Bean. . . . . . . . . . . . . . . . . . 21 3.2 Heap contexts for 2-obj and Bean. . . . . . . . . . . . . . . . . . . 23 3.3 Overview of Bean. . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.4 The OAGs for the two motivating programs in Figures 3.1 and 3.2. 26 3.5 Notations for object allocation graph. . . . . . . . . . . . . . . . . . 29 3.6 Rules for building the OAG, G = (N, E), for a program based on a pre-analysis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.7 Rules for basic relations in an OAG, G = (N, E). . . . . . . . . . . 31 3.8 Rules for context selection in an OAG, G = (N, E). . . . . . . . . . 32 3.9 An OAG. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.10 Three Cases marked for [Hctx-Div] and [Hctx-Cyc] in Figure 3.8. . . 35 3.11 A real-world application for using java.util.HaseSet. . . . . . . . 44 3.12 Part of OAG related to HS/1 and HS/2. . . . . . . . . . . . . . . . . 45 4.1 An example program illustrating object merging. . . . . . . . . . . 53 4.2 Field points-to graph rooted at o T 1 and o T 2 . . . . . . . . . . . . . . . 55 4.3 Illustrating Condition 2 in Definition 1. . . . . . . . . . . . . . . . . 57 ix