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

[Uday Khedker]

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.