# FDMJCompiler

**Repository Path**: demon0511/fdmjcompiler

## Basic Information

- **Project Name**: FDMJCompiler
- **Description**: 复旦大学2023春编译(H)：使用C语言，基于虎书的编译器框架，实现针对FDMJ（FuDan Mini Java）语言的编译器；本编译器拥有1个前端，将FDMJ生成Tiger IR+；2个后端，分别将Tiger IR+生成ARM assem和LLVM IR并可执行
- **Primary Language**: C
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 1
- **Created**: 2023-05-08
- **Last Updated**: 2025-04-07

## Categories & Tags

**Categories**: Uncategorized

**Tags**: C语言, Compiler, FDMJ, Llvm, arm

## README

# 复旦大学2023春编译(H)

> 20307130136 林琰钧

# 1. 总述

## 1.1. 编译器功能

- 本编译器的功能是将FDMJ（FuDan Mini Java）语言编译为可运行的文件

## 1.2. 编译器构成

- 本编译器的构成如下

  ![structure](docs/structure.png)
- 1个前端：将FDMJ生成Tiger IR+
- 2个后端：分别将Tiger IR+生成ARM assem和LLVM IR

## 1.3. 编译流程

- 本编译器的编译流程如下

  ![procedure](docs/procedure.png)
- 前端

  - 用lex和yacc模块【DIY】将testx.fmj中的FDMJ生成AST
  - 用semant模块【DIY】对AST进行检查，将第一条报错信息输出为 `.output`文件并终止程序
  - 用translate模块【DIY】在类型检查的同时生成Tiger IR+树（IR Trees）
- ARM后端：对Tiger IR+树中的每个method做如下流程

  - 用canon模块【已给】对Tiger IR+线性化（linearize），然后拆分成一系列Tiger IR+基本块（basic block），然后对基本块进行重排（trace）变成一串语句，然后重新分解为基本块
  - 用armgen模块【DIY】以Tiger IR+基本块为单位将Tiger IR+指令选择为ARM基本块同时加入起始块
  - 用bg模块【DIY】将一系列ARM基本块生成ARM基本块图（basic block graph）同时做死代码删除
  - 用assemblock模块【已给】对ARM基本块进行重排（trace），然后加入函数开头和结尾，生成ARM指令流
  - 用flowgraph、liveness和ig【已给】对ARM指令流进行活跃分析，并生成冲突图
  - 用regalloc模块【DIY】进行ARM的寄存器分配
  - 用assem模块【已给】输出 `.s`文件
  - 用gcc指令与外部库libsysy.s进行链接，输出 `.out`文件
- LLVM后端：对Tiger IR+树中的每个method做如下流程

  - 用canon模块【已给】对Tiger IR+线性化（linearize），然后拆分成一系列Tiger IR+基本块（basic block），然后对基本块进行重排（trace）变成一串语句，然后重新分解为基本块
  - 用llvmgen模块【DIY】以Tiger IR+基本块为单位将Tiger IR+指令选择为LLVM IR基本块同时加入起始块
  - 用bg模块【DIY】将一系列LLVM IR基本块生成LLVM IR基本块图（basic block graph）同时做死代码删除
  - 用ssa模块【DIY】将LLVM IR基本块图中原始的LLVM IR转换为一系列SSA形式的LLVM IR基本块
  - 用assemblock模块【已给】对LLVM IR基本块进行重排（trace），然后加入函数开头和结尾，生成LLVM指令流
  - 用flowgraph、liveness和ig【已给】对ARM指令流进行活跃分析，并生成冲突图（LLVM的这步其实没必要，但为了完整性还是加上了）
  - 用assem模块【已给】输出 `.ll`文件
  - 用lli指令与外部库libsysy.ll进行链接，输出 `.ll.ll`文件
- 编译过程中，会生成lex&yacc、translate、canonicalize、liveness analysis的debug信息，分别输出于 `.ast`、`.irp`、`.stm`、`.liv`文件中
- 注：【DIY】指自己编写的代码，【已给】指课程提供的代码

# 2. 部署

## 2.1. 项目结构

