用于模拟显式子例行程序调用的分支预测行为的方法和设备

摘要

本发明揭示一种用于模拟显式子例行程序调用的分支预测行为的设备。所述设备包含：第一输入，其经配置以接收指令地址；以及第二输入。所述第二输入经配置以接收将所述指令地址描述为与对子例行程序的隐式子例行程序调用有关的预解码信息。响应于所述预解码信息，所述设备还包含加法器，所述加法器经配置以将常数加到所述指令地址以界定返回地址，从而致使所述返回地址存储到显式子例行程序资源，因此，促进了返回调用指令的后续分支预测。

说明书

技术领域

本发明大体上涉及管线式处理器的领域，且明确地说，涉及一种模拟显式子例行程序调用对隐式子例行程序调用的分支预测行为以便减少电力且增加管线式处理器的利用率的方法。

背景技术

微处理器在许多种应用中执行计算任务。为了允许更快的操作和/或通过软件改变而增加的性能，经改进的处理器性能几乎总是所需的。在许多内嵌式应用(例如，便携式电子装置)中，省电也是处理器设计和实施中的重要目标。

许多现代处理器使用管线式结构，其中循序指令在执行中重叠以增加总体处理器通过量。为了实现高性能，维持经过管线的平滑执行是关键的。大部分现代处理器还利用分层存储器，其中快速的芯片上高速缓冲存储器存储新近存取的数据和指令的本地拷贝。

真实世界的程序包含间接分支指令，其实际分支行为直到所述指令在执行管线深处被实际地评估时才被知晓。大部分现代处理器使用某种形式的分支预测，借此间接分支指令的分支行为在管线中早期被预测(例如，在提取或解码管式级(pipe stage)期间)。通过利用分支预测技术，处理器推测性地提取间接分支指令的目标，且重新导向所述管线以开始处理经推测性提取的指令。当实际分支目标在稍后管式级(例如，执行管式级)中被确定时，如果分支被误预测，那么必须从管线中冲洗经推测性提取的指令，且从正确的目标地址提取新的指令。响应于错误分支目标预测而预提取指令会不利地影响处理器性能和功率消耗。

间接分支指令的一个实例包含用于从子例行程序返回的分支指令。举例来说，来自子例行程序的返回调用可包含返回地址由寄存器的内容界定的分支指令。返回地址界定将在子例行程序完成之后提取的下一指令，且通常是在子例行程序最初从中调用的分支指令之后的指令。许多高性能结构指定供子例行程序返回中使用的特定通用寄存器，通常被称为链接寄存器。

为了方便起见，返回调用还可被称为分支返回指令。为了使处理器管线将分支预测用于分支返回指令，常规软件包含例如分支和链接指令的显式子例行程序调用以将返回地址记录到链接寄存器中。许多高性能实施例在处理分支和链接指令的解码级包含链接堆叠结构。将链接返回值推到此堆叠上，以便在对应的子例行程序返回时允许准确的分支预测。常规链接堆叠结构含有返回地址列表，以便支持流经管线的多个子例行程序调用，且支持多个等级的子例行程序调用的嵌套。随后，当子例行程序内的分支返回指令正被解码时，如果其它分支预测硬件命令处理器应重新导向管线，那么从链接堆叠结构读取返回地址，以在分支预测中用以预测目标地址。如果所述预测指示重新导向管线，那么管线开始从已从链接堆叠读取的返回地址中提取指令。

然而，存在旧版软件，其在调用子例行程序时未并入有常规分支和链接指令，且因此，其不能够利用链接堆叠结构。作为实例，参看含有可在ARM有限公司(ARM Ltd.)的兼容处理器上执行的码段的下表：

表1旧版码段。

MOV LR、PC与BR指令的组合为到达子例行程序的后续分支准备处理器。在此实例中，进行调用所针对的实际子例行程序开始于地址0x00990000处。MOV LR、PC指令指示应将程序计数器(PC)的内容复制到链接寄存器(LR)中。在例如ARM的一些指令结构中，程序计数器实际上被界定为当前指令地址加8个字节。在此界定的情况下，将PC的内容移动到LR会导致将返回地址(地址0x00899908)存储到链接寄存器中。在子例行程序结束时，从链接寄存器检索所述返回地址。更具体地说，在执行BX LR(分支返回指令)时检索所述返回地址。

