通过循环结束分支来抑制分支历史寄存器的更新

摘要

本发明涉及通过循环结束分支来抑制分支历史寄存器的更新。检测终止代码循环的条件分支指令，且防止分支历史寄存器(BHR)更新以存储循环结束分支评估。这防止实施循环迭代的分支从所述BHR中取代其它分支评估历史。可通过编译器使用特定类型分支指令或在循环结束分支指令的操作码中插入指示位来静态地检测所述循环结束分支。循环结束分支指令可被动态地检测为任何后向分支，或者通过在更新所述BHR时存储最后一个或若干个分支指令的PC并对照最后分支PC(LBPC)寄存器检验分支指令的所述PC而动态地检测。如果所述分支PC匹配，那么抑制对所述BHR的更新。将循环迭代分支保持在所述BHR之外会改进分支预测训练时间和准确性。

权利要求

1.一种编译器或汇编器，其可操作以响应于程序代码而产生指令，所述编译器或汇编器包括：循环结束分支指令标记功能，其可操作以指示终止代码循环的条件分支指令，其中终止代码循环的条件分支指令的指示被安排以抑制分支历史寄存器的更新。

2.根据权利要求1所述的编译器或汇编器，其中所述循环结束分支指令标记功能可操作以产生唯一类型的分支指令来结束每一循环。

3.根据权利要求1所述的编译器或汇编器，其中所述循环结束分支指令标记功能可操作以在结束循环的每一条件分支指令中插入循环结束指示符。

4.根据权利要求3所述的编译器或汇编器，其中所述循环结束指示符包括在所述条件分支指令操作码中的一个或一个以上位。

5.一种编译程序代码的方法，其包括：

产生指令以响应程序代码；

标记循环结束分支指令，以指示终止代码循环的条件分支指令；以及响应于检测到关于条件分支指令终止代码循环的指示而抑制分支历史寄存器的更新。

6.根据权利要求5所述的方法，其中所述循环结束分支指令标记是用于结束每一循环的唯一类型的分支指令。

7.根据权利要求5所述的方法，其中所述循环结束分支指令标记是在结束循环的每一条件分支指令中的循环结束指示符。

8.根据权利要求7所述的方法，其中所述循环结束指示符是在所述条件分支指令中的预定字段中的一个或一个以上位。

9.一种处理器，其包括：

分支预测器，其可操作以预测对条件分支指令采用或不采用的评估；

指令执行管线，其可操作以基于来自所述分支预测器的预测以推测方式取得并执行指令；

分支历史寄存器(BHR)，其经配置以存储所述对条件分支指令采用或不采用的评估；以及控制电路，其在条件分支的分支目标地址确定后，可操作以在所述条件分支指令是循环结束分支指令时抑制存储所述对所述条件分支指令采用或不采用的评估。

10.根据权利要求9所述的处理器，其进一步包括最后分支PC(LBPC)寄存器，所述最后分支PC(LBPC)寄存器可操作以存储更新所述分支历史寄存器(BHR)的分支指令的PC，且其中所述控制电路可操作以在所述分支指令的PC与所述最后分支PC(LBPC)寄存器的内容匹配时抑制存储所述对条件分支指令采用或不采用的评估。

11.根据权利要求10所述的处理器，其进一步包括多个最后分支PC(LBPC)寄存器，所述多个最后分支PC(LBPC)寄存器可操作以存储更新所述分支历史寄存器(BHR)的多个分支指令的PC，且其中所述控制电路可操作以在所述分支指令的PC与任何最后分支PC(LBPC)寄存器的内容匹配时抑制存储所述对条件分支指令采用或不采用的评估。

12.根据权利要求9所述的处理器，其中所述控制电路可操作以在所述分支指令包含其为循环结束指令的指示时抑制存储所述对条件分支指令采用或不采用的评估。

13.根据权利要求12所述的处理器，其中所述分支指令为循环结束指令的所述指示为指令类型。

14.根据权利要求9所述的处理器，其中所述控制电路可操作以在分支指令目标地址小于所述分支指令PC时抑制存储所述对条件分支指令采用或不采用的评估。

15.一种用于编译程序代码的设备，其包括：

硬件处理器，其可操作以响应于程序代码而产生指令；以及

