12 目标代码生成和优化

1 现代微处理器体系结构简介

1.1 指令集架构

Pasted image 20251111091416.png
以 C=A+B 为例

  1. 栈式指令集架构
    类似于P-code和Java虚拟机
    Pasted image 20251111091547.png
    代码：
    PUSH A
    PUSH B
    ADD
    POP C
  2. 累加器式指令集架构
    Pasted image 20251111091608.png
    代码：
    LOAD A
    ADD B
    STORE C
    代码短了，开销不一定小。直接访问内存
  3. 寄存器架构
    • 寄存器-内存指令集架构 CISC
      LOAD R1, A
      ADD R3, R1, B
      STORE R3, C
    • 寄存器-寄存器指令架构 RISC
      LOAD R1, A
      LOAD R2, B
      ADD R3, R1, R2
      STORE R3, C
      区别：是否可以直接内存寻址
      共性：内部有多个寄存器可以直接作为ALU指令的任一操作数
      优点：
    • 减少内存访问
    • 减少指令数
      Pasted image 20251111091822.pngPasted image 20251111091830.png

1.2 存储层次架构

Pasted image 20251111092643.png

  • 为了提高效率，应尽可能少地访问寄存器之外的存储设备

    • 但寄存器的数量极其有限，所以分配策略很重要
    • 对缓存的利用，对于大型数据结构有用
      • 缓存的管理单位是：缓存行。（数十或上百字节）
      • 每次从内存载入的是一组地址连续的数据，而不仅仅是被访问数据

  • 因此，出现了循环交换（Loop Interchange）

    • c 语言存储是行优先，因此下面两段代码中第二段代码运行速度更快
      • 第一段代码外层循环是 j（列），内层循环是 i（行）。- 当 j=0 时，内层循环 i 从 0 到 4999，访问的是 x[0][0], x[1][0], x[2][0], ... x[4999][0]。x[0][0] 和 x[1][0] 在内存中相隔了一整行（100个元素）的距离。这种访问模式是跳跃式的、非连续的，缓存效率极低。
      • 第二段代码外层循环是 i（行），内层循环是 j（列）。当 i=0 时，内层循环 j 从 0 到 99，访问的是 x[0][0], x[0][1], x[0][2], ... x[0][99]。这种访问模式是连续的、顺序的，缓存效率高。
    • 循环交换就是一种通过改变嵌套循环的内外层顺序，来优化数据访问模式的编译器优化技术或手动优化技巧。
// 代码1
for (j = 0; j < 100; j = j+1)
    for (i = 0; i < 5000; i = i+1)
        x[i][j] = 2 * x[i][j];

// 代码2
for (i = 0; i < 5000; i = i+1)
    for (j = 0; j < 100; j = j+1)
        x[i][j] = 2 * x[i][j];

1.3 流水线

可以通过流水线来提高代码的运行效率

  • 如左边的代码按照 I0, I1, I2, I3 的顺序来执行，需要 6 个时钟周期
  • 但我们发现 I2 提前运行也不会影响其它代码的运行，因此选择让 I2 提前运行，并和其他代码同步并行运行
    Pasted image 20251113095222.png

2 地址空间

  • 代码区
    • 存放目标代码
  • 静态数据区
    • 全局变量
    • 静态变量
    • 部分常量，例如字符串
  • 动态内存区
    • 也被称为内存堆Heap
    • 程序员管理：C、C++
    • 自动管理（内存垃圾收集器）：Java、Ada
  • 程序运行栈
    • 活动记录
    • 函数调用的上下文现场
      • 由调用方保存的一些临时寄存器
      • 被调用方保存的一些全局寄存器

2.1 程序地址空间的实例分析

以MS-WIN下的应用程序为例，从高地址到低地址，自上而下的是：

  • 静态数据区：全局和静态量表
  • 代码区
  • 程序运行栈
  • 动态内存区：内存堆
    Pasted image 20251113095744.png

2.2 程序运行栈的设计

  • 子程序/函数运行时所需的基本空间：活动记录
  • 进入子程序/函数时分配，地址空间向下生长（从高地址到低地址）
  • 从子程序/函数返回时，当前运行栈将被废弃
  • 递归调用的同一个子程序/函数，每次调用都将获得独立的运行栈空间，从而保证了递归程序和多线程程序的正确运行

一个典型的运行栈包括 （活动记录）

  • 函数的返回地址
  • 全局寄存器的保存区
  • 临时变量的保存区
  • 未分配到全局寄存器的局部变量的保存区
  • 其他辅助信息的保存区：例，PASCAL/PL-I类语言的DISPLAY区
函数foo的运行栈

Pasted image 20251113100203.png
Pasted image 20251113100221.png
ESI：通常在内存操作指令中作为“源地址指针”使用。
EDI：通常在内存操作指令中作为“目的地址指针”使用。

RISC架构上的运行栈

Pasted image 20251113100305.png

3 寄存器的分配和指派

  • 寄存器通常分为
    • 通用寄存器
      • X86：EAX, EBX, ECX, EDX, ESI, EDI, EBP, ESP, etc
      • ARM: R0~R15, etc
    • 专用寄存器
      • X86：浮点寄存器栈, etc
  • 通用寄存器
    • 保留寄存器
      例如，X86的ESP栈指针寄存器，ARM的返回寄存器LR
    • 调用方保存的寄存器——临时寄存器
      • caller-saved register
      • X86：EAX, ECX, EDX
      • ARM：R0~R3, R12, LR
    • 被调用方保存的寄存器——全局寄存器
      • callee-saved register
      • X86：EBX, ESI, EDI, EBP （ESP为运行栈寄存器，不参与寄存器分配）
      • ARM：R4~R11

3.1 全局寄存器分配

  • 全局寄存器分配：
    • “全局”相对于“基本块”而言，不是“程序全局”
    • 全局寄存器分配的对象主要是函数的局部变量，包括函数入口参数。
  • 分配原则
    • 优先分配给跨基本块仍然活跃的变量，尤其是循环体内最活跃的变量
    • 局部变量参与全局寄存器分配
      寄存器专属于线程！为了线程安全，全局变量/静态变量一般不参与全局寄存器分配。
如果全局/静态量参与寄存器分配？

全局变量和静态变量一般不参与全局寄存器分配，即使他们在某个循环体中被多次访问
这是因为当一个全局变量或静态变量的值保存在于寄存器中时，如果发生线程切换，当前的寄存器状态将作为线程现场被保存，切入线程将恢复其此前保存的寄存器状态，这就导致了其他线程无法得到该寄存器在此前线程中的值，程序运行可能会发生不可预知的错误。
Pasted image 20251113101339.png

  • 常用全局寄存器分配方法
    • 引用计数
      通过统计变量在函数内被引用的次数，并根据被引用的特点赋予不同的权重，最终为每个变量计算出一个唯一的权值，根据权值的大小排序，将全局寄存器依次分配给权值最大的变量
    • 着色图算法
      通过构建变量之间的冲突图，在图上应用着色算法，将不同的全局寄存器分配给有冲突的变量。

1 引用计数

  • 原则：如果一个局部变量被访问的次数较多，那么它获得全局寄存器的机会也较大
  • 注意：出现在循环，尤其是内层嵌套循环中的变量的被访问次数应该得到一定的加权
  • 分配算法：如果有N个全局寄存器可供分配，则前N个变量拥有全局寄存器，其余变量在程序运行栈（活动记录）分配存贮单元
  • 问题：不再使用的变量不能及时释放寄存器
    如变量 a 在前期大量使用，后端程序中不适用了
  • 解决办法：
    • 活跃变量分析、冲突图
    • 着色算法
例子：3个局部变量，2个全局寄存器可供分配，谁将获得寄存器？

Pasted image 20251113101836.png
不加权时

  • a：3 次
  • b：4 次
  • j：5 次

加权时（循环加权值为 10）

  • a：30 次
  • b：3 次
  • j：32 次

2 图着色算法

  • 一种简化的图着色算法
    步骤：
    1. 通过数据流分析，构建变量的冲突图
    2. 如果可供分配k个全局寄存器，那么我们就尝试用k种颜色给该冲突图着色
  1. 通过数据流分析，构建变量的冲突图
    什么是变量的冲突图？
    • 它的结点是待分配全局寄存器的变量
    • 当两个变量中的一个变量在另一个变量定义（赋值）处是活跃的，它们之间便有一条边连接。所谓变量i在代码n处活跃，是指程序运行时变量i在n处拥有的值，在从n出发的某条路径上会被使用（活跃变量分析）。
    • 直观的理解，可以认为有边相连的变量，它们无法共用一个全局寄存器，或者同一存贮单元，否则程序运行将可能出错
    • 无连接关系的变量，即便它们占用同一全局寄存器，或同一存贮单元，程序运行也不会出错
  2. 如果可供分配 k 个全局寄存器，那么我们就尝试用 k 种颜色给该冲突图着色
例子

Pasted image 20251113103208.png
Pasted image 20251113103216.png
Pasted image 20251113103241.png
Pasted image 20251113103250.png

!!!算法12.2 一种启发式图着色算法

冲突图 G，寄存器数目为 k（假设 k=3）
Pasted image 20251113104227.png

  1. 找到第一个连接边数目小于K的结点，将它从图G中移走，形成图G’
    Pasted image 20251113104243.png
  2. 重复步骤1，直到无法再从G’中移走结点
    Pasted image 20251113104301.png
  3. 在图中选取适当的结点，将它记录为“不分配全局寄存器”的结点，并从图中移走
    Pasted image 20251113104445.png
  4. 重复步骤1~步骤3，直到图中仅剩余1个结点
    Pasted image 20251113104511.png
  5. 给剩余的最后一个结点选取一种颜色，然后按照结点被移走的顺序，反向将结点和边添加进去，并依次给新加入的结点选取颜色。（保证有链接边的结点着不同的颜色）
    Pasted image 20251113104841.png

3.2 临时寄存器分配

为什么在代码生成过程中，需要对临时寄存器进行管理？

  • 因为生成某些指令时，必须使用指定寄存器
  • 临时寄存器中保存有此前的计算中间结果

临时寄存器的管理原则和方法

  • 临时寄存器的生存范围
    • 不超越基本块
    • 不跨越函数调用
  • 临时寄存器的管理方法：寄存器池
例子

Pasted image 20251113105426.png

临时寄存器的分配和管理方法

  • 进入基本块时，清空临时寄存器池
  • 为当前中间代码生成目标代码时，无论临时变量还是局部变量（亦或全局变量和静态变量），如需使用临时寄存器，都可以向临时寄存器池申请
  • 临时寄存器池接到申请后，
    • 如寄存器池中有空闲寄存器，则可将该寄存器标识为被该申请变量占用，并返回该空闲寄存器
    • 如寄存器池中没有空闲寄存器，则选取一个在即将生成代码中不会被使用的寄存器写回相应的内存空间，标识该寄存器被新的变量占用，返回该寄存器
  • 在基本块结尾，或者函数调用发生前，将寄存器池中所有被占用的临时寄存器写回相应的内存空间，清空临时寄存器池

4 指令选择

不同的体系结构采用了不同类型的指令集，由于体系结构和指令集的差异，使得在生成代码时需要采用不同的指令选择策略

Pasted image 20251113110001.png
Pasted image 20251113110016.png

Built with MDFriday ❤️