CompilerDev/Implementing Conditional Statements And Loops - 版本历史

2022年3月19日 (六) 03:44 Zhang3

2022-03-19T03:44:16Z

←上一版本		2022年3月19日 (六) 03:44的版本
第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''反转即可获得正确的结果:

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

2022年3月19日 (六) 01:00 Zhang3

2022-03-19T01:00:57Z

←上一版本		2022年3月19日 (六) 01:00的版本
第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)
第197行：		第197行：
	对于这些简单的情况，由于给定运算符到其逆的映射是固定的 (例如，要实现 “小于”，总是会替换为 “大于或等于”)，因此唯一需要的更改是测试的代码从逆条件中发出。		对于这些简单的情况，由于给定运算符到其逆的映射是固定的 (例如，要实现 “小于”，总是会替换为 “大于或等于”)，因此唯一需要的更改是测试的代码从逆条件中发出。

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

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

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

	{\|		{\|
第268行：		第268行：
	\|}		\|}

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

Zhang3：创建页面，内容为“= 一般概念 = 对于传统的指令集体系结构，例如x86，ARM，8051，MIPS或目前广泛使用的大多数其他CPU类型 (2016)，条件语句 (例如 '''if' ''/'''elsif'''/'''else''')，以及循环构造 (例如 '''for''' 或 '''while''')，通常是通过组合测试来实现的，条件跳跃/分支 (jz，beq等) 和无条件分支 (jmp，bra，j等)。虽然某些常见的ISA(指令集架构)具有用于重复或循环的专用指令 (例如x…”

2022-02-08T08:43:25Z

创建页面，内容为“= 一般概念 = 对于传统的指令集体系结构，例如x86，ARM，8051，MIPS或目前广泛使用的大多数其他CPU类型 (2016)，条件语句 (例如 '''if' ''/'''elsif'''/'''else''')，以及循环构造 (例如 '''for''' 或 '''while''')，通常是通过组合测试来实现的，条件跳跃/分支 (jz，beq等) 和无条件分支 (jmp，bra，j等)。虽然某些常见的ISA(指令集架构)具有用于重复或循环的专用指令 (例如x…”

新页面

= 一般概念 =
对于传统的指令集体系结构，例如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>
|}

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