Efficient placement of software transactional memory operations around procedure calls

• US 20070169031A1
• Filed: 03/23/2006
• Published: 07/19/2007
• Est. Priority Date: 12/07/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Harris, Timothy
• Granted Patent: US 8,266,609 B2
• Time in Patent Office: Days
• US Class Current: 717/140
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 8/4435 Detection or removal of dead or redundant code
• CPC Class Codes: G06F 8/4441 Reducing the execution time required by the program code
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30047 Prefetch instructions; cache control instructions
• CPC Class Codes: G06F 9/30181 Instruction operation extension or modification
• CPC Class Codes: G06F 9/3802 Instruction prefetching
• CPC Class Codes: G06F 9/45525 Optimisation or modification within the same instruction set architecture, e.g. HP Dynamo
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/467 Transactional memory G06F9/528 takes precedence

Abstract

A software transactional memory system is described which utilizes decomposed software transactional memory instructions as well as runtime optimizations to achieve efficient performance. The decomposed instructions allow a compiler with knowledge of the instruction semantics to perform optimizations which would be unavailable on traditional software transactional memory systems. Additionally, high-level software transactional memory optimizations are performed such as code movement around procedure calls, addition of operations to provide strong atomicity, removal of unnecessary read-to-update upgrades, and removal of operations for newly-allocated objects. During execution, multi-use header words for objects are extended to provide for per-object housekeeping, as well as fast snapshots which illustrate changes to objects. Additionally, entries to software transactional memory logs are filtered using an associative table during execution, preventing needless writes to the logs. Finally a garbage collector with knowledge of the software transactional memory system compacts software transactional memory logs during garbage collection.

Claims

1. A method for compiling an efficient program utilizing software transactional memory operations, the method comprising:

identifying one or more procedures in the program which comprise one or more software transactional memory operations which are able to be optimized outside of the procedure;

creating, for each of the one or more procedures, a cloned version of the procedure which allows the calling of the software transactional memory operations which are able to be optimized outside of the cloned version;

moving the one or more software transactional memory operations which are able to be optimized outside of the procedures; and

replacing calls to each of the one or more procedures with calls to its cloned version.

2. The method of claim 1, further comprising optimizing the program by removing redundancies amongst the one or more software transactional memory operations which are able to be optimized.

3. The method of claim 2, wherein optimizing the program comprises performing common subexpression elimination on the program.

4. The method of claim 2, wherein the one or more software transactional memory operations which are able to be optimized comprise operations to get a transaction manager.

5. The method of claim 4, wherein cloned versions of procedures comprising operations to get a transaction manager comprise procedures which take instances of a transaction manager as inputs.

6. The method of claim 2, wherein the one or more software transactional memory operations which are able to be optimized comprise operations to open references for reading or update, the references being passed to the procedures as inputs.

7. The method of claim 6, wherein cloned versions of procedures comprising operations to open references for reading or update comprise procedures which rely on the references being opened before the procedures are called.

8. The method of claim 7, wherein cloned versions of procedures rely on a subset of all input references being opened.

9. The method of claim 7, wherein creating cloned versions of procedures comprising operations to open references for reading or update comprises performing a backwards dataflow analysis to determine which procedures comprise operations to open references for reading or update for references which are known at the beginnings of the procedures.

10. The method of claim 1, wherein at least one of the one or more software transactional memory operations which are able to be optimized outside of the procedure is not guaranteed to be performed in every possible execution of a procedure which contains it.

11. A compiler system for removing redundant instructions from a program containing software transactional memory operations, the system comprising an optimization module, the optimization module configured to:

locate methods in the program which contain software transactional memory operations which are able to be hoisted outside of the methods;

hoist the software transactional memory operations which are able to be hoisted out of the methods;

replace calls to the located methods with calls to specialized methods which do not contain the software transactional memory operations which are able to be hoisted; and

optimize the program, including the software transactional memory operations.

12. The compiler system of claim 11, wherein the optimization module is configured to locate methods in the program which contain software transactional memory operations which are able to be hoisted outside of the methods by locating methods which contain a software transactional memory operation to acquire a transaction manager.

13. The compiler system of claim 12, wherein the optimization module is configured to replace calls to the located methods with calls to specialized methods which take a transaction manager as an input variable.

14. The compiler system of claim 11, wherein the optimization module is configured to locate methods in the program which contain software transactional memory operations which are able to be hoisted outside of the methods by locating methods which contain one or more software transactional memory operations which open input variables for reading or update.

15. The compiler system of claim 14, wherein the optimization module is configured to replace calls to the located methods with calls to specialized methods which assume that one or more input variables have been opened before the method is called.

16. The compiler system of claim 14, locating methods which contain one or more software transactional memory operations which open input variables for reading or update by performing a backward dataflow analysis on the program.

17. One or more computer-readable media containing instructions which, when executed by a computer, cause the computer to perform a method for optimizing a program comprising software transactional memory instructions, the method comprising:

receiving an intermediate representation of the program, the intermediate representation including representations of procedures which comprise software transactional memory instructions which can be optimized outside of the procedures;

cloning procedures which comprise software transactional memory instructions which can be optimized outside of the procedures to create procedures which relies on the software transactional memory instructions which can be optimized outside of the procedures being performed before the procedures are called; and

moving the software transactional memory instructions which can be optimized outside of the procedures to call sites for the procedures.

18. The computer-readable media of claim 17, wherein:

procedures which comprise software transactional memory instructions which can be optimized outside of the procedures comprise procedures comprising instructions to acquire a transaction manager; and

cloning procedures comprises cloning the procedures to create procedures which take a transaction manager as an input variable.

19. The computer-readable media of claim 17, wherein:

procedures which comprise software transactional memory instructions which can be optimized outside of the procedures comprise procedures comprising instructions to open input references to the procedures for reading or update; and

cloning procedures comprises cloning the procedures to create procedures which assume that one or more of the input references are already open before the procedure begins.

20. The computer-readable media of claim 17, wherein at least one of the one or more software transactional memory instructions which can be optimized outside of the procedures is not guaranteed to be performed in every possible execution of a procedure which contains it.