FENCING AND MARCHING FORESTS ALGORITHMS FOR OBJECT-ORIENTED TYPE ANALYSIS
Original Publication Date: 2002-Oct-12
Included in the Prior Art Database: 2003-Jun-21
Problem The object-oriented type-analysis (OOTA) problem is to determine, under the all-paths-probable assumption, the set of possible types of each variable at every program location. If the problem is constrained to the most interesting programming locations, i.e., virtual call sites, then it is commonly known as the call graph construction (CGC) problem, which is at the core of every OO code analysis. The complexity of a precise OOTA (or CGC) is a result of the recursive nature of its definition—at a virtual call site, the probable paths are dependent on the possible types of the receiver. CGC becomes even more challenging in a setting of partial program analysis. In that situation, every virtual call site has the potential of invoking code on which the analyzer has absolutely no information. The worst-case assumptions that must be made on this code carry adverse effect on the results of the analysis. In the domain of whole program analysis, algorithms are measured by their ability to reduce the number of target implementations of a virtual call. In partial program analysis, the primary challenge is to show that a virtual call site may never lead to an external target. Perhaps the most rudimentary algorithm for OOTA is Class Hierarchy Analysis (CHA), in which the possible types of a variable are the concrete heirs of its static type declaration. There is a minor difficulty in applying CHA to the Java* bytecode language, in which locations in the stack frame have no global static type declaration. As an alternative, CHA uses the base method identification as it appears in the virtual call instruction, in order to determine the possible call targets, which are the set of overriding methods.