scc

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

cgen.c (13331B)


      1 #include <assert.h>
      2 #include <stdlib.h>
      3 
      4 #include <scc/cstd.h>
      5 #include <scc/scc.h>
      6 
      7 #include "arch.h"
      8 #include "../../cc2.h"
      9 
     10 enum sflags {
     11 	ISTMP  = 1,
     12 	ISCONS = 2
     13 };
     14 
     15 static char opasmw[] = {
     16 	[OADD] = ASADDW,
     17 	[OSUB] = ASSUBW,
     18 	[OMUL] = ASMULW,
     19 	[OMOD] = ASMODW,
     20 	[ODIV] = ASDIVW,
     21 	[OSHL] = ASSHLW,
     22 	[OSHR] = ASSHRW,
     23 	[OLT] = ASLTW,
     24 	[OGT] = ASGTW,
     25 	[OLE] = ASLEW,
     26 	[OGE] = ASGEW,
     27 	[OEQ] = ASEQW,
     28 	[ONE] = ASNEW,
     29 	[OBAND] = ASBANDW,
     30 	[OBOR] = ASBORW,
     31 	[OBXOR] = ASBXORW,
     32 };
     33 
     34 static char opasml[] = {
     35 	[OADD] = ASADDL,
     36 	[OSUB] = ASSUBL,
     37 	[OMUL] = ASMULL,
     38 	[OMOD] = ASMODL,
     39 	[ODIV] = ASDIVL,
     40 	[OSHL] = ASSHLL,
     41 	[OSHR] = ASSHRL,
     42 	[OLT] = ASLTL,
     43 	[OGT] = ASGTL,
     44 	[OLE] = ASLEL,
     45 	[OGE] = ASGEL,
     46 	[OEQ] = ASEQL,
     47 	[ONE] = ASNEL,
     48 	[OBAND] = ASBANDL,
     49 	[OBOR] = ASBORL,
     50 	[OBXOR] = ASBXORL,
     51 };
     52 
     53 static char opasms[] = {
     54 	[OADD] = ASADDS,
     55 	[OSUB] = ASSUBS,
     56 	[OMUL] = ASMULS,
     57 	[ODIV] = ASDIVS,
     58 	[OLT] = ASLTS,
     59 	[OGT] = ASGTS,
     60 	[OLE] = ASLES,
     61 	[OGE] = ASGES,
     62 	[OEQ] = ASEQS,
     63 	[ONE] = ASNES,
     64 };
     65 static char opasmd[] = {
     66 	[OADD] = ASADDD,
     67 	[OSUB] = ASSUBD,
     68 	[OMUL] = ASMULD,
     69 	[ODIV] = ASDIVD,
     70 	[OLT] = ASLTD,
     71 	[OGT] = ASGTD,
     72 	[OLE] = ASLED,
     73 	[OGE] = ASGED,
     74 	[OEQ] = ASEQD,
     75 	[ONE] = ASNED,
     76 };
     77 
     78 extern Type int32type, uint32type, ptrtype;
     79 
     80 static Node *
     81 tmpnode(Node *np, Type *tp)
     82 {
     83 	char flags;
     84 	Symbol *sym;
     85 
     86 	if (!np)
     87 		np = node(OTMP);
     88 	sym = getsym(TMPSYM);
     89 	sym->type = np->type = *tp;
     90 	flags = tp->flags & ~(PARF|INITF);
     91 	sym->type.flags = np->type.flags = flags;
     92 	sym->kind = STMP;
     93 	np->left = np->right = NULL;
     94 	np->u.sym = sym;
     95 	np->op = OTMP;
     96 	np->flags |= ISTMP;
     97 	return np;
     98 }
     99 
    100 static Node *
    101 load(Type *tp, Node *np, Node *new)
    102 {
    103 	int op;
    104 	int flags = tp->flags;
    105 
    106 	if (flags & (AGGRF|FUNF)) {
    107 		*new = *np;
    108 		return new;
    109 	}
    110 	switch (tp->size) {
    111 	case 1:
    112 		op = ASLDSB;
    113 		break;
    114 	case 2:
    115 		op = ASLDSH;
    116 		break;
    117 	case 4:
    118 		op = (flags & FLOATF) ? ASLDS : ASLDSW;
    119 		break;
    120 	case 8:
    121 		op = (flags & FLOATF) ? ASLDD : ASLDL;
    122 		break;
    123 	default:
    124 		abort();
    125 	}
    126 	/*
    127 	 * unsigned version of operations are always +1 the
    128 	 * signed version
    129 	 */
    130 	if ((flags & (INTF|SIGNF)) == INTF && tp->size < 8)
    131 		++op;
    132 
    133 	code(op, tmpnode(new, tp), np, NULL);
    134 
    135 	return new;
    136 }
    137 
    138 static Node *rhs(Node *np, Node *new);
    139 
    140 static Node *
    141 cast(Type *td, Node *ns, Node *nd)
    142 {
    143 	Type *ts;
    144 	Node aux1, aux2;
    145 	int op, d_isint, s_isint;
    146 
    147 	ts = &ns->type;
    148 	d_isint = (td->flags & INTF) != 0;
    149 	s_isint = (ts->flags & INTF) != 0;
    150 
    151 	if (d_isint && s_isint) {
    152 		if (td->size <= ts->size) {
    153 			*nd = *ns;
    154 			return nd;
    155 		}
    156 		assert(td->size == 4 || td->size == 8);
    157 		switch (ts->size) {
    158 		case 1:
    159 			op = (td->size == 4) ? ASEXTBW : ASEXTBL;
    160 			break;
    161 		case 2:
    162 			op = (td->size == 4) ? ASEXTHW : ASEXTHL;
    163 			break;
    164 		case 4:
    165 			op = ASEXTWL;
    166 			break;
    167 		default:
    168 			abort();
    169 		}
    170 		/*
    171 		 * unsigned version of operations are always +1 the
    172 		 * signed version
    173 		 */
    174 		op += (ts->flags & SIGNF) == 0;
    175 	} else if (d_isint) {
    176 		/* conversion from float to int */
    177 		switch (ts->size) {
    178 		case 4:
    179 			op = (td->size == 8) ? ASSTOL : ASSTOW;
    180 			break;
    181 		case 8:
    182 			op = (td->size == 8) ? ASDTOL : ASDTOW;
    183 			break;
    184 		default:
    185 			abort();
    186 		}
    187 		/* TODO: Add signess */
    188 	} else if (s_isint) {
    189 		/* conversion from int to float */
    190 		switch (ts->size) {
    191 		case 1:
    192 		case 2:
    193 			ts = (ts->flags&SIGNF) ? &int32type : &uint32type;
    194 			ns = cast(ts, ns, tmpnode(&aux2, ts));
    195 		case 4:
    196 			op = (td->size == 8) ? ASSWTOD : ASSWTOS;
    197 			break;
    198 		case 8:
    199 			op = (td->size == 8) ? ASSLTOD : ASSLTOS;
    200 			break;
    201 		default:
    202 			abort();
    203 		}
    204 		/* TODO: Add signess */
    205 	} else {
    206 		/* conversion from float to float */
    207 		op = (td->size == 4) ? ASEXTS : ASTRUNCD;
    208 	}
    209 
    210 	code(op, tmpnode(nd, td), ns, NULL);
    211 	return nd;
    212 }
    213 
    214 static Node *
    215 call(Node *np, Node *fun, Node *ret)
    216 {
    217 	int n, op;
    218 	Type *tp;
    219 	Node aux, **q, *p, *pars[NR_FUNPARAM];
    220 
    221 	for (n = 0, p = np->right; p; p = p->right)
    222 		pars[n++] = rhs(p->left, node(OTMP));
    223 
    224 	tp = &np->type;
    225 	code(ASCALL, tmpnode(ret, tp), fun, NULL);
    226 
    227 	for (q = pars; q < &pars[n]; ++q) {
    228 		op = (q == &pars[n-1]) ? ASPARE : ASPAR;
    229 		tmpnode(&aux, &(*q)->type);
    230 		code(op, NULL, *q, &aux);
    231 	}
    232 	code((np->op == OCALL) ? ASCALLE : ASCALLEX, NULL, NULL, NULL);
    233 
    234 	return ret;
    235 }
    236 
    237 static Node *
    238 assign(Type *tp, Node *to, Node *from)
    239 {
    240 	int op;
    241 
    242 	switch (tp->size) {
    243 	case 1:
    244 		op = ASSTB;
    245 		break;
    246 	case 2:
    247 		op = ASSTH;
    248 		break;
    249 	case 4:
    250 		op = (tp->flags & FLOATF) ? ASSTS : ASSTW;
    251 		break;
    252 	case 8:
    253 		op = (tp->flags & FLOATF) ? ASSTD : ASSTL;
    254 		break;
    255 	default:
    256 		op = ASSTM;
    257 		break;
    258 	}
    259 	code(op, to, from, NULL);
    260 	return from;
    261 }
    262 
    263 static Node *
    264 copy(Type *tp, Node *to, Node *from)
    265 {
    266 	int op;
    267 
    268 	switch (tp->size) {
    269 	case 1:
    270 		op = ASCOPYB;
    271 		break;
    272 	case 2:
    273 		op = ASCOPYH;
    274 		break;
    275 	case 4:
    276 		op = (tp->flags & FLOATF) ? ASCOPYS : ASCOPYW;
    277 		break;
    278 	case 8:
    279 		op = (tp->flags & FLOATF) ? ASCOPYD : ASCOPYL;
    280 		break;
    281 	default:
    282 		/* TODO: Need to handle the general case */
    283 		abort();
    284 	}
    285 	code(op, to, from, NULL);
    286 	return from;
    287 }
    288 
    289 /* TODO: Do field() transformation in sethi */
    290 
    291 static Node *
    292 field(Node *np, Node *ret, int islhs)
    293 {
    294 	Node base, node, off, add, *addr;
    295 	TUINT offset = np->right->u.sym->u.off;
    296 
    297 	addr = rhs(np->left, &base);
    298 
    299 	if (offset != 0) {
    300 		node.op = OADD;
    301 		node.type = ptrtype;
    302 		node.left = addr;
    303 		node.right = constnode(&off, offset, &ptrtype);
    304 		addr = rhs(&node, &add);
    305 	}
    306 
    307 	if (islhs)
    308 		*ret = *addr;
    309 	else
    310 		load(&np->type, addr, ret);
    311 
    312 	return ret;
    313 }
    314 
    315 static Node *
    316 lhs(Node *np, Node *new)
    317 {
    318 	switch (np->op) {
    319 	case OMEM:
    320 	case OAUTO:
    321 		*new = *np;
    322 		return new;
    323 	case OPTR:
    324 		return rhs(np->left, new);
    325 	case OFIELD:
    326 		return field(np, new, 1);
    327 	default:
    328 		abort();
    329 	}
    330 }
    331 
    332 static void
    333 bool(Node *np, Symbol *true, Symbol *false)
    334 {
    335 	Node *l = np->left, *r = np->right;
    336 	Node ret, ifyes, ifno;
    337 	Symbol *label;
    338 
    339 	switch (np->op) {
    340 	case ONEG:
    341 		bool(l, false, true);
    342 		break;
    343 	case OAND:
    344 		label = newlabel();
    345 		bool(l, label, false);
    346 		setlabel(label);
    347 		bool(r, true, false);
    348 		break;
    349 	case OOR:
    350 		label = newlabel();
    351 		bool(l, true, label);
    352 		setlabel(label);
    353 		bool(r, true, false);
    354 		break;
    355 	default:
    356 		label2node(&ifyes, true);
    357 		label2node(&ifno, false);
    358 		code(ASBRANCH, rhs(np, &ret), &ifyes, &ifno);
    359 		break;
    360 	}
    361 }
    362 
    363 static Node *
    364 ternary(Node *np, Node *ret)
    365 {
    366 	Node ifyes, ifno, phi, *colon, aux1, aux2, aux3;
    367 
    368 	tmpnode(ret, &np->type);
    369 	label2node(&ifyes, NULL);
    370 	label2node(&ifno, NULL);
    371 	label2node(&phi, NULL);
    372 
    373 	colon = np->right;
    374 	code(ASBRANCH, rhs(np->left, &aux1), &ifyes, &ifno);
    375 
    376 	setlabel(ifyes.u.sym);
    377 	copy(&ret->type, ret, rhs(colon->left, &aux2));
    378 	code(ASJMP, NULL, &phi, NULL);
    379 
    380 	setlabel(ifno.u.sym);
    381 	copy(&ret->type, ret, rhs(colon->right, &aux3));
    382 	setlabel(phi.u.sym);
    383 
    384 	return ret;
    385 }
    386 
    387 static Node *
    388 function(void)
    389 {
    390 	Node aux;
    391 	Symbol *p;
    392 
    393 	/* allocate stack space for parameters */
    394 	for (p = locals; p && (p->type.flags & PARF) != 0; p = p->next)
    395 		code(ASALLOC, label2node(&aux, p), NULL, NULL);
    396 
    397 	/* allocate stack space for local variables) */
    398 	for ( ; p && p->id != TMPSYM; p = p->next) {
    399 		if (p->kind != SAUTO)
    400 			continue;
    401 		code(ASALLOC, label2node(&aux, p), NULL, NULL);
    402 	}
    403 	/* store formal parameters in parameters */
    404 	for (p = locals; p; p = p->next) {
    405 		if ((p->type.flags & PARF) == 0)
    406 			break;
    407 		code(ASFORM, label2node(&aux, p), NULL, NULL);
    408 	}
    409 	return NULL;
    410 }
    411 
    412 static void
    413 swtch_if(Node *idx)
    414 {
    415 	Node aux1, aux2, *np;
    416 	Symbol *deflabel = NULL;
    417 
    418 	for (;;) {
    419 		np = delstmt();
    420 		setlabel(np->label);
    421 
    422 		switch (np->op) {
    423 		case OESWITCH:
    424 			if (!deflabel)
    425 				deflabel = np->u.sym;
    426 			aux1.op = OJMP;
    427 			aux1.label = NULL;
    428 			aux1.u.sym = deflabel;
    429 			cgen(&aux1);
    430 			return;
    431 		case OCASE:
    432 			aux1 = *np;
    433 			aux1.op = OBRANCH;
    434 			aux1.label = NULL;
    435 			aux1.left = &aux2;
    436 
    437 			aux2.op = OEQ;
    438 			aux2.type = idx->type;
    439 			aux2.left = np->left;
    440 			aux2.right = idx;
    441 
    442 			cgen(&aux1);
    443 			break;
    444 		case ODEFAULT:
    445 			deflabel = np->u.sym;
    446 			break;
    447 		default:
    448 			abort();
    449 		}
    450 	}
    451 }
    452 
    453 static Node *
    454 rhs(Node *np, Node *ret)
    455 {
    456 	Node aux1, aux2, *phi, *l = np->left, *r = np->right;
    457 	Type *tp;
    458 	int off, op;
    459 	char *tbl;
    460 	Symbol *true, *false;
    461 
    462 	tp = &np->type;
    463 
    464 	switch (np->op) {
    465 	case OBFUN:
    466 		return function();
    467 	case ONOP:
    468 	case OBLOOP:
    469 	case OELOOP:
    470 	case OEFUN:
    471 		return NULL;
    472 	case OTMP:
    473 	case OCONST:
    474 		*ret = *np;
    475 		return np;
    476 	case OMEM:
    477 	case OAUTO:
    478 		return load(tp, np, ret);
    479 	case ONEG:
    480 	case OAND:
    481 	case OOR:
    482 		true = newlabel();
    483 		false = newlabel();
    484 		phi = label2node(&aux1, NULL);
    485 		tmpnode(ret, &int32type);
    486 
    487 		bool(np, true, false);
    488 
    489 		setlabel(true);
    490 		code(ASCOPYW, ret, constnode(&aux2, 1, &int32type), NULL);
    491 		code(ASJMP, NULL, phi, NULL);
    492 
    493 		setlabel(false);
    494 		code(ASCOPYW, ret, constnode(&aux2, 0, &int32type), NULL);
    495 
    496 		setlabel(phi->u.sym);
    497 		return ret;
    498         case OMOD:
    499         case OSHR:
    500 		assert(tp->flags & INTF);
    501         case ODIV:
    502         case OLT:
    503         case OGT:
    504         case OLE:
    505         case OGE:
    506                 /*
    507                  * unsigned version of operations are always +1 the
    508                  * signed version
    509                  */
    510                 off = (tp->flags & SIGNF) == 0;
    511                 goto binary;
    512         case OSHL:
    513         case OBAND:
    514         case OBOR:
    515         case OBXOR:
    516 		assert(tp->flags & INTF);
    517         case OADD:
    518         case OSUB:
    519         case OMUL:
    520         case OEQ:
    521         case ONE:
    522                 off = 0;
    523         binary:
    524 		if (l->complex >= r->complex) {
    525 			rhs(l, &aux1);
    526 			rhs(r, &aux2);
    527 		} else {
    528 			rhs(r, &aux2);
    529 			rhs(l, &aux1);
    530 		}
    531                 switch (tp->size) {
    532                 case 4:
    533                         tbl = (tp->flags & FLOATF) ? opasms : opasmw;
    534                         break;
    535                 case 8:
    536                         tbl = (tp->flags & FLOATF) ? opasmd : opasml;
    537                         break;
    538                 default:
    539                         abort();
    540                 }
    541                 op = tbl[np->op] + off;
    542 		tmpnode(ret, tp);
    543                 code(op, ret, &aux1, &aux2);
    544                 return ret;
    545 	case OCALL:
    546 	case OCALLE:
    547 		if (l->op == OPTR)
    548 			l = rhs(l, &aux1);
    549 		return call(np, l, ret);
    550 	case OCAST:
    551 		return cast(tp, rhs(l, &aux1), ret);
    552 	case OASSIG:
    553 		/* TODO: Do this transformations in sethi */
    554 		switch (np->u.subop) {
    555 		case OINC:
    556 			op = OADD;
    557 			goto post_oper;
    558 		case ODEC:
    559 			op = OSUB;
    560 		post_oper:
    561 			aux1.op = op;
    562 			aux1.left = rhs(l, ret);
    563 			aux1.right = r;
    564 			aux1.type = np->type;
    565 			rhs(&aux1, &aux2);
    566 			lhs(l, &aux1);
    567 			assign(tp, &aux1, &aux2);
    568 			break;
    569 		default:
    570 			aux2.type = np->type;
    571 			aux2.op = np->u.subop;
    572 			aux2.right = np->right;
    573 			aux2.left = np->left;
    574 			r = rhs(&aux2, &aux1);
    575 			Node aux3;
    576 			if (l->op == OCAST) {
    577 				aux3.type = l->left->type;
    578 				aux3.op = OCAST;
    579 				aux3.left = r;
    580 				aux3.right = NULL;
    581 				r = &aux3;
    582 				l = l->left;
    583 			}
    584 		case 0:
    585 			/* TODO: see what is the most difficult */
    586 			lhs(l, &aux2);
    587 			rhs(r, ret);
    588 			return assign(tp, &aux2, ret);
    589 		}
    590 		return ret;
    591 	case OASK:
    592 		return ternary(np, ret);
    593 	case OCOMMA:
    594 		rhs(l, &aux1);
    595 		return rhs(r, ret);
    596 	case OPTR:
    597 		return load(tp, rhs(l, &aux1), ret);
    598 	case OADDR:
    599 		lhs(l, ret);
    600 		ret->type = *tp;
    601 		return ret;
    602 	case OFIELD:
    603 		return field(np, ret, 0);
    604 	case OBUILTIN:
    605 		switch (np->u.subop) {
    606 		case BVA_START:
    607 			l = rhs(l, &aux1);
    608 			code(ASVSTAR, NULL, l, NULL);
    609 			return NULL;
    610 		case BVA_END:
    611 			return NULL;
    612 		case BVA_ARG:
    613 			l = rhs(l, &aux1);
    614 			code(ASVARG, tmpnode(ret, tp), l, NULL);
    615 			return ret;
    616 		case BVA_COPY:
    617 			/* TODO */
    618 		default:
    619 			abort();
    620 		}
    621 	default:
    622 		abort();
    623 	}
    624 	abort();
    625 }
    626 
    627 Node *
    628 cgen(Node *np)
    629 {
    630 	Node aux, *p, *next;
    631 
    632 	setlabel(np->label);
    633 	switch (np->op) {
    634 	case OJMP:
    635 		label2node(&aux, np->u.sym);
    636 		code(ASJMP, NULL, &aux, NULL);
    637 		break;
    638 	case OBRANCH:
    639 		next = np->next;
    640 		if (!next->label)
    641 			next->label = newlabel();
    642 		bool(np->left, np->u.sym, next->label);
    643 		break;
    644 	case ORET:
    645 		p = (np->left) ? rhs(np->left, &aux) : NULL;
    646 		code(ASRET, NULL, p, NULL);
    647 		break;
    648 	case OBSWITCH:
    649 		p = rhs(np->left, &aux);
    650 		swtch_if(p);
    651 		break;
    652 	default:
    653 		rhs(np, &aux);
    654 		break;
    655 	}
    656 	return NULL;
    657 }
    658 
    659 /*
    660  * This is strongly influenced by
    661  * http://plan9.bell-labs.com/sys/doc/compiler.ps (/sys/doc/compiler.ps)
    662  * calculate addresability as follows
    663  *     AUTO => 11          value+fp
    664  *     REG => 11           reg
    665  *     STATIC => 11        (value)
    666  *     CONST => 11         $value
    667  * These values of addressability are not used in the code generation.
    668  * They are only used to calculate the Sethi-Ullman numbers. Since
    669  * QBE is AMD64 targered we could do a better job there, and try to
    670  * detect some of the complex addressing modes of these processors.
    671  */
    672 Node *
    673 sethi(Node *np)
    674 {
    675 	Node *lp, *rp;
    676 
    677 	if (!np)
    678 		return np;
    679 
    680 	np->complex = 0;
    681 	np->address = 0;
    682 	lp = np->left;
    683 	rp = np->right;
    684 
    685 	switch (np->op) {
    686 	case OAUTO:
    687 	case OREG:
    688 	case OMEM:
    689 	case OCONST:
    690 		np->address = 11;
    691 		break;
    692 	case OCPL:
    693 		assert(np->type.flags & INTF);
    694 		np->op = OBXOR;
    695 		rp = constnode(NULL, ~(TUINT) 0, &np->type);
    696 		goto binary;
    697 	case OSNEG:
    698 		np->op = OSUB;
    699 		rp = lp;
    700 		lp = constnode(NULL, 0, &np->type);
    701 		if ((np->type.flags & INTF) == 0)
    702 			lp->u.f = 0.0;
    703 	default:
    704 	binary:
    705 		lp = sethi(lp);
    706 		rp = sethi(rp);
    707 		break;
    708 	}
    709 	np->left = lp;
    710 	np->right = rp;
    711 
    712 	if (np->address > 10)
    713 		return np;
    714 	if (lp)
    715 		np->complex = lp->complex;
    716 	if (rp) {
    717 		int d = np->complex - rp->complex;
    718 
    719 		if (d == 0)
    720 			++np->complex;
    721 		else if (d < 0)
    722 			np->complex = rp->complex;
    723 	}
    724 	if (np->complex == 0)
    725 		++np->complex;
    726 	return np;
    727 }