Pointer analysis by type inference combined with a non-pointer a

Details Pointer analysis by type inference combined with a non-pointer a Pointer analysis by type inference combined with a non-pointer a

1996-06-18

2000-06-06

Hafiz, Tariq R.

395705, G06F 944

Patent

active

060729503

ABSTRACT:
A pointer analysis by type inference combined with a non-pointer analysis helps approximate run-time store usage for a computer program. The analysis initially describes the content of each location for the program with a separate type as a non-pointer value. The analysis identifies store relationships described by the program and determines whether the location(s) and/or function(s) affected by the identified store relationships are well-typed under typing constraints. For well-typed store relationships, the analysis identifies any potential points-to relationships for types representing non-pointer values in case the analysis subsequently determines in processing other store relationships that the types may represent a pointer value. If the identified store relationships are not well-typed, the analysis modifies types for location(s) and/or function(s) affected by the identified store relationships as necessary so the store relationships are well-typed. The analysis also modifies types for locations and/or functions for potential points-to relationships affected by the modification of types When the locations and/or functions for all identified store relationships are well-typed, the program is well-typed with the set of types defining a store model for the program.

REFERENCES:
patent: 5361351 (1994-11-01), Lenkov et al.
patent: 5488727 (1996-01-01), Agrawal et al.
patent: 5689665 (1997-11-01), Mitsui et al.
patent: 5748966 (1998-05-01), Sato
patent: 5790866 (1998-08-01), Robison
Aho, Alfred V., et al., Compilers: Principles, Techniques, and Tools, Addison-Wesley Publishing Company, pp. 11 and 22 (1986).
Aiken, Alexander, et al., "Static Type Inference in a Dynamically Typed Language," ACM, pp. 279-290 (1990).
Flannery, Kevin E., et al., "Conjunctive Polymorphic Type Checking On a Language of Combinators," Proceedings -1990 Southeastcon, Session 3D1, IEEE, pp. 183-187 (1990).
Giannini, Paola, et al., "Characterization of Typings in Polymorphic Type Discipline," IEEE, pp. 61-70 (1988).
Kfoury, A.J., et al., "On the Computational Power of Universally Polymorphic Recursion," IEEE, pp. 72-81 (1988).
Leroy, Xavier, "Unboxed Objects and Polymorphic Typing," ACM, pp. 177-188 (1992).
Pierce, Benjamin, et al., "Typing and Subtyping for Mobile Processes," Proceedings of the Eighth Annual Symposium on LICS, pp. 376-385 (1993).
Piperno, Adolfo, et al., "Type Inference and Extensionality," Proceedings of the Symposium on LICS, pp. 196-205 (1994).
Steensgaard, Bjarne, "Points-to Analysis in Almost Linear Time," Technical Report MSR-TR-95-08, Microsoft Research, Redmond, WA, pp. 1-12. Mar. 1995.
Steensgaard, Bjarne, "Points-to Analysis in Almost Linear Time," Proceedings of the 23rd SIGPLAN/SIGACT Symposium on Principles of Programming Languages, St. Petersburg, FL, pp. 32-41. Jan. 24, 1996.
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 Language, 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 (Jan. 1982).
Heintz, Nevin, Set Based Program Analysis, Ph.D. Thesis, Carnegie Mellon University, Abstract, Contents, and Chapter 1, pp. i-iv and 1-6 (1992).
Henglein, Fritz, "Type Inference with Polymorphic Recursion," ACM Transactions on Programming Languages and Systems, Vol. 15, No. 2, pp. 253-289 (Apr. 1993).
Mairson, Harry G., "Deciding ML Typability is Complete for Deterministic Exponential Time," Proceedings of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, pp. 382-401 (Jan. 1990).
Mycroft, Alan, "Polymorphi Type Schemes and Recursive Definitions," Lecture Notes in Computer Science, Vol. 167, Proceedings of the International Symposium on Programming, 6th Colloquium, Toulouse, pp. 217-228 (Apr. 17-19, 1984).
Talpin, Jean-Pierre, et al., Syntactic Control of Type Polymorphism for Recursive Function Definitions, Technical Report ECRC-94-29, European Computer-Industry Research Centre GmbH, pp. I-III, 1-15, and i-xiv (Jul. 1994, Revised Feb. 1995).
Talpin, Jean-Pierre, et al., "Syntactic Type Polymorphism for Recursive Function Definitions," Workshop on Types for Program Analysis, pp. 80-94 (May 26-27, 1995).
Andersen, Lars Ole, Program Analysis and Specialization for the C Programming Language, Ph.D. Thesis, DIKU, University of Copenhagen, Denmark (May 1994).
Austin, Todd M., et al., "Efficient Detection of All Pointer and Array Access Errors," SIGPLAN '94 Conference on Programming Language Design and Implementation, Orlando, Florida, pp. 290-301 (Jun. 1994).
Burke, Michael, et al., "Flow-Insensitive Interprocedural Alias Analysis in the Presence of Pointers", Research Report RC 19546, IBM T.J. Watson Research Center, Yorktown Heights, New York, pp. 1-21 (Sep. 1994).
Chase, David R., et al., "Analysis of Pointers and Structures," Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, White Plains, New York, pp. 296-310 (Jun. 20-22, 1990).
Choi, Jong-Deok, et al., "Efficient Flow-Sensitive Interprocedural Computation of Pointer-Induced Aliases and Side Effects," Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Language, Charleston, South Carolina, pp. 232-245 (Jan. 10-13, 1993).
Choi, Jong-Deok, et al., "On the Efficient Engineering of Ambitious Program Analysis," IEEE Transactions on Software Engineering, Vol. 20, No. 2, pp. 105-114 (Feb. 1994).
Cytron Ron, et al., "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph," ACM Transactions on Programming Languages and Systems, Vol. 13, No. 4, pp. 451-490 (Oct. 1991).
Deutsch, Alain, "A Storeless Model of Aliasing and its Abstractions using Finite Representations of Right-Regular Equivalence Relations," Proceedings of the IEEE 1992 International Conference on Computer Languages, Oakland, California, pp. 2-13 (Apr. 1992).
Deutsch, Alain, "Interprocedural May-Alias Analysis for Pointers: Beyond k-limiting," SIGPLAN '94 Conference on Programming Language Design and Implementation, Orlando, Florida, pp. 230-241 (Jun. 1994).
Emami, Maryam, et al., "Context-Sensitive Interprocedural Points-to Analysis in the Presence of Function Pointers," ACAPS Technical Memo 54, Advanced Compilers, Architectures and Parallel Systems Group, School of Computer Science, McGill University, Montreal, Canada, pp. 1-28 (Nov. 12, 1993).
Henglein, Fritz, "Efficient Type Inference for Higher-Order Binding-Time Analysis," Functional Programming Languages and Computer Architecture, 5th ACM Conference, Cambridge, Massachusetts, pp. 448-472 (Aug. 26-30, 1991).
Kahn, G., "Natural Semantics," Lecture Notes in Computer Science, vol. 247, STACS 87 4th Annual Symposium on Theoretical Aspects of Computer Science, Passau, Federal Republic of Germany, pp. 22-39 (Feb. 19-21, 1987).
Landi, William, et al., "A Safe Approximate Algorithm for Interprocedural Pointer Aliasing, " Proceeding of the SIGPLAN '92 Conference on Programming Language Design and Implementation, pp. 235-248 (Jun. 1992).
Land

Affiliated with

Also associated with

Rating

Pointer analysis by type inference combined with a non-pointer a 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 combined with a non-pointer a, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pointer analysis by type inference combined with a non-pointer a will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2221744