Method for JIT compiler to optimize repetitive synchronization

• US 7,552,428 B2
• Filed: 05/27/2004
• Issued: 06/23/2009
• 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:
  US10/854,873
• Publication Number:
  US 20040250240A1
• Time in Patent Office: 1,853 Days
• Field of Search: 717/148, 717/149, 717/154, 717/155, 717/156, 717/159
• 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;

analyzing said information to determine a set of synchronization operations to be removed from the program code, wherein said examining 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 the synchronization operations to be removed from the program code;

modifying the program code based on said set of the synchronization operations to be removed from the program code, said modifying includes inserting a new synchronization operation where necessary in the program code by removing the synchronization operations in said set by;

examining the program code in forward order for each instruction in said each block of instructions 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, and said step of examining the program code in the forward order further comprises, upon a given instruction under consideration being a locking operation on said given object and said flag indicating whether the earlier locking operation is to be performed on said given object is set, adding said given instruction to said set of the synchronization operations to be removed from the program code;

examining the program code in backward order for each instruction in said each block of instructions 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, and said step of examining the program code in the backward order further comprises, upon an additional given instruction under consideration being an unlocking operation on said given object and said flag indicating whether the later unlocking operation is to be performed on said given object is set, adding said additional given instruction to said set of the synchronization operations to be removed from the program code, wherein said flag indicating whether the earlier locking operation is to be performed and said flag indicating whether the later unlocking operation is to be performed are represented by a bit;

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 the earlier locking operation is to be performed on said given object and said bit indicating whether the later unlocking operation is to be performed on said given object;

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

2. A just-in-time compiler of program code stored on a computer readable 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 operate to:

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

analyze said information to determine a set of synchronization operations to be removed from the program code, wherein said examining identifies 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 the synchronization operations to be removed from the program code;

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

examining the program code in forward order for each instruction in said each block of instructions 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, and said step of examining the program code in the forward order further comprises, upon a given instruction under consideration being a locking operation on said given object and said flag indicating whether the earlier locking operation is to be performed on said given object is set, adding said given instruction to said set of the synchronization operations to be removed from the program code;

examining the program code in backward order for each instruction in said each block of instructions 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, and said step of examining the program code in the backward order further comprises, upon an additional given instruction under consideration being an unlocking operation on said given object and said flag indicating whether the later unlocking operation is to be performed on said given object is set, adding said additional given instruction to said set of the synchronization operations to be removed from the program code, wherein said flag indicating whether the earlier locking operation is to be performed and said flag indicating whether the later unlocking operation is to be performed are represented by a bit;

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 the earlier locking operation is to be performed on said given object and said bit indicating whether the later unlocking operation is to be performed on said given object;

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

3. A computer readable 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;

analyze said information to determine a set of synchronization operations to be removed from the program code, wherein said examining identifies 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 the synchronization operations to be removed from the program code;

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

examining the program code in forward order for each instruction in said each block of instructions 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, and said step of examining the program code in the forward order further comprises, upon a given instruction under consideration being a locking operation on said given object and said flag indicating whether the earlier locking operation is to be performed on said given object is set, adding said given instruction to said set of the synchronization operations to be removed from the program code;

examining the program code in backward order for each instruction in said each block of instructions 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, and said step of examining the program code in the backward order further comprises, upon an additional given instruction under consideration being an unlocking operation on said given object and said flag indicating whether the later unlocking operation is to be performed on said given object is set, adding said additional given instruction to said set of the synchronization operations to be removed from the program code, wherein said flag indicating whether the earlier locking operation is to be performed and said flag indicating whether the later unlocking operation is to be performed are represented by a bit;

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 the earlier locking operation is to be performed on said given object and said bit indicating whether the later unlocking operation is to be performed on said given object;

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