Method for optimizing locks in computer programs

• US 6,530,079 B1
• Filed: 06/02/1999
• Issued: 03/04/2003
• Est. Priority Date: 06/02/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gupta, Manish, Serrano, Mauricio J., Sreedhar, Vugranam C., Midkiff, Samuel Pratt, Choi, Jong-Deok
• Primary Examiner(s): Morse, Gregory
• Assistant Examiner(s): Vo, Ted T.
• Application Number:
  US09/323,989
• Time in Patent Office: 1,371 Days
• Field of Search: 707/9, 707/158, 707/8, 717/158, 717/159, 717/161, 717/152, 717/153, 717/157, 717/127, 717/128, 717/129, 717/130, 717/131, 712/227
• US Class Current: 717/158
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A method and several variants for using information about the scope of access of objects acted upon by mutual exclusion, or mutex, locks to transform a computer program by eliminating locking operations from the program or simplifying the locking operations, while strictly performing the semantics of the original program. In particular, if it can be determined by a compiler that the object locked can only be accessed by a single thread it is not necessary to perform the “acquire” or “release” part of the locking operation, and only its side effects must be performed. Likewise, if it can be determined that the side effects of a locking operation acting on a variable which is locked in multiple threads are not needed, then only the locking operation, and not the side effects, needs to be performed. This simplifies the locking operation, and leads to faster programs which use fewer computer processor resources to execute; and programs which perform fewer shared memory accesses, which in turn not only causes the optimized program, but also other programs executing on the same computing machine to execute faster. The method also describes how information about the semantics of the locking operation side effects and the information about the scope of access can also be used to eliminate performing the side effect parts of the locking operation, thereby completely eliminating the locking operation. The method also describes how to analyze the program to compute the necessary information about the scope of access. Variants of the method show how one or several of the features of the method may be performed.

Claims

1. A method for optimizing the locking operations in a computer program said method comprising the steps:

(a) classifying a state of all variables involved in locking operations in the computer program as either “

global_escape”

or “

thread-local”

; and

(b) transforming said program by removing all simple locking operations which are on variables having a state of “

thread-local”

,

wherein the strict semantics of the computer program are preserved.

2. A method for optimizing the locking operations in a computer program as recited in claim 1, wherein the step of classifying a state of all variables involved in locking operations in a program as either “

global_escape”

or “

thread-local”

is performed interprocedurally for the complete said program, where some procedures of said program cannot or should not be analyzed by a compiler.

3. A method for optimizing the locking operations in a computer program as recited in claim 2, wherein “

type”

information about program variables is used to improve the quality of information about whether the variable being locked has a state of “

global_escape”

or “

thread-local”

for all locks in a procedure of said program, wherein said procedure is not analyzed by a compiler.

4. A method for optimizing the locking operations in a computer program as recited in claim 1, wherein the step of classifying locked variables as having a state of either “

global_escape”

or “

thread-local”

correctly handles exceptions in a program by selectively modifying information about precious connections of program variables.

5. A method for optimizing the locking operations in a computer program as recited in claim 1, wherein the optimization of locking operations are selectively performed in a run-time system implementing locking operations, using information about whether the variable being locked has a state of “

global_escape”

or “

thread-local”

, said information being generated by a compiler.

6. A method for opting the locking operations in a computer program as recited in claim 1, further comprising the step (c) of transforming the program by simplifying each comprehensive locking operation that is on a variable having a state of “

thread-local”

by removing mutual exclusion.

7. A method for optimizing the locking operations in a computer program as recited in claim 1, further comprising the steps:

(c) determining all actions of the program that require the side effects of some comprehensive locking operation to be performed to preserve the semantics of said program; and

(d) transforming said program by removing from said program any comprehensive locking operation that is on a variable having a state of “

thread-local”

, and whose side effects are not necessary, as determined in step (c), to preserve the correct semantics of said program.

10. A method for optimizing the locking operations in a computer program as recited in claim 7, wherein the optimization of simplifying comprehensive locking operations is selectively performed in a run-time system implementing locking operations, using information about the side effects of locking operations, said information being generated by a compiler.

8. A method for optimizing the locking operations in a computer program having locks in single threads and multiple threads, wherein some locking operation semantics are comprehensive locks with side effects, and other locking operation semantics are simple locks without side effects, while preserving the semantics of the program, said method comprising the steps:

(a) determining the scope of access of all locks involved in locking operations in a program; and

(b) transforming said program by removing all simple locking operations which are on objects that are accessed in only a single thread,

wherein the step of determining the scope of access of all locks involved in locking operations in a program is performed interprocedurally for the complete said program, where some procedures of sad program cannot or should not be analyzed by a compiler, and wherein the step of determining the scope of access of all locks interprocedurally for a computer program summarizes the effects of invoking a first procedure for different calling contexts using a single summary representation, further comprising the steps of;

