Home
fold.c - scc - simple c99 compiler
HTML git clone git://git.simple-cc.org/scc
DIR Log
DIR Files
DIR Refs
DIR Submodules
DIR README
DIR LICENSE
---
fold.c (14428B)
---
1 #include <assert.h>
2 #include <stdlib.h>
3
4 #include <scc/scc.h>
5 #include "cc1.h"
6
7
8 TUINT
9 ones(int nbytes)
10 {
11 return (nbytes == 8) ? -1 : ~(-1ull << nbytes * 8);
12 }
13
14 static int
15 addi(TINT l, TINT r, Type *tp)
16 {
17 struct limits *lim = getlimits(tp);
18 TINT max = lim->max.i, min = lim->min.i;
19
20 if (l < 0 && r < 0 && l >= min - r ||
21 l == 0 ||
22 r == 0 ||
23 l < 0 && r > 0 ||
24 l > 0 && r < 0 ||
25 l > 0 && r > 0 && l <= max - r) {
26 return 1;
27 }
28 warn("overflow in constant expression");
29 return 0;
30 }
31
32 static int
33 addf(TFLOAT l, TFLOAT r, Type *tp)
34 {
35 struct limits *lim = getlimits(tp);
36 TFLOAT max = lim->max.f, min = lim->min.f;
37
38 if (l < 0 && r < 0 && l >= min - r ||
39 l == 0 ||
40 r == 0 ||
41 l < 0 && r > 0 ||
42 l > 0 && r < 0 ||
43 l > 0 && r > 0 && l <= max - r) {
44 return 1;
45 }
46 warn("overflow in constant expression");
47 return 0;
48 }
49
50 static int
51 subi(TINT l, TINT r, Type *tp)
52 {
53 return addi(l, -r, tp);
54 }
55
56 static int
57 subf(TFLOAT l, TFLOAT r, Type *tp)
58 {
59 return addf(l, -r, tp);
60 }
61
62 static int
63 muli(TINT l, TINT r, Type *tp)
64 {
65 struct limits *lim = getlimits(tp);
66 TINT max = lim->max.i, min = lim->min.i;
67
68 if (l > -1 && l <= 1 ||
69 r > -1 && r <= 1 ||
70 l < 0 && r < 0 && -l <= max/-r ||
71 l < 0 && r > 0 && l >= min/r ||
72 l > 0 && r < 0 && r >= min/l ||
73 l > 0 && r > 0 && l <= max/r) {
74 return 1;
75 }
76 warn("overflow in constant expression");
77 return 0;
78 }
79
80 static int
81 mulf(TFLOAT l, TFLOAT r, Type *tp)
82 {
83 struct limits *lim = getlimits(tp);
84 TFLOAT max = lim->max.f, min = lim->min.f;
85
86 if (l > -1 && l <= 1 ||
87 r > -1 && r <= 1 ||
88 l < 0 && r < 0 && -l <= max/-r ||
89 l < 0 && r > 0 && l >= min/r ||
90 l > 0 && r < 0 && r >= min/l ||
91 l > 0 && r > 0 && l <= max/r) {
92 return 1;
93 }
94 warn("overflow in constant expression");
95 return 0;
96 }
97
98 static int
99 divi(TINT l, TINT r, Type *tp)
100 {
101 struct limits *lim = getlimits(tp);
102
103 if (r == 0 || l == -lim->min.i && r == -1) {
104 warn("overflow in constant expression");
105 return 0;
106 }
107 return 1;
108 }
109
110 static int
111 divf(TFLOAT l, TFLOAT r, Type *tp)
112 {
113 struct limits *lim = getlimits(tp);
114
115 if (l < 0) l = -l;
116 if (r < 0) r = -r;
117
118 if (r == 0.0 || r < 1.0 && l > lim->max.f * r) {
119 warn("overflow in constant expression");
120 return 0;
121 }
122 return 1;
123 }
124
125 static int
126 lshi(TINT l, TINT r, Type *tp)
127 {
128 if (r < 0 || r >= tp->size * 8) {
129 warn("shifting %d bits is undefined", r);
130 return 0;
131 }
132 return muli(l, 1 << r, tp);
133 }
134
135 static int
136 rshi(TINT l, TINT r, Type *tp)
137 {
138 if (r < 0 || r >= tp->size * 8) {
139 warn("shifting %d bits is undefined", r);
140 return 0;
141 }
142 return 1;
143 }
144
145 static int
146 foldint(int op, Symbol *res, TINT l, TINT r)
147 {
148 TINT i;
149 Type *tp = res->type;
150 int (*validate)(TINT, TINT, Type *tp);
151
152 switch (op) {
153 case OADD: validate = addi; break;
154 case OSUB: validate = subi; break;
155 case OMUL: validate = muli; break;
156 case ODIV: validate = divi; break;
157 case OSHL: validate = lshi; break;
158 case OSHR: validate = rshi; break;
159 case OMOD: validate = divi; break;
160 default: validate = NULL; break;
161 }
162
163 if (validate && !(*validate)(l, r, tp))
164 return 0;
165
166 switch (op) {
167 case OADD: i = l + r; break;
168 case OSUB: i = l - r; break;
169 case OMUL: i = l * r; break;
170 case ODIV: i = l / r; break;
171 case OMOD: i = l % r; break;
172 case OSHL: i = l << r; break;
173 case OSHR: i = l >> r; break;
174 case OBAND: i = l & r; break;
175 case OBXOR: i = l ^ r; break;
176 case OBOR: i = l | r; break;
177 case OAND: i = l && r; break;
178 case OOR: i = l || r; break;
179 case OLT: i = l < r; break;
180 case OGT: i = l > r; break;
181 case OGE: i = l >= r; break;
182 case OLE: i = l <= r; break;
183 case OEQ: i = l == r; break;
184 case ONE: i = l != r; break;
185 case ONEG: i = !l; break;
186 case OSNEG: i = -l; break;
187 case OCPL: i = ~l; break;
188 default: return 0;
189 }
190 res->u.i = i;
191
192 DBG("FOLD i l=%lld %d r=%lld = %lld", l, op, r, i);
193 return 1;
194 }
195
196 static int
197 folduint(int op, Symbol *res, TUINT l, TUINT r)
198 {
199 TINT i;
200 TUINT u;
201
202 switch (op) {
203 case OADD: u = l + r; break;
204 case OSUB: u = l - r; break;
205 case OMUL: u = l * r; break;
206 case ODIV: u = l / r; break;
207 case OMOD: u = l % r; break;
208 case OSHL: u = l << r; break;
209 case OSHR: u = l >> r; break;
210 case OBAND: u = l & r; break;
211 case OBXOR: u = l ^ r; break;
212 case OBOR: u = l | r; break;
213 case ONEG: u = !l; break;
214 case OSNEG: u = -l; break;
215 case OCPL: u = ~l; break;
216 case OAND: i = l && r; goto sign;
217 case OOR: i = l || r; goto sign;
218 case OLT: i = l < r; goto sign;
219 case OGT: i = l > r; goto sign;
220 case OGE: i = l >= r; goto sign;
221 case OLE: i = l <= r; goto sign;
222 case OEQ: i = l == r; goto sign;
223 case ONE: i = l != r; goto sign;
224 default: return 0;
225 }
226 res->u.u = u & ones(res->type->size);
227
228 DBG("FOLD ui l=%llu %d r=%llu = %llu", l, op, r, u);
229 return 1;
230
231 sign:
232 res->u.i = i;
233
234 DBG("FOLD sui %llu %d %llu = %llu", l, op, r, i);
235 return 1;
236 }
237
238 static int
239 foldfloat(int op, Symbol *res, TFLOAT l, TFLOAT r)
240 {
241 TFLOAT f;
242 TINT i;
243 int (*validate)(TFLOAT, TFLOAT, Type *tp);
244
245 switch (op) {
246 case OADD: validate = addf; break;
247 case OSUB: validate = subf; break;
248 case OMUL: validate = mulf; break;
249 case ODIV: validate = divf; break;
250 default: validate = NULL; break;
251 }
252
253 if (validate && !(*validate)(l, r, res->type))
254 return 0;
255
256 switch (op) {
257 case OADD: f = l + r; break;
258 case OSUB: f = l - r; break;
259 case OMUL: f = l * r; break;
260 case ODIV: f = l / r; break;
261 case OLT: i = l < r; goto comparison;
262 case OGT: i = l > r; goto comparison;
263 case OGE: i = l >= r; goto comparison;
264 case OLE: i = l <= r; goto comparison;
265 case OEQ: i = l == r; goto comparison;
266 case ONE: i = l != r; goto comparison;
267 default: return 0;
268 }
269 res->u.f = f;
270
271 DBG("FOLD f l=%lf %d r=%lf = %lf", l, op, r, f);
272 return 1;
273
274 comparison:
275 res->u.i = i;
276
277 DBG("FOLD if l=%lf %d r=%lf = %lld", l, op, r, i);
278 return 1;
279 }
280
281 static Node *
282 foldconst(int type, int op, Type *tp, Symbol *ls, Symbol *rs)
283 {
284 Symbol *sym, aux;
285 TINT i;
286 TUINT u;
287 TFLOAT f;
288
289 aux.type = tp;
290 switch (type) {
291 case INT:
292 i = (rs) ? rs->u.i : 0;
293 if (!foldint(op, &aux, ls->u.i, i))
294 return NULL;
295 break;
296 case PTR:
297 case UNSIGNED:
298 u = (rs) ? rs->u.u : 0u;
299 if (!folduint(op, &aux, ls->u.u, u))
300 return NULL;
301 break;
302 case FLOAT:
303 f = (rs) ? rs->u.f : 0.0;
304 if (!foldfloat(op, &aux, ls->u.f, f))
305 return NULL;
306 break;
307 default:
308 abort();
309 }
310 sym = newsym(NS_IDEN, NULL);
311 sym->flags |= SCONSTANT;
312 sym->type = tp;
313 sym->u = aux.u;
314 return constnode(sym);
315 }
316
317 static Node *
318 foldcast(Node *np, Node *l)
319 {
320 TUINT negmask, mask, u;
321 Type *newtp = np->type, *oldtp = l->type;
322 Symbol aux, *sym, *osym = l->sym;
323
324 if ((l->flags & NCONST) == 0 || !osym)
325 return np;
326
327 switch (newtp->op) {
328 case PTR:
329 case INT:
330 case ENUM:
331 switch (oldtp->op) {
332 case PTR:
333 case INT:
334 case ENUM:
335 u = (oldtp->prop & TSIGNED) ? osym->u.i : osym->u.u;
336 break;
337 case FLOAT:
338 oldtp = newtp;
339 u = osym->u.f;
340 break;
341 default:
342 return np;
343 }
344 mask = ones(newtp->size);
345 if (newtp->prop & TSIGNED) {
346 negmask = ~mask;
347 if (u & (negmask >> 1) & mask)
348 u |= negmask;
349 aux.u.i = u;
350 } else {
351 aux.u.u = u & mask;
352 }
353 break;
354 case FLOAT:
355 /* FIXME: The cast can be from another float type */
356 aux.u.f = (oldtp->prop & TSIGNED) ? osym->u.i : osym->u.u;
357 break;
358 default:
359 return np;
360 }
361
362 DBG("FOLD cast %c->%c", oldtp->letter, newtp->letter);
363 freetree(np);
364 sym = newsym(NS_IDEN, NULL);
365 sym->flags |= SCONSTANT;
366 sym->type = newtp;
367 sym->u = aux.u;
368 return constnode(sym);
369 }
370
371 static Node *
372 foldunary(Node *np)
373 {
374 Node *l = np->left;
375 Node *aux;
376 Symbol *sym;
377 int op = l->op;
378
379 switch (np->op) {
380 case ONEG:
381 if (l->op == ONEG)
382 break;
383 return np;
384 case OADD:
385 DBG("FOLD unary delete %d", np->op);
386 np->left = NULL;
387 freetree(np);
388 return l;
389 case OCAST:
390 return foldcast(np, l);
391 case OSNEG:
392 case OCPL:
393 if (op != np->op)
394 return np;
395 break;
396 case OPTR:
397 if (op != OADDR || np->type != l->left->type)
398 return np;
399 break;
400 case OADDR:
401 /* &(*s).f -> s + offsetof(typeof(*s), f) */
402 if (op == OFIELD && l->left->op == OPTR) {
403 DBG("FOLD collapse '&(*s).f' %d", np->op);
404 aux = node(OADD,
405 np->type,
406 l->left->left,
407 offsetnode(l->right->sym, np->type));
408
409 if (aux->left->flags & NCONST)
410 aux->flags |= NCONST;
411 l->left->left = NULL;
412 freetree(np);
413 return aux;
414 }
415
416 /* &s.f -> &s + offsetof(typeof(s), f) */
417 if (op == OFIELD) {
418 DBG("FOLD collapse '&s.f' %d", np->op);
419 aux = node(OADD,
420 np->type,
421 node(OADDR, np->type, l->left, NULL),
422 offsetnode(l->right->sym, np->type));
423
424 if (np->flags & NCONST)
425 aux->flags |= NCONST;
426 l->left = NULL;
427 freetree(np);
428 return aux;
429 }
430
431 if (op != OPTR)
432 return np;
433 break;
434 default:
435 return np;
436 }
437 DBG("FOLD unary cancel %d", np->op);
438 aux = l->left;
439 l->left = NULL;
440 freetree(np);
441 return aux;
442 }
443
444 static Node *
445 fold(Node *np)
446 {
447 Symbol *rs, *ls;
448 Type *optype;
449 int type;
450 int op = np->op;
451 Node *p, *lp = np->left, *rp = np->right;
452 Type *tp = np->type;
453
454 if (!lp && !rp)
455 return np;
456
457 if ((op == ODIV || op == OMOD) && cmpnode(rp, 0)) {
458 warn("division by 0");
459 return np;
460 }
461 /*
462 * Return if any of the children is no constant,
463 * or it is a constant generated when
464 * the address of a static variable is taken
465 * (when we don't know the physical address so
466 * we cannot fold it)
467 */
468 if (!rp) {
469 rs = NULL;
470 } else {
471 if (!(rp->flags & NCONST) || !rp->sym)
472 return np;
473 rs = rp->sym;
474 }
475
476 if ((lp->flags & NCONST) == 0 || !lp->sym)
477 return np;
478 optype = lp->type;
479 ls = lp->sym;
480
481 type = optype->op;
482 switch (type) {
483 case ENUM:
484 case INT:
485 if (!(optype->prop & TSIGNED))
486 type = UNSIGNED;
487 case PTR:
488 case FLOAT:
489 if ((p = foldconst(type, op, tp, ls, rs)) == NULL) {
490 np->flags &= ~NCONST;
491 return np;
492 }
493 freetree(np);
494 return p;
495 default:
496 return np;
497 }
498 }
499
500 static void
501 commutative(Node *np)
502 {
503 int op = np->op;
504 Node *l = np->left, *r = np->right;
505
506 if (r == NULL || r->flags&NCONST || !(l->flags&NCONST))
507 return;
508
509 switch (op) {
510 case OLT:
511 case OGT:
512 case OGE:
513 case OLE:
514 DBG("FOLD neg commutative %d", np->op);
515 np->op = negop(op);
516 case OEQ:
517 case ONE:
518 case OADD:
519 case OMUL:
520 case OBAND:
521 case OBXOR:
522 case OBOR:
523 DBG("FOLD commutative %d", np->op);
524 np->left = r;
525 np->right = l;
526 break;
527 }
528 }
529
530 static Node *
531 identity(Node *np)
532 {
533 int iszeror, isoner;
534 int iszerol, isonel;
535 Node *lp = np->left, *rp = np->right;
536
537 if (!rp)
538 return np;
539
540 iszeror = cmpnode(rp, 0);
541 isoner = cmpnode(rp, 1),
542 iszerol = cmpnode(lp, 0);
543 isonel = cmpnode(lp, 1);
544
545 switch (np->op) {
546 case OOR:
547 /*
548 * 1 || i => 1 (free right)
549 * i || 0 => i (free right)
550 * 0 || i => i (free left)
551 * i || 1 => i,1 (comma)
552 */
553 if (isonel | iszeror)
554 goto free_right;
555 if (iszerol)
556 goto free_left;
557 if (isoner)
558 goto change_to_comma;
559 return np;
560 case OAND:
561 /*
562 * 0 && i => 0 (free right)
563 * i && 1 => i (free right)
564 * 1 && i => i (free left)
565 * i && 0 => i,0 (comma)
566 */
567 if (iszerol | isoner)
568 goto free_right;
569 if (isonel)
570 goto free_left;
571 if (iszeror)
572 goto change_to_comma;
573 return np;
574 case OSHL:
575 case OSHR:
576 /*
577 * i >> 0 => i (free right)
578 * i << 0 => i (free right)
579 * 0 >> i => 0 (free right)
580 * 0 << i => 0 (free right)
581 */
582 if (iszeror | iszerol)
583 goto free_right;
584 return np;
585 case OBXOR:
586 case OADD:
587 case OBOR:
588 case OSUB:
589 /*
590 * i + 0 => i
591 * i - 0 => i
592 * i | 0 => i
593 * i ^ 0 => i
594 */
595 if (iszeror)
596 goto free_right;
597 return np;
598 case OMUL:
599 /*
600 * i * 0 => i,0 (comma)
601 * i * 1 => i (free right)
602 */
603 if (iszeror)
604 goto change_to_comma;
605 if (isoner)
606 goto free_right;
607 return np;
608 case ODIV:
609 /* i / 1 => i */
610 if (isoner)
611 goto free_right;
612 return np;
613 case OBAND:
614 /* i & ~0 => i */
615 if (cmpnode(rp, -1))
616 goto free_right;
617 return np;
618 case OMOD:
619 /* i % 1 => i,1 */
620 if (isoner)
621 goto change_to_comma;
622 default:
623 return np;
624 }
625
626 free_right:
627 DBG("FOLD identity %d", np->op);
628 np->left = NULL;
629 freetree(np);
630 return lp;
631
632 free_left:
633 DBG("FOLD identity %d", np->op);
634 np->right = NULL;
635 freetree(np);
636 return rp;
637
638 change_to_comma:
639 DBG("FOLD identity %d", np->op);
640 np->op = OCOMMA;
641 return np;
642 }
643
644 static Node *
645 foldternary(Node *np)
646 {
647 Node *cond = np->left, *body = np->right;
648
649 if ((cond->flags & NCONST) == 0)
650 return np;
651 if (cmpnode(cond, 0)) {
652 np = body->right;
653 freetree(body->left);
654 } else {
655 np = body->left;
656 freetree(body->right);
657 }
658
659 DBG("FOLD ternary");
660 body->left = NULL;
661 body->right = NULL;
662 freetree(cond);
663 free(body);
664 return np;
665 }
666
667 static Node *xsimplify(Node *);
668
669 static void
670 reduce(Node *np)
671 {
672 Node *lp = np->left, *rp = np->right;
673 Node *aux, *aux2;
674 int op = np->op;
675
676 switch (op) {
677 case OMOD:
678 /* i % 2^n => i & n-1 */
679 if (power2node(rp, NULL)) {
680 np->op = OBAND;
681 rp->sym->u.u--;
682 break;
683 }
684 return;
685 default:
686 return;
687 }
688
689 DBG("FOLD reduce %d->%d", op, np->op);
690 }
691
692 static void
693 associative(Node *np)
694 {
695 Node *l = np->left, *r = np->right;
696
697 switch (np->op) {
698 case OADD:
699 case OMUL:
700 case OBAND:
701 case OBXOR:
702 case OBOR:
703 if (np->op != l->op
704 || l->right->op != OSYM
705 || !(l->right->sym->flags&SCONSTANT)) {
706 return;
707 }
708
709 DBG("FOLD associative %d", np->op);
710 np->left = l->left;
711 l->left = r;
712 np->right = fold(l);
713 break;
714 }
715 }
716
717 /* TODO: fold OCOMMA */
718 static Node *
719 xxsimplify(Node *np)
720 {
721 int op;
722
723 np->left = xsimplify(np->left);
724 np->right = xsimplify(np->right);
725
726 repeat:
727 switch (op = np->op) {
728 case OASK:
729 np = foldternary(np);
730 break;
731 case OCALL:
732 case OPAR:
733 case OSYM:
734 case OASSIGN:
735 case OA_MUL:
736 case OA_DIV:
737 case OA_MOD:
738 case OA_ADD:
739 case OA_SUB:
740 case OA_SHL:
741 case OA_SHR:
742 case OA_AND:
743 case OA_XOR:
744 case OA_OR:
745 break;
746 case OSNEG:
747 case OCPL:
748 case OADDR:
749 case OPTR:
750 case INC:
751 case DEC:
752 case OCAST:
753 case ONEG:
754 assert(!np->right);
755 np = foldunary(np);
756 np = fold(np);
757 break;
758 default:
759 commutative(np);
760 associative(np);
761 np = fold(np);
762 np = identity(np);
763 reduce(np);
764 break;
765 }
766
767 if (op != np->op)
768 goto repeat;
769 return np;
770 }
771
772 static Node *
773 xsimplify(Node *np)
774 {
775 if (!np)
776 return NULL;
777
778 if (enadebug)
779 prtree("simplify before", np);
780 np = xxsimplify(np);
781 if (enadebug)
782 prtree("simplify after", np);
783
784 return np;
785 }
786
787 Node *
788 simplify(Node *np)
789 {
790 DBG("SIMPLIFY");
791 return xsimplify(np);
792 DBG("SIMPLIFY DONE");
793 }