CompilerDev/Implementing Conditional Statements And Loops

From OSDev.wiki
Jump to navigation Jump to search

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.