US10514926B2

US10514926B2 - Method and apparatus to allow early dependency resolution and data forwarding in a microprocessor

Info

Publication number: US10514926B2
Application number: US14/211,476
Authority: US
Inventors: Mohammad A. Abdallah
Original assignee: Intel Corp
Current assignee: Intel Corp
Priority date: 2013-03-15
Filing date: 2014-03-14
Publication date: 2019-12-24
Also published as: WO2014151652A1; TW201502981A; US11294680B2; US20140281410A1; TWI529621B; US20200174792A1

Abstract

A microprocessor implemented method for performing early dependency resolution and data forwarding is disclosed. The method comprises mapping a plurality of instructions in a guest address space into a corresponding plurality of instructions in a native address space. For each current guest branch instruction in the native address space fetched during execution, performing (a) determining a youngest prior guest branch target stored in a guest branch target register, wherein the guest branch register is operable to speculatively store a plurality of prior guest branch targets corresponding to prior guest branch instructions; (b) determining a current branch target for a respective current guest branch instruction by adding an offset value for the respective current guest branch instruction to the youngest prior guest branch target; and (c) creating an entry in the guest branch target register for the current branch target.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims the benefit of U.S. Provisional Application No. 61/792,676, filed Mar. 15, 2013, which is hereby incorporated by reference.

This application is related to U.S. patent application Ser. No. 13/359,767, filed Jan. 27, 2012 (now U.S. Pat. No. 9,710,387, issued Jul. 18, 2017), titled “GUEST INSTRUCTION TO NATIVE INSTRUCTION RANGE BASED MAPPING USING A CONVERSION LOOK ASIDE BUFFER OF A PROCESSOR,” which is hereby incorporated by reference.

This application is related to U.S. patent application Ser. No. 14/211,655, filed Mar. 14, 2014 (now U.S. Pat. No. 10,228,950, issued Mar. 12, 2019), titled “METHOD AND APPARATUS FOR GUEST RETURN ADDRESS STACK EMULATION SUPPORTING SPECULATION,” which is hereby incorporated by reference.

FIELD OF THE INVENTION

Embodiments according to the present invention generally relate to microprocessor architecture and more particularly to the architecture for out-of-order microprocessors.

BACKGROUND OF THE INVENTION

In an Out-Of-Order (“OOO”) microprocessor, instructions are allowed to issue out of their program order. However, in most cases, they are required to retire from the machine in order. Further, memory operations in the machine, regardless of the issue order, need to acquire and update memory status in program order. These diverging ordering behaviors give rise to problems at several locations in a micro-architecture.

For example, in an OOO microprocessor, the instructions executing out of order need to preserve their data dependence constraints. Because instructions may finish in an arbitrary order, the architectural register file cannot be modified by the instructions as they finish because it would make it difficult to restore their values accurately in the event of an exception or an interrupt. To achieve high performance, register renaming is commonly used with the temporary register storage to allow the OOO processor to resolve false dependencies between instructions. Hence, every instruction that enters the pipeline is provided a temporary register where it can save its result. The temporary registers are eventually written into the architectural register file in program order. Thus, even though instructions are being executed out of order, the contents of the architectural register files change as though they were being executed in program order.

The architectural register file is typically maintained in the back-end of the OOO processor. As a result of using temporary register storage along with register renaming, instructions with write-after-write (WAW) and write-after-read (WAR) hazards can be issued out-of-order in conventional OOO processors.

There are cases in OOO microprocessor design where a value generated from a General Purpose Register (“GPR”), an architectural register also maintained at the back-end of the machine, could determine the control flow of the program (in the case of indirect branches), or could cause instructions or data values to be treated differently. In conventional OOO processors, instructions following a state producing instruction involving a GPR need to wait for the state producing instruction to get committed before being able to use its value. As a result, the process of executing instructions or even fetching new instructions becomes a serial process dependent on the execution of the state producing instruction getting committed to a quiescent state, which is visible to every microprocessor module that is affected by it. This serialization can introduce significant delays in the pipeline and diminish microprocessor performance.

BRIEF SUMMARY OF THE INVENTION

Accordingly, a need exists for a method and apparatus for a more efficient and flexible OOO processor architecture that is configured to mitigate the performance limiting issues associated with execution of state producing instructions, e.g., branches by exercising early data forwarding.

In one embodiment of the present invention, registers are provided at the front-end of the machine, e.g., towards the fetch stage that speculatively hold copies of the results of state producing instructions and make them available to instructions dependent on the state producing instruction without needing to wait for the state producing instructions to be committed to a quiescent state. This allows data to be speculatively made available at the early stage of the pipeline, e.g., at the fetch stage to the other instructions and prevents problems associated with serialization.

In one embodiment of the present invention, in an emulated architecture, branch targets that are required to allow guest branch instructions (being executed in native space) to compute their targets are stored speculatively in a guest branch target register at the front-end of the machine. In one embodiment, guest branch instructions write to the guest-target to this register if they are predicted to be taken. Subsequent instructions that require the guest-target to calculate either their own target (in the case of a branch instruction) or to use it as an operand can simply access it from the guest branch target register at the front-end of the machine instead of needing to wait for the earlier branch to execute and commit its values at the back-end of the machine. Accordingly, embodiments of the present invention allow for speculative maintenance of structures aiding in resolving data dependencies in early stages of a microprocessor. This is a significant advantage over conventional OOO processors wherein similar data forwarding cases are handled in the execution unit, which resides in the back-end of the machine.

In one embodiment, a microprocessor implemented method for performing early dependency resolution and data forwarding for instructions in a native space of an emulated architecture referencing a guest address is presented. The method comprises mapping a plurality of instructions in a guest address space into a corresponding plurality of instructions in a native address space. For each current guest branch instruction in the native address space fetched during execution, performing (a) determining a youngest prior guest branch target stored in a guest branch target register, wherein the guest branch register is operable to speculatively store a plurality of prior guest branch targets corresponding to prior guest branch instructions; (b) determining a current branch target for a respective current guest branch instruction by adding an offset value for the respective current guest branch instruction to the youngest prior guest branch target; and (c) creating an entry in the guest branch target register for the current branch target.