编译器或汇编器，其包括循环结束分支指令标记功能，其可操作以指示终止代码循环的条件分支指令，以此使用指示来阻止分支历史寄存器(BHR)的更新，所述分支历史寄存器(BHR)经配置以存储对条件分支指令采用或不采用的评估。

16.根据权利要求15所述的设备，其中所述循环结束分支指令标记功能可操作以产生唯一类型的分支指令来结束每一循环。

17.根据权利要求15所述的设备，其中所述循环结束分支指令标记功能可操作以在结束循环的每一条件分支指令中插入循环结束指示符。

18.根据权利要求17所述的设备，其中所述循环结束指示符包括在所述条件分支指令操作码中的一个或一个以上位。

说明书

通过循环结束分支来抑制分支历史寄存器的更新

[0001] 分案申请的相关信息

[0002] 本案是分案申请。该分案的母案是申请日为2006年2月24日、申请号为200680012619.8、发明名称为“通过循环结束分支来抑制分支历史寄存器的更新”的发明专利申请案。

技术领域

[0003] 本发明大体上涉及处理器领域，且更确切地说涉及一种通过用循环结束分支指令抑制对分支历史寄存器的更新而改进分支预测的方法。

背景技术

[0004] 微处理器在广泛的应用中执行计算任务。几乎始终需要改进的处理器性能以允许通过软件变化来实现较快的操作和/或增加的功能性。在许多嵌入式应用(例如，便携式电子装置)中，节省功率也是处理器设计和实施的一个目标。

[0005] 许多现代处理器使用管线结构，其中连续的指令(各具有多个执行步骤)在执行时重叠。为了实现改进的性能，指令应当连续流动穿过管线。任何导致指令在管线中停滞的情形均可对性能造成不利影响。如果从管线中冲洗(flush)指令并随后重新取得指令，那么性能和功率消耗均会受到损害。

[0006] 大多数程序包含条件分支指令，直到在管线深处评估指令时才会知道其实际分支行为。为了避免因等待对分支指令的实际评估而产生的停滞，现代处理器可采用某种形式的分支预测，借此在管线中早期预测条件分支指令的分支行为。基于预测出的分支评估，处理器以推测方式从预测出的地址取得(预取)并执行指令，所述预测出的地址是分支目标地址(如果预测会采用分支)或分支指令之后的下一顺序地址(如果预测不会采用分支)。当确定了实际分支行为时，如果分支被错误预测，那么必须从管线中冲洗以推测方式取得的指令，并从下一正确地址取得新的指令。响应于错误的分支预测而预取指令可对处理器性能和功率消耗造成不利影响。因此，改进分支预测的准确性是一个重要的设计目标。

[0007] 已知的分支预测技术包含静态和动态两种预测。可通过编程器和/或编译器来静态地预测一些分支指令的可能行为。分支预测的一个实例是错误检验例行程序。代码通常会正确执行，且错误是罕见的。因此，实施“遇错误分支(branch on error)”的分支指令将在非常高的百分比的时间中评估“不采用”。此种指令可在操作码中包含静态分支预测位，所述预测位是由编程器或编译器在知道分支条件的最可能结果的情况下设定的。

[0008] 动态预测一般基于正被预测的分支指令和/或同一代码中的其它分支指令的分支评估历史(且在一些情况下是分支预测准确性历史)。对实际代码的广泛分析指示，最近过去的分支评估模式可能是对未来分支指令的评估的良好指示。

[0009] 图1中描绘的一种已知形式的动态分支预测利用分支历史寄存器(BHR)100来存储过去n个分支评估。在简单的实施方案中，BHR30包括移位寄存器。将最近的分支评估结果移入(例如，1指示采用分支且0指示不采用分支)，而寄存器中的最早过去的评估被取代。处理器可针对每个分支指令维持局部BHR100。或者(或另外)，BHR100可含有对所有条件分支指令的最近过去的评估，其有时在此项技术中称为全局BHR或GHR。如本文所使用，BHR指代局部和全局分支历史寄存器两者。

[0010] 如图1中所描绘，BHR100可将分支预测器表(BPT)102编索引，所述BPT102同样可以是局部的或全局的。BHR100可直接将BPT102编索引，或者可在BPT索引逻辑104中与例如分支指令的程序计数器(PC)的其它信息组合。另外可利用对BPT索引逻辑104的其它输入。BPT索引逻辑104可将输入链接在一起(此项技术中通常称为gselect)，对输入进行异或运算(gshare)，执行散列函数，或以多种方式组合或转换输入。

