architecture-2022/hw4/loop_unrolling.md

循环展开

1 假设

关于源代码的形式，做如下的假设：

• 除了循环外，源代码中不含其他分支或跳转指令（比如if语句、goto语句、函数调用等）
• 不区分浮点运算和整数运算
• 仅包含形如for i = 0 to n - 1的循环，其中循环变量i在循环体内不会被修改，n是变量

进一步假设源代码中仅包含以下要素：

• 标签：形如label: [instruction]，其中label是标签，[instruction]是某条指令
• 功能型指令：
  • 加载：形如load reg1, offset(reg2)，其中reg是寄存器，offset是某个整数
  • 存储：形如store reg1, offset(reg2)，其中reg是寄存器，offset是某个整数
  • 加法：形如add reg1, reg2, reg3，其中reg1、reg2、reg3是寄存器
  • 移动：形如move reg1, reg2，其中reg1、reg2是寄存器
  • 加立即数：形如addi reg1, reg2, imm，其中reg1、reg2是寄存器，imm是某个整数
  • 空指令：形如nop
• 条件跳转指令：
  • 不相等时跳转：形如bne reg1, reg2, label，其中reg1、reg2是寄存器，label是标签
  • 相等时跳转：形如beq reg1, reg2, label，其中reg1、reg2是寄存器，label是标签

关于寄存器的使用，做如下假设：

• 物理寄存器有32个
• 存储器中有一块专用区域作为虚拟寄存器的交换空间：
  • 交换空间是一块起始地址为0的连续存储空间
  • 交换空间足够大

关于指令排序的约束，做如下假设：

• 5阶段流水线
• 分支延迟1周期，延迟槽中的指令无条件执行
• （其他假设由实现者自行补充在这里）

2 程序结构

整个程序的描述如下：

• 输入：源代码的中间表示
• 输出：经过循环展开和指令重排后的汇编代码
• 约束：输出代码应当能够直接被CPU执行，并且与输入代码等效

我们将整个程序划分为四个模块：

• 循环展开：将代码中的循环展开若干次，展开的次数应当作为参数输入
• 寄存器管理：将代码中使用的虚拟寄存器号转化为物理寄存器号，适当加入与存储器交换的指令
• 指令重排：将指令重新排列，以消除指令之间的冲突，并尽可能地提高执行效率
• 代码生成：将经过处理的中间表示转化为输出代码

2.1 中间表示的形式

• 一个程序是一个列表，其中每一项或者是一个功能型指令、或者是一个循环
• 仅考虑特定形式的for循环，因此一个循环可以用如下结构表示：
  • 循环变量：一个寄存器
  • 循环次数：一个寄存器
  • 循环体：一个程序，即一列功能型指令或循环（允许循环的嵌套）

形式化的表达是这样的：

program ::= [item, item, ..., item]
item ::= function | loop
loop ::= [iterator, times, program]

具体的实现在ir/ir.py中，可以阅读一下

2.2 循环展开模块

循环展开模块的作用是将一个中间表示中的循环展开指定次数，输出也是一个中间表示

实现时注意边界条件，展开后的循环在跳出前的最后一次循环体可能有不一样的形式

实现者可以自行决定嵌套的循环如何展开：

• 展开最内层的循环
• 从内向外展开所有循环
• 将嵌套的循环展开成单层的循环

2.3 寄存器管理模块

在循环展开模块中，通常需要使用更多的寄存器，我们允许指令访问的寄存器号可以是任意的，虚拟寄存器模块负责将这些虚拟寄存器号转化为物理寄存器号

当物理寄存器不够用时，需要将寄存器中的数据移到存储器中，在适当的时候调回（参考虚拟内存中的调页）

寄存器管理模块的输入输出都是一个中间表示，输入中允许访问任意的虚拟寄存器号，输出中仅允许访问有限的物理寄存器号

2.4 指令重排

指令重排模块的作用是将指令重新排列，使其成为满足假设的程序，输入输出都是一个中间表示

在正确的基础上，实现者可以自行决定优化到什么程度（可以先无脑插入nop）

2.5 代码生成模块

代码生成模块的作用是将一个中间表示转化为对应的汇编代码，并输出到指定文件

2 其他事项