22. 分支和跳转(所有处理器)

奔腾家族的处理器试图预测跳转的位置，条件跳转是否发生。如果预测正确，通过在跳转发生之前读取后续指令进入管道并解码，能够节省一大笔时间；如果预测失败，管道被清洗，花的代价取决于管道的长度。

预测基于分支目标缓存部件(Branch Target Buffer ，简称 BTB )，它为每一个分支存了历史记录或跳转指令，使预测基于每条指令执行的历史记录。

BTB组织得像一个组相联cache，那里新的表项按照伪随机替换算法分配。

为了优化代码，重要的是要减少预测失败的代价。 这需要很好地理解分支预测的工作机制。

分支预测机制在任何地方都没有很好地描述，包括Intel的手册。

因此我这里做了详细的描述。 这些信息基于我的研究(在 PPlain 的 Karki Jitendra Bahadur 的帮助下)。

接下去，我要用术语"控制转移指令"代替所有能够使ip变化的指令，包括条件\非条件跳转，直接\间接跳转，近\远，跳转，调用，返回。

所有这些指令都要预测。

22.1 PPlain 的分支预测

PPlain的分支预测机制比其它三种处理器复杂得多。

关于这个课题，在Intel文档或其它地方的信息直接误导读者，根据这些文档会写出不够理想的代码。

22.1.1 BTB的组织（PPlain）

PPlain有一个分支目标缓存(BTB)，它能缓存256条跳转指令。

该BTB像一个4路的组相联cache，每路有64项。 这意味着BTB不能储存4个以上组值相同的项。
和数据cache不同的是，BTB用了伪随机数替换算法，这意味着一个新项不一定替换具有相同组值的最近最少使用的项。 组值的计算方法后面介绍。

每个BTB项存储目标跳转地址和预测状态，可能有四种状态:

状态0:强烈预言不发生

状态1:弱预言不发生

状态2:弱预言发生

状态3:强烈预言发生

在状态2或3，一个跳转指令被预测为将要发生；在状态0或1，被预测为不发生。

状态变化就像一个2位的计数器，在发生后，状态值增加；在不发生后，状态值减少。 计数器是饱和计数而不是环绕计数，因此到了0，它不再减少；到了3，它不再增加。

看来，应该预测得蛮准，因为要使预测结果发生变化(比如以前预言不发生，现在变成预言发生)，分支指令可能要两次背离它以前的行为。

然而，该机制的一大弱点是BTB表项处于状态0意味着该BTB表项是没有用的。 因此处于状态0的BTB表项有了也等于没有。

这意义在于，如果一个分支指令没有BTB表项，那么它被预测为不发生。 这改善了BTB的利用，因为一般地，那些很少发生的分支指令不会占用BTB表项。

现在如果有一条件转移指令，它没有BTB表项。那么一个新的项会产生，该项的初值总是被置为状态3。这意味着它不可能从状态0到状态1(除了后面讨论的一种特殊情况)。如果发生，从状态0你只能到状态3?。如果不发生，分支被移出BTB表。

这是个严重的设计缺陷。通过将状态值为0的表项扔出BTB，并且总是将新的项置为状态3，设计者显然只优先考虑把无条件跳转和经常发生的分支指令的第一次运行代价最小化，而不顾这严重破坏了该机制的基本思想，降低了内部小循环的性能。

这会使得一个经常不发生的分支指令必须经过三次预测失败——和一个经常发生的分支指令一样多(显然，Intel工程师们没有注意到这个缺陷，直到我公开了我的发现)。

为了研究这个不对称，你可以组织你的分支指令，使它们发生的概率大于不发生的概率。

看这个if-then-else语句:

TEST
EAX，EAX JZ A

<分支1>

JMP E

A: 　　<分支2>

E:

如果分支1的概率比分支2大， 分支2很少连续执行2次，那么你可以交换这两个分支，这样JA A指令发生的概率就大于不发生的概率了，使相应的BTB表项进入状态3，这样可以减少预测失败：

TEST EAX，EAX

JNZ A

<分支 2>

JMP E

A: 　<分支
1>

E:

(这与Intel的指南手册中推荐的完全相反)。

有理由将经常执行的分支放在发生的位置，然而：

1. 把很少执行的分支远离你的代码底部却有利于改善指令cache的利用。
2. 使很少发生的分支指令大多数时间不在BTB内，可能改善BTB的利用。
3. 如果一条分支指令因为其它分支指令加入而被赶出BTB的话，它会被预测为不发生。
4. 只有PPlain机上存在不对称的分支预测。