在包含深管线且利用分支预测技术的现代处理器中，在不使用链接堆叠的情况下对分支返回指令进行解码时预测返回地址会由于各种原因而出问题。一个原因涉及微结构惯例，其不允许在管线的解码级期间存取例如链接寄存器的通用寄存器，因此排除了在分支预测时间使用链接寄存器的“当前”值对返回地址进行分支预测。即使可对此微结构惯例做出变化，现今的深管线也可能致使链接寄存器中所含有的数据对于预测目的来说是不可靠的。举例来说，在分支指令从针对返回地址做出预测的解码管式级流动到得出返回地址的实际分解的执行管式级所花费的时间中，后续分支指令可进入管线并重写链接寄存器，从而致使初始分支返回指令的返回地址的实际分解不同于所预测的返回地址。预测值与实际分解之间的此失配被称为分支目标误预测。分支误预测导致时间损失和功率损失，其两者均为沿不正确地预测的路径推测性地执行的结果。

在给定此旧版软件的渗透性(pervasiveness)和重写旧版软件以在调用子例行程序时利用常规分支和链接指令中所涉及的成本的情况下，存在对现今所开发的微处理器的需要，所述微处理器支持旧版软件且使所述旧版软件利用链接堆叠结构，以便在分支返回指令处于解码管式级时有效地预测返回地址。

发明内容

本发明辨识界定对子例行程序的隐式子例行程序调用的指令样式，且利用此辨识来设计用于利用显式子例行程序调用资源来允许分支预测对子例行程序的返回地址进行预测的方法和设备。

根据一个方面，揭示一种模拟显式子例行程序的分支预测行为的方法。所述方法包含：辨识指示对子例行程序的隐式子例行程序调用的指令地址；从所述指令地址计算返回地址；以及将所述返回地址存储到显式子例行程序资源。

另一方面涉及一种设备。所述设备包含：第一输入，其经配置以接收指令地址；以及第二输入。第二输入经配置以接收将所述指令地址描述为与对子例行程序的隐式子例行程序调用相关联的预解码信息。响应于所述预解码信息，所述设备还包含加法器，其经配置以将偏移加到指令地址，从而界定返回地址。所述加法器还经配置以将返回地址存储到显式子例行程序资源，从而促进返回调用指令的后续分支预测。

根据又一方面，揭示另一种设备。所述设备包括经配置以同时接收第一和第二指令地址以及相关联的预解码信息的第一和第二输入。所述设备进一步包括第一组加法器，其经配置以响应于指示第一或第二指令地址与对子例行程序的隐式子例行程序调用相关联的预解码信息而将偏移加到第一和第二指令地址以界定第一和第二结果。所述设备进一步包括用于从第一或第二结果中的一者选择返回地址的装置。

应了解，所属领域的技术人员从以下具体实施方式将容易明白本发明的其它实施例，其中本发明的各种实施例是作为说明而展示并描述的。如将认识到，本发明能够具有其它且不同的实施例，且本发明的若干细节能够在各种其它方面进行修改，而均不脱离本发明。因此，图式和具体实施方式应被视为本质上是说明性的，而非限制性的。

附图说明

图1是处理器的功能框图。

图2是遵循穿过图1中所说明的管线的指令流的时序图。

图3是单指令解码管式级的示范性部分。

图4是双指令解码管式级的一部分的示范性第一方面。

图5是图1的双指令解码管式级的一部分的示范性第二方面。

图6是说明在辨识隐式子例行程序调用时模拟显式子例行程序的分支预测行为的方法的流程图。

图7是展示图6中的区块610、620和630的进一步细节的流程图。

具体实施方式

图1描绘其中可使用本发明的方面的处理器100的功能框图。处理器100包含用于高速缓存新近处理的指令的指令高速缓冲存储器(I-高速缓冲存储器)110、用于在I-高速缓冲存储器110中未发现指令时存取存储器138的存储器接口136、用于执行从存储器138检索到的指令的有限解码的预解码逻辑电路128，以及用于响应于I-高速缓冲存储器110中的未中(miss)而将包含预解码位的指令数据写入到I-高速缓冲存储器110中的填充缓冲器逻辑电路130。预解码位与从存储器检索到的指令相关联，且含有描述所述指令的属性，例如，指令类型的指示。存储器138可位于处理器100上或处理器100外，且可包括层2(L2)存储器组件。

