Method and system using exceptions for code specialization in a computer architecture that supports transactions

A method and system uses exceptions for code specialization in a system that supports transactions. The method and system includes inserting one or more branchless instructions into a sequence of computer instructions. The branchless instructions include one or more instructions that are executable if a commonly occurring condition is satisfied and include one or more instructions that are configured to raise an exception if the commonly occurring condition is not satisfied.

BACKGROUND

Some computer architectures can support hardware and/or software transactional memory systems, such as Restricted Transactional Memory (RTM) systems and Software Transactional Memory (STM) systems. In transactional memory systems, computer instructions are permitted to execute concurrently, e.g. as single-threaded operations of a multi-threaded application. To do this, sequences of instructions in the computer program are defined as transactions, which can execute read and write instructions to shared memory independently of instructions running on other threads. The transactions can be defined by an interpreter, translator, program compiler, optimizer, or application programming interface (API), for example, depending on the type of transactional system. The transactional memory system includes control mechanisms to prevent concurrently executing instructions from accessing shared memory at the same time or in the wrong order. For example, a validation mechanism verifies that a transaction has successfully completed, e.g., without other program threads making changes to memory accessed by the transaction before the transaction completed. If the validation is successful, the results of the transaction are made permanent (e.g. by a “commit” operation).

If the transaction cannot be committed, an exception may be raised or the transaction may be aborted. If an exception is raised or the transaction is aborted, execution of the transaction can be rolled back to an earlier point in the program code, e.g., to a “checkpoint.” If the transaction is aborted, it may be re-executed from the beginning until it completes successfully, or simply terminated.

Computer program code can contain many specialized instructions, each of which may be designed to handle a particular condition that may be satisfied during execution of the program. Code specialization is a program optimization technique that attempts to, at runtime, optimize a computer program or portion thereof for a commonly occurring condition. However, code specialization typically adds branch instructions that can affect performance.

DETAILED DESCRIPTION OF THE DRAWINGS

References in the specification to “one embodiment”, “an embodiment”, “an example embodiment”, etc., indicate that the embodiment described may include a particular feature, structure, or characteristic, but every embodiment may not necessarily include the particular feature, structure, or characteristic. Moreover, such phrases are not necessarily referring to the same embodiment. Further, when a particular feature, structure, or characteristic is described in connection with an embodiment, it is submitted that it is within the knowledge of one skilled in the art to effect such feature, structure, or characteristic in connection with other embodiments whether or not explicitly described. Embodiments of the invention may be implemented in hardware, firmware, software, or any combination thereof. Embodiments of the invention implemented in a computer system may include one or more bus-based interconnects between components and/or one or more point-to-point interconnects between components. Embodiments of the invention may also be implemented as instructions carried by or stored on a transitory or non-transitory machine-readable medium, which may be read and executed by one or more processors. A machine-readable medium may be embodied as any device, mechanism or physical structure for storing or transmitting information in a form readable by a machine (e.g., a computing device). For example, a machine-readable medium may be embodied as read only memory (ROM); random access memory (RAM); magnetic disk storage media; optical storage media; flash memory devices; mini- or micro-SD cards, memory sticks, electrical signals, and others.

In the drawings, specific arrangements or orderings of schematic elements, such as those representing devices, modules, instruction blocks and data elements, may be shown for ease of description. However, it should be understood by those skilled in the art that the specific ordering or arrangement of the schematic elements in the drawings is not meant to imply that a particular order or sequence of processing, or separation of processes, is required. Further, the inclusion of a schematic element in a drawing is not meant to imply that such element is required in all embodiments or that the features represented by such element may not be included in or combined with other elements in some embodiments. In general, schematic elements used to represent instruction blocks may be implemented using any suitable form of machine-readable instruction, such as software or firmware applications, programs, functions, modules, routines, processes, procedures, plug-ins, applets, widgets, code fragments and/or others, and that each such instruction may be implemented using any suitable programming language, library, application programming interface (API), and/or other software development tools. For example, some embodiments may be implemented using Java, C++, and/or other programming languages. Similarly, schematic elements used to represent data or information may be implemented using any suitable electronic arrangement or structure, such as a register, data store, table, record, array, index, hash, map, tree, list, graph, file (of any file type), folder, directory, database, and/or others.

