Chapter 1.Introduction 3 parameter,k [71,53,55,75].As a result,if the length of the contexts is no larger than k,the contexts can be distinguished;otherwise,the contexts ending with the same k suffixes cannot be further distinguished and the points-to information un- der these contexts would be merged.Given a larger k-limiting,the analysis can partition the context space with finer grain and achieve better precision,but it may also cause the analysis to dramatically slow down or even become unscalable. Heap abstraction [32],which partitions the infinitely-sized heap into a finite number of(abstract)objects,is particularly important to the analysis for object- oriented languages such as Java.Generally,heap abstractions for points-to anal- ysis for Java may use one abstract object per class (allocation-type heap abstrac- tion)[99],or one abstract object per allocation site (allocation-site heap abstrac- tion)[38],which can be further separated context-sensitively in an orthogonal man- ner [53,75,34].Points-to analyses with different heap abstractions may exhibit significant differences in precision and efficiency [99,75,32].Allocation-site heap abstraction,as a finer abstraction,makes points-to analysis usually notably more precise than the ones using allocation-type heap abstraction.However,allocation- site-based points-to analysis usually runs significantly slower and its performance will dramatically become worse if context-sensitivity is applied to further distin- guish different heap objects for better precision. 1.2 Contributions In this thesis,we present a new context-sensitivity approach called BEAN [95]and a new heap abstraction approach called MAHJONG [96],to improve the precision and efficiency of points-to analysis respectively.Specifically,this thesis makes the following contributions.Chapter 1. Introduction 3 parameter, k [71, 53, 55, 75]. As a result, if the length of the contexts is no larger than k, the contexts can be distinguished; otherwise, the contexts ending with the same k suffixes cannot be further distinguished and the points-to information un￾der these contexts would be merged. Given a larger k-limiting, the analysis can partition the context space with finer grain and achieve better precision, but it may also cause the analysis to dramatically slow down or even become unscalable. Heap abstraction [32], which partitions the infinitely-sized heap into a finite number of (abstract) objects, is particularly important to the analysis for object￾oriented languages such as Java. Generally, heap abstractions for points-to anal￾ysis for Java may use one abstract object per class (allocation-type heap abstrac￾tion) [99], or one abstract object per allocation site (allocation-site heap abstrac￾tion) [38], which can be further separated context-sensitively in an orthogonal man￾ner [53, 75, 34]. Points-to analyses with different heap abstractions may exhibit significant differences in precision and efficiency [99, 75, 32]. Allocation-site heap abstraction, as a finer abstraction, makes points-to analysis usually notably more precise than the ones using allocation-type heap abstraction. However, allocation￾site-based points-to analysis usually runs significantly slower and its performance will dramatically become worse if context-sensitivity is applied to further distin￾guish different heap objects for better precision. 1.2 Contributions In this thesis, we present a new context-sensitivity approach called Bean [95] and a new heap abstraction approach called Mahjong [96], to improve the precision and efficiency of points-to analysis respectively. Specifically, this thesis makes the following contributions