```tree
.
├── build CMake命令构建产生的文件夹
│   └── ...
├── docs README.md所引用的一些资源存放的文件夹
│   └── ...
├── include 头文件
│   ├── backend
│   │   ├── arm
│   │   │   ├── armgen.h
│   │   │   └── regalloc.h
│   │   └── llvm
│   │       ├── llvmgen.h
│   │       └── ssa.h
│   ├── frontend
│   │   ├── semant.h
│   │   └── translate.h
│   ├── optimizer
│   │   ├── bg.h
│   │   ├── canon.h
│   │   ├── flowgraph.h
│   │   ├── ig.h
│   │   └── liveness.h
│   └── utils
│       ├── dsa
│       │   ├── assem.h
│       │   ├── assemblock.h
│       │   ├── env.h
│       │   ├── fdmjast.h
│       │   ├── frame.h
│       │   ├── graph.h
│       │   ├── symbol.h
│       │   ├── table.h
│       │   ├── temp.h
│       │   ├── treep.h
│       │   ├── types.h
│       │   └── util.h
│       └── printer
│           ├── pr_linearized.h
│           ├── pr_tree_readable.h
│           ├── printast.h
│           └── printtreep.h
├── lib 源文件
│   ├── CMakeLists.txt
│   ├── backend 编译器后端
│   │   ├── CMakeLists.txt
│   │   ├── arm arm后端
│   │   │   ├── CMakeLists.txt
│   │   │   ├── armgen.c ARM指令选择器
│   │   │   └── regalloc.c ARM寄存器分配器
│   │   └── llvm llvm后端
│   │       ├── CMakeLists.txt
│   │       ├── llvmgen.c LLVM指令选择器
│   │       └── ssa.c LLVM静态单赋值器，将翻译出的LLVM IR转换为SSA
│   ├── frontend 编译器前端
│   │   ├── CMakeLists.txt
│   │   ├── lexer.lex 词法分析器，将FDMJ转换为tokens
│   │   ├── parser.yacc 语法分析器，将tokens转换为AST
│   │   ├── semant.c 语义分析器，实现类型检查与翻译
│   │   └── translate.c 将ast翻译成IR
│   ├── optimizer 分析与优化IR
│   │   ├── CMakeLists.txt
│   │   ├── bg.h 基本块图生成器
│   │   ├── canon.h IR标准化器
│   │   ├── flowgraph.h 控制流分析器
│   │   ├── ig.h 冲突图生成器
│   │   └── liveness.h 数据流分析器
│   └── utils 工具
│       ├── CMakeLists.txt
│       ├── dsa 数据结构与算法
│       │   ├── assem.c 指令选择所需的数据结构
│       │   ├── assemblock.c 以基本块为单位做指令选择所需的数据结构
│       │   ├── env.c 符号表表项数据结构
│       │   ├── fdmjast.c FDMJ抽象语法数据结构
│       │   ├── frame.c 寄存器与栈帧相关
│       │   ├── graph.c 流图所需的数据结构
│       │   ├── symbol.c 符号表数据结构，table的封装
│       │   ├── table.c 抽象哈希表数据结构
│       │   ├── temp.c 用于生成IR中的寄存器与标记编号
│       │   ├── treep.c IR树抽象数据结构
│       │   ├── types.c 类型数据结构
│       │   └── util.c 工具变量和函数的定义
│       └── printer 打印输出以便调试
│           ├── pr_linearized.c 打印IR线性化的结果
│           ├── pr_tree_readable.c 打印IR(可读性强)
│           ├── printast.c 打印AST为FMJ
│           └── printtreep.c 打印IR
│── test .fmj测试文件
│   └── xxx.fmj 写有FDMJ的文件
│── tools 最终用户的应用程序
│   ├── CMakeLists.txt
│   ├── ARMCompiler.c 编译fmj文件为ARM的.s文件
│   └── LLVMCompiler.c 编译fmj文件为LLVM的.ll文件
├── vendor 外部链接库
│   ├── libsysy32.c 32位的外部库
│   ├── libsysy32.h
│   ├── libsysy64.c 64位的外部库
│   └── libsysy64.h
├── CMakeLists.txt CMake构建文件
├── LICENSE 许可证
├── Makefile 构建、测试、清理命令
└── README.md 本文件
```

## 2.2. 环境配置

想要运行本编译器，需要按照如下步骤进行环境配置：

- Ubuntu20.04 LTS（Windows的Linux子系统，wsl） ：自行按网站教程安装
- 安装gcc和g++（用于编译c程序）

  ```bash
  sudo apt-get install gcc g++ 
  ```
- 安装lex和yacc（用于编译器的词法分析和语法分析）

  ```bash
  sudo apt-get install flex bison
  lex --version
  Yacc --version
  ```
- 安装clang-14和llvm-14（需要14版本或以上，用于执行.ll文件，同时使用--opaque-pointer）

  ```bash
  # clang-14和llvm-14 (Unbuntu22版本会自动安装最新版，但Unbuntu20版本需要手动安装)
  wget -O - https://apt.llvm.org/llvm-snapshot.gpg.key | sudo apt-key add -
  sudo add-apt-repository "deb http://apt.llvm.org/focal/ llvm-toolchain-focal-14 main"
  sudo apt-get update
  sudo apt-get install clang-14
  sudo apt-get install llvm-14
  clang-14 -v
  lli-14 --version
  ```
