lab3-1实验报告

小组成员 姓名 学号
PB17000002 古宜民（队长）
PB15081586 苏文治
PB16001837 朱凡

实验要求

根据C-minus语义，修改src/cminusc/cminus_builder.cpp，在助教提供的框架上正确实现一个C-minus语言的IR生成器，将前序实验中得到的语法树翻译到正确的LLVM IR。

实验难点

如何全局地传递表达式的值

存在多个返回语句和if或while中出现返回语句的处理

if或while需要在已经生成的代码后补充代码的处理

var可被存储或取值，需要区分

数组的处理，GEP的使用

实验设计

1. 如何设计全局变量

BasicBlock* curr_block;

用于记住当前正在插入代码的BasicBlock，在if，while等内部有时需要创建新的BasicBlock，但又要在创建后返回原来的BasicBlock插入一些代码，就需要程序记住当前的BasicBlock；

BasicBlock* return_block;

标注函数的返回语句所在BasicBlock，用于实现函数体中出现return时的正确跳转；

Value* return_alloca;

用于存储返回值，便于函数中途遇到return时能够把返回值存放到正确的地方；

Function* curr_func;

用于创建BasicBlock时得到所在函数；

Value* expression;

用于值的全局传递，因为expression的解析和使用在语法树的不同部分，需要一个全局变量进行传递。

bool is_returned,is_returned_record;

标注是否已出现返回语句，用于忽略返回语句后的语句。为了在出现嵌套compound_stmt等情况下让if或while得知其中是否有return，并且避免因为记录了return而影响后续compound_stmt的分析，这里使用了两个全局变量，is_returned主要用于compound_stmt正常分析流程的控制，而is_returned_record为一个记录，保存了特定时刻is_returned的值，供if和while使用；

int label_cnt;

用于标签号管理，让生成的IR更易于阅读;

var_op curr_op;

用于确定当前对var作存储还是取值；

2. 如何解决实验难点中的问题

值传递的问题

因为在遍历语法树时，不同节点之间无法进行直接的值传递，如果需要父节点获得子节点的值（或者相反），就需要通过一个全局变量在子节点完成分析后将得到的值存储，调用分析子节点的方法后，父节点可以在这个全局变量中得到子节点的值。比如，在additive_expression中的a+b，需要先对a和b分析，结束后才能建立那条完成加法的CreateAdd，于是a和b的结果就需要先进行存储，而后在父节点中通过expression全局变量获得。其他信息，比如当前在进行指令插入的BasicBlock和Function，当前的返回值，都是用于完成类似功能的。

返回的处理

如果不进行特殊处理，在连续出现return语句，或者if、while中最后一条是return语句，生产的IR中会出现连续的ret，或者ret后紧跟br指令。开始我们认为这种格式没有问题，在运行出错后才发现原来LLVM IR会将ret，br等指令认为是BasicBlock的结束，从而开始一个新的（未显式标号）的BasicBlock，这将导致后面的代码和变量编号错误。于是必须使用方法发现代码中的return语句，并进行处理。我们的方法是使用两个全局变量（is_returned, is_returned_record）记录在if，else，while等内部有没有return语句，如果有，就不予添加正常在if等结束后该有的跳转br指令。同时在一个compound_stmt内部，如果发现了return_stmt，就不予分析后面可能还有的代码。于是这两处处理解决了return的问题。

if和while代码“回填”的问题

比如在if中，条件跳转指令在if的最前面，而该跳转指令的两个目标BasicBlock还没有生成， 就必须等待两个BasicBlock生成完成后，再回头补上这个CondBr。同样，在if和else结束后要补充一条到整个if结构后面的无条件跳转，而这条跳转也必须在if结构生成结束后补充添加。这种非线性的顺序给程序带来了一定的困难。因为在编写这部分时，我们尚不知道BasicBlock的添加可以指定位置，就只好按 if标签-if体-else标签-else体-结束标签-回填 的顺序进行分析。而回填时，如果直接SetInsertPoint到if标签和else标签后并不能成功，因为在if体内很可能生成了新的标签，而补充的br指令应该在if体整体的最后，而不只是if标签的最后。引入全局变量curr_block的主要目的就是解决这个问题：在if体分析结束后还能够获得最后一个BasicBlock，也就是br该被插入的地方。当然，这里很可能有更加优雅的解决方法。

