上一节:
下一节:

  编译器设计 - 代码生成

  • 简述

    代码生成可以被认为是编译的最后阶段。通过后期代码生成，可以对代码应用优化过程，但这可以看作是代码生成阶段本身的一部分。编译器生成的代码是某种低级编程语言的目标代码，例如汇编语言。我们已经看到，用高级语言编写的源代码被转换为低级语言，从而产生低级目标代码，它应该具有以下最低属性：
    • 它应该带有源代码的确切含​​义。
    • 它在 CPU 使用率和内存管理方面应该是高效的。
    我们现在将看到如何将中间代码转换为目标对象代码（在本例中为汇编代码）。

  • 有向无环图

    有向无环图 (DAG) 是一种描述基本块结构的工具，有助于查看基本块之间流动的值流，并提供优化。DAG 提供了对基本块的简单转换。DAG可以在这里理解：
    • 叶节点代表标识符、名称或常量。
    • 内部节点代表运营商。
    • 内部节点还表示表达式的结果或要存储或分配值的标识符/名称。
    Example: 
    
t0 = a + b
t1 = t0 + c
d = t0 + t1
    有向无环图
    [t 0 = 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
    • 移动 R0, R1
    我们可以删除第一条指令并将句子重写为： 
    
MOV x, R1

    无法访问的代码

    无法访问的代码是程序代码的一部分，由于编程结构，它永远不会被访问。程序员可能不小心编写了一段永远无法访问的代码。
    Example: 
    
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 时被删除。所以不用先跳到L1再跳到L2，控制可以直接到达L2，如下图： 
    
...      
MOV R1, R2
GOTO L2
...
L2 :   INC R1

    代数表达式简化

    在某些情况下，代数表达式可以变得简单。例如，表达式a = a + 0可以替换为a本身和表达式 a = a + 1 可以简单地替换为 INC a。

    强度降低

    有些操作会消耗更多的时间和空间。它们的“强度”可以通过将它们替换为消耗更少时间和空间但产生相同结果的其他操作来降低。
    例如，x * 2可以替换为x << 1，它只涉及一次左移。尽管 a * a 和 a 2的输出相同，但 a 2的实现效率更高。

    访问机器指令

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

  • 代码生成器

    代码生成器应该了解目标机器的运行时环境及其指令集。代码生成器在生成代码时应考虑以下事项：
    • Target language：代码生成器必须了解要转换代码的目标语言的性质。该语言可能会促进一些特定于机器的指令，以帮助编译器以更方便的方式生成代码。目标机器可以具有 CISC 或 RISC 处理器架构。
    • IR Type: 中间表示有多种形式。它可以是抽象语法树 (AST) 结构、反向波兰表示法或 3 地址代码。
    • Selection of instruction：代码生成器将中间表示作为输入，并将其转换（映射）为目标机器的指令集。一种表示可以有多种方式（指令）来转换它，因此代码生成器有责任明智地选择合适的指令。
    • Register allocation: 一个程序在执行期间有许多值要维护。目标机器的架构可能不允许将所有值保存在 CPU 内存或寄存器中。代码生成器决定将哪些值保留在寄存器中。此外，它决定了用于保存这些值的寄存器。
    • Ordering of instructions: 最后，代码生成器决定指令的执行顺序。它为指令创建时间表以执行它们。

  • 描述符

    代码生成器在生成代码时必须同时跟踪寄存器（可用性）和地址（值的位置）。对于它们，都使用了以下两个描述符：
    • Register descriptor：寄存器描述符用于通知代码生成器有关寄存器的可用性。寄存器描述符跟踪存储在每个寄存器中的值。每当在代码生成期间需要一个新寄存器时，都会查询该描述符以了解寄存器的可用性。
    • Address descriptor：程序中使用的名称（标识符）的值可能在执行时存储在不同的位置。地址描述符用于跟踪存储标识符值的内存位置。这些位置可能包括 CPU 寄存器、堆、堆栈、内存或上述位置的组合。
    代码生成器实时更新两个描述符。对于加载语句，LD R1, x，代码生成器：
    • updates the Register Descriptor R1 that has value of x and
    • updates the Address Descriptor (x) to show that one instance of x is in R1.

  • 代码生成

    基本块由一系列三地址指令组成。代码生成器将这些指令序列作为输入。
    Note：如果在多个位置（寄存器、缓存或内存）找到名称的值，则寄存器的值将优先于缓存和主内存。同样，缓存的值将优先于主内存。主存储器几乎没有任何偏好。
    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.
    • 确定当前位置z使用与步骤 2 相同的方法y并生成以下指令：
      OPz', L
      在哪里z’表示复制的值z.
    • 现在 L 包含 y OP z 的值，它打算分配给x. 因此，如果 L 是一个寄存器，则更新它的描述符以表明它包含x. 更新描述符x表示它存储在位置L.
    • 如果 y 和 z 没有进一步的用途，可以将它们交还给系统。
    循环和条件语句等其他代码结构以通用汇编方式转换为汇编语言。
上一节:
下一节: