scc

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