The Ant and The Grasshopper: Fast and Accurate Pointer Analysis for Millions of Lines of Code Ben Hardekopf and Calvin Lin PLDI 2007 (slides put together by Saheel) Contributions of the Paper Identify current state­of­the­art  Compare 3 well­known algorithms  Fastest takes ½ hour to analyze 1M lines of C Advance the state­of­the­art  Two techniques for inclusion­based analysis  Over 3x faster, same precision Why Pointer Analysis ? Pointer information ­ vital for most program  analyses like program verification and  program understanding.  Precise pointer analysis is NP hard. The most precise analyses are flow sensitive  and context sensitive, but do not scale to large  programs. Example ptr x z y w ptr x z y w x := &z ptr := @x Andersen’s algorithm y := @w ptr := @y ptr x,y z,w Flow-sensitive algorithm Steensgard’s algorithm Dataflow Equations – Flow-Sensitive G G x := &y x := *y G’ = G with pt’(x)  {y} G’ = G with pt’(x)  U pt(a) for all a in pt(y) G G x := y *x := y G’ = G with pt’(x)  pt(y) G’ = G with pt’(a) U pt(y) for all a in pt(x) weak update strong updates Dataflow Equations – Flow-Insensitive Statements weak updates only G G x := &y x := *y G = G with pt(x) U {y} G = G with pt(x) U pt(a) for all a in pt(y) G G x := y *x := y G = G with pt(x) U pt(y) G = G with pt(a) U pt(y) for all a in pt(x) Strong v/s Weak updates Suppose S and S1 are set­valued variables. S ← S1: strong update = set assignment ● S U← S1: weak update = set union ● this is like S ← S U S1 ● Set Constraints Statements Simple Base x := &y x := *y Complex1 Complex2 x := y *x := y Background: Anderson's algorithm • Generate constraints from the code • Build a constraint graph • Nodes: variables • Edges: inclusion constraints • Add indirect constraints  • Pointer dereference • Recursively compute transitive closure of the graph Background: Inclusion-based Analysis c = &f; e = &c; g = &a; a = d; b = a; d = *e; *e = b; *g = e;