In another embodiment, a processor unit configured for performing early dependency resolution and data forwarding for instructions in a native space of an emulated architecture referencing a guest address is presented. The method comprises mapping a plurality of instructions in a guest address space into a corresponding plurality of instructions in a native address space. For each current guest branch instruction in the native address space fetched during execution, performing: (a) determining a youngest prior guest branch target stored in a guest branch target register, wherein the guest branch register is operable to speculatively store a plurality of prior guest branch targets corresponding to prior guest branch instructions; (b) determining a current branch target for a respective current guest branch instruction by adding an offset value for the respective current guest branch instruction to the youngest prior guest branch target; and (c) creating an entry in the guest branch target register for the current branch target.

In a different embodiment, an apparatus configured to perform early dependency resolution and data forwarding for instructions in a native space of an emulated architecture referencing a guest address is disclosed. The apparatus comprises a memory and a processor communicatively coupled to the memory, wherein the processor is configured to process instructions out of order, and further wherein the processor is configured to perform a method. The method comprises mapping a plurality of instructions in a guest address space into a corresponding plurality of instructions in a native address space. For each current guest branch instruction in the native address space fetched during execution, performing: (a) determining a youngest prior guest branch target stored in a guest branch target register, wherein the guest branch register is operable to speculatively store a plurality of prior guest branch targets corresponding to prior guest branch instructions; (b) determining a current branch target for a respective current guest branch instruction by adding an offset value for the respective current guest branch instruction to the youngest prior guest branch target; and (c) creating an entry in the guest branch target register for the current branch target.

The following detailed description together with the accompanying drawings will provide a better understanding of the nature and advantages of the present invention.

BRIEF DESCRIPTION OF THE DRAWINGS

Embodiments of the present invention are illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings and in which like reference numerals refer to similar elements.

FIG. 1 is an exemplary computer system in accordance with embodiments of the present invention.

FIG. 2 is an exemplary diagram of pipe stages of a pipeline for an out of order microprocessor on which embodiments of the present invention can be implemented in accordance with one embodiment of the present invention.

FIG. 3 illustrates an example of maintaining data for a general purpose register (GPR) speculatively in the front-end of the pipeline in accordance with an embodiment of the present invention.

FIG. 4 illustrates the manner in which far branches are processed in an emulated architecture by maintaining registers at the front-end of the pipeline in accordance with one embodiment of the present invention.

FIG. 5 illustrates the manner in which the pipelined guest branch target register is updated using a prior branch target in accordance with one embodiment of the present invention.

FIG. 6 illustrates the manner in which each instruction fetched is tagged with information about the last branch instruction that updated the guest branch target register in accordance with one embodiment of the present invention.

FIG. 7 depicts a flowchart 700 for an exemplary computer controlled process for performing early dependency resolution and data forwarding for instructions in the native space of an emulated architecture referencing a guest address in accordance with embodiments of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

Reference will now be made in detail to the various embodiments of the present disclosure, examples of which are illustrated in the accompanying drawings. While described in conjunction with these embodiments, it will be understood that they are not intended to limit the disclosure to these embodiments. On the contrary, the disclosure is intended to cover alternatives, modifications and equivalents, which may be included within the spirit and scope of the disclosure as defined by the appended claims. Furthermore, in the following detailed description of the present disclosure, numerous specific details are set forth in order to provide a thorough understanding of the present disclosure. However, it will be understood that the present disclosure may be practiced without these specific details. In other instances, well-known methods, procedures, components, and circuits have not been described in detail so as not to unnecessarily obscure aspects of the present disclosure.

NOTATION AND NOMENCLATURE

Some portions of the detailed descriptions that follow are presented in terms of procedures, logic blocks, processing, and other symbolic representations of operations on data bits within a computer memory. These descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. In the present application, a procedure, logic block, process, or the like, is conceived to be a self-consistent sequence of steps or instructions leading to a desired result. The steps are those utilizing physical manipulations of physical quantities. Usually, although not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated in a computer system. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as transactions, bits, values, elements, symbols, characters, samples, pixels, or the like.

It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the following discussions, it is appreciated that throughout the present disclosure, discussions utilizing terms such as “mapping,” “determining,” “adding,” “creating,” “computing,” “performing,” “appending,” “transmitting,” “forwarding,” or the like, refer to actions and processes (e.g., flowchart 700 of FIG. 7) of a computer system or similar electronic computing device or processor (e.g., system 110 of FIG. 1). The computer system or similar electronic computing device manipulates and transforms data represented as physical (electronic) quantities within the computer system memories, registers or other such information storage, transmission or display devices.

Embodiments described herein may be discussed in the general context of computer-executable instructions residing on some form of computer-readable storage medium, such as program modules, executed by one or more computers or other devices. By way of example, and not limitation, computer-readable storage media may comprise non-transitory computer-readable storage media and communication media; non-transitory computer-readable media include all computer-readable media except for a transitory, propagating signal. Generally, program modules include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types. The functionality of the program modules may be combined or distributed as desired in various embodiments.

Computer storage media includes volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer-readable instructions, data structures, program modules or other data. Computer storage media includes, but is not limited to, random access memory (RAM), read only memory (ROM), electrically erasable programmable ROM (EEPROM), flash memory or other memory technology, compact disk ROM (CD-ROM), digital versatile disks (DVDs) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium that can be used to store the desired information and that can accessed to retrieve that information.

Communication media can embody computer-executable instructions, data structures, and program modules, and includes any information delivery media. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, radio frequency (RF), infrared, and other wireless media. Combinations of any of the above can also be included within the scope of computer-readable media.

