Method for directly inlining virtual calls without on-stack replacement

• US 6,223,340 B1
• Filed: 10/09/1998
• Issued: 04/24/2001
• Est. Priority Date: 10/09/1998
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Detlefs, David L.
• Primary Examiner(s): Powell, Mark R.
• Assistant Examiner(s): DAS, CHAMELI
• Application Number:
  US09/169,341
• Time in Patent Office: 928 Days
• Field of Search: 717/5, 717/7, 717/9, 117/207, 117/163
• US Class Current: 717/145
• CPC Class Codes: G06F 9/4491 Optimising based on receiver type

Abstract

A dynamic compiler determines whether to inline methods in place of virtual method calls by inspecting such calls'"'"' receiver expressions. If a given call site meets other criteria for inlining, the method is inlined if its receiver expression can be proved to have a property called “pre-existence.” One kind of expression whose pre-existence is easily proved is a calling-procedure argument to which the body of the calling procedure makes no assignment. One of the other criteria is that the argument'"'"'s static type is a class whose definition of the callee method has not been overridden, and the compiler employs a dependency data structure to record against both the caller and the callee that the caller contains code whose validity depends on the assumption that this criterion has been met. If the compiler thereafter compiles another implementation of the callee method, it inspects the dependency structures in which dependencies have been recorded against the callee method, and it recompiles the callers whose object code'"'"'s validity is indicated by such structures to depend on that callee method'"'"'s not having been overridden. The restriction of inlining to pre-existing receiver expression allows currently running invocations of the original compilation of the caller method to continue without fear of error.

Claims

1. A computer system configured by machine-readable instructions to:

A) read electrical signals representing a source-code calling procedure that includes at least one call site at which the calling procedure calls a virtual method on an object referred to by a receiver expression that refers to an object;

B) compile the source-code calling procedure into an object-code calling procedure by;

i) determining, for each call site that meets threshold criteria for direct inlining, whether that call site meets any of at least one preexistence criterion from which it can be inferred during the calling procedure'"'"'s compilation that the class of the object to which the receiver refers during any given execution of the calling procedure will have been loaded by the time the given execution commences; and

ii) for each call site thereby determined to meet a pre-existence criterion, placing into the object-code calling procedure directly inlined code for each currently loaded form of the virtual method called by the source-code calling procedure thereat; and

C) store the object-code calling procedure in a machine-readable storage medium.

2. A computer system as defined in claim 1 wherein the machine-readable instructions configure the computer system to:

A) record, against each virtual method inlined in the object-code calling procedure as a result of its call site'"'"'s meeting at least one said pre-existence criterion, the object-code calling procedure'"'"'s dependence on the current number of implementations of that virtual method;

B) thereafter read electrical signals representing a new source-code form of a virtual method after the object-code calling procedure has been stored in the machine-readable storage medium;

C) compile the new source-code form into a new object-code form;

D) determine whether the new form overrides a virtual method against which the calling procedure'"'"'s dependence on a given number of implementations has been recorded; and

E) if the new form does override such a virtual method;

i) recompile the source-code calling procedure into a replacement object-code calling procedure; and

ii) store the replacement object-code calling procedure in a machine-readable storage medium before permitting any of the compiled object code to be executed after the new source-code form has been compiled.

3. A computer system as defined in claim 2 wherein one said threshold criterion for direct inlining at a call site is that only one form of the virtual method called at the call site has been loaded.

4. A computer system as defined in claim 1 wherein one said pre-existence criterion is that the receiver expression is a calling-procedure local variable to which the calling procedure does not assign a value.

5. A computer system as defined in claim 1 wherein one said pre-existence criterion is that the receiver expression is an invariant local variable, where an invariant local variable is defined as a local variable to which the calling procedure does not assign a value other than that of another invariant local variable.

6. A computer system as defined in claim 1 wherein one said pre-existence criterion for a call site is that the receiver expression refers to an immutable member of an object that meets a criterion from which it can be inferred during the calling procedure'"'"'s compilation that the object to which receiver refers during any given execution of the calling procedure will have been constructed by the time the given execution commences.

