complier-lab5

This lab comes from SE3355 *Compilers* lab5, which requires me to implement a complete runnable tiger compiler.

​ 致谢:Lab5的完成离不开Girafboy学长仓库所提供的参考和思路,为了避免有抄袭之嫌,我将重新以我的思路阐述清楚我的代码。

​ 首先明确,我们这个Lab5的目标是把做完escape analysis的AST转化为tree language(middle IR),再转化为assem(lower IR)。正如院长所说,前4个Lab其实是把代码文本转化成了AST,只生成了一个IR,但是我们需要在Lab5一下子完成两个IR的转换和生成,并且我们生成tree language后,其实非常不好Debug,因为有各种各样的嵌套语句,也没有解释器来解析tree language,我们必须等到生成了assem后才能够被汇编解释器所解释执行。

Part1 AST翻译成Tree Language

​ 前半部分是根据AST翻译成tree language。这部分相对比较简单,但是一件很麻烦的事情就是translation和Lab4的semantic analysis是非常紧密地intertwine在一起的,如果我们希望在Translate中调用SemAnalyze,会导致大量的代码重构,基本上是一整个Lab4的工作量加上额外的Debug时间,并且还涉及到一个非常trivial,还是很麻烦的点:

1
2
3
4
5
type::Ty *SemAnalyze(env::VEnvPtr venv, env::TEnvPtr tenv, int labelcount,
err::ErrorMsg *errormsg) override;
tr::ExpAndTy *Translate(env::VEnvPtr venv, env::TEnvPtr tenv,
tr::Level *level, temp::Label *label,
err::ErrorMsg *errormsg) override;

​ 我们可以看到,在模板所提供的的接口定义中,Translate函数是没有labelcount参数的,所以它并不能判断某个break语句是否在某些循环语句的里面,我们必须使用SemAnalyze来判定这个错误,所以哪怕我们把语义分析的语句全部迁移到Translate中,还是会有这个问题。为了避免过于丑陋的实现,我在这里纠结了一段时间,不过后来我仔细地查看了Lab5的测试代码(而不是Lab5-part1,Lab5-part1测试脚本没有Semantic analysis阶段,误导了我很久),如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
...
{
// Lab 4: semantic analysis
TigerLog("-------====Semantic analysis=====-----\n");
sem::ProgSem prog_sem(std::move(absyn_tree), std::move(errormsg));
prog_sem.SemAnalyze();
absyn_tree = prog_sem.TransferAbsynTree();
errormsg = prog_sem.TransferErrormsg();
}
{
// Lab 5: escape analysis
TigerLog("-------====Escape analysis=====-----\n");
esc::EscFinder esc_finder(std::move(absyn_tree));
esc_finder.FindEscape();
absyn_tree = esc_finder.TransferAbsynTree();
}
{
// Lab 5: translate IR tree
TigerLog("-------====Translate=====-----\n");
tr::ProgTr prog_tr(std::move(absyn_tree), std::move(errormsg));
prog_tr.Translate();
errormsg = prog_tr.TransferErrormsg();
}
...

​ 所以虽然上课说应该在translation的时候做同时做类型检查的,在Lab中评测中还是没有要求的这么严格。为了避免在Translate阶段又做一遍类型检查,我对AST上的所有节点添加了一个成员type::Ty *type,这样我们做完SemAnalyze后就可以缓存住每个节点的真正类型,然后在Translate阶段使用。这样我们基本上就完成了做Translate的准备动作。

​ Translate接口的定义如下:

1
2
3
tr::ExpAndTy *Translate(env::VEnvPtr venv, env::TEnvPtr tenv,
tr::Level *level, temp::Label *label,
err::ErrorMsg *errormsg) override;

​ 解决掉Translate的关键就是理解level和label参数的含义,理解了自然后面就都好做了。

​ 我们先来看label,涉及到label修改和使用的只有两处:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
tr::ExpAndTy *WhileExp::Translate(env::VEnvPtr venv, env::TEnvPtr tenv,
tr::Level *level, temp::Label *label,
err::ErrorMsg *errormsg) {
tr::Exp *exp = nullptr;
temp::Label *done_label = temp::LabelFactory::NewLabel();
tr::ExpAndTy *check_test = test_->Translate(venv, tenv, level, label, errormsg);
tr::ExpAndTy *check_body = body_->Translate(venv, tenv, level, done_label, errormsg);
......
}

