scc

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

cgen.c (13385B)


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