|
|
# 循环展开
|
|
|
## 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 其他事项
|
