Method for JIT compiler to optimize repetitive synchronization

• US 20040250240A1
• Filed: 05/27/2004
• Published: 12/09/2004
• Est. Priority Date: 05/30/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sundaresan, Vijay, Stoodley, Mark Graham
• Granted Patent: US 7,552,428 B2
• Time in Patent Office: Days
• US Class Current: 717/116
• CPC Class Codes: G06F 9/45516 Runtime code conversion or optimisation
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

Repetitive synchronization in program code is optimized through lock coarsening that is performed subject to a number of constraints. Using a forward pass over the program code followed by a backward pass, region extent bits may be determined that identify the points in the program where object locking can be coarsened. The program code may then be modified to realize coarsened locking regions determined based on the region extent bits. Alternatively, previously determined value numbers may provide much of the information collected by the two passes. In such a case, a single pass over the program code may locate features that limit lock coarsening opportunities. A set of synchronization operations that can be removed may then be determined and used when modifying the program code to coarsen locking regions.

Claims

1. In a just-in-time compiler of program code, the program code including a plurality of blocks of instructions and the program code, when executed, performing repetitive synchronization on a plurality of objects, a method of optimizing said repetitive synchronization, said method comprising the steps of:

considering said program code to collect information about each block of said plurality of blocks;

analyzing said information to determine a set of synchronization operations that may be removed;

modifying the program code based on said set of synchronization operations that may be removed, where said modifying includes inserting a new synchronization operation where necessitated by removing synchronization operations in said set.

2. The method of claim 1, wherein said considering step further comprises identifying candidate locking operations and candidate unlocking operations, in paths between an initial locking operation and a final unlocking operation, to add to said set of synchronization operations that may be removed.

3. The method of claim 2, further comprising the step of:

considering the program code in forward order to determine, at least for the beginning and end of each block of instructions, a flag indicating whether an earlier locking operation is to be performed on a given object.

4. The method of claim 3, wherein said step of considering the program code in forward order to determine a flag indicating whether an earlier locking operation is to be performed is performed for each instruction in said each block of instructions.

5. The method of claim 4, wherein said step of considering the program code in forward order further comprises, if a given instruction under consideration is a locking operation on said given object and said flag said flag indicating whether an earlier locking operation is to be performed on said given object is set, adding said given instruction to said set of synchronization operations that may be removed.

6. The method of claim 5, further comprising the step of:

considering the program code in backward order to determine, at least for said beginning and end of said each block of instructions, a flag indicating whether a later unlocking operation is to be performed on said given object.

7. The method of claim 6, wherein said step of considering the program code in backward order to determine said flag indicating whether a later unlocking operation is to be performed is performed for each instruction in said each block of instructions.

8. The method of claim 7, wherein said step of considering the program code in backward order further comprises, if a further given instruction under consideration is an unlocking operation on said given object and said flag indicating whether a later unlocking operation is to be performed on said given object is set, adding said further given instruction to said set of synchronization operations that may be removed.

9. The method of claim 8, wherein said flag indicating whether an earlier locking operation is to be performed and said flag indicating whether a later unlocking operation is to be performed are represented by a bit.

10. The method of claim 9, further comprising the steps of:

determining a new bit for said given object for said beginning and end of each said block, where said determining said new bit includes performing a logical AND operation on said bit indicating whether an earlier locking operation is to be performed on said given object and said bit indicating whether a later unlocking operation is to be performed on said given object; and

where said new bit for the beginning of a given block of said plurality of blocks differs from said new bit for a directly preceding block, inserting a corrective synchronization operation.

11. The method of claim 10, wherein said step of considering the program code in forward order further comprises identifying a synchronization operation for a particular object as a not legally coarsenable synchronization operation.

12. The method of claim 11, further comprising the step of:

removing candidate synchronization operations associated with said particular object from said set of synchronization operations that may be removed.

13. The method of claim 12, wherein said step of modifying the program code further comprises removing from the program code each synchronization operation in said set of synchronization operations that may be removed.

14. The method of claim 2, wherein said information includes a first subset of said plurality of blocks, where said first subset includes blocks that include a locking operation.

15. The method of claim 14, wherein said information includes a second subset of said plurality of blocks, where said second subset includes blocks that include an unlocking operation.

16. The method of claim 15, wherein said information includes a third subset of said plurality of blocks, where said third subset includes blocks that succeed a given block.

17. The method of claim 16, wherein said step of analyzing said information further comprises the substeps of:

selecting a given object of said plurality of objects, where said given object is repetitively synchronized;

selecting a given block, from said second subset, in which a unlocking operation on said given object is to be performed;

selecting a successor block, from an intersection of said first subset and said third subset, in which a locking operation on said given object is to be performed; and

adding said unlocking operation and said locking operation to said set of synchronization operations that may be removed.

18. The method of claim 17, wherein said step of analyzing said information further comprises the substeps of:

determining a fifth subset of said plurality of blocks, where said fifth subset includes blocks that intervene said given block and said successor block; and

only performing said adding if all blocks in said fifth subset do not include features that limit lock coarsening opportunities.

19. The method of claim 18, wherein said subsets of selecting said given block is performed based on a ranking of said plurality of objects.

20. The method of claim 19, wherein said ranking of a particular object of said plurality of objects is based on a number of times said particular object is synchronized throughout said program code.

21. The method of claim 16, wherein said information includes a fourth subset of said plurality of blocks, where said fourth subset includes blocks that precede a given block.

22. The method of claim 21 wherein said step of analyzing said information further comprises the substeps of:

selecting a given object of said plurality of objects, where said given object is repetitively synchronized;

selecting a given block, from said first subset, in which a locking operation on said given object is performed;

selecting a predecessor block, from an intersection of said second subset and said fourth subset, in which an unlocking operation on said given object is performed; and

adding said locking operation and said unlocking operation to said set of synchronization operations that may be removed.

23. The method of claim 22, wherein said step of analyzing said information further comprises the substeps of:

determining a sixth subset of said plurality of blocks, where said seventh subset includes blocks that intervene said predecessor block and said given block; and

only performing said adding if all blocks in said subset of said sixth type do not include features that limit lock coarsening opportunities.

24. A just-in-time compiler of program code, said program code including a plurality of blocks of instructions and said program code, when executed, performing repetitive synchronization on a plurality of objects, said compiler operable to:

consider said program code to collect information about each block of said plurality of blocks;

analyze said information to determine a set of synchronization operations that may be removed;

modify said program code based on said set of synchronization operations that may be removed, where said modifying includes inserting a new synchronization operation where necessitated by removing synchronization operations in said set.

25. A computer readable medium containing computer-executable instructions which, when performed by a processor in a computer system, cause said computer system to:

consider a listing of program code, said program code including a plurality of blocks of instructions and said program code, when executed, performing repetitive synchronization on a plurality of objects, to collect information about each block of said plurality of blocks;

analyze said information to determine a set of synchronization operations that may be removed; and

modify said program code based on said set of synchronization operations that may be removed, where said modifying includes inserting a new synchronization operation where necessitated by removing synchronization operations in said set.