tr::ExpAndTy *BreakExp::Translate(env::VEnvPtr venv, env::TEnvPtr tenv,
tr::Level *level, temp::Label *label,
err::ErrorMsg *errormsg) {
tree::Stm *stm = new tree::JumpStm(new tree::NameExp(label), new std::vector<temp::Label *>({label}));
return new tr::ExpAndTy(new tr::NxExp(stm), type);
}

​ 注意到for循环最终是规约到while的,所以for循环没有使用到label。这样我们就很清楚了,label就是为了让break语句跳出循环使用的。换句话说,就是循环中done:的位置。这样看来,如果我们希望在translation中一遍同时做类型检查,没有labelcount也无伤大雅,我们只需要判断label是不是等于外面传入的默认值即可。

​ 接下来是level函数,它主要的意义就是负责static link。换句话说,如果我们在$level=k_1$的函数体中引用到了$level=k_2<k_1$的变量,那么我们需要通过$k_1-k_2$次static link跳转,找到这个变量所在的frame,并且通过其InReg还是InFrame来获取到具体的值。

​ 所以,level的修改只会出现在FunctionDec的时候:

1
2
3
4
5
6
7
8
9
10
tr::Exp *FunctionDec::Translate(env::VEnvPtr venv, env::TEnvPtr tenv,
tr::Level *level, temp::Label *label,
err::ErrorMsg *errormsg) {
for (FunDec *fundec : functions_->GetList()) {
type::TyList *formaltys = make_formal_tylist(tenv, fundec->params_);
tr::Level *new_level = tr::Level::NewLevel(level, fundec->name_, make_formal_esclist(fundec->params_));
......
tr::ExpAndTy *entry = fundec->body_->Translate(venv, tenv, funentry->level_, funentry->label_, errormsg);
}
}

StaticLink的处理

​ static link的核心逻辑如下所示:

1
2
3
4
5
6
7
8
9
tree::Exp *StaticLink(tr::Level *target, tr::Level *level) {
tree::Exp *staticlink = new tree::TempExp(reg_manager->FramePointer());
while(level != target){
frame::Access *sl = level->frame_->formals.back();
staticlink = sl->ToExp(staticlink);
level = level->parent_;
}
return staticlink;
}

​ 当我们在某个函数中尝试使用一个变量的时候,我们需要在venv中找到此变量的定义层数,并且调用StaticLink函数找到对应的层数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
tr::Exp *TranslateSimpleVar(tr::Access *access, tr::Level *level) {
tree::Exp *real_fp = StaticLink(access->level_, level);
return new tr::ExExp(access->access_->ToExp(real_fp));
}

tr::ExpAndTy *CallExp::Translate(env::VEnvPtr venv, env::TEnvPtr tenv,
tr::Level *level, temp::Label *label,
err::ErrorMsg *errormsg) {
......
auto *list = new tree::ExpList();
for (Exp* args_p:args_->GetList()) {
tr::ExpAndTy *check_arg = args_p->Translate(venv, tenv, level, label, errormsg);
list->Append(check_arg->exp_->UnEx());
}
if(!fun_entry->level_->parent_) {
exp = new tr::ExExp(frame::externalCall(func_->Name(), list));
}
else {
list->Append(StaticLink(fun_entry->level_->parent_, level));
exp = new tr::ExExp(new tree::CallExp(new tree::NameExp(func_), list));
}

return new tr::ExpAndTy(exp, type);
}

​ 注意在CallExp中,如果我们是外部调用的话,不需要添加static link参数,因为外部调用要求不传入static link。

外部调用的处理

1
2
3
tree::Exp *externalCall(std::string s, tree::ExpList *args) {
return new tree::CallExp(new tree::NameExp(temp::LabelFactory::NamedLabel(s)), args);
}

关系运算的翻译

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
case EQ_OP:
case NEQ_OP:
{
tree::CjumpStm *stm;
switch (oper_) {
case EQ_OP:
if (dynamic_cast<type::StringTy *>(leftExpAndTy->ty_) != nullptr) {
auto expList = new tree::ExpList({leftExp, rightExp});
stm = new tree::CjumpStm(tree::RelOp::EQ_OP, frame::externalCall("string_equal", expList), new tree::ConstExp(1), nullptr, nullptr);
}
else
stm = new tree::CjumpStm(tree::RelOp::EQ_OP, leftExp, rightExp, nullptr, nullptr);
break;
case NEQ_OP:
stm = new tree::CjumpStm(tree::RelOp::NE_OP, leftExp, rightExp, nullptr, nullptr);
break;
}
auto trues = new temp::Label*[2];
auto falses = new temp::Label*[2];
trues[0] = stm->true_label_; trues[1] = nullptr;
falses[0] = stm->false_label_; falses[1] = nullptr;
exp = new tr::CxExp(trues, falses, stm);
break;
}