- 安装交叉编译器（用于将汇编语言转变为arm机器码）

  ```bash
  cd ~/software
  # 下载 gcc-arm-8.2-2018.11-x86_64-arm-linux-gnueabihf.tar.xz
  wget https://armkeil.blob.core.windows.net/developer/Files/downloads/gnu-a/8.2-2018.11/gcc-arm-8.2-2018.11-x86_64-arm-linux-gnueabihf.tar.xz
  tar xf gcc-arm-8.2-2018.11-x86_64-arm-linux-gnueabihf.tar.xz
  echo "export PATH=~/software/gcc-arm-8.2-2018.11-x86_64-arm-linux-gnueabihf/bin:$PATH" >> ~/.bashrc
  # 重启终端，然后查看版本
  arm-linux-gnueabihf-g++ -v
  ```
- 安装qemu模拟器（用于执行交叉编译出的arm机器码）

  ```bash
  sudo apt install ninja-build pkg-config libglib2.0-dev
  cd ~/software
  # 下载 qemu-6.2.0.tar.xz
  wget https://download.qemu.org/qemu-6.2.0.tar.xz
  tar xf qemu-6.2.0.tar.xz
  cd qemu-6.2.0
  mkdir build
  cd build
  ../configure --target-list=arm-linux-user
  make -j4
  sudo make install
  qemu-arm --version
  ```
- 安装Cmake（需要3.20.0版本或以上，用于项目构建）

  ```bash
  # Cmake3.20.0 (Unbuntu22版本会自动安装最新版，但Unbuntu20版本需要手动安装)
  cd $HOME
  sudo apt update
  sudo apt install -y libssl-dev
  wget https://github.com/Kitware/CMake/releases/download/v3.20.0/cmake-3.20.0-linux-x86_64.tar.gz
  tar -xzvf cmake-3.20.0-linux-x86_64.tar.gz
  echo 'export PATH="$HOME/cmake-3.20.0-linux-x86_64/bin:$PATH"' >> ~/.bashrc
  source ~/.bashrc
  cmake --version
  ```
- 安装Ninja（用于快速运行CMake）

  ```bash
  sudo apt-get install ninja-build
  ```

## 2.3. 编译运行

- 建立 `test`文件夹并编写 `testx.fmj`文件，输入某个特定的FDMJ
  - 支持libsysy中的putint, putch, putarray, getint, getch, getarray, starttime, stoptime
  - 支持malloc（汇编时自动生成，程序中当然不能出现）
- 在主文件夹打开wsl命令行，依次进行如下操作：
  - 构建安装：`make build`使用CMake和Ninja，在 `build`文件夹下进行构建和安装，其中：
    - `bin`文件夹下的 `ARMCompiler`和 `LLVMCompiler`是可执行文件，用于编译
    - `extlib`文件夹下的 `libsysy32.s`和 `libsysy64.ll`是外部库文件，用于链接
  - 测试运行：
    - ARM环境：`make runarm`将会对 `test`文件夹下所有的 `testx.fmj`文件
      - 先使用 `ARMCompiler`进行编译生成 `testx.s`文件
      - 然后与 `libsysy32.s`进行链接生成 `testx.s.out`文件
      - 最后执行 `qemu-arm`命令运行
    - LLVM环境：`make runllvm`将会对 `test`文件夹下所有的 `testx.fmj`文件
      - 先使用 `LLVMCompiler`进行编译生成 `testx.ll`文件
      - 然后与 `libsysy64.ll`进行链接生成 `testx.ll.ll`文件
      - 最后执行 `lli`命令运行
  - 清理：
    - `make clean`清除 `test`文件夹下的所有中间文件
    - `make veryclean`先执行 `make clean`，然后清除CMake产生的 `build`文件夹
    - `make rebuild`先执行 `make veryclean`，然后执行 `make build`重新构建

# 3. 细节【DIY】

![procedure_hw](docs/procedure_hw.png)

- 以下提到的所有阅读材料均在 `docs`文件夹中

## 3.1. Lex & Parse (hw3 ~ hw4)

