MIPS bne beq 计算机组织与设计

Question

好的，我将引用我的教材（计算机组成与设计），然后提出我的问题：

Compiling if-then-else into Conditional branches

In the following code segment, f, g, j, i and j are variables. If the five variables f through j correspond to the five registers $s0 through $s4, what is the compiled MIPS code for this C if statement?

if (i == j) f = g + h; else f = g - h;

Figure 2.9 is a flowchart of what the MIPS code should do. The first expression compares for equality, so it would seem that we would want the branch if registers are equal instruction (beq). In general, the code will be more efficient if we test for the opposite condition to branch over the code that performs the subsequent then part of the if (the label Else is defined below) and so we use the branch if registers are not equal instruction (bne):

bne $s3, $s4, Else # go to Else if i ≠ j

我搜索了一段时间，但我找不到为什么bne比beq更高效的原因。（但是我发现有时会推荐使用bne，因为它使代码更易于理解，当条件成立时要执行的语句就在bne语句下面。）

所以，如果在一般情况下它不会更高效，那么在这个特定的练习中它仍然可能更高效。我思考了一下，假设分支指令在被执行时需要更多的时间，因此我们希望尽量减少所需跳转（已执行分支）的数量。这意味着当我们期望条件成立时，我们应该使用bne，而当我们期望条件失败时，我们应该使用beq。

现在，如果我们测试$ s3 是否等于$ s4 ，当我们对这些寄存器的内容没有任何信息时，假设它们可能相等是不合理的。相反，更有可能它们不相等，这应该支持使用beq而不是bne。

总之：教科书说bne比beq更高效，无论是普遍情况还是只针对这个示例都不清楚，但在任何情况下我都不明白为什么。

- jvanheesch

---

我在那里没有看到问题，但是这里有很多假设却没有太多的支持... - JasonD

我认为任何条件分支比另一个更“高效”可能是罕见的（至少对于通用寄存器和标志而言——一些系统/控制/特殊目的寄存器/标志可能会有性能惩罚）。也许bne被认为“更高效”的原因是心理上的，程序员倾向于编写形式为if (most_likely_condition) something(); else something_else();的代码。这个以及无分支代码更加缓存友好，可能会使“相反的条件”“更高效”。 - twalberg

为了明确（我马上编辑我的帖子）：教科书字面上说bne会更有效率，我的问题是为什么。我不假设任何东西来证明他们错了，我只是想到了一些理论，为什么bne和beq可能有不同的效率，但是这些理论中的每一个都适用于这个例子，结果是bne并不更有效率。 - jvanheesch

我最近也在阅读这本教科书。它真的帮助我理解了计算机体系结构的概念。我有一个假设，即“bne”和“beq”的机器代码的效率差异体现在直接比较上。考虑两个指令正在比较两个寄存器。执行“beq”的操作必须经过每一位才能给出答案并将其存储到目标寄存器中。而“bne”则可以在前几位中找到区别。我没有任何确凿的证据支持这个假设。如果有人能证实或提供反驳意见，我将非常高兴。 - Vibert Thio

Answer 1

效率并非来自对 bne 和 beq 的机器码的直接比较。该文本描述了通过编写缩短最常见代码路径来优化整体性能的方法。

如果您假设值更可能不相等，则使用 bne 时只需要处理一条指令，如果使用 beq，则在失败时必须执行额外的跳转。

最短的路径是通过比较，失败后不跳转。

从http://www.cs.gmu.edu/~setia/cs365-S02/class3.pdf：

不常见的分支情况

beq $18, $19, L1

- else 处理 - jmp 替换为

bne $18, $19, L2

- 成功处理 - 结束

L2:

使常见情况快速 - 对于大多数分支只需一条指令。

重新阅读您的问题，我认为关键在于这个假设：

“现在，如果我们测试$s3是否等于$s4，而我们对这些寄存器的内容没有任何信息，那么假设它们很可能相等是不合理的；相反，它们更可能不相等，这应该导致使用beq而不是bne。”

这似乎是混淆了，我们需要找到一些证据或原因来确定哪种可能性更大，即寄存器相等或不相等。

在这种情况下，我们正在检查一个if-then-else。我断言我们期望if-test通过，这是twalberg描述的心理学。寄存器不太可能包含随机值，因为它们包含程序员所期望的数据——之前操作的结果。