[0011] 在一个实例中，BPT102可包括多个饱和计数器，其MSB充当双模态分支预测器。举例来说，每个表条目可包括2位计数器，所述计数器采用四种状态中的一种，所述四种状态中的每一者被指派有加权预测值，例如：

[0012] 11-强力预测采用

[0013] 10-弱预测采用

[0014] 01-弱预测不采用

[0015] 00-强力预测不采用

[0016] 每当相应的分支指令评估“采用”时，所述计数器递增，且每当指令评估“不采用”时，所述计数器递减。计数器的MSB是双模态分支预测器，其将预测一个分支是采用还是不采用，而不管基础预测的强度或权重如何。饱和计数器减少不频繁的分支评估的预测错误。始终单向评估的分支将使计数器饱和。相反地不频繁评估将改变计数器值(以及预测的强度)，但不是双模态预测值。因此，不频繁的评估将只错误预测一次而不是两次。饱和计数器的表只是说明性实例，一般来说，BHT可将含有多种分支预测机制的表编索引。

[0017] 不论在BPT102中采用哪种分支预测机制，BHR100(单独的或与例如分支指令PC的其它信息组合)将BPT102编索引以获得分支预测。通过在BHR100中存储先前分支评估并在分支预测中使用所述评估，使正被预测的分支指令与过去的分支行为相关——在局部BHR100的情况下为其自身的过去行为而在全局BHR100的情况下为其它分支指令的行为。这种相关至少在高度重复的代码的情况下可能是准确的分支预测的关键。

[0018] 请注意，图1描绘存储在BHR100中的分支评估，即对条件分支指令的实际评估，其可能只有在管线深处(例如在执行管级中)才被了解。虽然这是最终结果，但在实践中，许多高性能处理器将来自BPT102的预测出的分支评估存储在BHR100中，并之后在证实预测错误时作为错误预测恢复操作的一部分而对BHR100进行校正。为了清晰起见，附图未反映这种实施特征。

[0019] 可能会降低采用BHR100的分支预测器的功效的一种常用代码结构是循环。循环以测试循环结束条件的条件分支指令结束，所述循环结束条件例如为每次通过循环时递增的索引变量是否已达到循环结束值。如果没有，那么执行形成分支回到循环的开始处以进行另一次迭代和另一次循环结束条件分支评估。相对于n位BHR100，存在关于循环的三种相关情况：循环不执行；循环通过m次迭代执行(其中m＜n)；和循环执行m次(其中m＞=n)。

[0020] 如果循环不执行，那么循环开始处的前向分支在循环主体上形成分支，从而产生一个采用的分支评估。这对BHR100具有最小影响，因为BHR100中的过去分支评估历史只由一个分支评估取代(实际上，预测准确性可通过与这个分支评估的相关来改进)。

[0021] 如果循环通过m次迭代来执行(其中m＞=n)，那么循环结束分支指令的“采用”后向分支使BHR100饱和。也就是说，在循环结束时，n位BHR将始终含有恰好n-1个一且后面跟着单个零，这对应于由循环迭代产生的较长系列的采用的评估，且在循环终止时以单个未采用评估结束。这实际上损害BHR100的功效，因为与先前分支评估(对于局部或全局BHR100)的所有相关全部丢失。在此情况下，BHR100将很可能映射到相同的BPT102条目以获取给定的分支指令(视对BPT索引逻辑104的其它输入而定)，而不是映射到含有反映分支指令与先前分支评估的相关的分支预测的条目。

[0022] 此外，饱和的BHR100可增加BPT102中的混淆。也就是说，如果BHR100直接将BPT102编索引，那么具有许多迭代的循环之后的所有分支指令将映射到相同的BPT102条目。即使在BHR100与其它信息组合的情况下，混淆的可能性也会增加。这不但对于循环之后的分支指令而且对于混淆到其在BPT102中的条目的所有分支指令，均会不利地影响预测准确性。

