1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 /*
6 * portable half of code generator.
7 * mainly statements and control flow.
8 */
9
10 #include "go.h"
11
12 static void cgen_dcl(Node *n);
13 static void cgen_proc(Node *n, int proc);
14 static void checkgoto(Node*, Node*);
15
16 static Label *labellist;
17 static Label *lastlabel;
18
19 Node*
20 sysfunc(char *name)
21 {
22 Node *n;
23
24 n = newname(pkglookup(name, runtimepkg));
25 n->class = PFUNC;
26 return n;
27 }
28
29 void
30 allocparams(void)
31 {
32 NodeList *l;
33 Node *n;
34 uint32 w;
35 Sym *s;
36 int lno;
37
38 if(stksize < 0)
39 fatal("allocparams not during code generation");
40
41 /*
42 * allocate (set xoffset) the stack
43 * slots for all automatics.
44 * allocated starting at -w down.
45 */
46 lno = lineno;
47 for(l=curfn->dcl; l; l=l->next) {
48 n = l->n;
49 if(n->op == ONAME && n->class == PHEAP-1) {
50 // heap address variable; finish the job
51 // started in addrescapes.
52 s = n->sym;
53 tempname(n, n->type);
54 n->sym = s;
55 }
56 if(n->op != ONAME || n->class != PAUTO)
57 continue;
58 if (n->xoffset != BADWIDTH)
59 continue;
60 if(n->type == T)
61 continue;
62 dowidth(n->type);
63 w = n->type->width;
64 if(w >= MAXWIDTH)
65 fatal("bad width");
66 stksize += w;
67 stksize = rnd(stksize, n->type->align);
68 if(thechar == '5')
69 stksize = rnd(stksize, widthptr);
70 n->xoffset = -stksize;
71 }
72 lineno = lno;
73 }
74
75 void
76 clearlabels(void)
77 {
78 Label *l;
79
80 for(l=labellist; l!=L; l=l->link)
81 l->sym->label = L;
82
83 labellist = L;
84 lastlabel = L;
85 }
86
87 static Label*
88 newlab(Node *n)
89 {
90 Sym *s;
91 Label *lab;
92
93 s = n->left->sym;
94 if((lab = s->label) == L) {
95 lab = mal(sizeof(*lab));
96 if(lastlabel == nil)
97 labellist = lab;
98 else
99 lastlabel->link = lab;
100 lastlabel = lab;
101 lab->sym = s;
102 s->label = lab;
103 }
104
105 if(n->op == OLABEL) {
106 if(lab->def != N)
107 yyerror("label %S already defined at %L", s, lab->def->lineno);
108 else
109 lab->def = n;
110 } else
111 lab->use = list(lab->use, n);
112
113 return lab;
114 }
115
116 void
117 checklabels(void)
118 {
119 Label *lab;
120 NodeList *l;
121
122 for(lab=labellist; lab!=L; lab=lab->link) {
123 if(lab->def == N) {
124 for(l=lab->use; l; l=l->next)
125 yyerrorl(l->n->lineno, "label %S not defined", lab->sym);
126 continue;
127 }
128 if(lab->use == nil && !lab->used) {
129 yyerrorl(lab->def->lineno, "label %S defined and not used", lab->sym);
130 continue;
131 }
132 if(lab->gotopc != P)
133 fatal("label %S never resolved", lab->sym);
134 for(l=lab->use; l; l=l->next)
135 checkgoto(l->n, lab->def);
136 }
137 }
138
139 static void
140 checkgoto(Node *from, Node *to)
141 {
142 int nf, nt;
143 Sym *block, *dcl, *fs, *ts;
144 int lno;
145
146 if(from->sym == to->sym)
147 return;
148
149 nf = 0;
150 for(fs=from->sym; fs; fs=fs->link)
151 nf++;
152 nt = 0;
153 for(fs=to->sym; fs; fs=fs->link)
154 nt++;
155 fs = from->sym;
156 for(; nf > nt; nf--)
157 fs = fs->link;
158 if(fs != to->sym) {
159 lno = lineno;
160 setlineno(from);
161
162 // decide what to complain about.
163 // prefer to complain about 'into block' over declarations,
164 // so scan backward to find most recent block or else dcl.
165 block = S;
166 dcl = S;
167 ts = to->sym;
168 for(; nt > nf; nt--) {
169 if(ts->pkg == nil)
170 block = ts;
171 else
172 dcl = ts;
173 ts = ts->link;
174 }
175 while(ts != fs) {
176 if(ts->pkg == nil)
177 block = ts;
178 else
179 dcl = ts;
180 ts = ts->link;
181 fs = fs->link;
182 }
183
184 if(block)
185 yyerror("goto %S jumps into block starting at %L", from->left->sym, block->lastlineno);
186 else
187 yyerror("goto %S jumps over declaration of %S at %L", from->left->sym, dcl, dcl->lastlineno);
188 lineno = lno;
189 }
190 }
191
192 static Label*
193 stmtlabel(Node *n)
194 {
195 Label *lab;
196
197 if(n->sym != S)
198 if((lab = n->sym->label) != L)
199 if(lab->def != N)
200 if(lab->def->right == n)
201 return lab;
202 return L;
203 }
204
205 /*
206 * compile statements
207 */
208 void
209 genlist(NodeList *l)
210 {
211 for(; l; l=l->next)
212 gen(l->n);
213 }
214
215 void
216 gen(Node *n)
217 {
218 int32 lno;
219 Prog *scontin, *sbreak;
220 Prog *p1, *p2, *p3;
221 Label *lab;
222 int32 wasregalloc;
223
224 lno = setlineno(n);
225 wasregalloc = anyregalloc();
226
227 if(n == N)
228 goto ret;
229
230 p3 = pc; // save pc for loop labels
231 if(n->ninit)
232 genlist(n->ninit);
233
234 setlineno(n);
235
236 switch(n->op) {
237 default:
238 fatal("gen: unknown op %N", n);
239 break;
240
241 case OCASE:
242 case OFALL:
243 case OXCASE:
244 case OXFALL:
245 case ODCLCONST:
246 case ODCLFUNC:
247 case ODCLTYPE:
248 break;
249
250 case OEMPTY:
251 break;
252
253 case OBLOCK:
254 genlist(n->list);
255 break;
256
257 case OLABEL:
258 lab = newlab(n);
259
260 // if there are pending gotos, resolve them all to the current pc.
261 for(p1=lab->gotopc; p1; p1=p2) {
262 p2 = unpatch(p1);
263 patch(p1, pc);
264 }
265 lab->gotopc = P;
266 if(lab->labelpc == P)
267 lab->labelpc = pc;
268
269 if(n->right) {
270 switch(n->right->op) {
271 case OFOR:
272 case OSWITCH:
273 case OSELECT:
274 // so stmtlabel can find the label
275 n->right->sym = lab->sym;
276 }
277 }
278 break;
279
280 case OGOTO:
281 // if label is defined, emit jump to it.
282 // otherwise save list of pending gotos in lab->gotopc.
283 // the list is linked through the normal jump target field
284 // to avoid a second list. (the jumps are actually still
285 // valid code, since they're just going to another goto
286 // to the same label. we'll unwind it when we learn the pc
287 // of the label in the OLABEL case above.)
288 lab = newlab(n);
289 if(lab->labelpc != P)
290 gjmp(lab->labelpc);
291 else
292 lab->gotopc = gjmp(lab->gotopc);
293 break;
294
295 case OBREAK:
296 if(n->left != N) {
297 lab = n->left->sym->label;
298 if(lab == L) {
299 yyerror("break label not defined: %S", n->left->sym);
300 break;
301 }
302 lab->used = 1;
303 if(lab->breakpc == P) {
304 yyerror("invalid break label %S", n->left->sym);
305 break;
306 }
307 gjmp(lab->breakpc);
308 break;
309 }
310 if(breakpc == P) {
311 yyerror("break is not in a loop");
312 break;
313 }
314 gjmp(breakpc);
315 break;
316
317 case OCONTINUE:
318 if(n->left != N) {
319 lab = n->left->sym->label;
320 if(lab == L) {
321 yyerror("continue label not defined: %S", n->left->sym);
322 break;
323 }
324 lab->used = 1;
325 if(lab->continpc == P) {
326 yyerror("invalid continue label %S", n->left->sym);
327 break;
328 }
329 gjmp(lab->continpc);
330 break;
331 }
332 if(continpc == P) {
333 yyerror("continue is not in a loop");
334 break;
335 }
336 gjmp(continpc);
337 break;
338
339 case OFOR:
340 sbreak = breakpc;
341 p1 = gjmp(P); // goto test
342 breakpc = gjmp(P); // break: goto done
343 scontin = continpc;
344 continpc = pc;
345
346 // define break and continue labels
347 if((lab = stmtlabel(n)) != L) {
348 lab->breakpc = breakpc;
349 lab->continpc = continpc;
350 }
351 gen(n->nincr); // contin: incr
352 patch(p1, pc); // test:
353 bgen(n->ntest, 0, breakpc); // if(!test) goto break
354 genlist(n->nbody); // body
355 gjmp(continpc);
356 patch(breakpc, pc); // done:
357 continpc = scontin;
358 breakpc = sbreak;
359 if(lab) {
360 lab->breakpc = P;
361 lab->continpc = P;
362 }
363 break;
364
365 case OIF:
366 p1 = gjmp(P); // goto test
367 p2 = gjmp(P); // p2: goto else
368 patch(p1, pc); // test:
369 bgen(n->ntest, 0, p2); // if(!test) goto p2
370 genlist(n->nbody); // then
371 p3 = gjmp(P); // goto done
372 patch(p2, pc); // else:
373 genlist(n->nelse); // else
374 patch(p3, pc); // done:
375 break;
376
377 case OSWITCH:
378 sbreak = breakpc;
379 p1 = gjmp(P); // goto test
380 breakpc = gjmp(P); // break: goto done
381
382 // define break label
383 if((lab = stmtlabel(n)) != L)
384 lab->breakpc = breakpc;
385
386 patch(p1, pc); // test:
387 genlist(n->nbody); // switch(test) body
388 patch(breakpc, pc); // done:
389 breakpc = sbreak;
390 if(lab != L)
391 lab->breakpc = P;
392 break;
393
394 case OSELECT:
395 sbreak = breakpc;
396 p1 = gjmp(P); // goto test
397 breakpc = gjmp(P); // break: goto done
398
399 // define break label
400 if((lab = stmtlabel(n)) != L)
401 lab->breakpc = breakpc;
402
403 patch(p1, pc); // test:
404 genlist(n->nbody); // select() body
405 patch(breakpc, pc); // done:
406 breakpc = sbreak;
407 if(lab != L)
408 lab->breakpc = P;
409 break;
410
411 case OASOP:
412 cgen_asop(n);
413 break;
414
415 case ODCL:
416 cgen_dcl(n->left);
417 break;
418
419 case OAS:
420 if(gen_as_init(n))
421 break;
422 cgen_as(n->left, n->right);
423 break;
424
425 case OCALLMETH:
426 cgen_callmeth(n, 0);
427 break;
428
429 case OCALLINTER:
430 cgen_callinter(n, N, 0);
431 break;
432
433 case OCALLFUNC:
434 cgen_call(n, 0);
435 break;
436
437 case OPROC:
438 cgen_proc(n, 1);
439 break;
440
441 case ODEFER:
442 cgen_proc(n, 2);
443 break;
444
445 case ORETURN:
446 cgen_ret(n);
447 break;
448 }
449
450 ret:
451 if(anyregalloc() != wasregalloc) {
452 dump("node", n);
453 fatal("registers left allocated");
454 }
455
456 lineno = lno;
457 }
458
459 /*
460 * generate call to non-interface method
461 * proc=0 normal call
462 * proc=1 goroutine run in new proc
463 * proc=2 defer call save away stack
464 */
465 void
466 cgen_callmeth(Node *n, int proc)
467 {
468 Node *l;
469
470 // generate a rewrite for method call
471 // (p.f)(...) goes to (f)(p,...)
472
473 l = n->left;
474 if(l->op != ODOTMETH)
475 fatal("cgen_callmeth: not dotmethod: %N");
476
477 n->op = OCALLFUNC;
478 n->left = n->left->right;
479 n->left->type = l->type;
480
481 if(n->left->op == ONAME)
482 n->left->class = PFUNC;
483 cgen_call(n, proc);
484 }
485
486 /*
487 * generate code to start new proc running call n.
488 */
489 void
490 cgen_proc(Node *n, int proc)
491 {
492 switch(n->left->op) {
493 default:
494 fatal("cgen_proc: unknown call %O", n->left->op);
495
496 case OCALLMETH:
497 cgen_callmeth(n->left, proc);
498 break;
499
500 case OCALLINTER:
501 cgen_callinter(n->left, N, proc);
502 break;
503
504 case OCALLFUNC:
505 cgen_call(n->left, proc);
506 break;
507 }
508
509 }
510
511 /*
512 * generate declaration.
513 * nothing to do for on-stack automatics,
514 * but might have to allocate heap copy
515 * for escaped variables.
516 */
517 static void
518 cgen_dcl(Node *n)
519 {
520 if(debug['g'])
521 dump("\ncgen-dcl", n);
522 if(n->op != ONAME) {
523 dump("cgen_dcl", n);
524 fatal("cgen_dcl");
525 }
526 if(!(n->class & PHEAP))
527 return;
528 if(n->alloc == nil)
529 n->alloc = callnew(n->type);
530 cgen_as(n->heapaddr, n->alloc);
531 }
532
533 /*
534 * generate discard of value
535 */
536 static void
537 cgen_discard(Node *nr)
538 {
539 Node tmp;
540
541 if(nr == N)
542 return;
543
544 switch(nr->op) {
545 case ONAME:
546 if(!(nr->class & PHEAP) && nr->class != PEXTERN && nr->class != PFUNC && nr->class != PPARAMREF)
547 gused(nr);
548 break;
549
550 // unary
551 case OADD:
552 case OAND:
553 case ODIV:
554 case OEQ:
555 case OGE:
556 case OGT:
557 case OLE:
558 case OLSH:
559 case OLT:
560 case OMOD:
561 case OMUL:
562 case ONE:
563 case OOR:
564 case ORSH:
565 case OSUB:
566 case OXOR:
567 cgen_discard(nr->left);
568 cgen_discard(nr->right);
569 break;
570
571 // binary
572 case OCAP:
573 case OCOM:
574 case OLEN:
575 case OMINUS:
576 case ONOT:
577 case OPLUS:
578 cgen_discard(nr->left);
579 break;
580
581 // special enough to just evaluate
582 default:
583 tempname(&tmp, nr->type);
584 cgen_as(&tmp, nr);
585 gused(&tmp);
586 }
587 }
588
589 /*
590 * generate assignment:
591 * nl = nr
592 * nr == N means zero nl.
593 */
594 void
595 cgen_as(Node *nl, Node *nr)
596 {
597 Node nc;
598 Type *tl;
599 int iszer;
600
601 if(nl == N)
602 return;
603
604 if(debug['g']) {
605 dump("cgen_as", nl);
606 dump("cgen_as = ", nr);
607 }
608
609 if(isblank(nl)) {
610 cgen_discard(nr);
611 return;
612 }
613
614 iszer = 0;
615 if(nr == N || isnil(nr)) {
616 // externals and heaps should already be clear
617 if(nr == N) {
618 if(nl->class == PEXTERN)
619 return;
620 if(nl->class & PHEAP)
621 return;
622 }
623
624 tl = nl->type;
625 if(tl == T)
626 return;
627 if(isfat(tl)) {
628 clearfat(nl);
629 goto ret;
630 }
631
632 /* invent a "zero" for the rhs */
633 iszer = 1;
634 nr = &nc;
635 memset(nr, 0, sizeof(*nr));
636 switch(simtype[tl->etype]) {
637 default:
638 fatal("cgen_as: tl %T", tl);
639 break;
640
641 case TINT8:
642 case TUINT8:
643 case TINT16:
644 case TUINT16:
645 case TINT32:
646 case TUINT32:
647 case TINT64:
648 case TUINT64:
649 nr->val.u.xval = mal(sizeof(*nr->val.u.xval));
650 mpmovecfix(nr->val.u.xval, 0);
651 nr->val.ctype = CTINT;
652 break;
653
654 case TFLOAT32:
655 case TFLOAT64:
656 nr->val.u.fval = mal(sizeof(*nr->val.u.fval));
657 mpmovecflt(nr->val.u.fval, 0.0);
658 nr->val.ctype = CTFLT;
659 break;
660
661 case TBOOL:
662 nr->val.u.bval = 0;
663 nr->val.ctype = CTBOOL;
664 break;
665
666 case TPTR32:
667 case TPTR64:
668 nr->val.ctype = CTNIL;
669 break;
670
671 case TCOMPLEX64:
672 case TCOMPLEX128:
673 nr->val.u.cval = mal(sizeof(*nr->val.u.cval));
674 mpmovecflt(&nr->val.u.cval->real, 0.0);
675 mpmovecflt(&nr->val.u.cval->imag, 0.0);
676 break;
677 }
678 nr->op = OLITERAL;
679 nr->type = tl;
680 nr->addable = 1;
681 ullmancalc(nr);
682 }
683
684 tl = nl->type;
685 if(tl == T)
686 return;
687
688 cgen(nr, nl);
689 if(iszer && nl->addable)
690 gused(nl);
691
692 ret:
693 ;
694 }
695
696 /*
697 * gather series of offsets
698 * >=0 is direct addressed field
699 * <0 is pointer to next field (+1)
700 */
701 int
702 dotoffset(Node *n, int *oary, Node **nn)
703 {
704 int i;
705
706 switch(n->op) {
707 case ODOT:
708 if(n->xoffset == BADWIDTH) {
709 dump("bad width in dotoffset", n);
710 fatal("bad width in dotoffset");
711 }
712 i = dotoffset(n->left, oary, nn);
713 if(i > 0) {
714 if(oary[i-1] >= 0)
715 oary[i-1] += n->xoffset;
716 else
717 oary[i-1] -= n->xoffset;
718 break;
719 }
720 if(i < 10)
721 oary[i++] = n->xoffset;
722 break;
723
724 case ODOTPTR:
725 if(n->xoffset == BADWIDTH) {
726 dump("bad width in dotoffset", n);
727 fatal("bad width in dotoffset");
728 }
729 i = dotoffset(n->left, oary, nn);
730 if(i < 10)
731 oary[i++] = -(n->xoffset+1);
732 break;
733
734 default:
735 *nn = n;
736 return 0;
737 }
738 if(i >= 10)
739 *nn = N;
740 return i;
741 }
742
743 /*
744 * make a new off the books
745 */
746 void
747 tempname(Node *nn, Type *t)
748 {
749 Node *n;
750 Sym *s;
751 uint32 w;
752
753 if(stksize < 0)
754 fatal("tempname not during code generation");
755
756 if (curfn == N)
757 fatal("no curfn for tempname");
758
759 if(t == T) {
760 yyerror("tempname called with nil type");
761 t = types[TINT32];
762 }
763
764 // give each tmp a different name so that there
765 // a chance to registerizer them
766 snprint(namebuf, sizeof(namebuf), "autotmp_%.4d", statuniqgen);
767 statuniqgen++;
768 s = lookup(namebuf);
769 n = nod(ONAME, N, N);
770 n->sym = s;
771 n->type = t;
772 n->class = PAUTO;
773 n->addable = 1;
774 n->ullman = 1;
775 n->noescape = 1;
776 n->curfn = curfn;
777 curfn->dcl = list(curfn->dcl, n);
778
779 dowidth(t);
780 w = t->width;
781 stksize += w;
782 stksize = rnd(stksize, t->align);
783 if(thechar == '5')
784 stksize = rnd(stksize, widthptr);
785 n->xoffset = -stksize;
786
787 // print("\ttmpname (%d): %N\n", stksize, n);
788
789 *nn = *n;
790 }