CompilerDev/Implementing Conditional Statements And Loops

General Concepts

For a conventional instruction set architecture such as x86, ARM, 8051, MIPS, or most other CPU types in widespread use at this time (2016), conditional statements such as if/elsif/else, and loop constructs such as for or while, are generally implemented through a combination of tests, conditional jumps/branches (jz, beq, etc.) and unconditional branches (jmp, bra, j, etc.). While some common ISAs have special-purpose instructions for repetition or looping (e.g., the REP and LOOP instructions on the x86), few compilers use them due to the added work of determining where they can be applied.

Examples below are given for Intel x86-64, ARM, and MIPS R2000 assembly language instruction sets. It is assumed that the compiler produces assembly language; for compilers that generate an Executable File directly, the compiler must handle the housekeeping (e.g., tracking branch targets) that would otherwise be done by the assembler.

General Conditional Statements

If

A naive implementation of a basic if statement will generally consist of a conditional branch to the code for the when the condition is true (the consequent), an unconditional branch past the end of the consequent, and the consequent itself:

if (a == b)
{
    /* do something */
}

The generated code (assuming that a and b are in the appropriate registers already) might look like:

x86-64	ARM	MIPS
cmp rax, rbx je main.if0.true jmp main.if0.end main.if0.true:  ;;; consequent main.if0.end:	teq r0, r1 beq main.if0.true b main.if0.end main.if0.true:  ;;; consequent main.if0.end:	beq $t0, $t1, main.if0.true j main.if0.end main.if0.true: ### consequent main.if0.end:

Note that the compiler has to generate a unique label or target table listing for each of the branch targets; the simplest implementation of this is to keep a count of the labels, and assign them a separate label name with the count appended to it. For the sake of readability, the example code uses a local label with the function name (main, in this case), the type of expression, and the count of the expressions of this type.

Thus, for nested ifs, such as

if (a == b)
{
    if (b <= c)
    {
        /* do the inner clause */
    }
    /* do the rest of the outer clause */
}

it might produce:

x86-64	ARM	MIPS
cmp rax, rbx je main.if1.true jmp main.if1.end main.if1.true: cmp rbx, rcx jle main.if2.true jmp main.if2.end main.if2.true:  ;;; do the inner clause main.if2.end:  ;;; do the rest of the outer clause main.if1.end:		bge $t0, $t1, main.if1.true j main.if1.end main.if2.true: blt $t0, $t2, main.if2.true j main.if2.end main.if2.true:  ;;; consequent for inner conditional main.if2.end:  ;;; remaining code main.if1.end:

Compound Boolean Conditionals

For compound conditionals, such as logical AND or logical OR, there naive implementation would be to first perform the tests, then use the logical ligatures to produce a testable outcome.

if (!(a <= b && b < c))
    /* do something */
}

it could naively generate

x86-64	ARM	MIPS
		ble $t0, $t1, main.if3.and0.left.true clear $t3 j main.if3.and0.right main.if3.and0.left.true: move $t3, 1 j main.if3.and0.right main.if3.and0.right: ble $t0, $t1, main.if3.and0.right.true clear $t3 j main.if3.and0.test main.if3.and0.right.true: move $t3, 1 j main.if3.and0.test main.if3.and0.test: and $t3, $t3, $t4 not $t5, $t3 bnez $t5, main.if3.true j main.if3.end main.if3.true:  ;;; consequent main.if3.end:

While this is a literal translation of the condition, it is clearly less than optimal.

Basic Optimizations

An obvious, and reasonably simple, optimization of this is to negate or reverse the condition, thus eliminating the need for the unconditional branch:

x86-64	ARM	MIPS
cmp rax, rbx jne main.if0.end  ;;; consequent main.if0.end:	teq r0, r1 bne main.if0.end  ;;; consequent main.if0.end:	bne $t0, $t1, main.if4.end  ;;; consequent main.if4.end:

Similarly, for nested ifs where the inner if is the first or last clause of the outer loop, then it can remove an extraneous labels:

x86-64	ARM	MIPS
cmp rax, rbx jne main.if1.end  ;;; if(rax == rbx) cmp rbx, rcx jg main.if2.end  ;;; if(rbx <= rcx)  ;;; do the inner clause main.if2.end:  ;;; do the rest of the outer clause main.if1.end:		blt $t0, $t1, main.if5.end bge $t0, $t2, main.if6.end  ;;; inner consequent main.if6.end:  ;;; remaining code of outer consequent main.if2.end:

For these simple cases, since the mapping of a given operator to its inverse is fixed (e.g., to implement 'less than' you would always substitute 'greater than or equal'), the only change needed is that the code for the test be issued fro the inverse.

Optimizing compound conditionals is a bit trickier, as you would need to consider which operations invert which other ones, and how to apply things like de Morgan's Law. However, it is still reasonable for most compilers to perform certain eliminations, such as replacing separate tests with short-circuiting branches. In the case of an AND', one can start by short-circuiting the first test to the end of the and part conditional, so that the second test only gets checked if the first is true. For the NOT, you can get the right result simply by not inverting the final case:

However, with a little more effort, a better solution might be possible, if we keep a table of boolean functions and their inverses, and are willing to perform a simple analysis of the order of operations.

Definite Loops

The naive implementation of a definite loop is a conditional branch at the start of the loop and an unconditional branch back to that conditional branch at the end of the loop, which is also the naive implementation of an explicit for loop. An example in MIPS assembly code (using pseudo-instructions) might be:

x86-64	ARM	MIPS
xor rcx, rcx mov rbx, for_loop_count for0.start:  ; if rcx is greater than or equal  ; to rbx, jump past the loop cmp rcx, rbx jge for1.end  ;; body of the loop here inc rcx jmp for0.start for0.end:	mov r0, #0 mov r1, #for_loop_count for0.start:  ; if r1 is greater than or equal  ; to r0, jump past the loop cmp r0, r1 bge for1.end  ;; body of the loop here add r0, r0, #1 b for0.start for0.end:	clear $t0 move $t1, for_loop_count for0.start:  ; if t1 is greater than or equal  ; to t0, jump past the loop bge $t0, $t1, for1.end  ;; body of the loop here addi $t0, $t0, 1 bra for0.start for0.end

However, even a naive compiler will usually do loop inversion by using an unconditional branch, followed by the loop label, followed by the body, and then put the loop condition as the target of the original unconditional branch with the condition inverted:

x86-64	ARM	MIPS
		clear $t0 move $t1, for_loop_count bra for1.test for1.start:  ;; body of the loop here addi $t0, $t0, 1 for1.test:  ; if t1 is less than to t0,  ; jump past the loop blt $t0, $t1, for1.start for1.end

This means that after the loop entry, the loop has just the unconditional branch, making it faster. For a hand-coded recursive descent compiler, this becomes simply a matter of changing the order in which the parsing-emitting functions are called.