[0023] 如果循环通过m次迭代执行(其中m＜n)，那么BHR100不饱和且保持某一先前分支评估历史。然而，代表先前分支评估历史的位被m个位位置取代。特别在m变化的情况下，这对分支预测具有两个有害影响。首先，分支指令将映射到BPT102中的更大数目的条目，以俘获与先前分支评估的相同相关，从而与没有循环结束分支影响BHR30的情况下将需要的BPT102相比，对于相同数目的分支指令需要更大的BPT102来支持相同的准确性。第二，BPT102中的分支预测器将花费较长时间来“训练”，从而增加了在BPT102开始提供准确的分支预测之前必须执行的代码量。

[0024] 举例来说，考虑8位BHR100和一代码段，其具有分支指令A-H，接着是循环，且接下来是分支指令X。分支X与分支G和H的评估历史强力相关。插入的循环的各种迭代将在预测X时产生下表1中呈现的BHR结果。

[0025]

[0026] 表1：各种数目的循环迭代之后的BHR100内容

[0027] 在此实例中，每种情况下BHR100中均存在正被预测的分支指令X与对分支G和H的先前评估之间的所需相关。然而，其位于BHR100中的不同位置，且因此每种情况将映射到不同的BPT102条目。这会浪费BPT102空间，增加分支预测训练时间，并增加BPT102中的混淆的可能性，所有这些都会降低预测准确性。

发明内容

[0028] 在一个或一个以上实施例中，通过识别循环结束分支指令并响应于循环结束指令而抑制对BHR的更新来改善在BHR中存储循环结束的分支指令评估的不良影响。以多种方式识别循环结束指令。

[0029] 在一个实施例中，分支预测方法包含响应于分支指令的性质而在分支指令执行时视情况抑制对BHR的更新。

[0030] 在另一实施例中，处理器包含：分支预测器，其可操作以预测对条件分支指令的评估；以及指令执行管线，其可操作以基于来自分支预测器的预测以推测方式取得和执行指令。所述处理器还包含：BHR，其可操作以存储对条件分支指令的评估；以及控制电路，其可操作以响应于分支指令的性质而抑制存储对条件分支指令的评估。

[0031] 在又一实施例中，可操作以响应于程序代码而产生指令的编译器或汇编器包含可操作以指示终止代码循环的条件分支指令的循环结束分支指令标记功能。

附图说明

[0032] 图1是现有技术分支预测器电路的功能方框图。

[0033] 图2是处理器的功能方框图。

[0034] 图3是执行分支指令的方法的流程图。

[0035] 图4是包含一个或一个以上最后分支PC寄存器的分支预测器电路的功能方框图。

具体实施方式

[0036] 图1描绘处理器10的功能方框图。处理器10根据控制逻辑14在指令执行管线12中执行指令。在一些实施例中，管线12可为超标量设计，其具有多个并行管线。管线12包含组织成管级的各种寄存器或锁存器16，以及一个或一个以上算术逻辑单元(ALU)18。通用寄存器(GPR)文件20提供包括存储器层级的顶部的寄存器。

[0037] 管线12从指令高速缓冲存储器(I-cache)22取得指令，其中由指令侧转译后备缓冲器(ITLB)24来管理存储器地址转译和许可。当在管线12中早期解码条件分支指令时，分支预测器26预测分支行为，并向指令预取单元28提供预测。指令预取单元28对于“采用的”分支预测在管线12中计算出的分支目标地址处或对于预测为“不采用”的分支在下一顺序地址处以推测方式从指令高速缓冲存储器22取得指令。在任一情况下，均将预取的指令加载到管线12中以用于推测性执行。

[0038] 分支预测器26包含分支历史寄存器(BHR)30、分支预测器表(BPT)32、BPT索引逻辑34以及BHR更新逻辑36。分支预测器26可额外包含一个或一个以上最后分支PC寄存器38，本文下文中对其进行更充分描述。

[0039] 从数据高速缓冲存储器(D-cache)40存取数据，其中由主转译后备缓冲器(TLB)42管理存储器地址转译和许可。在各种实施例中，ITLB24可包括TLB42的一部分的副本。或者，ITLB24与TLB42可集成。类似地，在处理器10的各种实施例中，I-cache22与D-cache40可集成或合并。I-cache22和/或D-cache40中的未中导致在存储器接口46的控制下存取主(芯片外)存储器44。

[0040] 处理器10可包含输入/输出(I/O)接口46，其控制对各种外围装置50的存取。所属领域的技术人员将认识到，处理器10的许多变化形式是可能的。举例来说，处理器10可包含用于I-cache22和D-cache40中的任一者或两者的第二层(L2)高速缓冲存储器。此外，特定实施例中可省略处理器10中描绘的功能块中的一者或一者以上。