1. 阅读 `Lex−A_Lexical_Analyzer_Generator(Lesk)`、`Yacc-Yet_Another_Compiler-Compiler(Johnson)`、`虎书的2-3章`、第二周实验课的 `MiniLexYacc`指南，学习词法分析和语法分析的原理以及如何使用Lex和Yacc工具。

   - lexer.lex以终结符为输入（源代码即一系列终结符），向parser.yacc返回token；parser.yacc则以token为输入，根据每个非终结符的规则进行解析（规则即 `FDMJ.md`中的文法），最后构建出AST（即在parse的过程中同时做parse action）；Lex和Yacc共同维护了各个AST结点的位置。

     ![Lex&Yacc](docs/Lex&Yacc.png)
   - 这两个文件都分为三个部分，两个部分之间用两个百分号%%隔开：

     ```text
     声明部分
     %%
     规则部分
     %%
     辅助函数
     ```
2. Lex（根据 `FDMJ.md`的文法）：

   1. 确定AST类型、终结符，在paser.yacc声明部分定义yylval、termianl symbols（即所谓token）。
   2. 在lexer.lex的声明部分包含y.tab.h，并定义状态转移（默认是INITIAL，引入以支持注释）
   3. 在lexer.lex的规则部分添加lexer规则
3. Yacc（根据 `FDMJ.md`的文法）：

   1. 确定非终结符、开始符，在paser.yacc声明部分定义non-termianl symbols, start symbol
   2. 按照C语言运算符优先级，在parser.yacc的声明部分定义precedence
   3. 在parser.yacc的规则部分添加yacc规则

## 3.2. Type Checking (hw5 ~ hw6)

### 3.2.1. 数据结构

- Ty_ty会用到以下3种（type.h）
  - Ty_int：变量类型是整型，Ty_Int()
  - Ty_array：变量类型是整型数组，Ty_Array(Ty_Int())
  - Ty_name：变量类型是名为class_id的类，Ty_Name(class_id, NULL)
- S_table中存储S_symbol到E_enventry的映射，E_enventry有以下3种（env.h）
  - E_varEntry：变量或常量声明
    - vd：A_varDecl类型，用于继承时如果发生重定义错误时输出pos
    - ty：Ty_ty类型，用于标识其类型，可能是Ty_int或Ty_array或Ty_name
  - E_classEntry：类声明
    - cd：A_classDecl类型，用于检测到循环时输出pos
    - fa：S_symbol类型，用于记录父类名
    - status：E_status类型，用于环检测
    - vtbl：S_table类型，用于存储类的变量声明
    - mtbl：S_table类型，用于存储类的方法声明
  - E_methodEntry：方法声明
    - md：A_methodDecl类型，用于继承时如果发生重定义错误时输出pos
    - from：S_symbol类型，用于记录方法的来源类名
    - ret：Ty_ty类型，用于标识返回值类型，可能是Ty_int或Ty_array或Ty_name
    - fl：Ty_fieldList类型，用于存储方法参数列表类型，由Ty_fieldList(Ty_field(var_id, var_ty), Ty_fieldList(…))构成
- 每个S_table中存储的只能是E_enventry的3种类型之一（semant.c）
  - cenv：类环境（class environment）
    - class_id →  E_classEntry
    - vtbl：类变量环境（variable environment）
      - var_id →  E_varEntry
    - mtbl：类方法环境（method environment）
      - meth_id →  E_methodEntry
  - venv：变量环境（variable environment）
    - var_id →  E_varEntry

### 3.2.2. 代码流程

1. 初始阶段：初始化静态全局变量（静态是为了仅在本文件中使用，全局是为了函数少传些参数）
   1. cenv：类环境
   2. venv：变量环境
   3. MAIN_CLASS：一个dummy class的名字，是所有没有extend的类的父类
   4. cur_class_id：目前正在检查的类名，在类型检查阶段使用
   5. cur_method_id：目前正在检查的方法名，在类型检查阶段使用
2. 预处理阶段：检查并建立cenv
   1. 遍历类：
      - 记录extend关系
      - 检查类变量与方法是否重定义
      - 记录类变量与方法到cenv
   2. 遍历类：查看是否有父类，如果有，先递归做父类，然后将父类变量与方法复制到子类
      - 能够检查extend关系是否有循环
      - 如果变量与父类中的同名，报错重定义
      - 如果方法与父类中的同名，检查签名是否相同(返回值和参数列表类型)，若不同则报错
3. 类型检查阶段：检查类和主方法
   1. 遍历类：
      - 检查类变量
      - 检查类方法
   2. 检查主方法
   3. 遍历方法时会遇到变量声明、stm和exp，需要特别注意
      - 每次进入一个方法S_beginScope(venv)，检查退出后S_endScope(venv)
      - 类变量、方法变量（包括方法的参数），都不能重定义
      - 检查类型为class的变量时，需要查询cenv看这个class是否存在
      - 赋值给类型为class的变量时，需要检查是否为其本身或其子类

## 3.3. Translate (hw7 ~ hw8)

