HTML CSS JAVASCRIPT PYTHON PYTHON2 JAVA C C++ C# SQL Excel Linux AI BOOTSTRAP PHP 教程库 参考手册 技术文章 测验 练习 HOWTO FAQ
❮ 上一节 下一节 ❯

编译器设计 - 代码生成

代码生成可以视为编译的最后阶段。通过后代码生成，可以对代码应用优化过程，但这可以看作是代码生成阶段本身的一部分。编译器生成的代码是某些低级编程语言（例如汇编语言）的目标代码。我们已经看到，用高级语言编写的源代码被转换成低级语言，从而产生低级目标代码，该代码应具有以下最低属性：

  • 它应该具有源代码的确切含​​义。
  • 它应该在 CPU 使用率和内存管理方面高效。

现在我们将看到如何将中间代码转换为目标目标代码（在本例中为汇编代码）。

有向无环图

有向无环图 (DAG) 是一种描述基本块结构的工具，有助于查看基本块之间流动的值流，并提供优化。DAG 可轻松转换基本块。 DAG 可以这样理解：

  • 叶节点表示标识符、名称或常量。

  • 内部节点表示运算符。

  • 内部节点还表示表达式的结果或要存储或分配值的标识符/名称。

示例：

t0 = a + b
t1 = t0 + c
d = t0 + t1
有向无环图

[t0 = a + b]

 有向无环图

[t1 = t0 + c]

 有向无环图

[d = t0 + t1]

窥视孔优化

此优化技术在源代码上进行本地工作，将其转换为优化代码。本地是指手头代码块的一小部分。这些方法可以应用于中间代码以及目标代码。分析一堆语句并检查以下可能的优化：

冗余指令消除

在源代码级别，用户可以执行以下操作：

int add_ten(int x)
   {
   int y, z;
   y = 10;
   z = x + y;
   return z;
   }

int add_ten(int x)
   {
   int y;
   y = 10;
   y = x + y;
   return y;
   }

int add_ten(int x)
   {
   int y = 10;
   return x + y;
   }
   
   

int add_ten(int x)
   {
   return x + 10;
   }

在编译级别，编译器会搜索本质上冗余的指令。即使删除某些指令，多次加载和存储指令也可能具有相同的含义。例如：

  • MOV x, R0
  • MOV R0, R1

我们可以删除第一条指令并将该句子重写为：

MOV x, R1

无法访问的代码

无法访问的代码是由于编程结构而永远不会访问的程序代码的一部分。程序员可能不小心编写了一段永远无法访问的代码。

示例：

void add_ten(int x)
{
   return x + 10;
   printf(“value of x is %d”, x);
}

在此代码段中，printf 语句永远不会执行，因为程序控制在执行之前就返回，因此可以删除 printf。

控制流优化

在代码中，有些情况下程序控制会来回跳转而不执行任何重要任务。这些跳转可以删除。请考虑以下代码块：

...		
MOV R1, R2
GOTO L1
...
L1 :   GOTO L2
L2 :   INC R1

在此代码中，标签 L1 可以在将控制权传递给 L2 时被删除。因此，控制权可以直接到达 L2，而不是先跳转到 L1，然后再跳转到 L2，如下所示：

...
MOV R1, R2
GOTO L2
...
L2 : INC R1

代数表达式简化

有些情况下代数表达式可以简化。例如，表达式 a = a + 0 可以用 a 本身替换，而表达式 a = a + 1 可以简单地用 INC a 替换。

强度降低

有些操作会消耗更多时间和空间。可以通过用其他消耗更少时间和空间但产生相同结果的操作替换它们来降低它们的"强度"。

例如，x * 2可以用x << 1替换，后者只涉及一次左移。虽然 a * a 和 a2的输出相同，但 a2 的实现效率要高得多。

访问机器指令

目标机器可以部署更复杂的指令，这些指令可以更高效地执行特定操作。如果目标代码可以直接容纳这些指令，那么不仅可以提高代码质量，还可以产生更高效的结果。

代码生成器

代码生成器需要了解目标机器的运行时环境及其指令集。代码生成器在生成代码时应考虑以下事项：

  • 目标语言：代码生成器必须了解代码要转换为的目标语言的性质。该语言可能有助于某些特定于机器的指令，以帮助编译器以更方便的方式生成代码。目标机器可以具有 CISC 或 RISC 处理器架构。

  • IR 类型：中间表示具有多种形式。它可以是抽象语法树 (AST) 结构、逆波兰表示法或 3 地址代码。

  • 指令选择：代码生成器将中间表示作为输入并将其转换（映射）到目标机器的指令集中。一种表示可以有多种转换方式（指令），因此代码生成器有责任明智地选择适当的指令。

  • 寄存器分配：程序在执行期间需要维护许多值。目标机器的架构可能不允许将所有值保存在 CPU 内存或寄存器中。代码生成器决定将哪些值保存在寄存器中。此外，它还决定使用哪些寄存器来保存这些值。

  • 指令排序：最后，代码生成器决定执行指令的顺序。它为指令创建执行时间表。

描述符

代码生成器在生成代码时必须跟踪寄存器（可用性）和地址（值的位置）。对于这两者，使用以下两个描述符：

  • 寄存器描述符：寄存器描述符用于通知代码生成器有关寄存器的可用性。寄存器描述符跟踪存储在每个寄存器中的值。每当代码生成期间需要新寄存器时，都会查阅此描述符以了解寄存器的可用性。

  • 地址描述符：程序中使用的名称（标识符）的值在执行过程中可能存储在不同的位置。地址描述符用于跟踪存储标识符值的内存位置。这些位置可能包括 CPU 寄存器、堆、堆栈、内存或上述位置的组合。

代码生成器实时更新描述符。对于加载语句 LD R1, x，代码生成器：

  • 更新具有 x 值的寄存器描述符 R1 并
  • 更新地址描述符 (x) 以显示 x 的一个实例在 R1 中。

代码生成

基本块由一系列三地址指令组成。代码生成器将这些指令序列作为输入。

注意：如果名称的值在多个位置（寄存器、缓存或内存）找到，则寄存器的值将优先于缓存和主内存。同样，缓存的值将优先于主内存。主内存几乎没有任何优先权。

getReg：代码生成器使用 getReg 函数来确定可用寄存器的状态和名称值的位置。 getReg 的工作原理如下：

  • 如果变量 Y 已经在寄存器 R 中，则使用该寄存器。

  • 否则，如果某个寄存器 R 可用，则使用该寄存器。

  • 否则，如果上述两个选项都不可行，则选择需要最少加载和存储指令的寄存器。

对于指令 x = y OP z，代码生成器可以执行以下操作。让我们假设 L 是要保存 y OP z 的输出的位置（最好是寄存器）：

  • 调用函数 getReg，以确定 L 的位置。

  • 通过查阅 y 的地址描述符来确定 y 的当前位置（寄存器或内存）。如果 y 目前不在寄存器 L 中，则生成以下指令以将 y 的值复制到 L：

    MOV y', L

    其中 y' 表示 y 的复制值。

  • 使用步骤 2 中用于 y 的相同方法确定 z 的当前位置并生成以下指令：

    OP z', L

    其中 z' 表示 z 的复制值。

  • 现在 L 包含 y OP z 的值，该值旨在分配给 x。因此，如果 L 是寄存器，则更新其描述符以指示它包含 x 的值。更新 x 的描述符以指示它存储在位置 L。

  • 如果 y 和 z 没有进一步的用途，则可以将它们返回给系统。

其他代码结构（如循环和条件语句）以通用汇编方式转换为汇编语言。

❮ 上一节 下一节 ❯