CALL GRAPH CONSTRUCTION IN OBJECT-ORIENTED LANGUAGES

Interprocedural analyses enable optimizing compilers to more precisely model the effects of non-inlined procedure calls, potentially resulti ng in substantial increases in application performance. Applying inter procedural analysis to programs written in object-oriented or function al languages is complicated by the difficulty of constructing an accur ate program call graph. This paper presents a parameterized algorithmi c framework for call graph construction in the presence of message sen ds and/or first-class functions. We use this framework to describe and to implement a number of well-known and new algorithms. We then empir ically assess these algorithms by applying them to a suite of medium-s ized programs written in Cecil and Java, reporting on the relative cos t of the analyses, the relative precision of the constructed call grap hs, and the impact of this precision on the effectiveness of a number of interprocedural optimizations.