FIG. 1 is a block diagram of an example of a computing system 110 capable of being integrated with a processor 114 of an embodiment of the present disclosure. Computing system 110 broadly represents any single or multi-processor computing device or system capable of executing computer-readable instructions. Examples of computing system 110 include, without limitation, workstations, laptops, client-side terminals, servers, distributed computing systems, handheld devices, or any other computing system or device. In its most basic configuration, computing system 110 may include at least one processor 114 of an embodiment of the present invention and a system memory 116.

Processor

114 incorporates embodiments of the present invention and generally represents any type or form of processing unit capable of processing data or interpreting and executing instructions. In certain embodiments, processor 114 may receive instructions from a software application or module. These instructions may cause processor 114 to perform the functions of one or more of the example embodiments described and/or illustrated herein. In one embodiment, processor 114 may be an out of order microprocessor. In a different embodiment, processor 114 may be a superscalar processor. In yet another embodiment, processor 114 may comprise multiple processors operating in parallel.

System memory

116 generally represents any type or form of volatile or non-volatile storage device or medium capable of storing data and/or other computer-readable instructions. Examples of system memory 116 include, without limitation, RAM, ROM, flash memory, or any other suitable memory device. Although not required, in certain embodiments computing system 110 may include both a volatile memory unit (such as, for example, system memory 116) and a non-volatile storage device (such as, for example, primary storage device 132).

Computing system

110 may also include one or more components or elements in addition to processor 114 and system memory 116. For example, in the embodiment of FIG. 1, computing system 110 includes a memory controller 118, an input/output (I/O) controller 120, and a communication interface 122, each of which may be interconnected via a communication infrastructure 112. Communication infrastructure 112 generally represents any type or form of infrastructure capable of facilitating communication between one or more components of a computing device. Examples of communication infrastructure 112 include, without limitation, a communication bus (such as an Industry Standard Architecture (ISA), Peripheral Component Interconnect (PCI), PCI Express (PCIe), or similar bus) and a network.

Memory controller

118 generally represents any type or form of device capable of handling memory or data or controlling communication between one or more components of computing system 110. For example, memory controller 118 may control communication between processor 114, system memory 116, and I/O controller 120 via communication infrastructure 112.

I/O controller 120 generally represents any type or form of module capable of coordinating and/or controlling the input and output functions of a computing device. For example, I/O controller 120 may control or facilitate transfer of data between one or more elements of computing system 110, such as processor 114, system memory 116, communication interface 122, display adapter 126, input interface 130, and storage interface 134.

Communication interface

122 broadly represents any type or form of communication device or adapter capable of facilitating communication between example computing system 110 and one or more additional devices. For example, communication interface 122 may facilitate communication between computing system 110 and a private or public network including additional computing systems. Examples of communication interface 122 include, without limitation, a wired network interface (such as a network interface card), a wireless network interface (such as a wireless network interface card), a modem, and any other suitable interface. In one embodiment, communication interface 122 provides a direct connection to a remote server via a direct link to a network, such as the Internet. Communication interface 122 may also indirectly provide such a connection through any other suitable connection.

Communication interface

122 may also represent a host adapter configured to facilitate communication between computing system 110 and one or more additional network or storage devices via an external bus or communications channel. Examples of host adapters include, without limitation, Small Computer System Interface (SCSI) host adapters, Universal Serial Bus (USB) host adapters, IEEE (Institute of Electrical and Electronics Engineers) 1394 host adapters, Serial Advanced Technology Attachment (SATA) and External SATA (eSATA) host adapters, Advanced Technology Attachment (ATA) and Parallel ATA (PATA) host adapters, Fibre Channel interface adapters, Ethernet adapters, or the like. Communication interface 122 may also allow computing system 110 to engage in distributed or remote computing. For example, communication interface 122 may receive instructions from a remote device or send instructions to a remote device for execution.

As illustrated in FIG. 1, computing system 110 may also include at least one display device 124 coupled to communication infrastructure 112 via a display adapter 126. Display device 124 generally represents any type or form of device capable of visually displaying information forwarded by display adapter 126. Similarly, display adapter 126 generally represents any type or form of device configured to forward graphics, text, and other data for display on display device 124.

As illustrated in FIG. 1, computing system 110 may also include at least one input device 128 coupled to communication infrastructure 112 via an input interface 130. Input device 128 generally represents any type or form of input device capable of providing input, either computer- or human-generated, to computing system 110. Examples of input device 128 include, without limitation, a keyboard, a pointing device, a speech recognition device, or any other input device.

As illustrated in FIG. 1, computing system 110 may also include a primary storage device 132 and a backup storage device 133 coupled to communication infrastructure 112 via a storage interface 134.

Storage devices

132 and 133 generally represent any type or form of storage device or medium capable of storing data and/or other computer-readable instructions. For example,

storage devices

132 and 133 may be a magnetic disk drive (e.g., a so-called hard drive), a floppy disk drive, a magnetic tape drive, an optical disk drive, a flash drive, or the like. Storage interface 134 generally represents any type or form of interface or device for transferring data between

storage devices

132 and 133 and other components of computing system 110.

In one example, databases 140 may be stored in primary storage device 132. Databases 140 may represent portions of a single database or computing device or it may represent multiple databases or computing devices. For example, databases 140 may represent (be stored on) a portion of computing system 110. Alternatively, databases 140 may represent (be stored on) one or more physically separate devices capable of being accessed by a computing device, such as computing system 110.

Continuing with reference to FIG. 1,

storage devices

132 and 133 may be configured to read from and/or write to a removable storage unit configured to store computer software, data, or other computer-readable information. Examples of suitable removable storage units include, without limitation, a floppy disk, a magnetic tape, an optical disk, a flash memory device, or the like.

Storage devices

132 and 133 may also include other similar structures or devices for allowing computer software, data, or other computer-readable instructions to be loaded into computing system 110. For example,

storage devices

132 and 133 may be configured to read and write software, data, or other computer-readable information.

Storage devices

132 and 133 may also be a part of computing system 110 or may be separate devices accessed through other interface systems.

