CompilerDev/Implementing Conditional Statements And Loops

来自osdev
Zhang3讨论 | 贡献2022年3月19日 (六) 01:00的版本
跳到导航 跳到搜索

一般概念

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

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

一般条件语句

If

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

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

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

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),表达式类型以及该类型表达式的计数的本地标签。

因此,对于嵌套的 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

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

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

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