BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Interprocedural Data Flow Analysis: Resurrecting the Classical Cal
 l Strings Method - Uday Khedker ( IIT Bombay)
DTSTART:20110517T133000Z
DTEND:20110517T143000Z
UID:TALK31410@talks.cam.ac.uk
CONTACT:Alan Mycroft
DESCRIPTION:Context   sensitive   interprocedural   data  flow   analysis 
   requires\nincorporating the  effect of all  possible calling contexts on
   the data\nflow information  at a program  point. The call strings  appro
 ach\, which\nrepresents context information in the form  of a call string\
 , bounds the\ncontexts by  terminating the call string  construction using
  precomputed\nlength bounds.  These bounds are  large enough  to guarantee
  a  safe and\nprecise solution\, but usually result in  a large number of 
 call strings\,\nthereby rendering the method impractical.\n\nWe propose a 
 simple change in  the classical call strings method. Unlike\nthe tradition
 al approach in which call string construction is orthogonal\nto the comput
 ation of data flow values\, our variant uses the equivalence\nof data  flo
 w values for  termination of call string  construction. This\nallows  us  
 to  discard  call  strings  where  they  are  redundant  and\nregenerate t
 hem when required. For the cyclic call strings\, regeneration\nfacilitates
  iterative computation of data flow values without explicitly\nconstructin
 g most of  the call strings. This reduces the  number of call\nstrings\,  
 and  hence  the  analysis  time\, by  orders  of  magnitude  as\ncorrobora
 ted by our empirical measurements.\n\nOn the theoretical  side\, our metho
 d reduces the worst  case call string\nlength from quadratic in the size  
 of lattice to linear. Further\, unlike\nthe classical method\,  this worst
  case length need not  be reached since\ntermination does not depend on co
 nstructing  all call strings up to this\nlength. Our  approach retains the
  precision\,  generality\, and simplicity\nof the call strings method and 
 simultaneously reduces the complexity and\nincreases  efficiency  signific
 antly  without  imposing  any  additional\nconstraints.\n\nReference: \nUd
 ay P. Khedker and Bageshri Karkare. \n   Efficiency\, Precision\, Simplici
 ty\, and Generality in Interprocedural \n   Data Flow Analysis: Resurrecti
 ng the Classical Call Strings Method. \n   International Conference on Com
 piler \n   Construction (CC 2008)\, Hungary.\n
LOCATION:GS15\, Computer Laboratory
END:VEVENT
END:VCALENDAR