Many other devices or subsystems may be connected to computing system 110. Conversely, all of the components and devices illustrated in FIG. 1 need not be present to practice the embodiments described herein. The devices and subsystems referenced above may also be interconnected in different ways from that shown in FIG. 1. Computing system 110 may also employ any number of software, firmware, and/or hardware configurations. For example, the example embodiments disclosed herein may be encoded as a computer program (also referred to as computer software, software applications, computer-readable instructions, or computer control logic) on a computer-readable medium.

The computer-readable medium containing the computer program may be loaded into computing system 110. All or a portion of the computer program stored on the computer-readable medium may then be stored in system memory 116 and/or various portions of

storage devices

132 and 133. When executed by processor 114, a computer program loaded into computing system 110 may cause processor 114 to perform and/or be a means for performing the functions of the example embodiments described and/or illustrated herein. Additionally or alternatively, the example embodiments described and/or illustrated herein may be implemented in firmware and/or hardware.

Method and Apparatus to Allow Early Dependency Resolution and Data Forwarding in a Microprocessor

In one embodiment, the present invention provides a method and apparatus for a more efficient and flexible OOO processor architecture that is configured to mitigate the performance limiting issues associated with execution of state producing instructions by exercising early data forwarding.

For example, a branch instruction is an example of a state producing instruction. In an emulated architecture, both guest and native states exist. The guest architecture is emulated on top of the native machine. Further, the address space used to define the instruction offset in the guest space is dissociated from the native address space. As a result, a guest branch instruction when executed in the native space does not have access to the corresponding Guest Program Counter (GPC) value in order to compute its target. The guest branch instruction, therefore, may require a branch target value from a prior guest branch instruction to calculate its own target. This results in a performance limiting case, because the prior guest branch would first need to commit the updated GPC value that is maintained in a General Purpose Register (GPR) at the back-end of the machine before the current guest branch instruction would have access to it. This prevents the fetch machine from making progress and results in serialization of the pipeline, causing significant delays.

Embodiments of the present invention allow the data generated by the guest branch instructions (e.g., the branch targets) to be made speculatively available early enough to the fetch machine by implementing certain registers in the front-end of the pipeline, e.g., registers to calculate the targets of the branch instructions.

FIG. 2 is a block diagram of pipe stages an exemplary pipeline for an OOO microprocessor in accordance with embodiments of the present invention.

Instructions are fetched at the fetch stage 202 and placed in the instruction fetch queue (IFQ) (not shown) within fetch stage 202. The instructions are generally the original assembly instructions found in the executable program. These instructions reference the architectural registers which are stored in register file 210. If the first fetched instruction was to be interrupted or raise an exception, the architectural register file 210 stores the results of all instructions until that point. Stated differently, the architectural register file stores the state that needs to be saved and restored in order to return back to the program break point during debugging or otherwise.

In an OOO microprocessor, the instructions execute out-of-order while still preserving data dependence constraints. Because instructions may finish in an arbitrary order, the architectural register file 210 cannot be modified by the results of out of order instructions as they finish because it would make it difficult to restore their values accurately in the event of an exception or an interrupt. Hence, every instruction that enters the pipeline is provided a temporary register where it can save its result. The temporary registers are eventually written into the architectural register file in program order when the associated instruction retires. Thus, even though instructions are being executed out of order, the contents of the architectural register files change as though they were being executed in program order.

The ROB 208 facilitates the process of instruction retirement. After the instructions are dispatched from the fetch unit 202, they are decoded by decode module 204 and are placed in the ROB 208 and issue queue 206 (IQ). The ROB 208 and IQ 206 may be part of a scheduler module 272. As instructions are issued out of IQ 206 out of order, they are executed by execute module 212. Instruction execution at 212 is allowed out of order as long as data dependencies are maintained.

In one embodiment, the write back module 214 will write the resulting values from those instructions back to the temporary registers in ROB 208 and rely on the ROB 208 to facilitate committing or “retiring” the instructions in order. However, in a different embodiment, write back module 214 writes the values resulting from instruction execution directly into register file 210 without sorting them. The unordered elements are added in physical memory to the register file 210 in an unordered fashion and are then retired to the architectural files in order at the retirement stage using a ROB initiated protocol.

The instructions issued out of order from the IQ 206 may also comprise loads and stores. As explained above, when loads and stores are issued out of order from the IQ 206, there are memory dependencies between them that need to be resolved before those instructions can be committed. Accordingly, the store instructions are stored in order in a Load Store Queue (LSQ) 216 while the dependencies between the loads and stores are resolved with the help of ROB 208.

As discussed above, there are certain circumstances in a processor design where a value generated from a GPR, e.g., a control register could determine the control flow of the program or cause instructions or data values to be treated differently. For example, certain control flow instructions (also called state producing instructions) or branches may require data from a GPR to determine the manner in which to direct the flow of the program. However, because GPRs are maintained deep in the pipeline and are updated towards the end of the pipeline, a control flow instruction in a conventional OOO processor design would have to wait on the instruction(s) updating the associated GPR to execute and commit before being able to use the data. As a result, serialization is introduced in the pipeline because the execution of the control flow instruction and instructions subsequent to it are dependent on the resolution of the data in the GPR.

Embodiments of the present invention mitigate this performance-limiting problem by exercising early data forwarding. In one embodiment, the present invention speculatively maintains certain registers in the front end of the pipeline to be able to provide values from a GPR earlier to control flow instructions and branches as soon as they are fetched from Fetch stage 202 so that serialization and any resultant delays in the pipeline are avoided.

FIG. 3, for example, illustrates an exemplary instruction sequence 390. Instruction sequence 390 may comprise instructions, e.g., 331 that write to a rounding control register. Table 350 illustrates the different modes of the control register. The execution unit of the processor rounds the result of floating point (FP) instructions in accordance with the mode programmed in the control register. For example, a value of 01 programmed in the control register conveys to the execution unit that the result of all FP instructions should be truncated. Similarly, a value of 10 indicates that the result of all FP instructions should be rounded to the nearest value.