然而循环式思维是有点多虑了，因此我仍然推荐使跳转指令的发生概率大于不发生。
除非分支2使用概率太小了，那么分支预测的失败可以忽略了，那么考虑Intel的推荐。

同样的，你需要完善地组织底部有分支指令的循环，就像下面的例子：

MOV ECX， [N]

L:
MOV [EDI]，EAX

ADD EDI，4

DEC ECX

JNZ L

如果N很大，那么JNZ指令会大量地发生，不可能有两次连续的不发生。

考虑这样一种情况——每两次发生一次。
转移指令第一次进入BTB项的时候是状态3，然后就会在2和3之间颠簸。 这样它每次都被预测为发生，导致50%的预测失败。 假定现在它背离了规律，有了一次意外的不发生。跳转模式如下:

01010100101010101010101, ０表示不发生, 1表示发生。
    ^

意外的不发生用^表示。　在这个事变之后，BTB表项将在1和2之间颠簸，导致100%的预测失败。　这个不幸的模式将一直继续，直到又一个0101的背离发生。　这是这个分支预测机制的最坏情况了。

22.1.2 BTB 记录的是前一个指令对的U管道指令的地址

BTB机制计算的是指令对，而不是单条指令。 因此，为了分析BTB表项存了什么地址，你必须知道指令的配对情况。
对于任何转移指令，BTB表项总是记录前一个指令对的U管道指令的地址(不配对的指令也看作一个"指令对")。 比如:

SHR EAX，1

MOV EBX，[ESI]

CMP EAX，EBX

JB L

这里SHR指令与MOV指令配对，CMP与JB配对。 因此对于JB L指令，BTB表项记录了SHR EAX，1的地址。
当到达这个BTB表项并且它处于状态2或3，Pentium会读出BTB表项中的目标地址，加载L之后的指令进入流水线。 这一步在分支指令 JB L被解码之前就已发生，因此对于分支预测，Pentium只依赖BTB中的信息。

你应该知道，指令在第一次执行的时候很少配对的(见第八章)。

如果上述的指令完全不配对，BTB表项会记录CMP指令的地址，而这对于下一次执行（此时指令是配对的）显然是错的。

然而，多数情况下PPlain足够聪明，它一般不会对从没使用过的"指令对"分配BTB表项。

因此要到第二次执行，才会有BTB表项的分配；推论是要到第三次执行，才会有分支预测(不过例外的是，如果第二条指令是单字节指令，那么在第一次执行的时候，你就会得到一个BTB表项，而在第二次执行的时候这个表项是无效的。

但既然这回BTB表项记录的指令将发送到V管道，这将被忽略而不会带来惩罚，因为BTB表项只读U管道的指令)。

一个BTB表项的id是它的组号，等于它记录的地址的0-5位。

6-31位也存入BTB做为标志位。 地址差为64字节的倍数的地址将拥有相同的组号。 最多允许有四个BTB表项拥有相同的组号。

如果你想检查是否你的转移指令争用同一个BTB表项，你必须比较它的前一个指令对中U管道指令地址的0-5位。 这很

要命的，我从来没有见过有人这么干过，也没有什么工具可以帮你干这件事。

22.1.3 连续的跳转(PPlain)

当跳转预测失败的时候，流水线被清洗。
如果下一个执行过的指令对也包括转移指令，PPlain不会加载它的跳转目标。 因为在流水线被清洗的时候不能加载新的跳转目标。
结果是不顾第二个转移指令的BTB表项状态，它被预测为不发生。
因此，如果第二个转移是发生的，你又会得到惩罚，哪怕事实上对于第二个跳转指令，BTB表项得到了正确的更新。
如果你有一个很长的转移指令的链，并且第一个转移指令预测失败，那么流水线会不断地刷新，在此其中如果没有不发生的"指令对"，你就会每个转移指令都预测失败。
最极端的例子是一个跳转至它本身的循环: 每次叠代都会得到预测失败的惩罚。

连续的转移指令带来的问题还不止这个。
再一个问题是如果你有BTB表项和属于它的转移指令之间的另一转移指令，如果第一个转移指令跳转到其它地方，奇怪的事情发生了。 看这个例子:

SHR EAX，1

MOV EBX，[ESI]

CMP
EAX，EBX

JB L1

JMP L2

L1: 　　MOV EAX，EBX

INC EBX