Referring now toFIG. 1, an illustrative computing device100includes at least one processor110, a memory120, an input/output (I/O) subsystem122, a storage device124, and one or more peripheral devices140. The processor110supports a transactional memory system222as shown inFIG. 2. As described in more detail below, computer program code is analyzed during execution. A specializer228interfaces with the transactional memory system222to specialize code regions or transactions for one or more commonly occurring conditions. Rather than adding branch instructions to the program code, as is often done when conventional code specialization techniques are employed, the specializer228inserts one or more branchless instructions in the code region or transaction that are configured to utilize the exception handling features of the transactional memory system222. More specifically, the instruction(s) inserted by the specializer228are configured to raise an exception if a commonly occurring condition is not satisfied. In this way, the normal program flow is allowed to continue uninterrupted, and without branching, in response to the commonly occurring condition being satisfied. The computing device100may be embodied in or as any type of computing device, such as, for example, a desktop computer system, a laptop or tablet computer system, a server, an enterprise computer system, a network of computers, a handheld computing device, or other electronic device depending on the particular application.

The illustrative processor110includes multiple processor cores or logical sections of a single core,112,114,116, which are referred to herein simply as “cores” for ease of description. One or more of the cores112,114,116can be configured to process multi-threaded computer programs. The cores112,114,116include or are communicatively coupled to one or more cache memory118. The cache118may be utilized to temporarily store data and/or instructions during operation of the specializer228and/or other components of the computing device100.

In addition to the cache memory118, the processor110and/or its cores112,114,116include, or are otherwise communicatively coupled to, the memory120. Portions of the memory120may be embodied as any type of suitable memory device, such as a dynamic random access memory device (DRAM), synchronous dynamic random access memory device (SDRAM), double-data rate dynamic random access memory device (DDR SDRAM) and/or other volatile memory devices.

The processor110is also communicatively coupled to the I/O subsystem122. Although not specifically shown, the I/O subsystem122typically includes a memory controller (e.g., a memory controller hub (MCH) or northbridge), an input/output controller (e.g., an input/output controller hub (ICH) or southbridge), and a firmware device. Of course, in other embodiments, I/O subsystems having other configurations may be used. For example, in some embodiments, the I/O subsystem122may form a portion of a system-on-a-chip (SoC) and be incorporated, along with the processor110and other components of the computing device100, on a single integrated circuit chip. As such, it will be appreciated that each component of the I/O subsystem122may be located on a common integrated circuit chip in some embodiments.

The I/O subsystem122is communicatively coupled to one or more storage devices124. Portions of the storage124may be embodied as any suitable device for storing data and/or instructions, such as disk storage (e.g. hard disks), memory cards, memory sticks, and/or others. In some embodiments, an operating system (O/S)126, one or more sequences of program code (e.g., application code)128, a program compiler130and/or a database management system (DBMS)132may be embodied in the storage124. During execution, portions of the O/S126, code128, compiler130and/or DBMS132may be loaded into the memory120and/or the cache118, for faster processing or other reasons.

The I/O subsystem122may be communicatively coupled to one or more peripheral devices140. The peripheral device(s)140may include one or more network interfaces, graphics and/or video adaptors, keyboard, touchscreens, displays, printers, data storage devices, and/or other peripheral devices, depending upon, for example, the intended use of the computing device100. Further, it should be appreciated that the computing device100may include other components, sub-components, and devices not illustrated inFIG. 1for clarity of the description.

In general, the components of the computing device100are communicatively coupled as shown inFIG. 1, by one or more signal paths, which are represented schematically as double-headed arrows. Such signal paths may be embodied as any type of wired or wireless signal paths capable of facilitating communication between the respective devices. For example, the signal paths may be embodied as any number of wires, printed circuit board traces, via, bus, point-to-point interconnects, intervening devices, and/or the like. Referring now toFIG. 2, the illustrative processor core112includes a fetch unit210, a logic unit212, one or more registers214, an execution unit216, and a retirement unit218. While not specifically shown, it should be understood that one or more of the cores114,116may have the same or similar configuration as the core112. Each of the fetch unit210, logic unit212, registers214, execution unit216, and retirement unit218may be embodied as computer circuitry, e.g. as electronic components of a central processing unit of the core112.