In a conventional OOO processor, instruction 332, which converts a floating point value to an integer, would have to wait for value 01 to be written to control register at the back-end of the pipeline before executing. This is because control registers in conventional OOO processors are typically not renamed and, accordingly, instruction 331 acts as a serializing instruction. Instruction 332 and subsequent instructions, therefore, need to wait until instruction 331 reaches the back end of the machine, commits and changes the value of the control register before starting to execute again.

In one embodiment of the present invention, register entry 340 can be maintained in the front-end in-order part of the pipeline where values for the control register can be stored speculatively for quicker access. Thus, instead of waiting for instruction 331 to commit its value at the back-end of the machine, a speculative copy of the control register can be maintained at the front end of the machine in pipeline register 340, where it can be accessed soon after instruction 331 is fetched. In one embodiment, every subsequent instruction following instruction 331 is tagged with the speculative value of the control register. This allows subsequent instructions to have immediate access to the correct control register value when they are executed. It also allow the pipeline to be flushed easily in case of a misprediction.

Similarly, for instruction 333, a speculative copy of the control register with value 10 can be maintained at the front end of the machine in pipeline register 340. Every instruction subsequent to instruction 333, e.g., FP instruction 334 is then tagged with this more recent value of the control register.

Eventually, the control register instructions, e.g., 331 and 333 reach the back-end of the machine, where they are retired and the values are updated. However, by this point all the instructions in sequence 390, e.g.,

instructions

332 and 334 have received the correct values speculatively at the front-end. Accordingly, the delaying effect of serializing

instructions

331 and 333 are mitigated.

As described in detail in related U.S. patent application Ser. No. 13/359,767, filed Jan. 27, 2012 (now U.S. Pat. No. 9,710,387, issued Jul. 18, 2017), titled, “GUEST INSTRUCTION TO NATIVE INSTRUCTION RANGE BASED MAPPING USING A CONVERSION LOOK ASIDE BUFFER OF A PROCESSOR” which is hereby incorporated by reference (hereinafter “U.S. Pat. No. 9,710,387”), guest instruction blocks are converted or mapped into native conversion blocks in an emulated architecture. As described in U.S. Pat. No. 9,710,387, guest instructions in an emulated architecture can be from a number of different guest instruction architectures (e.g., Java, x86, MIPS etc.) and multiple guest instruction blocks can be converted into one or more corresponding native conversion blocks. This conversion occurs on a per instruction basis.

Also, as described in U.S. Pat. No. 9,710,387 and shown in FIG. 4, in one embodiment, every instruction block, both guest instruction blocks and native instruction blocks, conclude with a far branch. (The difference between near branches and far branches are detailed in U.S. Pat. No. 9,710,387, however, for purposes of the embodiments of the present invention, far branches are used as examples and will hereinafter be referred to as “branches.”) For example, guest instruction block A 435 concludes with a branch 471 predicted to jump to guest instruction block B 436, guest instruction block B concludes with a branch 452 predicted to jump to guest instruction block C 437, etc. The branch is a jump to the next subsequent instruction block or sequence of instructions in memory.

As discussed above, when a guest architecture is emulated on top of a native machine, the address space used to define the instruction offset in the guest space is disassociated from the native address space. As a result, the branch targets from the guest branches are required to calculate the targets of any future guest branches (whose targets are often presented as addresses relative to the respective addresses in the emulated address space).

Processing guest branches that require targets from earlier branches in order to compute their own targets results in a performance limiting condition in emulated architectures of conventional OOO processors. As mentioned above, a guest branch instruction when executed in the native space does not have access to the corresponding Guest Program Counter (GPC) value in order to compute its target. The guest branch instruction, therefore, may require a branch target value from a prior guest branch instruction to calculate its own target. This is a performance limiting case, because the prior guest branch would first need to commit the updated GPC value that is maintained in a General Purpose Register (GPR) at the back-end of the machine before the current guest branch instruction would have access to it.

In order for the fetch stage 202 to continue making progress and to prevent serialization of the pipeline, these guest branch instructions require targets from earlier branches sooner than the delay associated with waiting for the earlier branches to be resolved in the back-end of the machine. For example, when executing branch instruction G.Branch.c2 467 (FIG. 4) in native instruction block B 441, which is a converted instruction corresponding to branch instruction Branch.c2 452 in guest instruction block B 436, the target of the earlier branch G.Branch.c1 465 is required to compute the target for branch 467. As will be discussed in detail below, embodiments of the present invention allow a speculative target value to be provided to branch 467 without having to wait for the target of the earlier branch 465 to be committed at the back-end of the pipeline.

As mentioned above, the target of a guest branch (a branch whose target is an address in the guest space or emulated slave space) is often presented as an offset relative to the address of the guest branch in the emulated address space. For example, offset1 is an address relative to the address (Guest Program Counter) of the instruction Branch.c1 in instruction 471. Because of the dissociation between the native and guest address spaces, instruction 465 in native space, which corresponds to instruction 471 in guest space, will have a different program counter than the Guest Program Counter (GPC) of instruction 471. Accordingly, when executing instruction 465, the corresponding GPC is required which is then added to the offset1′ value from instruction 465 to compute the branch target. The branch target so calculated will also be needed for the subsequent branch, e.g., instruction G.Branch.c2′ 467 to compute the target for that branch.

Once the branch target is determined in the emulated address space (e.g., once the GPC value of the branch target is determined), it is then converted to native space using a conversion look-aside buffer (CLB) as discussed in U.S. Pat. No. 9,710,387 to provide the corresponding target in native address space.

In a conventional emulated architecture, processing instruction 467 would require waiting until instruction 465 had finished calculating the branch target and committed its value post-execution at the back-end of the pipeline. It should be noted, that guest branch instruction 467 (G.Branch.c2) needs to compute its target in the emulated address space because, as mentioned above, the target of a guest branch is typically presented as an offset relative to its address in the emulated address space. Accordingly, offset2′ is tied to the emulated address space and instruction 467 needs to compute its target in the guest address space.