7. A computer system as defined in claim 1 wherein one said pre-existence criterion for a call site is that the receiver expression refers to an immutable member either of another immutable member or of an object that is referred to by an invariant local variable, where an immutable member is one that can be assigned only in a constructor, and an ins variant local variable is defined as a local variable to which the calling procedure does not assign a value other than that of another invariant local variable.

8. A computer system configured by machine-readable instructions to:

A) read electrical signals representing a source-code calling procedure that calls a target virtual method;

B) compile the source-code calling procedure into an object-code calling procedure by placing directly inlined code for each currently loaded form of the target virtual method into the object-code calling procedure;

C) record against the calling procedure and the target method the calling procedure'"'"'s dependence on the current number of implementations of the target virtual method;

D) store the object-code calling procedure in a machine-readable storage medium;

E) thereafter read electrical signals representing a new form of a virtual method;

F) determine whether the new form overrides a virtual method against which the calling procedure'"'"'s dependence on a given number of implementations has been recorded;

G) if so, recompile the source-code calling procedure into a replacement object-code calling procedure; and

H) store the replacement object-code calling procedure in a machine-readable storage medium.

9. A computer system including:

A) means for reading electrical signals representing a source-code calling procedure that includes at least one call site at which the calling procedure calls a virtual method on an object referred to by a receiver expression that refers to an object;

B) means for compiling the source-code calling procedure into an object-code calling procedure by;

i) determining, for each call site that meets threshold criteria for direct inlining, whether that call site meets any of at least one preexistence criterion from which it can be inferred during the calling procedure'"'"'s compilation that the class of the object to which the receiver refers during any given execution of the calling procedure will have been loaded by the time the given execution commences; and

ii) for each call site thereby determined to meet a pre-existence criterion, placing into the object-code calling procedure directly inlined code for each currently loaded form of the virtual method called by the source-code calling procedure thereat; and

C) means for storing the object-code calling procedure in a machine-readable storage medium.

10. A computer system as defined in claim 9 further including:

A) means for recording, against each virtual method inlined in the object-code calling procedure as a result of its call site'"'"'s meeting at least one said preexistence criterion, the object-code calling procedure'"'"'s dependence on the current number of implementations of that virtual method;

B) means for thereafter reading electrical signals representing a new source-code form of a virtual method after the object-code calling procedure has been stored in the machine-readable storage medium;

C) means for compiling the new source-code form into a new object-code form;

D) means for determining whether the new form overrides a virtual method against which the calling procedure'"'"'s dependence on a given number of implementations has been recorded; and

E) means for, if the new form does override such a virtual method;

i) recompiling the source-code calling procedure into a replacement object-code calling procedure; and

ii) storing the replacement object-code calling procedure in a machine-readable storage medium before permitting any of the compiled object code to be executed after the new source-code form has been compiled.

11. A computer system as defined in claim 10 wherein one said threshold criterion for direct inlining at a call site is that only one form of the virtual method called at the call site has been loaded.

12. A computer system as defined in claim 9 wherein one said pre-existence criterion is that the receiver expression is a calling-procedure local variable to which the calling procedure does not assign a value.

13. A computer system as defined in claim 9 wherein one said pre-existence criterion is that the receiver expression is an invariant local variable, where an invariant local variable is defined as a local variable to which the calling procedure does not assign a value other than that of another invariant local variable.

14. A computer system as defined in claim 9 wherein one said pre-existence criterion for a call site is that the receiver expression refers to an immutable member of an object that meets a criterion from which it can be inferred during the calling procedure'"'"'s compilation that the object to which receiver refers during any given execution of the calling procedure will have been constructed by the time the given execution commences.

15. A computer system as defined in claim 9 wherein one said pre-existence criterion for a call site is that the receiver expression refers to an immutable member either of another immutable member or of an object that is referred to by an invariant local variable, where an immutable member is one that can be assigned only in a constructor, and an invariant local variable is defined as a local variable to which the calling procedure does not assign a value other than that of another invariant local variable.

