[talks] 3:00pm Mon Mar 5: Uday Khedker on Heap Reference Analysis

Moses S. Charikar moses at CS.Princeton.EDU
Thu Mar 1 10:45:10 EST 2012


Speaker: Uday Khedker, IIT Bombay
Title:       Heap Reference Analysis Using Access Graphs
Day:       Monday, March 5, 2012
Time:      3:00 pm
Room:    Room 402, CS building

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  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  formulate  the  following  new analyses  for  heap  data: liveness,  availability,  and  anticipability and  propose solution  methods for  them. Together,  they cover  various combinations of directions  of analysis (i.e. forward  and backward) and confluence of information (i.e. union an!
 d interse
ction).

Our analysis can also be used for plugging memory leaks in C/C++ languages.

Reference:
Uday P. Khedker, Amitabha Sanyal, and Amey Karkare. Heap Reference Analysis Using Access Graphs. ACM Transactions on Programming Languages & Systems. 30, 1 (Nov. 2007), 1. DOI=http://doi.acm.org/10.1145/1290520.1290521.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20120301/b0b7c398/attachment.html>


More information about the talks mailing list