LCC编译器的源程序分析(52)寄存器溢出

当寄存器分配完了,但又有一些指令需要寄存器,那么就需要把占用寄存器的值保存到内存里,才可以重新分配那些寄存器。下面就来分析LCC的寄存溢出算法。
spillee是用来计算那个寄存器最好保存到内存里,然后重新使用的。它的代码如下:
#001 static Symbol spillee(Symbol set, unsigned mask[], Node here) {
#002 Symbol bestreg = NULL;
#003 int bestdist = -1, i;
#004
#005 assert(set);
#006 if (!set->x.wildcard)
#007 bestreg = set;
#008 else {
#009 for (i = 31; i >= 0; i—) {
#010 Symbol ri = set->x.wildcard[i];
#011 if (
#012 ri != NULL &&
#013 ri->x.lastuse &&
#014 (ri->x.regnode->mask&tmask[ri->x.regnode->set]&mask[ri->x.regnode->set])
#015 ) {
#016 Regnode rn = ri->x.regnode;
#017 Node q = here;
#018 int dist = 0;
#019 for (; q && !uses(q, rn); q = q->x.next)
#020 dist++;
#021 if (q && dist > bestdist) {
#022 bestdist = dist;
#023 bestreg = ri;
#024 }
#025 }
#026 }
#027 }
#028 assert(bestreg); /* Must be able to spill something. Reconfigure the register allocator
#029 to ensure that we can allocate a register for all nodes without spilling
#030 the node's necessary input regs. */
#031 assert(bestreg->x.regnode->vbl == NULL); /* Can't spill register variables because
#032 the reload site might be in other blocks. Reconfigure the register allocator
#033 to ensure that this register is never allocated to a variable. */
#034 return bestreg;
#035 }
在第9行到第26行里遍历了32个寄存器,寻找最好清空的寄存器。
第11行到第15行里根据规则来找到合适的寄存器。

spill函数然后生成溢出寄存器的代码,比如先把寄存器的值保存到内存,然后再标志这个寄存器为空,可以使用的状态,它的代码如下:
#001 void spill(unsigned mask, int n, Node here) {
#002 int i;
#003 Node p;
#004
#005 here->x.spills = 1;
#006 usedmask[n] |= mask;
#007 if (mask&~freemask[n]) {
#008
#009 assert( /* It makes no sense for a node to clobber() its target. */
#010 here->x.registered == 0 || /* call isn't coming through clobber() */
#011 here->syms[RX] == NULL ||
#012 here->syms[RX]->x.regnode == NULL ||
#013 here->syms[RX]->x.regnode->set != n ||
#014 (here->syms[RX]->x.regnode->mask&mask) == 0
#015 );
#016
#017 for (p = here; p; p = p->x.next)
#018 for (i = 0; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) {
#019 Symbol r = p->x.kids[i]->syms[RX];
#020 assert(r);
#021 if (p->x.kids[i]->x.registered && r->x.regnode->set == n
#022 && r->x.regnode->mask&mask)
#023 spillr(r, here);
#024 }
#025 }
#026 }
第6行清空使用的寄存器。
第7行判断这个寄存器是否使用中。
第23行调用函数spillr来生成保存寄存器的值到内存的代码。

下面接着来看函数spillr的代码:
#001 static void spillr(Symbol r, Node here) {
#002 int i;
#003 Symbol tmp;
#004 Node p = r->x.lastuse;
#005 assert(p);
#006 while (p->x.prevuse)
#007 assert(r == p->syms[RX]),
#008 p = p->x.prevuse;
#009 assert(p->x.registered && !readsreg(p));
#010 tmp = newtemp(AUTO, optype(p->op), opsize(p->op));
#011 genspill(r, p, tmp);
#012 for (p = here->x.next; p; p = p->x.next)
#013 for (i = 0; i < NELEMS(p->x.kids) && p->x.kids[i]; i++) {
#014 Node k = p->x.kids[i];
#015 if (k->x.registered && k->syms[RX] == r)
#016 genreload(p, tmp, i);
#017 }
#018 putreg(r);
#019 }
第11行里调用函数genspill生成保存寄存器值到内存的代码。
第16行里当寄存器使用完后,又需要生成重新从内存取回这个寄存值的代码。
第18行是把寄存放到空闲队列,这样就可以让这个寄存器腾出来使用了。

这样就把整个寄存器分析完成了,这里只是分析了一个大概的东西,还有很多细节没有深入地分析。有机会以后再慢慢地分析它们,下一次就分析到模式匹配和指令选择了。

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License