当JB L1不发生的时候，对于JMP L2，你会得到一个附上CMP EAX，EBX地址的BTB表项。 但如果JB
L1发生时情况又如何呢？在这个时候JMP L2的BTB表项已经被读到，但处理器不知道下一个指令对不包括转移指令，因此它把指令对MOV EAX，EBX /INC
EBX预测为跳转到L2。 预测非转移指令为跳转的惩罚是3个时钟周期。 JMP L2的BTB表项的状态值减1，因为它被应用于不发生跳转的指令上。
如果我们不断在循环中跳转到L1，JMP L2的BTB表项状态会被减为1和0。 于是问题一直出现，直到某一次JMP L2被执行。

预测非转移指令为跳转的代价仅仅发生在跳转至L1被预测到的情况下。
如果JB L1是预测失败的跳转，那么流水线被清洗，我们不会像前面那样加载L2这个错误目标。所以这回我们不会有预测非转移指令为跳转的惩罚，但JMP
L2的BTB表项状态值还是减小。

现在假定我们把 INC EBX 指令替换为另一个jump指令。 那么这个jump指令会用和JMP
L2相同的BTB表项(该表项预测跳转到L2)，该表项可能会预测到错误的目标而带来惩罚(除非这个jump指令碰巧也以L2为目标)。

总结一下，连续的转移指令可能导致下面问题:

*如果前一个转移预测失败，流水线被刷新，无法加载下一个转移指令的转移目标(强制预测为不发生)

*BTB表项可能被错误地用于非转移指令，并且预测它们是跳转的。

*上述的一个推论是:一个被错误应用的BTB表项的状态值会减小，可能到以后真正属于它的跳转要发生它却预测不发生。
由于这个理由，甚至无条件跳转的指令都会被 预测为不发生。

*两个很近的jump指令可能会共用一个BTB表项，导致预测到错误的目标。

所有这些混乱会带给你许多惩罚。
因此你要明确避免在一个随机转移(不太好预测的)的指令的后面，和它转移目标的后面紧跟一个包括转移指令的指令对(两条转移指令之间至少要间隔两条其它指令)。

一个实例:

　　　　CALL P
　　　　TEST EAX，EAX
　　　　JZ L2
L1： 　 MOV [EDI]，EBX
　　　　ADD EDI，4
　　　　DEC EAX
　　　　JNZ L1
L2： 　 CALL P

看上去这似乎是一段"优美的"代码:一个过程调用，当计数不为0的时候来个循环，再调用过程。你能发现多少问题呢?

首先，我们注意到P过程在两个不同的位置被调用。
这意味着P的返回地址一直在变，从而，对P的返回指令总是预测失败。

现在假设EAX是0。而因为P过程返回的预测失败导致的流水线刷新，使得该跳转到L2，却无法加载它的目标地址。
然后，因为JZ L2预测失败而刷新，第二个P调用又无法加载它的目标地址。
我们就进入了这样一个"境界":因为第一个jump预测失败，连续的jump导致流水线不断刷新。 JZ
L2的BTB表项存储P的返回指令的地址，这个BTB表项会被错误地应用于第二个P调用后的任何指令。
但这倒不会带来惩罚，因为第二个返回的预测失败流水线被刷新了。

现在我们考虑EAX非0的情况:因为刷新，JZ L2一直被预测为不发生。 第二个P调用的BTB表项记录TEST
EAX，EAX的地址。 这个表项会被错误地用于MOV/ADD指令对，预测它跳转到P。 这引起刷新，阻止JNZ L1加载它的目标。
如果我们以前执行过这里，第二个P调用会有另一个附着DEC EAX地址的BTB表项。
在第二、第三次叠代后，这个表项也被错误地应用到MOV/ADD指令对，直到它的状态减为1或0。 这种情况是在第二次叠代的时候没有惩罚，因为JNZ
L1的预测失败导致了刷新，阻止了错误目标的加载。 但在第三次叠代的时候有惩罚。 后续的叠代没有惩罚，但因为上述情况的存在，JNZ
L1一直预测失败，刷新会阻止P调用加载它的目标地址。 直到P调用的BTB表项因为几次错误的应用而被废除。

我们可以通过插入一些NOP，分开所有连续的转移来改进代码:

CALL P

TEST EAX，EAX

NOP

JZ L2

L1: 　　MOV [EDI]，EBX

ADD
EDI，4

DEC EAX

JNZ L1

L2: 　　NOP

NOP

CALL P

虽然额外的NOP花费2个时钟周期，但节省得更多。 此外，JZ
L2这回移入了U管道(因为CALL进入V管道)，这样当预测失败的时候，代价就由4个时钟周期减为3个时钟周期。 只剩的问题就是P过程的返回地址一直会预测失败。
要解决的话，只有用内联宏来代替P过程的调用(如果你的CPU指令cache足够大的话)。