During operation of the computing device100, the fetch unit210obtains instructions to be executed by the core112from the cache118, the memory120, and/or the storage124. The logic unit212processes the instructions and converts them to a form that can be executed by the execution unit216(e.g. machine-level instructions). In accordance with the design of the transactional memory system222, after instructions are successfully executed by the execution unit216, the retirement unit218may commit and then retire the instructions (by de-allocating registers or updating the processor state, for example). The registers214may be used to store values that are involved in the processing and/or execution of the instructions, such as data values, pointer addresses, and/or trip counts. In general, the translator220is configured to translate programmer-accessible computer instructions to an executable form that is compatible with the processor architecture. In the illustrative embodiments, the translator220adapts program code to run on a computer architecture that supports the transactional memory system222. In other embodiments, which may include, for example, software transactional memory systems, the translator220may be embodied as a compiler, application programming interface (API), database management system, or the like, depending on the specific implementation.

The translator220includes an optimizer226. Generally speaking, the optimizer226is configured to minimize or maximize one or more attributes of a computer program during execution of the program. As should be understood by those skilled in the art, there are many types of optimization that can be used, depending on the requirements of a particular application or system design. For example, some optimizers examine the program code to see if any sequences of computer instructions, in particular frequently-executed sequences, can be replaced with less code.

In the illustrative embodiments, the optimizer226identifies regions of code that require access to shared memory (e.g., code regions that include load or store instructions), and defines the regions of code as transactions. The optimizer226inserts checkpoint and commit instructions into the code regions as needed to define the transactions. In some embodiments, a binary translation dynamic optimizer, or similar device configured to optimize sequences of instructions as encountered and then cache the optimized instructions, may be used. In other embodiments, a static optimizer may be used.

The optimizer226may include the specializer228as a subcomponent, or the specializer228may be embodied as a separate component of the translator220as shown. The specializer228is configured to optimize a sequence of computer instructions for a commonly occurring condition. Whether or not a particular condition is considered to be commonly occurring may be determined in advance (e.g. by the programmer), or “on the fly” (e.g. as a result of previous executions of the computer instructions). Some examples of commonly occurring conditions for which it may be desirable to specialize computer instructions include runtime disambiguation checks (e.g., where code is specialized for the occurrence of a specific alias or no alias), value specialization (e.g., where code is specialized for the occurrence of a frequently occurring value of a variable, such as NULL), and loop multiversioning (e.g., where code is specialized for the occurrence of a particular loop trip count).

As described below in connection withFIGS. 3-6, the illustrative specializer228is configured to use the features of the transactional memory system222to optimize a sequence of computer instructions for a commonly occurring condition without introducing any new branch instructions.

The illustrative transactional memory system222is embodied as a hardware system that supports transactions, such as a restricted transactional memory (RTM) system. However, it should be understood that a software transactional memory system (STM) or other system that implicitly transfers control on exceptions may be used in other embodiments. The transactional memory system222includes checkpointing logic230, transaction execution semantics232, overflow logic234, and an exception handler236.

The checkpointing logic230includes computer instructions that are configured to interface with the optimizer226to establish the checkpoints and define code regions or transactions in a sequence of computer instructions. In addition, the checkpointing logic230may specify the action(s) to be taken in response to a checkpoint instruction. For example, the checkpointing logic222may initiate the storing of data relating to a particular state of the core112or other component of the computing device100in response to a checkpoint instruction.

The transaction execution semantics232include the semantics (e.g. instructions or code libraries) that can be used in program code to invoke and utilize the features of the transactional memory system222. For example, the transaction execution semantics232enable the implicit transfer of control (e.g. to an interpreter or to native execution, depending on the system design) on exceptions. In the illustrative embodiment, the transaction execution semantics232include checkpoint, rollback, and commit semantics, as well as semantics for Boolean or bitwise logic, arithmetic, and invoking the exception handler236.

