Dynamic division optimization for a just-in-time compiler

• US 7,194,736 B2
• Filed: 12/10/2002
• Issued: 03/20/2007
• Est. Priority Date: 12/10/2002
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Lueh, Guei-Yuan, Shi, Xiaohua, Ying, Zhiwei
• Primary Examiner(s): Dam; Tuan
• Assistant Examiner(s): KENDALL, CHUCK O
• Application Number:
  US10/316,596
• Publication Number:
  US 20040111714A1
• Time in Patent Office: 1,561 Days
• Field of Search: 717130-161
• US Class Current: 717/153
• CPC Class Codes: G06F 9/45516 Runtime code conversion or optimisation

Abstract

An arrangement is provided for improving the performance of a dynamic compiler, specifically for dynamically optimizing integer division operations. When a compiler receives an integer division code at runtime, the compiler dynamically profiles a divisor of the division code. The integer division code is then optimized based on the characteristics of the divisor, which are determined at runtime.

Claims

1. A method for improving the performance of a dynamic compiler, comprising:

receiving a first code;

determining a strategy for optimizing a segment of the first code, wherein determining the strategy includes dynamically determining a best strategy available to the compiler to optimize the segment according to characteristics of the segment;

optimizing the segment of the first code using the determined optimization strategy, wherein optimizing the segment includes dynamically optimizing integer division operations; and

outputting a second code, the second code representing the optimized first code.

2. The method of claim 1, wherein the first code represents a computer programming code in a high-level programming language.

3. The method of claim 1, wherein optimizing the segment of the first code comprises converting the segment in a high-level language to a set of lower-level computing instructions native to an underlying computing architecture, selecting a best optimization implementation, and optimizing the set of lower-level computing instructions based on the determined optimization strategy.

4. The method of claim 1, wherein the second code comprises the optimized first code in lower-level computing instructions native to the underlying computing architecture.

5. An article comprising a machine accessible medium having content stored thereon, wherein when the content is accessed by a processor, the content provides for improving the performance of a dynamic compiler by:

receiving a first code;

determining a strategy for optimizing a segment of the first code, wherein determining the strategy includes dynamically determining a best strategy available to the compiler to optimize the segment according to characteristics of the segment;

optimizing the segment of the first code using the determined optimization strategy, wherein optimizing the segment includes dynamically optimizing integer division operations; and

outputting a second code, the second code representing the optimized first code.

6. The article of claim 5, wherein the first code represents a computer programming code in a high-level programming language.

7. The article of claim 5, wherein content for optimizing the segment of the first code comprises content for converting the segment in a high-level language to a set of lower-level computing instructions native to an underlying computing architecture, selecting a best optimization implementation, and optimizing the set of lower-level computing instructions based on the determined optimization strategy.

8. The article of claim 5, wherein the second code comprises the optimized first code in lower-level computing instructions native to the underlying computing architecture.

9. A compiling system, comprising:

at least one pre-processing module to receive a first code in a high-level computer programming language;

an optimization strategy selection mechanism to determine a strategy for optimizing a segment of the first code, the optimization strategy selection mechanism including a component to dynamically determine a best strategy available to the compiler to optimize the segment according to characteristics of the segment;

at least one optimization mechanism to optimize the segment of the first code using the determined optimization strategy, the optimization mechanism including a division optimization mechanism to dynamically optimize integer division operations;

a library to provide optimization implementations; and

at least one post-processing module to generate a second code based on optimized segments of the first code and optimization implementations in the library.

10. The compiling system of claim 9, wherein the optimization mechanism comprises a selection component to select an optimization implementation for the segment of the first code based on the determined optimization strategy.

11. The compiling system of claim 9, wherein the post-processing module processes optimized segments of the first code to generate a second code in lower-level computing instructions native to an underlying computing architecture.

12. A method for dynamically optimizing integer division operations, comprising:

receiving a division code at runtime;

identifying a divisor of the division code;

updating information describing the divisor in a divisor cache, if the divisor is not invariant;

preparing optimization parameters for the divisor, if the divisor becomes invariant for the first time during runtime; and

invoking a division implementation for an invariant divisor using the optimization parameters.

13. The method of claim 12, wherein identifying the divisor comprises:

identifying a zero-valued divisor;

throwing an arithmetic exception if the divisor is zero; and

searching the divisor cache for the divisor if the divisor is not zero.

14. The method of claim 13, wherein searching the divisor cache for the divisor comprises identifying an invariant divisor whose optimization parameters have already been prepared and were previously stored in the divisor cache.

15. The method of claim 14, wherein identifying an invariant divisor comprises comparing the divisor with a value of a flag field in the divisor cache.

16. The method of claim 12, wherein updating information describing the divisor in the divisor cache comprises:

creating a new entry in the divisor cache and initializing at least a flag field and an optimization parameter field of the entry, if the divisor appears for the first time;

incrementing the number of occurrences of the divisor of the entry;

determining that the divisor becomes invariant for the first time during runtime, if the number of occurrences of the divisor becomes equal to a pre-set trigger number; and

requesting preparation of optimization parameters for the divisor which becomes invariant for the first time during runtime.