通过这个例子，你懂得了应该仔细地寻找连续的转移指令然后考虑是否可以通过插入一些NOP节省时间。
另外，你看到了一些必然预测失败的情况，比如循环退出的时候，当一个被不同位置调用的过程返回的时候。
当然，如果你有一些有用的代码可以插入，那么应该选择有用的代码而不是NOP。

多分支(case: 状态)既可以用树型的大量转移指令实现，也可以用跳转表实现。
如果你选择了树型的转移指令，那么你必须用一些NOP或其它指令隔开连续的转移指令。因此在PPlain上，跳转表可能是一个更好的解决方案。
跳转地址表应该放在数据段，决不能放在代码段!

22.1.4小循环(PPlain)

在小循环中，你经常以很短的时间间隔重复访问同一个BTB表项。 这不会引起延迟。
因为PPlain不知怎么从流水线上开了一个"后门": 它能在写回BTB之前得到最近一次跳转的状态值，而不是等待BTB表项的更新。
该机制对用户几乎是透明的，但有时它会产生有趣的效果: 如果状态0来不及写回BTB，你会看到分支预测的状态总是从0到1，而不是3。
这在一个循环小于4个指令对时发生。
在只有两个指令对的循环中，你可能会在连续两次叠代中，使用不是来自BTB的状态0；在如此小的循环中，甚至会偶然地用两次以前叠代的状态值，而不用最近的一次来预测。
一般来说，这些有趣的效果在执行时不会带来什么副作用。

22.2 PMMX， PPro， PII and PIII的分支预测

22.2.1 BTB的组织(PMMX，PPro，PII和PIII)

PMMX的分支目标缓存(BTB)有256个表项，组织成16路*16组。
每个表项用属于它的转移指令的最后一个字节的地址的2-31位作为ID。 2-5位作为组值，6-31位存入BTB中作为标记。
两条地址相隔64字节的转移指令将有相同的组值，可能会被踢出BTB表。 但因为每组有16路，因此不会经常发生这种事情。

PPro，PII和PIII的分支目标缓存(BTB)有512个表项，组织成16路*32组。
每个表项用属于它的转移指令的最后一个字节的地址的4-31位作为ID。 4-8位作为组值，并且所有的4-31位都存入BTB作为标记。
两条地址相隔512字节的转移指令将有相同的组值，可能会被踢出BTB表。 但因为每组有16路，因此不会经常发生这种事情。

对于任何控制转移指令，PPro，PII和PIII在它第一次执行的时候就会分配BTB表项。
而在PMMX上，是在转移指令第一次发生的时候分配表项，没发生过的分支指令不进入BTB表，一旦它发生以后，哪怕它以后一直是不发生，它也驻留在BTB表中。

在另一条拥有相同组值的转移指令需要一个BTB表项的时候，原来的表项被踢出BTB。

22.2.2 预测失败的惩罚(PMMX，PPro，PII和PIII)

在PMMX上，U管道上执行的条件jump指令(JXX)预测失败的代价是4个周期，在V管道上是5个周期。
其它的转移指令都是4个周期的惩罚。

在PPro，PII和PIII上，因为管道比较长，预测失败的代价很大，一般需要10-20个时钟周期。
因此在PPro，PII和PIII上的程序要格外留意那些不大好预测的分支。

22.2.3 条件跳转的模式识别(PMMX，PPro，PII和PIII)

这些处理器有先进的模式识别机制，能够正确预测有规律的分支指令，比如每四次叠代来一次发生，其它三次是不发生。

事实上，它们能够预测所有长度不超过5的模式的发生和不发生，和许多更长的模式。

该机制号称"两级自适应分支预测模式"，由 T.-Y.Yeh 和 Y.N.Patt 发明。
它以前面描述的PPlain上的2位计数器模式为基础(但没有2位计数器那样不对称的缺陷)。
2位计数器是在跳转发生时状态值增加，在不发生时减少；在到达3或0时饱和；分支指令在相应的计数器值是2或3时被预测为发生，0和1时预测为不发生。现在通过在每一个BTB表项中有16个这样的计数器获得了大大的改进。
参考分支指令最近4次的执行历史，从16个计数器中选出1个。 比如，分支指令发生一次然后不发生三次，你会得到历史位串1000(1=发生，0=不发生)。
这就使得CPU下一次预测用计数器8(1000b=8)，并且以后更新计数器8。

