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 int
  23 phitmp(int t, Tmp *tmp)
  24 {
  25         int tp;
  26
  27         tp = tmp[t].phi;
  28         return tp ? tp : t;
  29 }
  30
  31 static void
  32 phifix(int t1, int *phi, Tmp *tmp)
  33 {
  34         int t, t2;
  35
  36         /* detect temporaries arguments
  37          * of the same phi node that
  38          * interfere and separate them
  39          */
  40         t = phitmp(t1, tmp);
  41         t2 = phi[t];
  42         if (t2 && t2 != t1) {
  43                 if (t != t1) {
  44                         tmp[t1].phi = t1;
  45                         t = t1;
  46                 } else {
  47                         tmp[t2].phi = t2;
  48                         phi[t2] = t2;
  49                 }
  50         }
  51         phi[t] = t1;
  52 }
  53
  54 static void
  55 bset(Ref r, Blk *b, int *nlv, int *phi, Tmp *tmp)
  56 {
  57
  58         if (rtype(r) != RTmp)
  59                 return;
  60         bsset(b->gen, r.val);
  61         phifix(r.val, phi, tmp);
  62         if (!bshas(b->in, r.val)) {
  63                 nlv[KBASE(tmp[r.val].cls)]++;
  64                 bsset(b->in, r.val);
  65         }
  66 }
  67
  68 /* liveness analysis
  69  * requires rpo computation
  70  */
  71 void
  72 filllive(Fn *f)
  73 {
  74         Blk *b;
  75         Ins *i;
  76         int k, t, m[2], n, chg, nlv[2];
  77         int *phi;
  78         BSet u[1], v[1];
  79         Mem *ma;
  80
  81         bsinit(u, f->ntmp);
  82         bsinit(v, f->ntmp);
  83         phi = emalloc(f->ntmp * sizeof phi[0]);
  84         for (b=f->start; b; b=b->link) {
  85                 bsinit(b->in, f->ntmp);
  86                 bsinit(b->out, f->ntmp);
  87                 bsinit(b->gen, f->ntmp);
  88         }
  89         chg = 1;
  90 Again:
  91         for (n=f->nblk-1; n>=0; n--) {
  92                 b = f->rpo[n];
  93
  94                 bscopy(u, b->out);
  95                 if (b->s1) {
  96                         liveon(v, b, b->s1);
  97                         bsunion(b->out, v);
  98                 }
  99                 if (b->s2) {
 100                         liveon(v, b, b->s2);
 101                         bsunion(b->out, v);
 102                 }
 103                 chg |= !bsequal(b->out, u);
 104
 105                 memset(phi, 0, f->ntmp * sizeof phi[0]);
 106                 memset(nlv, 0, sizeof nlv);
 107                 b->out->t[0] |= RGLOB;
 108                 bscopy(b->in, b->out);
 109                 for (t=0; bsiter(b->in, &t); t++) {
 110                         phifix(t, phi, f->tmp);
 111                         nlv[KBASE(f->tmp[t].cls)]++;
 112                 }
 113                 if (rtype(b->jmp.arg) == RCall) {
 114                         assert(bscount(b->in) == NRGlob && nlv[0] == NRGlob && nlv[1] == 0);
 115                         b->in->t[0] |= retregs(b->jmp.arg, nlv);
 116                 } else
 117                         bset(b->jmp.arg, b, nlv, phi, f->tmp);
 118                 for (k=0; k<2; k++)
 119                         b->nlive[k] = nlv[k];
 120                 for (i=&b->ins[b->nins]; i!=b->ins;) {
 121                         if ((--i)->op == Ocall && rtype(i->arg[1]) == RCall) {
 122                                 b->in->t[0] &= ~retregs(i->arg[1], m);
 123                                 for (k=0; k<2; k++)
 124                                         nlv[k] -= m[k];
 125                                 if (nlv[0] + NISave > b->nlive[0])
 126                                         b->nlive[0] = nlv[0] + NISave;
 127                                 if (nlv[1] + NFSave > b->nlive[1])
 128                                         b->nlive[1] = nlv[1] + NFSave;
 129                                 b->in->t[0] |= argregs(i->arg[1], m);
 130                                 for (k=0; k<2; k++)
 131                                         nlv[k] += m[k];
 132                         }
 133                         if (!req(i->to, R)) {
 134                                 assert(rtype(i->to) == RTmp);
 135                                 t = i->to.val;
 136                                 if (bshas(b->in, i->to.val))
 137                                         nlv[KBASE(f->tmp[t].cls)]--;
 138                                 bsset(b->gen, t);
 139                                 bsclr(b->in, t);
 140                                 phi[phitmp(t, f->tmp)] = 0;
 141                         }
 142                         for (k=0; k<2; k++)
 143                                 switch (rtype(i->arg[k])) {
 144                                 case RMem:
 145                                         ma = &f->mem[i->arg[k].val];
 146                                         bset(ma->base, b, nlv, phi, f->tmp);
 147                                         bset(ma->index, b, nlv, phi, f->tmp);
 148                                         break;
 149                                 default:
 150                                         bset(i->arg[k], b, nlv, phi, f->tmp);
 151                                         break;
 152                                 }
 153                         for (k=0; k<2; k++)
 154                                 if (nlv[k] > b->nlive[k])
 155                                         b->nlive[k] = nlv[k];
 156                 }
 157         }
 158         if (chg) {
 159                 chg = 0;
 160                 goto Again;
 161         }
 162         free(phi);
 163
 164         if (debug['L']) {
 165                 fprintf(stderr, "\n> Liveness analysis:\n");
 166                 for (b=f->start; b; b=b->link) {
 167                         fprintf(stderr, "\t%-10sin:   ", b->name);
 168                         dumpts(b->in, f->tmp, stderr);
 169                         fprintf(stderr, "\t          out:  ");
 170                         dumpts(b->out, f->tmp, stderr);
 171                         fprintf(stderr, "\t          gen:  ");
 172                         dumpts(b->gen, f->tmp, stderr);
 173                         fprintf(stderr, "\t          live: ");
 174                         fprintf(stderr, "%d %d\n", b->nlive[0], b->nlive[1]);
 175                 }
 176         }
 177 }