编译实验

文法解读

文法概述

课上使用语言是SysY，C语言的一个子集。
一个该语言源程序有且仅有一个名为main的主函数定义，此外有若干全局变量、常量声明和其他函数定义。支持32位有符号数int类型及其一维数组类型，const修饰符用于限定”常量”。
该语言并未提供输入/输出，I/O以运行时库方式提供，可以被调用。
部分库函数的参数类型会超出其支持的数据类型，如字符串。编译器需要能够处理此种情况并将参数进行正确的传递。

  • 函数：函数体由若干声明和语句组成。
  • 变量/常量声明：可以一次声明多个，可带初始化表达式，要求先定义再使用。
  • 语句：包括赋值语句、表达式语句、语句块、if语句、for语句、break语句、continue语句、return语句，其中语句块可以包含若干**变量声明和语句(递归属于是了)**。
  • 表达式：算术、关系和逻辑运算。优先级和结合性以及计算规则同C语言。

运行时库函数

getint函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
    int getint() {
        int t;
        scanf("%d",&t);
        while(getchar()!='\n');
        return t;
    }
```  
`printf`函数：`'printf''('<StringConst>{,<Exp>}')'`。  `<StringConst>`为字符串常量终结符，其解析超出该文法支持的数据类型情况下编译器需要能够处理这种情况。    
### 文法及测试程序覆盖要求
#### 覆盖要求
需覆盖文法中**所有语法规则**，并**满足文法语义约束(即程序需要是正确的)**。  
#### 文法
使用的是扩展的`Backus`范式:   
终结符是单引号括起来的串或者`Ident`、`IntConst`、`StringConst`这样的记号。   
**所有类似'main'这样用单引号括起来的字符串都是保留的关键字**。  
```c
    识别符号 CompUnit -> {Decl} {FuncDef} MainFuncDef

        量的声明 Decl -> ConstDecl |VarDecl

            常量声明 ConstDecl -> 'const' 'int' ConstDef {',' ConstDef}';' // 这里的{}是代表重复0-多次的意思

                常量定义 ConstDef -> Ident ['[' ConstExp ']' ] '=' ConstInitVal // 此处的[]代表重复0-1次的意思

                    标识符定义 Ident -> Ident-nondigit { Ident-nondigit | digit}   

                        非数字 Ident-nondigit -> '_' | ['A'-'Z'] | ['a' - 'z']

                        数字 digit -> [0 - 9]

                    常量表达式 ConstExp -> AddExp 此处使用的Ident必为常量

                    常量初值 ConstInitVal -> ConstExp | '{' [ ConstExp { ',' ConstExp } ] '}' // 常量表达式初值和一维数组初值

            变量声明 VarDecl -> ['static'] 'int' VarDef {',' VarDef } ';' 

                变量定义 VarDef -> Ident [ '[' ConstExp ']' ] | Ident [ '[' ConstExp ']' ] '=' InitVal

                    变量初值 InitVal -> Exp | '{' [ Exp { ',' Exp }] '}' 

                        表达式 Exp -> AddExp

                            加减表达式 AddExp -> MulExp { ('+' | '-') MulExp} 

                                乘除模表达式 MulExp -> UnaryExp {('*' | '/' | '%') UnaryExp}   

                                    一元表达式 UnaryExp -> PrimaryExp | Ident '(' [FuncRParams] ')' | UnaryOp UnaryExp 

                                        基本表达式 PrimaryExp -> '(' Exp ')' | LVal | Number

                                            左值表达式 LVal -> Ident ['[' Exp ']']

                                            数值 Number -> IntConst  

                                                整型常量 IntConst -> decimal-const | 0

                                                    十进制常量 decimal-const -> nonzero-digit {digit}

                                                        非0数字 nonzero-digit -> [1-9]

                                        函数实参表达式 FuncRParams -> Exp {',' Exp}

                                        单目运算符 UnaryOp -> '+' | '-' | '!'

        函数声明 FuncDef -> ('void' | 'int') Ident '(' [FuncFParams] ')' Block
            
            函数形参表 FuncFParams -> FuncFParam {, FuncFParam}  

                函数形参 FuncFParam -> 'int' Ident ['[' ']']

            语句块 Block -> '{' {    BlockItem } '}'
            
                语句块项 BlockItem -> Decl | Stmt 
                
                    语句 Stmt -> LVal '=' Exp ';' | [Exp] ; | Block | 'if' '(' Cond ')' Stmt [ 'else' Stmt ] | 'for' '(' [ForStmt] ';' [Cond] ';' [ForStmt] ')' Stmt | 'break' ';' | 'continue' ';' | 'return' [Exp] ';' | 'printf' '(' StringConst {',' Exp}')'';'   

                        条件表达式 Cond -> LOrExp
                            
                            逻辑或表达式 LOrExp -> LAndExp {'||' LAndExp}
                                
                                逻辑与表达式 LAndExp -> EqExp {'&&' EqExp}
                                   
                                    相等表达式 EqExp -> RelExp {('==' | '!=') RelExp}

                                        关系表达式 RelExp -> AddExp {('<' | '>' | '<=' | '>=') AddExp}  


                        for语句 ForStmt -> LVal '=' Exp {',' LVal '=' Exp}

                        字符串常量 StringConst -> '"' {Char}'"' 

                            字符 Char -> FormatChar | NormalChar

                                FormatChar -> %d

                                NormalChar -> 十进制编码为32、33、40-126的ASCII字符，'\'(编码92)出现时仅当为\n

        主函数声明 MainFuncDef -> 'int' 'main' '(' ')' Block

任务要求

  1. 对文法中每条规则定义的语法成分进行分析,编写4-6个能共同覆盖所有语法规则及常见组合情况测试程序,其中每个测试程序10条写语句.
  2. 需要提供每个测试程序的输入数据(有<读语句>则提供,否则提供空文件),输出数据,命名:testfilex,inputx.txt,outputx.txt.

编译器整体框架和词法分析

整体架构

分为前中后端：前端包括(词法分析器–token–>语法分析器–AST–>)、中端包括(语义分析器<–符号信息–符号表管理和–中间代码–>中间代码容器)、后端(存储管理–存储信息–>目标翻译器–目标代码(mips)–>)

词法分析

划分单词、提取类别、值等信息，处理注释和统计行号。
词法分析器主要数据成员：源程序字符串、当前字符串位置指针、解析单词值、解析单词类型、保留字表、当前行号和解析数值(number)。
主要功能如下：
alt text

语法分析

将词法分析得到的线性结构转化为能表示结构层次的树形结构(也就是语法树)，便于中间代码的生成。

AST抽象语法树

表示方法

由于文法反映了不同结构间组成关系，而关于组成，可以将整体以类的形式、子部分由相应属性来定义。
对于有多个生成式的文法规则，可以采用引入一个type来标识对应第几个生成规则进而区分不同形式。后续语义分析、代码生成等可以通过其来判断类型，当然也可以使用创建子类的方式。
可以统一创建一个语法树节点基类Node，在其中定义了例如output等共同具有的属性，方便评测。
对原本语法树进行化简，去掉冗余结构的为抽象语法树，例如：

1
2
3
FuncDef → FuncType Ident '(' [ FuncFParams ] ')' Block

FuncFParams → FuncFParam { ',' FuncFParam }

对于如上文法，没必要多定义一个FuncFParams，可以直接以FuncFParam { ',' FuncFParam }作为FuncDef的组成部分。

节点设计

保证：语法树子树表示程序模块，语法树深度反映求值顺序。

语法分析

采用LL分析法进行自顶向下的推导方法，其中较为简单非递归下降子程序法莫属。
为了便于进行语法分析，我通过巴科斯范式将文法修改为非左递归式的，并设置相应的回溯机制(使用一个回溯点)来方便预读处理。

期中试题

题目

改写文法：

1
2
3
识别符号 CompUnit -> {Decl} {FuncDef | FuncStmt} MainFuncDef
        函数声明 FuncStmt -> ('void' | 'int') Ident '(' [FuncFParams] ')';
        语句 Stmt -> LVal '=' Exp ';' | [Exp] ; | Block | 'if' '(' Cond ')' Stmt {'elif' '(' Cond ')' Stmt } [ 'else' Stmt ] | 'for' '(' [ForStmt] ';' [Cond] ';' [ForStmt] ')' Stmt | 'break' ';' | 'continue' ';' | 'return' [Exp] ';' | 'printf' '(' StringConst {',' Exp}')'';'

elif<->ELIFTK,其他文法并未发生改变,此处不赘述。

结果

testcase7RE，经水群里讨论可知，应该是处理单行注释时并没有考虑到是最后一行的情况，即此时不能以不等于\n来判断，因为此后不一定有\n，还需要判断是否到达了文件末尾!!!!
alt text
注意:一定要判断越界问题，while一定要判断越界的情况。
一定注意越界问题，加强测试，不可自以为是，一定注意越界问题!

语义分析

核心目标遍历语法树、维护符号表并最终生成中间代码。
将符号信息尽可能充分地存储到中间代码中，从而使得在目标代码翻译时不用考虑符号管理，只需要考虑目标存储架构。
维护设计文档

遍历语法树

两种遍历方法：

  1. 每个节点设置一个visit方法，递归调用子节点的visit方法，完成对整棵树的遍历。信息只能作为参数和返回值，沿着节点遍历顺序传递。遍历时注意错误处理以及符号表的切换以及新建等操作。
  2. 使用访问者模式，定义一个访问者类Visitor，其中包含对不同节点类型的处理方法，然后在语法树节点中实现一个accept方法，即为每种节点类型提供专门的访问方法，共享类作用域。这样信息不仅能沿着遍历顺序传递，还能跨越语法树传递到任何地方，不用经过层级调用。
    整个AST遍历体系由多个Visitor类构成，分工处理不同类型的节点。Visitor.java作为入口，负责遍历编译单元（CompUnit）的所有子节点（声明、函数定义、主函数）。

维护符号表

记录各个符号标识和相应信息，包括作用域、类型、大小、维度和存储地址等。
进行符号表插入时，需要在当前作用域符号表中是否发生重定义错误，有则返回错误，否则正确插入。
符号表查询，先在当前作用域符号表中查询，若无则利用当前作用域符号表的pre指针访问外层作用域符号表，同理进行查询操作。
可以采用树状符号表或者栈式符号表来实现。

作用域管理

注意作用域不同，即父子符号表的切换，例如：函数定义处理过程中，函数形参已属于函数内的作用域，因此解析之前就应进入相应的作用域，分析完后退出相应作用域

符号的构建与类型系统

符号表中每个符号不仅应记录语法信息(变量名、类型等)，还应关联对应的IR对象(如变量的分配指令、函数的IR函数对象)。如，解析变量定义时，会创建IR的AllocateInstr(内存分配指令)，将其绑定到符号中(动作符号？)：

1
2
3
4
5
AllocateInstr allocateInstr = new AllocateInstr(GetSymbolIrType(symbol));
symbol.SetIrValue(allocateInstr); // 符号关联IR地址

IrFunction irFunction = IrBuilder.GetNewFunctionIr(funcName, irType);
funcSymbol.SetIrValue(irFunction); // 函数符号关联IR函数

此外，AST中各个成员的类型和中间代码中各个成员的类型是不同的。在代码中，需要通过SymbolType（AST 层面的类型）与IrType（IR 层面的类型）的映射，实现类型一致性检查与转换。例如：

1
2
3
4
5
6
7
8
private static IrType GetSymbolIrType(ValueSymbol symbol) {
    return switch (symbol.GetSymbolType()) {
        case CHAR, CONST_CHAR -> IrBaseType.INT8; // char映射为IR的int8
        case INT, CONST_INT -> IrBaseType.INT32; // int映射为IR的int32
        case CHAR_ARRAY -> new IrArrayType(depth, IrBaseType.INT8); // 字符数组
        // ... 其他类型
    };
}

由于类型的嵌套关系，可以考虑定义所有类型的公共父类 Type。所有其他类型类继承自该类。对于不同基本类型，可以考虑将其设计为单例。对于数组和指针，则需在其字段中包含元素类型和引用类型。（另外数组还需额外设定数组长度。）

构建中间代码

表达式生成

将表达式节点设定为单目或双目运算。则我们只需先分别访问左子树和右子树，就可以得到三地址码中的两个地址。而第三个地址，则是当前节点中创建的新的指令。我们将这第三个地址返回，便实现了这一递归的过程。

1
2
3
4
5
6
7
8
9
10
11
public static IrValue VisitAddExp(AddExp addExp) {
    // 先遍历单独暴露的MulExp
    IrValue irValue1 = VisitMulExp((MulExp) nodeList.get(0));
    // 遍历后续可能存在的"+"或"-"运算
    for (int i = 1; i < nodeList.size(); i += 2) {
        TokenNode op = (TokenNode) nodeList.get(i); // 运算符
        IrValue irValue2 = VisitMulExp((MulExp) nodeList.get(i+1)); // MulExp
        irValue1 = new AluInstr(op.GetSimpleName(), irValue1, irValue2); // 生成指令
    }
    return irValue1;
}

