Compiler support for optimizing decomposed software transactional memory operations

• US 8,799,882 B2
• Filed: 03/23/2006
• Issued: 08/05/2014
• Est. Priority Date: 12/07/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Tarditi, David Read Jr., Harris, Timothy Lawrence, Plesko, Mark Ronald, Shinnar, Avraham E.
• Primary Examiner(s): Zhen, Li B
• Assistant Examiner(s): BODDEN, EVRAL E
• Application Number:
  US11/389,451
• Publication Number:
  US 20070169030A1
• Time in Patent Office: 3,057 Days
• Field of Search: None
• US Class Current: 717/151
• CPC Class Codes: G06F 8/443 Optimisation
• CPC Class Codes: G06F 9/466 Transaction processing

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 of compiling a program, the program including software transactional memory blocks and the method comprising:

by a computer, optimizing the program to create an optimized program containing software transactional memory instructions;

wherein optimizing the program comprises;

(a) inserting one or more word-based direct-access software transactional memory instructions at the software transactional memory blocks;

(b) replacing the one or more word-based direct-access software transactional memory instructions with decomposed software transactional memory instructions in the program at the software transactional memory blocks;

and

(c) performing optimizations on the program to create the optimized program, such that at least some of the optimizations are configured to operate specifically on the decomposed software transactional memory instructions;

wherein performing optimizations comprises performing a common subexpression elimination procedure which is modified to operate on decomposed software transactional memory instructions such that a decomposed software transactional memory instruction to open an object for read, that comprises a parameter that references the object, is eliminated which takes place after a decomposed software transactional memory instruction to open the object for update within a same transaction;

wherein the optimizations are performed within software transactional memory constraints, the software transactional memory constraints comprising data dependencies which are introduced into the decomposed software transactional memory instructions;

wherein the data dependencies enforce a call order based on output variables for at least some of the decomposed software transactional memory instructions being input variables for subsequent decomposed software transactional memory instructions; and

compiling the optimized program.

2. The method of claim 1, further comprising compiling the program into an intermediate representation, and wherein performing the optimizations comprises performing optimizations on the intermediate representation.

3. The method of claim 2, wherein the intermediate representation comprises representations of the decomposed software transactional memory instructions.

4. The method of claim 1, wherein the common subexpression elimination procedure is further modified such that redundant reads and writes to memory addresses and redundant logs for memory addresses within a transaction are removed.

5. The method of claim 4, wherein the common subexpression elimination procedure is further modified such that reads and writes in a first transaction are eliminated if they are made redundant by reads or writes in a second transaction, wherein the first transaction is nested within the second transaction.

6. The method of claim 3, wherein performing the optimizations comprises performing code motion optimizations.

7. The method of claim 3, wherein the software transactional memory constraints comprise constraints on a control flow graph of the program.

8. A compiler system for compiling a program containing software transactional memory blocks, the system comprising:

a processor;

a memory;

a first compilation module configured to represent source code of the program as an intermediate representation comprising, at least in part, representations of decomposed software transactional memory instructions, the decomposed software transactional memory instructions replacing at least one or more word-based software transactional memory instructions; and

an optimization module configured to optimize an intermediate representation for the source code of the program, the intermediate representation comprising, at least in part, decomposed software transactional memory instructions;

wherein the optimization module is further configured to perform a common subexpression elimination on the decomposed software transactional memory instructions, the common subexpression elimination comprising removing a redundant decomposed software transactional memory instruction to open an object for reading, that comprises a parameter that references the object, located after a decomposed software transactional memory instruction to open the object for updating within a same transaction;

wherein the representations of decomposed software transactional memory instructions are optimized at least in part according to software transactional memory optimization rules, the software transactional memory optimization rules comprising data dependencies in the decomposed software transactional memory instructions;

wherein the data dependencies enforce a call order based on output variables for at least some of the decomposed software transactional memory instructions being input variables for subsequent decomposed software transactional memory instructions; and

a second compilation module configured to compile the optimized intermediate representation into an executable form.

9. The system of claim 8, wherein the optimization module is further configured to:

remove redundant memory and log accesses for software transactional memory instructions; and

perform code motion optimizations on software transactional memory instructions.

10. One or more computer-readable storage memories or magnetic disk containing instructions which, when executed by a computer, cause the computer to perform a method for optimizing a program comprising decomposed direct-access software transactional memory instructions, the method comprising:

receiving an intermediate representation of the program comprising a control-flow graph, the intermediate representation including representations of the decomposed direct-access software transactional memory instructions located in the program in software transactional memory, blocks marked as atomic, wherein the decomposed direct-access software transactional memory, instructions replace at least one or more word-based software transactional memory instructions in one or more transactions that perform operations directly to a heap; and

applying optimization rules specific to decomposed direct-access software transactional memory instructions in order to optimize the representations of the decomposed direct-access software transactional memory instructions, wherein applying optimization rules comprises;

performing a modified common subexpression elimination on the decomposed direct-access software transactional memory instructions which eliminates read open instructions which occur after update open instructions, wherein a respective read open instruction of the eliminated read open instructions comprises a parameter that references an object and the respective read open instruction is subsumed by a respective update open instruction of the update open instructions;

wherein the modified common subexpression elimination procedure also eliminates read open instructions of the decomposed direct-access software transactional memory instructions in a first transaction which are made redundant and subsumed by read open instructions or update open instructions of the decomposed direct-access software transactional memory instructions in a second transaction, wherein the first transaction is nested within the second transaction;

removing redundant load-store elimination for decomposed direct-access software transactional memory instructions which comprise reads, writes, and entries to logs; and

performing code motion optimizations for decomposed direct-access software transactional memory instructions;

wherein the optimization rules comprise restrictions on the control-flow graph for the intermediate representation, the restrictions on the control-flow graph comprising data dependencies between decomposed direct-access software transactional memory instructions, wherein the data dependencies enforce a call order, at least for atomicity, which enforces that a location is open for reading when read or the location is open for updating when updated or a store is logged for the location when updated, the enforcement based on output variables for decomposed direct-access software transactional memory instructions being input variables for-subsequent decomposed direct access software transactional memory instructions.