Pointer analysis by type inference for programs with...

Details Pointer analysis by type inference for programs with... Pointer analysis by type inference for programs with...

1996-09-24

2001-03-13

Swann, Todd R. (Department: 2767)

Data processing: software development, installation, and managem

Software program development tool

Translation of code

Reexamination Certificate

active

06202202

ABSTRACT:

This application contains a Microfiche Appendix consisting of 18 frames, 1 sheet.
FIELD OF THE INTENTION
The present invention relates generally to the field of computer program analysis. More particularly, the present invention relates to the field of pointer analysis for computer programs.
BACKGROUND OF THE INVENTION
Software compilers compile source code in a source language into target code in a target language. The target code may be executed directly by a data processing system or linked by a suitable linker with other target code for execution by the data processing system.
To help improve the execution of target code by the data processing system, one typical compiler performs optimization techniques based on the expected run-time usage of memory locations for the compiled program as defined by a store model or storage shape graph. The compiler may generate the store model by performing a pointer analysis to determine the effects of program statements referencing memory locations with constants, variables, or functions, for example.
One typical pointer analysis by type inference treats structured memory objects, such as structures or records, as single memory locations and may therefore generate an overly conservative store model. Another typical pointer analysis by type inference describes structured memory objects and elements of structured memory objects for a program by types based only on the type declarations of the program. Such a pointer analysis, however, produces inaccurate store models for programs using arbitrary type casts, unions, and pointer arithmetic.
SUMMARY OF THE INVENTION
A method performs a pointer analysis for a program with a data processing system. The method may be implemented in software stored by a memory for execution by a data processing system. The method may perform the pointer analysis for a program browser or while compiling the program for execution by a data processing system.
For the method, a store usage in the program accessing locations is identified and may be identified based on a form of a program statement describing the store usage. Locations for the identified store usage are represented with types describing access patterns for the locations for the identified store usage based on how the locations for the identified store usage are accessed in the program such that the types representing the locations for the identified store usage comply with a typing constraint.
Each type may be represented by a type variable and an associated type constructor. A content of one of the locations for the identified store usage may be described with a location type and a function type.
One of the locations for the identified store usage may be represented with a type describing the one location is accessed as a structured memory object if the one location is accessed as a structured memory object for the identified store usage. The one location may also be represented with a type comprising location types describing locations of elements of the structured memory object. Also, one of the locations for the identified store usage may be represented with a type comprising a location type describing a location representing a structured memory object if the one location represents an element of the structured memory object.
One of the locations for the identified store usage may be represented with a type describing the one location is accessed inconsistently if an access pattern of the one location as defined by the identified store usage is different from the access pattern described by the type representing the one location. Also, one of the locations for the identified store usage may be represented with a type describing the one location is accessed inconsistently if the one location is accessed through an offset pointer.
A location pointer may be described with a location type representing a pointed-to location and with an offset describing how the location pointer points to the pointed-to location relative to a beginning of the pointed-to location. One of the locations for the identified store usage may be represented with a type describing a size of the one location based on a size of an assigned value for the identified store usage.
The method may unify types representing values of locations for the identified store usage if the types representing values of locations for the identified store usage are different and if a select one of the types representing values of locations for the identified store usage describes a potential pointer value.
The method may determine whether the types representing the locations for the identified store usage comply with the typing constraint and may determine whether the types representing the locations for the identified store usage comply with a type rule specifying the typing constraint for the identified program statement form. If the types representing the locations for the identified store usage do not comply with the typing constraint, the method modifies types representing locations for the identified store usage to comply with the typing constraint.
The method may identify any potential constraints for types representing locations for the identified store usage and may identify a potential constraint in a pending set. The method may identify from the identified store usage an access pattern relationship for types representing locations for the identified store usage. The method may identify from the identified store usage a pointer offset relationship for types representing locations for the identified store usage. The method may identify from the identified store usage any potential points-to relationships for a type representing a non-pointer value. Types representing locations for any identified potential constraints affected by the modification of types representing locations for the identified store usage may also be modified.
The method may analyze each store usage for the program only one time in an order independent of program control flow.
A data processing system performing the pointer analysis comprises a translator for translating a program in a first language into code in a second language, a pointer analyzer for performing the pointer analysis for the program, a store model for storing the types representing locations for the program, and an optimizer for optimizing the code based on the store model.


REFERENCES:
patent: 5689665 (1997-11-01), Mitsui et al.
patent: 5790866 (1998-08-01), Robison
Aho, et. al., “Compilers, Principles, Techniques, and Tools”, pp. 11 and 22.
Aho et al; Compilers, Principles, Techniques, and Tools; pp. 4-9, 11, 399-400, 473-488 and 527-528, 1986.
Booch et al, “Software Engineering with ADA” pp. 89-132, 1994.
Compleat C, by J.F. Peters and Hamed M. Sallam, pp. 298-309, 1986.
Aho, Alfred V., et al.,Compilers: Principles, Techniques, and Tools,Addison—Wesley Publishing Company, Contents and Chapter 6, pp. vii-x and 343-388 (1986).
Agesen, Ole,Concrete Type Inference: Delivering Object-Oriented Applications,Ph.D. Thesis, Stanford University, Abstract and Table of Contents, pp. i-ii, iv, and vi-viii (Dec. 1995).
Aiken, Alexander, et al., “Better Static Memory Management: Improving Region-Based Analysis of Higher-Order Languages,” SIGPLAN '95 Conference on Programming Language Design and Implementation, La Jolla, California, pp. 174-185 (Jun. 1995).
Birkedal, Lars, et al., “From Region Inference to von Neumann Machines via Region Representation Inference,” Proceedings of the 23rd SIGPLAN-SIGACT Symposium on Principles of Programming Languages, St. Petersburg, Florida, pp. 171-183 (Jan. 1996).
Cousot, Patrick et al., “Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints,” Proceedings of the Fourth Annual ACM Symposium on Principles of Programming Languages, pp. 238-252 (Jan. 1977).
Damas, Luis, et al., “Principal Type-Schemes for Functional Programs,” Conference Record of the Ninth Annual ACM Symposium on Principles of Programming Languages, Albuquerque, New Mexico, pp. 207-212 (Ja

Affiliated with

Also associated with

Rating

Pointer analysis by type inference for programs with... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Pointer analysis by type inference for programs with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pointer analysis by type inference for programs with... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2485135