9.2 KiB

Raw Permalink Blame History Unescape Escape

PW6 实验报告

PB21111682 龚劲铭 PB21000175 李润时

问题回答

1-1 请给出 while 语句对应的 LLVM IR 的代码布局特点，重点解释其中涉及的几个`br`指令的含义（包含各个参数的含义）

while语句需要细分为至少三个基本块（不考虑嵌套）：condbb、truebb、falsebb，控制流（从 preds 注释可以看出）为：通过condbb的终止语句br i1 %4, label %5, label %11判断，若条件%4 为真跳转到truebb入口%5，否则跳转到falsebb入口%11，一般falsebb入口也是紧跟在while循环体后的下一个基本块入口%11，truebb的出口跳转到condbb%2，即循环执行一次后重新判断循环条件是否成立，无条件跳转br label %2;至于truebb和falsebb的入口标号值分配，需要视truebb内标号使用情况而定。

1-2 请简述函数调用语句对应的 LLVM IR 的代码特点

函数调用的指令有如下格式

%result = call return_type @function_name(arg_type %arg1, arg_type %arg2, ...)

其中return_typr为返回类型,每一个arg_type为对应参数的类型。 @function_name为函数名称，以@作为标识符。以func.sy中的函数调用为例:

%7 = call i32 @add(i32 %4, i32 %5)

以call标识为函数调用语句,第一个i32标记函数的返回类型，add为调用的函数名称，后续括号内为对应参数的类型和传入的参数。

2-1. 请给出`SysYFIR.md`中提到的两种 getelementptr 用法的区别, 并解释原因:

%2 = getelementptr [10 x i32], [10 x i32]* %1, i32 0, i32 %0
%2 = getelementptr i32, i32* %1, i32 %0

两者的寻址单位大小不同：第一种用法将地址计算单位（指针指向的类型）解释为指向10个int32类型整数的一维数组，后续偏移量参数的+1计算会占用一个一维数组的大小，之所以有[]表示可重复参数是为了适应多维数组（结构体）的情况第二种用法的地址计算单位（指针指向的类型）即一个int32整数 更详细的示例如下：

struct RT {
  char A;
  int B[10][20];
  char C;
};
struct ST {
  int X;
  double Y;
  struct RT Z;
};
int *foo(struct ST *s) {
  return &s[1].Z.B[5][13];
}

其中&s[1].Z.B[5][13]的地址计算为 %arrayidx = getelementptr inbounds %struct.ST, %struct.ST* %s, i64 1, i32 2, i32 1, i64 5, i64 13 进一步可分解为：

%t1 = getelementptr %struct.ST, %struct.ST* %s, i32 1                        ; yields %struct.ST*:%t1
%t2 = getelementptr %struct.ST, %struct.ST* %t1, i32 0, i32 2                ; yields %struct.RT*:%t2
%t3 = getelementptr %struct.RT, %struct.RT* %t2, i32 0, i32 1                ; yields [10 x [20 x i32]]*:%t3
%t4 = getelementptr [10 x [20 x i32]], [10 x [20 x i32]]* %t3, i32 0, i32 5  ; yields [20 x i32]*:%t4
%t5 = getelementptr [20 x i32], [20 x i32]* %t4, i32 0, i32 13               ; yields i32*:%t5

3-1. 在`scope`内单独处理`func`的好处有哪些。

1,变量和函数可以重名。 2,可以提高查找效率。

实验设计

常量表

建立并例化一个类GlobalConst，类中主要维护两个map映射，在生成 IR 过程中该类负责存储声明为const的常量，并允许程序通过常量名从常量表中引用对应的常量值。

变量定义

全局变量 利用 SysIF 提供的接口GlobalVariable::create声明全局变量，并push到全局scope中。若变量被显式初始化，则检查initializers类型是否匹配，若是数组变量则还要检查初始值个数是否一致，不一致的剩余部分全部初始化为 0。
局部变量 需要生成分配内存空间alloca、类型转换fptosi/sitofp、存储变量初始值store的系列 IR，数组变量初始值在store之前还需生成gep指令先计算元素具体存储位置，最后将被声明变量push到局部scope中。

左值

直接返回数值 在全局变量声明时，左值可以作为初始值，比如在这之前被声明为const的单变量或数组元素，需要查找常量表直接返回对应数值。
数组元素 先从scope中返回数组基址，再从语法树节点中的array_index返回下标偏移量，然后相应地生成gep和loadIR 指令。
指针或普通变量 直接生成load指令。
左值为函数名的情形在Funcvisit 里处理。