如果1000序列总是发生，计数器8将很快到达它最大状态值3，这样它将一直预测1000序列。
要两次背离这个模式才会改变预测结果。 重复模式100010001000使得计数器8的状态值是3，计数器1，2，4的状态值为0。
另外12个计数器不用。

22.2.4 可完美预测的模式(PMMX，PPro，PII和PIII)

如果某个长度大于5的模式串中任何一个4位的子串都是唯一的，那么这个模式串能被完美地预测。
下面列出了能被完美预测的模式串:

看了这个表，你应该意识到如果一个模式串能被正确地预测，那么它的回文串(反过来读)和补串也能被正确预测。
比如，我们发现了模式0001011，其回文串是:1101000，补串是1110100，补串的回文串是0010111。 这四个串都可预测。
小循环左移一位得到:0010110，这不是一个新的模式，仅仅是同一个模式的小循环移位版。 所有由上表中的模式经过回文，取补，小循环移位得到的模式都能识别。
至于明确的理由这里没有给出。

在BTB表项分配之后，模式识别机制学习一个规律化的模式需要两个阶段。 学习过程中预测失败的模式不可再生。
这可能是因为BTB表项包括了一些分配之前的东西。既然BTB表项是随机分配的，在初始化学习过程中很少有机会去预测。

22.2.5 处理背离规律模式的情况(PMMX，PPro，PII和PIII)

分支预测机制还能够完善地处理"几乎有规律"的模式，和背离规律模式的情况。它不仅学习规律化的模式的样子，还学习规律化的模式发生背离的情况。如果背离也有相同的模式，它会记住背离的模式，这样背离的预测失败只发生一次。

比如:

0001110001110001110001011100011100011100010111000
                   ^                   ^

这个序列中，0意味着不发生，1意味着发生。
机器学习到重复模式是000111。 第一次背离是一个0，用^标出。
在这个0以后的三次跳转可能预测不到了，因为它还没学习到0010，0101，1011后会发生什么。
在同样的意外发生1次或2次后，它学习到0010后是个1，0101后是个1，1011后是个1。
这意味着相同类型的意外最多发生两次，经过一次预测失败，它就学会处理这类意外。

对于两个不同的规律化模式的切换，该机制也很有效。
比如，我们已经重复了000111模式(长度为6)很多次，然后重复01模式(长度为2)很多次，然后又回到000111模式的时候，它不需要再学习000111模式，因为000111序列所用的计数器在01期间没有被改过。
在两个模式之间交替的几次后，它还会懂得处理模式的变换，对于每次模式切换，代价只有一次预测失败。

22.2.6不能完美预测的模式(PMMX，PPro，PII和PIII)

最简单的不能被完美预测的模式是每六次有一次发生。该模式是:

000001000001000001
 ^^    ^^    ^^
 ab    ab    ab

0000序列总是跟在一个0(用a标出)和一个1(用b标出)后面。 这使得计数器0一直在上上下下。
如果计数器0从状态0或1开始，那么它会一直在0和1之间交替，b位置将一直发生预测失败；如果计数器0从状态3开始，那么它会一直在2和3之间交替，a位置将一直发生预测失败。
最坏的情况是它从状态2开始，它会不幸在1和2之间交替，我们在a和b处都会预测失败(这有点像前面说的PPlain的最坏情况)。
我们会从哪个状态开始取决于该转移指令的BTB表项分配之前的历史。 因为随机分配，所以我们无法控制。

为了避免每次循环有两个预测失败的最坏情况，理论上我们可以给CPU一个专门设计的分支序列，使它的计数器值为理想的状态，然而，不推荐这个办法，因为考虑到额外代码的开销，而且不管我们在计数器中放入什么信息，在以后有中断或任务切换的时候仍然会丢失。

22.2.7　完全随机的模式(PMMX，PPro，PII和PIII)

在完全没有规律的序列下，强大的模式识别机制也有小的缺点。

下面的表格列出了在完全随机的跳转发生/不发生序列下的预测失败率:

预测失败率比没有模式识别机制略高。
因为处理器在毫无规律的序列里仍然在试图找重复的模式。

22.2.8 小循环(PMMX)

在小循环下，PMMX的分支预测是不可靠的，因为模式识别机制在又一次碰到分支指令之前来不及更新它的数据。
这意味着通常能够完美预测的简单模式也不能预测了。然而，正常情况下不能识别的模式，能在小循环下完美地预测。
比如，一个总是循环6次，底部有一个分支指令的循环将有111110的模式。 这个模式在正常情况下总得有1到2次预测失败，但在小循环里不会有预测失败。
对于总是循环7次的小循环也是如此。 大多数其它循环次数的循环作为小循环都比正常情况下预测得差。 这意味着叠代6或7次的循环更适合做成小循环，其它情况下不适合。
如果需要把循环做大，你可以将它展开。