16. A computer system comprising:

A) means for reading electrical signals representing a source-code calling procedure that calls a target virtual method;

B) means for compiling the source-code calling procedure into an object-code calling procedure by placing directly inlined code for each currently loaded form of the target virtual method into the object-code calling procedure;

C) means for recording against the calling procedure and the target method the calling procedure'"'"'s dependence on the current number of implementations of the target virtual method;

D) means for storing the object-code calling procedure in a machine-readable storage medium;

E) means for thereafter reading electrical signals representing a new form of a virtual method;

F) means for determining whether the new form overrides a virtual method against which the calling procedure'"'"'s dependence on a given number of implementations has been recorded;

G) means for, if so, recompiling the source-code calling procedure into a replacement object-code calling procedure; and

H) means for storing the replacement object-code calling procedure in a machine-readable storage medium.

17. A method of generating object code comprising:

A) reading electrical signals representing a source-code calling procedure that includes at least one call site at which the calling procedure calls a virtual method on an object referred to by a receiver expression that refers to an object;

B) compiling the source-code calling procedure into an object-code calling procedure by;

i) determining, for each call site that meets threshold criteria for direct inlining, whether that call site meets any of at least one preexistence criterion from which it can be inferred during the calling procedure'"'"'s compilation that the class of the object to which the receiver refers during any given execution of the calling procedure will have been loaded by the time the given execution commences; and

ii) for each call site thereby determined to meet a pre-existence criterion, placing into the object-code calling procedure directly inlined code for each currently loaded form of the virtual method called by the source-code calling procedure thereat; and

C) storing the object-code calling procedure in a machine-readable storage medium.

18. A method as defined in claim 17 further including:

A) recording, against each virtual method inlined in the object-code calling procedure as a result of its call site'"'"'s meeting at least one said preexistence criterion, the object-code calling procedure'"'"'s dependence on the current number of implementations of that virtual method;

B) thereafter reading electrical signals representing a new source-code form of a virtual method after the object-code calling procedure has been stored in the machine-readable storage medium;

C) compiling the new source-code form into a new object-code form;

D) determining whether the new form overrides a virtual method against which the calling procedure'"'"'s dependence on a given number of implementations has been recorded; and

E) if the new form does override such a virtual method;

i) recompiling the source-code calling procedure into a replacement object-code calling procedure; and

ii) storing the replacement object-code calling procedure in a machine-readable storage medium before permitting any of the compiled object code to be executed after the new source-code form has been compiled.

19. A method as defined in claim 18 wherein one said threshold criterion for direct inlining at a call site is that only one form of the virtual method called at the call site has been loaded.

20. A method as defined in claim 17 wherein one said pre-existence criterion is that the receiver expression is a calling-procedure local variable to which the calling procedure does not assign a value.

21. A method as defined in claim 17 wherein one said pre-existence criterion is that the receiver expression is an invariant local variable, where an invariant local variable is defined as a local variable to which the calling procedure does not assign a value other than that of another invariant local variable.

22. A method as defined in claim 17 wherein one said pre-existence criterion for a call site is that the receiver expression refers to an immutable member of an object that meets a criterion from which it can be inferred during the calling procedure'"'"'s compilation that the object to which receiver refers during any given execution of the calling procedure will have been constructed by the time the given execution commences.

23. A method as defined in claim 17 wherein one said pre-existence criterion for a call site is that the receiver expression refers to an immutable member either of another immutable member or of an object that is referred to by an invariant local variable, where an immutable member is one that can be assigned only in a constructor, and an invariant local variable is defined as a local variable to which the calling procedure does not assign a value other than that of another invariant local variable.

24. A method of compiling object code comprising:

A) reading electrical signals representing a source-code calling procedure that calls a target virtual method;

B) compiling the source-code calling procedure into an object-code calling procedure by placing directly inlined code for each currently loaded form of the target virtual method into the object-code calling procedure;