Before instruction 467 computes its target address in a conventional emulated architecture, it must wait until instruction 465 has computed its branch target and committed the results. Waiting until instruction 465 has computed its branch target and committed the results entails waiting until instruction 465 has executed, computed its branch target in the emulated address space, committed the resultant values in the back-end of the machine and converted the guest address over to a corresponding native address in native instruction block B 441 using a CLB. Accordingly, in a conventional OOO processor, instruction 465 would act as a serializing instruction, thereby delaying the subsequent guest branch, e.g., instruction 467 and any instructions following it.

Embodiments of the present invention circumvent this problem by maintaining a guest branch target register (GBTR) in the front-end of the pipeline, which stores the targets of the guest branches speculatively so that the data is readily available to the fetch machine. In one embodiment, the invention provides a mechanism to maintain a pipelined GBTR in the front-end of the machine. Guest branch instructions write to this register with the guest-target if they are predicted to be taken.

It should be noted that maintaining the GBTR at the front-end of the machine allows every native instruction block to implicitly maintain a corresponding guest address for the starting instruction within the respective native instruction block. For example, in FIG. 4, G_Address_Block A 471 is the corresponding guest address maintained within the GBTR for the starting address of native instruction block A 430. G_Address_Block A 471 is the corresponding guest address for the starting instruction of block A 430, e.g., Inst A′ 440. Assuming guest instruction block A 435 is the first instruction block in the user-defined code, then G_Address_Block A 471 is simply the starting GPC of the instruction sequence of guest instruction block A 435. The starting entry into the GBTR is typically populated by software at the time of mapping the guest instruction blocks into native conversion blocks.

Similarly, G_Address_Block B 474 is the corresponding guest address maintained in the GBTR for the starting address of native instruction block B 441. G_Address_Block C 472 is the corresponding guest address maintained in GBTR for the starting address of native instruction block C 472. G_Address_Block D 473 is the corresponding guest address maintained in GBTR for the starting address of native instruction block D 443. Accordingly, a guest address is implicitly maintained in the front-end of the pipeline for each instruction sequence boundary. Prior guest addresses implicitly maintained in the GBTR for the instruction sequence boundaries are used to calculate the branch targets of subsequent guest branches, e.g., the corresponding guest address of G.Branch.c1 465 is used to calculate the corresponding guest address for G.Branch.c2 467, etc., at execution time. The subsequent guest branch targets are then populated into the GBTR as will be discussed in FIG. 5.

It should be noted that because only the guest address corresponding to the start of any native instruction block is available for the calculation of the guest branch targets at execution time, the offset values for each of the guest branch instructions needs to be adjusted to account for this when mapping the instructions from guest space into native space. For example, guest branch, G.Branch.c2 467 does not have access to the GPC of corresponding guest instruction 452, but it does have access to guest address G_Address_Block B 474. Accordingly, offset2′ needs to be adjusted to account for the difference in GPC between Inst C 434 and Branch.c2 instruction 452 (because recall that G_Address_Block B 474 is the guest address corresponding to the start of guest instruction block B 436).

In one embodiment, this adjustment of offset values is made by software during the initial mapping when instruction 452 Branch.c2 is mapped over from guest address space to corresponding instruction 467 G.Branch.c2 in native address space. Accordingly, the value of offset2 from instruction 452 is adjusted to a value of offset2′ for instruction 467. The updated offset value, offset2′, added to guest address, G_Address_Block B 474 will yield the correct branch target address, which can then be added to the GBTR as will be discussed in FIG. 5. Because the branch target address so calculated will be in emulated space, a CLB will be required to convert it to over to a corresponding native space address.

FIG. 5 illustrates the manner in which the pipelined guest branch target register is updated using a prior branch target in accordance with one embodiment of the present invention. During execution, if a guest branch instruction 535 (e.g., instruction 467, G.Branch.c2) is encountered and predicted to be taken, in one embodiment, the GBTR 590 needs to be updated. The offset value determined in software for that instruction (e.g. offset2′), as discussed above, is added to the prior branch target 534 by module 538 to yield a new guest branch target, which is stored in GBTR 590 at entry 539 as the new youngest unretired guest branch. Further, when the new branch target is added to the GBTR, the youngest unretired guest branch pointer 591 to the register is updated to point to the newly added target. As seen from FIG. 5, the new entries are added to the GBTR on a FIFO basis—the first branch entered will also be the first to be retired from the queue.

The embodiments of the present invention therefore advantageously allow resolution of the branch target address earlier in the pipeline (e.g., at the fetch stage) as compared with conventional solutions that wait for the process of the prior branch instructions to finish execution at the back-end of the machine and commit their values.

As stated above, the guest addresses stored in the GBTR can be mapped back to native address space by using a CLB as discussed in detail in U.S. Pat. No. 9,710,387.

Similar to guest branch target 539, the other guest branch targets are also determined using prior guest branch targets. For example, branch target 534 is determined using branch target 533. Branch target 533 is determined using branch target 532, and so forth. As discussed with respect to entry G_Address_Block A 471 in FIG. 4, target 531 (0xA) may either be the starting guest address of the user's code sequence or alternatively, it could be the target of the youngest retired guest branch. If the latter, then entry 531 comprises the oldest unretired guest branch.

It should be noted that all values in the GBTR are updated speculatively. Because register values are updated speculatively, in one embodiment, multiple copies of the GBTR to be maintained in the front-end of the pipeline. Further, in one embodiment, read and write pointers are maintained within the GBTR. In one embodiment, the pointers allow the most current value in the register to be easily retrieved. For example, a pointer 591 is maintained that allows the youngest unretired guest branch to be retrieved from the GBTR. Also, a pointer 592 to the oldest unretired guest branch can be maintained.

