Computer Science – Programming Languages
Scientific paper
2006-08-28
Computer Science
Programming Languages
Accepted for printing by ACM TOPLAS. This version incorporates referees' comments
Scientific paper
Despite significant progress in the theory and practice of program analysis, analysing properties of heap data has not reached the same level of maturity as the analysis of static and stack data. The spatial and temporal structure of stack and static data is well understood while that of heap data seems arbitrary and is unbounded. We devise bounded representations which summarize properties of the heap data. This summarization is based on the structure of the program which manipulates the heap. The resulting summary representations are certain kinds of graphs called access graphs. The boundedness of these representations and the monotonicity of the operations to manipulate them make it possible to compute them through data flow analysis. An important application which benefits from heap reference analysis is garbage collection, where currently liveness is conservatively approximated by reachability from program variables. As a consequence, current garbage collectors leave a lot of garbage uncollected, a fact which has been confirmed by several empirical studies. We propose the first ever end-to-end static analysis to distinguish live objects from reachable objects. We use this information to make dead objects unreachable by modifying the program. This application is interesting because it requires discovering data flow information representing complex semantics. In particular, we discover four properties of heap data: liveness, aliasing, availability, and anticipability. Together, they cover all combinations of directions of analysis (i.e. forward and backward) and confluence of information (i.e. union and intersection). Our analysis can also be used for plugging memory leaks in C/C++ languages.
Karkare Amey
Khedker Uday
Sanyal Amitabha
No associations
LandOfFree
Heap Reference Analysis Using Access Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Heap Reference Analysis Using Access Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Heap Reference Analysis Using Access Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-106064