CompilerDev/Implementing Conditional Statements And Loops

一般概念

对于传统的指令集体系结构，例如x86，ARM，8051，MIPS或目前广泛使用的大多数其他CPU类型 (2016)，条件语句 (例如 if' /elsif/else)，以及循环构造 (例如 for 或 while)，通常是通过组合测试来实现的，条件跳跃/分支 (jz，beq等) 和无条件分支 (jmp，bra，j等)。 虽然某些常见的ISA(指令集架构)具有用于重复或循环的专用指令 (例如x86上的 rep 和 LOOP 指令)，但由于增加了需要确定它们可用的工作，因此很少有编译器使用它们。

下面给出了 Intel x86-64 、 ARM 和 MIPS R2000汇编语言 指令集的示例。 这里假设编译器先产生汇编语言; 对于直接生成 可执行文件 的编译器，必须处理将由汇编程序完成的内部处理 (例如，跟踪分支目标)。

一般条件语句

If

基本的 if 语句的直接实现通常由判断条件和为true时的代码条件分支(称为consequent)组成，在之后是无条件结尾分支:

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

生成的代码 (假设 a 和 b 已经在适当的寄存器中) 可能看起来像:

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:

请注意，编译器必须为每个分支目标生成唯一的标签或目标表列表; 最简单的实现是保留标签的计数，并为它们分配一个单独的标签名称，并附加计数。(译者注：这里main.if0.true,main.if0.true这样的汇编定位标签) 为了可读性，示例代码使用带有函数名称 (在本例中为main)，表达式类型以及该类型表达式的计数的本地标签。

因此，对于嵌套的 if'，例如

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

它可能产生:

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:

复合布尔条件

对于复合条件，例如逻辑和或逻辑或，简单直接的实现是首先执行测试，然后使用逻辑连字来产生可测试的结果。

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

它可以简单地产生

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:

虽然这是条件的字面翻译，但显然不是最佳的。

基本优化

一个明显的，合理简单的优化是否定或反转条件，从而消除了对无条件分支的需求:

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:

同样，对于嵌套的 if，其中内部 if' 是外部循环的第一个或最后一个子句，则它可以删除无关的标签:

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:

对于这些简单的情况，由于给定运算符到其逆的映射是固定的 (例如，要实现 “小于”，总是会替换为 “大于或等于”)，因此唯一需要的更改是测试的代码从逆条件中发出。

优化复合条件有点棘手，因为您需要考虑哪些操作会反转哪些其他操作，以及如何应用诸如”德·摩根定理“（或称为反演律）之类的方法。 但是，对于大多数编译器来说，执行某些消除仍然是合理的，例如用短路分支代替单独的测试。 在 AND' 的情况下，可以通过将第一个测试短路到有条件的 AND 部分的末尾来开始，以便仅在第一个测试为真的情况下才检查第二个测试。 对于 NOT' ，只需将最终情况“ not ”反转即可获得正确的结果:

尽管麻烦，但如果我们保留一个布尔函数及其逆的表，并且愿意对操作顺序进行简单的分析，那么稍加努力，可能会有更好的解决方案。

定义循环

确定循环的直接简单实现是在循环开始时的条件分支，在循环结束时的无条件分支回到该条件分支，这也是显式for循环的简单实现。 MIPS汇编代码中的一个示例 (使用伪指令) 可能是:

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

然而，即使是简易的编译器，通常也会通过使用无条件分支来进行「循环反转」，然后是循环标签，然后是主体，然后将循环条件作为原始无条件分支的目标，条件倒置:

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

这意味着在循环进入之后，循环只有无条件分支，使其更快。 对于手动编码的递归下降编译器，这仅是更改解析发射函数的调用顺序的问题。