具有固定/预分配寄存器的表达式的代码生成

我正在使用这个(见下文)算法(从这个答案的想法)到树的代码生成.我的目标是x86 arch,现在我需要处理使用寄存器eax/ebx作为参数的mul/div指令.

我的问题是:

如何修改它以加载某个指令的操作数以加载到固定寄存器？比如,对于mul指令加载左右子树eax和ebx寄存器.我当前的实现是:传递当前节点开始评估为参数,如果它是MUL或DIV设置reg为R0或R1根据树的一侧,如果它LEFT或RIGHT分别.如果reg是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!");
}

Gene.. 8

使用像这样的单程代码生成器,您的选择是有限的.首先生成3地址代码或其他线性中间表示可能更简单,然后担心寄存器定位(这是您要完成的内容的名称).

尽管如此,你想做的事情是可能的.需要注意的是,您将无法获得高质量的代码.为了让它更好,你将不得不扔掉这台发电机并重新开始.

您遇到的主要问题是Sethi-Ulman标签不是代码生成算法.这只是选择代码生成顺序的一种方式.你仍然缺少重要的想法.

有了这一切,有些观点:

推送和弹出寄存器以暂时保存它们会使生活变得困难.原因很明显.您只能以LIFO顺序访问已保存的值.

如果您在堆栈框架中分配可能是寄存器或内存位置的"位置",事情会变得更容易.存储器位置有效地扩展了寄存器文件,使其尽可能大.稍微复杂的是,您需要记住每个函数对于该函数的堆栈帧中的位置需要多少个字,并且返回函数前导码以分配该数字.

接下来,实现一个全局操作数堆栈,其中每个堆栈元素都是一个PLACE.PLACE是一个描述符,用于说明已经发出的代码计算出的操作数的位置:寄存器或内存以及如何访问它.(为了更好的代码,您还可以允许PLACE成为用户变量和/或立即值,但是下面描述的PLACE分配器永远不会返回这样的PLACE.此外,您允许的PLACE类型越多,则必须包含的内容越多.由代码发射器处理,也在下面描述.)

一般原则是"懒惰".稍后我们可以等待发出代码,可用的信息就越多.有了更多信息,就可以生成更好的代码.一堆PLACE在完成这项工作方面做得相当不错.

代码生成器不变的是它发出的代码将结果PLACE保留在操作数堆栈的顶部.

您还需要一个PLACE分配器.这将跟踪寄存器和正在使用的存储器字.如果所有寄存器和当前字已经忙,它会分配新的存储字.

PLACE分配器中的寄存器可以有三种可能的状态:FREE,BUSY,PINNED.PINNED寄存器是保存无法移动的值所必需的寄存器.(我们将其用于具有特定寄存器要求的指令.)BUSY寄存器是可以根据需要移动到不同PLACE的值所需的寄存器.免费注册没有价值.

PLACE分配器中的内存是FREE或BUSY.

PLACE分配器至少需要这些入口点:

allocate_register 选择一个FREE寄存器R,使其忙,然后返回R.如果没有FREE寄存器,则分配一个空闲的存储字P,在那里移动BUSY寄存器R的内容,然后返回R.

pin_register(R)执行如下操作:如果R是PINNED,则引发致命错误.如果R为BUSY,则获得一个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作为PLACE,以便x它以递归方式调用自身进行编译x + 1.这将向下委托将计算值转移到正确的内存位置,即x.ow 的emit_code_for情况以递归方式调用以评估操作数并进入堆栈.由于我们有用于用户变量和立即值的PLACE,因此它们被压入堆栈,而根本不生成任何代码.该发射器现在必须足够聪明,知道如果看到一个内存位置L和堆栈上的常量C和目标也是L,那么它可以发出,并且它的完成.ADDemit_code_forx1ADDadd L, C

请记住,每次通过为代码生成器提供更多信息来使代码生成器"更智能"时,它将变得更长,更复杂,因为有更多的情况需要处理.