The overflow logic234includes logic configured to specify action(s) to be taken if an overflow occurs (e.g., a value exceeds the maximum size that can be stored in the cache118or the memory120). For example, the overflow logic234may store data relating to the state of the computing device100or a component thereof in response to an overflow event.

The exception handler236includes logic configured to determine action(s) to be taken if an exception is raised by an instruction obtained by the fetch unit210. For example, the exception handler236may include logic configured to roll back the program execution to a previous checkpoint in a sequence of instructions and continue execution from the checkpoint, or to abort a transaction.

The arithmetic and logic unit (ALU)224includes an arithmetic unit240and a logic unit242. The arithmetic unit240is configured to handle arithmetic operations such as add, subtract, divide, multiply, and/or others. The logic unit242is configured to handle Boolean and/or bitwise logic operations such as and, or, and exclusive-or operations.

Referring now toFIG. 3, in operation, a sequence of computer instructions322is input to the translator220. The instructions322are referred to as “unspecialized” code because they have not yet been processed by the optimizer226and/or specializer228. After processing by the translator220(including the optimizer226and the specializer228) as described herein, an optimized and/or specialized version330of the instructions322is produced. The optimized and/or specialized instructions330may be stored in the cache118until execution by the execution unit216.

Referring now toFIG. 4, an illustrative method400executable by the code specializer228is shown. At block410, the method400obtains (e.g., from the cache118or the memory120) one or more instructions that have been defined as a code region or transaction by the optimizer226. For purposes of this disclosure, a “code region” may include a sequence of computer instructions determined by the translator220(e.g., the optimizer226) to include at least one transaction. In other words, in some embodiments, a code region may include one or more transactions, while in other embodiments, a code region may include a single transaction.

In the illustrative embodiments, transactions are defined by a checkpoint instruction followed by a commit instruction. At block412, the method400analyzes each transaction in the code region to determine which of the one or more instructions in the transaction are desired to be executable in response to a commonly occurring condition. To make this determination, the method400may consider whether there are certain instructions that are only executed if the commonly occurring condition is satisfied. Alternatively or in addition, the method400may determine that although all or multiple of the instructions in the transaction may be executed in response to the commonly occurring condition, it may be desirable to execute only certain of those instructions in response to the commonly occurring condition. This may be the case, for example, when portions of the code are optimized for different conditions.

At block414, the method400inserts one or more branchless instructions into the code region. The branchless instructions are configured to preserve the normal program flow (e.g., without branching) for the commonly occurring condition. In the illustrative embodiments, the branchless instruction(s) include at least one instruction that is configured to raise an exception (and thereby invoke the exception handler236) in response to the commonly occurring condition not being satisfied. The branchless instructions may include any form of non-branching logical and/or arithmetic operations that may be supported by the ALU224. In other words, no compare and branch instructions are inserted into the code region as a result of block414.

At block416, the method400identifies any instructions in the code region that are not desired to be executable in response to the commonly occurring condition, and interfaces with the exception handler236to associate those instructions with an exception handling mechanism (e.g., a rollback or abort instruction), as may be appropriate for a particular application or design. In transactional memory systems and other systems that implicitly transfer control on exceptions, the transfer of control and execution of the instructions that are not executable in response to the commonly occurring condition is handled implicitly by the exception handler236.

At block418, the method400removes the instructions that are not desired to be executable in response to the commonly occurring condition (e.g., the instructions associated with the exception at block416), from the code region. This can be done, for example, by inserting comment brackets around the instructions. The instructions may be removed entirely (e.g. so that the program aborts if an uncommonly occurring condition is encountered) or may be moved to another location in the sequential listing of the program code. In this way, a code region or transaction can be specialized so that it only contains code that is directed to the commonly occurring condition. Moreover, if the code that is desired to be executable in response to the commonly occurring condition has been optimized, the code region may only contain optimized code. Any code that is directed to the handling of uncommonly occurring conditions, or which is not desired to be executable in response to the commonly occurring condition, may remain un-optimized, or may be separately processed by the optimizer226.

