Compiler Branches

This excerpt from the IBM PowerPC™ Compiler Writer's Guide gives coding examples of how a compiler can avoid branches in the application code that it generates. The document is written for experienced C-language compiler developers. The complete document, written by Warthman Associates, is on IBM's Web site.

The following PowerPC instructions are used in this excerpt:

3.1.5 Avoiding Branches

Branching, both conditional and unconditional, slows most implementations. Even an unconditional branch or a correctly predicted taken branch may cause a delay if the target instruction is not in the fetch buffer or the cache. It is therefore best to use branch instructions carefully and to devise algorithms that reduce branching. Many operations that normally use branches may be performed either with fewer or no branches.

Reducing the number of branches:

• Increases the size of the basic blocks, and therefore increases opportunities for scheduling within a basic block.
• Decreases the number of basic blocks.

3.1.5.1 Computing Predicates

Predicates utilize a boolean expression as an integer value. For example, in C:

ne = ((x != y) ? 1 : 0);

Figure 3-15 shows how to calculate this expression using an ordinary control flow translation.

Figure 3-15. Predicate Calculation: Branching Code Sequence

You can avoid the branch by using Condition Register logical instructions, as shown in Figure 3-16. In this case, the result of the comparison is directly transferred from the Condition Register to a General-Purpose Register, from which the bit is extracted and then flipped.

Figure 3-16. Predicate Calculation: Condition Register Logical Sequence

Some implementations have delays associated with accessing the Condition Register using the mfcr instruction. An alternative that uses only fixed-point operations is shown in Figure 3-17.

Figure 3-17. Predicate Calculation: Fixed-Point Operation Code Sequence

You can generate all boolean predicates with straight-line code that does not use the Condition Register. Figure 3-18 shows arithmetic expressions that yield a sign-bit reflecting the appropriate result.

Figure 3-18. Arithmetic Expressions for Boolean Predicates

Boolean Predicate	Arithmetic Expression
x y	(x - y) | (y - x)
x = y	¬((x - y) | (y - x))
x < y	(x & ¬y) | ((x y) & (x - y))
x <= y	(x | ¬y) & ((x y) | ¬(y - x))
x < y, unsigned	(¬x & y) | ((x y) & (x - y)), or (¬x & y) | ((¬x | y) & (x - y))
x <= y, unsigned	(¬x | y) & ((x y) | ¬(y - x))

Shorter sequences exist for many of these operations. The GNU superoptimizer is a program that exhaustively searches a subset of machine instructions to find the shortest branch-free combinations that perform a specified operation. Appendix D lists the PowerPC GNU superoptimizer results for a number of functions.

3.1.5.2 Conditionally Incrementing a Value by 1

Figure 3-19 shows the C code fragment for conditionally incrementing a value by 1 and equivalent branching and non-branching assembly code sequences. For simple conditions, branch-free equivalents can be formed using computed predicates.

Figure 3-19. Conditionally Incrementing a Value by 1 Code Example

C Source Code
	if (a < b) ++b;
Branching Code
	# R3 contains a
	# R4 contains b
	cmpw	cr0,R3,R4	# compare a and b
	bge	cr0,lab	# branch if a >= b
	addi	R4,R4,1	# b = b + 1
lab:
			# R4 contains the desired result
Branch-Free Code
	# R3 contains a
	# R4 contains b
	subf	R0,R4,R3	# a - b
	eqv	R2,R3,R4	# a b
	and	R2,R0,R2	# (a b) & (a - b)
	andc	R0,R3,R4	# a & ~b
	or	R0,R0,R2	# (a & ~b) | ((a b) & (a - b))
	rlwinm	R0,R0,1,31,31	# extract predicate
	add	R4,R4,R0	# if (a < b) then b++

3.1.5.3 Condition Register Logical

The Condition Register logical instructions can be used to combine several branch conditions, thus reducing the number of branches. For example, Figure 3-20 shows the C code fragment for a complex conditional expression and two equivalent assembly code sequences: one that has a comparison and branch for each side of the OR, and another that uses a Condition Register logical OR to combine the results of the compare and recording operations for a single test by a conditional branch. This form may present itself in situations where a common sub-expression exists between this and other code, thus offering opportunities for multiple compare and recording instructions within a single basic block.

Figure 3-20. Complex Condition Register Logical Code Example

Figure 3-21 shows code sequences for a C switch for which the optimal implementation of the multi-way branch is simply a sequence of compare-branch tests. Because the tests all have a common target address, they can be combined using Condition Register logical instructions, reducing the total number of branches from four to one. For a specific implementation, compare the timing of sequences using Condition Register logical instructions to the equivalent multiple-branch sequences because the relative performance may vary.

Figure 3-21. C Switch: Condition Register Logical Code Example