scc

simple C compiler
git clone git@git.2f30.org/scc.git
Log | Files | Refs | README | LICENSE

fold.c (12812B)


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