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