1#include "all.h"
2
3void
4liveon(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
22static void
23bset(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 */
38void
39filllive(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;
55Again:
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 b->in->t[0] == T.rglob);
78 b->in->t[0] |= T.retregs(b->jmp.arg, nlv);
79 } else
80 bset(b->jmp.arg, b, nlv, f->tmp);
81 for (k=0; k<2; k++)
82 b->nlive[k] = nlv[k];
83 for (i=&b->ins[b->nins]; i!=b->ins;) {
84 if ((--i)->op == Ocall && rtype(i->arg[1]) == RCall) {
85 b->in->t[0] &= ~T.retregs(i->arg[1], m);
86 for (k=0; k<2; k++) {
87 nlv[k] -= m[k];
88 /* caller-save registers are used
89 * by the callee, in that sense,
90 * right in the middle of the call,
91 * they are live: */
92 nlv[k] += T.nrsave[k];
93 if (nlv[k] > b->nlive[k])
94 b->nlive[k] = nlv[k];
95 }
96 b->in->t[0] |= T.argregs(i->arg[1], m);
97 for (k=0; k<2; k++) {
98 nlv[k] -= T.nrsave[k];
99 nlv[k] += m[k];
100 }
101 }
102 if (!req(i->to, R)) {
103 assert(rtype(i->to) == RTmp);
104 t = i->to.val;
105 if (bshas(b->in, t))
106 nlv[KBASE(f->tmp[t].cls)]--;
107 bsset(b->gen, t);
108 bsclr(b->in, t);
109 }
110 for (k=0; k<2; k++)
111 switch (rtype(i->arg[k])) {
112 case RMem:
113 ma = &f->mem[i->arg[k].val];
114 bset(ma->base, b, nlv, f->tmp);
115 bset(ma->index, b, nlv, f->tmp);
116 break;
117 default:
118 bset(i->arg[k], b, nlv, f->tmp);
119 break;
120 }
121 for (k=0; k<2; k++)
122 if (nlv[k] > b->nlive[k])
123 b->nlive[k] = nlv[k];
124 }
125 }
126 if (chg) {
127 chg = 0;
128 goto Again;
129 }
130
131 if (debug['L']) {
132 fprintf(stderr, "\n> Liveness analysis:\n");
133 for (b=f->start; b; b=b->link) {
134 fprintf(stderr, "\t%-10sin: ", b->name);
135 dumpts(b->in, f->tmp, stderr);
136 fprintf(stderr, "\t out: ");
137 dumpts(b->out, f->tmp, stderr);
138 fprintf(stderr, "\t gen: ");
139 dumpts(b->gen, f->tmp, stderr);
140 fprintf(stderr, "\t live: ");
141 fprintf(stderr, "%d %d\n", b->nlive[0], b->nlive[1]);
142 }
143 }
144}
145