[0041] 根据一个或一个以上实施例，通过防止循环结束分支破坏分支预测器26中的一个或一个以上BHR30来改进分支预测准确性。图3中将这个过程描绘成流程图。将条件分支指令解码(方框52)。确定分支是否为循环结束分支(方框54)。如果不是，那么更新BHR30以记录分支评估(方框56)，即，分支指令评估为“采用”还是“不采用”。执行接着分别在分支目标地址或下一顺序地址处继续(方框58)。如果分支不是循环结束分支，那么抑制更新BHR30以记录对循环结束分支指令的分支评估(如从方框54到方框58的路径所指示)。以此方式，循环迭代分支不会通过取代相关分支评估历史而破坏BHR30的内容。查询(方框54)将分支指令识别为循环结束分支指令，所述步骤可通过多种方式来实现。

[0042] 循环通过从循环结束处向后向循环开始处形成分支来迭代。根据一个实施例，假设每个分支目标地址小于分支指令地址或PC的条件分支指令(即后向分支)是循环结束分支指令，且防止其更新BHR30。这个实施例提供简化的优点。在BHR30更新时间，当分支指令实际上在管线中评估时将分支指令PC与分支目标地址(BTA)进行比较。如果BTA

[0043] 另一种检测循环结束分支的方式是辨别对同一分支指令的重复执行。在图4中描绘的一个实施例中，最后分支PC(LBPC)寄存器38存储其评估被存储在BHR30中的最后分支指令的PC。在简单循环的情况下，如果分支指令的PC与LBPC38匹配(也就是说，分支指令是所评估的最后分支指令)，那么假设分支指令是循环结束分支指令，且抑制对BHR30的进一步更新。如上文参看图1所论述，虽然图4描绘在任何给定实施方案中将LBPC38的内容与BHR更新逻辑36中的实际分支评估进行比较，但可将LBPC38与预测的分支评估进行比较，其中在错误预测的情况下对BHR30进行校正。这个实施例只存储循环的第一次迭代，只从BHR30中取代一个先前分支评估。这个实施例不需要编译器支持，且不需要在BHR30更新时间确定分支的方向。

[0044] 循环可含有一个或一个以上嵌套循环，或者可在循环内包含其它分支。在此情况下，可通过LBPC方法抑制内部循环使BHR30饱和；然而，外部循环结束分支仍然将被存储在BHR30中。在一个实施例中，可提供两个或两个以上LBPC寄存器38，其中将连续评估的分支指令的PC存储在相应的LBPC寄存器(LBPC0，LBPC1，...LBPCM)38中。如果分支指令的PC与LBPCN寄存器38中的任一者匹配，那么可抑制对BHR30的更新。

[0045] 也可由编译器或汇编器静态地标记循环结束分支指令。在一个实施例中，编译器产生只用于循环结束分支的特定类型的分支指令，例如“BRLP”。辨别BRLP指令，且当BRPE指令在执行管级中评估时决不更新BHR30。在另一实施例中，编译器或汇编器可例如通过在操作码中设定一个或一个以上预界定的位而在分支指令中嵌入循环结束分支指示。检测循环结束分支位，且当所述分支指令在执行管级中评估时抑制对BHR30的更新。对循环结束分支的静态识别通过将循环结束识别功能移动到编译器或汇编器中而减小硬件和计算复杂性。

[0046] 条件分支指令可具有许多性质，其中包含(例如)分支指令地址或PC、指令类型和操作码中是否存在指示位。如本文所使用，将分支操作的性质和/或与分支有关的程序的性质视为分支指令的性质。举例来说，分支指令PC是否与一个或一个以上LBPC寄存器38的内容匹配以及分支目标地址相对于分支指令PC是正向还是后向的，这些是分支指令的性质。

[0047] 虽然本文中已就本发明的特定特征、方面和实施例描述了本发明，但将了解，在本发明的广泛范围内可能有许多变化、修改和其它实施例，且因此，应认为所有变化、修改和实施例均在本发明的范围内。因此，应在所有方面均将当前实施例理解为说明性的而非限制性的，且希望属于所附权利要求书的意义和等效范围内的所有变化均包含在其中。