编译器实现之旅——第十五章 函数调用的代码生成器分派函数的实现
在前面几个章节的旅程中，我们实现了一些各有特点的代码生成器分派函数，而在这一章的旅程中，我们将迎来整个代码生成器，乃至整个编译器实现之旅的重头戏：函数调用的实现。现在，就让我们开始吧。
1. 函数调用概观
函数调用是一个复杂的过程，从代码生成器层面看，其涉及到符号表以及多个与之相关的分派函数，此外，函数调用还需要在稍后经由链接器组件进行处理；而从虚拟机层面看，函数调用涉及到了虚拟机的所有寄存器和许多特殊的指令。由此可见，函数调用这一分派函数所涉及到的面之广，是其他分派函数所不能达到的。下面，让我们首先来看看一次函数调用的代码生成，究竟需要经历哪些步骤：
- 局部变量压栈
- 实参压栈
- BP寄存器准备
- IP寄存器准备
- 函数调用跳转
- 实参与局部变量退栈
我们将在下文中逐条的讨论这些步骤的含义与实现。
接下来，我们将上一章中绘制的栈内存结构图中，与函数调用相关的部分展示如下：
+-------+ ... +-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+ ...
| 索引值 | ... | N - 9 | N - 8 | N - 7 | N - 6 | N - 5 | N - 4 | N - 3 | N - 2 | N - 1 | N | N + 1 | ...
+-------+ ... +-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+ ...
| 值 | ... | ? | ? | ? | ? | N - 8 | ? | ? | ? | ? | ? | IP | ...
+-------+ ... +-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+-------+ ...
^ ^ ^ ^ ^ ^ ^ ^ ^ ^
| | | | | | | | | |
f e[0] e[1] e[2] e d c b a BP
也许你早已发现：由于BP在栈中的位置在所有的参数之后，故我们压栈的顺序应当与符号表中变量的编号完全相反。此外，还记得我们在生成符号表的时候提到：一定要先为形参编号，再为局部变量编号吗？这样做，就使得符号表中的变量编号具有了一个非常重要的性质：任何局部变量的编号一定大于任何形参的编号。在此基础上，通过进一步的分析与整理，我们可以得到以下要点：
- 我们应当按照符号表中的变量编号从大到小的顺序进行压栈
- 实参信息存在于root的第二子节点（如果有）中
- 我们可以用符号表中所有变量的数量，减去root的第二子节点（如果有）的所有子节点的数量，即实参的数量，得到局部变量的数量
- 在对局部变量进行压栈时，我们需要判定当前这个局部变量是不是数组。如果是，则我们应首先进行数组长度次压栈，为数组内容留出空间；然后，我们应计算数组的第一个元素在栈中的索引值，并将其压栈。怎么计算呢？不难发现，其值等于：SP - (数组长度 - 1)
- 实参不可能是一个数组
上述结论将作为我们实现函数调用的理论基础。
2. 内置函数的实现
在讨论函数调用的各个步骤之前，我们首先来看看内置函数的实现。CMM有两个内置函数：input和output。input函数没有参数，其用于读入一个数字；而output的参数是一个表达式，其用于输出这个表达式的结果。这两个内置函数，分别由INPUT和OUTPUT指令提供支持。所以，当我们发现函数名为input时，我们直接生成一条INPUT指令即可；而当我们发现函数名为output时，我们就先为其仅有的一个参数生成代码，再追加一条OUTPUT指令即可。请看：
vector<string> CodeGenerator::__generateCallCode(AST *root) const
{
if (root->subList[0]->tokenStr == "input")
{
return {"INPUT"};
}
else if (root->subList[0]->tokenStr == "output")
{
vector<string> codeList = __generateExprCode(root->subList[1]->subList[0]);
codeList.push_back("OUTPUT");
return codeList;
}
// 未完待续...
3. 局部变量压栈
作为函数调用的第一步，我们首先需要进行的便是局部变量压栈了。根据第一节中得到的第三条要点，我们可以从符号表中分离出所有的局部变量信息。请看：
// ...接上文中代码
vector<string> codeList;
vector<pair<string, pair<int, int>>> pairList(
__symbolTable.at(root->subList[0]->tokenStr).size());
for (auto &mapPair: __symbolTable.at(root->subList[0]->tokenStr))
{
pairList[pairList.size() - mapPair.second.first - 1] = mapPair;
}
int topIdx = pairList.size() - (root->subList.size() == 2 ?
root->subList[1]->subList.size() : 0);
// 未完待续...
上述代码中，我们首先将符号表中各个变量的信息按变量编号从大到小排列，然后通过减法得到了topIdx，这个变量就代表了局部变量在列表中的最大索引值。
接下来，我们进行局部变量压栈。请看：
// ...接上文中代码
for (int idx = 0; idx < topIdx; idx++)
{
if (pairList[idx].second.second)
{
for (int _ = 0; _ < pairList[idx].second.second; _++)
{
codeList.push_back("PUSH");
}
codeList.push_back("PUSHSP");
codeList.push_back("LDC " + to_string(pairList[idx].second.second - 1));
codeList.push_back("SUB");
codeList.push_back("POP");
codeList.push_back("PUSH");
}
else
{
codeList.push_back("PUSH");
}
}
// 未完待续...
上述代码中，我们按照已经排列好的顺序，依次为每个局部变量压栈。通过判断当前变量的数组长度，我们可以获知当前变量是不是数组。如果不是，事情就好办了：直接生成一条PUSH指令即可；如果是，则我们就需要首先生成数组长度条PUSH指令，为数组内容留好空间；然后开始计算数组的第一个元素在栈中的索引值。根据公式：SP - (数组长度 - 1)，我们首先执行PUSHSP指令，将SP压入栈顶，作为减法的第一操作数；然后，我们将“数组长度 - 1”装载入AX，作为减法的第二操作数；接下来，我们执行减法，此时，AX中装载的就是我们需要的索引值了；接下来，我们将减法的第一操作数退栈；最后，将AX压栈，完成数组的第一个元素在栈中的索引值的计算与压栈。
4. 实参压栈
相较于局部变量的压栈，实参的压栈就简单许多了，这要归功于“实参不可能是一个数组”这一性质。由于实参信息存在于root的第二子节点（如果有）中，所以我们可以将这部分的代码生成委托给ArgList节点的分派函数进行。请看：
// ...接上文中代码
if (root->subList.size() == 2)
{
vector<string> argListCodeList = __generateArgListCode(root->subList[1]);
codeList.insert(codeList.end(), argListCodeList.begin(), argListCodeList.end());
}
// 未完待续...
那么，__generateArgListCode函数又是怎么实现的呢？请看：
vector<string> CodeGenerator::__generateArgListCode(AST *root) const
{
vector<string> codeList;
for (int idx = root->subList.size() - 1; idx >= 0; idx--)
{
vector<string> exprCodeList = __generateExprCode(root->subList[idx]);
codeList.insert(codeList.end(), exprCodeList.begin(), exprCodeList.end());
codeList.push_back("PUSH");
}
return codeList;
}
ArgList节点含有一至多个Expr子节点，我们要做的便是倒序遍历这些子节点，生成当前子节点的代码；由于Expr节点的代码最终一定会将结果装载入AX中，故我们直接再追加一条PUSH指令即可。
5. BP寄存器准备
至此，我们已经将函数运行时所需要的所有变量压栈，接下来，我们就需要为LD指令的基石：BP做准备了。说的很复杂的样子，实际上这一动作只需要一条SAVSP指令即可。但是，有一件非常重要的事情我们不能忘记：BP的值在SAVSP的时候并不是无意义，可以随意覆盖的，而是作为外部函数，如main函数的BP存在的。所以，我们需要在执行SAVSP指令之前，先通过PUSHBP指令将旧的BP压栈，并在函数调用结束后，通过POPBP指令恢复旧的BP。请看：
// ...接上文中代码
codeList.push_back("PUSHBP");
codeList.push_back("SAVSP");
// 未完待续...
6. IP寄存器准备与函数调用
终于可以进行函数调用了！但请先别着急，我们需要思考这样一个问题：不难想到，函数调用本质上就是一条JMP指令，但不同于普通的JMP指令，函数调用是一个“回旋镖”，在调用结束后，IP是需要回来的。这怎么实现？上一节中的“PUSHBP-POPBP”方案带给我们灵感：我们可以通过“PUSHIP-POPIP”方案实现这样的“回旋镖”。请看：
// ...接上文中代码
codeList.push_back("PUSHIP");
// 未完待续...
PUSHIP以后，我们就放心了。我们知道：在函数调用结束的那个时候，不管我们身处何方，都可以通过POPIP指令回到这里。所以，现在就可以进行函数调用了。但是，我们立刻又遇到了一个新的问题：
我们应该去哪？
我们无法回答这个问题。我们现在充其量只知道我们自己现在在哪，调用哪个函数，但是并不知道我们应该去哪。那么，什么时候才能知道去哪呢？不难想到：当所有的代码都呈现在我们面前的时候，我们就知道去哪了。这正是链接器所具有的功能。所以，我们在这里需要暂且生成一条CALL伪指令，并在稍后通过链接器的广阔视野，将这条伪指令变为一条真正的JMP指令。请看：
// ...接上文中代码
codeList.push_back("CALL " + root->subList[0]->tokenStr);
// 未完待续...
可见，我们在这里仅仅生成了一条“CALL 函数名”伪指令。
在CALL结束后，我们将通过POPIP指令，使得IP重新指向CALL之后一条指令的位置。此时，我们不要忘了：旧的BP还在栈中呢。所以，我们需要立即通过一条POPBP指令，将静候多时的旧的BP重新请出来。请看：
// ...接上文中代码
codeList.push_back("POPBP");
// 未完待续...
在这一节的末尾，我们需要补充说明一个问题：虚拟机中POPIP指令的实现。不难发现：PUSHIP和CALL指令在我们生成的代码中一定会一前一后同时出现，此时，如果虚拟机将POPIP指令实现为“IP = SS.back()”，并于稍后发生“IP++”的话，IP将在函数返回后又错误的指向了CALL指令，这显然不是我们希望看到的。所以，虚拟机实际上将POPIP指令实现成了“IP = SS.back() + 1”，这样，在函数返回后，IP就将越过随后的CALL指令，从而正确的指向CALL指令后面的POPBP指令了。
7. 实参与局部变量退栈
在函数调用结束后，我们需要将先前为了函数调用而进行的压栈全部退栈。那么，我们究竟需要退栈多少次呢？稍加思考，不难得到以下结论：
- 对于符号表中的每个变量，不管是不是数组，都需要退栈一次
- 如果一个变量是数组，则还应额外退栈数组长度次
由此，我们可以得到以下实现：
// ...接上文中代码
for (auto &mapPair: __symbolTable.at(root->subList[0]->tokenStr))
{
codeList.push_back("POP");
for (int _ = 0; _ < mapPair.second.second; _++)
{
codeList.push_back("POP");
}
}
// 终于不是未完待续了！
return codeList;
}
至此，函数调用的代码生成器分派函数的实现就全部完成了。但是，我们仍有三个遗留问题尚待解决：
- 我们需要实现一个链接器，以将所有的CALL伪指令转变为一条真正的JMP指令
- 我们需要为全局变量压栈
- main函数需要在程序启动时被自动调用
这些问题，我们都将在下一章的旅程中进行讨论。请看下一章：《代码装载、链接器、全局变量与main函数》。
原文：https://www.cnblogs.com/yingyulou/p/14416607.html