变量存取的设计

由于在赋值操作中，左值和右值都是expression，并没有在语法树中区分，但赋值中明显对左右值的操作是不同的：右值需要被读或计算，而左值需要获得其存储位置并进行存操作。于是需要一个全局变量记录当前操作——curr_op。

类型转换的问题

由于Cminus允许进行如if(a),a=b<c等比较值（i1）与整数值（i32）混用，在编译时需要对类型不同的地方进行转换。我们使用的方法是i32到i1的转换使用一个ICmp对该i32和0比较。而i1到i32用的是CreateIntCast方法，在IR里就是zext指令。

数组的处理

数组的处理是本项目中遇到的最大的困难。

对于普通的数组，在函数内部作为局部变量定义，其使用（以下假设其长度为100）alloca [100 x i32]分配，类型为[100 x i32]*，可以认为是指向一个结构体的指针（这个结构体就是[100 x i32]），即指向一个100个int32型的数据块的指针。注意并不是简单的指向int的32指针i32*。为了进行寻址，就要先使用getelementptr进行地址计算，然后用load从计算好的地址处进行取值。

而在getelementptr指令中，经过反复查找文档发现，其第一个参数为寻址第二个参数的类型，也就是第二个指针参数所指的类型（[100 x i32]）。第二个参数为结构体指针的类型。第三个参数是用于寻址结构体的。第四个参数是用于结构体内部的寻址，在本例子中就是100个int32内部的寻址，也就是直观理解的“数组寻址”应该用的数组下标参数。由于被[100 x i32]*指向的只有一个结构体，而不是一个结构体数组（像LLVM文档The Often Misunderstood GEP Instruction中的例子那样），第三个参数恒等于0。

那么在我们的程序中怎么由从符号表中得到的[100 x i32]*类型变为第一个参数需要的[100 x i32]呢？开始我们看到数组分配时的类型是AllocaInst，这个类型有一个方法GetAllocatedType()能够实现这个功能。但从符号表中读出的是父类型Value，Value并没有这个方法，于是就需要用dyn_cast从Value*转化成AllocaInst*。但后来这种并不好的方法导致了诸多问题。而后才发现Value类型可以直接用->getType()->getPointerElementType()简单的实现同样的功能，不需要类型转换了，也解决了问题。

对于数组的其他更复杂的情况，处理反而简单了一些。如果数组不是局部定义，而是全局变量或者从函数参数传进来，那么它就不是[100 x i32]*类的指针了，而是简单的int32型指针i32*。进行GEP的时候也就简单了很多，只需要使用三个参数的GEP，直接获得目标地址，再store或load即可。全局变量数组虽然类型是GlobalVariable*，但其实就是指针，所以可以和参数数组一并处理。

如何判断数组是哪一种情况？目前的方法是判断，如果是i32*，就是指针引用，如果不是，就是局部定义数组的复杂情况。

还需要注意的就是数组如果作为参数传递给函数，就必须从[100 x i32]*转化为i32*（第一个数组元素的地址），而参考clang生成的IR后，发现通过一个两个参数都是0的GEP即可实现。

进一步完善？

项目中还有一些地方有完善空间，比如：

错误处理，目前分析到语义错误的Cminus程序时可能会直接崩溃，而不会给出友好的错误提示，这是可以完善的一点；

代码中有一些冗余的指令，比如说在LOAD、STORE处的处理时不同的case中可以提出case外的内容写了两遍。

[Notice 2020.4] This scored 98/100 in tests: not a bad result but there are bugs!

实验总结

我们的收获和教训：

收获：我们获得了编写较大项目的经验，以及团队合作编写代码的经验。

教训：阅读文档。我们在实验中遇到了一些难以解决的问题，或是中途使用了一些有些“野”的解决方法，但其实最后发现更好地、现成的解决方法就在LLVM的库函数里，而我们没有找到。

同时，在处理数组时，我们进行了大量的搜索，但无论是官方文档，还是stackoverflow，都没能找到一个CreateGEP寻址数组的具体例子。于是我们只能通过clang生成的IR和LLVM函数API“盲猜”函数的用法，花了很长时间才有所突破。

实验反馈

对本次实验的建议（可选 不会评分）