This is the mail archive of the
mailing list for the GCC project.
Re: Fully flow and context sensitive points-to analysis in GCC 4.6.0
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
My apologies for the delay. I wanted to check some details with the
original implementor Prashant who had his exams. Here's my final
- 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,