基本策略是一边做类型检查一边翻译

- 类型检查在transXXX的函数体，即为hw5&hw6的实现（semant）
- 翻译在transXXX的return部分，通过调用专用的翻译函数实现（translate）

### 3.3.1. 数据结构

- 按照虎书上的描述，设计Tr_exp，用以将semant和translate模块解耦合（translate）
  - Ex代表有返回值的exp，包装了T_exp
  - Nx代表无返回值的stm，包装了T_stm
  - Cx代表条件语句，包装了T_stm，以及真假label的两个patchList
- 用Tr_Ex, Tr_Nx, Tr_Cx将T_exp, T_stm, Cx包装为Tr_exp（translate）
- 用unEx, unNx, unCx将Tr_exp转换为T_exp, T_stm, Cx，即实现3类Tr_exp的相互转换（translate）
  - unEx
    - Tr_ex直接返回其中的T_exp
    - Tr_nx用T_Escq返回0，这是自定义的返回值，没有实际意义
    - Tr_cx会填充patchList，并利用T_Escq根据真假label返回1或0
  - unNx
    - Ex用T_Exp包装其中的T_exp返回
    - Tr_nx直接返回其中的T_stm
    - Tr_cx会填充patchList，并根据真假label将一个临时变量赋值为1或0，没有实际意义
  - unCx
    - Tr_ex用T_Cjump根据其中的T_exp是否等于0占位真假patchList返回Cx
    - Tr_nx无法包装为Cx，会报错
    - Tr_cx直接返回其中的Cx

### 3.3.2. 代码细节

- 运算
  - 算术运算（+, -, ...）：包装成T_Binop，返回Tr_Ex
  - 比较运算（>, <, ...）：包装成T_Cjump，其中真假label的patchList待填充，返回Tr_Cx
  - or：填充第一个Exp的false label为next，将两个Exp的true label给join起来待填充，第二个Exp的false label也待填充，返回Tr_Cx
  - and：填充第一个Exp的true label为next，将两个Exp的false label给join起来待填充，第二个Exp的true label也待填充，返回Tr_Cx
  - 取反运算：使用unCx获得一个Cx，交换其真假label的patchList，返回Tr_Cx
- 赋值：
  - 使用unEx获得一个T_exp然后赋值
- 条件
  - if
    - 使用unCx获得一个Cx，然后对patchList进行填充，据是否有else返回不同的语句
  - while
    - 使用unCx获得一个Cx，然后对patchList进行填充，据是否有loop返回不同的语句
    - 在semant模块中会维护whiletests和whileends两个标签栈，以检查continue和break是否在while中
- 数组
  - 初始化：int[] a={ConstList}
    - 调用malloc分配空间，然后通过计算偏移并取Mem为某位置赋值
  - 赋值：a[]={expList}，a=new int[exp]
    - 同上
  - 存储：exp[exp]
    - 通过计算偏移并取Mem获取某位置
  - 注意：由于数组需要多存储一个长度字段，因此数组需要多malloc一个长度字段。malloc后返回第一个地址作为数组指针的值，把数组长度存在-1，这样便于之后取数组元素时下标不用再加1了
- method列表
  - 在构建method列表时，main method为首，class method跟随其后
  - 命名
    - main method名为main
    - 假设class名为c，c中有一个method名为m，则该class method名为c_m
  - 参数列表
    - main method的参数列表为空
    - 所有class method的参数列表中，第一个参数统一为t99，表示this，剩下的为定义的参数
- Unified Object Record
  - 起初，偏移表varoff和methoff为空，globaloff为0
  - 预处理时（transA_xxx_basic函数）
    - 每遇到一个var，如果varoff中没有此id，则记录映射id->globaloff到varoff，然后globaloff递增
    - 每遇到一个meth，如果methoff中没有此id，则记录映射id->globaloff到methoff，然后globaloff递增
  - 最终，globaloff为所有class的所有var和method的数量（var同名只算一次，meth同名只算一次），varoff和methoff记录相应var和meth的偏移量（所有偏移的单位都是ARCH_SIZE）
- class主要有3种操作
  - new类：先新建一个temp，为其分配globaloff大小的空间，然后根据id遍历其vtbl和mtbl，进行必要的初始化
    - 由于在vtbl和mtbl中记录了A_varDecl，因此容易对变量进行初始化
    - 由于在mtbl中记录了method的类来源from，因此容易对方法m进行初始化为from_m以实现多态（多态在FDMJ里便从运行时提到了编译时）
  - 类变量：通过varoff找到var的位置
  - 类方法：通过methoff找到meth的位置，然后进行函数调用，传参数时需要额外传递obj的temp

## 3.4. Instruction Selection for LLVM (hw9 ~ hw10)

根据 `LLVM IR Mini.md`，按照如下tiling规则进行LLVM IR的指令选择

![tiling_LLVM](docs/tiling_LLVM.png)

## 3.5. SSA for LLVM (hw12)

- 在bg.c中加入死代码删除的逻辑，以免SSA从起始结点开始遍历的时候遍历不到那些死结点导致错误。所谓死代码，就是那些没有前驱的结点（除了起始节点以外），这可能是由于fmj中在return或break语句之后还写了其他语句，因此在拆分为basic block的过程中产生新label导致的，变成了没有前驱的死结点
  - 方法是在create_bg末尾一直遍历，每次遇到除了开始结点以外没前驱的就删掉其出边及其本身（图结点会越来越少），当图结点不变时就是结束，这样就做到了死代码删除
- SSA主要逻辑在ssa.c中，其中的算法参考虎书10、17、18、19，流程如下：
  - init：初始化全局变量
    - 以图结点的mykey做索引，初始化图数组cfg，这样方便拓扑排序记录图结点的次序到sorted数组；以图结点的label做索引，初始化图哈希表benv，这样以后label就可以视为图结点，便于labellist进行集合交并补操作
    - 记录每个变量到数组var中，方便后续对变量进行遍历
    - 此外，还有大量S_table形式的全局变量用来记录必要的信息
    - 确定每个结点的def和use时需要注意：
      - 在llvmgen之后bg之前，会插入一个dummy结点，其中有唯一一条语句是跳转到下一个block，这样传入的参数可以视为在该结点def，同时避免第一个结点有前驱的问题（防止函数一上来就while循环，LLVM报第一个block不能有前驱错误）
      - 由于书里做liveness时，每个结点是一条语句，而这里的每个结点是多条语句，因此新增一个有关use的规则：如果block内的某个变量在use之前def了，就不算use（避免像icmp这样产生的只在一个block中存在的临时变量）
  - topo_sort：对输入的有环图cfg进行类拓扑排序，以便优化后续大部分算法的效率
    - 算法详见虎书ch-17.4.3
  - liveness：对各block进行活跃分析，确定in和out，以辅助insert_phi
    - 算法详见虎书ch-10.1.1
    - 这里使用了拓扑排序的结果，自底向上遍历结点，可以显著地加快算法的收敛过程
  - find_dom：计算必经结点（dominator, dom），以辅助find_idom
    - 算法详见虎书ch-18.1.1
    - 这里使用了拓扑排序的结果，自顶向下遍历结点，可以显著地加快算法的收敛过程
  - find_idom：计算直接必经结点（intermidiate dominator, idom）与必经结点树（idom_tree），以辅助find_df
    - 算法详见虎书ch-18.1.2
    - idom利用其3条性质计算，计算idom时反向引用即可得出idom_tree
  - find_df：计算必经结点边界，以辅助insert_phi
    - 算法详见虎书ch-19.1.2
  - insert_phi：插入phi函数
    - 算法详见虎书ch-19.1.3（算法倒2行应改成$A_{orig}[Y]$）
    - 必经结点边界标准：只要结点x包含某个变量a的一个定值，则x的必经结点边界中的任何结点z都需要有一个a的phi函数。修正：还要判断，如果结点n插入a的phi，那么在结点n中a是live in的（否则会插入大量无关的临时变量，LLVM报向前引用错误）
  - rename_var：重命名变量
    - 算法详见虎书ch-19.1.4
    - 有个区别是直接使用stack数组存temp的list即可，每次new一个temp，无需count编号；同时，为了防止栈内的变量找不到，用repo存temp的list，在stack进行push的时也push，但永远不pop

## 3.6. Instruction Selection for ARM (hw13)

根据 `ARM.md`，按照如下tiling规则进行ARM的指令选择

![tiling_ARM](docs/tiling_ARM.png)

## 3.7. Register Allocation for ARM (hw14)

- ARM中的寄存器分为

  - Caller-Saved（调用者保存）寄存器

    | 主要名称 | 别名 | 别名全称                              | 说明                     |
    | -------- | ---- | ------------------------------------- | ------------------------ |
    | r0-r3    |      |                                       | 存储函数参数、函数返回值 |
    | r12      | IP   | Intra-Procedure-call scratch register | 临时存储寄存器           |
    | r14      | LR   | Link Register                         | 返回地址寄存器           |


    - r0-r3和ip在调用函数前要保存（作为def），因为被调用的函数可能修改
    - lr在开头要保存（入栈），在结尾要使用（出栈为pc）
  - Callee-Saved（被调用者保存）寄存器

    | 主要名称 | 别名 | 别名全称        | 说明                                 |
    | -------- | ---- | --------------- | ------------------------------------ |
    | r4-r10   |      |                 | 存储临时数据、中间计算结果和局部变量 |
    | r11      | FP   | Frame Pointer   | 帧指针                               |
    | r13      | SP   | Stack Pointer   | 栈指针                               |
    | r15      | PC   | Program Counter | 程序计数器                           |


    - r4-r10在开头要保存（入栈），在结尾要恢复（出栈）
    - fp不能用于其他用途，在开头要保存（入栈），在结尾要恢复（出栈）
    - sp不能用于其他用途，在函数返回时通过pop指令恢复
    - pc不能用于其他用途，在函数返回时通过出栈lr恢复
  - N/A（不适用）寄存器

    | 主要名称 | 别名 | 别名全称                | 说明           |
    | -------- | ---- | ----------------------- | -------------- |
    | CPSR     | PSR  | Program Status Register | 程序状态寄存器 |
- 寄存器分配的思路为

  - 约定：

    - 将r0-r9作为简化寄存器（simplify的着色）
    - 将r10, ip(r12), lr(r14)作为溢出寄存器（spill的着色）
  - 流程：

    ![regalloc](docs/regalloc.png)

    - 构造（build）：通过活跃分析生成冲突图，结点代表临时变量，边代表冲突（同时活跃，或其他约束，导致不能分配同一个寄存器）；将可用寄存器划分为简化寄存器和溢出寄存器，分别用于简化和溢出的着色；将所有可用寄存器着色为本身，以便那些本身就是可用寄存器的临时变量在之后的流程保持不变（比如在ARM中r0~r3用于函数的前4个参数传递）
    - 简化（simplify）：不断从图中删除未着色、低度数的结点，推入简化结点栈。低度数指目前结点的度小于简化寄存器数，这能够保证在后续步骤重新加入该结点时一定有颜色可着。
    - 潜在溢出（potential_spill）：当简化步骤无法进行时，尝试从图中找一个未着色的结点删除，推入溢出结点栈。如果能找到，则重新进行简化阶段，否则进行着色阶段。
    - 着色（color）：首先，不断从简化结点栈弹出结点，重新加入图中，并选择不与邻居冲突的简化寄存器着色；然后，不断遍历溢出结点栈，每次选择一个假溢出的结点重新加入图中，假溢出指可以找到一个不与邻居冲突的简化寄存器着色；最后，如果溢出节点栈还有结点，说明是真溢出，则为每个结点在栈中预留一块空间，留以后续处理。
    - 调整（adjust）：如果存在真溢出结点，则偏移sp为其预留空间；然后，遍历每条指令，如果存在颜色映射，则将其替换为映射到的简化寄存器；如果不存在颜色映射（真溢出），则分配一个溢出寄存器r，若其为dst，则将值存入r，然后将r的值保存到栈帧，若其为src，则从栈帧中取出值到r，然后使用r，该条指令结束后释放r。
- 为了方便起见

  - 程序开始时push {r4, r5, r6, r7, r8, r9, r10, fp, lr}
  - 程序结束时pop {r4, r5, r6, r7, r8, r9, r10, fp, pc}
  - 因此栈帧布局如下：

    ```text
    +------+
    +  r4  + <- fp
    +------+
    + .... +
    +------+
    +  r10 +
    +------+
    +  fp  +
    +------+
    +  lr  + (fp - 32)
    +------+
    +spill1+
    +------+
    + .... +
    +------+
    +spilln+ <- sp (begin)
    +------+ |
    + .... + | function call, sp move down
    +------+ |
             V
    ```

# 4. 细节【已给】

## 4.1. Canon (hw9)

转换过程分以下三步进行。

1. 通过C_linearize将一棵树重写成规范树（canonical tree）

   - 规范树是一个线性的list
     - RULE-1. 不含ESEQ和SEQ结点
     - RULE-2. 每一个CALL的父亲不是EXP(…)，就是MOVE(TEMP t, …)
   - 利用重写规则转换为标准树的方法是：
     - 将ESEQ一级一级往上提
     - 将SEQ变成StmList
     - 利用ESEQ暂存CALL的结果，然后消除ESEQ