处理器100还包含：指令管线105，其用于处理指令的；以及分支预测电路132，其用于预测间接分支指令的目标地址且预测是否重新导向指令管线105以处理所述目标地址。如果分支预测电路132预测重新导向指令管线105，那么所述间接分支指令被称为已“预测为被采用(predicted taken)”。如果间接分支指令已“预测为被采用”，那么分支预测电路132预测间接分支指令的目标地址，且重新导向指令管线105以开始提取开始于所述目标地址的指令。

处理器100根据控制逻辑电路122而在指令管线105中处理指令。在一些实施例中，管线105可以是具有两个或两个以上平行管线的超标量设计。管线105包含各种管式级：指令高速缓冲存储器查找(IC)级102、指令数据对准(IDA)级104、解码(DCD)级106、指令列队(IQ)级108、第一寄存器存取(RACC1)级112、第二寄存器存取(RACC2)级114、保留站(RSV)级116，以及四个执行级(X1到X4)120A到120D。在一些实施例中，管式级一次可处理单个指令。在另一实施例中，管式级可同时处理两个或两个以上指令。应注意，在不限制本发明的范围的情况下，可将管式级加到管线105或从管线105减去。处理器100还包含通用寄存器(GPR)堆118，其包含(通过微结构惯例)可由管式级112、114和120A到120D存取的寄存器。

指令高速缓冲存储器查找(IC)级102尝试从I-高速缓冲存储器110检索指令。指令数据对准级104分析出多个指令以及与多个指令相关联的预解码信息。如果在I-高速缓冲存储器110中未发现指令地址，那么指令数据对准级104起始请求以从存储器138检索对应的指令。解码级106对指令进行完全解码。此外，除了常规功能之外，解码级106辨识显式子例行程序调用指令，且将返回地址写入到链接堆叠结构134中。此外，解码级106还辨识来自旧版软件的隐式子例行程序调用，且将返回地址存储到链接堆叠结构134中。链接堆叠结构134可以是被作为循环缓冲器管理的一组寄存器。返回地址是指令的在隐式子例行程序完成时管线105将重新导向的地址。将结合图3到图5的论述而更充分地描述解码级106的相干方面的结构和操作。

指令列队级108缓冲一个或一个以上指令，以便允许推测性提取在执行管线的中止期间继续。第一寄存器存取级112和第二寄存器存取级114从通用寄存器118检索一个或一个以上操作数(如可能为指令所需)。保留站级116允许指令等待写后读(read-after-write)冒险及其类似物被解决。执行级包含例如算术逻辑单元及其类似物的已知组件。执行级120A到120D执行指令。从执行级产生的结果被写入到GPR堆118。在执行级120A到120D期间，实际分支分解发生以确定在解码级106期间所做出的分支预测是否正确。如果实际分支分解不同于所预测的目的地，那么分支被称为已被误预测。

所属领域的技术人员将认识到，处理器100的大量变化是可能的。举例来说，处理器100可包含I-高速缓冲存储器110的第二等级(L2)高速缓冲存储器。另外，处理器100中所描绘的功能区块中的一者或一者以上可从特定实施例中省略。可驻存在处理器100中的其它功能区块(例如，翻译后备缓冲器、数据高速缓冲存储器及其类似物)与本发明的描述内容关系不大，且为了清楚起见而被省略。

图2是遵循穿过图1中所说明的管线105的指令流的时序图200。显式地说，时序图200中所追踪的指令流是如表1中所说明的旧版码段。出于本发明的目的，术语“隐式子例行程序调用”指代两个或两个以上指令的组合，所述指令的组合功能是设置为子例行程序调用作准备的寄存器且调用子例行程序。举例来说，参看表1，MOV LR、PC/BR组合中的两个指令界定隐式子例行程序调用。在此情况下，MOV LR、PC指令界定隐式子例行程序调用的开头，且BR指令界定隐式子例行程序调用的结尾。

时序图200的最初十一个行对应于管线105的级。列210A到210W对应于循序时序循环。出于阐释的目的，每一管式级每循环处理一个指令。然而，所属领域的技术人员应认识到，本发明的教示适用于多个循环管式级且适用于每循环能够处理多个指令的管式级。