In one embodiment, in addition to being updated when new targets are added to the register, the pointers to a GBTR can also be updated on the flush or retirement of an instruction. If an instruction is flushed or retired, both

pointers

592 and 591, for example, would need to be updated. To enable flushing, each instruction carries as a tag, which, in one embodiment, can be a pointer to the last branch instruction that updated this register. In a different embodiment, the branch target can itself be appended to the instruction as a tag. For example, as shown in FIG. 5, a tag component 537 gets appended to the instruction component 535 of guest branch 535 before being dispatched to the instruction scheduling unit.

FIG. 6 illustrates the manner in which each instruction fetched is tagged with information about the last branch instruction that updated the guest branch target register in accordance with one embodiment of the present invention. As shown in FIG. 6, the oldest unretired guest branches in the GBTR get retired before the youngest unretired guest branches. So target 0xA is retired prior to target 0xB 632 and so on. When a new instruction 636 is fetched, it will typically get tagged with the branch target of the youngest unretired guest branch 635. This tag 637 can either be a pointer or the actual value of the branch target. The instruction is then dispatched to the scheduler 272. The tagging is advantageous because in case of a pipeline flush, it helps identify the relative position of each instruction. For example, if all instructions between target 0xA 631 and target 0xB 632 needed to be flushed, the tag would enable those instructions to be easily identified.

Further, in one embodiment of the present invention, the tagging is useful for non-branch instructions that operate on the guest program counter value. For example, Inst E′ 466 in FIG. 4 needs the GPC value as an operand. However, the GPC is unavailable in the native address space. Accordingly, tagging every instruction by attaching the current value of the GBTR as an immediate-value to the instruction and sending it along with the instruction is useful because the branch target can be used to calculate the corresponding GPC value for instruction 466 (which is the GPC value for instruction 476 in guest address space). This advantageously enables the register, which is exercised in the back-end of the processor, to be available readily in the front-end of the processor.

The embodiments of the present invention advantageously also eliminate the read-after-write dependency between the guest-branch and the instruction requiring a read of this register. The data is forwarded from the producer to a subsequent consumer. This allows the guest-branch and the subsequent instruction to execute in any order thus eliminating the performance problem stemming from the serialization required as a result of a data dependency.

The embodiments of the present invention provides a low-cost maintenance mechanism wherein an implicit update of the guest branch target registers can be performed. Explicit update of these registers by software requires serialization and flushing of the machine. By comparison, the embodiments of the present invention allows for speculative maintenance of structures aiding in resolving data dependencies in early stages of a microprocessor. This is a significant advantage over conventional OOO processors wherein similar data forwarding cases are handled in the execution unit 212, which resides in the back-end of the machine.

Finally, instruction 6 also demonstrates the retirement order of the branches entered in the GBTR. As mentioned above entries are entered into the GBTR on a FIFO basis. Accordingly, the earliest entered target, e.g. instruction 631 will be the first to be retired.

FIG. 7 depicts a flowchart 700 for an exemplary computer controlled process for performing early dependency resolution and data forwarding for instructions in the native space of an emulated architecture referencing a guest address in accordance with embodiments of the present invention. While the various steps in this flowchart are presented and described sequentially, one of ordinary skill will appreciate that some or all of the steps can be executed in different orders and some or all of the steps can be executed in parallel. Further, in one or more embodiments of the invention, one or more of the steps described below can be omitted, repeated, and/or performed in a different order. Accordingly, the specific arrangement of steps shown in FIG. 7 should not be construed as limiting the scope of the invention. Rather, it will be apparent to persons skilled in the relevant art(s) from the teachings provided herein that other functional flows are within the scope and spirit of the present invention. Flowchart 700 may be described with continued reference to exemplary embodiments described above, though the method is not limited to those embodiments. Process 700 may also be implemented in hardware in one embodiment.

At step 702, a plurality of instructions are mapped from a guest address space to a native address space.

At step 704, the instructions in the native address space begin executing. For each current guest branch instruction that is encountered while fetching the instructions, a branch target value is determined for a prior guest branch by performing a look-up in a GBTR. As mentioned above, this typically takes place at the front-end of the machine, e.g., at the fetch stage. The GBTR, as discussed above, is a series of registers maintained to speculatively store the branch targets of guest branches at the front-end of the machine, e.g., at the fetch stage. The prior guest branch target looked up in the GBTR is used to speculatively determine the branch target for the current guest branch instruction, so that the information regarding where the current branch instruction jumps to is available at the front end of the pipeline. This is in contrast to conventional processors that need to wait for prior guest branches to resolve completely at the back end of the machine before allowing subsequent guest branches to proceed forward.

At step 706, an offset value from a respective current guest branch instruction is added to the target value for the prior guest branch (looked-up in the GBTR) in order to determine the branch target for the respective current guest branch instruction.

Finally, at step 708, a new entry is creating in the GBTR for the newly determined branch target (of the current guest branch instruction) and the GBTR is updated by adding this branch target to the new entry. This entry now becomes the youngest unretired guest branch and the pointer to the youngest unretired guest branch is updated accordingly in the GBTR.

While the foregoing disclosure sets forth various embodiments using specific block diagrams, flowcharts, and examples, each block diagram component, flowchart step, operation, and/or component described and/or illustrated herein may be implemented, individually and/or collectively, using a wide range of hardware, software, or firmware (or any combination thereof) configurations. In addition, any disclosure of components contained within other components should be considered as examples because many other architectures can be implemented to achieve the same functionality.

The process parameters and sequence of steps described and/or illustrated herein are given by way of example only. For example, while the steps illustrated and/or described herein may be shown or discussed in a particular order, these steps do not necessarily need to be performed in the order illustrated or discussed. The various example methods described and/or illustrated herein may also omit one or more of the steps described or illustrated herein or include additional steps in addition to those disclosed.