C) recording against the calling procedure and the target method the calling procedure'"'"'s dependence on the current number of implementations of the target virtual method;

D) storing the object-code calling procedure in a machine-readable storage medium;

E) thereafter reading electrical signals representing a new form of a virtual method;

F) determining whether the new form overrides a virtual method against which the calling procedure'"'"'s dependence on a given number of implementations has been recorded;

G) if so, recompiling the source-code calling procedure into a replacement object-code calling procedure; and

H) storing the replacement object-code calling procedure in a machine-readable storage medium.

25. A computer data signal embodied in a carrier wave and representing a sequence of instructions that, when executed by a computer system, configures the computer system to:

A) read electrical signals representing a source-code calling procedure that includes at least one call site at which the calling procedure calls a virtual method on an object referred to by a receiver expression that refers to an object;

B) compile the source-code calling procedure into an object-code calling procedure by;

i) determining, for each call site that meets threshold criteria for direct inlining, whether that call site meets any of at least one preexistence criterion from which it can be inferred during the calling procedure'"'"'s compilation that the class of the object to which the receiver refers during any given execution of the calling procedure will have been loaded by the time the given execution commences; and

ii) for each call site thereby determined to meet a pre-existence criterion, placing into the object-code calling procedure directly inlined code for each currently loaded form of the virtual method called by the source-code calling procedure thereat; and

C) store the object-code calling procedure in a machine-readable storage medium.

26. A computer data signal as defined in claim 25 wherein the machine-readable instructions configure the computer system to:

A) record, against each virtual method inlined in the object-code calling procedure as a result of its call site'"'"'s meeting at least one said pre-existence criterion, the object-code calling procedure'"'"'s dependence on the current number of implementations of that virtual method;

B) thereafter read electrical signals representing a new source-code form of a virtual method after the object-code calling procedure has been stored in the machine-readable storage medium;

C) compile the new source-code form into a new object-code form;

D) determine whether the new form overrides a virtual method against which the calling procedure'"'"'s dependence on a given number of implementations has been recorded; and

E) if the new form does override such a virtual method;

i) recompile the source-code calling procedure into a replacement object-code calling procedure; and

ii) store the replacement object-code calling procedure in a machine-readable storage medium before permitting any of the compiled object code to be executed after the new source-code form has been compiled.

27. A computer data signal as defined in claim 26 wherein one said threshold criterion for direct inlining at a call site is that only one form of the virtual method called at the call site has been loaded.

28. A computer data signal as defined in claim 25 wherein one said pre-existence criterion is that the receiver expression is a calling-procedure local variable to which the calling procedure does not assign a value.

29. A computer data signal as defined in claim 25 wherein one said pre-existence criterion is that the receiver expression is an invariant local variable, where an invariant local variable is defined as a local variable to which the calling procedure does not assign a value other than that of another invariant local variable.

30. A computer data signal as defined in claim 25 wherein one said pre-existence criterion for a call site is that the receiver expression refers to an immutable member of an object that meets a criterion from which it can be inferred during the calling procedure'"'"'s compilation that the object to which receiver refers during any given execution of the calling procedure will have been constructed by the time the given execution commences.

31. A computer data signal as defined in claim 25 wherein one said pre-existence criterion for a call site is that the receiver expression refers to an immutable member either of another immutable member or of an object that is referred to by an invariant local variable, where an immutable member is one that can be assigned only in a constructor, and an invariant local variable is defined as a local variable to which the calling procedure does not assign a value other than that of another invariant local variable.

32. A computer data signal embodied in a carrier wave and representing a sequence of instructions that, when executed by a computer system, configures the computer system to:

A) read electrical signals representing a source-code calling procedure that calls a target virtual method;

B) compile the source-code calling procedure into an object-code calling procedure by placing directly inlined code for each currently loaded form of the target virtual method into the object-code calling procedure;

C) record against the calling procedure and the target method the calling procedure'"'"'s dependence on the current number of implementations of the target virtual method;

D) store the object-code calling procedure in a machine-readable storage medium;

