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