(a) creating phantom nodes to represent the locks that are accessed in said first procedure, or any other procedure that is called, directly or indirectly, by said first procedure, but created neither in said first procedure nor in any procedure transitively invoked by said first procedure;

(b) using a return value, formal parameters, said phantom nodes, and locks accessed transitively within said first procedure to determine the effects of invoking said first procedure on the scope of access of all locks;

(c) summarizing said determined effects of invoking said first procedure on the scope of access of all locks in terms of said return value and said formal parameters of said first procedure;

(d) determining the scope of access of all locks at each calling context of said first procedure by matching the locks reachable from said return value or actual parameters of said first procedure with the locks reachable from said return value or said formal parameters, all at said calling context corresponding to the return value or the actual parameters of said first procedure.

9. A method for optimizing the locking operations in a computer program having locks in single threads and multiple threads, wherein some locking operation semantics are comprehensive locks with side effects, and other locking operation semantics are simple locks without side effects, while preserving the semantics of the program, said method comprising the steps:

(a) determining the scope of access of all locks involved in locking operations in a program;

(b) transforming said program by removing all simple locking operations which are on objects that are accessed in only a single thread;

(c) determining all actions of said program that require side effects of a comprehensive locking operation to be performed to preserve the semantics of the program; and

(d) transforming said program comprising the steps;

(i) simplifying each comprehensive locking operation by replacing with a more efficient operation all comprehensive locking operations that are on an object that is locked only within a single thread but whose side effects are necessary, as determined in step (c), to preserve the correct semantics of said program;

(ii) simplifying each comprehensive locking operation by replacing with a more efficient operation all comprehensive locking operations that are on an object that is locked in multiple threads, but whose side effects are not necessary, as determined in step (c), to preserve the correct semantics of said program; and

(iii) removing from the program any comprehensive locking operation that are on an object that is locked only within a single thread, and whose side effects are not necessary, as determined in step (c), to preserve the correct semantics of said program,

wherein the step of determining the scope of access of all locks involved in locking operations in a program is performed interprocedurally for the complete said program, where some procedures of said program cannot or should not be analyzed by a compiler.

11. A method for optimizing the locking operations in a computer program having locks in single threads and multiple threads, while preserving the semantics of the program, said method comprising the steps:

(a) determining the scope of access of all locks involved in locking operations in a program;

(b) determining all actions of said program that require the side effects of some comprehensive locking operation to be performed to preserve the semantics of said program; and

(c) transforming said program comprising the steps;

(i) simplifying each comprehensive locking operation by replacing with a more efficient operation all comprehensive locking operations that are on an object that is locked only within a single thread but whose side effects are necessary, as determined in step (b), to preserve the correct semantics of said program;

(ii) simplifying each comprehensive locking operation by replacing with a more efficient operation all comprehensive locking operations that are on an object that is locked in multiple threads, but whose side effects are not necessary, as determined in step (b), to preserve the correct semantics of said program; and

(iii) removing from the program any comprehensive locking operation that are on an object that is locked only within a single thread, and whose side effects are not necessary, as determined in step (b), to preserve the correct semantics of said program.

12. A method for optimizing the locking operations in a computer program having locking operations on variables, while preserving the semantics of the program, said method comprising the steps:

a. determining whether the variable being locked has a state of “

global_escape”

or “

thread-local”

for all locking operations in a program; and

b. transforming said program by simplifying all comprehensive locking operations that are on a variable having a state of “

thread-local”

by removing the locking, or primary, part of the locking operation.

13. A method for optimizing the locking operations in a computer program having locking operations on variables, a state of said variable being either “

global_escape”

or “

thread-local”

, while preserving the semantics of the program, said method comprising the steps;

(a) determining whether the variable being locked has a state of “

global_escape”

or “

thread-local”

for all locking operations in a program;

(b) determining all actions of said program that require the side effects of some comprehensive locking operation to be performed to preserve the semantics of the program; and

(c) transforming the program by removing from said program any comprehensive locking operation that is on a variable having a state of “

thread-local”

, and whose side effects are not necessary, as determined in step (b), to preserve the correct semantics of the program.

14. A method for optimizing the locking operations in a computer program having locking operations on variables, a state of said variable being either “

global_escape”

or “

thread-local”

, while preserving the semantics of the program, said method comprising the steps;

a. determining all actions of said program that require the side effects of some comprehensive locking operation on a variable to be performed to preserve the semantics of said program; and

b. transforming the program by simplifying all comprehensive locking operations with unnecessary side effects by removing the side effects part of the locking operation,

