1#include "all.h"
2
3static int
4iscon(Ref r, int64_t bits, Fn *fn)
5{
6 return rtype(r) == RCon
7 && fn->con[r.val].type == CBits
8 && fn->con[r.val].bits.i == bits;
9}
10
11static int
12iscopy(Ins *i, Ref r, Fn *fn)
13{
14 static bits extcpy[] = {
15 [WFull] = 0,
16 [Wsb] = BIT(Wsb) | BIT(Wsh) | BIT(Wsw),
17 [Wub] = BIT(Wub) | BIT(Wuh) | BIT(Wuw),
18 [Wsh] = BIT(Wsh) | BIT(Wsw),
19 [Wuh] = BIT(Wuh) | BIT(Wuw),
20 [Wsw] = BIT(Wsw),
21 [Wuw] = BIT(Wuw),
22 };
23 bits b;
24 Tmp *t;
25
26 switch (i->op) {
27 case Ocopy:
28 return 1;
29 case Omul:
30 case Odiv:
31 case Oudiv:
32 return iscon(i->arg[1], 1, fn);
33 case Oadd:
34 case Osub:
35 case Oor:
36 case Oxor:
37 case Osar:
38 case Oshl:
39 case Oshr:
40 return iscon(i->arg[1], 0, fn);
41 default:
42 break;
43 }
44 if (!isext(i->op) || rtype(r) != RTmp)
45 return 0;
46 if (i->op == Oextsw || i->op == Oextuw)
47 if (i->cls == Kw)
48 return 1;
49
50 t = &fn->tmp[r.val];
51 assert(KBASE(t->cls) == 0);
52 if (i->cls == Kl && t->cls == Kw)
53 return 0;
54 b = extcpy[t->width];
55 return (BIT(Wsb + (i->op-Oextsb)) & b) != 0;
56}
57
58static Ref
59copyof(Ref r, Ref *cpy)
60{
61 if (rtype(r) == RTmp && !req(cpy[r.val], R))
62 return cpy[r.val];
63 return r;
64}
65
66/* detects a cluster of phis/copies redundant with 'r';
67 * the algorithm is inspired by Section 3.2 of "Simple
68 * and Efficient SSA Construction" by Braun M. et al.
69 */
70static void
71phisimpl(Phi *p, Ref r, Ref *cpy, Use ***pstk, BSet *ts, BSet *as, Fn *fn)
72{
73 Use **stk, *u, *u1;
74 uint nstk, a;
75 int t;
76 Ref r1;
77 Phi *p0;
78
79 bszero(ts);
80 bszero(as);
81 p0 = &(Phi){.narg = 0};
82 stk = *pstk;
83 nstk = 1;
84 stk[0] = &(Use){.type = UPhi, .u.phi = p};
85 while (nstk) {
86 u = stk[--nstk];
87 if (u->type == UIns && iscopy(u->u.ins, r, fn)) {
88 p = p0;
89 t = u->u.ins->to.val;
90 }
91 else if (u->type == UPhi) {
92 p = u->u.phi;
93 t = p->to.val;
94 }
95 else
96 continue;
97 if (bshas(ts, t))
98 continue;
99 bsset(ts, t);
100 for (a=0; a<p->narg; a++) {
101 r1 = copyof(p->arg[a], cpy);
102 if (req(r1, r))
103 continue;
104 if (rtype(r1) != RTmp)
105 return;
106 bsset(as, r1.val);
107 }
108 u = fn->tmp[t].use;
109 u1 = &u[fn->tmp[t].nuse];
110 vgrow(pstk, nstk+(u1-u));
111 stk = *pstk;
112 for (; u<u1; u++)
113 stk[nstk++] = u;
114 }
115 bsdiff(as, ts);
116 if (!bscount(as))
117 for (t=0; bsiter(ts, &t); t++)
118 cpy[t] = r;
119}
120
121static void
122subst(Ref *pr, Ref *cpy)
123{
124 assert(rtype(*pr) != RTmp || !req(cpy[pr->val], R));
125 *pr = copyof(*pr, cpy);
126}
127
128/* requires use and rpo, breaks use */
129void
130copy(Fn *fn)
131{
132 BSet ts[1], as[1];
133 Use **stk;
134 Phi *p, **pp;
135 Ins *i;
136 Blk *b;
137 uint n, a;
138 Ref *cpy, r;
139 int t;
140
141 bsinit(ts, fn->ntmp);
142 bsinit(as, fn->ntmp);
143 cpy = emalloc(fn->ntmp * sizeof cpy[0]);
144 stk = vnew(10, sizeof stk[0], Pheap);
145
146 /* 1. build the copy-of map */
147 for (n=0; n<fn->nblk; n++) {
148 b = fn->rpo[n];
149 for (p=b->phi; p; p=p->link) {
150 assert(rtype(p->to) == RTmp);
151 if (!req(cpy[p->to.val], R))
152 continue;
153 r = R;
154 for (a=0; a<p->narg; a++)
155 if (p->blk[a]->id < n)
156 r = copyof(p->arg[a], cpy);
157 assert(!req(r, R));
158 cpy[p->to.val] = p->to;
159 phisimpl(p, r, cpy, &stk, ts, as, fn);
160 }
161 for (i=b->ins; i<&b->ins[b->nins]; i++) {
162 assert(rtype(i->to) <= RTmp);
163 if (!req(cpy[i->to.val], R))
164 continue;
165 r = copyof(i->arg[0], cpy);
166 if (iscopy(i, r, fn))
167 cpy[i->to.val] = r;
168 else
169 cpy[i->to.val] = i->to;
170 }
171 }
172
173 /* 2. remove redundant phis/copies
174 * and rewrite their uses */
175 for (b=fn->start; b; b=b->link) {
176 for (pp=&b->phi; (p=*pp);) {
177 r = cpy[p->to.val];
178 if (!req(r, p->to)) {
179 *pp = p->link;
180 continue;
181 }
182 for (a=0; a<p->narg; a++)
183 subst(&p->arg[a], cpy);
184 pp=&p->link;
185 }
186 for (i=b->ins; i<&b->ins[b->nins]; i++) {
187 r = cpy[i->to.val];
188 if (!req(r, i->to)) {
189 *i = (Ins){.op = Onop};
190 continue;
191 }
192 subst(&i->arg[0], cpy);
193 subst(&i->arg[1], cpy);
194 }
195 subst(&b->jmp.arg, cpy);
196 }
197
198 if (debug['C']) {
199 fprintf(stderr, "\n> Copy information:");
200 for (t=Tmp0; t<fn->ntmp; t++) {
201 if (req(cpy[t], R)) {
202 fprintf(stderr, "\n%10s not seen!",
203 fn->tmp[t].name);
204 }
205 else if (!req(cpy[t], TMP(t))) {
206 fprintf(stderr, "\n%10s copy of ",
207 fn->tmp[t].name);
208 printref(cpy[t], fn, stderr);
209 }
210 }
211 fprintf(stderr, "\n\n> After copy elimination:\n");
212 printfn(fn, stderr);
213 }
214 vfree(stk);
215 free(cpy);
216}
217