?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
rename Tmp.ins to be more descriptive
[qbe.git] / fold.c
blob2bb3a2feee95c464bb04302a8c1959ba9d831fad
1 #include "all.h"
2
3 enum {
4 Bot = -2, /* lattice bottom */
5 Top = -1, /* lattice top */
6 };
7
8 typedef struct Edge Edge;
9
10 struct Edge {
11 int dest;
12 int dead;
13 Edge *work;
14 };
15
16 static int *val;
17 static Edge *flowrk, (*edge)[2];
18 static Use **usewrk;
19 static uint nuse;
20
21 static int
22 iscon(Con *c, int w, uint64_t k)
23 {
24 if (c->type != CBits)
25 return 0;
26 if (w)
27 return (uint64_t)c->bits.i == k;
28 else
29 return (uint32_t)c->bits.i == (uint32_t)k;
30 }
31
32 static int
33 latval(Ref r)
34 {
35 switch (rtype(r)) {
36 case RTmp:
37 return val[r.val];
38 case RCon:
39 return r.val;
40 default:
41 die("unreachable");
42 }
43 }
44
45 static int
46 latmerge(int v, int m)
47 {
48 return m == Top ? v : (v == Top || v == m) ? m : Bot;
49 }
50
51 static void
52 update(int t, int m, Fn *fn)
53 {
54 Tmp *tmp;
55 uint u;
56
57 m = latmerge(val[t], m);
58 if (m != val[t]) {
59 tmp = &fn->tmp[t];
60 for (u=0; u<tmp->nuse; u++) {
61 vgrow(&usewrk, ++nuse);
62 usewrk[nuse-1] = &tmp->use[u];
63 }
64 val[t] = m;
65 }
66 }
67
68 static int
69 deadedge(int s, int d)
70 {
71 Edge *e;
72
73 e = edge[s];
74 if (e[0].dest == d && !e[0].dead)
75 return 0;
76 if (e[1].dest == d && !e[1].dead)
77 return 0;
78 return 1;
79 }
80
81 static void
82 visitphi(Phi *p, int n, Fn *fn)
83 {
84 int v;
85 uint a;
86
87 v = Top;
88 for (a=0; a<p->narg; a++)
89 if (!deadedge(p->blk[a]->id, n))
90 v = latmerge(v, latval(p->arg[a]));
91 update(p->to.val, v, fn);
92 }
93
94 static int opfold(int, int, Con *, Con *, Fn *);
95
96 static void
97 visitins(Ins *i, Fn *fn)
98 {
99 int v, l, r;
100
101 if (rtype(i->to) != RTmp)
102 return;
103 if (optab[i->op].canfold) {
104 l = latval(i->arg[0]);
105 if (!req(i->arg[1], R))
106 r = latval(i->arg[1]);
107 else
108 r = CON_Z.val;
109 if (l == Bot || r == Bot)
110 v = Bot;
111 else if (l == Top || r == Top)
112 v = Top;
113 else
114 v = opfold(i->op, i->cls, &fn->con[l], &fn->con[r], fn);
115 } else
116 v = Bot;
117 /* fprintf(stderr, "\nvisiting %s (%p)", optab[i->op].name, (void *)i); */
118 update(i->to.val, v, fn);
119 }
120
121 static void
122 visitjmp(Blk *b, int n, Fn *fn)
123 {
124 int l;
125
126 switch (b->jmp.type) {
127 case Jjnz:
128 l = latval(b->jmp.arg);
129 assert(l != Top && "ssa invariant broken");
130 if (l == Bot) {
131 edge[n][1].work = flowrk;
132 edge[n][0].work = &edge[n][1];
133 flowrk = &edge[n][0];
134 }
135 else if (iscon(&fn->con[l], 0, 0)) {
136 assert(edge[n][0].dead);
137 edge[n][1].work = flowrk;
138 flowrk = &edge[n][1];
139 }
140 else {
141 assert(edge[n][1].dead);
142 edge[n][0].work = flowrk;
143 flowrk = &edge[n][0];
144 }
145 break;
146 case Jjmp:
147 edge[n][0].work = flowrk;
148 flowrk = &edge[n][0];
149 break;
150 default:
151 if (isret(b->jmp.type))
152 break;
153 die("unreachable");
154 }
155 }
156
157 static void
158 initedge(Edge *e, Blk *s)
159 {
160 if (s)
161 e->dest = s->id;
162 else
163 e->dest = -1;
164 e->dead = 1;
165 e->work = 0;
166 }
167
168 static int
169 renref(Ref *r)
170 {
171 int l;
172
173 if (rtype(*r) == RTmp)
174 if ((l=val[r->val]) != Bot) {
175 assert(l != Top && "ssa invariant broken");
176 *r = CON(l);
177 return 1;
178 }
179 return 0;
180 }
181
182 /* require rpo, use, pred */
183 void
184 fold(Fn *fn)
185 {
186 Edge *e, start;
187 Use *u;
188 Blk *b, **pb;
189 Phi *p, **pp;
190 Ins *i;
191 int t, d;
192 uint n, a;
193
194 val = emalloc(fn->ntmp * sizeof val[0]);
195 edge = emalloc(fn->nblk * sizeof edge[0]);
196 usewrk = vnew(0, sizeof usewrk[0], PHeap);
197
198 for (t=0; t<fn->ntmp; t++)
199 val[t] = Top;
200 for (n=0; n<fn->nblk; n++) {
201 b = fn->rpo[n];
202 b->visit = 0;
203 initedge(&edge[n][0], b->s1);
204 initedge(&edge[n][1], b->s2);
205 }
206 initedge(&start, fn->start);
207 flowrk = &start;
208 nuse = 0;
209
210 /* 1. find out constants and dead cfg edges */
211 for (;;) {
212 e = flowrk;
213 if (e) {
214 flowrk = e->work;
215 e->work = 0;
216 if (e->dest == -1 || !e->dead)
217 continue;
218 e->dead = 0;
219 n = e->dest;
220 b = fn->rpo[n];
221 for (p=b->phi; p; p=p->link)
222 visitphi(p, n, fn);
223 if (b->visit == 0) {
224 for (i=b->ins; i<&b->ins[b->nins]; i++)
225 visitins(i, fn);
226 visitjmp(b, n, fn);
227 }
228 b->visit++;
229 assert(b->jmp.type != Jjmp
230 || !edge[n][0].dead
231 || flowrk == &edge[n][0]);
232 }
233 else if (nuse) {
234 u = usewrk[--nuse];
235 n = u->bid;
236 b = fn->rpo[n];
237 if (b->visit == 0)
238 continue;
239 switch (u->type) {
240 case UPhi:
241 visitphi(u->u.phi, u->bid, fn);
242 break;
243 case UIns:
244 visitins(u->u.ins, fn);
245 break;
246 case UJmp:
247 visitjmp(b, n, fn);
248 break;
249 default:
250 die("unreachable");
251 }
252 }
253 else
254 break;
255 }
256
257 if (debug['F']) {
258 fprintf(stderr, "\n> SCCP findings:");
259 for (t=Tmp0; t<fn->ntmp; t++) {
260 if (val[t] == Bot)
261 continue;
262 fprintf(stderr, "\n%10s: ", fn->tmp[t].name);
263 if (val[t] == Top)
264 fprintf(stderr, "Top");
265 else
266 printref(CON(val[t]), fn, stderr);
267 }
268 fprintf(stderr, "\n dead code: ");
269 }
270
271 /* 2. trim dead code, replace constants */
272 d = 0;
273 for (pb=&fn->start; (b=*pb);) {
274 if (b->visit == 0) {
275 d = 1;
276 if (debug['F'])
277 fprintf(stderr, "%s ", b->name);
278 edgedel(b, &b->s1);
279 edgedel(b, &b->s2);
280 *pb = b->link;
281 continue;
282 }
283 for (pp=&b->phi; (p=*pp);)
284 if (val[p->to.val] != Bot)
285 *pp = p->link;
286 else {
287 for (a=0; a<p->narg; a++)
288 if (!deadedge(p->blk[a]->id, b->id))
289 renref(&p->arg[a]);
290 pp = &p->link;
291 }
292 for (i=b->ins; i<&b->ins[b->nins]; i++)
293 if (renref(&i->to))
294 *i = (Ins){.op = Onop};
295 else
296 for (n=0; n<2; n++)
297 renref(&i->arg[n]);
298 renref(&b->jmp.arg);
299 if (b->jmp.type == Jjnz && rtype(b->jmp.arg) == RCon) {
300 if (iscon(&fn->con[b->jmp.arg.val], 0, 0)) {
301 edgedel(b, &b->s1);
302 b->s1 = b->s2;
303 b->s2 = 0;
304 } else
305 edgedel(b, &b->s2);
306 b->jmp.type = Jjmp;
307 b->jmp.arg = R;
308 }
309 pb = &b->link;
310 }
311
312 if (debug['F']) {
313 if (!d)
314 fprintf(stderr, "(none)");
315 fprintf(stderr, "\n\n> After constant folding:\n");
316 printfn(fn, stderr);
317 }
318
319 free(val);
320 free(edge);
321 vfree(usewrk);
322 }
323
324 /* boring folding code */
325
326 static int
327 foldint(Con *res, int op, int w, Con *cl, Con *cr)
328 {
329 union {
330 int64_t s;
331 uint64_t u;
332 float fs;
333 double fd;
334 } l, r;
335 uint64_t x;
336 uint32_t lab;
337 int typ, rel;
338
339 typ = CBits;
340 rel = RelDef;
341 lab = 0;
342 l.s = cl->bits.i;
343 r.s = cr->bits.i;
344 if (op == Oadd) {
345 if (cl->type == CAddr) {
346 if (cr->type == CAddr)
347 return 1;
348 lab = cl->label;
349 rel = cl->reloc;
350 typ = CAddr;
351 }
352 else if (cr->type == CAddr) {
353 lab = cr->label;
354 rel = cr->reloc;
355 typ = CAddr;
356 }
357 }
358 else if (op == Osub) {
359 if (cl->type == CAddr) {
360 if (cr->type != CAddr) {
361 lab = cl->label;
362 rel = cl->reloc;
363 typ = CAddr;
364 } else if (cl->label != cr->label)
365 return 1;
366 }
367 else if (cr->type == CAddr)
368 return 1;
369 }
370 else if (cl->type == CAddr || cr->type == CAddr)
371 return 1;
372 if (op == Odiv || op == Orem || op == Oudiv || op == Ourem) {
373 if (iscon(cr, w, 0))
374 return 1;
375 if (op == Odiv || op == Orem) {
376 x = w ? INT64_MIN : INT32_MIN;
377 if (iscon(cr, w, -1))
378 if (iscon(cl, w, x))
379 return 1;
380 }
381 }
382 switch (op) {
383 case Oadd: x = l.u + r.u; break;
384 case Osub: x = l.u - r.u; break;
385 case Oneg: x = -l.u; break;
386 case Odiv: x = w ? l.s / r.s : (int32_t)l.s / (int32_t)r.s; break;
387 case Orem: x = w ? l.s % r.s : (int32_t)l.s % (int32_t)r.s; break;
388 case Oudiv: x = w ? l.u / r.u : (uint32_t)l.u / (uint32_t)r.u; break;
389 case Ourem: x = w ? l.u % r.u : (uint32_t)l.u % (uint32_t)r.u; break;
390 case Omul: x = l.u * r.u; break;
391 case Oand: x = l.u & r.u; break;
392 case Oor: x = l.u | r.u; break;
393 case Oxor: x = l.u ^ r.u; break;
394 case Osar: x = (w ? l.s : (int32_t)l.s) >> (r.u & (31|w<<5)); break;
395 case Oshr: x = (w ? l.u : (uint32_t)l.u) >> (r.u & (31|w<<5)); break;
396 case Oshl: x = l.u << (r.u & (31|w<<5)); break;
397 case Oextsb: x = (int8_t)l.u; break;
398 case Oextub: x = (uint8_t)l.u; break;
399 case Oextsh: x = (int16_t)l.u; break;
400 case Oextuh: x = (uint16_t)l.u; break;
401 case Oextsw: x = (int32_t)l.u; break;
402 case Oextuw: x = (uint32_t)l.u; break;
403 case Ostosi: x = w ? (int64_t)cl->bits.s : (int32_t)cl->bits.s; break;
404 case Ostoui: x = w ? (uint64_t)cl->bits.s : (uint32_t)cl->bits.s; break;
405 case Odtosi: x = w ? (int64_t)cl->bits.d : (int32_t)cl->bits.d; break;
406 case Odtoui: x = w ? (uint64_t)cl->bits.d : (uint32_t)cl->bits.d; break;
407 case Ocast:
408 x = l.u;
409 if (cl->type == CAddr) {
410 lab = cl->label;
411 rel = cl->reloc;
412 typ = CAddr;
413 }
414 break;
415 default:
416 if (Ocmpw <= op && op <= Ocmpl1) {
417 if (op <= Ocmpw1) {
418 l.u = (int32_t)l.u;
419 r.u = (int32_t)r.u;
420 } else
421 op -= Ocmpl - Ocmpw;
422 switch (op - Ocmpw) {
423 case Ciule: x = l.u <= r.u; break;
424 case Ciult: x = l.u < r.u; break;
425 case Cisle: x = l.s <= r.s; break;
426 case Cislt: x = l.s < r.s; break;
427 case Cisgt: x = l.s > r.s; break;
428 case Cisge: x = l.s >= r.s; break;
429 case Ciugt: x = l.u > r.u; break;
430 case Ciuge: x = l.u >= r.u; break;
431 case Cieq: x = l.u == r.u; break;
432 case Cine: x = l.u != r.u; break;
433 default: die("unreachable");
434 }
435 }
436 else if (Ocmps <= op && op <= Ocmps1) {
437 switch (op - Ocmps) {
438 case Cfle: x = l.fs <= r.fs; break;
439 case Cflt: x = l.fs < r.fs; break;
440 case Cfgt: x = l.fs > r.fs; break;
441 case Cfge: x = l.fs >= r.fs; break;
442 case Cfne: x = l.fs != r.fs; break;
443 case Cfeq: x = l.fs == r.fs; break;
444 case Cfo: x = l.fs < r.fs || l.fs >= r.fs; break;
445 case Cfuo: x = !(l.fs < r.fs || l.fs >= r.fs); break;
446 default: die("unreachable");
447 }
448 }
449 else if (Ocmpd <= op && op <= Ocmpd1) {
450 switch (op - Ocmpd) {
451 case Cfle: x = l.fd <= r.fd; break;
452 case Cflt: x = l.fd < r.fd; break;
453 case Cfgt: x = l.fd > r.fd; break;
454 case Cfge: x = l.fd >= r.fd; break;
455 case Cfne: x = l.fd != r.fd; break;
456 case Cfeq: x = l.fd == r.fd; break;
457 case Cfo: x = l.fd < r.fd || l.fd >= r.fd; break;
458 case Cfuo: x = !(l.fd < r.fd || l.fd >= r.fd); break;
459 default: die("unreachable");
460 }
461 }
462 else
463 die("unreachable");
464 }
465 *res = (Con){.type=typ, .label=lab, .reloc=rel, .bits={.i=x}};
466 return 0;
467 }
468
469 static void
470 foldflt(Con *res, int op, int w, Con *cl, Con *cr)
471 {
472 float xs, ls, rs;
473 double xd, ld, rd;
474
475 if (cl->type != CBits || cr->type != CBits)
476 err("invalid address operand for '%s'", optab[op].name);
477 *res = (Con){.type = CBits};
478 memset(&res->bits, 0, sizeof(res->bits));
479 if (w) {
480 ld = cl->bits.d;
481 rd = cr->bits.d;
482 switch (op) {
483 case Oadd: xd = ld + rd; break;
484 case Osub: xd = ld - rd; break;
485 case Oneg: xd = -ld; break;
486 case Odiv: xd = ld / rd; break;
487 case Omul: xd = ld * rd; break;
488 case Oswtof: xd = (int32_t)cl->bits.i; break;
489 case Ouwtof: xd = (uint32_t)cl->bits.i; break;
490 case Osltof: xd = (int64_t)cl->bits.i; break;
491 case Oultof: xd = (uint64_t)cl->bits.i; break;
492 case Oexts: xd = cl->bits.s; break;
493 case Ocast: xd = ld; break;
494 default: die("unreachable");
495 }
496 res->bits.d = xd;
497 res->flt = 2;
498 } else {
499 ls = cl->bits.s;
500 rs = cr->bits.s;
501 switch (op) {
502 case Oadd: xs = ls + rs; break;
503 case Osub: xs = ls - rs; break;
504 case Oneg: xs = -ls; break;
505 case Odiv: xs = ls / rs; break;
506 case Omul: xs = ls * rs; break;
507 case Oswtof: xs = (int32_t)cl->bits.i; break;
508 case Ouwtof: xs = (uint32_t)cl->bits.i; break;
509 case Osltof: xs = (int64_t)cl->bits.i; break;
510 case Oultof: xs = (uint64_t)cl->bits.i; break;
511 case Otruncd: xs = cl->bits.d; break;
512 case Ocast: xs = ls; break;
513 default: die("unreachable");
514 }
515 res->bits.s = xs;
516 res->flt = 1;
517 }
518 }
519
520 static int
521 opfold(int op, int cls, Con *cl, Con *cr, Fn *fn)
522 {
523 Ref r;
524 Con c;
525
526 if (cls == Kw || cls == Kl) {
527 if (foldint(&c, op, cls == Kl, cl, cr))
528 return Bot;
529 } else
530 foldflt(&c, op, cls == Kd, cl, cr);
531 r = newcon(&c, fn);
532 assert(!(cls == Ks || cls == Kd) || c.flt);
533 return r.val;
534 }
QBE - Compiler Backend