给一个AST树 ,我想生成一个类似汇编的语言。 我正在尝试使用Sethi-Ullman算法,但我在算法实现中有一些问题。
我用完寄存器后该怎么办?
目前我做以下事情:
发出一个push REG
,其中REG
是右子树的寄存器,评估左子树,得到一个自由寄存器指定为右子树的寄存器,然后发出POP REG
操作,其中REG
也是右子树的寄存器。
我该如何实现该function以获得免费注册? 目前我正在使用这样的实现而不是基于堆栈:
enum Reg { Reg_r0, Reg_r1 }; Reg regs[] = { Reg_r0, Reg_r1 }; Reg getreg() { static int c; if(c == sizeof(regs) / sizeof(int)) c = 0; return regs[c++]; }
这是一个伪代码(来自C语言)如何从我unsertood(包括label()
函数)实现它
// K is the number of registers available int K = 2; void gen(AST ast) { if(ast.left != null && ast.right != null) { int l = ast.left.n; int r = ast.right.n; if(l >= K && r >= K) { gen(ast.right); ast.n -= 1; emit_operation(PUSH, ast.right.reg); gen(ast.left); ast.reg = getreg(); emit_operation(POP, ast.right.reg); } else if(l >= r) { gen(ast.left); gen(ast.right); ast.n -= 1; } else if(l < r) { gen(ast.right); gen(ast.left); ast.n -= 1; } ast.reg = getreg(); Reg r1 = ast.left.reg; Reg r2 = ast.right.reg; emit_operation(ast.type, r1, r2); } else if(ast.type == Type_id || ast.type == Type_number) { ast.n += 1; ast.reg = getreg(); 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!"); }
编辑:请告诉我,如果需要更多的背景来理解这一点。
Sethi-Ullman实际上只是一种调度算法,而不是寄存器分配算法,所以它只是告诉你操作的顺序 ,以最小化所需的寄存器数量; 它没有告诉你哪些寄存器在哪里使用。
所以你需要将它与寄存器分配策略结合起来 – 通常只是一个贪婪的分配器。 然后就是如果你的注册用完了怎么办的问题 – 你是否插入内联溢出,或者中止并做其他事情?
为了与您的调度和指令生成内联进行简单的贪婪分配(您似乎在使用简单的gen
递归过程进行操作),您需要在任何给定时间跟踪正在使用的寄存器。 最简单的方法是在gen函数中添加一个额外的in_use
参数:
typedef unsigned RegSet; /* using a simple bitmask for a set -- assuming that * unsigned is big enough to have a bit per register */ void gen(AST *ast, RegSet in_use) { if(ast->left != 0 && ast->right != 0) { if (ast->left->n >= ast->right->n) { gen(ast->left, in_use); gen(ast->right, in_use | (1 << ast->left->reg)); } else { gen(ast->right, in_use); gen(ast->left, in_use | (1 << ast->right->reg)); } ast->reg = ast->left->reg emit_operation(ast->type, ast->left->reg, ast->right->reg); } else if(ast->type == Type_id || ast->type == Type_number) { ast->reg = pick_unused_register(in_use); emit_load(ast); } else ....
请注意,您需要一个单独的递归传递来计算每个节点的n
(Sethi-Ullman本身需要两次遍历,第一次遍历计算自下而上,第二次遍历的n
值自上而下使用)。
现在上面的代码根本不涉及寄存器的耗尽。 为此,您需要插入一些溢出物。 一种方法是在进行递归调用和溢出之前检测所有寄存器是否正在使用,之后恢复:
void gen(AST *ast, RegSet in_use) { 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 ...
当然,事实certificate这并不是非常有效 – 通常更好地溢出并稍后重新填充,但只有当你知道你将用完寄存器时才会这样。
以上就是c/c++开发分享使用Sethi-Ullman算法的表达式代码生成器相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/562235.html