由于图3和图4中所说明的解码管式级的方面，时序图200的行211对应于例如链接堆叠结构134的链接堆叠结构的内容。由于图5中所说明的解码管式级的方面，时序图200的行213对应于所述链接堆叠结构的内容。将结合图5的论述来论述行213。时序图200的行212对应于链接寄存器的内容。

一般来说，指令进入IC级102且传播到下一循环中的下一级。在215处，MOV LR、PC指令处于解码级106中。在所述时间点，解码级106辨识MOV LR、PC，且将返回地址MOV+8存储到链接堆叠结构中。出于命名的目的，MOV+8指代将偏移8加到MOV指令的地址。值8包含MOV指令的四个字节以及后续BR指令的四个字节，使得链接堆叠结构含有BR指令之后的循序指令的地址。如将结合图3到图4的论述而进一步论述，根据本发明的本教示的解码级将偏移8加到MOV指令的地址。如将结合图5的论述而进一步论述，根据本发明的本教示的替代性解码级将偏移4加到BR指令的地址。应注意，记号MOV+8和BR+4两者均指代地址0x00899908(返回地址)。在参考符号220处，链接堆叠结构将其内容展示为MOV+8。当BR指令由解码级106处理时，分支指令的目标(子例行程序的开头)被预测且在下一循环中由管线提取。在参考符号219处，LDA指令(子例行程序的开头)由IC级102处理。由于管线105由于分支指令的预测的缘故而已被重新导向以提取LDA指令，所以地址BR+4和BR+8处的指令被从管线冲洗。循序地在LDA指令之后的指令接着被提取到管线105中。

在参考符号225处，分支返回指令BX由解码级106处理。解码级106以链接堆叠结构的内容来调用分支预测电路132以预测返回地址。在另一实施例中，分支预测电路132对链接堆叠结构进行读取。在任一情况下，分支预测电路132利用链接堆叠结构来预测返回地址，且在参考符号230处，管线被重新导向以提取返回地址0x00899908处的指令。一旦被利用，行211列210J处的MOV+8条目就从链接堆叠结构移除。

在针对隐式子例行程序调用不使用链接堆叠的常规处理器中，当子例行程序返回指令处于DCD级中且尝试预测时，链接寄存器(LR)的值本身可能尚未被及时地更新以用于循环210I中。如图中所示，LR直到循环210M时才被更新，循环210M比将被要求在DCD级中使用此值的循环迟四个循环。参考符号235处的循环210M在进行分支返回地址的预测和提取的循环210I之后。因此，在常规处理器中，对存储在链接寄存器中的分支返回指令的分支预测可能是不可靠的。

图3到图5说明本发明的与例如解码管式级106的解码管式级有关的替代性方面。这些替代性方面为隐式子例行程序调用以及常规分支和链接指令寻址用于写入到链接状态结构的路径。应注意，其它路径包含于解码管式级中，例如，指令集中的其它指令的路径，但所述路径与本发明的此方面无关且因此未在图式中描绘。

图3是单指令解码管式级的示范性部分300。单指令解码管式级的部分300可合适地安置在解码级106中。单指令解码管式级的部分300包含指令地址310和与指令地址310相关联的预解码位315。指令地址310的大小为32个位长，且预解码位315的大小为8个位长。应注意，本发明的方面预期指令地址或预解码位的各种大小及其相应的位位置。指令地址310和预解码位315输入到解码管式级的部分300，且可驻存在相同或不同的数据寄存器中。

预解码位315包含与对应于指令地址310的指令有关的信息，且由预解码逻辑电路128确定。预解码位315指示对应指令是否为例如表1中所列出的MOV/BR组合中的MOV LR、PC指令的隐式子例行程序调用的开头。可以各种方式对预解码位315进行编码，所述方式包含对特定位或预解码位315的组合进行编码，以指示指令地址310指代隐式子例行程序调用的开头或常规分支和链接指令。在另一实施例中，指令的操作码(opcode)可用于将隐式子例行程序调用以及常规分支和链接指令与指令集中的其它指令区分开。

