Hybrid design between Fast points-to analysis and Context Sensitive points-to analysis" , R&D for McCAT Compiler, McGill University, Montreal,Canada,12/97.
This paper reports on the design, partial implementation and expected results of the hybrid approach between FP (fast points-to) analysis and CSP (context-sensitive points-to) analysis models to collect alias information.
FP computes a class equivalence memory model that estimates the possible targets of pointers at compile time, in almost linear time in the size of the call graph.
CSP, on the other hand, gathers approximate points-to relationships between pairs of stack locations over all contexts of the invocation graph. CSP may in the worst case run in exponential time in the size of the call graph.
The new hybrid approach reuses FP knowledge of points-to information to initialize the CSP initial estimate of the alias output information for recursive functions, and has the potential to reduce the number of iterations these functions are processed. This strategy results in a faster CSP algorithm that collects accurate points-to information with initial knowledge gathered by the FP analysis on recursive functions. Other attempts presented in this paper, tried to combine the FP and CSP models and resulted in a hybrid approach in which FP classifies functions as Selected or Excluded depending on their ability to modify or leave intact the alias information. .