While various embodiments have been described and/or illustrated herein in the context of fully functional computing systems, one or more of these example embodiments may be distributed as a program product in a variety of forms, regardless of the particular type of computer-readable media used to actually carry out the distribution. The embodiments disclosed herein may also be implemented using software modules that perform certain tasks. These software modules may include script, batch, or other executable files that may be stored on a computer-readable storage medium or in a computing system. These software modules may configure a computing system to perform one or more of the example embodiments disclosed herein. One or more of the software modules disclosed herein may be implemented in a cloud computing environment. Cloud computing environments may provide various services and applications via the Internet. These cloud-based services (e.g., software as a service, platform as a service, infrastructure as a service, etc.) may be accessible through a Web browser or other remote interface. Various functions described herein may be provided through a remote desktop environment or any other cloud-based computing environment.

The foregoing description, for purpose of explanation, has been described with reference to specific embodiments. However, the illustrative discussions above are not intended to be exhaustive or to limit the invention to the precise forms disclosed. Many modifications and variations are possible in view of the above teachings. The embodiments were chosen and described in order to best explain the principles of the invention and its practical applications, to thereby enable others skilled in the art to best utilize the invention and various embodiments with various modifications as may be suited to the particular use contemplated.

Embodiments according to the invention are thus described. While the present disclosure has been described in particular embodiments, it should be appreciated that the invention should not be construed as limited by such embodiments, but rather construed according to the below claims.

Claims

What is claimed is:

1. A microprocessor implemented method of performing early dependency resolution and data forwarding for instructions in a native space of an emulated architecture referencing a guest address, said method comprising:

mapping a plurality of instructions in a guest address space to a corresponding plurality of instructions in a native address space;

for each guest branch instruction in said native address space fetched during execution, performing:

determining a youngest prior guest branch target stored in a guest branch target register, wherein said guest branch target register is operable to speculatively store a plurality of prior guest branch targets in said guest address space corresponding to prior guest branch instructions in said native address space, and wherein said guest branch target register is maintained at a fetch stage of a pipeline;

determining a branch target in said guest address space for a respective guest branch instruction in said native address space by adding an offset value for said respective guest branch instruction to said youngest prior guest branch target, wherein said offset value is an adjusted offset that is adjusted during said mapping to account for a difference in address in said guest address space between an instruction at a beginning of a guest instruction block and a branch instruction in said guest instruction block that corresponds to said respective guest branch instruction; and

creating an entry in said guest branch target register for said branch target, wherein said creating further comprises updating a pointer to said youngest prior guest branch target to point to said branch target in said guest branch target register, wherein said guest branch target register comprises a first-in first-out (FIFO) queue, and wherein further said guest branch target register maintains a pointer to an oldest unretired guest branch target and maintains a pointer to a youngest unretired guest branch target within said guest branch target register.

2. The method of claim 1, further comprises retiring instructions in said guest branch target register in order, wherein said oldest unretired guest branch target is retired first, and wherein said youngest unretired guest branch target is retired last.

3. The method of claim 1, further comprising for each guest branch instruction in said native address space fetched during execution:

appending information associated with said youngest prior guest branch target in a tag field to said respective guest branch instruction; and

transmitting said respective guest branch instruction to a scheduling stage of said pipeline of an out-of-order micro-architecture.

4. The method of claim 1, further comprising for each non-branch instruction in said native address space fetched during execution:

appending information associated with said youngest prior guest branch target in a tag field to a respective non-branch instruction; and

forwarding said respective non-branch instruction to a scheduling stage of said pipeline of an out-of-order micro-architecture.

5. A processor unit configured to perform operations for early dependency resolution and data forwarding for instructions in a native space of an emulated architecture referencing a guest address, the operations comprising:

mapping a plurality of instructions in a guest address space into a corresponding plurality of instructions in a native address space;

determining a youngest prior guest branch target stored in a guest branch target register, wherein said guest branch target register is operable to speculatively store a plurality of prior guest branch targets in said guest address space corresponding to prior guest branch instructions in said native address space;

creating an entry in said guest branch target register for said branch target wherein said creating further comprises:

updating a pointer to said youngest prior guest branch target to point to said branch target in said guest branch target register wherein said guest branch target register comprises a first-in first-out (FIFO) queue, and wherein further said guest branch target register maintains a pointer to an oldest unretired guest branch target and maintains a pointer to a youngest unretired guest branch target within said guest branch target register.

6. The processor unit of claim 5, wherein said operations further comprise retiring instructions in said guest branch target register in order, wherein said oldest unretired guest branch target is retired first, and wherein said youngest unretired guest branch target is retired last.

7. The processor unit of claim 5, wherein said operations further comprise for each guest branch instruction in said native address space fetched during execution:

transmitting said respective guest branch instruction to a scheduling stage of a pipeline of an out-of-order micro-architecture.

8. The processor unit of claim 5, wherein said operations further comprise for each non-branch instruction in said native address space fetched during execution:

forwarding said respective non-branch instruction to a scheduling stage of a pipeline of an out-of-order micro-architecture.

9. An apparatus configured to perform early dependency resolution and data forwarding for instructions in a native space of an emulated architecture referencing a guest address, said apparatus comprising:

a memory;

a processor communicatively coupled to said memory, wherein said processor is configured to process instructions out of order, and further wherein said processor is configured to perform operations comprising:

creating an entry in said guest branch target register for said branch target wherein said creating further comprises updating a pointer to said youngest prior guest branch target to point to said branch target in said guest branch target register wherein said guest branch target register comprises a first-in first-out (FIFO) queue, and wherein further said guest branch target register maintains a pointer to an oldest unretired guest branch target and maintains a pointer to a youngest unretired guest branch target within said guest branch target register.

10. The apparatus of claim 9, wherein said operations further comprise retiring instructions in said guest branch target register in order, wherein said oldest unretired guest branch target is retired first, and wherein said youngest unretired guest branch target is retired last.

11. The apparatus of claim 9, wherein said operations further comprise for each guest branch instruction in said native address space fetched during execution:

12. The apparatus of claim 9, wherein said operations further comprise for each non-branch instruction in said native address space fetched during execution: