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.