控制流语句

if、for的中间代码生成依赖于基本块和跳转指令。
if核心逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// 解析条件，生成分支指令
VisitorExp.VisitCond(cond, ifBlock, elseBlock);
// 处理if块
IrBuilder.SetCurrentBasicBlock(ifBlock);
VisitStmt(ifStmt); // 执行if体内语句
JumpInstr jumpToFollow = new JumpInstr(followBlock); // 跳转到合并块
// 处理else块（若有）
IrBuilder.SetCurrentBasicBlock(elseBlock);
VisitStmt(elseStmt);
JumpInstr jumpToFollow2 = new JumpInstr(followBlock);
// 合并块
IrBuilder.SetCurrentBasicBlock(followBlock);
```  
`for`循环实现：循环变量初始化，这个应该在外面的块进行，接下来是，条件判断块（condBlock）；然后进入循环体块（bodyBlock），接下来是步进块（stepBlock，更新循环变量）；最后循环结束。
同时，通过IrBuilder.LoopStack管理循环上下文，支持break（跳转到followBlock）和continue（跳转到stepBlock）。
#### 左值与访存操作
"左值"为可被赋值的对象，具有内存地址的值。
代码中`VisitorLVal`专门处理左值的地址计算与取值：

`VisitLValForAssign`：返回左值的内存地址（用于赋值，生成`StoreInstr`）；

`VisitLValForValue`：返回左值的内容（用于取值，生成`LoadInstr`）。
例如，数组元素的赋值：
```java
IrValue pointer = symbol.GetIrValue(); // 数组首地址
// 计算偏移（如a[2]的地址 = 首地址 + 2 * 元素大小）
IrValue gepInstr = new GepInstr(pointer, VisitorExp.VisitExp(expList.get(0)));
return gepInstr; // 返回元素地址，供StoreInstr使用
```   
#### 函数调用与参数传递
函数调用的中间代码生成涉及实参计算、函数符号查找和调用指令的创建：
1. 计算实参表达式的 IR 值（VisitorExp.VisitExp）；
2. 查找函数符号对应的 IR 函数对象（FuncSymbol.GetIrValue）；
3. 生成CallInstr指令

### 错误处理
只需考虑以下错误：
#### 名字重定义
函数名或变量名在**当前作用域**下重复定义，不同级作用域下，内层覆盖外层定义，这个在向当前符号表插入符号时注意特判是否出错。报错行号为`Ident`所在行号。    
#### 未定义的名字
使用了未定义的标识符，在遍历到对`Ident`标识符进行引用时查询包括直系外层符号表及当前符号表未果后进行处理。报错行号为`Ident`所在行号。    
#### 函数参数个数不匹配
函数调用语句中，参数个数与函数定义中参数个数不匹配，报错行号为函数调用语句中函数名所在行号。     
需要在实际调用函数时进行考虑。    
#### 函数参数类型不匹配
函数调用语句中，参数类型与函数定义中对应位置参数类型不匹配，报错行号为函数调用语句中函数名所在行号。具体指，传递数组给变量，传递变量给数组。        
#### 无返回值函数存在不匹配的return语句
也就是无返回值的函数不能返回值，需要在函数体结束时判断return后有无返回值。报错行号为return所在语句。      
#### 有返回值函数缺少return语句
考虑函数末尾是否存在return语句，**无需考虑控制流**，报错行号为函数结尾的`}`行号
#### 不能改变常量值
对于常量左值，不能对其进行修改，报错行号为左值所在行号。    
#### printf中格式字符与表达式个数不匹
报错行号为`printf`所在行号，在解析`printf`时需要注意统计`%d`的个数。
#### 在非循环块中使用`break`和`continue`
通过判断使用这两个语句时是否在for循环中来进行爆错处理。    

#### 语义部分可能的错误和注意点
1. 保证所有测试程序中有返回值的函数 Block 的最后一句一定会显式的给出 return 语句， 否则就当作“无返回语句”的错误处理，同时需要注意**int函数的函数体block里面没有blockitem的情况**。     
2.  对于一个名字重定义的函数，也**应该完整分析函数内部是否具有其它错误**。    
3.  所有测试程序中，实参被判定为数组当且仅当它是一个单独的数组Ident标识符且为数组标识符，不包含指针运算。因此可以基于此判断是否是数组类型。
4. 对于f类错误，注意不能只遍历函数block中的return语句，因为函数的block语句中还可能有block语句，要递归判断
5. 对于 【g 类错误】，即【有返回值的函数缺少return语句】的错误，只需要考虑函数体 最后一条语句，且只需判断有没有 return 语句，不需要考虑 return 语句是否有返回值，也不需要检查函数体内其他的 return 语句是否有值，一个有返回值的函数最多只会有一个 g 类错误，不会有 f 类错误, **【f 类错误】需要检查 void 类型函数体内 每一条 return 语句都没有值，遇到有值的 return 语句就报 f 类错误，有多少个就报出多少个**。
6. 函数参数个数不匹配优先于类型不匹配，即同时遇到参数个数不匹配和类型不匹配问题，应该先输后为个数不匹配问题。   
7. `getint`函数的调用以及参数不匹配错误：
    ```c
    int main() {
        int a, b, c;

        getint();
        getint(a);  // 5 d
        getint(a, b); // 6 d
        getint(a, b, c); // 7 d

        return 0;
    }
error.txt：


1
2
3
5 d
6 d
7 d
  1. getint不应触发c类错误，因此需要进行特判
  2. 换句话说，同学们可以默认getint在最开始的时候就已经存在于符号表中，并为其标记类型等。或者直接自定义类型GETINTTK的类型，因为其相关的检查是在词法和语法分析中的。
  3. 注意进出for循环层的统计
  4. 有关 h 类错误：ForStmt 中需要考虑左值修改是常量的问题，且可能有多个左值修改
  5. 有关 b 类错误：函数形参列表中的变量和函数体内定义的重名变量也会发生重定义问题
  6. 数组类变量在定义的时候，如果发生 k 类错误，仍需要正常记录为数组类型，否则在函数调用时可能出现额外的 e 类报错
  7. ConstExp 在编译期内是可被求值的，ConstExp -> AddExp 中涉及到的的 ident 均必须是常量，即只能使用常数、可以取得具体值的常量以及由它们组成的、在编译器内可被求值的算术表达式。因此，需要设置相应的计算函数在编译阶段就将相应的常量值计算出来!

中间代码生成

以LLVM IR为例的数据结构

文法涉及的LLVM IR语法结构

  1. 函数块define dso_local i32 @add(i32 %0, i32 %1) {}
  2. 指令集：具体参照网页
  3. 局部变量/字面量，设计了对应的value类存储上下文信息

架构设计

按粒度高至低为:

  1. 整个模块 Module
  2. 函数 Function
  3. 基本代码块 BasicBlock（以label和跳转语句为界限）
  4. 指令 Instruction
  5. 变量/常量 && 符号
  6. 变量：参数、局部变量；常量：字面量
    alt text
    对于模块中不同粒度的所有语法结构，都视为Value的子类，其中，User是一个特殊的、可使用其他Value对象的类。Function、BasicBlock 和 Instruction 都有使用的语法结构，都是 User 的子类，也是 Value 的子类。
    User与Value之间的配对用Use类记录，通过Use建立起语法结构上下级关系双向索引，使所有语法结构统一成Value类，之间关系可都统一成Use类。
    例子：
    1
    2
    3
    A: %add = add nsw i32 %a, %b
    B: %add1 = add nsw i32 %a, %b
    C: %add2 = add nsw i32 %add, %add1
    其中A语句是一个指令，继承自User，而User引用了a和b两个Value，又被C语句引用。
    因此设计Value如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
        public abstract class Value {
        protected Type type;  // 值类型
        protected String name; // 名字
        
        protected List<Use> useList; // 使用关系索引列表
        protected List<Use> userList;
        
        private ValueType valueType; // 语法类型
        
        // 构造函数和其他方法...
    }

    // 语法类型，不同语法结构通过该枚举值区分
    public enum ValueType {
        // Value
        ARGUMENT,        // 参数
        BASIC_BLOCK,     // 基本块

        // Value -> Constant
        CONSTANT,        // 常量标识符
        CONSTANT_DATA,   // 字面量

        // Value -> Constant -> GlobalValue
        FUNCTION,
        GLOBAL_VARIABLE,

        // Value -> User -> Instruction
        BINARY_OPERATOR,
        COMPARE_INST,
        BRANCH_INST,
        RETURN_INST,
        STORE_INST,
        CALL_INST,
        INPUT_INST,
        OUTPUT_INST,
        ALLOCA_INST,
        LOAD_INST,
        UNARY_OPERATOR,
    }

    // 值类型，记录的是返回值类型，与上者不同，记录的是llvm本省语法结构中的数据结构，可以理解为一个指令的返回值类型
    /*
    比如对于指令对象 %add = add i32 %a, %b，返回值类型 Type 为 %add 的类型 i32，指令类型 ValueType 为二元操作数指令类型 BINARY_OPERATOR
    */
    public enum TypeID {
        // Primitive types
        VOID,       // 空返回值
        LABEL,      // 标签类型

        // Derived types
        INTEGER,    // 整数类型
        FLOAT,      // 浮点数类型
        FUNCTION,   // 函数类型
        POINTER,    // 指针类型
    }

    // 索引Use和User
    /*
        前者记录指令和操作数关系，针对每一条指令，将操作数作为Usee，指令作为User，创建Use对象，同时保存在全局记录和User对象的uselist属性中
        指令和每个操作数之间都是Use关系，
    */
    // llvmContext记录全局的Use关系，每个编译单元Module中一个llvmContext，用于存储对象的引用，记录对象间索引关系为之后的代码优化提供便利，便于查找到某个变量的所有使用位置，方便进行变量替换、活跃变量分析和公共子表达式删除
    public class LlvmContext {
        private List<FunctionType> functionTypes;
        private List<PointerType> pointerTypes;
        
        private List<Value> values;
        private List<Use> uses;
    }
    // Value中记录的名称，只在全局变量中有意义，局部变量的无意义，因为翻译后要用数字对虚拟寄存器重命名——按出现顺序进行编号
    /*
        Value 对象中通过 Use 保存域内各个成员结构的引用索引，成员间的使用关系中无需语法对象名称信息，即整个翻译过程与对象名称无关，与虚拟寄存器编号也无关。因此，分配虚拟寄存器编号不用在翻译过程中实现，可以推迟到代码打印的部分。
    */
    // 使用SlotTracker 类作为一个工具类，在中间代码打印时为一个函数域分配虚拟寄存器，记录各语句对应的虚拟寄存器编号。
    public class SlotTracker {
        private Map<Value, Integer> slot;
        
        public void traceMethod(MethodDefinition method) {
            // 为方法中的变量分配寄存器编号
        }
        
        public void traceClass(ClassDefinition classDef) {
            // 为类中的字段分配寄存器编号
        }
    }
    llvm模块文件结构说明：

LLVM

底层虚拟机，提供一种现代、基于SSA(静态单一赋值)的编译策略，能支持任意编程语言的静态和动态编译。
采用三端设计，前后端和优化器，其中前端解析源代码，检查错误，构建AST，AST进一步转化为新的目标码优化，最终由后端生成具体二进制可执行文件。优化器提高代码运行效率，如消除冗余计算等。后端负责将代码映射到目标指令集，其常见的功能包括指令选择、寄存器分配和指令调度。

速上手

平常使用中，LLVM一般指LLVM IR，中间代码，使用Clang来生产该中间代码，因为其不能单独存在。
基本命令：
一般有三种表示形式，1.代码中的数据结构；2.作为输出的二进制位码格式.bc和文本格式.ll，实验中要求能够输出正确的.ll文件

1
2
3
4
5
6
7
8
9
clang -ccc-print-phases main.c               # 查看编译的过程
clang -E -Xclang -dump-tokens main.c         # 生成 tokens（词法分析）
clang -fsyntax-only -Xclang -ast-dump main.c # 生成抽象语法树
clang -S -emit-llvm main.c -o main.ll -O0    # 生成 LLVM ir (不开优化)
clang -S -emit-llvm main.m -o main.ll -Os    # 生成 LLVM ir (中端优化)
clang -S main.c -o main.s                    # 生成汇编
clang -S main.bc -o main.s -Os               # 生成汇编（后端优化）
clang -c main.c -o main.o                    # 生成目标文件
clang main.c -o main                         # 直接生成可执行文件

一个实例：

1
2
3
4
5
6
7
8
9
10
int a = 1;

int add(int x, int y) {
    return x + y;
}

int main() {
    int b = 2;
    return add(a, b);
}

