Post-register allocation profile directed instruction scheduling

• US 20070150880A1
• Filed: 12/28/2005
• Published: 06/28/2007
• Est. Priority Date: 12/28/2005
• Status: Active Grant

• Current Assignee: Twitter Inc (X Holdings Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Vasilevskiy, Alexander, Mitran, Marcel
• Granted Patent: US 7,770,161 B2
• Time in Patent Office: Days
• US Class Current: 717/161
• CPC Class Codes: G06F 8/441 Register allocation; Assignment of physical memory space to logical memory space
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836

Abstract

A computer implemented method, system, and computer usable program code for selective instruction scheduling. A determination is made whether a region of code exceeds a modification threshold after performing register allocation on the region of code. The region of code is marked as a modified region of code in response to the determination that the region of code exceeds the modification threshold. A determination is made whether the region of code exceeds an execution threshold in response to the determination that the region of code is marked as a modified region of code. Post-register allocation instruction scheduling is performed on the region of code in response to the determination that the region of code is marked as a modified region of code and the determination that the region of code exceeds the execution threshold.

Claims

1. A computer implemented method for selective instruction scheduling, the computer implemented method comprising:

determining whether a region of code exceeds a modification threshold after performing register allocation on the region of code;

responsive to determining that the region of code exceeds the modification threshold, marking the region of code as a modified region of code;

responsive to marking the region of code as the modified region of code, determining whether the region of code exceeds an execution threshold; and

responsive to determining that the region of code is marked as a modified region of code and determining that the region of code exceeds the execution threshold, performing post-register allocation instruction scheduling on the region of code.

2. The computer implemented method of claim 1, wherein the execution threshold is based on hotness and comprises one of a hot threshold, a warm threshold, and a cold threshold.

3. The computer implemented method of claim 2, wherein the hot threshold is defined as the region of code being executed more than 10% of the time, the warm threshold is defined as the region of code being executed between 1%-10% of the time, and the cold threshold is defined as the region of code being executed less than 1% of the time.

4. The computer implemented method of claim 3, wherein the execution threshold is one of the warm threshold or the hot threshold.

5. The computer implemented method of claim 1, further comprising:

recording a number of register spills, a number of register copies and a number of register exchanges that occur during register allocation.

6. The computer implemented method of claim 5, further comprising

assigning weights to register spills, register copies and register exchanges;

multiplying the number of register spills, register copies and register exchanges by the respective weight assigned thereto to form a weighted sum of the number of register spills, the number of register copies and the number of register exchanges that occur during register allocation to determine whether the region of code exceeds the modification threshold.

7. The computer implemented method of claim 6, wherein a user specifies a weight for each of the number of register spills, the number of register copies, and the number of register exchanges to be used in the weighting and summing step.

8. The computer implemented method of claim 9, the modification threshold is that at least one of the following occurs:

(a) the number of register spills is one;

(b) the number of register copies is three;

or

(c) the number of register exchanges is one.

9. The computer implemented method of claim 1, further comprising profiling the region of code during execution of the region of code to determine the execution threshold.

10. The computer implemented method of claim 9, wherein the profiling step is performed by a dynamic compiler and profile data gathered by the dynamic compiler includes at least one of execution statistics and language semantics.

11. The computer implemented method of claim 1, wherein the region of code is one of a plurality of regions of code within a module of code.

12. A system comprising:

a processor for executing an operating system and a dynamic compiler; and

a storage operably coupled to the processor for storing the operating system and dynamic compiler wherein the operating system and dynamic compiler may be loaded into a main memory for execution by the processor wherein the dynamic compiler determines whether a region of code exceeds a modification threshold after performing register allocation on the region of code, marks the region of code as a modified region of code in response to a determination that the region of code exceeds a modification threshold, determines whether the region of code exceeds an execution threshold in response to determining that the region of code is marked as a modified region of code, and performs post-register allocation instruction scheduling on the modified region of code in response to the determination that the region of code is marked as a modified region of code and that the region of code exceeds the execution threshold.

13. The system of claim 12, wherein the dynamic compiler is a Java just-in-time compiler.

14. The system of claim 12, wherein the region of code is one of a plurality of regions of code within a module of code.

15. The system of claim 12, wherein the dynamic compiler comprises an instruction scheduler, a register allocator, and a profiler.

16. A computer program product comprising a computer usable medium including computer usable program code for selective instruction scheduling, said computer program product including:

computer usable program code for determining whether a region of code exceeds a modification threshold after performing register allocation on the region of code;

computer usable program code responsive to determining the region of code exceeds a modification threshold, for marking the region of code as a modified region of code;

computer usable program code responsive to determining that the region of code has been marked as a modified region of code, for determining whether a region of code exceeds an execution threshold; and

computer usable program code responsive to the region of code being marked as a modified region of code and determining that the region of code exceeds the execution threshold, for performing post-register allocation instruction scheduling on the modified region of code.

17. The computer program product of claim 16, further comprising:

computer usable program code for profiling the region of code during execution of the region of code to determine the execution threshold.

18. The computer program product of claim 16, further comprising:

computer usable program code for recording a number of register spills, a number of register copies and a number of register exchanges that occur during register allocation.

19. The computer program product of claim 18, further comprising

computer usable program code for assigning weights to register spills, register copies and register exchanges;

computer usable program code for multiplying the number of register spills, register copies and register exchanges by the respective weight assigned thereto to form a weighted sum of the number of register spills, the number of register copies and the number of register exchanges that occur during register allocation to determine whether the region of code exceeds the modification threshold.

20. The computer program product of claim 16, wherein the execution threshold is one of a warm threshold or a hot threshold.