Browse Prior Art Database

FENCING AND MARCHING FORESTS ALGORITHMS FOR OBJECT-ORIENTED TYPE ANALYSIS

IP.com Disclosure Number: IPCOM000015796D
Original Publication Date: 2002-Oct-12
Included in the Prior Art Database: 2003-Jun-21
Document File: 3 page(s) / 49K

Publishing Venue

IBM

Abstract

Problem

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 44% of the total text.

Page 1 of 3

  FENCING AND MARCHING FORESTS ALGORITHMS FOR OBJECT-ORIENTED TYPE ANALYSIS

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.

    CHA is of minimal value in partial program analysis because the whole inheritance hierarchy is not available to the analyzer. Thus, a simple-minded CHA analysis of Java determines that a virtual call has bounded branching only if it refers to a final method, or to a non-final method in a final class.

    RTA [WHAT IS THIS AN ABBREVIATION FOR?] is an improvement over CHA. RTA analyzes the complete program to identify all classes that may be instantiated during the program execution, and then performs CHA, ignoring the concrete heirs, which cannot be instantiated. This effective technique, however, is totally inapplicable in partial analysis problems.

    Sealed calls analysis (SCA, see A. Zaks, V. Feldman and N. Aizikowitz, "Sealed Calls in Java Packages," Proceedings of OOPSLA '00, ACM SIGPLAN Notices, 35(10), October 2000) is the natural extension to CHA in Java, where sealing is used to identify oligomorphic classes, i.e., classes and interfaces all of whose heirs are known. This makes it possible to bound the branching of more call sites.

1

Page 2 of 3

Solution

    We propose two static analysis techniques, Marching Forests and Fencing, which improve upon CHA, are highly scalable...