​ 其实就是一个CxExp的构造,我们需要把true_label和false_label的地址传入,以便之后回填。

Part2 Tree Language翻译成Assem

基本数据结构

1
2
3
4
5
6
7
8
9
10
class Frame {
public:
temp::Label *label;
std::list<Access*> formals;
int s_offset;

Frame() {};
Frame(temp::Label *name, std::list<bool> *escapes) : label(name) {}
virtual frame::Access *allocLocal(bool escape) = 0;
};

​ Frame主要是存放函数的名字、寄存器的escape信息、以及栈上的分配offset。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class X64RegManager : public RegManager {
public :
X64RegManager() {
……
caller_saved_regiters = new temp::TempList({rax, rdi, rsi, rdx, rcx, r8, r9, r10, r11});
callee_saved_registers = new temp::TempList({rbx, rbp, r12, r13, r14, r15});
registers = new temp::TempList({rax, rdi, rsi, rdx, rcx, r8, r9, r10, r11, rbx, rbp, r12, r13, r14, r15, fp, rsp});
args_registers = new temp::TempList({rdi, rsi, rdx, rcx, r8, r9});
ret_sink_registers = new temp::TempList({rsp, rax, rbx, rbp, r12, r13, r14, r15});
allregs_noRSP = new temp::TempList({rax, rdi, rsi, rdx, rcx, r8, r9, r10, r11, rbx, rbp, r12, r13, r14, r15, fp});
}

//caller-saved registers
temp::Temp *rax, *rdi, *rsi, *rdx, *rcx, *r8, *r9, *r10, *r11;

//callee-saved registers
temp::Temp *rbx, *rbp, *r12, *r13, *r14, *r15;

temp::Temp *fp;
temp::Temp *rsp;

temp::TempList *caller_saved_regiters, *callee_saved_registers, *registers, *args_registers, *ret_sink_registers, *allregs_noRSP;
};

其他情况

​ 其他情况不再赘述,详见之后公开的Github仓库。

ProcEntryExit1

​ 主要是用来做view shift的,也就是把传入的寄存器参数存放到函数内来看它的位置。强调我的实现只是完成了功能,并没有性能上的考虑。所以,考虑到多个参数的情况,我先把所有传入的寄存器上的值和6个参数以外的栈上的值全部移到临时寄存器中,再重新根据我们的需要安排到栈上,此处的多余move应当是不必要的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
tree::Stm *procEntryExit1(frame::Frame *frame, tree::Stm *stm) {
int num = 1;
tree::Stm *viewshift = new tree::ExpStm(new tree::ConstExp(0));
int total_size = frame->formals.size();
std::vector<temp::Temp *> tempList;
for (frame::Access *formal : frame->formals) {
temp::Temp *reg = temp::TempFactory::NewTemp();
if (num <= 6) {
viewshift = new tree::SeqStm(viewshift, new tree::MoveStm(new tree::TempExp(reg), new tree::TempExp(reg_manager->ARG_nth(num))));
}
else {
viewshift = new tree::SeqStm(viewshift, new tree::MoveStm(new tree::TempExp(reg), tree::NewMemPlus_Const(new tree::TempExp(reg_manager->FramePointer()), -1 * (num - 6) * reg_manager->WordSize())));
}
tempList.push_back(reg);
num++;
}
num = 1;
for (frame::Access *formal : frame->formals) {
viewshift = new tree::SeqStm(viewshift, new tree::MoveStm(formal->ToExp(new tree::TempExp(reg_manager->FramePointer())), new tree::TempExp(tempList[num - 1])));
num++;
}
return new tree::SeqStm(viewshift, stm);
}

ProcEntryExit2

​ ProcEntryExit2是要在翻译完的body instruction后添加一条空指令,告诉我们函数结束的时候哪些寄存器是要被用到的。