wherein said determining and transforming steps are independent of said state of said variable.

15. A machine readable medium containing code for optimizing the locking operations in a computer program having locking operations on variables, a state of said variable being either “

global_escape”

or “

thread-local”

, while preserving the semantics of the program, the code implementing the steps of;

(a) determining for all locking operations in a program whether the variable being locked is “

global_escape”

or “

thread-local”

; and

(b) transforming said program by removing all simple locking operations which are on variables having a state of “

thread-local”

.

16. A machine readable medium containing code for optimizing the locking operations in a computer program having locks in single treads and multiple threads, wherein some locking operation semantics are comprehensive locks with side effects, and other locking operation semantics are simple locks without side effects while preserving the semantics of the program, the code implementing the steps:

(a) determining the scope of access of all locks involved in locking operations in a program; and

(b) transform said program by removing all simple locking operations which are on objects that are accessed in only a single thread;

(c) determining all actions of said program that require side effects of a comprehensive locking operation to be performed to preserve the semantics of the program; and

(d) transforming said program comprising the steps;

(i) simplifying each comprehensive locking operation by replacing with a more efficient operation all comprehensive locking operations that are on an object that is locked only within a single thread but whose side effects are necessary, as determined in step (c), to preserve the correct semantics of said program;

(ii) simplifying each comprehensive locking operation by replacing with a more efficient operation all comprehensive locking operations that are on an object that is locked in multiple threads, but whose side effects are not necessary, as determined in step (c), to preserve the correct semantics of said program; and

(iii) removing from the program any comprehensive locking operation that are on an object that is locked only within a single thread, and whose side effects are not necessary, as determined in step (c), to preserve the correct semantics of said program.

17. A machine readable medium containing code for optimizing the locking operations in a computer program having locks in single threads and multiple threads, while preserving the semantics of the program, the code implementing the steps of:

(a) determining the scope of access of all locks involved in locking operations in a program; and

(b) determining all actions of said program that require the side effects of some comprehensive locking operation to be performed to preserve the semantics of said program;

(c) transforming said program comprising the steps;

(i) simplifying each comprehensive locking operation by replacing with a more efficient operation all comprehensive locking operations that are on an object that is locked only within a single thread but whose side effects are necessary, as determined in step) (b), to preserve the correct semantics of said program;

(ii) simplifying each comprehensive locking operation by replacing with a more efficient operation all comprehensive locking operations that are on an objects that is locked in multiple threads, but whose side effects are not necessary, as determined in step (b), to preserve the correct semantics of said program; and

(iii) removing from the program any comprehensive locking operation that are on an object that is locked only within a single thread, and whose side effects are not necessary, as determined in step (b), to preserve the correct semantics of said program.

18. A machine readable medium containing code for optimizing the locking operations in a computer program having locking operations on variables, a state of said variable being either “

global_escape”

or “

thread-local”

, while preserving the semantics of the program, the code implementing the steps of;

a. determining for all locking operations in a program whether the variable being locked is “

global_escape”

or “

thread-local”

; and

b. transforming said program by simplifying all comprehensive locking operations that are on a variable having a state of “

thread-local”

by removing the locking, or primary, part of the locking operation.

19. A machine readable medium containing code for optimizing the locking operations in a computer program having locking operations on variables, a state of said variable being either “

global_escape”

or “

thread-local”

, while preserving the semantics of the program, the code implementing the steps of;

(a) determining for all locking operations in a program whether the variable being locked is “

global_escape”

or “

thread-local”

;

(b) determining all actions of said program that require the side effects of some comprehensive locking operation to be performed to preserve the semantics of the program; and

(c) transforming the program by removing from said program any comprehensive locking operation that is on a variable having a state of “

thread-local”

, and whose side effects are not necessary, as determined in step (b), to preserve the correct semantics of the program.

20. A machine readable medium containing code for optimizing the locking operations in a computer program having locking operations on variables, a state of said variable being either “

global_escape”

or “

thread-local”

, while preserving the semantics of the program, said method comprising the steps;

a. determining all actions of said program that require the side effects of some comprehensive locking operation on a variable to be performed to preserve the semantics of said program; and

b. transforming the program by simplifying all comprehensive locking operations with unnecessary side effects by removing the side effects part of the locking operation,

wherein said determining and transforming steps are independent of said state of said variable.

21. A method for optimizing the locking operations in a computer program, said method comprising the steps:

(a) classifying a state of all variables involved in locking operations in the computer program as either “

global_escape”

or “

thread-local”

, wherein said classifying step uses information about connections in said program between objects and pointers; and

(b) transforming said program by removing all simple locking operations at run time which are on variables having a state of “

thread-local”

,

wherein the strict semantics of the computer program are preserved.