“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行：
= 一般概念 =
#REDIRECT [[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''' 指令)，但由于增加了需要确定它们可用的工作，因此很少有编译器使用它们。
 
下面给出了 [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|可执行文件]] 的编译器，必须处理将由汇编程序完成的内部处理 (例如，跟踪分支目标)。
 
== 一般条件语句 ==
=== If ===
基本的 '''if''' 语句的直接实现通常由判断条件和为true时的代码条件分支(称为''consequent'')组成，在之后是无条件结尾分支:
 
<source lang="C">if (a == b)
{
    /* do something */
}</source>
 
生成的代码 (假设 '''a''' 和 '''b''' 已经在适当的寄存器中) 可能看起来像:
 
{|
! x86-64
! ARM
! MIPS
|+
|<pre>
    cmp rax, rbx
    je main.if0.true
    jmp main.if0.end
main.if0.true:
    ;;; consequent
main.if0.end:
</pre>
|<pre>
    teq r0, r1
    beq main.if0.true
    b main.if0.end
main.if0.true:
    ;;; consequent
main.if0.end:
</pre>
|<pre>
    beq $t0, $t1, main.if0.true
    j main.if0.end
main.if0.true:
    ### consequent
main.if0.end:
</pre>
|}
 
请注意，编译器必须为每个分支目标生成唯一的标签或目标表列表; 最简单的实现是保留标签的计数，并为它们分配一个单独的标签名称，并附加计数。(译者注：这里main.if0.true,main.if0.true这样的汇编定位标签) 为了可读性，示例代码使用带有函数名称 (在本例中为main)，表达式类型以及该类型表达式的计数的本地标签。
 
因此，对于嵌套的 ''if'，例如
 
<source lang="C">if (a == b)
{
    if (b <= c)
    {
        /* do the inner clause */
    }
    /* do the rest of the outer clause */
}</source>
 
 
它可能产生:
{|
! x86-64
! ARM
! MIPS
|+
|<pre>    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:
</pre>
|<pre>
</pre>
|<pre>    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:</pre>
|}
 
==== 复合布尔条件 ====
对于复合条件，例如逻辑和或逻辑或，简单直接的实现是首先执行测试，然后使用逻辑连字来产生可测试的结果。
 
<source lang="C">if (!(a <= b && b < c))
    /* do something */
}</source>
 
它可以简单地产生
 
{|
! x86-64
! ARM
! MIPS
|+
|<pre>
</pre>
|<pre>
</pre>
|<pre>
    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:</pre>
|}
 
 
虽然这是条件的字面翻译，但显然不是最佳的。
 
==== 基本优化 ====
 
一个明显的，合理简单的优化是否定或反转条件，从而消除了对无条件分支的需求:
 
{|
! x86-64
! ARM
! MIPS
|+
|<pre>
    cmp rax, rbx
    jne main.if0.end
    ;;; consequent
main.if0.end:
</pre>
|<pre>
    teq r0, r1
    bne main.if0.end
    ;;; consequent
main.if0.end:
</pre>
|<pre>
    bne $t0, $t1, main.if4.end
    ;;; consequent
main.if4.end:</pre>
|}
 
同样，对于嵌套的 '''if''，其中内部 '''if''' 是外部循环的第一个或最后一个子句，则它可以删除无关的标签:
 
{|
! x86-64
! ARM
! MIPS
|+
|<pre>
    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:
</pre>
|<pre>
</pre>
|<pre>
    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:</pre>
|}
 
 
对于这些简单的情况，由于给定运算符到其逆的映射是固定的 (例如，要实现 “小于”，总是会替换为 “大于或等于”)，因此唯一需要的更改是测试的代码从逆条件中发出。
 
优化复合条件有点棘手，因为您需要考虑哪些操作会反转哪些其他操作，以及如何应用诸如”德·摩根定理“（或称为反演律）之类的方法。 但是，对于大多数编译器来说，执行某些消除仍然是合理的，例如用短路分支代替单独的测试。 在 '''AND''' 的情况下，可以通过将第一个测试短路到有条件的 '''AND''' 部分的末尾来开始，以便仅在第一个测试为真的情况下才检查第二个测试。 对于 '''NOT' ''，只需将最终情况“ not ”反转即可获得正确的结果:
 
尽管麻烦，但如果我们保留一个布尔函数及其逆的表，并且愿意对操作顺序进行简单的分析，那么稍加努力，可能会有更好的解决方案。
 
== 定义循环 ==
确定循环的直接简单实现是在循环开始时的条件分支，在循环结束时的无条件分支回到该条件分支，这也是显式for循环的简单实现。 MIPS汇编代码中的一个示例 (使用伪指令) 可能是:
 
{|
! x86-64
! ARM
! MIPS
|+
|<pre>
        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:</pre>
|<pre>        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:</pre>
|<pre>        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</pre>
|}
 
然而，即使是简易的编译器，通常也会通过使用无条件分支来进行「循环反转」，然后是循环标签，然后是主体，然后将循环条件作为原始无条件分支的目标，条件倒置:
 
{|
! x86-64
! ARM
! MIPS
|+
|<pre>
</pre>
|<pre>
</pre>
|<pre>  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</pre>
|}
 
这意味着在循环进入之后，循环只有无条件分支，使其更快。 对于手动编码的递归下降编译器，这仅是更改解析发射函数的调用顺序的问题。

2022年2月8日 (二) 08:43的最新版本

重定向到：

取自“http://wiki.foofun.cn//index.php?title=Implementing_Conditional_Statements_And_Loops&oldid=398”