MIPS bne beq Computer Organization and Design

Question

So, I'll quote my textbook(Computer Organization and Design) and then I'll ask my 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

I've searched for a while but I couldn't find why bne would be more efficient than beq. (I did however find that bne is sometimes recommended because it makes the code easier to understand, as the statements to be executed when the condition holds are right below the bne statement.)

So, if it would not be more efficient in general, it still could be more efficient in this particular exercise. I've thought about that, and I assumed that a jump instruction costs time, and therefore we'd want to minimize the amount of jumps needed. This means that, when we expect the condition to hold, we should use bne, and when we expect the condition to fail, we should use beq.

Now if we test whether $s3 equals $s4, when we have no information whatsoever about the content of those registers, it's not reasonable to assume that they're likely to be equal; on the contrary, it's more likely that they're not equal, which should result in using beq instead of bne.

So, to sum up: textbook says bne is more efficient than beq, whether it's in general or just in this example is not clear, but in either case I don't understand why.

I don't see a question there, but that's a lot of assumptions without much to back them up... — JasonD
I think it would be rare for any conditional branch to be more "efficient" than another (at least for general-purpose registers and flags - some of the system/control/special-purpose registers/flags might have a performance penalty associated). Probably the reason bne is seen to be "more efficient" is a psychological one where coders tend to write code of the form if (most_likely_condition) something(); else something_else();. That, along with branchless code being more cache-friendly, might tend to make "the opposite condition" "more efficient". — twalberg
To make it clear (I'll edit my post in a min): The textbook literally said that bne would be more efficient, my question is why. I don't assume anything to prove them wrong, I just came up with a couple of theories why bne and beq could have different efficiency, but each of these theories applied to this example result in bne NOT being more efficient. — jvanheesch
I am also reading this textbook recently. It's really helping me out with the idea of computer architecture. I have a hypothesis, that the difference of efficiency is from direct comparison of machine code of bne and beq. Consider that two instructions are comparing two register. The operation of beq must go through every bit to give an answer and store it to the register of destination. On the other hand, bne might counter difference in first few. I don't have any solid evidence for the hypothesis. I'm really glad if someone can back this up or op — Vibert Thio

Paxic Paxic · Accepted Answer · 2012-12-31T17:39:39

The efficiency is not from a direct comparison of the machine code for a bne versus beq. The text describes optimizing the over all performance by coding to shorten the most common code path.

~~If you assume the values are more likely to be unequal then only one instruction needs be processed when using bne, if you use beq you must perform an additional jump on failure.~~

The shortest path is to drop through the compare, to fail it and not jump.

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

Uncommon Case for branches

beq $18, $19, L1

else handling
jmp

replaced by

bne $18, $19, L2

success handling
end

L2:

Make the common case fast - one instruction for most branches

Re-reading your question, I think the crux is this assumption:

"Now if we test whether $s3 equals $s4, when we have no information whatsoever about the content of those registers, it's not reasonable to assume that they're likely to be equal; on the contrary, it's more likely that they're not equal, which should result in using beq instead of bne."

This seems to be the confusion, we need to find some evidence or reason to determine which possibility is more likely, registers equal or unequal.

In this case we are examining an if-then-else. I make the assertion that we expect the if-test to pass, this is the psychology described by twalberg. The registers are unlikely to contain random values as they contain data that the programer is expecting - the result of previous operations.

MIPS bne beq Computer Organization and Design

2 Answers