1 #include "gc.h" 2 3 void 4 codgen(Node *n, Node *nn) 5 { 6 Prog *sp; 7 Node *n1, nod, nod1; 8 9 cursafe = 0; 10 curarg = 0; 11 maxargsafe = 0; 12 13 /* 14 * isolate name 15 */ 16 for(n1 = nn;; n1 = n1->left) { 17 if(n1 == Z) { 18 diag(nn, "cant find function name"); 19 return; 20 } 21 if(n1->op == ONAME) 22 break; 23 } 24 nearln = nn->lineno; 25 gpseudo(ATEXT, n1->sym, nodconst(stkoff)); 26 sp = p; 27 28 /* 29 * isolate first argument 30 */ 31 if(REGARG) { 32 if(typesu[thisfn->link->etype]) { 33 nod1 = *nodret->left; 34 nodreg(&nod, &nod1, REGARG); 35 gmove(&nod, &nod1); 36 } else 37 if(firstarg && typechlpv[firstargtype->etype]) { 38 nod1 = *nodret->left; 39 nod1.sym = firstarg; 40 nod1.type = firstargtype; 41 nod1.xoffset = align(0, firstargtype, Aarg1); 42 nod1.etype = firstargtype->etype; 43 nodreg(&nod, &nod1, REGARG); 44 gmove(&nod, &nod1); 45 } 46 } 47 48 retok = 0; 49 gen(n); 50 if(!retok) 51 if(thisfn->link->etype != TVOID) 52 warn(Z, "no return at end of function: %s", n1->sym->name); 53 noretval(3); 54 gbranch(ORETURN); 55 56 if(!debug['N'] || debug['R'] || debug['P']) 57 regopt(sp); 58 maxargsafe = round(maxargsafe, 8); 59 sp->to.offset += maxargsafe; 60 } 61 62 void 63 supgen(Node *n) 64 { 65 long spc; 66 Prog *sp; 67 68 if(n == Z) 69 return; 70 suppress++; 71 spc = pc; 72 sp = lastp; 73 gen(n); 74 lastp = sp; 75 pc = spc; 76 sp->link = nil; 77 suppress--; 78 } 79 80 void 81 gen(Node *n) 82 { 83 Node *l, nod; 84 Prog *sp, *spc, *spb; 85 Case *cn; 86 long sbc, scc; 87 int f, o; 88 89 loop: 90 if(n == Z) 91 return; 92 nearln = n->lineno; 93 o = n->op; 94 if(debug['G']) 95 if(o != OLIST) 96 print("%L %O\n", nearln, o); 97 98 retok = 0; 99 switch(o) { 100 101 default: 102 complex(n); 103 cgen(n, Z); 104 break; 105 106 case OLIST: 107 gen(n->left); 108 109 rloop: 110 n = n->right; 111 goto loop; 112 113 case ORETURN: 114 retok = 1; 115 complex(n); 116 if(n->type == T) 117 break; 118 l = n->left; 119 if(l == Z) { 120 noretval(3); 121 gbranch(ORETURN); 122 break; 123 } 124 if(typesu[n->type->etype]) { 125 sugen(l, nodret, n->type->width); 126 noretval(3); 127 gbranch(ORETURN); 128 break; 129 } 130 regret(&nod, n); 131 cgen(l, &nod); 132 regfree(&nod); 133 if(typefd[n->type->etype]) 134 noretval(1); 135 else 136 noretval(2); 137 gbranch(ORETURN); 138 break; 139 140 case OLABEL: 141 l = n->left; 142 if(l) { 143 l->xoffset = pc; 144 if(l->label) 145 patch(l->label, pc); 146 } 147 gbranch(OGOTO); /* prevent self reference in reg */ 148 patch(p, pc); 149 goto rloop; 150 151 case OGOTO: 152 retok = 1; 153 n = n->left; 154 if(n == Z) 155 return; 156 if(n->complex == 0) { 157 diag(Z, "label undefined: %s", n->sym->name); 158 return; 159 } 160 if(suppress) 161 return; 162 gbranch(OGOTO); 163 if(n->xoffset) { 164 patch(p, n->xoffset); 165 return; 166 } 167 if(n->label) 168 patch(n->label, pc-1); 169 n->label = p; 170 return; 171 172 case OCASE: 173 l = n->left; 174 if(cases == C) 175 diag(n, "case/default outside a switch"); 176 if(l == Z) { 177 cas(); 178 cases->val = 0; 179 cases->def = 1; 180 cases->label = pc; 181 cases->isv = 0; 182 goto rloop; 183 } 184 complex(l); 185 if(l->type == T) 186 goto rloop; 187 if(l->op == OCONST) 188 if(typechlv[l->type->etype]) { 189 cas(); 190 cases->val = l->vconst; 191 cases->def = 0; 192 cases->label = pc; 193 cases->isv = typev[l->type->etype]; 194 goto rloop; 195 } 196 diag(n, "case expression must be integer constant"); 197 goto rloop; 198 199 case OSWITCH: 200 l = n->left; 201 complex(l); 202 if(l->type == T) 203 break; 204 if(!typechlv[l->type->etype]) { 205 diag(n, "switch expression must be integer"); 206 break; 207 } 208 209 gbranch(OGOTO); /* entry */ 210 sp = p; 211 212 cn = cases; 213 cases = C; 214 cas(); 215 216 sbc = breakpc; 217 breakpc = pc; 218 gbranch(OGOTO); 219 spb = p; 220 221 gen(n->right); 222 gbranch(OGOTO); 223 patch(p, breakpc); 224 225 patch(sp, pc); 226 regalloc(&nod, l, Z); 227 nod.type = typev[l->type->etype]? types[TVLONG]: types[TLONG]; /* always signed */ 228 cgen(l, &nod); 229 doswit(&nod); 230 regfree(&nod); 231 patch(spb, pc); 232 233 cases = cn; 234 breakpc = sbc; 235 break; 236 237 case OWHILE: 238 case ODWHILE: 239 l = n->left; 240 gbranch(OGOTO); /* entry */ 241 sp = p; 242 243 scc = continpc; 244 continpc = pc; 245 gbranch(OGOTO); 246 spc = p; 247 248 sbc = breakpc; 249 breakpc = pc; 250 gbranch(OGOTO); 251 spb = p; 252 253 patch(spc, pc); 254 if(n->op == OWHILE) 255 patch(sp, pc); 256 bcomplex(l, Z); /* test */ 257 patch(p, breakpc); 258 259 if(n->op == ODWHILE) 260 patch(sp, pc); 261 gen(n->right); /* body */ 262 gbranch(OGOTO); 263 patch(p, continpc); 264 265 patch(spb, pc); 266 continpc = scc; 267 breakpc = sbc; 268 break; 269 270 case OFOR: 271 l = n->left; 272 gen(l->right->left); /* init */ 273 gbranch(OGOTO); /* entry */ 274 sp = p; 275 276 scc = continpc; 277 continpc = pc; 278 gbranch(OGOTO); 279 spc = p; 280 281 sbc = breakpc; 282 breakpc = pc; 283 gbranch(OGOTO); 284 spb = p; 285 286 patch(spc, pc); 287 gen(l->right->right); /* inc */ 288 patch(sp, pc); 289 if(l->left != Z) { /* test */ 290 bcomplex(l->left, Z); 291 patch(p, breakpc); 292 } 293 gen(n->right); /* body */ 294 gbranch(OGOTO); 295 patch(p, continpc); 296 297 patch(spb, pc); 298 continpc = scc; 299 breakpc = sbc; 300 break; 301 302 case OCONTINUE: 303 if(continpc < 0) { 304 diag(n, "continue not in a loop"); 305 break; 306 } 307 gbranch(OGOTO); 308 patch(p, continpc); 309 break; 310 311 case OBREAK: 312 if(breakpc < 0) { 313 diag(n, "break not in a loop"); 314 break; 315 } 316 gbranch(OGOTO); 317 patch(p, breakpc); 318 break; 319 320 case OIF: 321 l = n->left; 322 if(bcomplex(l, n->right)) { 323 if(typefd[l->type->etype]) 324 f = !l->fconst; 325 else 326 f = !l->vconst; 327 if(debug['c']) 328 print("%L const if %s\n", nearln, f ? "false" : "true"); 329 if(f) { 330 supgen(n->right->left); 331 gen(n->right->right); 332 } 333 else { 334 gen(n->right->left); 335 supgen(n->right->right); 336 } 337 } 338 else { 339 sp = p; 340 if(n->right->left != Z) 341 gen(n->right->left); 342 if(n->right->right != Z) { 343 gbranch(OGOTO); 344 patch(sp, pc); 345 sp = p; 346 gen(n->right->right); 347 } 348 patch(sp, pc); 349 } 350 break; 351 352 case OSET: 353 case OUSED: 354 usedset(n->left, o); 355 break; 356 } 357 } 358 359 void 360 usedset(Node *n, int o) 361 { 362 if(n->op == OLIST) { 363 usedset(n->left, o); 364 usedset(n->right, o); 365 return; 366 } 367 complex(n); 368 switch(n->op) { 369 case OADDR: /* volatile */ 370 gins(ANOP, n, Z); 371 break; 372 case ONAME: 373 if(o == OSET) 374 gins(ANOP, Z, n); 375 else 376 gins(ANOP, n, Z); 377 break; 378 } 379 } 380 381 void 382 noretval(int n) 383 { 384 385 if(n & 1) { 386 gins(ANOP, Z, Z); 387 p->to.type = REGRET; 388 } 389 if(n & 2) { 390 gins(ANOP, Z, Z); 391 p->to.type = FREGRET; 392 } 393 } 394 395 /* welcome to commute */ 396 static void 397 commute(Node *n) 398 { 399 Node *l, *r; 400 401 l = n->left; 402 r = n->right; 403 if(r->complex > l->complex) { 404 n->left = r; 405 n->right = l; 406 } 407 } 408 409 void 410 indexshift(Node *n) 411 { 412 int g; 413 414 if(!typechlpv[n->type->etype]) 415 return; 416 simplifyshift(n); 417 if(n->op == OASHL && n->right->op == OCONST){ 418 g = vconst(n->right); 419 if(g >= 0 && g <= 3) 420 n->addable = 7; 421 } 422 } 423 424 /* 425 * calculate addressability as follows 426 * NAME ==> 10/11 name+value(SB/SP) 427 * REGISTER ==> 12 register 428 * CONST ==> 20 $value 429 * *(20) ==> 21 value 430 * &(10) ==> 13 $name+value(SB) 431 * &(11) ==> 1 $name+value(SP) 432 * (13) + (20) ==> 13 fold constants 433 * (1) + (20) ==> 1 fold constants 434 * *(13) ==> 10 back to name 435 * *(1) ==> 11 back to name 436 * 437 * (20) * (X) ==> 7 multiplier in indexing 438 * (X,7) + (13,1) ==> 8 adder in indexing (addresses) 439 * (8) ==> &9(OINDEX) index, almost addressable 440 * 441 * calculate complexity (number of registers) 442 */ 443 void 444 xcom(Node *n) 445 { 446 Node *l, *r; 447 int g; 448 449 if(n == Z) 450 return; 451 l = n->left; 452 r = n->right; 453 n->complex = 0; 454 n->addable = 0; 455 switch(n->op) { 456 case OCONST: 457 n->addable = 20; 458 break; 459 460 case ONAME: 461 n->addable = 10; 462 if(n->class == CPARAM || n->class == CAUTO) 463 n->addable = 11; 464 break; 465 466 case OREGISTER: 467 n->addable = 12; 468 break; 469 470 case OINDREG: 471 n->addable = 12; 472 break; 473 474 case OADDR: 475 xcom(l); 476 if(l->addable == 10) 477 n->addable = 13; 478 else 479 if(l->addable == 11) 480 n->addable = 1; 481 break; 482 483 case OADD: 484 xcom(l); 485 xcom(r); 486 if(n->type->etype != TIND) 487 break; 488 489 switch(r->addable) { 490 case 20: 491 switch(l->addable) { 492 case 1: 493 case 13: 494 commadd: 495 l->type = n->type; 496 *n = *l; 497 l = new(0, Z, Z); 498 *l = *(n->left); 499 l->xoffset += r->vconst; 500 n->left = l; 501 r = n->right; 502 goto brk; 503 } 504 break; 505 506 case 1: 507 case 13: 508 case 10: 509 case 11: 510 /* l is the base, r is the index */ 511 if(l->addable != 20) 512 n->addable = 8; 513 break; 514 } 515 switch(l->addable) { 516 case 20: 517 switch(r->addable) { 518 case 13: 519 case 1: 520 r = n->left; 521 l = n->right; 522 n->left = l; 523 n->right = r; 524 goto commadd; 525 } 526 break; 527 528 case 13: 529 case 1: 530 case 10: 531 case 11: 532 /* r is the base, l is the index */ 533 if(r->addable != 20) 534 n->addable = 8; 535 break; 536 } 537 if(n->addable == 8 && !side(n)) { 538 indx(n); 539 l = new1(OINDEX, idx.basetree, idx.regtree); 540 l->scale = idx.scale; 541 l->addable = 9; 542 l->complex = l->right->complex; 543 l->type = l->left->type; 544 n->op = OADDR; 545 n->left = l; 546 n->right = Z; 547 n->addable = 8; 548 break; 549 } 550 break; 551 552 case OINDEX: 553 xcom(l); 554 xcom(r); 555 n->addable = 9; 556 break; 557 558 case OIND: 559 xcom(l); 560 if(l->op == OADDR) { 561 l = l->left; 562 l->type = n->type; 563 *n = *l; 564 return; 565 } 566 switch(l->addable) { 567 case 20: 568 n->addable = 21; 569 break; 570 case 1: 571 n->addable = 11; 572 break; 573 case 13: 574 n->addable = 10; 575 break; 576 } 577 break; 578 579 case OASHL: 580 xcom(l); 581 xcom(r); 582 indexshift(n); 583 break; 584 585 case OMUL: 586 case OLMUL: 587 xcom(l); 588 xcom(r); 589 g = vlog(l); 590 if(g >= 0) { 591 n->left = r; 592 n->right = l; 593 l = r; 594 r = n->right; 595 } 596 g = vlog(r); 597 if(g >= 0) { 598 n->op = OASHL; 599 r->vconst = g; 600 r->type = types[TINT]; 601 indexshift(n); 602 break; 603 } 604 commute(n); 605 break; 606 607 case OASLDIV: 608 xcom(l); 609 xcom(r); 610 g = vlog(r); 611 if(g >= 0) { 612 n->op = OASLSHR; 613 r->vconst = g; 614 r->type = types[TINT]; 615 } 616 break; 617 618 case OLDIV: 619 xcom(l); 620 xcom(r); 621 g = vlog(r); 622 if(g >= 0) { 623 n->op = OLSHR; 624 r->vconst = g; 625 r->type = types[TINT]; 626 indexshift(n); 627 break; 628 } 629 break; 630 631 case OASLMOD: 632 xcom(l); 633 xcom(r); 634 g = vlog(r); 635 if(g >= 0) { 636 n->op = OASAND; 637 r->vconst--; 638 } 639 break; 640 641 case OLMOD: 642 xcom(l); 643 xcom(r); 644 g = vlog(r); 645 if(g >= 0) { 646 n->op = OAND; 647 r->vconst--; 648 } 649 break; 650 651 case OASMUL: 652 case OASLMUL: 653 xcom(l); 654 xcom(r); 655 g = vlog(r); 656 if(g >= 0) { 657 n->op = OASASHL; 658 r->vconst = g; 659 } 660 break; 661 662 case OLSHR: 663 case OASHR: 664 xcom(l); 665 xcom(r); 666 indexshift(n); 667 break; 668 669 default: 670 if(l != Z) 671 xcom(l); 672 if(r != Z) 673 xcom(r); 674 break; 675 } 676 brk: 677 if(n->addable >= 10) 678 return; 679 if(l != Z) 680 n->complex = l->complex; 681 if(r != Z) { 682 if(r->complex == n->complex) 683 n->complex = r->complex+1; 684 else 685 if(r->complex > n->complex) 686 n->complex = r->complex; 687 } 688 if(n->complex == 0) 689 n->complex++; 690 691 switch(n->op) { 692 693 case OFUNC: 694 n->complex = FNX; 695 break; 696 697 case OCAST: 698 if(l->type->etype == TUVLONG && typefd[n->type->etype]) 699 n->complex += 2; 700 break; 701 702 case OLMOD: 703 case OMOD: 704 case OLMUL: 705 case OLDIV: 706 case OMUL: 707 case ODIV: 708 case OASLMUL: 709 case OASLDIV: 710 case OASLMOD: 711 case OASMUL: 712 case OASDIV: 713 case OASMOD: 714 if(r->complex >= l->complex) { 715 n->complex = l->complex + 3; 716 if(r->complex > n->complex) 717 n->complex = r->complex; 718 } else { 719 n->complex = r->complex + 3; 720 if(l->complex > n->complex) 721 n->complex = l->complex; 722 } 723 break; 724 725 case OLSHR: 726 case OASHL: 727 case OASHR: 728 case OASLSHR: 729 case OASASHL: 730 case OASASHR: 731 if(r->complex >= l->complex) { 732 n->complex = l->complex + 2; 733 if(r->complex > n->complex) 734 n->complex = r->complex; 735 } else { 736 n->complex = r->complex + 2; 737 if(l->complex > n->complex) 738 n->complex = l->complex; 739 } 740 break; 741 742 case OADD: 743 case OXOR: 744 case OAND: 745 case OOR: 746 /* 747 * immediate operators, make const on right 748 */ 749 if(l->op == OCONST) { 750 n->left = r; 751 n->right = l; 752 } 753 break; 754 755 case OEQ: 756 case ONE: 757 case OLE: 758 case OLT: 759 case OGE: 760 case OGT: 761 case OHI: 762 case OHS: 763 case OLO: 764 case OLS: 765 /* 766 * compare operators, make const on left 767 */ 768 if(r->op == OCONST) { 769 n->left = r; 770 n->right = l; 771 n->op = invrel[relindex(n->op)]; 772 } 773 break; 774 } 775 } 776 777 void 778 indx(Node *n) 779 { 780 Node *l, *r; 781 782 if(debug['x']) 783 prtree(n, "indx"); 784 785 l = n->left; 786 r = n->right; 787 if(l->addable == 1 || l->addable == 13 || r->complex > l->complex) { 788 n->right = l; 789 n->left = r; 790 l = r; 791 r = n->right; 792 } 793 if(l->addable != 7) { 794 idx.regtree = l; 795 idx.scale = 1; 796 } else 797 if(l->right->addable == 20) { 798 idx.regtree = l->left; 799 idx.scale = 1 << l->right->vconst; 800 } else 801 if(l->left->addable == 20) { 802 idx.regtree = l->right; 803 idx.scale = 1 << l->left->vconst; 804 } else 805 diag(n, "bad index"); 806 807 idx.basetree = r; 808 if(debug['x']) { 809 print("scale = %d\n", idx.scale); 810 prtree(idx.regtree, "index"); 811 prtree(idx.basetree, "base"); 812 } 813 } 814 815 int 816 bcomplex(Node *n, Node *c) 817 { 818 complex(n); 819 if(n->type != T) 820 if(tcompat(n, T, n->type, tnot)) 821 n->type = T; 822 if(n->type != T) { 823 if(c != Z && n->op == OCONST && deadheads(c)) 824 return 1; 825 boolgen(n, 1, Z); 826 } else 827 gbranch(OGOTO); 828 return 0; 829 } 830