Methods for enhancing flow analysis

Details Methods for enhancing flow analysis Methods for enhancing flow analysis

2000-06-30

2004-11-02

Zhen, Wei (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Testing or debugging

C717S154000

Reexamination Certificate

active

06813761

ABSTRACT:

TECHNICAL FIELD
The technical field relates generally to program analysis. More particularly, it pertains to flow analysis of programs that include function pointers.
COPYRIGHT NOTICE—PERMISSION
A portion of the disclosure of this patent document contains material, which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data.as described below and in the drawings attached hereto: Copyright© 1999, 2000, Microsoft Corporation, All Rights Reserved.
BACKGROUND
A program is a list of statements. This list of statements may be translated, through processes that include compilation, to produce an executable file that can cause a computer to perform a desired action. One type of statement is an assignment statement. An illustrative example of an assignment statement is x=y( ). This statement may be translated to mean that the result of the invocation of the function variable y is assigned to the variable x.
One type of variable is a function pointer. Pointers are often used in programs because they offer flexibility in coding. A function is a group of statements identified by a name that can be invoked within a program by referencing that name. A function pointer contains a location of a function. Thus, a function pointer points to a function. Through a function pointer, a function may be invoked. In the idiom of software analysis, programs that have function pointers are called higher-order programs, and programs that lack function pointers are called first-order programs.
It is beneficial to analyze programs in order to obtain information that may be used to improve them. One type of analysis focuses on the flow of values in a program. Values arise from various computations in a program to obtain a desired result. Because of the presence of functions within a program, values flow in and out of those functions. The type of analysis that analyzes the flow of values in a program to provide an understanding of the behavior of the program is known as flow analysis. Flow analysis is complicated by the presence of function pointers.
Current flow analyses inefficiently deal with the presence of function pointers. One particular technique is described by the following references: See Ramkrisha Chatterjee et al.,
Relevant Context Inference
, Conference Record of the 26
th
Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (January 1999); Donglin Liang and Mary Jean Harrold,
Efficient Points
-
to Analysis for Whole-Program Analysis
, Proceedings of the 7
th
European Software Engineering Conference And the 7
th
ACM SIGSOFT Symposium on the Foundations of Software Engineering (September 1999). Another similar technique is described by the following references: See John Whaley and Martin Rinard,
Compositional Pointer And Escape Analysis for Java Programs
, OOPSLA, pp. 187-206 (1999); Jong-Deok Choi et al.,
Escape Analysis for Java
, OOPSLA, pp. 1-19 (1999). A different technique is described by the following references: See Robert P. Wilson and Monica S. Lam,
Efficient Context
-
Sensitive Pointer Analysis for C Programs
, Proceedings of the 1995 ACM SIGPLAN Conference on Programming Language Design and Implementation (June 1995). Current flow analyses described by the above techniques are either too costly in terms of time or too imprecise in terms of information. Tools that rely on such pointer analyses such as optimizer and debugging tools have been constrained by having to make inferior assumptions about behaviors of programs. As the size of programs has increased with each generation of technology, such inferior assumptions may slow the improvement of programs and lead to the eventual lack of acceptance of such programs in the marketplace.
Thus, what is needed are methods and structures to enhance flow analysis of programs.
SUMMARY
Methods and structures to support enhanced flow analysis are discussed. An illustrative aspect includes a method for enhancing flow analysis. The method includes inferring types for a program, forming a type graph having polarities and indices from the types, and forming a flow graph from the type graph to inhibit imprecise paths so as to enhance context-sensitivity of flow analysis. Another illustrative aspect includes another method for enhancing flow analysis. The method includes forming a type graph that includes polarities and indicies, and forming a flow graph that includes a set of flow paths. The set of flow paths excludes imprecise paths so as to enhance context-sensitivity of flow analysis. Another illustrative aspect includes another method for enhancing flow analysis. The method includes abstracting program expressions into types, and forming a type graph from the types. The type graph includes polarities and indices so as to enhance flow analysis. Another illustrative aspect includes another method for enhancing flow analysis. The method includes annotating each expression in a program by a label, associating the label of an expression with a type of the expression, and tracing at least one path on a type graph having polarities to determine if a value arising at one label in the program flows to another label in the program. Yet another illustrative aspect includes another method for enhancing flow analysis. The method includes forming a type instantiation graph that includes polarities and indices, and computing points-to information for at least one program point by answering reachability queries on the type instantiation graph. The polarities of the type graph as discussed hereinbefore exist on a plurality of instantiation edges of the type graph, in one aspect.
Another illustrative aspect includes a method for inferring types to enhance flow analysis. The method includes generating constraints from a program and solving the constraints to infer at least one type. The act of solving includes propagating polarities so as to enhance flow analysis.
Another illustrative aspect includes a data structure to enhance flow analysis. The data structure includes a data member type to represent a type of a program expression, and a data member flow having a data member polarity and a data member index to represent a flow path between two types.


REFERENCES:
patent: 6014518 (2000-01-01), Steensgaard
patent: 6072950 (2000-06-01), Steensgaard
patent: 6077313 (2000-06-01), Ruf
patent: 6202202 (2001-03-01), Steensgaard
patent: 6327699 (2001-12-01), Larus et al.
patent: 6457023 (2002-09-01), Pinter et al.
patent: 6467075 (2002-10-01), Sato et al.
patent: 6493868 (2002-12-01), DaSilva et al.
patent: 6675379 (2004-01-01), Kolodner et al.
Fahndrich et al. Scalable Context-Sensitive Flow Analysis Using Instantiation Constraints. ACM. 2000. pp. 253-263.*
Callahan. The Program Summary Graph and Flow-Sensitive Interprocedural Data Flow Analysis. ACM. 1988. pp. 47-56.*
Gupta et al. A Framework for Partial Data Flow Analysis. IEEE. 1994. pp. 4-13.*
Yur et al. An Incremental Flow and Context Sentitive Pointer Aliasing Analysis. ACM. 1999. pp. 442-451.*
Chatterjee, R., et al., “Relevant Context Inference”,Conference Record of POPL '99: The 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages,pp. 133-146, (1999).
Choi, J., et al., “Escape Analysis for Java”,OOPSLA,pp. 1-19, 1999.
Donglin, L., et al., “Efficient Points-to Analysis for Whole-Program Analysis”,Proceedings of the 7th European Software Engineering Conference and the 7th ACM SIGSOFT Symposium on the Foundations of Software Engineering,pp. 199-215, (1999).
Steensgaard, B., “Points-to Analysis in Almost Linear Time”,ACM POPL '96, pp. 32-41, (1996).
Whaley, J., et al., “Compositional Pointer and Escape Analysis”,OOPSLA, pp. 187-206, (1999).
Wilson, R.P., et al., “Efficient Context-Sensitive Pointer Analysis for C Programs”,Proceedings of the 1995 ACM SIGPLAN Confere

Affiliated with

Also associated with

Rating

Methods for enhancing flow analysis does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods for enhancing flow analysis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods for enhancing flow analysis will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3340042