Method for JIT compiler to optimize repetitive synchronization

• US 8,104,028 B2
• Filed: 03/31/2009
• Issued: 01/24/2012
• Est. Priority Date: 05/30/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Stoodley, Mark Graham, Sundaresan, Vijay
• Primary Examiner(s): Kang, Insun
• Application Number:
  US12/414,991
• Publication Number:
  US 20090235240A1
• Time in Patent Office: 1,029 Days
• Field of Search: None
• US Class Current: 717/148
• 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:

examining said program code to collect information about each block of said plurality of blocks to identify candidate locking operations and candidate unlocking operations in paths between an initial locking operation and a final unlocking operation, wherein said information includes a first subset, a second subset and a third subset of said plurality of blocks, where said first subset includes blocks that include a locking operation, said second subset includes blocks that include an unlocking operation, and said third subset includes blocks that succeed a given block;

analyzing said information to determine a set of synchronization operations to be removed, including;

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 to be removed;

modifying the program code based on said set of synchronization operations to 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, further comprising the step of:

examining 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.

3. The method of claim 2, wherein said step of examining 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.

4. The method of claim 3, wherein said step of examining 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 to be removed.

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

examining 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.

6. The method of claim 5, wherein said step of examining 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.

7. The method of claim 6, wherein said step of examining 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 to be removed.

8. The method of claim 7, 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.

9. The method of claim 8, 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.

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

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

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

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

13. The method of claim 1, 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.

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

15. The method of claim 14, 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.

16. The method of claim 1, wherein said information includes a fourth subset of said plurality of blocks, where said fourth subset includes blocks that precede 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 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 to be removed.

18. The method of claim 17, 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.

19. A just-in-time compiler of program code stored on a computer readable tangible medium, 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 configured to:

examine said program code to collect information about each block of said plurality of blocks to identify candidate locking operations and candidate unlocking operations in paths between an initial locking operation and a final unlocking operation, wherein said information includes a first subset, a second subset and a third subset of said plurality of blocks, where said first subset includes blocks that include a locking operation, said second subset includes blocks that include an unlocking operation, and said third subset includes blocks that succeed a given block;

analyze said information to determine a set of synchronization operations to be removed by

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 to be removed;

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

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

examine 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 to identify candidate locking operations and candidate unlocking operations in paths between an initial locking operation and a final unlocking operation, wherein said information includes a first subset, a second subset and a third subset of said plurality of blocks, where said first subset includes blocks that include a locking operation, said second subset includes blocks that include an unlocking operation, and said third subset includes blocks that succeed a given block;

analyze said information to determine a set of synchronization operations to be removed by

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 to be removed; and

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