使用clang -S -emit-llvm main.c -o main.ll命令后同目录下生成一个main.ll文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
; ModuleID指明该模块的标识
; ModuleID = 'main.c' 
; 在LLVM IR中以;开头作为注释
; 源文件表示模块从什么文件编译而来，若是通过链接则显式`llvm-link`
source_filename = "main.c"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"
; 这两个target的标签为程序标签属性说明，和硬件/系统有关
; 全局变量，名为a，类型为i32，初始值为1，对齐为4bytes，dso_local 表明该变量会在同一个链接单元（llvm-link 命令的源文件范围）内解析符号。
@a = dso_local global i32 1, align 4

; Function Attrs: noinline nounwind optnone uwtable
; 函数定义，第一个i32为返回值类型，@add为函数名，接着为形参类型和形参名(如:%1)
; 这里的标识符分为两种，全局和局部，前者含函数名和全局变量，加@前缀；后者加%前缀
; #0 指出了函数的 attribute group。由于每个函数的 attribute 很多，而且不同函数的 attributes 往往相同，因此将相同的 attributes 合并为一个 attribute group，从而使 IR 更加简洁清晰，并在后续统一标明
; 花括号中为函数体，由一系列BasicBlock组成，每个 BasicBlock 都有一个 label，label 使得该 BasicBlock 有一个符号表的入口点。BasicBlock 以 terminator instruction（ret、br 等）结尾。每个 BasicBlock 由一系列 Instruction 组成，Instruction 是 LLVM IR 的基本指令。
;   %7 = add nsw i32 %5, %6：随便拿上面一条指令来说，%7 是一个临时寄存器，是 Instruction 的实例，它的操作数里面有两个值，一个是 %5，一个是 %6。%5 和 %6 也是临时寄存器，即前两条 Instruction 的实例，其中nsw是No Signed Wrap的缩写，即假设了运算结果不会发生有符号溢出，实际发生了运算结果未定义，其主要是为了给编译器提供优化依据，其会做出这段有符号加法运算结果一定在目标类型的取值范围内，不发溢出，进而采用更激进的优化。
; 同理对于无符号整数的溢出约束有nuw，都是提供优化依据的。
define dso_local i32 @add(i32 noundef %0, i32 noundef %1) #0 {
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  store i32 %0, ptr %3, align 4
  store i32 %1, ptr %4, align 4
  %5 = load i32, ptr %3, align 4
  %6 = load i32, ptr %4, align 4
  %7 = add nsw i32 %5, %6
  ret i32 %7
}

; Function Attrs: noinline nounwind optnone uwtable
define dso_local i32 @main() #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  store i32 0, ptr %1, align 4
  store i32 2, ptr %2, align 4
  %3 = load i32, ptr @a, align 4
  %4 = load i32, ptr %2, align 4
  %5 = call i32 @add(i32 noundef %3, i32 noundef %4)
  ret i32 %5
}

attributes #0 = { noinline nounwind optnone uwtable "frame-pointer"="all" "min-legal-vector-width"="0" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cmov,+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "tune-cpu"="generic" }

!llvm.module.flags = !{!0, !1, !2, !3, !4}
!llvm.ident = !{!5}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{i32 8, !"PIC Level", i32 2}
!2 = !{i32 7, !"PIE Level", i32 2}
!3 = !{i32 7, !"uwtable", i32 2}
!4 = !{i32 7, !"frame-pointer", i32 2}
!5 = !{!"Ubuntu clang version 18.1.3 (1ubuntu1)"}
```    
此后使用`lli main.ll`将解释执行该文件，若一切正常，则输入`echo $?`将返回上一条指令的返回值，也就是`main.c`中的`main`函数的返回值       
#### 常用指令：      
| LLVM IR       | 使用方法                                                      | 简介                                             |
|---------------|---------------------------------------------------------------|--------------------------------------------------|
| add           | \<result\> = add \<type> \<op1>, \<op2>                              | /                                                |
| sub           | \<result> = sub \<type> \<op1>, \<op2>                              | /                                                |
| mul           | \<result> = mul \<type> \<op1>, \<op2>                              | /                                                |
| sdiv          | \<result> = sdiv \<type> \<op1>, \<op2>                             | 有符号除法                                       |
| srem          | \<result> = srem \<type> \<op1>, \<op2>                           | 有符号取余                                       |
| icmp          | \<result> = icmp \<cond> \<type> \<op1>, \<op2>                      | 比较指令                                         |
| and           | \<result> = and \<type> \<op1>, \<op2>                              | 按位与                                           |
| or            | \<result> = or \<type> \<op1>, \<op2>                               | 按位或                                           |
| call          | \<result> = call [ret attrs] \<type> \<name>(\<...args>)            | 函数调用                                         |
| alloca        | \<result> = alloca \<type>                                      | 分配内存                                         |
| load          | \<result> = load \<type>, ptr \<pointer>                           | 读取内存                                         |
| store         | store \<type> \<value>, ptr \<pointer>                             | 写内存                                           |
| getelementptr | \<result> = getelementptr \<type>, ptr \<ptrval>{, \<type> \<idx>}*    | 计算目标元素的位置（数组部分会单独详细说明）     |
| phi           | \<result> = phi [fast-math-flags] \<type> [\<val0>, \<label0>], ... | /                                                |
| zext..to      | \<result> = zext \<type> \<value> to \<type2>                         | 将 type 的 value 的 type 扩充为 type2（zero extend） |
| trunc..to     | \<result> = trunc \<type> \<value> to \<type2>                        | 将 type 的 value 的 type 缩减为 type2（truncate）    |
| br            | br i1 \<cond>, label \<iftrue>, label \<iffalse> br label \<dest> | 改变控制流                                       |
| ret           | ret \<type> \<value> , ret void                                 | 退出当前函数，并返回值                           |
#### LLVM IR构建单元
在LLVM IR中一个`.ll`对应一个模块：![alt text](image-85.png)        
可见，`LLVM IR`中所有类都直接或间接继承自`Value`，则可以通过继承关系得到其类型系统。       
此外，为了表达 Value 之间的引用关系，LLVM IR 中还有一种特殊的 Value 叫做 User，其将其他 Value 作为参数。例如，对于下面的代码：
```LLVM IR
A: %add1 = add nsw i32 %a, %b
; A是一条指令，是一个 BinaryOperator，它在代码中的体现就是 %add1，即指令的返回值，也称作一个虚拟寄存器。Instruction 继承自 User，因此它可以将其他 Value（%a 和 %b）作为参数。因此，在 %add1 与 %a、%b 之间分别构成了 Use 关系。紧接着，%add1 又和 %add2 一起作为 %sum 的参数，从而形成了一条 Use 链。
B: %add2 = add nsw i32 %a, %b
C: %sum  = add nsw i32 %add1, %add2

这种指令间的关系是和LLVM IR核心，这样方便进行分析和优化，例如：易知，%add1 和 %add2 实际上是同一个值，因此可以进行替换。同时，如果一个 Value 没有 Use 关系，那么它很可能就是可以删除的冗余代码。
此部分即是根据AST，构建出LLVM IR(或四元式)。
易见，clang 生成的 LLVM IR 中，虚拟寄存器是按数字命名的。LLVM IR 限制了一个函数内所有数字命名的虚拟寄存器必须严格从 0 开始递增。其实，这些数字就是每个（对应了虚拟寄存器的） Value 在 Function 内的顺序，实现起来并没有想象中那么复杂，可以参考 LLVM IR 中的 SlotTracker 类。如果不想严格按照数字命名，那么就需要使用非数字的字符串命名，两种方式不能混用。

不同语法结构的LLVM生成要点

主函数与常量表达式
主函数
  1. 遍历AST，遍历到函数时获取函数名和返回值类型。
  2. 遍历到BlockItem内的Stmt时，若为return语句，生成对应的ret指令。
常量表达式

由于此处只是常数的四则运算，例如：对于1+2+3*4，采用最左推导的生成顺序，先生成 1，然后生成 2，然后生成 1 + 2，然后生成 3，然后生成 4，然后生成 3 * 4，最后生成 1 + 2 + 3 * 4。
而对于数字前的正负，可以看作是0和其做一次加减运算，此处可作为特殊的AddExp处理。

全局变量和局部变量
全局变量

同样使用和函数一样的前缀@，因此写法几乎同函数定义一致。
实践可知对于static的处理需要像全局变量一样先在开头进行声明，也就是将其当作某个函数内的全局变量来实现，形如：@add.a = internal global i32 2, align 4，这就表示了在函数add中定义了一个static int a = 2;，使用同全局变量，先用load到一个虚拟寄存器中，因为提供的@...是地址，再通过该寄存器完成相应的计算，具体看如下代码的中间代码的生成。
由于这两者如果被赋初值，均可在编译阶段完成，或者未被赋初值则直接初始化为0，因此在生成的 LLVM IR 中需要直接算出其具体的值，同时，也需要完成必要的类型转换。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>
extern int getint();
extern int getchar();
int a = 1;

int add(int x, int y) {
    static int a = 2;
    return x + y + a;
}
int main() {
    static int b;
    return -3 + 9 * 66 / 99 % 17 + a - b;
}
/*
中间代码
...
@a = dso_local global i32 1, align 4
@add.a = internal global i32 2, align 4
@main.b = internal global i32 0, align 4

; Function Attrs: noinline nounwind optnone uwtable
define dso_local i32 @add(i32 noundef %0, i32 noundef %1) #0 {
  %3 = alloca i32, align 4
  %4 = alloca i32, align 4
  store i32 %0, ptr %3, align 4
  store i32 %1, ptr %4, align 4
  %5 = load i32, ptr %3, align 4
  %6 = load i32, ptr %4, align 4
  %7 = add nsw i32 %5, %6
  %8 = load i32, ptr @add.a, align 4
  %9 = add nsw i32 %7, %8
  ret i32 %9
}

; Function Attrs: noinline nounwind optnone uwtable
define dso_local i32 @main() #0 {
  %1 = alloca i32, align 4
  store i32 0, ptr %1, align 4
  %2 = load i32, ptr @a, align 4
  %3 = add nsw i32 3, %2
  %4 = load i32, ptr @main.b, align 4
  %5 = sub nsw i32 %3, %4
  ret i32 %5
}
...
*/
局部变量与作用域

使用%，不同于全局变量，局部变量在赋值前需要通过alloca申请一块内存。在对局部变量操作的时候也需要采用 load/store 来对内存进行操作。
例如：

1
2
3
4
5
6
7
8
9
10
11
// 以下都是局部变量
int a = 1 + 2;

/*
%1 = alloca i32
%2 = add i32 1, 2
store i32 %2, i32* %1

 注意此处教程对于store的使用方式是：store \<type> \<value>, ptr \<pointer>
 这里的ptr是无类型指针 / 不透明指针，Opaque Pointer，对于LLVM>=15的情况写，可以都统一写成ptr来简化中间代码的生成，但是实验使用的是llvm=12，因此不支持该无类型指针，因此还是显式使用对应指针为好
*/
符号表设计

由于在不同的作用域或者Name Space下，变量名可以相同，因此，需要设计好符号表来达到，对于某个变量准确锁定到其所有相关的属性上来。举例来看：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int a = 1;
int b = 3;

int main() {
    int c = b + 4;
    return a + b + c;
}

/**
@a = dso_local global i32 1
@b = dso_local global i32 3

define dso_local i32 @main() {
    %1 = alloca i32          ; 分配 c
    %2 = load i32, i32* @b   ; 加载 b 到内存
    %3 = add nsw i32 %2, 4   ; b + 4
    store i32 %3, i32* %1    ; c = b + 4
    %4 = load i32, i32* @a   ; 加载 a 到内存
    %5 = load i32, i32* @b   ; 加载 b 到内存
    %6 = add nsw i32 %4, %5  ; a + b
    %7 = load i32, i32* %1   ; 加载 c 到内存
    %8 = add nsw i32 %6, %7  ; a + b + c
    ret i32 %8               ; 返回 a + b + c
}
*/

此处具体实现是在第一次遇见变量声明时，将标识符与对应的 LLVM IR 中的 Value实例 添加到符号表中，那么之后再次遇到标识符时就可以获得最初的声明，找不到的话说明出现了使用未定义变量的错误。

虚拟寄存器的数字并不是符号表的一部分，它们只是输出时的标记。
因此，只需要在输出 LLVM IR 时，遍历一遍 Function 内的所有 Value，对其标号即可。
同时还需要注意作用域下的覆盖问题，其实也就是从本层作用域开始向外找相应的变量名只要一找到即拿来做操作数即可。

函数定义及调用
库函数

对于库函数的添加，需要在中间代码的开头声明，对于使用到这些库函数的代码，编译时均需用llvm-link进行链接。 

1
2
3
4
5
declare i32 @getint()
declare i32 @getchar()
declare void @putint(i32)
declare void @putch(i32)
declare void @putstr(i8*)

此处对于库函数的使用其实只涉及到了getint和printf，其中后者还涉及到了有无Exp的情况，此处举例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int main() {
    int a;
    a = getint();
    printf("Hello: %d", a);
    return 0;
}

/**
// LLVM代码如下
declare i32 @getint()
declare void @putint(i32)
declare void @putstr(i8*)


@.str = private unnamed_addr constant [8 x i8] c"Hello: \00", align 1

define dso_local i32 @main() {
    %1 = alloca i32
    %2 = call i32 @getint()
    store i32 %2, i32* %1
    %3 = load i32, i32* %1
    call void @putstr(i8* getelementptr inbounds ([8 x i8], [8 x i8]* @.str, i64 0, i64 0))
    call void @putint(i32 %3)
    ret i32 0
}
*/

可以看得出来，call i32 @getint()调用了getint，其他同理。
对于printf的处理较为特殊，将其转化为读条语句，比较方便后续向mips的转化，即将格式字符串与变量值分别输出，对前者直接调用putstr，可直接转化为MIPS的4号系统调用，不过这需要配合全局的字符串常量：@.str = private unnamed_addr constant [8 x i8] c"Hello: \00", align 1，可通过硬编码的方式实现，其中注意llvm对于\n和\0需要进行转义，实际硬编码为\0A和\00。

函数定义与调用

对于一个一般函数，其特征包括函数名、函数返回值类型给和参数。
FuncFParams 之后的 Block 则与之前主函数内处理方法一样。值得一提的是，由于每个临时寄存器和基本块占用一个编号，所以没有参数的函数的第一个临时寄存器的编号应该从 1 开始，因为函数体入口基本块占用了一个编号 0。而有参数的函数，参数编号从 0 开始，进入 Block 后需要跳过一个基本块入口的编号。

如果存在用编号的命名寄存器，则命名规则要与系统默认的编号分配规则相同；如果全部采用字符串编号寄存器，上述问题都不会存在。
针对上述问题，如果函数入口基本块已经由字符串命名，则编号0按顺序分配给后续寄存器。
推荐使用字符串命名寄存器。
其实函数调用和全局变量一致，对于有参数的函数调用，则在调用的函数内传入参数。对于没有返回值的函数，则直接 call 即可，不用为语句赋一个实例。

条件语句与短路求值
条件语句

若使用数字进行虚拟寄存器编号，则跳转后的基本块的数字并未得知，回填在优化时不切实际，但是由于这个只涉及到输出，因此只需要在输出前变量函数中的所有Value进行编号即可。 

1
Stmt    → 'if' '(' Cond ')' Stmt1 [ 'else' Stmt2 ] BasicBlock3

注意此处Cond中的代码，即 LOr 和 LAnd，Eq 和 Rel。不难发现，其处理方式和加减乘除非常像，除了运算结果都是 1 位（i1）而非 32 位（i32）。可能需要用到 trunc 或者 zext 指令进行类型转换。

短路求值

由于短路求值的存在，LLVM IR 不能够单纯的把 Cond 计算完后再进行跳转。这时候就需要对 Cond 的跳转逻辑进行改写。需要在判断出来LOrExp为真或者LAndExp为假时直接中止生成，此处提供一下实现思路：
对于条件（对应非终结符 Cond）的解析，主要涉及三个基本块：条件为真跳转的目标块，条件为假跳转的目标块，以及条件的运算所属的基本块(对if来说，可为当前基本块，而不用新建一个基本块来专门放置)。这三个块根据表达式的不同（如 if，for）而有一些区别，但是都符合这一模式。那么在解析前，我们应该准备好这三个基本块，但暂时不将其插入函数中。
接下来，将这三个块作为节点属性解析，以下(其他的类似)主要涉及 Cond，OrExp，AndExp，和 EqExp（作为条件对应的 Value）。下图为 if (a || b && c || d) 中 Cond 的解析过程，解析时进行先序遍历。
alt text
对于其中的每个节点，左上角代表条件真要跳转的基本块，右上角为假要跳转到的基本块，左下角为将要生成的条件所在基本块，右下角为当前节点新创建的基本块。↓ 表示该基本块由父节点传递下来，↑ 表示进入时即将该基本块插入函数，并作为当前基本块，即之后生成的指令（条件计算）会添加到该基本块中。对于任意的继承属性，其由父节点压栈，由子节点弹栈；对于综合属性，则正好相反。
样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
int a = 1;
int func() {
    a = 2;
    return 1;
}

int func2() {
    a = 4;
    return 10;
}
int func3() {
    a = 3;
    return 0;
}
int main() {
    if (0 || func() && func3() || func2()) {
        printf("%d--1", a);
    }
    if (1 || func3()) {
        printf("%d--2", a);
    }
    if (0 || func3() || func() < func2()) {
        printf("%d--3", a);
    }
    return 0;
}
/***
//中间代码如下
declare i32 @getint()
declare i32 @getchar()
declare void @putint(i32)
declare void @putch(i32)
declare void @putstr(i8*)

@a = dso_local global i32 1

@.str = private unnamed_addr constant [4 x i8] c"--1\00", align 1
@.str.1 = private unnamed_addr constant [4 x i8] c"--2\00", align 1
@.str.2 = private unnamed_addr constant [4 x i8] c"--3\00", align 1

define dso_local i32 @func() {
    store i32 2, i32* @a
    ret i32 1
}

define dso_local i32 @func2() {
    store i32 4, i32* @a
    ret i32 10
}

define dso_local i32 @func3() {
    store i32 3, i32* @a
    ret i32 0
}

define dso_local i32 @main() {
    br label %1

1:                                                ; preds = %0
    %2 = call i32 @func()
    %3 = icmp ne i32 %2, 0
    br i1 %3, label %4, label %7 

4:                                                ; preds = %1
    %5 = call i32 @func3()
    %6 = icmp ne i32 %5, 0
    br i1 %6, label %10, label %7 ; 基本块1和4一起来判断fun() && fun3()是否为0

7:                                                ; preds = %4, %1
    %8 = call i32 @func2()
    %9 = icmp ne i32 %8, 0
    br i1 %9, label %10, label %12

10:                                               ; preds = %7, %4
    %11 = load i32, i32* @a
    call void @putint(i32 %11)
    call void @putstr(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0))
    br label %12

12:                                               ; preds = %10, %7
    br label %16

13:
    %14 = call i32 @func3()
    %15 = icmp ne i32 %14, 0
    br i1 %15, label %16, label %18

16:                                               ; preds = %13, %12
    %17 = load i32, i32* @a
    call void @putint(i32 %17)
    call void @putstr(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.1, i64 0, i64 0))
    br label %18

18:                                               ; preds = %16, %13
    br label %19

19:                                               ; preds = %18
    %20 = call i32 @func3()
    %21 = icmp ne i32 %20, 0
    br i1 %21, label %26, label %22

22:                                               ; preds = %19
    %23 = call i32 @func()
    %24 = call i32 @func2()
    %25 = icmp slt i32 %23, %24
    br i1 %25, label %26, label %28

26:                                               ; preds = %22, %19
    %27 = load i32, i32* @a
    call void @putint(i32 %27)
    call void @putstr(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str.2, i64 0, i64 0))
    br label %28

28:                                               ; preds = %26, %22
    ret i32 0
}
*/


条件判断与循环
循环

