Dynamic branch hints using branches-to-nowhere conditional branch

#This patent application is a U.S. National Phase Application under 35 U.S.C. §371 of International Application No. PCT/US2012/031635, filed Mar. 30, 2012, entitled DYNAMIC BRANCH HINTS USING BRANCHES-TO-NOWHERE CONDITIONAL BRANCH.

#Embodiments of the present invention relate generally to branch predictions of a processor. More particularly, embodiments of the invention relate to dynamic branch hints using a branch-to-nowhere conditional branch.

#Modern microprocessor pipelines use branch prediction to mitigate performance loss due to control dependency stalls. Many solutions where the branch predictor learns entirely in hardware or in a combination with software have been proposed and used in several generations of microprocessors. All of these schemes attempt to predict a branch outcome based on a history context that is derived from prior computation state that contains correlated information to the branch outcome. Global history based branch predictors such as gshare and bgG use a context derived from global branch history which has been proven to contain correlated information for correctly predicting branches in many cases. However, in certain cases such as when the branch outcome depends on input data with no predictable patterns, the global history may not have any correlated information, and such branches are hard to predict using predictors such as gshare.

#Embodiments of the invention are illustrated by way of example and not limitation in the figures of the accompanying drawings in which like references indicate similar elements.

#FIGS. 1A-1C are pseudocode representing a typical program loop with a conditional branch.

#FIG. 2 is a block diagram of an execution pipeline of a processor or processor core according to one embodiment of the invention.

#Various embodiments and aspects of the inventions will be described with reference to details discussed below, and the accompanying drawings will illustrate the various embodiments. The following description and drawings are illustrative of the invention and are not to be construed as limiting the invention. Numerous specific details are described to provide a thorough understanding of various embodiments of the present invention. However, in certain instances, well-known or conventional details are not described in order to provide a concise discussion of embodiments of the present inventions.

#Reference in the specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in conjunction with the embodiment can be included in at least one embodiment of the invention. The appearances of the phrase “in one embodiment” in various places in the specification do not necessarily all refer to the same embodiment.

#According to some embodiments, a mechanism is presented to boost predictability of hard-to-predict branches by injecting correlated information into the global history of dynamic predictors such as gshare using existing conditional branch instructions effectively as dynamic branch hints by means of specific modifications to the microarchitecture. An embodiment of the invention is to replace the mythical branch_hint instruction with a standard conditional branch, but one that goes to the next instruction in the code stream, whether the branch is taken or not (also referred to as a branch-to-nowhere conditional branch). The rationale is that by inserting such a branch in code prior to the branch-under-prediction (subject to certain minimum distance requirements between the two), it injects correlated information into the global history that will help the subsequent branch to predict correctly.