CDQ

XOR EBX,ECX

AND EDX,EBX

XOR EDX,ECX

Whether or not such tricks are worth the extra code depends on how predictable a conditional jump would be, and the latency of the extra code. The examples that use CDQ are faster than conditional moves on the P4.

Another way of avoiding branches in newer processors is to use the MAX.., MIN.., PMAX.. and PMIN.. instructions and the saturating PADD.. and PSUB.. instructions.

You can conditionally move data in memory by using REP MOVS with ECX = 0 when you don't want to move.

Replacing conditional jumps by conditional moves (PPro, P2, P3, P4)

The PPro, P2, P3 and P4 processors have conditional move instructions intended specifically for avoiding branches, because branch misprediction is very time-consuming on these processors. There are conditional move instructions for both integer and floating-point registers (See page 110 for how to make conditional moves in MMX and XMM registers). For code that will not run on old processors you may replace poorly predictable branches with conditional moves.

This example again finds the minimum of two unsigned numbers: if (b < a) a = b;

CMP EAX,EBX

CMOVNB EAX,EBX

The misprediction penalty for a branch may be so high that it is advantageous to replace it with conditional moves even when it costs several extra instructions. But conditional move instructions have two important disadvantages:

1.they make dependence chains longer

2.they introduce an unnecessary dependence on the operand not chosen

A conditional move is waiting for three operands to be ready before it can be executed: the condition flag and the two move operands. You have to consider if any of these three operands are likely to be delayed by dependence chains or cache misses. If the condition flag is available long before the move operands then you may as well use a branch, because a possible branch misprediction could be resolved while waiting for the move operands. In situations where you have to wait long for a move operand that may not be needed after all, the branch may be faster than the conditional move despite a possible misprediction penalty. The opposite situation is when the condition flag is delayed while both move operands are available early. In this situation the conditional move is preferred over the branch if misprediction is likely.

13 Optimizing for P1 and PMMX

13.1 Pairing integer instructions

Perfect pairing

The P1 and PMMX have two pipelines for executing instructions, called the U-pipe and the V-pipe. Under certain conditions it is possible to execute two instructions simultaneously,

one in the U-pipe and one in the V-pipe. This can almost double the speed. It is therefore advantageous to reorder the instructions to make them pair.

The following instructions are pairable in either pipe:

•MOV register, memory, or immediate into register or memory

•PUSH register or immediate, POP register

•LEA, NOP

•INC, DEC, ADD, SUB, CMP, AND, OR, XOR,

•and some forms of TEST (see page 135).

The following instructions are pairable in the U-pipe only:

•ADC, SBB

•SHR, SAR, SHL, SAL with immediate count

•ROR, ROL, RCR, RCL with an immediate count of 1

The following instructions can execute in either pipe but are only pairable when in the V- pipe:

•near call

•short and near jump

•short and near conditional jump.

All other integer instructions can execute in the U-pipe only, and are not pairable.

Two consecutive instructions will pair when the following conditions are met:

1. The first instruction is pairable in the U-pipe and the second instruction is pairable in the V-pipe.

2. The second instruction does not read or write a register which the first instruction writes to.

Examples:

3. In rule 2, partial registers are treated as full registers. Example:

MOV AL, BL / MOV AH, 0

writes to different parts of the same register, do not pair.

4. Two instructions which both write to parts of the flags register can pair despite rule 2 and 3. Example:

5. An instruction that writes to the flags can pair with a conditional jump despite rule 2. Example:

6. The following instruction combinations can pair despite the fact that they both modify the stack pointer:

PUSH + PUSH, PUSH + CALL, POP + POP

7. There are restrictions on the pairing of instructions with prefix. There are several types of prefixes:

•instructions addressing a non-default segment have a segment prefix.

•instructions using 16 bit data in 32 bit mode, or 32 bit data in 16 bit mode have an operand size prefix.

The two operands are within the same DWORD, so they cannot execute simultaneously. The pair takes 2 clock cycles.

MOV AL, [ESI+3] / MOV BL, [ESI+4]

Here the two operands are on each side of a DWORD boundary, so they pair perfectly, and take only one clock cycle.

3. The preceding rule is extended to the case where bits 2 - 4 are the same in the two addresses (cache line conflict). For DWORD addresses this means that the difference between the two addresses should not be divisible by 32.

Pairable integer instructions, which do not access memory, take one clock cycle to execute, except for mispredicted jumps. MOV instructions to or from memory also take only one clock cycle if the data area is in the cache and properly aligned. There is no speed penalty for using complex addressing modes such as scaled index registers.

A pairable integer instruction that reads from memory, does some calculation, and stores the result in a register or flags, takes 2 clock cycles. (read/modify instructions).

A pairable integer instruction that reads from memory, does some calculation, and writes the result back to the memory, takes 3 clock cycles. (read/modify/write instructions).

4. If a read/modify/write instruction is paired with a read/modify or read/modify/write instruction, then they will pair imperfectly.

The number of clock cycles used is given in the following table:

Example:

ADD [mem1], EAX / ADD EBX, [mem2] ; 4 clock cycles

ADD EBX, [mem2] / ADD [mem1], EAX ; 3 clock cycles

5. When two paired instructions both take extra time due to cache misses, misalignment, or jump misprediction, then the pair will take more time than each instruction, but less than the sum of the two.

6. A pairable floating-point instruction followed by FXCH will make imperfect pairing if the next instruction is not a floating-point instruction.

In order to avoid imperfect pairing you have to know which instructions go into the U-pipe, and which to the V-pipe. You can find out this by looking backwards in your code and search for instructions which are unpairable, pairable only in one of the pipes, or cannot pair due to one of the rules above.

Imperfect pairing can often be avoided by reordering your instructions. Example:

Here the two MOV instructions form an imperfect pair because they both access the same memory location, and the sequence takes 3 clock cycles. You can improve the code by reordering the instructions so that INC ECX pairs with one of the MOV instructions.