scc

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

fold.c (12752B)


      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 UNSIGNED:
    297 		u = (rs) ? rs->u.u : 0u;
    298 		if (!folduint(op, &aux, ls->u.u, u))
    299 			return NULL;
    300 		break;
    301 	case FLOAT:
    302 		f = (rs) ? rs->u.f : 0.0;
    303 		if (!foldfloat(op, &aux, ls->u.f, f))
    304 			return NULL;
    305 		break;
    306 	}
    307 	sym = newsym(NS_IDEN, NULL);
    308 	sym->flags |= SCONSTANT;
    309 	sym->type = tp;
    310 	sym->u = aux.u;
    311 	return constnode(sym);
    312 }
    313 
    314 static Node *
    315 foldcast(Node *np, Node *l)
    316 {
    317 	TUINT negmask, mask, u;
    318 	Type *newtp = np->type, *oldtp = l->type;
    319 	Symbol aux, *sym, *osym = l->sym;
    320 
    321 	if (!(l->flags & NCONST))
    322 		return np;
    323 
    324 	switch (newtp->op) {
    325 	case PTR:
    326 	case INT:
    327 	case ENUM:
    328 		switch (oldtp->op) {
    329 		case PTR:
    330 		case INT:
    331 		case ENUM:
    332 			u = (oldtp->prop & TSIGNED) ? osym->u.i : osym->u.u;
    333 			break;
    334 		case FLOAT:
    335 			oldtp = newtp;
    336 			u = osym->u.f;
    337 			break;
    338 		default:
    339 			return  np;
    340 		}
    341 		mask = ones(newtp->size);
    342 		if (newtp->prop & TSIGNED) {
    343 			negmask = ~mask;
    344 			if (u & (negmask >> 1) & mask)
    345 				u |= negmask;
    346 			aux.u.i = u;
    347 		} else {
    348 			aux.u.u = u & mask;
    349 		}
    350 		break;
    351 	case FLOAT:
    352 		/* FIXME: The cast can be from another float type */
    353 		aux.u.f = (oldtp->prop & TSIGNED) ? osym->u.i : osym->u.u;
    354 		break;
    355 	default:
    356 		return np;
    357 	}
    358 	DBG("FOLD cast %c->%c", oldtp->letter, newtp->letter);
    359 	freetree(np);
    360 	sym = newsym(NS_IDEN, NULL);
    361 	sym->flags |= SCONSTANT;
    362 	sym->type = newtp;
    363 	sym->u = aux.u;
    364 	return constnode(sym);
    365 }
    366 
    367 static Node *
    368 foldunary(Node *np, Node *l)
    369 {
    370 	int op = l->op;
    371 	Node *aux;
    372 
    373 	switch (np->op) {
    374 	case ONEG:
    375 		if (l->op == ONEG)
    376 			break;
    377 		return NULL;
    378 	case OADD:
    379 		DBG("FOLD unary delete %d", np->op);
    380 		np->left = NULL;
    381 		freetree(np);
    382 		return l;
    383 	case OCAST:
    384 		if (op != OCAST)
    385 			return foldcast(np, l);
    386 		/* TODO: This is wrong: (float)(int) 7.2 */
    387 		DBG("FOLD unary collapse %d", np->op);
    388 		np->left = l->left;
    389 		l->left = NULL;
    390 		freetree(l);
    391 		return np;
    392 	case OSNEG:
    393 	case OCPL:
    394 		if (op != np->op)
    395 			return NULL;
    396 		break;
    397 	case OPTR:
    398 		if (op != OADDR || np->type != l->left->type)
    399 			return NULL;
    400 		break;
    401 	case OADDR:
    402 		if (op != OPTR)
    403 			return NULL;
    404 		break;
    405 	default:
    406 		return NULL;
    407 	}
    408 	DBG("FOLD unary cancel %d", np->op);
    409 	aux = l->left;
    410 	l->left = NULL;
    411 	freetree(np);
    412 	return aux;
    413 }
    414 
    415 static Node *
    416 fold(Node *np)
    417 {
    418 	Symbol *rs, *ls;
    419 	Type *optype;
    420 	int type;
    421 	int op = np->op;
    422 	Node *p, *lp = np->left, *rp = np->right;
    423 	Type *tp = np->type;
    424 
    425 	assert(lp && rp);
    426 	if ((op == ODIV || op == OMOD) && cmpnode(rp, 0)) {
    427 		warn("division by 0");
    428 		return NULL;
    429 	}
    430 	/*
    431 	 * Return if any of the children is no constant,
    432 	 * or it is a constant generated when
    433 	 * the address of a static variable is taken
    434 	 * (when we don't know the physical address so
    435 	 * we cannot fold it)
    436 	 */
    437 	if (!rp) {
    438 		rs = NULL;
    439 	} else {
    440 		if (!(rp->flags & NCONST) || !rp->sym)
    441 			return NULL;
    442 		rs = rp->sym;
    443 	}
    444 
    445 	if (!(lp->flags & NCONST) || !lp->sym)
    446 		return NULL;
    447 	optype = lp->type;
    448 	ls = lp->sym;
    449 
    450 	switch (type = optype->op) {
    451 	case ENUM:
    452 	case INT:
    453 		if (!(optype->prop & TSIGNED))
    454 			type = UNSIGNED;
    455 	case PTR:
    456 	case FLOAT:
    457 		if ((p = foldconst(type, op, tp, ls, rs)) == NULL)
    458 			return NULL;
    459 		freetree(np);
    460 		return p;
    461 	default:
    462 		return NULL;
    463 	}
    464 }
    465 
    466 static void
    467 commutative(Node *np, Node *l, Node *r)
    468 {
    469 	int op = np->op;
    470 
    471 	if (r == NULL || r->flags&NCONST || !(l->flags&NCONST))
    472 		return;
    473 
    474 	switch (op) {
    475 	case OLT:
    476 	case OGT:
    477 	case OGE:
    478 	case OLE:
    479 		DBG("FOLD neg commutative %d", np->op);
    480 		np->op = negop(op);
    481 	case OEQ:
    482 	case ONE:
    483 	case OADD:
    484 	case OMUL:
    485 	case OBAND:
    486 	case OBXOR:
    487 	case OBOR:
    488 		DBG("FOLD commutative %d", np->op);
    489 		np->left = r;
    490 		np->right = l;
    491 		break;
    492 	}
    493 }
    494 
    495 static Node *
    496 identity(Node *np)
    497 {
    498 	int iszeror, isoner;
    499 	int iszerol, isonel;
    500 	Node *lp = np->left, *rp = np->right;
    501 
    502 	if (!rp)
    503 		return NULL;
    504 
    505 	iszeror = cmpnode(rp, 0);
    506 	isoner = cmpnode(rp, 1),
    507 	iszerol = cmpnode(lp, 0);
    508 	isonel = cmpnode(lp, 1);
    509 
    510 	switch (np->op) {
    511 	case OOR:
    512 		/*
    513 		 * 1 || i => 1    (free right)
    514 		 * i || 0 => i    (free right)
    515 		 * 0 || i => i    (free left)
    516 		 * i || 1 => i,1  (comma)
    517 		 */
    518 		if (isonel | iszeror)
    519 			goto free_right;
    520 		if (iszerol)
    521 			goto free_left;
    522 		if (isoner)
    523 			goto change_to_comma;
    524 		return NULL;
    525 	case OAND:
    526 		/*
    527 		 * 0 && i => 0    (free right)
    528 		 * i && 1 => i    (free right)
    529 		 * 1 && i => i    (free left)
    530 		 * i && 0 => i,0  (comma)
    531 		 */
    532 		if (iszerol | isoner)
    533 			goto free_right;
    534 		if (isonel)
    535 			goto free_left;
    536 		if (iszeror)
    537 			goto change_to_comma;
    538 		return NULL;
    539 	case OSHL:
    540 	case OSHR:
    541 		/*
    542 		 * i >> 0 => i    (free right)
    543 		 * i << 0 => i    (free right)
    544 		 * 0 >> i => 0    (free right)
    545 		 * 0 << i => 0    (free right)
    546 		 */
    547 		if (iszeror | iszerol)
    548 			goto free_right;
    549 		return NULL;
    550 	case OBXOR:
    551 	case OADD:
    552 	case OBOR:
    553 	case OSUB:
    554 		/*
    555 		 * i + 0  => i
    556 		 * i - 0  => i
    557 		 * i | 0  => i
    558 		 * i ^ 0  => i
    559 		 */
    560 		if (iszeror)
    561 			goto free_right;
    562 		return NULL;
    563 	case OMUL:
    564 		/*
    565 		 * i * 0  => i,0
    566 		 * i * 1  => i
    567 		 */
    568 		if (iszeror)
    569 			goto change_to_comma;
    570 		if (isoner)
    571 			goto free_right;
    572 		return NULL;
    573 	case ODIV:
    574 		/* i / 1  => i */
    575 		if (isoner)
    576 			goto free_right;
    577 		return NULL;
    578 	case OBAND:
    579 		/* i & ~0 => i */
    580 		if (cmpnode(rp, -1))
    581 			goto free_right;
    582 		return NULL;
    583 	case OMOD:
    584 		/* i % 1  => i,1 */
    585 		/* TODO: i % 2^n => i & n-1 */
    586 		if (isoner)
    587 			goto change_to_comma;
    588 	default:
    589 		return NULL;
    590 	}
    591 
    592 free_right:
    593 	DBG("FOLD identity %d", np->op);
    594 	np->left = NULL;
    595 	freetree(np);
    596 	return lp;
    597 
    598 free_left:
    599 	DBG("FOLD identity %d", np->op);
    600 	np->right = NULL;
    601 	freetree(np);
    602 	return rp;
    603 
    604 change_to_comma:
    605 	DBG("FOLD identity %d", np->op);
    606 	np->op = OCOMMA;
    607 	return np;
    608 }
    609 
    610 static Node *
    611 foldternary(Node *np, Node *cond, Node *body)
    612 {
    613 	if (!(cond->flags & NCONST))
    614 		return np;
    615 	if (cmpnode(cond, 0)) {
    616 		np = body->right;
    617 		freetree(body->left);
    618 	} else {
    619 		np = body->left;
    620 		freetree(body->right);
    621 	}
    622 
    623 	DBG("FOLD ternary");
    624 	body->left = NULL;
    625 	body->right = NULL;
    626 	freetree(cond);
    627 	free(body);
    628 	return np;
    629 }
    630 
    631 /* TODO: fold OCOMMA */
    632 
    633 Node *
    634 simplify(Node *np)
    635 {
    636 	Node *p, *l, *r;
    637 
    638 	if (!np)
    639 		return NULL;
    640 	if (debug)
    641 		prtree(np);
    642 
    643 	l = np->left = simplify(np->left);
    644 	r = np->right = simplify(np->right);
    645 
    646 	switch (np->op) {
    647 	case OASK:
    648 		return foldternary(np, l, r);
    649 	case OCALL:
    650 	case OPAR:
    651 	case OSYM:
    652 	case OASSIGN:
    653 	case OA_MUL:
    654 	case OA_DIV:
    655 	case OA_MOD:
    656 	case OA_ADD:
    657 	case OA_SUB:
    658 	case OA_SHL:
    659 	case OA_SHR:
    660 	case OA_AND:
    661 	case OA_XOR:
    662 	case OA_OR:
    663 		return np;
    664 	case OSNEG:
    665 	case OCPL:
    666 	case OADDR:
    667 	case OPTR:
    668 	case INC:
    669 	case DEC:
    670 	case OCAST:
    671 	case ONEG:
    672 		assert(!r);
    673 		if ((p = foldunary(np, l)) != NULL)
    674 			return p;
    675 		return np;
    676 	default:
    677 		commutative(np, l, r);
    678 		if ((p = fold(np)) != NULL)
    679 			return p;
    680 		if ((p = identity(np)) != NULL)
    681 			return p;
    682 		return np;
    683 	}
    684 }