我使用这个（见下文）算法（从起飞想法此答案）来生成代码树。我的目标是x86 arch，现在我需要处理使用寄存器eax / ebx作为参数的mul / div指令。
我的问题是：
如何修改此设置以加载特定指令的操作数以加载到固定寄存器？例如，对于mul指令加载，左子树和右子树都在eax和ebx寄存器上。我当前的实现是：通过当前节点开始作为参数求值，如果它是MUL或DIV设置reg为R0或R1根据树的一方，分别是LEFT或RIGHT。如果reg为is in_use，则推入reg堆栈并将其标记为开始可用（尚未实施）。当前实现无效，因为它确实assert(r1 != r2)在emit_load()函数中声明了（这意味着作为参数传递的两个寄存器都等于r1 = REG_R0和r2 = REG_R0）
void gen(AST *ast, RegSet in_use, AST *root) {
if(ast->left != 0 && ast->right != 0) {
Reg spill = NoRegister; /* no spill yet */
AST *do1st, *do2nd; /* what order to generate children */
if (ast->left->n >= ast->right->n) {
do1st = ast->left;
do2nd = ast->right;
} else {
do1st = ast->right;
do2nd = ast->left; }
gen(do1st, in_use);
in_use |= 1 << do1st->reg;
if (all_used(in_use)) {
spill = pick_register_other_than(do1st->reg);
in_use &= ~(1 << spill);
emit_operation(PUSH, spill);
}
gen(do2nd, in_use);
ast->reg = ast->left->reg
emit_operation(ast->type, ast->left->reg, ast->right->reg);
if (spill != NoRegister)
emit_operation(POP, spill);
} else if(ast.type == Type_id || ast.type == Type_number) {
if(node->type == MUL || node->type == DIV) {
REG reg;
if(node_side == ASTSIDE_LEFT) reg = REG_R0;
if(node_side == ASTSIDE_RIGHT) reg = REG_R1;
if(is_reg_in_use(in_use, reg)) {
emit_operation(PUSH, reg);
}
} else {
ast->reg = pick_unused_register(in_use);
emit_load(ast);
}
} else {
print("gen() error");
// error
}
}
// ershov numbers
void label(AST ast) {
if(ast == null)
return;
label(ast.left);
label(ast.right);
if(ast.type == Type_id || ast.type == Type_number)
ast.n = 1;
// ast has two childrens
else if(ast.left not null && ast.right not null) {
int l = ast.left.n;
int r = ast.right.n;
if(l == r)
ast.n = 1 + l;
else
ast.n = max(1, l, r);
}
// ast has one child
else if(ast.left not null && ast.right is null)
ast.n = ast.left.n;
else
print("label() error!");
}
使用这样的一遍代码生成器，您的选择就受到限制。首先生成3地址代码或其他线性中间表示，然后担心寄存器定向（这是您要完成的工作的名称），这可能会更简单。
尽管如此，您想做的事还是有可能的。需要注意的是，您不会获得非常高质量的代码。为了使它更好，您必须丢弃此生成器并重新开始。
您遇到的主要问题是Sethi-Ulman标记不是代码生成算法。这只是选择代码生成顺序的一种方式。您仍然缺少重要的想法。
有了这些，请注意以下几点：
推动并弹出寄存器以暂时保存它们会使生活变得困难。原因很明显。您只能按LIFO顺序访问保存的值。
如果您在堆栈帧中分配可能是寄存器或存储器位置的“位置”，事情就会变得更加容易。存储器位置有效地扩展了寄存器文件，使其必要时更大。稍微复杂一点是，您需要为每个函数记住该函数的堆栈框架中的位置需要多少个单词，然后回补函数序言以分配该数字。
接下来，实现一个全局操作数堆栈，其中每个堆栈元素都是一个PLACE。PLACE是一个描述符，用于说明已经由已发出的代码计算出的操作数的位置：寄存器或内存以及如何访问它。（为获得更好的代码，您还可以允许PLACE成为用户变量和/或立即数，但是下面描述的PLACE分配器永远不会返回这样的PLACE。此外，允许的PLACE种类越多，则必须使用的情况越多由代码发射器处理，也将在下面进行说明。）
一般原则是“懒惰”。我们等待的时间越晚，发出代码的机会就越多。有了更多的信息，就有可能生成更好的代码。PLACE堆栈可以很好地完成此任务。
代码生成器不变是它发出的代码将结果PLACE留在操作数堆栈的顶部。
您还将需要一个PLACE分配器。这样可以跟踪寄存器和正在使用的存储字。如果所有寄存器和当前字都已经忙，它将分配新的存储字。
PLACE分配器中的寄存器可以具有三种可能的状态：FREE，BUSY，PINNED。需要一个PINNED寄存器来保存一个不能移动的值。（我们将使用它来满足具有特定寄存器要求的指令。）BUSY寄存器是一个必需的寄存器，可以将值按要求移动到其他PLACE。免费寄存器不具有任何价值。
PLACE分配器中的内存是空闲或繁忙。
PLACE分配器至少需要以下入口点：
allocate_register 选择一个空闲寄存器R，使其变为繁忙，然后返回R。如果没有可用的空闲寄存器，则分配一个空闲存储字P，将一个繁忙寄存器R的内容移到那里，然后返回R。pin_register(R)如下所示：如果R为PINNED，则引发致命错误。如果R忙，则获得一个FREE PLACE P（寄存器或存储字），发出将R的内容移至P的代码，标记R PINNED并返回。如果R是免费的，则将其标记为PINNED并返回。请注意，当固定或分配寄存器R需要移动其内容时，分配器必须更新操作数堆栈中的相应元素。必须将原来的R更改为P。为此，分配器维护一个映射，将每个寄存器带到描述它的操作数堆栈PLACE中。
完成所有这些之后，用于二进制操作的代码生成器将很简单：
gen_code_for(ast_node) {
if (ast_node->left_first) {
gen_code_for(ast_node->left_operand)
gen_code_for(ast_node->right_operand)
} else {
gen_code_for(ast_node->right_operand)
gen_code_for(ast_node->left_operand)
swap_stack_top_2() // get stack top 2 elements in correct order
}
emit_code_for(ast_node)
}
代码发射器将像这样工作：
emit_code_for(ast_node) {
switch (ast_node->kind) {
case DIV: // An operation that needs specific registers
pin_register(EAX) // Might generate some code to make EAX available
pin_register(EDX) // Might generate some code to make EDX available
emit_instruction(XOR, EDX, EDX) // clear EDX
emit_instruction(MOV, EAX, stack(1)) // lhs to EAX
emit_instruction(DIV, stack(0)) // divide by rhs operand
pop(2) // remove 2 elements and free their PLACES
free_place(EDX) // EDX not needed any more.
mark_busy(EAX) // EAX now only busy, not pinned.
push(EAX) // Push result on operand stack
break;
case ADD: // An operation that needs no specific register.
PLACE result = emit_instruction(ADD, stack(1), stack(0))
pop(2)
push(result)
break;
... and so on
}
}
最后，指令发射器必须知道当其操作数具有处理器指令集不支持的类型组合时该怎么做。例如，可能必须将内存PLACE加载到寄存器中。
emit_instruction(op, lhs, [optional] rhs) {
switch (op) {
case DIV:
assert(RAX->state == PINNED && RDX->state == PINNED)
print_instruction(DIV, lhs)
return RAX;
case ADD:
if (lhs->kind == REGISTER) {
print_instruction(ADD, lhs, rhs)
return lhs
}
if (rhs->kind == REGISTER) {
print_instruction(ADD, rhs, lhs)
return rhs
}
// Both operands are MEMORY
R = allocate_register // Get a register; might emit some code.
print_instruction(MOV, R, lhs)
print_instruction(ADD, R, rhs)
return R
... and so on ...
我一定要讲很多细节。问不清楚的地方。
OP解决的问题
您是对的，我打算stack(n)成为n操作数堆栈顶部的PLACE 。
语法树的叶子只需将PLACE推入操作数堆栈上的计算值即可满足不变量。
如上所述，您可以为这些操作数创建特殊类型的PLACE（用户标记的内存位置和/或立即值），或者-更简单（如您所建议的那样）-分配一个寄存器并发出将值加载到该寄存器中的代码，然后将寄存器的PLACE推入堆栈。比较简单的方法将导致不必要的加载指令，并消耗比所需更多的寄存器。例如，x = x + 1将生成类似以下的代码：
mov esi, [ebp + x]
mov edi, 1
add esi, edi
mov [ebp + x], esi
在这里，我x用来表示变量的基本指针偏移量。
使用用于变量和文字的PLACE，您可以轻松获得：
mov esi, [ebp + x]
add esi, 1
mov [ebp + x], esi
通过使代码生成器知道PLACE分配作业在何处放置答案，您可以获得
add [ebp + x], 1
或同等
inc [bp + x]
通过PLACE *target在代码生成器中添加一个参数来实现此目的，该参数描述了计算表达式值的最终值需要存放的位置。如果当前不编译表达式，则将其设置为NULL。注意，使用target，代码生成器不变：除非 target设置，否则表达式结果的PLACE位于操作数堆栈的顶部。在那种情况下，它已经被计算到目标的PLACE中。
这将如何进行x = x + 1？该过程中的ASSIGNMENT情况emit_code_for将target作为x递归调用自身进行编译时的PLACE x + 1。这将责任下放，以将计算的值保存到正确的存储位置，即x。ow调用的emit_code_for情况以递归的方式评估操作数并进入堆栈。由于我们具有用于用户变量和立即值的PLACE，因此这些变量被压入堆栈，而根本不生成任何代码。现在，发射器必须足够聪明，才能知道，如果它在堆栈上看到一个内存位置L和一个字面常量C，并且目标也是L，那么它就可以发出，并且完成了。ADDemit_code_forx1ADDadd L, C
请记住，每次通过为代码生成器提供更多信息以使其做出这样的决策而使其“更智能”时，由于要处理的情况更多，代码生成器将变得越来越长，越来越复杂。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句