判断在PMMX上的一个循环是否是小循环，你可以遵循拇指法则:给循环中的指令计数。 如果小于等于6，该循环是小循环。
如果有多于7条指令，你就能保证模式识别的功能正常了。 相当奇怪的是，各条指令用多少时钟周期，有没有延迟，是否配对都无所谓。
复杂的整形指令不计在内(复杂的整形指令是指不能配对的(NP)整形指令，通常需要多余一个周期来执行)，一个可以有许多复杂的整形指令而在行为上仍是一个小循环。
复杂的浮点指令和MMX指令也计为1条指令。 注意，该法则只是启发性的，并非完全可靠。 重要的是实验测试。
在PMMX上，你可以用性能监控器35H为分支预测的失败计数。 测试结果也是不确定的，因为分支预测的结果取决于BTB表项分配之前的历史记录。

在PPro，PII和PIII上小循环的预测是正常的，因为每次叠代至少要花去2个时钟周期用于更新数据。

22.2.9 间接跳转和调用(PMMX，PPro，PII和PIII)

间接跳转和调用没有模式识别机制，对于一个间接跳转，BTB
只能记住一个目标。它只是简单地预测到达与上一次相同的目标。

22.2.10 JECXZ 和 LOOP(PMMX)

在PMMX上，这两个指令没有模式识别。 它们被简单地预测与最近一次执行的目标相同。
因此PMMX上，对运行时间苛刻的代码要避免这两条指令(在PPro，PII和PIII上对它们有模式识别机制，但是loop指令的效率仍然低于DEC
ECX/JNZ)。

22.2.11 返回(PMMX，PPro，PII和PIII)

PMMX，PPro，PII和PIII上有一个返回栈缓存(RSB)用于预测返回指令。 RSB工作时是先进后出。
每当CALL指令被执行时，相应的返回地址被压入RSB。 每次返回指令执行时，一个返回地址弹出RSB用于预测返回地址。
该机制保证了同一个子程序，哪怕在不同的地方被调用，其返回指令也能被正确地预测。

为了保证该机制的正常工作，你必须保证所有的CALL和返回指令匹配。
不要没有返回便从一个子过程跳出，如果速度要求苛刻的话，不要将返回指令当作间接跳转指令使用。

在PMMX上，RSB可有四个表项，在PPro，PII和PIII上可有16个。
在RSB空的情况下，返回指令的预测与间接跳转指令相同，即它被预测为到达与上一次执行同样的位置。

在PMMX上，当子程序嵌套深度大于4时，最内层的4次调用使用RSB，只要没有新的调用，所有外层子程序的返回都用简单的预测机制。
一条利用RSB的返回指令仍然占有一个BTB表项。 PMMX的4个RSB表项听起来不多，但可能已经足够了。
一般来说，子程序嵌套大于4层很正常，但真正影响速度的是最内层的快慢，当然这不包括递归程序。

在PPro，PII和PIII上，当子程序嵌套深度大于16时，最内层的16次调用使用RSB，所有外层子程序的返回都会预测失败。
因此递归过程的深度最好不要超过16层。

22.2.12 PMMX上的静态预测

PMMX上，以前没有执行过的或者BTB表中没有的控制转移指令总是被预测为不发生，而不管它是前行还是后行的。

总是不发生的分支指令不会分配BTB表项。只要它发生一次，它就得到一个BTB表项，以后不管它不发生多少次，它总在BTB表内。只有当其它的转移指令正好要抢占它的表项时，它才被踢出BTB表。

任何跳转的目标地址紧随其后的转移指令不会得到BTB表项。比如:

JMP SHORT LL

LL:

该指令不可能得到BTB表项，因此总是预测失败。

22.2.13 PPro，PII，PIII上的静态预测

在PPro，PII和PIII上，对于以前没有执行过的或者BTB表中没有的控制转移指令，如果是前行的则被预测为不发生，如果是后行的则被预测为跳转(比如一个循环)。
在这些处理器上，静态的预测花费的时间比动态的预测长。

如果你的代码不太可能放入cache，那么最好把最常用的执行分支做成不发生的，这样是为了改进指令的预取。

22.2.14 非常靠近的转移指令(PMMX)

在PMMX上，如果两条转移指令太过靠近的话，它们有共享一个BTB表项的风险。 明显的后果就是它们总是预测失败。

