Contruction of call multigraphs revisited
This paperpresentsan algorithm for constructingcall multigraphsfor procedurallanguageprograms. The call graph construction(CGC) problem is analogousto the problem of performing control flow analysis(CFA) of Scheme[Shi88, Shi91b]. As shownlater, this problemis also analogousto the problemof determiningtypes (TD) at specific programpoints for object-orientedlanguages[PS91, PR93, Suz81]. Our CGC algorithm may be easily adaptedto perform CFA and TD. The algorithm is significantsince the CGC, CFA, and TD problems areof fundamentalimportancefor efficient compilationof programsin procedural,functional,andobject-oriented languages,respectively. Pande& Ryder [PR93] haveshownthat the TD problemis NP-hardin the presenceof single-levelpointers. We showthat the CGC problemis analogousto the TD problem. The CGC problemtoo is, therefore,intractable. Any polynomialalgorithmfor it canonly give approximateresults.The algorithmpresentedmakesthe following contributions: