Pointer analysis by type inference for programs with structured memory objects and potentially inconsistent memory object accesses

• US 6,202,202 B1
• Filed: 09/24/1996
• Issued: 03/13/2001
• Est. Priority Date: 09/24/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Steensgaard, Bjarne
• Primary Examiner(s): Swann, Todd R.
• Assistant Examiner(s): Smithers, Matthew
• Application Number:
  US08/719,144
• Time in Patent Office: 1,631 Days
• Field of Search: 395/705, 395/707, 395/708, 395/836, 711/100, 711/111, 711/117, 717/8
• US Class Current: 717/127
• CPC Class Codes: G06F 8/437 Type checking

Abstract

A pointer analysis by type inference for a computer program ith structured memory objects and potentially inconsistent memory object accesses helps approximate run-time store usage for the program. The analysis represents locations for the program with types describing access patterns for the represented locations based on how the locations are accessed in the program. The analysis describes access patterns for structured memory objects, elements of structured memory objects, and memory objects accessed in inconsistent manners in the program. The analysis identifies store usages described by the program and determines whether the location(s) and/or function(s) affected by the identified store usages are well-typed under typing constraints. If the identified store usages are not well-typed, the analysis modifies types for location(s) and/or function(s) affected by the identified store usages as necessary so the store usages are well-typed. When the locations and/or functions for all identified store usages are well-typed, the program is well-typed with the set of types defining a store model for the program.

Claims

1. A method for performing a pointer analysis for a program with a data processing system, the method comprising the steps of:

(a) identifying in the program one or more store usages accessing locations; and

(b) generating a store model to approximate run-time store usage for the program, the store model comprising types having components representing locations for the identified store usage(s) such that the types describe access patterns for the locations for the identified store usage(s) based on how the identified store usage(s) access the locations and such that the types representing the locations for the identified store usage(s) comply with a typing constraint.

2. The method of claim 1, wherein the generating step (b) comprises the step of representing one location with a type describing the one location is accessed as a structured memory object.

3. The method of claim 2, wherein the generating step (b) comprises the step of representing the one location with a type comprising location types describing locations of elements of the structured memory object.

4. The method of claim 1, wherein the generating step (b) comprises the step of representing a location representing an element of a structured memory object with a type comprising a location type describing a location representing the structured memory object.

5. The method of claim 1, wherein the generating step (b) comprises the step of representing one location with a type describing the one location is accessed inconsistently if identified store usages define different access patterns for the one location.

6. The method of claim 1, wherein the generating step (b) comprises the step of representing one location with a type describing the one location is accessed inconsistently if an identified store usage accesses the one location through an offset pointer.

7. The method of claim 1, wherein the generating step (b) comprises the step of describing a location pointer for an identified store usage 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.

8. The method of claim 1, wherein the generating step (b) comprises the step of representing one location with a type describing a size of the one location.

9. The method of claim 1, wherein the generating step (b) comprises the step of describing a content of one location with a location type and a function type.

10. The method of claim 1, wherein each type is represented by a type variable and an associated type constructor.

11. The method of claim 1, wherein the generating step (b) comprises the step of unifying different types representing values of locations if a select one of the different types describes a potential pointer value.

12. The method of claim 1, wherein the method performs the pointer analysis while compiling the program for execution by a data processing system.

13. The method of claim 1, wherein the method performs the pointer analysis for a program browser.

14. The method of claim 1, wherein the generating step (b) comprises the steps of:

i) determining whether the types representing the locations for one identified store usage comply with the typing constraint, and

ii) if the types representing the locations for the one identified store usage do not comply with the typing constraint, modifying types representing locations for the one identified store usage to comply with the typing constraint.

15. The method of claim 14, wherein the identifying step (a) comprises the step of identifying a form of a program statement describing the one identified store usage, and wherein the determining step (b)(i) comprises the step of determining whether the types representing the locations for the one identified store usage comply with a type rule specifying the typing constraint for the identified program statement form.

16. A method for performing a pointer analysis for a program with a data processing system, the method comprising the steps of:

identifying in the program a store usage accessing locations;

determining whether types representing the locations for the identified store usage comply with a typing constraint;

identifying any potential constraints for types representing locations for the identified store usage;

if the types representing the locations for the identified store usage do not comply with the typing constraint, modifying types representing locations for the identified store usage to comply with the typing constraint,

wherein the modifying step (d) comprises the step of representing locations for the identified store usage with a hierarchy of types describing access patterns for the locations for the identified store usage based on how the identified store usage accesses the locations; and

modifying types representing locations for any identified potential constraints affected by the modifying step (d).

17. The method of claim 16, wherein the modifying step (d) comprises the step of representing one of the locations for the identified store usage with a type describing the one location is accessed as a structured memory object.

18. The method of claim 16, wherein the modifying step (d) comprises the step of representing one of the locations for the identified store usage with a type describing the one location is accessed inconsistently if the identified store usage and another store usage in the program define different access patterns for the one location.

19. The method of claim 16, wherein the modifying step (d) comprises the step of representing one of the locations for the identified store usage with a type describing the one location is accessed inconsistently if the identified store usage accesses the one location through an offset pointer.

20. The method of claim 16, wherein the modifying step (d) comprises the step of describing a location pointer for the identified store usage 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.

21. The method of claim 16, wherein the modifying step (d) comprises the step of representing one of the locations for the identified store usage with a type describing a size of the one location.

22. The method of claim 16, wherein one of the types comprises a location type and a function type, each describing a content of a location represented by the one type.

23. The method of claim 16, wherein each type is represented by a type variable and an associated type constructor.

24. The method of claim 16, wherein the identifying step (c) identifies a potential constraint in a pending set.

25. The method of claim 16, wherein the identifying step (c) comprises the step of identifying from the identified store usage an access pattern relationship for types representing locations for the identified store usage.

26. The method of claim 16, wherein the identifying step (c) comprises the step of identifying from the identified store usage a pointer offset relationship for types representing locations for the identified store usage.

27. The method of claim 16, wherein the identifying step (c) comprises the step of identifying from the identified store usage any potential points-to relationships for a type representing a non-pointer value.

28. The method of claim 16, wherein the program describes a plurality of store usages and wherein the method analyzes each described store usage only one time in an order independent of program control flow.

29. The method of claim 16, wherein the identifying step (a) comprises the step of identifying a form of a program statement describing the store usage, and

wherein the determining step (b) comprises the step of determining 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.

30. The method of claim 16, wherein the method performs the pointer analysis while compiling the program for execution by a data processing system.

31. The method of claim 16, wherein the method performs the pointer analysis for a program browser.

32. A memory for storing software for execution by a data processing system to perform a pointer analysis for a program, the memory comprising:

program code stored by the memory for identifying a store usage in the program accessing locations; and

program code stored by the memory for representing locations for the identified store usage with types having components 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.

33. The computer-readable medium of claim 32, wherein the program code (b) comprises program code for representing one of the locations for the identified store usage with a type describing the one location is accessed as a structured memory object.

34. The computer-readable medium of claim 33, wherein the program code (b) comprises program code for representing the one location with a type comprising location types describing locations of elements of the structured memory object.

35. The computer-readable medium of claim 32, wherein the program code (b) comprises program code for representing a location representing an element of a structured memory object with a type comprising a location type describing a location representing the structured memory object.

36. The computer-readable medium of claim 32, wherein the program code (b) comprises program code for representing one of the locations for the identified store usage with a type describing the one location is accessed inconsistently if the identified store usage and another store usage in the progam define different access patterns for the one location.

37. The computer-readable medium of claim 32, wherein the program code (b) comprises program code for representing one of the locations for the identified store usage with a type describing the one location is accessed inconsistently if the identified store usage accesses the one location through an offset pointer.

38. The computer-readable medium of claim 32, wherein the program code (b) comprises program code for describing a location pointer for the identified store usage 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.

39. The computer-readable medium of claim 32, wherein the program code (b) comprises program code for representing one of the locations for the identified store usage with a type describing a size of the one location.

40. The computer-readable medium of claim 32, wherein the program code (b) comprises program code for describing a content of one of the locations for the identified store usage with a location type and a function type.

41. The computer-readable medium of claim 32, comprising program code for representing each type by a type variable and an associated type constructor.

42. The computer-readable medium of claim 32, wherein the program code (b) comprises program code for unifying different types representing values of locations for the identified store usage if a select one of the different types describes a potential pointer value.

43. The computer-readable medium of claim 32, comprising program code for compiling the program for execution by a data processing system.

44. The computer-readable medium of claim 32, comprising program code for a program browser.

45. The computer-readable medium of claim 32, wherein the program code (b) comprises:

i) program code for determining whether the types representing the locations for the identified store usage comply with the typing constraint, and

ii) program code for modifying types representing locations for the identified store usage to comply with the typing constraint if the types representing the locations for the identified store usage do not comply with the typing constraint.

46. The computer-readable medium of claim 45, wherein the program code (a) comprises program code for identifying a form of a program statement describing the store usage, and

wherein the program code (b)(i) comprises program code for determining 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.

47. The computer-readable medium of claim 32, wherein the program code (b) comprises:

i) program code for determining whether the types representing the locations for the identified store usage comply with the typing constraint,

ii) program code for identifying any potential constraints for types representing locations for the identified store usage,

iii) program code for modifying types representing locations for the identified store usage to comply with the typing constraint if the types representing the locations for the identified store usage do not comply with the typing constraint, and

iv) program code for modifying types representing locations for any identified potential constraints affected by the modification of types representing locations for the identified store usage.

48. The computer-readable medium of claim 47, wherein the program code (b)(ii) comprises program code for identifying a potential constraint in a pending set.

49. The computer-readable medium of claim 47, wherein the program code (b)(ii) comprises program code for identifying from the identified store usage an access pattern relationship for types representing locations for the identified store usage.

50. The computer-readable medium of claim 47, wherein the program code (b)(ii) comprises program code for identifying from the identified store usage a pointer offset relationship for types representing locations for the identified store usage.

51. The computer-readable medium of claim 47, wherein the program code (b)(ii) comprises program code for identifying from the identified store usage any potential points-to relationships for a type representing a non-pointer value.

52. The computer-readable medium of claim 47, wherein the program describes a plurality of store usages and wherein the program code of the computer-readable medium, when executed by a data processing system, analyzes each described store usage only one time in an order independent of program control flow.

53. A data processing system comprising:

a) a translator for translating a program in a first language into code in a second language;

b) a pointer analyzer for performing a pointer analysis for the program, the pointer analyzer for identifying in the program a store usage accessing locations and for representing locations for the identified store usage with a set of hierarchical types describing different access patterns for the locations for the identified store usage based on how the identified store usage accesses the locations such that the types representing the locations for the identified store usage comply with a typing constraint;

c) a store model for storing the types representing locations for the program; and

d) an optimizer for optimizing the code based on the store model.

54. The data processing system of claim 53, comprising a symbol table for identifying locations for the program.

55. The data processing system of claim 53, wherein the pointer analyzer represents one of the locations for the identified store usage with a type describing the one location is accessed as a structured memory object.

56. The data processing system of claim 53, wherein the pointer analyzer represents one of the locations for the identified store usage with a type describing the one location is accessed inconsistently if the identified store usage and another store usage in the program define different access patterns for the one location.

57. The data processing system of claim 53, wherein the pointer analyzer represents one of the locations for the identified store usage with a type describing the one location is accessed inconsistently if the identified store usage accesses the one location through an offset pointer.

58. The data processing system of claim 53, wherein the pointer analyzer describes a location pointer for the identified store usage 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.

59. The data processing system of claim 53, wherein the pointer analyzer represents one of the locations for the identified store usage with a type describing a size of the one location.

60. The data processing system of claim 53, wherein the pointer analyzer describes a content of one of the locations for the identified store usage with a location type and a function type.

61. The data processing system of claim 53, wherein each type is represented by a type variable and an associated type constructor.

62. The data processing system of claim 53, wherein the pointer analyzer determines whether the types representing the locations for the identified store usage comply with the typing constraint and modifies types representing locations for the identified store usage to comply with the typing constraint if the types representing the locations for the identified store usage do not comply with the typing constraint.

63. A method for performing a pointer analysis for a program with a data processing system, the method comprising:

(a) identifying in the program one or more store usages accessing locations; and

(b) generating a store model to approximate run-time store usage for the program, the store model comprising types representing locations for the identified store usage(s) such that the types describe access patterns for the locations for the identified store usage(s) based on how the identified store usage(s) access the locations wherein the types are comprised of components defining such access patterns.

64. The method of claim 63 wherein the types comprise a hierarchy of types.

65. The method of claim 64 wherein types ma y be p romot ed to ty pes higher in the hierarchy based on constraints.

66. The method of claim 64 wherein one type describes locations whose content values are used only as a unit, and a fuirther type describes locations whose content values are used only as structured objects.

67. The method of claim 64 whe rein one type describes locations whose content values are used in inconsistent manners by use of components comprising a size, a parent type, a location pointer type, and a function type.

68. The method of claim 63 wherein access patterns for various types are described by components selected from the group consisting of size, parent type, location pointer type, function type, element mapping type, and an offset type.

69. A method for identifying utilization of computer storage by a computer program, the method comprising:

identifying portions of the program that utilize storage; and

generating a store model by identifyWing each portion as a type from a hierarchy of types, each type identifying different access patterns based on how storage is accessed.

70. The method of claim 69 wherein the types comprise components selected from multiple components describing different access patterns.

71. A computer readable medium having instructions stored thereon for causing a computer to execute a method for performing a pointer analysis for a program with a data processing system, the method comprising:

(a) identifying in the program one or more store usages accessing locations; and

(b) generating a store model to approximate run-time store usage for the program, the store model comprising types representing locations for the identified store usage(s) such that the types describe access patterns for the locations for the identified store usage(s) based on how the identified store usage(s) access the locations wherein the types are comprised of components defining such access patterns.