Re: Fully flow and context sensitive points-to analysis in GCC 4.6.0

[Uday Khedker <uday at cse dot iitb dot ac dot in>]

On Saturday 13 October 2012 02:34 AM, Xinliang David Li wrote:
> Somewhere it is mentioned that heap is handled conservatively. Does
> it mean the algorithm can not disambiguate heap objects all all, or
> it can but does not track pointer values stored in heap objects?
>
> How about field sensitivity? For many programs (mostly C++ ones),
> this is very important.
>
> For CS, virtual calls in C++ will be one of the the biggest
> challenges. How is that dealt with? It can be combined with type
> propagation/analysis.
>
> thanks,
>
> David

My apologies for the delay. I wanted to check some details with the
original implementor Prashant who had his exams. Here's my final
response.

- In our earlier version, we represented heap locations in terms of base
  and offset pairs and all locations allocated at the same pointed were
  treated alike. We used pointer arithmetic to map offset calculation to
  find out which heap locations can possibly coincide. Where we could
  not determine unambiguously, we assumed that the location could
  coincide with any other location.

- For non-heap structures (allocated on stack or static area), our
  analysis is completely field sensitive.

- In our updated implementation, we have removed offsets completely
  for simplicity and made the implementation more conservative. This was
  primarily to simplify the implementation and gain some efficiency.
  But a bigger reason is that we have a much better technique of heap
  analysis in the pipeline. It essentially uses the same abstract idea
  of restricting pointer information to live data but would use heap
  liveness analysis [Khedker-Sanyal-Karkare, TOPLAS 2007]. This analysis
  discovers accesses in deep heap through a data flow analysis that
  represents the this data flow information flow sensitively in the
  form of graphs rooted at stack variables.

- We handle calls through function pointers by adjusting the call graph
  as and when we get pointees of the function pointers. In case of a
  function pointer fptr, we see what fptr may point to, and consider
  all those functions called from that point. We haven't looked at
  GCC's IR for a C++ program with virtual functions. But maybe we can
  store the type of the classes pointed to by an object during the
  pointer analysis to determine the appropriate function that needs
  to be invoked.

Thanks and regards,

Uday.