编译器中的反向控制转移

In code generation，循环和跳转指令在控制程序流程方面发挥着关键作用。Intermediate code generation 是编译器中的一个关键阶段，将高级语言结构转换为机器可解释的代码。虽然指令通常遵循线性序列，但在许多情况下，执行需要循环回到之前的指令。这种backward flow，称为reverse transfer of control，对于实现loops、recursion和error recovery至关重要。

在本章中，我们将讨论reverse transfer of control、其类型，以及编译器如何生成机器代码来处理backward jumps。

什么是反向控制转移？

反向控制转移发生在执行跳转回之前的一组指令以重新执行时。那么，何时需要它？

反向控制转移在以下场景中很有用 −

• Loops − 重复代码直到满足条件。
• Function Recursion − 函数调用自身直到达到基本情况。
• Error Recovery − 在失败后重试操作。

与前向转移不同，反向跳转专注于迭代和重复。现在编译器生成优化的指令（例如，J、BGE、JAL）来提供高效的反向控制流。

控制反向转移的类型

让我们检查一下控制反向转移的不同类型 −

循环 (While、For、Do-While)

循环依赖于向后跳转来重复执行代码块。编译器会策略性地放置条件检查和跳转指令。

示例：C 语言中的 While 循环

看一下以下示例 −

while (i < 10) {  
   i = i + 1;  
}  

使用 Atoms 的中间表示 (IR)

(LBL, L1)  
(TST, i, 10, <, L2)   # 如果 i >= 10，退出循环  
(ADD, i, 1, i)        # i = i + 1  
(JMP, L1)             # 重复循环  
(LBL, L2)

翻译为机器码 (MIPS 示例)

L1:  
    lw $t1, i  
    li $t2, 10  
    bge $t1, $t2, L2   # 如果 i >= 10，退出循环  

    addi $t1, $t1, 1   # i = i + 1  
    sw $t1, i  
    j L1               # 重复循环  

L2:  

在这里，我们可以看到 j L1 指令将控制转移回后方，以持续执行循环。

Do-While 循环

让我们看看另一种类型的循环。这是一种出口控制循环。与 while 循环不同，do-while 循环在检查条件之前总是至少执行一次。编译器将循环条件检查放置在末尾，如果条件仍然有效则向后跳转。

示例：C 语言中的 Do-While 循环

看一下以下示例 −

do {  
   i = i + 1;  
} while (i < 10);   

使用 Atoms 的中间表示 (IR) −

(LBL, L1)  
(ADD, i, 1, i)        # i = i + 1  
(TST, i, 10, <, L1)   # 如果 i < 10，重复循环  

翻译为机器码 (MIPS 示例) −

L1:  
    addi $t1, $t1, 1   # i = i + 1  

    lw $t1, i  
    li $t2, 10  
    blt $t1, $t2, L1   # 如果 i < 10，重复循环  

blt（小于则分支）指令将控制转移回 L1，重复执行。

For 循环

for 循环也是一种入口控制循环。但它以结构化形式包含初始化、条件检查和递增。编译器生成跳转来处理条件检查和迭代步骤。

示例：C 语言中的 For 循环

看一下以下示例 −

for (i = 0; i < 10; i++) {  
   sum = sum + i;  
}   

使用 Atoms 的中间表示 (IR) −

(MOV, 0, , i)         # i = 0  
(LBL, L1)  
(TST, i, 10, <, L2)   # 如果 i >= 10，退出循环  
(ADD, sum, i, sum)    # sum = sum + i  
(ADD, i, 1, i)        # i = i + 1  
(JMP, L1)             # 重复循环  
(LBL, L2)   

翻译为机器码 (MIPS 示例) −

    li $t1, 0          # i = 0  
L1:  
    bge $t1, 10, L2    # 如果 i >= 10，退出循环  

    add $t3, $t3, $t1  # sum = sum + i  
    addi $t1, $t1, 1   # i = i + 1  
    j L1               # 重复循环  

L2:  

在这里，我们可以看到条件检查和递增操作是分开的，j L1 将控制转移回后方。

函数递归

对于基于函数的方法如递归，会发生向后转移。在递归函数调用中，执行跳转回函数的起点，直到满足基本条件。

示例：C 语言中的阶乘函数

看一下以下示例 −

int factorial(int n) {  
   if (n == 0) return 1;  
   return n * factorial(n - 1);  
}   

使用 Atoms 的中间表示 (IR) −

(TST, n, 0, ==, L1)   # 如果 n == 0，返回 1  
(SUB, n, 1, T1)  
(CALL, factorial, T1, T2)  
(MUL, n, T2, R)       # R = n * factorial(n-1)  
(LBL, L1)  
(MOV, 1, , R)

翻译为机器码 (MIPS 示例) −

factorial:  
    beq $a0, 0, base_case   # 如果 n == 0，返回 1  

    addi $sp, $sp, -4  
    sw $ra, 0($sp)          # 保存返回地址  

    addi $a0, $a0, -1  
    jal factorial           # 递归调用  

    lw $ra, 0($sp)  
    addi $sp, $sp, 4  
    mul $v0, $a0, $v0       # n * factorial(n-1) 的乘法  
    jr $ra                  # 返回  

base_case:  
    li $v0, 1               # 返回 1  
    jr $ra 

每次递归调用都将控制转移回 factorial，从而执行另一个函数调用，直到达到基本情况。

为了轻松记住控制反向转移，您可以参考下表 −

Conclusion

在本章中，我们探讨了编译器设计中的reverse transfer of control（反向控制转移）概念，这是处理loops（循环）和recursion（递归）的根本。在编译器将高级结构如while循环、for循环和递归函数翻译成分支和跳转指令，以实现高效的反向执行。

我们介绍了编译器如何管理backward jumps（反向跳转），开发者如何编写优化的代码，以及迭代和递归在低级层面如何工作。无论是简单的循环还是复杂的递归算法，反向控制转移都能确保程序重复且可预测地执行。