- Paxic

---

编辑：我无法使用这个东西，不知道如何换行。我相当确定我按照您的逻辑操作（因为尝试使常见情况更快是我尝试做的事情，只是忘了像那样解释它），但我不确定我完全理解它。我会引用您的话："如果您假设值更可能不相等，则在使用bne时只需要处理一个指令，如果使用beq，则必须在失败时执行额外的跳转。" 难道不恰恰相反吗？如果使用beq将跳转到相等的位置，所以如果您不希望它们相等，应该使用bne，我想？ - jvanheesch

我需要花点时间思考，这个想法是，如果你期望值不相等，则使用bne，因为只会执行一条指令。如果你期望它们相等，则使用beq。当任何一个比较失败时，你就需要额外的一条指令——跳转。编写代码时，尽可能少地使用“失败”跳转。 - Paxic

不要让我或自己感到困惑。使用bne或beq进行比较的成本将是相同的，效率将来自于最小化代码路径。 - Paxic

是的，但以下内容让我彻底困惑了：我会说如果你期望值相等就使用 bne（因为 bne 表示跳转到不相等的状态，这种情况较少出现），但你说如果我期望它们相等，我应该使用 beq，这让我很困惑。 - jvanheesch

是的，我同意这很令人困惑。据我记得，目标是尽可能少地跳跃。正如twalberg所指出的那样，我们倾向于测试成功，通过测试意味着我们进行了跳跃。我希望代码在比较后能够顺利执行 - 保持本地。在我们想要处理的值上测试失败，让代码沿着失败的路径执行。对于意外情况进行分支处理，失败时进行分支。 - Paxic

我看到你编辑了你的帖子。如果我没错的话，你现在同意我的观点，即失败的测试不会跳转。因此，就像你所说的那样，我们应该测试不常见的情况。现在看到我示例中的代码，书中是否有可能正确地说bne更有效（在这个示例中），还是一个错误？我并不是说beq本身更有效，但我不知道bne怎么可能更有效。 （顺便说一句，非常感谢你的回复！） - jvanheesch

Answer 2

我相信这与简化编译器有关。在您有一个等式断言的情况下，如果条件不满足，则希望跳过执行代码。我认为这个决定是为了在您有else条件和没有else条件的情况下使用完全相同的过程。这是我的想法。如果我的推理有误，请告诉我！ :)

从OP给出的伪代码开始：

if (i == j) {
  f = g + h;
}
else {
  f = g - h;
}

会被翻译成：

      bne  $s3, $s4, Else
      add  $s0, $s1, $s2
      j    Exit
Else: sub  $s0, $s1, $s2
Exit: ...

如果您将C代码更改为仅在i == j时执行加法：

if (i == j) {
  f = g + h;
}

编译器会生成类似于这样的代码：

      bne  $s3, $s4, Exit
      add  $s0, $s1, $s2
Exit: ...

现在，让我们考虑一下如果使用beq来测试断言，编译后的代码会是什么样子。我猜它看起来会像这样：

      beq  $s3, $s4, Equal
      j    Exit
Equal:
      add  $s0, $s1, $s2
Exit: ...

这似乎比使用bne测试要低效得多。

编辑 还有一个事实，检查不等式对于CPU来说比检查等式更快。

如果您尝试比较两个32位数字是否相等，则CPU必须比较该32位数字的每个位以确保它们相等。如果测试非等式，如果2个数字的第一位不同，则CPU无需费心测试任何其他位以断言不等式。

- Simon Germain

---

是的，那种愚蠢的beq-over-a-j模型可能是他们所考虑的替代方案，以及他们将按照相同顺序在汇编中布置if和else块的天真/简单假设。(当然这并非必要; 您可以将if或else块放在函数结束后，以便快速路径甚至不必跳过它。 （例如beq i、j、if_body，并且有一些带有j done的指令）。当具有分析信息表明一侧运行频率远高于另一侧时，真实编译器的基于分析的优化将完成此操作。) - Peter Cordes

我感觉好像来晚了，但是现在才开始涉足这个领域。谢谢你的解释，很清晰易懂。 - Simon Germain

Answer 3

另一个原因是简单的分支预测器通常假设前向分支不被执行，而后向分支被执行。这种假设对于简单循环来说可以提高性能。

- markgz