E) thereafter read electrical signals representing a new form of a virtual method;

F) determine whether the new form overrides a virtual method against which the calling procedure'"'"'s dependence on a given number of implementations has been recorded;

G) if so, recompile the source-code calling procedure into a replacement object-code calling procedure; and

H) store the replacement object-code calling procedure in a machine-readable storage medium.

33. A storage medium containing instructions readable by a computer system to configure the computer system to:

A) read electrical signals representing a source-code calling procedure that includes at least one call site at which the calling procedure calls a virtual method on an object referred to by a receiver expression that refers to an object;

B) compile the source-code calling procedure into an object-code calling procedure by;

i) determining, for each call site that meets threshold criteria for direct inlining, whether that call site meets any of at least one pre-existence criterion from which it can be inferred during the calling procedure'"'"'s compilation that the class of the object to which the receiver refers during any given execution of the calling procedure will have been loaded by the time the given execution commences; and

ii) for each call site thereby determined to meet a pre-existence criterion, placing into the object-code calling procedure directly inlined code for each currently loaded form of the virtual method called by the source-code calling procedure thereat; and

C) store the object-code calling procedure in a machine-readable storage medium.

34. A storage medium as defined in claim 33 wherein the machine-readable instructions configure the computer system to:

A) record, against each virtual method inlined in the object-code calling procedure as a result of its call site'"'"'s meeting at least one said pre-existence criterion, the object-code calling procedure'"'"'s dependence on the current number of implementations of that virtual method;

B) thereafter read electrical signals representing a new source-code form of a virtual method after the object-code calling procedure has been stored in the machine-readable storage medium;

C) compile the new source-code form into a new object-code form;

D) determine whether the new form overrides a virtual method against which the calling procedure'"'"'s dependence on a given number of implementations has been recorded; and

E) if the new form does override such a virtual method;

i) recompile the source-code calling procedure into a replacement object-code calling procedure; and

ii) store the replacement object-code calling procedure in a machine-readable storage medium before permitting any of the compiled object code to be executed after the new source-code form has been compiled.

35. A storage medium as defined in claim 34 wherein one said threshold criterion for direct inlining at a call site is that only one form of the virtual method called at the call site has been loaded.

36. A storage medium as defined in claim 33 wherein one said pre-existence criterion is that the receiver expression is a calling-procedure local variable to which the calling procedure does not assign a value.

37. A storage medium as defined in claim 33 wherein one said pre-existence criterion is that the receiver expression is an invariant local variable, where an invariant local variable is defined as a local variable to which the calling procedure does not assign a value other than that of another invariant local variable.

38. A storage medium as defined in claim 33 wherein one said pre-existence criterion for a call site is that the receiver expression refers to an immutable member of an object that meets a criterion from which it can be inferred during the calling procedure'"'"'s compilation that the object to which receiver refers during any given execution of the calling procedure will have been constructed by the time the given execution commences.

39. A storage medium as defined in claim 33 wherein one said pre-existence criterion for a call site is that the receiver expression refers to an immutable member either of another immutable member or of an object that is referred to by an invariant local variable, where an immutable member is one that can be assigned only in a constructor, and an invariant local variable is defined as a local variable to which the calling procedure does not assign a value other than that of another invariant local variable.

40. A storage medium configured by machine-readable instructions to:

A) read electrical signals representing a source-code calling procedure that calls a target virtual method;

B) compile the source-code calling procedure into an object-code calling procedure by placing directly inlined code for each currently loaded form of the target virtual method into the object-code calling procedure;

C) record against the calling procedure and the target method the calling procedure'"'"'s dependence on the current number of implementations of the target virtual method;

D) store the object-code calling procedure in a machine-readable storage medium;

E) thereafter read electrical signals representing a new form of a virtual method;

F) determine whether the new form overrides a virtual method against which the calling procedure'"'"'s dependence on a given number of implementations has been recorded;

G) if so, recompile the source-code calling procedure into a replacement object-code calling procedure; and

H) store the replacement object-code calling procedure in a machine-readable storage medium.