Efficient placement of software transactional memory operations around procedure calls
First Claim
1. A method for compiling an efficient program comprising atomic blocks utilizing software transactional memory operations, the method comprising:
- identifying one or more procedures in the program comprising atomic blocks 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;
wherein the cloned version relies on the software transactional memory operations which are able to be optimized outside of the procedure being performed before the cloned version of the procedure is called;
wherein the one or more procedures further comprise arguments and at least one software transactional memory operation that gives a result;
wherein the creating further comprises creating the cloned version which takes an instance of the result given by the at least one software transactional memory operation of the one or more procedures as an input variable in addition to the arguments of the one or more procedures, and replacing occurrences of the at least one software transactional memory operation with the input variable taken by the cloned version;
moving the one or more software transactional memory operations which are able to be optimized outside of the one or more procedures to one or more call sites for the one or more procedures;
replacing calls to each of the one or more procedures with calls to its cloned version; and
optimizing the program by removing redundancies amongst the moved one or more software transactional memory operations.
2 Assignments
0 Petitions
Accused Products
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 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.
92 Citations
13 Claims
-
1. A method for compiling an efficient program comprising atomic blocks utilizing software transactional memory operations, the method comprising:
-
identifying one or more procedures in the program comprising atomic blocks 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; wherein the cloned version relies on the software transactional memory operations which are able to be optimized outside of the procedure being performed before the cloned version of the procedure is called; wherein the one or more procedures further comprise arguments and at least one software transactional memory operation that gives a result; wherein the creating further comprises creating the cloned version which takes an instance of the result given by the at least one software transactional memory operation of the one or more procedures as an input variable in addition to the arguments of the one or more procedures, and replacing occurrences of the at least one software transactional memory operation with the input variable taken by the cloned version; moving the one or more software transactional memory operations which are able to be optimized outside of the one or more procedures to one or more call sites for the one or more procedures; replacing calls to each of the one or more procedures with calls to its cloned version; and optimizing the program by removing redundancies amongst the moved one or more software transactional memory operations. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A compiler system for removing redundant instructions from a program comprising atomic blocks containing software transactional memory operations, the compiler system comprising a computer executing an optimization module, the optimization module configured to:
-
locate methods in the program comprising atomic blocks 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 and move the hoisted software transactional memory operations to one or more call sites for 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; optimize the program, including the software transactional memory operations by removing redundancies amongst the hoisted software transactional memory operations; wherein the specialized methods rely on the software transactional memory operations which are able to be hoisted outside of the methods being performed before the specialized methods are called; wherein the methods in the program comprising atomic blocks which contain software transactional memory operations which are able to be hoisted outside of the methods comprise arguments and at least one operation to acquire a transaction manager that gives the transaction manager as a result; and wherein the specialized methods take the resulting transaction manager given by the at least one operation to acquire the transaction manager as an input variable in addition to the arguments of the methods which comprise atomic blocks which contain software transactional memory operations, and replacing occurrences of the at least one operation to acquire the transaction manager with the input variable taken by the specialized methods. - View Dependent Claims (9, 10, 11)
-
-
12. One or more computer-readable storage memory or magnetic disks containing instructions which, when executed by a computer, cause the computer to perform a method for optimizing a program comprising atomic blocks with software transactional memory instructions, the method comprising:
-
receiving an intermediate representation of the program comprising atomic blocks, 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 rely on the software transactional memory instructions which can be optimized outside of the procedures being performed before the created procedures are called; wherein procedures which comprise software transactional memory instructions which can be optimized outside of the procedures further comprise arguments and instructions to acquire a transaction manager give the transaction manager as a result; cloning procedures comprising cloning the procedures to create procedures which take the resulting transaction manager given by the instructions to acquire the transaction manager of the cloned procedures as an input variable in addition to the arguments of the cloned procedures which comprise software transactional memory instructions which can be optimized outside of the procedures, and replacing occurrences of the instruction to acquire the transaction manager with the input variable taken by the created procedures; moving the software transactional memory instructions which can be optimized outside of the procedures which comprise the instruction to acquire a transaction manager to call sites for the procedures; 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; optimizing the intermediate representation of the program by removing redundancies amongst the moved one or more software transactional memory operations which can be optimized outside of the procedures; and wherein optimizing the intermediate representation of the program comprises performing common subexpression elimination on the intermediate representation of the program. - View Dependent Claims (13)
-
Specification