scc

simple c99 compiler
git clone git://git.simple-cc.org/scc
Log | Files | Refs | README | LICENSE

fold.c (12796B)


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