for (initialization ; condition ; step){ // code to be executed }
根据该规则，得到跳转循环图：alt text

break/continue

break 跳出循环，continue 跳过本次循环。再通俗点说就是，break 跳转到的是 BasicBlock，而 continue 跳转到的是 ForStmt2即可实现。
得到流程图如下：alt text

数组与函数
数组

此处先前提提要一下getelementptr 指令，其用来计算地址，本身不对数据做任何访问和修改，逐类型维度展开：<result> = getelementptr (<ty>, <ty>* <ptrval>{, [inrange] <ty> <idx>}*)，其中第一个<ty>为第一个索引指向类型，有时为返回值类型，第二个表示后面的指针基地址ptrVal类型， <ty> <index> 表示的是一组索引的类型和值，索引指向的基本类型确定的是增加索引值时指针的偏移量，

  1. 若访问三维数组某元素arr[0][0][0]，则GEP:gep [2*[2*[2*i32]]], [2*[2*[2*i32]]] * %..., i64 0, i64 0, i64 0, i64 0
  2. 但是对于一个指向二维数组的指针取某元素，同样是arr[0][0][0]，GEP却为:gep [2*[2*i32]], [2*[2*i32]] * %..., i64 0, i64 0, i64 0
  3. 原因在于，对于三维数组arr[2][2][2]，GEP将其解析为指向三维数组的指针，也就是说对于GEP来说如果解析类型已为指针类型则将相应的索引指向类型设置为该指针类型的Ref-Type，反之将该类型作为索引指向类型。
    当该指令指定 inbound 时，如果下标访问超过了数组的实际大小，那么 getelementptr 就会返回一个 “poison” 值，而不是正常计算得到的地址，算是一种越界检查。
    结合实例来讨论一下： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 考虑数组a[5]
    可以采用如下两种方法：
    // 因为此处a表示的存储相应数组对象的地址，因此@a的值与&a的值一致，因此此处@a的类型为[5 x i32]*，而其指向的元素即数组对象的类型则为[5 x i32]，相应的偏移为@a[0][3]，即*(@a + 0)[3] <==> *(&a)[3]
    ; 方法一
    %1 = getelementptr [5 x i32], [5 x i32]* @a, i32 0, i32 3

    ; 方法二
    %2 = getelementptr [5 x i32], [5 x i32]* @a, i32 0, i32 0
    %3 = getelementptr i32, i32* %2, i32 3
数组定义与调用

对于全局数组定义，与全局变量一样，同学们需要将所有量全部计算到特定的值。对于一个维度内全是 0 的地方，可以采用 zeroinitializer 来统一置 0，同样的对于局部的static来说其位置仍置于全局中，还需要声明internal的链接，对于const属性的设置，只需在相应的链接符后添加即可。 

1
2
3
4
5
6
7
8
9
10
int a[1 + 2 + 3 + 4] = { 1, 1 + 1, 1 + 3 - 1, 0, 0, 0, 0, 0, 0, 0 };
int b[20];
char c[8] = "foobar";
/***
//中间代码
@a = dso_local global [10 x i32] [i32 1, i32 2, i32 3, i32 0, i32 0, i32 0, i32 0, i32 0, i32 0, i32 0]
@b = dso_local global [20 x i32] zeroinitializer
@c = dso_local global [8 x i8] c"foobar\00\00", align 1
*/

对于局部数组定义前同样需要使用alloca指令，存取仍要load和store，只是在此之前需要采用 getelementptr 获取数组内应位置的地址。
例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
int a[3 + 3] = {1, 2, 3, 4, 5, 6};
int foo(int x, int y[]) {
    return x + y[2];
}

int main() {
    int c[3] = {1, 2, 3};
    int x = foo(a[4], a);
    printf("%d - %d\n", x, foo(c[0], c));
    return 0;
}
// 中间代码
/***
declare i32 @getint()
declare i32 @getchar()
declare void @putint(i32)
declare void @putch(i32)
declare void @putstr(i8*)

@a = dso_local global [6 x i32] [i32 1, i32 2, i32 3, i32 4, i32 5, i32 6]

@.str = private unnamed_addr constant [4 x i8] c" - \00", align 1
@.str.1 = private unnamed_addr constant [2 x i8] c"\0A\00", align 1

define dso_local i32 @foo(i32 %0, i32* %1) {
    %3 = alloca i32
    %4 = alloca i32*
    store i32 %0, i32* %3
    store i32* %1, i32** %4
    %5 = load i32, i32* %3
    %6 = load i32*, i32** %4
    %7 = getelementptr inbounds i32, i32* %6, i32 2
    %8 = load i32, i32* %7
    %9 = add nsw i32 %5, %8
    ret i32 %9
}

define dso_local i32 @main() {
    %1 = alloca [3 x i32]
    %2 = getelementptr inbounds [3 x i32], [3 x i32]* %1, i32 0, i32 0
    store i32 1, i32* %2
    %3 = getelementptr inbounds i32, i32* %2, i32 1
    store i32 2, i32* %3
    %4 = getelementptr inbounds i32, i32* %3, i32 1
    store i32 3, i32* %4
    %5 = alloca i32
    %6 = getelementptr inbounds [6 x i32], [6 x i32]* @a, i32 0, i32 4
    %7 = load i32, i32* %6
    %8 = getelementptr inbounds [6 x i32], [6 x i32]* @a, i32 0, i32 0
    %9 = call i32 @foo(i32 %7, i32* %8)
    store i32 %9, i32* %5
    %10 = getelementptr inbounds [3 x i32], [3 x i32]* %1, i32 0, i32 0
    %11 = load i32, i32* %10
    %12 = getelementptr inbounds [3 x i32], [3 x i32]* %1, i32 0, i32 0
    %13 = call i32 @foo(i32 %11, i32* %12)
    %14 = load i32, i32* %5
    call void @putint(i32 %14)
    call void @putstr(i8* getelementptr inbounds ([4 x i8], [4 x i8]* @.str, i64 0, i64 0))
    call void @putint(i32 %13)
    call void @putstr(i8* getelementptr inbounds ([2 x i8], [2 x i8]* @.str.1, i64 0, i64 0))
    ret i32 0
}
*/

设计要点

value

按照指导书的方式，Value的属性主要包括值类型(具体的值由相应的子类自行实现，例如函数的值就是返回值其余同理，因此这里参考最终可能会输出的情况，设置VOID、LABEL、INT1、INT32、)、名称(即该中间成分的名字，对于这些会通过统一规定命名的方式保证相应生成的虚拟寄存器名的规范性，同时便于后续进行优化)、被使用链和使用链、语法类型(DECLARE、GLOBALVAR、CONSTANT、FUNCTION、BASICBLOCK、INSTRUCTION、OPERATOR、)

basic_block

注意为了区别于指令，基本块的名称没有%，但是为了llvm语法能够正常解析且保持指令格式的统一性，在使用相应的跳转指令时，需要添加上%，即:

1
2
3
4
5
br label %b_1

b_1:
    ...

因此我将基本块的名称除去%，而相应对label类型的变量进行字符化时为其名称添加上%.

全局变量、static变量等的使用

和alloca声明得到的类型一样都是指针类型，因此，注意对于一开始的变量的类型声明注意应该是指针类型，同理全局常量数组也是指针类型，注意创建时的类型正确，不过对于全局非数组常量来说，编译阶段可以确定，因此后续使用时可以直接拿数进行运算，而不用再声明相应的变量，因此其实最后可以直接将这类声明去掉，因为后续的代码并没有使用此类变量，不过这仅限于最后生成中间代码。

GEP的实现

为了提高拓展性，此处采用逐步拆解数组的方式，也就是逐层剥开数组，例如下：

1
2
3
4
5
6
7
// 如下是为一个a[5][5][6]数组的a[0][4][1]赋值0
// 即每次只褪去一层数组
 %5 = alloca [5 x [5 x [6 x i32]]], align 16
%11 = getelementptr inbounds [5 x [5 x [6 x i32]]], [5 x [5 x [6 x i32]]]* %5, i64 0, i64 0
  %12 = getelementptr inbounds [5 x [6 x i32]], [5 x [6 x i32]]* %11, i64 0, i64 4
  %13 = getelementptr inbounds [6 x i32], [6 x i32]* %12, i64 0, i64 1
  store i32 0, i32* %13, align 4

若为指针后套指针则需先转化成单指针再进行偏移计算，因为gep不支持多重指针的偏移,本质上是没有长度限制，也就是不允许直接在i32**上做偏移，需要先通过load，转化成i32*后再进行偏移，同时对于i32*的偏移不用两位，一位偏移即可。注意gep的偏移不一定是常量，也可以是变量，应该传入IrValue，而不是直接传入常数值

SSA

通过一次定义多次使用，实现静态单变量赋值，这样可以极大的扩大虚拟寄存器的活跃区间，便于实际寄存器的分配。

字符串的处理

这里注意如果词法分析时将双引号也纳入了是需要将其删去的

短路求值

假设LOrExp正确跳转到的基本块为trueBlock，错误跳转到的是falseBlock。对于LOrExp中的每个LAndExp，生成一个基本块，不如按顺序编号为0、1、2、…，则对于0号LAndExp，在其当前基本块内递归写入条件语句，并且判断正确直接跳转到trueBlock，而错误则跳转到1号基本块，其余除了最后一个同理。
对于最后一个LAndExp基本块，显然是最后的希望了，因此其跳转情况与LOrExp一致了。
假设对于LAndExp正确跳转到的基本块为trueBlock，错误跳转到的是falseBlock。LAndExp中的EqExp同理，则0号EqExp判断正确跳转到1号，判断错误则直接跳转到falseBlock，最后一号EqExp判断逻辑同LAndExp。

变量赋值

对于非数组变量直接拿alloca后的地址或者全局变量赋予的地址进行store指令赋值即可，对于数组才使用GEP指令。
请问如果局部数组给了一部分初值，没有初值的元素需要进行置零处理。

目标代码生成

常以编译器此前生成的中间代码、符号表及其他相关信息作为输入，输出与源程序语义等价的目标程序代码。
此处可以理解为对中间代码的翻译.

MIPS回顾

详见CO篇

.data段生成

全局数据段使用.data伪指令定义,涵盖所有全局变量的声明:具体操作为对每个全局变量，生成对应的指令。指令的格式应该根据变量的类型和初始化情况来确定。例如，对于 int 类型的变量，可以使用 .word 伪指令来分配 4 字节的空间。对于 printf 中的字符串，可以使用 .asciiz 来分配空间。
例如:对如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int a = 2;
int b[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

int main() {
    printf("This is a string\n");
    return 0;
}

/**
// 生成如下mips的.data代码
// 其中对于重复的初值可使用<value>:<count>的形式避免长串的值
// 此处暂时不用考虑字节对齐问题,因为在 .data 段汇编器是会自动完成字节对齐的操作的,但是在.text段使用1 字节存储 char 类型变量时就需要注意变量的分配的位置
// 且需要为printf格式化的字符串单独分配全局变量名称
    .data
    a: .word 2
    b: .word 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
    .str: .asciiz "This is a string\n"
*/

.text段生成

含有所有可执行指令以及用于跳转的标签,此处的关键就是将中间代码中虚拟寄存器转换为实际的寄存器,并完成内存管理.

栈帧管理

调用函数时需要为栈上分配一段内存为栈帧,其中含有函数中定义的局部变量,溢出的变量,保存的寄存器以及传出的参数.
此处较为关键的是参数的处理,不同函数间不可见,因此为了使被调用函数能正确获取参数,调用者需要将参数保存在紧挨着被调用者栈帧的位置，即当前的栈顶.尽管我们可以将前 4 个参数通过 $a0 - $a3 传递，我们仍需要在栈中为其预留位置（不用保存值）。由于实验只要求了int类型,因此此处不存在字节对齐问题.MIPS 要求了 lw/sw 指令的地址必须四字节对齐。此外，规范的 MIPS 还要求栈帧 8 字节对齐，因此必要时可以在 local variable 之后添加 4 字节的 padding.

寄存器分配

由于MIPS是寄存器到寄存器模型,每个参与运算的值都必须加载到寄存器中,因此中间代码中参与运算的变量都对应了一个寄存器(虚拟寄存器),但其数量是无限的,而MIPS中只有有限的32个寄存器,因此需要进行映射,即寄存器分配.
若不考虑优化,可使用栈式存储的方式,将变量保存在栈上,寄存器仅保存计算时的中间结果,计算完成后将结果写入栈中,但是并没有充分发挥寄存器存储下的运算优势,每次存取将会花费大量时间.
则需要考虑全局寄存器和局部寄存器的分配,对应于s和t寄存器,前者对应生命周期跨越基本块的,而后者则对应基本块内的变量.对于前者的分配,要考虑不同变量的生命周期范围,避免寄存器冲突,采用图着色和线性两种分配方式.但对于后者,基本块内不存在分支,结构简单,因此维护寄存器池即可高效分配.

数组操作

三个地方涉及数组:

  • 全局数组,存在.data,使用la加载基地址
  • 局部数组,在栈上分配一段连续空间,使用$sp与偏移量访问
  • 参数数组,传递数组基地址即可,保存时也只保存地址
    操作核心只有:1.基地址的获取2.偏移量的计算
    例如:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    int a[2] = { 1, 2 };
    a[1] = 3;
    /**
    //当a存在$sp+0处
    li $t0, 1           # a[0] 初始化
    li $t1, 0			# index = 0
    sll $t1, $t1, 2		# 4字节对齐
    addu $t2, $sp, $t1
    sw $t0, ($t2)

    li $t0, 2           # a[1] 初始化
    li $t1, 1			# index = 1
    sll $t1, $t1, 2		# 4字节对齐
    addu $t2, $sp, $t1
    sw $t0, ($t2)

    li $t0, 3           # a[1] = 3
    li $t1, 1
    sll $t1, $t1, 2
    addu $t2, $sp, $t1
    sw $t0, ($t2)
    */

函数调用

对一个函数来说,除了自身指令,前后还应各有一小段代码进行准备和清理工作,即函数序言和函数尾声,前者申请所需栈空间,更新$sp,保存使用到的全局寄存器,及自身的$ra寄存器;后者释放栈空间，恢复全局寄存器（如果需要）以及 $ra 寄存器。
对于函数调用者，有以下几个步骤：

  1. 参数传递，将函数参数压入栈中，对MIPS，可以将前四个参数通过 $a0 - $a3 四个寄存器传递，但仍需要为其在栈中预留位置。参数的位置由参数编号和当前的 $sp 决定，从而被调用者可以在不知道调用者栈帧的情况下获取参数。
  2. 保存现场，也可交由被调用者的函数序言。
  3. 函数跳转，通过jal 或 jalr 指令跳转到被调用的函数，函数返回值被保存在 $v0 寄存器中。
  4. 恢复现场，也可将这任务交由被调用者的函数尾声。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//例如，对于如下函数调用
int f(int a) {
    int b = a;
    return b;
}

int main() {
    f(1);
    return 0;
}

/***
f:
    subu $sp, $sp, 8   # 申请栈空间
    sw   $ra, 0($sp)   # 保存自己的 $ra
                       # 如有必要，保存使用到的全局寄存器
    
    sw   $a0, 8($sp)   # 如需要，保存参数至预留的栈空间，这里是保留到调用者的栈空间
    
    lw   $t0, 8($sp)   # b = a，相应的取数的时候也是去调用者的栈空间里取
    sw   $t0, 4($sp)
    
    lw   $t0, 4($sp)   # 准备返回值
    move $v0, $t0
    
    lw   $ra, 0($sp)   # 恢复自己的 $ra
    addu $sp, $sp, 8   # 恢复栈帧
    
    jr   $ra           # 返回
    
main:
    subu $sp, $sp, 8   # 申请栈空间
    sw   $ra, 4($sp)   # 保存自己的 $ra
                       # 如有必要，保存使用到的全局寄存器
                       
    li   $a0, 1        # 传递参数
    jal  f             # 调用函数
    move $t0, $v0      # 获取返回值（此处未使用该返回值）
    
    lw   $ra, 4($sp)   # 恢复自己的 $ra  
    addu $sp, $sp, 8   # 恢复栈帧
    
    li $v0, 10         # 10 号系统调用，结束程序
    syscall
*/

参考代码中的目标代码生成

结构设计

要点在于内存管理和寄存器的处理，即怎样将 LLVM IR 中的虚拟寄存器对应到 MIPS 的物理寄存器和内存。

寄存器相关
栈式结构

将内存的数据区视为一个栈，将运行期数据存放到内存栈中，保证当前执行指令的每个操作数都位于栈顶，操作数出栈后计算，结果入栈。寄存器不能用于保存运算结果。对于内存频繁出入栈将导致目标程序的开销巨大。

寄存器池

使运行期数据能够存储在寄存器中，如：

1
2
3
4
5
6
7
8
    ; a = a-4;
%2 = load i32, i32 * %1
%3 = sub i32 %2, 4
store i32 %3, i32 * %1
// 相应asm代码为
lw    $t0, xxx($fp)
sub   $t1, $t0, 4
store $t1, xxx($fp)

此方式重点在于找到与虚拟寄存器关联的MIPS寄存器，要建立可用寄存器池，以及已用寄存器的全局符号表，维护寄存器与指令关联关系的上下文信息，包括关联关系的建立和释放。比如，load 指令翻译中将 $t0 与 %2 相关联，sub 指令翻译中将 $t1 与 %3 相关联。sub 指令后 %2 不再使用，可以取消 $t0 与 %2 的关联。将寄存器的分配、虚拟寄存器和 MIPS 寄存器的符号表通过全局管理器操作。

相应实现：

  1. 按申请顺序循环轮流分配寄存器，达到性能平衡
  2. 管理寄存器和中间代码语法结构间关联关系，按照语法翻译需要给出绑定、索引和释放方法，做好寄存器的发放和回收。
  3. 寄存器不够分配时给出将寄存器数据转移到内存中的解决方案，此处可以理论上释放不再使用的虚拟寄存器的关联关系，或近期/该基本块内不再被使用的寄存器。
  4. 寄存器不够用时，将最远使用的寄存器数据推到栈上，并将原本 LLVM IR 语法结构与寄存器的关联修改为与栈指针的关联。可以将栈上的指针表示为与栈底的偏移量。
    因此，与 MIPS 栈指针关联的语法结构有两种：
  5. LLVM IR 指针，包括 alloc 指令和 getelementptr 指令
  6. 尚未作为操作数使用，但是因为 MIPS 寄存器不够因此被推到栈上的 LLVM IR 虚拟寄存器

相关需要注意的地方

最朴素的想法便是使用栈式寄存器分配，类似于中间代码的生成，对于MIPS来说，针对中间代码的生成做逐一翻译，即可，设置MipsModule类仿照IrModule，其中存储.data段和.text段的所有mips指令，因此在生成时只需要顺序打印这些指令即可完成翻译。
再通过一个MipsManager类实现相应指令的插入以及函数栈的管理，这种栈式寄存器，通过计算操作数以及计算结果都存取自(有时操作数可能来自于较少的函数调用时分配的a0-a3寄存器)内存，因此对于内存的存取操作需要格外细致，此处设计的函数栈，包含一个当前函数栈中栈顶至栈底的偏移offset，由于每个函数都有自己的函数栈，因此栈底即$sp的值也会随时变动，因此此处只存储相应的栈顶的偏移，同时为了存取对应中间代码IrValue的值，部分是操作数部分是计算结果，设计了一个哈希表来存储在该函数栈中存储的IrValue存储空间相对于栈底的偏移，需要从内存中获取的时候直接根据偏移从相应的地址处load数据即可，同时由于栈空间是从高地址向低地址生长，而写入内存值的时候却是从低地址向高地址写的，因此对于存储的地址都是采用低地址作为首地址，也就是先分配空间(offset-x)，再返回相应的offset，此外，默认每个函数内可使用所有可调用的寄存器来完成相应的计算，因为在函数调用时会将现场保存到调用函数的函数栈中，返回时再重新恢复现场，这样就给了函数内计算很大的操作空间，因此每个函数需要一个相应寄存器与相应存储的IrValue的哈希表来表示当前函数中分配出的所有寄存器，作为函数调用时保留现场的依据。
此外，设计了一个MipsComponent类来抽象所有的mips指令的操作，并实现其在创建时便自动加入mipsModule的相应段中，其中对于.data段主要有.word、.asciiz和.space等伪指令分别用来表征全局变量、字符串和数组，都代表的是相应的数据的存储空间；对于.text段，则主要是alu(addu、subu(此处使用无符号计算是为了避免计算溢出，因为有符号计算有溢出的风险)、and、or、sll、sra等)、branch(bne、beq等)、icmp(sgt、seq、slt等)、lw、sw、mul、div、mfhi、mflo、j、jal、jr、syscall、label和la、li、move等拓展指令，按照指令的格式划分为了几个类便于最终mips代码的翻译打印。
最后就是针对每个IrValue类进行相应的翻译工作了，对于IrModule来说，就是将所有组件都mips化就行了，从全局变量到全局字符串，再到所有的函数，但是注意在开始函数的翻译之前，需要先添加一条jal main和j end的指令，前者是先去执行main函数，后者是在main函数结束后跳转到程序结束的函数end处。
对于IrFunction，先为所有的参数分配相应的存储空间，由于可以使用a0-a3寄存器作为存储前四个参数的寄存器，因此此处对于前四个参数，都是存储在寄存器中的，需要标记在该函数的已分配寄存器中，此外的参数只能存储在函数栈中，此处虽然前四个参数没有存储在内存中，但是为了与标准统一，此处在函数栈中还是为前四个参数保留的存储空间，这一点需要与函数调用时对于实参的存储保持统一。不过此处只是进行空间的分配，并不进行实际的值的写入，主要是因为在中间代码生成时对于函数内部的实现，为了减少寄存器的活跃范围，使用了alloca和store语句来重新分配虚拟寄存器并存入相应参数值，因此具体的参数存储需要等到执行这两个语句时来实现。再来就是执行其下所有的Block进行mips化了。
对于IrBasicBlock，对每个指令都进行mips化即可。
对于IrInstruction，伪指令的实现，按照相应的格式添加即可，其中采用标签名为对应变量名取掉首字符，也就是去掉%或@，除了基本块，此外就是逐条翻译，这里给出几个需要注意的点。
对于io类型的指令，此处需要注意到对于输出的值，都需要先存储在$a0里进而调用syscall来实现输出，但是$a0在函数调用时就给分配出去了，里面很可能存储着第一个参数，因此，需要在进行输出前后分别进行对$a0值的保留和复原。
对于alloca指令，由于是指针类型，因此操作的数据都是地址，首先先针对数组或者普通变量，进行相应的空间分配，此处全部分配到函数栈上，因为操作的是地址，也就是相应变量的地址，然后根据当前的IrValue存储的空间进行地址值的写入，若存在寄存器中，则写入寄存器，若存在内存中则写入内存。
对于alu和icmp类型的指令，先将操作数加载到相应的寄存器中(已分配的或者暂时的寄存器$k0或$k1中)，然后通过计算存放到结果寄存器中，再将寄存器中的值存入当前IrValue的存储空间(可能是寄存器，也可能是已有的或新开的函数栈空间)。
对于位扩展与截断指令，对于扩展来说，mips并不存在所谓的扩展指令，都是以32位作为位宽的，除了部分浮点寄存器，因此此处只需要将原来的IrValue对应的值映射到当前IrValue存储的空间即可，也就是先为当前IrValue分配一个寄存器，然后将原来IrValue对应的值存储到该寄存器中，然后再将寄存器中的值存入当前IrValue的存储空间；同理mips中也没有特别的截断指令，无非是对需要保留的所有位进行与1处理，而其余位则通过与0进行置0，因此需先为原先的IrValue分配一个寄存器，然后load值，然后进行与操作，最后存储到当前IrValue的存储空间。
对于跳转指令，只要生成跳转到相应的Block的指令即可，注意到此处并不知道两个block执行完后的block块的标签，因此，此处只生成跳转到相应block的指令，也就是将cond的值，同$zero比较，bne成立则跳转到trueBlock的标签所在处，否则多加一条指令跳转j到falseBolck指令所在处，注意，此处为什么不使用将某个基本块紧贴着条件跳转语句从而减少一条跳转指令的方式，因为不知道紧贴着条件跳转语句的是true还是false，因此直接使用两条跳转语句更为保险。
对于call指令要做的主要有以下几件事，首先，保存当前函数的现场，也即将当前函数中所有的分配了的寄存器的值存入函数栈中，位置为sp + currentOffset - 4 * length(所有被分配寄存器个数) <-> sp + currentOffset，其中按照顺序依次填入，此后的sp+currentOffset-4length-4 填入当前的栈顶$sp的值，方便回溯栈顶，sp+currentOffset-4*length-8填入当前进入新函数前的$ra寄存器值，为了后续回复$ra的值，以便递归函数的实现，然后将被调用的函数传入的实参在当前函数中获取并存入相应的寄存器或者新的函数栈内，(栈顶为sp+currentOffset-4*length-8的新栈)，并设置新栈顶$sp为sp+currentOffset-4*length-8,随后可以跳转到相应的函数处去执行了相应的函数逻辑内，注意此处使用*Jal,此后调用完函数回来，一方面需要进行现场的恢复，也就是将原来存入内存的值返还给分配的寄存器，此处注意先获取原来的$ra值，赋给$ra；然后直接获取原栈顶值$sp，自赋值，就恢复到原栈顶了,随后再根据偏移去依次恢复现场，最后还需要将可能的存入$v0的返回值存储到当前IrValue存储的空间中。
对于gep指令，需要分别为address和offset分配寄存器并且load相应的值，并为result申请寄存器，通过addu计算得到相应的地址值存入result寄存器，注意这里指针的单位是4个字节，因此此处的偏移乘上4才是实际的地址偏移，并将相应的寄存器内的值传入当前IrGep存储的空间中。
对于jump指令，直接跳转即可，使用j指令。
对于load和store指令，都是先为相应的地址和加载或存储的值分配寄存器，前者通过lw将内存地址中的值写入相应寄存器中，后者则通过将相应的值写入地址中。
对于ret则处理一下可能的返回值，这里规定返回值统一存储在$v0中，与函数调用处达到一致即可，随后调用jr返回即可。
需要注意：使用calc_i需要注意相应的立即数有没有超过2的16次方，即131,072，超过将会导致溢出问题，需要特别考虑，而不能盲目使用

代码优化部分

由于时间因素，我只做了以下几种常见的优化。

中端优化

SSA

普通赋值语句通过重命名变量即可
对于较为复杂的，如控制流

引入phi指令实现，其只能放置在基本块开头，且并行执行，即其返回值取决于进入当前基本块时状态。例如：

1
2
3
4
5
6
7
8
9
10
11
12
...
1:
    %2 = icmp eq i32 %0, 42
    br i1 %1, label %3, label %4
3: 
    br label %6
4:
    %5 = add i32 %0, 2
    br label %6
6:
    %7 = phi i32 [1, %3], [%5, %4]
    ret i32 %7

mem2reg:内存引用提升为寄存器引用

理论

将仅被load和store引用的alloca提升为虚拟寄存器。
共分为两步:

  1. 插入phi函数，对某个变量v，原有的v定义和新插入的phi函数将程序分割为多个活跃区间。每个区间以v定义开始且仅有这个定义能到达活跃区间内v的引用。
  2. 变量重命名，对变量的每个活跃区间，重命名变量所有定义和使用，即拆分为不同的变量，其中的定义和使用都唯一对应于一处赋值，这也就是链和网的作用。
插入phi

为了确定哪些基本块需要插入phi函数，引入join node概念：

  • 对两个不同的基本块n1、n2，及基本块n3(可与前两者相同，也可不同)
  • 若控制流图中存在从n1->n3的路径和n2->n3，且路径至少经过一条控制流图边，且这两条路径仅有n3一个交点，则n3为前两个基本块的join node。

对于同一变量不同定义所在的两个不同基本块，两者的join node必须插入phi。
对于变量可能存在多个基本块都有定义，则这些基本块构成集合中任意两个基本块的join node都必插入phi，而这也就是join set。由于插入的phi也是对该变量的定义，因此这些phi所在的基本块集合与此前所有非phi基本块集合的并集都要两两求join node并插入phi，可证，实际上只需要求出所有非phi定义所在基本块的join set即可。
对于SSA形式中的变量v，(其中，基本块x为基本块y必经节点指1.若控制流图中从入口到基本块y的所有路径都经过x，则称x为y的必经节点或称x支配y；若x支配y，且x !=``y，则称x严格支配y。支配树：则让x成为y的祖先，通过这种方式能使支配关系唯一确定一个树状结构，即支配树，根节点为入口节点。若不存在被x严格支配同时严格支配y的节点，则x为y的直接支配者，节点y的直接支配着x即是y在支配树上的父节点):

  • 若v被基本块中一个phi(n:v,...)引用，则v的定义节点为n必经节点。
  • 若v被基本块中不是phi的语句引用，则v定义节点为当前基本块的必经节点。

通过迭代的方式计算支配关系：

  • 根据控制流图迭代计算支配关系，设支配x的点集为DOM(x)，
  • 对每个节点x初始化支配关系DOM(x) = {x}，
  • 对每个节点按DOM(x) = 将控制流图中x的所有前驱节点的DOM取交集后同{x}取并迭代计算，原因是支配x的节点一定也支配x的所有前驱，不然不能支配x
  • 重复迭代步骤直到所有节点支配关系都不变，实际实现中可使用bitset加速。

通过支配关系来得到支配树

  • 若x严格支配y，则x的祖先节点明显少于y，则|DOM(x)| < |DOM(y)|。
  • 则对于y来说，所有严格支配y的节点x中DOM(x)最大的即为y的直接支配者，也就是y在支配树上的父节点。

要在定义节点恰不能支配的节点处插入phi函数。
给出支配边界定义：

  • 若节点n不严格支配节点x，但严格支配x的一个前驱节点，则x在n的支配边界DF(n)中。
  • DF(n)为满足上述条件的所有点集
  • 节点集合S的支配边界为其中所有节点的支配边界的并集。
    由于phi函数定义的存在，此处仍需要去迭代求支配边界，最终得到DF+(Dv) = join-set(Dv∪{entry}) = join-set(Dv)
    相应计算方式：
    alt text

插入算法：
alt text

变量重命名

插入phi后，变量v的一个活跃区间含：1. 活跃区间开头v的唯一定义；2.以及活跃区间中v的引用。
因此需要重命名对定义和所有引用，具体的：遍历到定义时创建新变量，遇到引用，找到支配该处引用的定义并替换为相应创建的新变量，需利用此前求出的支配树。
alt text
alt text
由于mips里没有实现phi函数的指令，因此需要中间代码中的phi函数消除：

  1. 将phi替换为并行赋值指令,即生成一系列不在MIPS指令集中的pc指令，与phi不同的是，其插入的是前驱基本块的末尾，而mem2reg中phi指令插入的是后继基本块的开头，其实也就是因为在mips中，跳转后并不知道跳转前来自哪里
  2. 并行赋值指令串行化，也即替换为一系列move指令
并行赋值

若前驱基本块有多个后继，则所有后继中phi对应的pc指令都将插入前驱基本块末尾，但实际上只应该执行其中的一条，其他的pc指令不当被执行，执行可能将影响语义，因此提出关键边。
关键边：若控制流图中的边(u,v)，若u有多个后继，且v有多个前驱，则这边为关键边。
没有关键边的SSA称为边分割的SSA
对于多个后继的基本块，在其每条出边上新建一个基本块即可移除控制流图所有关键边。
alt text

串行化

称pc指令b<-a中，b为目标寄存器，a为源寄存器。
则可将所有涉及虚拟寄存器看作有向图节点，pc指令方向表示依赖方向，即b需要获得a的值，每次只能选目标寄存器b未被依赖的pc进行改写，否则将会因为改写b而导致别的pc指令的错乱。若依赖关系成环，则选环上一寄存器，将其复制为a‘来破环。
具体算法：
pc指令转化为move指令

实践
  1. 遇到了call指令没有正常维护使用链的情况，使用的指令需要都添加到usesList中；修正了求直接支配者的算法，应该是当前节点的所有支配者(不含自身)的支配者个数最多的节点，而不是最少。
  2. 修改了gep的翻译逻辑，由于alloca和store语句的消除，当函数参数作为偏移时，gep指令不能直接将偏移结果直接存在偏移参数对应的寄存器中，这将会覆盖相应寄存器的值，应该先存到结果寄存器中，最后再将结果寄存器与相应的地址相加得到最终结果，具体实现如下：
    1
    2
    3
    4
    5
    6
    7
    8
    Register offsetRegister = getValueRegisterOrK1(offset);
                    this.loadValueToRegister(offset, offsetRegister);
                    // 此时值已经存在了分配给偏移的寄存器中
                    // 此时进行移位操作
                    new MipsAlu(MipsAlu.ALUType.SLL, result,
                            offsetRegister, 2);
                    new MipsAlu(MipsAlu.ALUType.ADDU, result, addressRegister, result);

死代码删除

理论

在SSA分析基础上，删除非活跃的的指令，活跃指令包含：

  • 对涉及控制流或有副作用的指令，指令引用的变量是活跃的，如br、call、sw、ret等
  • 对为活跃变量定值的指令，指令引用的变量活跃
    以函数为单位变量所有指令，维护指令和变量的活跃标记，迭代更新活跃标记，对无用的，删除定义其的指令，修改时同时维护定义-使用链。

可以删除不可达的函数和基本块，前者通过调用关系从main出发遍历所有函数，后者从控制流图入口基本块出发遍历所有基本块，其实通过分析支配关系可知，入口基本块不支配不可达基本块，发生变化后可再次分析并删除不可达代码，如：常量折叠或常量传播后，若跳转跳转为常量，则可改为无条件跳转，改变控制流图中的点或边。

实践
  1. 去除一个基本块中跳转指令后的多余指令(这些指令都不会再被执行了)和函数中不能到达的基本块。
  2. 主要删除了没有被调用的函数、无法到达的基本块和不会被输入输出、产生副作用的函数调用、内存存储和跳转返回指令等调用的无用指令，同时还针对可以进行合并的基本块进行合并，删去连接两者的唯一的跳转指令。即如下所示的情况：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    // 判断当前基本块是否可以和其唯一前驱基本块进行合并
        public boolean canMergeBlock() {
            // 判断前驱基本块是否唯一
            if (this.preBlocks.size() == 1) {
                IrBasicBlock preBlock = this.preBlocks.get(0);
                // 判断前驱基本块是否只有唯一的后继基本块且为当前基本块
                return preBlock.postBlocks.size() == 1
                        && preBlock.postBlocks.get(0).equals(this);
            }
            return false;
        }

GVN & GCM

理论

局部值编号，通过哈希寻找基本块内等价指令，合并等价指令定义的变量。
具体的，处理一条指令d<-op(a1,a2,...)时:

  • 若指令计算结果为常数，则将d的所有引用都替换为这个常数，即常数折叠
  • 若指令结果与操作数ai相同，则同样全用ai替换
  • 若指令计算值与其他指令d'<-op(...)同，同理
    全局值编号与LVN类似，但不限于基本块内，而是寻找函数内等价指令。
    GVN可能导致定义在引用后，需全局代码移动来予以纠正。
    全局代码移动大致如下：
  • 计算支配关系并建立支配树
  • 基于循环分析求出各个基本块的循环深度
  • 求出每条指令能被调度的最早基本块
  • 求出每条指令能被调度的最晚基本块
  • 在最早和最晚确定的区间内选择合适的基本块
    选择依据是循环深度尽可能的浅，且尽可能靠前。
实践

此处进行了针对比较指令的常量折叠，因为运算指令在生成的时候已经进行了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
IrValue valueL = usesList.get(0);
IrValue valueR = usesList.get(1);
if (valueL.isCon() && valueR.isCon()) {
    int numL = valueL.getConstInt();
    int numR = valueR.getConstInt();
    int result;
    if (type.equals(cmpType.EQ)) {
        result = (numL == numR) ? 1 : 0;
    }
    else if (type.equals(cmpType.NE)) {
        result = (numL != numR) ? 1 : 0;
    }
    else if (type.equals(cmpType.SGE)) {
        result = (numL >= numR) ? 1 : 0;
    }
    else if (type.equals(cmpType.SGT)) {
        result = (numL > numR) ? 1 : 0;
    }
    else if (type.equals(cmpType.SLE)) {
        result = (numL <= numR) ? 1 : 0;
    }
    else if (type.equals(cmpType.SLT)) {
        result = (numL < numR) ? 1 : 0;
    }
    else {
        throw new RuntimeException("Illegal cmpType: " + type);
    }
    this.changeAllUsersToValue(new IrConstInt(new IrValueType(IrBaseType.INT1), result));
    // 折叠成功
    return true;
}
return false;

然后利用块内的GVN编号将针对alu、icmp、gep指令的公共子表达式进行了替换删除，具体做法就是为上述几种指令设计特有的GVN编号：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// alu
// 按照字典序的方式组成string
        String nameL = usesList.get(0).getName();
        String nameR = usesList.get(1).getName();
        return (this.orderFree() && nameL.compareTo(nameR) >= 0) ?
                nameL + " " + instrType + " " + nameR :
                nameR + " " + instrType + " " + nameL;

// gep
        String addressName = getAddress().getName();
        String offsetName = getOffset().getName();
        return addressName + ":" + offsetName;

// icmp
// 按照从左至右排列的方式，可能没有覆盖全部类型，但是也能凑合用了
        String nameL = usesList.get(0).getName();
        String nameR = usesList.get(1).getName();
        return nameL + " " + instrType + " " + nameR;

然后遍历每个基本块，进行GVN编号与相应指令的哈希表维护，只使用当前基本块以及其支配者的特有的指令，若出现GVN编号重复则复用表中相同GVN编号该指令。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
boolean finished = true;
// 折叠潜在的常数比较指令
finished &= this.foldCompare(currentBlock);

// 当前基本块和其支配的基本块可以使用的新的公共子表达式，
// 由于对于其兄弟不一定可以使用，因此在遍历完所有子基本块后需要进行删除
HashSet<IrInstruction> usableBlocks = new HashSet<>();
finished &= this.removeSharedInstr(currentBlock, usableBlocks);
// 遍历其所直接支配的所有基本块
for (IrBasicBlock child : currentBlock.getChildren()) {
    finished &= this.visit(child);
}

// 你的兄弟享受不到你的红利嘞
for (IrInstruction instruction : usableBlocks) {
    gvnMap.remove(instruction.GVNValue());
}
return finished;

后端优化

对于alloca指令和gep指令翻译的优化

由于alloca指令的中间代码对应的值本质上就是存储空间的地址，同时该指令的使用不会跨越不同的函数栈，即在某一函数中定义的alloca不会在其他函数中再次被使用，则可以通过函数栈顶加上偏移的方式获得相应的alloca值。因此可以不用特意为其单开一块存储空间，而是直接考虑像记录该中间代码在栈中的位置一样，存储该指令值，只不过，对于其它指令来说获得在栈中位置后需要再从栈中取数，而对于alloca指令来说，其在栈中的偏移位置加上栈顶就是相应的值，不用多一次存取操作，可以减少对内存的操作。
同理，若gep的address是alloca，这里的alloca作用域一定限于当前的函数栈，且offset是constint，因此此时仍旧可以使用此前的只存储偏移的方式进行gep值的存储，减少对于内存的存取。
具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// alloca
 if (IOAdjuster.OPTIMIZE_BUTTON) {
            // 进行alloca指令的优化
            // 只存储相应的函数栈偏移不新开辟一个空间
            MipsManager.setValuesOffset(this, offset);
        }

// gep
if (offset instanceof IrConstInt irConstInt) {
                // 是常数的话，直接计算到相应的result寄存器中
                new MipsAlu(MipsAlu.ALUType.ADDIU, result, addressRegister,
                        irConstInt.getValue() << 2);
            }

// 同理存取时也不用直接从内存进行存取
// load
if (IOAdjuster.OPTIMIZE_BUTTON && address instanceof IrInstruction instruction
                && instruction.allocaOrConstGep()) {
            // 优化
            // 从栈中获取的偏移+上$sp就是实际地址
            new MipsLoadStore(MipsLoadStore.LoadStoreType.LW,
                    targetRegister, MipsManager.getValuesOffset(address),
                    Register.SP);
        }

// store
if (IOAdjuster.OPTIMIZE_BUTTON && address instanceof IrInstruction instruction &&
                instruction.allocaOrConstGep()) {
            // 优化
            new MipsLoadStore(MipsLoadStore.LoadStoreType.SW, tmpRegister,
                    MipsManager.getValuesOffset(address), Register.SP);
        }

乘除法优化

乘法优化

通过判断乘的常数是否为2的整数次幂，因此可以通过优化成<<与+的组合，例如：x*3 <=> x << 1 + x << 0,x*10 <=> x<<3 + x << 1,x*15 <=> x << 3 + x << 2 + x << 1 + x << 0。这样可以极大的简化运算。
同时对于两个操作数都是常数的情况，可以直接由编译器计算完成，直接得到相应的结果；对于其中一个操作数是常数的情况可以根据上述方式进行简化，其中可以特判1和-1的情况，前者保持非常数寄存器的值不变即可，而前者则用$0减去非常数寄存器值即可，对于0来说，相乘直接就是0了，因此需要特判上述三种常数。
对于两个都是非常数的情况只能相乘了。

除法优化

有定理如下：
$设m,d,l为非负整数，d != 0且2^{N+l} <= m * d <= 2^{N+l} + 2^l，则对于0<=n<2^N的整数n有n/d = (m * n) / 2^{N + l}$
大致思路是将除法转化为乘法指令和移位指令，如下:quotient = dividend / divisor = (dividend * multiplier) >> shift，即先乘一个较大的常数，然后用右移的方式得到最终的答案，因此核心在于如何得到multiplier，由于mips为32位的架构，因此需考虑溢出的问题，即mips中乘法运算会将结果保存在hi、lo中，当结果超过32位时，将出现高32位在hi寄存器中，低32位在lo中的情况。因此，尽量使得乘上multiplier后的数刚好在2^(N + l)和2^(N+l) + 2^l之间，其中N为32，这样乘完后取hi中的值，再将该值右移l位后的结果就是相应的整除结果。
其中，对于移位为0的情况，可以不用考虑，避免多余sra指令，例如： 

1
2
3
4
5
6
7
if (k == 1) {
                new MipsAlu(MipsAlu.ALUType.SRL, resultRegister, Register.K1, 32 - k);
            }
            else {
                new MipsAlu(MipsAlu.ALUType.SRA, resultRegister, Register.K1, k - 1);
                new MipsAlu(MipsAlu.ALUType.SRL, resultRegister, resultRegister, 32 - k);
            }

因此，可以依次枚举l，验证定理中的式子是否成立，进而得到一组合法的m、l，由于是向零取整的有符号除法，则计算m,l时N需要代入N-1=31，且d要取绝对值。
即由于$2^{N+l}/d<=m<=(2^{N+l} + 2^l)/d$，因此先令$l=log_2d$，这样可保证取值范围不为空，然后不断减小$l$，直到取值范围内只有一个整数，这样可以使$m$尽可能的小，且少数情况下可使$l=1$，在实现的时候可以使用一个子类来涵盖所有相关的信息。
当d>0时，可将n/d改写为：

  • $n, d=1$
  • $SRA(n+SRL(SRA(n, k-1), 32 - k), k), d = 2^k$
  • $SRA(MULSH(m,n), l-1) + SRL(n, 31), m < 2 ^{31}$
  • $SRA(n + MULSH(m-2^{32}, n), l - 1) + SRL(n,31)$, 其他情况
    SRA(x,n)为算数右移n位，SRL位逻辑右移n位。MULSH(x,y)为取x与y有符号乘后的高32位
    对于d<0的情况，求出|d|后对计算结果取反即可。
运算处的常量折叠

考虑了两个常数(包括IrConstInt和值为IrConstInt的Global)直接运算的情况，对加法考虑了+0的情况；对减法也考虑了-0和被0-的情况；对and考虑了x&0=0，x&(-1)=x，x&x=x的情况；对or考虑了x|0=x，x|(-1)=-1，x|x=x的情况；乘法只考虑了将乘以2的幂次的情况改为左移，看评测需求好像对于二进制只有两位1的转换为两个左移加法应该会优于单mul的效果，还考虑了乘0、乘1、乘-1的情况；对于除法，考虑了除1、除-1的情况，对于模，考虑了x%x=0，以及将x%d转化为x-x/N*N的情况。

线性寄存器分配

迫于时间原因，通过活跃变量分析实现了较为简单的线性寄存器池分配，也就是谁有空就用谁，将后续不再使用的寄存器释放，同时释放遍历的当前指令使用的中间代码为其在本基本块中最后一次使用，且其不在当前基本块的out集合中，也就是该基本块的后续支配基本块都不会再用到该中间代码，且其有寄存器分配在身，此时可以释放其所分配的寄存器。
具体实现如下：

1
2
3
4
5
6
7
if (this.valueRegisterMap.containsKey(useValue)
                            && lastUseMap.get(useValue).equals(instruction)
                            && !instruction.isInOutSet(useValue)) {
                        // 对该指令使用的该value后续不再参与分配
                        this.registerValueMap.remove(this.valueRegisterMap.get(useValue));
                        neverUseSet.add(useValue);
                    }

此外，尤其需要注意对于当前基本块与其兄弟基本块直接的寄存器分配情况，也就是注意需要缓存当前父节点使用的寄存器分配规则，你可以释放但是你的兄弟不一定可以。同时需要考虑其本身以及其所有子节点是否能够用到某个value，如果用不到则可释放，即考虑该中间代码是否在子节点的in集合中，有则说明后续还需要使用，否则则不用。
因此每次为一个基本块及其所有支配子基本块进行完寄存器分配都要进行寄存器分配关系的恢复，例如： 

1
2
3
4
// 释放所有子节点定义的value用到的寄存器
this.freeDefineRegisters(defineSet);
// 恢复所有子节点认为没有用的且不是子节点定义的value
this.recoverNeverUse(defineSet, neverUseAfterDefSet);

你应该注意到了，要想做的上面那些，对于in和out的求解至关重要，根据定义:in[B] = use[B] \cup (out[B] - def[B])；out[B] = \cup in[P] P为B的后继基本块，因此需要先求解def和use集合：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
for (IrFunction function : module.getFunctions()) {
        for (IrBasicBlock block : function.getBlocks()) {
            HashSet<IrValue> defSet = block.getDefSet();
            HashSet<IrValue> useSet = block.getUseSet();

            // 先考虑phi指令，这些指令应该是最早发生的以及使用的
            // 使用的是来自前驱节点的值，当前全算进use里
            for (IrInstruction instruction : block.getInstructions()) {
                if (instruction instanceof IrPhi phi ) {
                    for (IrValue value : phi.getUsesList()) {
                        if (value != null && value.isUseValue()) {
                            useSet.add(value);
                        }
                    }
                }
            }

            // 接着再分析其他指令
            for (IrInstruction instruction : block.getInstructions()) {
                // 对所有指令进行分析
                for (IrValue useValue : instruction.getUsesList()) {
                    if (!defSet.contains(useValue) && useValue != null
                            && useValue.isUseValue()) {
                        useSet.add(useValue);
                    }
                }
                // 分析instr本身是否为定义指令
                // 即先定义后使用
                if (!useSet.contains(instruction) || instruction.defValue()) {
                    defSet.add(instruction);
                }
            }
        }
    }

此后再进行in和out集合的求解，即可，注意根据定义是需要一直求到完全不发生变化为止：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
for (IrFunction function : module.getFunctions()) {
            ArrayList<IrBasicBlock> blocks = function.getBlocks();
            // 对每个函数内都进行活跃变量的分析，直到in、out集合不变为止
            boolean changed = true;
            while (changed) {
                changed = false;
                // 对所有基本块逆序遍历
                for (int i = blocks.size() - 1; i >= 0; i--) {
                    IrBasicBlock analysisBlock = blocks.get(i);
                    // out：考虑所有后继块的in
                    HashSet<IrValue> newOutSet = new HashSet<>();
                    for (IrBasicBlock postBlock : analysisBlock.getPostBlocks()) {
                        newOutSet.addAll(postBlock.getInSet());
                    }

                    // in:
                    HashSet<IrValue> newInSet = new HashSet<>(newOutSet);
                    newInSet.removeAll(analysisBlock.getDefSet());
                    newInSet.addAll(analysisBlock.getUseSet());

                    // 比较看是否有发生变化
                    HashSet<IrValue> oldOutSet = analysisBlock.getOutSet();
                    HashSet<IrValue> oldInSet = analysisBlock.getInSet();
                    if (!newOutSet.equals(oldOutSet)
                            || !newInSet.equals(oldInSet)) {
                        changed = true;
                        analysisBlock.setInSet(newInSet);
                        analysisBlock.setOutSet(newOutSet);
                    }

                }
            }
        }

特殊的，此处还需要注意不用为alloca和地址是alloca且偏移为常数的gep指令分配寄存器,因为在优化状态下，它们的值自然存在函数栈中，不需要参与到寄存器的分配中来。

窥孔优化

考虑了对于同一块地址进行连续的写入sw覆盖操作，只保留其中最近的一条：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
boolean finished = true;
        ArrayList<MipsComponent> text = module.getText();
        HashSet<MipsLoadStore> deleteSet = new HashSet<>();
        for (int i = 0; i < text.size(); i++) {
            if (i > 0) {
                // 考虑除了第一条指令外其前是否有连续写的情况发生
                MipsComponent nowInstr = text.get(i);
                if (nowInstr instanceof MipsLoadStore nowSW
                        && nowSW.isSW()) {
                    // 只有是sw指令才考虑连续写入的问题
                    MipsComponent preInstr = text.get(i - 1);
                    if (preInstr instanceof MipsLoadStore preSW
                            && preSW.isSW()) {
                        if (nowSW.getAddress().equals(preSW.getAddress())) {
                            // 前一个写入的地址与当前写入的地址一致，那么这两者取后者即可
                            finished = false;
                            deleteSet.add(preSW);
                        }
                    }
                }
            }
        }

        for (MipsLoadStore store : deleteSet) {
            // 删除所有连续写
            module.deleteTextValue(store);
        }
        return finished;

识别对同一地址的连续LW，只保留第一个LW，后续的LW转为MOVE:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
boolean finished = true;
    // 识别对同一地址的连续LW，只保留第一个LW，
    // 后续的LW转为MOVE
    ArrayList<MipsComponent> text = module.getText();
    boolean flag = false;
    while (!flag) {
        flag = true;
        // 当无法再进行消除的时候退出
        ArrayList<MipsLoadStore> toMoveLWs = new ArrayList<>();
        Register originalRt = null;
        for (int i = 0; i < text.size(); i++) {
            MipsComponent component = text.get(i);
            if (component instanceof MipsLoadStore lw && lw.isLW()) {
                String address = lw.getAddress();
                for (int j = i + 1; j < text.size(); j++) {
                    if (text.get(j) instanceof MipsLoadStore postLw
                            && postLw.isLW() && postLw.getAddress().equals(address)) {
                        // 紧接着连续是对同一地址的数据加载，则可以寄存器复用
                        toMoveLWs.add(postLw);
                    }
                    else {
                        // 否则直接退出即可
                        break;
                    }
                }
                // 如果有连续的对同一地址的加载，那么lw就是始祖了
                if (!toMoveLWs.isEmpty()) {
                    // 有孩子孩孙
                    originalRt = lw.getRt();
                    // 直接退出进行替换
                    flag = false;
                    finished = false;
                    break;
                }
            }
        }
        if (originalRt != null) {
            // 存在始祖
            // 为孩子孩孙进行指令的替换，后续lw全换成move
            for (int i = 0; i < toMoveLWs.size(); i++) {
                MipsLoadStore lw = toMoveLWs.get(i);
                Register moveDst = lw.getRt();
                MipsMove newMove = new MipsMove(moveDst, originalRt, false);
                module.setTextValue(lw, newMove);
            }
        }
    }
    return finished;

对于对同一寄存器的连续lw在一定情况下也可以删除前面多余的指令，前提是前面lw的得到的值在后续的连续lw指令中不会再当作base使用到，也就是它不是加载地址的指令的时候，此时可以将其删除，因为其值会被后续的lw指令给覆盖掉，具体实现如下：

1

利用zero替换掉被li用0赋值的寄存器，其中只能替换掉可以使用的寄存器，例如t0-t9、s0-s7、以及k0、k1、fp和gp(在我的设计中，这些都可以被使用()):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 由于将k0或者k1作为暂存
// 因此直到下一条对于k0或者k1的赋值
// 中间对于k0或者k1的引用都可以修改为zero
ArrayList<MipsComponent> text = module.getText();
boolean finished = false;
while (!finished) {
    finished = true;
    Iterator<MipsComponent> iterator = text.iterator();
    while (iterator.hasNext()) {
        // 考虑li指令，且只考虑li k0/k1/fp 0
        // 这三个临时寄存器
        MipsComponent component = iterator.next();
        if (component instanceof MipsLi li && li.canReplace()) {
            Register replacedRegister = li.getDst();
            // 删掉该li指令，直到下一条对该register进行赋值的指令之前
            // 中间所有对该寄存器的应用都可以用zero代替
            iterator.remove();
            while (iterator.hasNext()) {
                MipsComponent nextComponent = iterator.next();
                // 若发生改变则返回为true，则相应的还不能结束
                finished &= !nextComponent.setRegisterToZero(replacedRegister);
                if (nextComponent.valueToRegister(replacedRegister)) {
                    // 遇到对原寄存器赋值的指令，则设置完zero后直接退出
                    break;
                }
            }
        }
    }
}

基本块重排

若基本块B1后继仅有B2，也即B1无条件跳转到B2，那在汇编代码中直接将B1与B2相邻可节省B1的跳转，因此可以删除mips生成后多余的j跳转指令，例如对于j跳转的基本块就紧挨着j指令的情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
ArrayList<MipsComponent> text = module.getText();
        int len = text.size();
        ArrayList<MipsJump> deleteArray = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            MipsComponent component = text.get(i);
            if (component instanceof MipsJump jump
                    && jump.getJumpType().equals(MipsJump.JumpType.J)) {
                // 只对j指令有效
                if (i < len - 1) {
                    MipsComponent nextComponent = text.get(i + 1);
                    if (nextComponent instanceof MipsLabel label) {
                        if (jump.getLabel().equals(label.getLabel())) {
                            // 添加删除j指令的下标
                            deleteArray.add(jump);
                        }
                    }
                }
            }
        }
        // 统一删除所有的多余j指令
        for (int i = 0; i < deleteArray.size(); i++) {
            module.deleteTextValue(deleteArray.get(i));
        }
```     
重调添加`if`分支跳转基本块顺序，由于对于该分支的翻译是先       
`bne ... $zero true_block`       
再          
`j false_block`
因此重调基本块顺序的时候先递归展开`false_block`，这样`j false_block`与`false_block`相连，又可以去掉一条`j`指令。      
此外，还进行了去掉原先与跳转到`end`的`j`指令，直接将`end`安在`jal main`后执行即可:


## 期末
### 一.新增两个文法
**注意看清楚测试点，并不是所有点都是课上的，请你认真审题，一定要认真审题，不要急躁**。
```c
// 新增的cin作为新的保留字，token为CINTK;新的作用符，token为SHR
语句 Stmt -> LVal '=' Exp ';' | [Exp] ; | Block | 'if' '(' Cond ')' Stmt [ 'else' Stmt ] | 'for' '(' [ForStmt] ';' [Cond] ';' [ForStmt] ')' Stmt | 'break' ';' | 'continue' ';' | 'return' [Exp] ';' | 'printf' '(' StringConst {',' Exp}')'';' | 'cin' '>>' LVal ';'

// 新增的运算符：->, token为LEFTTORIGHT，此处说明'->'和*、/、%的作用级一致
// a->b=a+(a+1)+...+b，这里应该使用等差数列来简化运算，而不是使用循环的方式(也可以只要你考场上能写出来)
// 即a->b = (a+b) * (b - a + 1) / 2，使用这个公式就很简单了，一定要认真思考而不是直接上手，你看你考完，用半个小时不到就解决了
乘除模表达式 MulExp -> UnaryExp {('*' | '/' | '%' | '->') UnaryExp}

一定要汲取经验教训，认真审题，动脑思考!!!

优化三个点

课下没问题就可以通过

简答题

由于打包优化前后的中间代码和目标代码的时候出现了点小差错，导致写最后一题的时间不是很充足了，真是一次糟糕的考试，不要让这次成为常态，你太急躁了。
只记得前两道题了，其实也就只做到了前两道题，害，时间分配和对自己代码不够熟悉的问题，忘了将end函数内的内容直接安在jal main后这个给忘了，而不是单纯作为一个优化，害，自找麻烦。
注意此处题目指明需要结合自身代码进行回答，也就是需要具体到相应的类名

  1. 问你如何处理第5个参数的传递，以及在函数内如何调用该参数？
  2. 问你如何处理调用函数时函数内与调用函数内的重名变量的关系?
  3. 后面的没做，害，太差劲了!