解码管式级的部分300进一步包含加法器/多路复用器组合330。加法器/多路复用器组合330包含加法器325A到325B、多路复用器320和链接堆叠结构134。在指令地址310指代常规分支和链接指令的情况下，加法器325A将常数4加到指令地址。在指令地址310指代隐式子例行程序调用的开头的情况下，加法器325B将常数8加到指令地址。通过多路复用器320，预解码位315选择将哪一经递增地址或返回地址写入到链接堆叠结构134(如果存在的话)。参看表1，其说明偏移8以反映返回地址的位置在MOV指令之后八个字节。在常规分支和链接指令中，返回地址在分支和链接指令之后四个字节。尽管未图示，但可视组成隐式子例行程序调用的指令的数目和组成隐式子例行程序调用的指令中的每一者的大小而添加其它加法器或可更换图3到图5中所说明的加法器。

图4是双指令解码管式级的一部分400的示范性第一方面。双指令解码管式级的部分400可合适地安置在解码级106中。双指令解码管式级的部分400包含两个指令地址410A到410B(与其相应的预解码位407A到407B同时被接收到)，以及两组加法器/多路复用器组合425A到425B。指令地址410A到410B和预解码位407A到407B被输入到解码管式级的部分400，且可驻存在相同或不同的数据寄存器中。

例如MOV LR、PC指令的地址等隐式子例行程序调用的开头可在任一指令地址410A或410B中发现。按照惯例，指令地址410A或DCD0在程序次序上为第一，且指令地址410B或DCD₁在程序次序上为第二。当界定例如MOV LR、PC指令的地址等隐式子例行程序的开头的指令的地址位于指令地址410A中时，加法器/多路复用器425A的输出是有效的，且此经递增地址被写入到链接堆叠结构134。如果隐式子例行程序的开头的地址是指令地址410B，那么加法器/多路复用器425B的输出是有效的，且此经递增地址或返回地址被写入到链接堆叠结构134。当隐式子例行程序被辨识出时，图3和图4中所说明的解码管式级的方面在界定隐式子例行程序的指令开始时写入到链接堆叠结构134。

图5是双指令解码管式级的一部分500的示范性第二方面。双指令解码管式级的部分500可合适地安置在解码级106中。双指令解码管式级的部分500响应于接收到界定隐式子例行程序调用的最后一个指令地址而将返回地址写入到链接堆叠结构134。返回参看图2，例如，在对MOV/BR组合的分支指令进行解码之后一个循环，链接状态结构213在参考符号221处由双指令解码管式级的部分500写入。因此，如所说明，在参考符号221处，BR+4的值被写入到链接状态结构213。

双指令解码管式级的部分500包含两个指令地址510A到510B(与其相应的预解码位507A到507B同时被接收)。指令地址510A到510B(DCD₀和DCD₁)及其相应的预解码位507A到507B(PDCD₀和PDCD₁)输入到解码管式级的部分500，且可驻存在相同或不同的数据寄存器中。

解码管式级的部分500进一步包含选择/启用逻辑电路510、旗标设置逻辑电路515、加法器525A和525B以及多路复用器520。旗标设置逻辑电路515设置旗标530且使旗标530复位。旗标530追踪隐式子例行程序调用的开头是否已在地址510A或地址510B中被辨识出。如果同时接收到指示隐式子例行程序调用的开头和结尾的两个地址，那么不利用旗标530。在隐式子例行程序由MOV LR、PC/BR组合界定的情况下，当指令MOV LR、PC的地址驻存在可为DCD₀(当DCD₁无效时)或DCD₁的最后有效解码时隙中时，利用PDCD₀和PDCD₁位的旗标设置逻辑电路515设置旗标530。

选择/启用逻辑电路510确定DCD₀或DCD₁是否含有隐式子例行程序调用的结尾的地址。如果隐式子例行程序调用的结尾处于DCD₀中，那么加法器525A将4加到DCD₀中的地址，以便计算隐式子例行程序调用的返回地址。如果隐式子例行程序调用的结尾处于DCD₁中，那么加法器525B将4加到DCD₁中的地址，以便计算返回地址。如果隐式子例行程序调用的结尾存在于DCD₀或DCD₁中，那么选择/启用逻辑电路510产生选择信号540，且如果这样的话，那么选择将哪一经递增指令地址535A或535B写入链接堆叠结构134中。