我们已知转移指令的BTB表项由指令的最后一个字节的地址的2-31位来指定。
如果两条转移指令如此接近以至它们的地址只有0-1位不同，就会发生共享一个BTB表项的问题。 比如:

CALL P

JNC SHORT L

如果CALL指令的最后一个字节和JNC指令的最后一个字节在记忆体的同一个双字内，我们就会付出代价。　你必须根据程序的输出汇编窗口，看是否这两个地址已经被双字界线隔开(双字界线是一个能被4整除的地址)。

解决这个问题有很多办法:

1．在记忆体中将代码序列稍微搬动一点，这样你就使得两个地址被双字线隔开。

2．将short jump改为near
jump(有四个字节偏移)，这样第二条指令的尾部离得远了。如果没有办法控制汇编器，只能靠简单地硬性规定近转移分支，那么你用这个方法。

3．在CALL和JNC之间插入一些指令。如果你因为段不是双字对齐的，或者代码一直在上下移动而不知道双字界线在哪里，那么这是最容易的方法，你更改代码如下:

CALL P

MOV EAX，EAX 　;填充2个字节就安全了

JNC SHORT L

如果你还想在PPlain也避免问题，那么插入两个NOP，这样可以避免配对(见前述22。1。3节)。

RET指令对于这个问题特别敏感，因为它只有一个字节长:

JNZ NEXT

RET

这里你要用三个字节填充:

JNZ NEXT

NOP

MOV EAX，EAX

RET

22.2.15 连续的调用或返回(PMMX)

如果在过程调用指向的目标的第一个指令对中包括另外一个CALL指令，或者一个返回紧跟着另一个返回，那么会有惩罚。
比如:

FUNC1 PROC NEAR

NOP ; 避免过程在被调用之后紧跟call指令

NOP

CALL FUNC2

CALL FUNC3

NOP ;
避免在FUNC3返回之后紧跟返回指令

RET

FUNC1 ENDP

这里需要两个NOP，因为一个NOP会与CALL配对。 对于RET，一个NOP够了，因为RET是不可配对的。
两个CALL指令之间不需要NOP，因为在CALL返回之后再CALL是没有惩罚的(在PPlain上你就需要在这里也加两个NOP了)。

连续CALL的惩罚仅仅发生在同一个子过程在几个不同的位置被调用的时候(可能因为RSB需要更新)。
而连续的返回总是有惩罚。
有时CALL后跟一个jump会有小的延迟，但CALL后跟return、return后跟CALL(如上)、jump后跟jump，call或者return、return后跟jump都没有惩罚。

22.2.16 连续的转移(PPro，PII和PIII)

在前一个jump，call或return后的第一个时钟周期内，后一个jump，call或return无法执行。
因此对于连续的转移，每个转移都要花2个周期，你可能希望处理器在这段时间内并行做一些其它事情。
同样的道理，在这些处理器上，loop指令的每次叠代也至少花两个时钟周期。

22.2.17 设计可预测的分支(PMMX，PPro，PII和PIII)

多路分支(switch/case 状态值)既可由使用跳转表的间接跳转来实现，也可由树型的分支指令来实现。
因为间接跳转很难预测，所以如果有可预测的模式和足够的BTB表项的话，推荐后者。 如果你要使用前者，推荐把跳转地址表放在数据段。

你可能希望重新组织代码，使得不能完美预测的分支模式变成可完美预测的模式。
比如，一个循环总是执行20次，底部的条件转移指令总是19次发生，第20次不发生。 模式是有规律的，但不能被模式识别机制识别，因此那次不发生总是预测失败。
为了使得模式可识别，你可以把每两个循环做成四个或五个，或者将循环展开成4份让它执行5次。
这种复杂的做法增加额外代码，只有在PPo，PII和PIII这些预测失败代价昂贵的机器上才值得。
如果循环次数更多，则没必要为了这一个预测失败而采取任何措施。

22.3 避免跳转(所有处理器)

有很多理由促使你想减少jump，call和return指令的数量:

*转移预测失败的代价很大

*与不同处理器相关的，有各种对于连续的、链式的跳转的惩罚

*因为随机替换算法，转移指令会彼此排挤对方出BTB表

*一个返回指令在PPlain和PMMX上花费2个周期，call和return在PPro
PII，PIII上要产生4条微指令。

*在PPro，PII和PIII上，在转移指令之后的指令预取可能会被延迟(第15章)，而且对于跳转，引退的效果比其它微指令小得多(第18章)。

