live.c

   1 #include "all.h"
   2
   3 void
   4 liveon(BSet *v, Blk *b, Blk *s)
   5 {
   6         Phi *p;
   7         uint a;
   8
   9         bscopy(v, s->in);
  10         for (p=s->phi; p; p=p->link)
  11                 if (rtype(p->to) == RTmp)
  12                         bsclr(v, p->to.val);
  13         for (p=s->phi; p; p=p->link)
  14                 for (a=0; a<p->narg; a++)
  15                         if (p->blk[a] == b)
  16                         if (rtype(p->arg[a]) == RTmp) {
  17                                 bsset(v, p->arg[a].val);
  18                                 bsset(b->gen, p->arg[a].val);
  19                         }
  20 }
  21
  22 static void
  23 bset(Ref r, Blk *b, int *nlv, Tmp *tmp)
  24 {
  25
  26         if (rtype(r) != RTmp)
  27                 return;
  28         bsset(b->gen, r.val);
  29         if (!bshas(b->in, r.val)) {
  30                 nlv[KBASE(tmp[r.val].cls)]++;
  31                 bsset(b->in, r.val);
  32         }
  33 }
  34
  35 /* liveness analysis
  36  * requires rpo computation
  37  */
  38 void
  39 filllive(Fn *f)
  40 {
  41         Blk *b;
  42         Ins *i;
  43         int k, t, m[2], n, chg, nlv[2];
  44         BSet u[1], v[1];
  45         Mem *ma;
  46
  47         bsinit(u, f->ntmp);
  48         bsinit(v, f->ntmp);
  49         for (b=f->start; b; b=b->link) {
  50                 bsinit(b->in, f->ntmp);
  51                 bsinit(b->out, f->ntmp);
  52                 bsinit(b->gen, f->ntmp);
  53         }
  54         chg = 1;
  55 Again:
  56         for (n=f->nblk-1; n>=0; n--) {
  57                 b = f->rpo[n];
  58
  59                 bscopy(u, b->out);
  60                 if (b->s1) {
  61                         liveon(v, b, b->s1);
  62                         bsunion(b->out, v);
  63                 }
  64                 if (b->s2) {
  65                         liveon(v, b, b->s2);
  66                         bsunion(b->out, v);
  67                 }
  68                 chg |= !bsequal(b->out, u);
  69
  70                 memset(nlv, 0, sizeof nlv);
  71                 b->out->t[0] |= T.rglob;
  72                 bscopy(b->in, b->out);
  73                 for (t=0; bsiter(b->in, &t); t++)
  74                         nlv[KBASE(f->tmp[t].cls)]++;
  75                 if (rtype(b->jmp.arg) == RCall) {
  76                         assert((int)bscount(b->in) == T.nrglob &&
  77                                 nlv[0] == T.nrglob &&
  78                                 nlv[1] == 0);
  79                         b->in->t[0] |= T.retregs(b->jmp.arg, nlv);
  80                 } else
  81                         bset(b->jmp.arg, b, nlv, f->tmp);
  82                 for (k=0; k<2; k++)
  83                         b->nlive[k] = nlv[k];
  84                 for (i=&b->ins[b->nins]; i!=b->ins;) {
  85                         if (iscall((--i)->op) && rtype(i->arg[1]) == RCall) {
  86                                 b->in->t[0] &= ~T.retregs(i->arg[1], m);
  87                                 for (k=0; k<2; k++) {
  88                                         nlv[k] -= m[k];
  89                                         /* caller-save registers are used
  90                                          * by the callee, in that sense,
  91                                          * right in the middle of the call,
  92                                          * they are live: */
  93                                         nlv[k] += T.nrsave[k];
  94                                         if (nlv[k] > b->nlive[k])
  95                                                 b->nlive[k] = nlv[k];
  96                                 }
  97                                 b->in->t[0] |= T.argregs(i->arg[1], m);
  98                                 for (k=0; k<2; k++) {
  99                                         nlv[k] -= T.nrsave[k];
 100                                         nlv[k] += m[k];
 101                                 }
 102                         }
 103                         if (!req(i->to, R)) {
 104                                 assert(rtype(i->to) == RTmp);
 105                                 t = i->to.val;
 106                                 if (bshas(b->in, i->to.val))
 107                                         nlv[KBASE(f->tmp[t].cls)]--;
 108                                 bsset(b->gen, t);
 109                                 bsclr(b->in, t);
 110                         }
 111                         for (k=0; k<2; k++)
 112                                 switch (rtype(i->arg[k])) {
 113                                 case RMem:
 114                                         ma = &f->mem[i->arg[k].val];
 115                                         bset(ma->base, b, nlv, f->tmp);
 116                                         bset(ma->index, b, nlv, f->tmp);
 117                                         break;
 118                                 default:
 119                                         bset(i->arg[k], b, nlv, f->tmp);
 120                                         break;
 121                                 }
 122                         for (k=0; k<2; k++)
 123                                 if (nlv[k] > b->nlive[k])
 124                                         b->nlive[k] = nlv[k];
 125                 }
 126         }
 127         if (chg) {
 128                 chg = 0;
 129                 goto Again;
 130         }
 131
 132         if (debug['L']) {
 133                 fprintf(stderr, "\n> Liveness analysis:\n");
 134                 for (b=f->start; b; b=b->link) {
 135                         fprintf(stderr, "\t%-10sin:   ", b->name);
 136                         dumpts(b->in, f->tmp, stderr);
 137                         fprintf(stderr, "\t          out:  ");
 138                         dumpts(b->out, f->tmp, stderr);
 139                         fprintf(stderr, "\t          gen:  ");
 140                         dumpts(b->gen, f->tmp, stderr);
 141                         fprintf(stderr, "\t          live: ");
 142                         fprintf(stderr, "%d %d\n", b->nlive[0], b->nlive[1]);
 143                 }
 144         }
 145 }