An Improved Intra-procedural May-alias Analysis Algorithm

摘要: Hind et al.~\cite({Hind99}) use a standard data flow framework \cite{Rosen79, Tarjan81} to formulate an intra-procedural may-alias computation. The aliasing information is computed by applying well-known iterative techniques the Sparse Evaluation Graph (SEG) (\cite{Choi91}). computation requires transfer function for each node that causes potential pointer assignment (relating flowing into and out of node), set aliases holding at entry SEG. analysis assumes precomputed in form summary functions available all function-call sites procedure being analyzed. time complexity algorithm presented al.~(\cite{Hind99}) $O(N^6)$ worst case (where $N$ size SEG). In this paper we present $O(N^3)$ compute same information.