Compiler support for optimizing decomposed software transactional memory operations

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.

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.