1
2
3
4
5
assem::InstrList *procEntryExit2(assem::InstrList *body) {
temp::TempList *returnSink = reg_manager->ReturnSink();
body->Append(new assem::OperInstr("", nullptr, returnSink, nullptr));
return body;
}

ProcEntryExit3

​ ProcEntryExit3生成过程入口处理和出口处理的汇编语言代码,主要是对栈指针的更改,以及设置framesize变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
assem::Proc *procEntryExit3(frame::Frame *frame, assem::InstrList * body) {
static char instr[256];

std::string prolog;
int size = -frame->s_offset - 8;
sprintf(instr, ".set %s_framesize, %d\n", frame->label->Name().c_str(), size);
prolog = std::string(instr);
sprintf(instr, "%s:\n", frame->label->Name().c_str());
prolog.append(std::string(instr));
sprintf(instr, "subq $%d, %%rsp\n", size);
prolog.append(std::string(instr));

sprintf(instr, "addq $%d, %%rsp\n", size);
std::string epilog = std::string(instr);
epilog.append(std::string("retq\n"));
return new assem::Proc(prolog, body, epilog);
}

处理传入大于6个参数的函数调用的情况

首先,我们在tigermain中存在一个返回值-1,所以当我们主程序结束后,会根据这个-1跳转到run函数的循环。

1
2
3
4
5
6
# interpreter.py
def run(self):
pc = self._state_table.get_pc()
while pc >= 0:
self._instructions[pc].execute(self._state_table)
pc = self._state_table.get_pc()

​ 如下图所示,我们目前创造了A的栈帧,并且把传入的参数都根据其是否逃逸放到了对应的寄存器和栈上。

​ 我们假设此时A希望调用函数B,并且需要传入8个参数+1个static link,由于传参寄存器只有6个,所以后两个参数(记作23和45)和static link都需要放在栈上。

​ 注意此时,在%rsp-8处我们需要填充一个空的八字节,然后再依次放入23,45和static link。上图为call(B)前的栈上状态。

​ 在call(B)后,解释器会帮我们填入A的返回地址pc的位置,所以这八个字节是要空出来的,如上图所示。

1
2
3
4
5
6
7
8
9
10
11
12
13
# state_table.py
def call(self, label):
# print(self._reg_table)
label = label.replace('@PLT', '')
if label in self._label_table:
self._func_name_stack.append(self._current_func)
self._current_func = label
rsp = self.load_reg('%rsp') - 8
self.store_mem(rsp, self._pc)
self.store_reg('%rsp', rsp)
self._pc = self._label_table[label]
self._func_temp_stack.append(self._temp_table.copy())
self._temp_table.clear()

​ 如下图所示,这是我们调用call(B)瞬间,还没有对传入参数做寄存器和栈分配时,栈上的情况。

​ 接下来,我们继续对寄存器做escape allocation,最终得到一个完整的B运行时栈。

​ 故代码如下:

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
temp::TempList *ExpList::MunchArgs(assem::InstrList &instr_list, std::string_view fs) {
auto tempList = new temp::TempList();
int num = 1;
int out_formal = exp_list_.size() - 6;

if (out_formal > 0)
instr_list.Append(new assem::OperInstr("subq $" + std::to_string(reg_manager->WordSize()) + ",%rsp",
nullptr, nullptr, nullptr));

for (tree::Exp *exp : exp_list_) {
temp::Temp *arg = exp->Munch(instr_list, fs);
tempList->Append(arg);
if (reg_manager->ARG_nth(num)) {
instr_list.Append(new assem::MoveInstr("movq `s0, `d0", new temp::TempList(reg_manager->ARG_nth(num)), new temp::TempList(arg)));
}
else {
instr_list.Append(new assem::OperInstr("subq $" + std::to_string(reg_manager->WordSize()) + ",%rsp",nullptr, nullptr, nullptr));
instr_list.Append(new assem::MoveInstr("movq `s0, (`d0)", new temp::TempList(reg_manager->StackPointer()), new temp::TempList(arg)));
}
num++;
}
if (out_formal > 0)
instr_list.Append(new assem::OperInstr("addq $" + std::to_string(reg_manager->WordSize() * (out_formal + 1)) + ",%rsp",nullptr, nullptr, nullptr));
return tempList;
}
Author

Kami-code

Posted on

2021-12-14

Updated on

2021-12-26

Licensed under

Comments