条件表达式

单目运算符 在语法树中UnaryCondOp只有NOT!，目标是生成与零值比较的icmp_eq/fcmp_eqIR，整型数要保证扩展到 32 位，指针型数据由于是非零值则默认为真。
双目运算符 普通关系运算符的处理逻辑与单目类似，有时需要进行零扩展或类型转换。比较特殊的是双目逻辑运算符LAND和LOR，需要实现短路计算,故先访问lhs再按需要访问rhs，并创建四个 bb 块label:true_bb表示整个条件成立跳转地址、false_bb表示整个条件不成立跳转地址、next_bb表示下一个待判定条件跳转地址、after_bb表示整个条件判定结束后跳转地址,然后根据短路计算的逻辑生成相应的set_insert_point和cond_brIR 指令。

计算表达式

直接返回计算值 全局变量声明中部分常量表达式需要直接计算出结果，利用全局变量expr_cal_result在分别访问语法树中 lhs（双目）和 rhs 后获得表达式操作数值，再根据不同的操作符运算返回结果，更新expr_cal_result。
生成相应计算 IR 双目运算符需要先分别访问语法树中 lhs 和 rhs 获得表达式左右值指针，再进行零扩展和类型转换后，根据 node.op 类型生成相应的ixxx/fxxx计算 IR，特别的是，针对PLUS运算符需要考虑指针计算的情形，生成的是gep。单目运算符只有遇到MINUS时才需要生成相应的isub/fsub指令。

函数

函数定义 通过从语法树的FuncDef类中获取函数的返回类型和参数列表，为参数预先分配空间并进行初始化,通过调用accept函数,建立函数体。
返回值 返回语句的创建在函数声明的最后实现。在在函数声明时,预先创立返回语句的基本块,并预分配返回值的空间。当遇到return语句时在返回值处理完毕后，将其存入预先分配的空间中，并跳转到返回语句的基本块。
函数调用 首先在scope中找到需要调用的函数,检查传入参数的类型和函数的参数类型是否匹配,若不匹配则进行类型转换。

语句

if 首先查看是否存在else 语句，以创建对于数量的基本块。随后visit 条件表达式，将获取的值转为需要的类型，以创建跳转语句。在访问if_stmt和else_stmt后,需建立到if语句后的跳转指令。
Assign 分别访问语法树节点中的target和value后，获得左值和右值对应的Ptr<Value>,判断是否需要零扩展zext和类型转换sitofp/fptosi后，生成storeIR。
While 创建三个 bb 块 label：cond_bb表示循环条件判断域，true_bb表示条件为真时循环体执行域，after_bb表示循环语句结束后跳转至下一条语句，与条件表达式同样需要根据真假逻辑创建相应的icmp_ne/fcmp_ne、set_insert_point和cond_brIR 指令。特别的是，循环体中可能会遇到break或continue语句，故需要分别维护两个全局栈break_point和continue_point记录当前可能的下个跳转地址。在 while 循环中合适位置更新维护这两个栈中的内容。

实验难点及解决方案

函数返回

原先实现是在每一个return语句处均建立一个返回语句，但是对于void类型返回值的函数和，某些不含return语句的函数的情况不好处理，后选择在函数声明时统一创建返回语句，且对于返回值以 0 作为默认值。

赋值

对于赋值语句,需要获取赋值的地址。本来通过在scope中找所需的变量,后考选择从对lval的visit函数中将地址直接引出。

数组

llvm设计的数组类型较为特殊,其在原数组外套了一层指针结构,以记录数组的长度等信息。当时忽视了这一点随后在 debug 的过程中一度认为其数组实现出现问题而要修改源代码。

短路

对于and和or运算需要考虑短路，即A and B当A为假时不对B进行计算。为每一个and和or单独开设两个基本块,对表达式的真与假做标记。以A and B为例,若A为假则直接跳转到false基本块,设置表达式为假后跳转到后续执行指令;若为真则继续判断B,根据B判断跳转到true还是false。

实验总结

本次实验即为实现编译器的中间代码生成过程，让我们更深入的理解编译器的操作和其语法分析,并训练了我们在访问者模式下的面向对象编程能力。在经过近两周的折磨后，让我对llvm的实现有了一个较深的理解。在编写和debug过程中遇到了不少问题,但最后在我们的尝试和沟通下得以解决。迫于时间原因,基本要求已经实现,但是一些操作冗余,基本块仅包含跳转语句等地方还未进行优化。

9.2 KiB Raw Permalink Blame History Unescape Escape