调用和返回可以通过用内联宏替换来解决。在许多情况下，可以通过重构你的代码减少大量的jump指令。
比如，一个跳到jump指令的jump，可以用一个跳到最终地址的jump来代替。 有时如果条件是相同的或者是已知的，这甚至对条件跳转也适用。
一个跳到RET指令的jump可以直接替换成RET。 如果你想消除返回之后的返回，你不应该修改堆栈指针，因为这将会干扰RSB的预测机制。
你应该把前一个CALL替换成一个jump。 比如，CALL PRO1/RET可以被替换成JMP PRO1，前提是PRO1过程的返回地址与RET相同。

你还可以通过重复一遍跳转后的指令来消除跳转。
如果你在循环中，或在返回之前有两路分支，这很管用:

A:
CMP [EAX+4*EDX]，ECX

JE B

CALL X

JMP C

B: 　　CALL Y

C: 　　INC
EDX

JNZ A

MOV ESP，
EBP

POP EBP

RET

跳转到C可以通过重复循环的尾部代码来消除:

A: 　　CMP [EAX+4*EDX]，ECX

JE B

CALL X

INC EDX

JNZ A

JMP D

B: 　　CALL Y

C: 　　INC EDX

JNZ A

D: 　　MOV ESP， EBP

POP
EBP

RET

最经常执行的分支应该优先考虑。 跳转到D已经是出了循环了，因此不是关键。
如果这个jmp经常发生，那么也要优化，方法是替换JMP D为D后面的三条指令。

22.4 利用标志位避免条件跳转(所有处理器)

最需要消除的就是条件跳转，尤其当它们不大好预测的时候。 有时灵活地运用标志位能获得和条件跳转一样的逻辑。
比如你可以不用条件跳转计算一个带符号数的绝对值:

CDQ

XOR EAX，EDX

SUB EAX，EDX

(在PPlain和PMMX上，用MOV EDX，EAX/SAR
EDX，31代替CDQ)

对于下列情况，进位标志特别有用:

如果值为0，则置进位标志:CMP
[VALUE]，1

如果值不为0，则置进位标志:XOR EAX，EAX / CMP EAX，[VALUE]

如果进位了，增加一个数:ADC EAX，0

每当进位标志是1，将某个位置位:RCL EAX，1

如果进位标志是1，产生一个掩码:SBB EAX，EAX

如果满足某个条件，将某个位置位:SETcond AL

如果满足某个条件，将所有位置位:XOR EAX，EAX / SETNcond AL / DEC
EAX(记得将上一个例子的条件取反)

找出两个带符号数的小者:if(b<a)a=b;

SUB EBX，EAX

SBB ECX，ECX

AND ECX，EBX

ADD EAX，ECX

两个数选择其一:if(a!=0)a=b;else a=c;

CMP EAX，1

SBB EAX，EAX

XOR ECX，EBX

AND EAX，ECX

XOR EAX，EBX

这些技巧所产生的额外代码是否值得取决于:一个条件跳转的可预测性如何，在树型分支指令之间是否可被利用插入一些其它指令对或程序，跳转后面是否紧跟其它跳转(这将导致连续跳转的惩罚)。

22．5 用条件传输代替条件跳转(PPro，PII和PIII)

PPro，PII和PIII处理器由专门用于避免条件跳转的条件传输指令，因为对于这些机器预测失败的代价太大了。
对于整型和浮点型寄存器都有条件传输指令。 对于只运行在这些机器上的代码，你应该尽可能用条件传输指令代替不大好预测的条件转移指令。
如果想使你的代码在所有机器上都能运行，你对于瓶颈代码就得准备两个版本，一个用于支持条件传输的处理器，一个用于不支持条件传输的处理器(见27.10节，如何侦测条件传输指令是否被支持)。

预测失败的代价很大，因此哪怕有一些额外的指令，用条件传输指令代替条件跳转都是值得的。
但条件传输指令有使得依赖链变长的缺点，哪怕只需要一个，它也要等到两个寄存器操作数都就绪。 一个条件传输指令要等三个操作数处于就绪态: 条件标志和两个传输操作数。
你必须考虑到是否这三个操作数的任何一个可能会因为依赖链或者cache不命中带来延迟。
如果两个操作数就绪速度比条件标志慢得多，那你还是用条件跳转好，因为可能有等待两个操作数的时间，一个条件预测失败已经解决了。在需要漫长等待一个你可能还用不到的操作数的情况下，即使考虑到预测失败，一个条件跳转比条件传输快。
相反的，当两个操作数早已准备好，条件标志延迟的情况下，又考虑到分支预测可能失败，那么条件传输优于条件跳转。