“CompilerDev/Implementing Conditional Statements And Loops”的版本间差异

来自osdev
跳到导航 跳到搜索
(创建页面,内容为“= 一般概念 = 对于传统的指令集体系结构,例如x86,ARM,8051,MIPS或目前广泛使用的大多数其他CPU类型 (2016),条件语句 (例如 '''if' ''/'''elsif'''/'''else'''),以及循环构造 (例如 '''for''' 或 '''while'''),通常是通过组合测试来实现的,条件跳跃/分支 (jz,beq等) 和无条件分支 (jmp,bra,j等)。 虽然某些常见的ISA(指令集架构)具有用于重复或循环的专用指令 (例如x…”)
 
 
(未显示同一用户的1个中间版本)
第1行: 第1行:
= 一般概念 =
= 一般概念 =
对于传统的指令集体系结构,例如x86,ARM,8051,MIPS或目前广泛使用的大多数其他CPU类型 (2016),条件语句 (例如 '''if' ''/'''elsif'''/'''else'''),以及循环构造 (例如 '''for''' 或 '''while'''),通常是通过组合测试来实现的,条件跳跃/分支 (jz,beq等) 和无条件分支 (jmp,bra,j等)。 虽然某些常见的ISA(指令集架构)具有用于重复或循环的专用指令 (例如x86上的 ''rep''' 和 '''LOOP''' 指令),但由于增加了需要确定它们可用的工作,因此很少有编译器使用它们。
对于传统的指令集体系结构,例如x86,ARM,8051,MIPS或目前广泛使用的大多数其他CPU类型 (2016年),条件语句 (例如 '''if'''/'''elsif'''/'''else'''),以及循环构造 (例如 '''for''' 或 '''while'''),通常是通过组合测试来实现的,条件跳跃/分支 (jz,beq等) 和无条件分支 (jmp,bra,j等)。 虽然某些常见的ISA(指令集架构)具有用于重复或循环的专用指令 (例如x86上的 '''rep''' 和 '''LOOP''' 指令),但由于增加了需要确定它们可用的工作,因此很少有编译器使用它们。


下面给出了 [https://en.wikipedia.org/wiki/X86_assembly_language Intel x86-64] 、 [[ARM Overview|ARM]] 和 [https://en.wikipedia.org/wiki/MIPS_instruction_set MIPS R2000汇编语言] 指令集的示例。 这里假设编译器先产生汇编语言; 对于直接生成 [[Executable Formats|可执行文件]] 的编译器,必须处理将由汇编程序完成的内部处理 (例如,跟踪分支目标)。
下面给出了 [https://en.wikipedia.org/wiki/X86_assembly_language Intel x86-64]、[[ARM Overview|ARM]]和[https://en.wikipedia.org/wiki/MIPS_instruction_set MIPS R2000汇编语言] 指令集的示例。 这里假设编译器先产生汇编语言; 对于直接生成 [[Executable Formats|可执行文件]] 的编译器,必须处理将由汇编程序完成的内部处理 (例如,跟踪分支目标)。


== 一般条件语句 ==
== 一般条件语句 ==
第45行: 第45行:
|}
|}


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


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


<source lang="C">if (a == b)
<source lang="C">if (a == b)
第93行: 第93行:


==== 复合布尔条件 ====
==== 复合布尔条件 ====
对于复合条件,例如逻辑和或逻辑或,简单直接的实现是首先执行测试,然后使用逻辑连字来产生可测试的结果。
对于复合条件,例如逻辑与(AND)或逻辑或(OR),简单直接的实现是首先执行测试,然后使用逻辑连字来产生可测试的结果。


<source lang="C">if (!(a <= b && b < c))
<source lang="C">if (!(a <= b && b < c))
第164行: 第164行:
|}
|}


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


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


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


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


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


{|
{|
第268行: 第268行:
|}
|}


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

2022年3月19日 (六) 03:44的最新版本

一般概念

对于传统的指令集体系结构,例如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:

复合布尔条件

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

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)函数的调用顺序的问题。