Seminar by Amey Karkare
Heap Reference Analysis
Amey Karkare
Synopsys India Pvt Ltd, Bangalore
Date: Friday, March 12, 2010
Time: 4:00 PM
Venue: CS101.
Abstract:
Despite significant progress in the theory and practice of program analysis, analyzing 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 for properties of heap data by summarizing information using the structure of the program which manipulates the heap. 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).
About The Speaker:
Dr Amey Karkare completed his PhD from IIT Bombay in 2009, and his B.Tech. from IIT Kanpur in 1998. His areas of interest include Program Analysis, Compiler Optimizations, and Functional Programming. He has more than 6 years of industrial experience most of which is in the area of Compiler Optimizations. He is currently working at Synopsys India Pvt Ltd, Bangalore on Symbolic Simulation based Model Generation for Hardware Descriptions in Verilog/VHDL