2. 通过C_basicBlocks将规范树分组组合成不含转移和标号的基本块（basic block）集合

   - 基本块是语句组成的一个序列，控制只能从这个序列的开始处进入并从结尾处退出，即
     - RULE-3. 第一个语句是一个LABEL
     - RULE-4. 最后一个语句是JUMP或者CJUMP
     - RULE-5. 没有其他的LABEL、JUMP或者CJUMP。
   - 之所以有基本块的设计，是因为在分析程序的控制流中，任何非转移指令的行为对分析都没有意义。因此，可以将由非分支指令组成的序列集中到一个基本块中，并分析这些基本块之间的控制流。将一长串语句序列划分成基本块的方法是：
     - 从头至尾扫描语句序列，每发现一个LABEL，就开始一个新的基本块（并结束前一个基本块）
     - 每发现一个JUMP或CJUMP就结束一个基本块（并开始下一个基本块）
     - 如果这个过程遗留有任何基本块不是以 JUMP或CJUMP结束的，则在这个基本块的末尾增加一条转移到下一个基本块标号处的 JUMP。如果下一个没有基本块，就跳转到exit基本块，即return -1。
     - 如果遗留有任何基本块不是以LABEL开始的，则生成一个新的标号并插入该基本块的开始
3. 通过C_traceSchedule对基本块排序并形成一组轨迹（trace）

   - 轨迹是在程序执行期间可能连贯执行的语句序列，可以包含条件分支，满足：
     - RULE-6. 每一个CJUMP之后都直接跟随它的false标号
   - 一个程序有许多不同的、重叠的轨迹。为了适当安排 CJUMP和 false 标号，我们需要建立一组正好能覆盖整个程序的轨迹，也就是每一个基本块在一条且只在一条轨迹中。为了使从一条轨迹到另一条轨迹的JUMP个数最少，覆盖集合中的轨迹越少越好。找出这种能覆盖整个程序的轨迹集合的方法是：
     - 从某个基本块开始（它是一个轨迹的开始），追寻一条可能执行的路径——即追寻该轨迹的其余部分。

## 4.2. Liveness Analysis (hw14)

Tiger编译器的流分析分两步进行：

1. 分析 Assem 程序的控制流（control flow analysis）并生成一个控制流图（flow graph）
   - 控制流图：程序中的每条语句都是流图中的一个结点。如果语句x之后跟随着语句y，则图中会有一条从x到y的边。变量的活跃性沿着控制流图的各条边"流动
   - 根据JUMP和CJUMP来确定前驱和后继，就可以生成一个控制流图
2. 在控制流图中分析变量的活跃性（data flow analysis）并生成冲突图（interference graph）
   - 活跃性：一个变量在一条边上是活跃的是指，存在一条从这条边通向该变量的一个 use 的有向路径，并且此路径不经过该变量的任何 def。活跃信息（入口活跃信息和出口活跃信息）可以用如下方式从 use 和def 求出：
     1. 如果一个变量属于use[n]，那么它在结点n是入口活跃的。也就是说，如果一条语句使用了一个变量，则该变量在这条语句入口是活跃的。
     2. 如果一个变量在结点 n是入口活跃的，那么它在所有属于 pred[n] 的结点 m 中都是出口活跃的。
     3. 如果一个变量在结点 n是出口活跃的，而且不属于def[n]，则该变量在结点n是入口活跃的。也就是说，如果变量a的值在语句n结束后还需使用，但是n并没有对a 赋值，则 a的值在进入n的入口时就是需要使用的。
   - 上述三点陈述可以写成关于变量集合的方程，然后用迭代方法求解。具体见虎书ch10
   - 冲突图：描述了程序中变量间的依赖关系，即变量之间的干扰情况。阻止将a和b分配到同一个寄存器的条件称为冲突。冲突图记录了变量之间的活跃性信息，包括哪些变量在同一时间被活跃，这些变量之间的依赖关系，以及它们是否可以被分配给同一个寄存器等信息。为每一个新定值添加冲突边的方法如下：
     1. 对于任何对变量 a定值的非传送指令，以及在该指令处是出口活跃的变量b1,…,bj，添加冲突边(a,b1),…,(a,bj)
     2. 对于传送指令a←c，如果变量b1,…,bj，在该指令处是出口活跃的，则对每一个不同于c的b添加冲突边(a,b1),…,(a,bj)
   - 在求出活跃信息后，就可以根据上述二点陈述建立冲突图

# 5. 例子

- 如 `2.1. 项目结构`中所述，在 `test`文件夹里有若干示例的FDMJ源文件。
- 如果想知道编译这些源文件的细节，首先通过 `2.2. 环境配置`准备好环境，然后通过 `2.3. 编译运行`输入命令，就会按照 `1.3. 编译流程`编译源文件并执行代码，中间过程会生成于对应的 `.ast`、`.irp`、`.stm`、`.liv`文件中，本报告由于篇幅限制就不将这些中间过程粘贴入，读者可以结合上述描述的细节很容易地理解这些中间过程的生成。