为了确保链接堆叠结构134不会被不必要地写入，选择/启用逻辑电路510从分支预测电路132接收分别对应于指令地址DCD₀和DCD₁的预测为被采用的信号550A和550B作为输入。如果隐式子例行程序调用在数据寄存器505中被辨识出，且隐式子例行程序已由分支预测电路132预测为被采用，那么选择/启用逻辑电路510向链接堆叠结构134产生写入启用信号545，以启用链接堆叠结构134以被写入。如果隐式子例行程序调用被辨识出但被预测为未被采用，那么选择/启用逻辑电路510不向链接堆叠结构134产生写入启用。以此方式，预测为未被采用的隐式子例行程序调用不会导致写入到链接堆叠结构134。应注意，尽管本发明在解码级管线中描述隐式子例行程序调用的辨识和对的链接堆叠结构的写入，但所属领域的技术人员将认识到，本发明的这些方面可在处理器管线的已确定了预解码位且已进行了分支预测的任何级中实践。

图6是说明在辨识隐式子例行程序调用时模拟显式子例行程序的分支预测行为的方法600的流程图。在区块610处，在处理器管线中辨识指示对子例行程序的隐式子例行程序调用的指令地址。在区块620处，从所述指令地址计算返回地址。如果隐式子例行程序调用包括两个或两个以上指令，那么加到所述指令地址的偏移量取决于各种因素，包含辨识是在隐式子例行程序调用的开头还是结尾进行以及组成隐式子例行程序调用的指令的大小。在区块630处，将返回地址存储到例如链接堆叠结构134的显式子例行程序资源。如图3到图5中所描述，区块610、620和630可在解码级106期间进行。

在区块640处，处理器管线处理与被调用的子例行程序相关联的指令。举例来说，参看表1，在区块640处，将处理指令地址0x00990000到0x00990008。在区块650处，响应于指示来自例如表1中的0x00990008 BX的子例行程序的返回调用的分支指令，从显式子例行程序资源读取返回地址。另外，在区块650处，将处理器管线重新导向到从显式子例行程序资源读取的返回地址。当返回调用指令处于解码级106中时，以与响应于对由常规分支和链接指令调用的子例行程序的返回调用而检索返回地址时相同的方式，从链接堆叠结构134检索返回地址。一旦检索到返回地址且返回调用指令被预测为被采用，那么处理器管线提取所述返回地址，从而有利地允许如图2中所说明的返回地址的早期提取。

图7是展示图6中的区块610、620和630的进一步细节的流程图700。在区块710处，读取与指令地址相关联的预解码位。在区块720处，流程图700确定预解码位是否指示隐式子例行程序调用。如果预解码位指示隐式子例行程序调用，那么区块730将偏移加到指令地址。在区块740处，将经递增地址存储到链接堆叠结构中。在区块750处，管线过程继续以常规方式来处理指令。如果预解码位不指示隐式子例行程序调用，那么区块720进行到其中处理器管线继续以常规方式来处理指令的区块750。

结合本文所揭示的实施例而描述的各种说明性逻辑区块、模块、电路、元件和/或组件可用通用处理器、数字信号处理器(DSP)、专用集成电路(ASIC)、现场可编程门阵列(FPGA)或其它可编程逻辑组件、离散门或晶体管逻辑、离散硬件组件或其经设计以执行本文所描述的功能的任何组合来实施或执行。通用处理器可以是微处理器，但在替代方案中，处理器可以是任何常规处理器、控制器、微控制器或状态机。处理器还可实施为计算组件的组合，例如，DSP与微处理器的组合、多个微处理器、结合DSP核心的一个或一个以上微处理器，或任何其它此类配置。

结合本文所揭示的实施例而描述的方法可直接体现于硬件中、由处理器执行的软件模块中或二者的组合中。软件模块可驻存在RAM存储器、快闪存储器、ROM存储器、EPROM存储器、EEPROM存储器、寄存器、硬盘、可移除盘、CD-ROM或此项技术中已知的任何其它形式的存储媒体中。存储媒体可耦合到处理器，使得处理器可从存储媒体读取信息并将信息写入到存储媒体。在替代方案中，存储媒体可与处理器成一体式。

虽然在实施例的情况下揭示了本发明，但将认识到，所属领域的技术人员可使用与以上论述内容以及所附权利要求书一致的许多种实施方案。