Referring now toFIG. 5, an example of a sequence of computer instructions522that has been specialized using a conventional code specialization technique is shown. The instructions522include a code region532. Although not illustrated, it should be understood that the code522may include other computer instructions and/or code regions as well.

After processing using a conventional code specialization technique, the code region532is defined by a checkpoint instruction540followed sequentially by a commit instruction550.

Between the checkpoint instruction540and the commit instruction550, compare and branch instructions542have been added to the code region532. The compare and branch instructions542compare the data stored in two registers, r1and r2. If the values stored in r1and r2are equal, the program execution skips over the instructions544, which are configured to be executed if the commonly occurring condition is not satisfied, as indicated by the label, “Unoptimized version.”

The program flow jumps to the “Optimized version” label and continues executing from there, the instructions546, which are configured to be executed if the commonly occurring condition is satisfied. Once the instructions546have finished executing, the program flow proceeds to the commit instruction550.

If the results of the compare and branch instructions542indicate that the data stored in r1and r2are not equal, then the program flow proceeds to execute the instructions544. When the instructions544are finished executing, the program flow jumps to the Fallthrough label548. As can be seen from the above example, branching takes place both when the commonly occurring condition (e.g., r1equals r2) is satisfied and when an uncommonly occurring condition (e.g., r1does not equal r2) is satisfied.

Referring now toFIG. 6, a sequence of computer instructions622comprising a code region632is shown after having been processed by the specializer228as disclosed herein. The remainder of the sequence of instructions (e.g. the portion of the sequence of instructions622outside of the code region632) may remain unaffected by the processing of the code region632, or may be altered by the processing of the code region632. For example, instructions configured to be executed in response to the occurrence of an uncommon condition may be removed from the code region632and placed elsewhere in the sequence of instructions622.

The specialized code region632does not include any compare and branch instructions. The specialized code region632is defined by a checkpoint instruction640and a commit instruction650. Between the checkpoint instruction640and the commit instruction650, a sequence of exception generating instructions642,644,646is inserted into the code region632. In the illustrated example, the exception generating instructions642,644,646include a Boolean or bitwise logic instruction (642), an arithmetic function (644), and an exception raising instruction646.

More specifically, in the illustrated example, an exclusive-or (XOR) function is used to compare data stored in the registers r1and r2. If the data stored in r1and r2are equal, the result of the XOR function will be zero and the value zero will be stored in r1. An addition function (e.g., ADD) adds the value of r1to the maximum allowable integer (e.g., $INT_MAX). If the value of r1is anything other than zero, an overflow flag will be set because the sum of r1and $INT_MAX will be greater than the maximum allowable integer.

An exception raising instruction (e.g., INTO) raises an exception, invoking the exception handler236, if the overflow flag is set. If the overflow flag is not set, then the data stored in the registers r1and r2are equal and the program flow continues uninterrupted and without branching, to the sequence of instructions that are optimized for the commonly occurring condition (which is, in this example, that r1and r2are equal). For example, in some embodiments, an NOP (no operation performed) instruction may be issued if the overflow flag is not set. Following execution of the instructions for the commonly occurring condition, the program flow proceeds to the commit instruction650.

If the overflow flag is set, thereby indicating that an uncommonly occurring condition has been satisfied, the exception handler236may be configured to roll back the transaction and/or redirect the program flow to the location of the instructions to be executed in the case of an uncommonly occurring condition, or may abort the transaction.

While the disclosure has been illustrated and described in detail in the drawings and foregoing description, such an illustration and description is to be considered as exemplary and not restrictive in character, it being understood that only illustrative embodiments have been shown and described and that all changes and modifications that come within the spirit of the disclosure are desired to be protected. Further, while aspects of the present disclosure have been described in the context of a hardware-based transactional memory system, it will be understood that the various aspects have other applications, for example, any application in which it is desired to specialize program code for one or more commonly occurring conditions where the features of a transaction memory system, or other system that implicitly transfers control on exceptions, are available. (e.g., hardware and/or software-based transactional systems). Such applications may include, for example, compilers, system or application software, and/or database systems.