17. The method of claim 16, wherein preparing optimization parameters for the divisor comprises:

preparing optimization parameters required by available optimization implementations;

storing the prepared optimization parameters in the divisor cache; and

updating the flag field in the divisor cache after optimization parameters of the divisor are stored in the divisor cache.

18. The method of claim 12, wherein invoking a division implementation comprises:

invoking a normal division code if the divisor is not invariant at runtime; and

selecting a best optimization implementation, passing optimization parameters to the selected implementation, and invoking the optimized implementation, if the divisor is invariant at runtime.

19. An article comprising:

a machine accessible medium having content stored thereon, wherein when the content is accessed by a processor, the content provides for dynamically optimizing integer division operations by;

receiving a division code at runtime;

identifying a divisor of the division code;

updating information describing the divisor in a divisor cache, if the divisor is not invariant;

preparing optimization parameters for the divisor, if the divisor becomes invariant for the first time during runtime; and

invoking a division implementation for an invariant divisor using the optimization parameters.

20. The article of claim 19, wherein content for identifying the divisor comprises content for:

identifying a zero-valued divisor;

throwing an arithmetic exception if the divisor is zero; and

searching the divisor cache for the divisor if the divisor is not zero.

21. The article of claim 20, wherein content for searching the divisor cache for the divisor comprises content for identifying an invariant divisor whose optimization parameters have already been prepared and were previously stored in the divisor cache.

22. The article of claim 21, wherein content for identifying an invariant divisor comprises content for comparing the divisor with a value of a flag field in the divisor cache.

23. The article of claim 19, wherein content for updating information describing the divisor in the divisor cache comprises content for:

creating a new entry in the divisor cache and initializing at least a flag field and an optimization parameter field of the entry, if the divisor appears for the first time;

incrementing the number of occurrences of the divisor in the entry;

determining that the divisor becomes invariant for the first time during runtime, if the number of occurrences of the divisor becomes equal to a pre-set trigger number; and

requesting preparation of optimization parameters for the divisor which becomes invariant for the first time during runtime.

24. The article of claim 23, wherein content for preparing optimization parameters for the divisor comprises content for:

preparing optimization parameters required by available optimization implementations;

storing the prepared optimization parameters in the divisor cache; and

updating the flag field in the divisor cache after optimization parameters of the divisor are stored in the divisor cache.

25. The article of claim 19, wherein content for invoking a division implementation comprises content for:

invoking a normal division code if the divisor is not invariant at runtime; and

selecting a best optimization implementation, passing optimization parameters to the selected implementation, and invoking the optimized implementation, if the divisor is invariant at runtime.

26. A system for dynamically optimizing integer divisions, comprising:

a divisor identifier to receive a division code at runtime and to identify a divisor of the division code;

a divisor cache to store information describing divisors;

a divisor profiling mechanism to profile divisors at runtime and to update the divisor cache; and

an optimization preparation mechanism to prepare optimization parameters if the divisor becomes invariant for the first time during runtime.

27. The system of claim 26, wherein the divisor identifier further comprises a detection component to detect a zero-valued divisor and an exception processing component to throw an arithmetic exception if a divisor is zero.

28. The system of claim 27, wherein the divisor identifier further comprises a search component to search for the divisor in the divisor cache to determine whether the divisor is invariant by comparing the divisor with the value in a flag field in the divisor cache, if the divisor is not zero.

29. The system of claim 26, wherein the divisor cache comprises at least one entry for storing information describing a divisor.

30. The system of claim 29, wherein the entry for a divisor in the divisor cache further comprises:

a flag field to store information indicating whether the divisor is found invariant during runtime;

a divisor value field to store the value of the divisor;

a divisor counter field to store the number of occurrences of the divisor at runtime; and

a divisor optimization parameter field to store optimization parameters if the divisor is found invariant during runtime.

31. The system of claim 26, wherein the divisor profiling mechanism comprises:

a creation component to create a new entry in a divisor cache, if a divisor appears for the first time;

an initialization component to initialize at least a flag field and an optimization parameter field of the newly created entry for the divisor in the divisor cache; and

a counting component to increment the number of occurrences of the divisor and record the new number in the divisor counter field of the entry for the divisor in the divisor cache.

32. The system of claim 31, wherein the divisor profiling mechanism further comprises:

a component to determine whether a divisor becomes invariant for the first time during runtime by comparing the number of occurrences of the divisor with a pre-set trigger number;

a component to select a best optimization implementation for a division code with the divisor; and

a component to send requests to the optimization preparation mechanism to prepare optimization parameters for the divisor, if the divisor becomes o invariant for the first time during runtime.

33. The system of claim 32, wherein the divisor profiling mechanism further comprises a component to store the prepared optimization parameters in the divisor cache for the divisor, and to replace the value of the divisor'"'"'s flag field with the divisor in the divisor cache.

34. The system of claim 26, wherein the optimization preparation mechanism comprises:

a component to prepare optimization parameters required by the selected optimization implementation;

a component to pass optimization parameters to the divisor profiling mechanism to update the divisor cache, and to the selected optimization implementation to invoke the selected optimization implementation.