Abstract—Points-to analysis is the problem of approximating
run-time values of pointers statically or at compile-time.
Points-to sets are used to store the approximated values of
pointers during points-to analysis. Memory usage and running
time limit the ability of points-to analysis to analyze large
programs.
To our knowledge, works which have implemented a
bit-vector representation of points-to sets so far, allocates bits
for each pointer without considering pointer’s type. By
considering the type, we are able to allocate bits only for a
subset of all abstract objects which are of compatible type with
the pointer’s type and as a consequence improve the memory
usage and running time. To achieve this goal, we number
abstract objects in a way that all the abstract objects of a type
and all of its sub-types are consecutive in order.
Our most efficient implementation uses about 2.5× less
memory than hybrid points-to set (default points-to set in Spark)
and also improves the analysis time for sufficiently large
programs.
Index Terms—Programming languages, points-to analysis,
points-to sets, data structures, bit-vectors, class hierarchy, Java.
Hamid A. Toussi is with the Department of Mathematics and Computer
Science, University of Sistan and Baluchestan, Zahedan, Iran (e-mail:
hamid2c@gmail.com).
Ahmed Khademzadeh was with the Department of Computer Engineering,
Islamic Azad University, Mashhad, Iran. He is now a PhD student and
member of the biocomplex lab at Florida Institute of Technology, Florida,
USA (e-mail: akhademzadeh2011@my.fit.edu).
[PDF]
Cite:Hamid A. Toussi and Ahmed Khademzadeh, "Improving Bit-Vector Representation of Points-To Sets Using Class Hierarchy," International Journal of Computer Theory and Engineering vol. 5, no. 3, pp. 494-499, 2013.
