cgen.c (15244B)
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 15 static Node *cgen(Node *); 16 17 static 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 37 static 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 57 static 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 71 static 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 85 static unsigned char (*opbin[][2])[2] = { 86 {opasmw, opasml}, 87 {opasms, opasmd}, 88 }; 89 90 static 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 104 static 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 115 static 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 */ 139 static Node * 140 complex(Node *np) 141 { 142 Node *lp = np->left, *rp = np->right; 143 144 if (np->address > 10) 145 return np; 146 if (lp) 147 np->complex = lp->complex; 148 if (rp) { 149 int d = np->complex - rp->complex; 150 151 if (d == 0) 152 ++np->complex; 153 else if (d < 0) 154 np->complex = rp->complex; 155 } 156 if (np->complex == 0) 157 ++np->complex; 158 159 return np; 160 } 161 162 Node * 163 sethi(Node *np) 164 { 165 Node *lp, *rp; 166 167 if (!np) 168 return np; 169 170 np->complex = 0; 171 np->address = 0; 172 lp = np->left; 173 rp = np->right; 174 175 switch (np->op) { 176 case OAUTO: 177 case OREG: 178 case OMEM: 179 case OCONST: 180 np->address = 11; 181 break; 182 case OASSIG: 183 assert(lp->op != OCAST); 184 goto binary; 185 case OCPL: 186 assert(np->type.flags & INTF); 187 np->op = OBXOR; 188 rp = constnode(NULL, ~(TUINT) 0, &np->type); 189 goto binary; 190 default: 191 binary: 192 lp = sethi(lp); 193 rp = sethi(rp); 194 break; 195 } 196 np->left = lp; 197 np->right = rp; 198 199 return complex(np); 200 } 201 202 static int 203 bytes2idx(int nbytes) 204 { 205 if (nbytes== 1) 206 return I1BYTES; 207 else if (nbytes == 2) 208 return I2BYTES; 209 else if (nbytes == 4) 210 return I4BYTES; 211 else if (nbytes == 8) 212 return I8BYTES; 213 else 214 abort(); 215 } 216 217 static Node * 218 load(Type *tp, Node *np) 219 { 220 int op; 221 Node *new; 222 int flags = tp->flags; 223 224 if (flags & (AGGRF|FUNF|ARRF|PTRF)) 225 return np; 226 227 switch (tp->size) { 228 case 1: 229 op = ASLDSB; 230 break; 231 case 2: 232 op = ASLDSH; 233 break; 234 case 4: 235 op = (flags & FLOATF) ? ASLDS : ASLDSW; 236 break; 237 case 8: 238 op = (flags & FLOATF) ? ASLDD : ASLDL; 239 break; 240 default: 241 abort(); 242 } 243 /* 244 * unsigned version of operations are always +1 the 245 * signed version 246 */ 247 if ((flags & (INTF|SIGNF)) == INTF && tp->size < 8) 248 ++op; 249 250 new = tmpnode(tp); 251 code(op, new, np, NULL); 252 253 return new; 254 } 255 256 static Node *rhs(Node *np); 257 258 static Node * 259 cast(Type *td, Node *np) 260 { 261 Type *ts; 262 Node *tmp; 263 int op, d_isint, s_isint, sidx, didx, sign; 264 265 ts = &np->type; 266 d_isint = (td->flags & INTF) != 0; 267 s_isint = (ts->flags & INTF) != 0; 268 269 sidx = bytes2idx(ts->size); 270 didx = bytes2idx(td->size); 271 272 sign = (ts->flags & SIGNF) == 0; 273 274 if (d_isint && s_isint) { 275 /* conversion from int to int */ 276 if (didx < I4BYTES) 277 didx = bytes2idx(4); 278 279 if (didx <= sidx) { 280 np->type = *td; 281 return np; 282 } 283 284 op = i2i_conv[sidx][didx][sign]; 285 } else if (d_isint) { 286 /* conversion from float to int */ 287 if (didx < I4BYTES) 288 didx = bytes2idx(4); 289 290 op = f2i_conv[sidx][didx][sign]; 291 } else if (s_isint) { 292 /* conversion from int to float */ 293 if (sidx == I1BYTES || sidx == I2BYTES) { 294 ts = (ts->flags&SIGNF) ? &int32type : &uint32type; 295 np = cast(ts, np); 296 } 297 op = i2f_conv[sidx][didx][sign]; 298 } else { 299 /* conversion from float to float */ 300 op = (didx == I4BYTES) ? ASEXTS : ASTRUNCD; 301 } 302 303 assert(op != 0); 304 tmp = tmpnode(td); 305 code(op, tmp, np, NULL); 306 307 return tmp; 308 } 309 310 static Node * 311 call(Node *np, Node *fun) 312 { 313 int n, op; 314 Type *tp; 315 Node **q, *tmp, *p, *pars[NR_FUNPARAM]; 316 317 for (n = 0, p = np->right; p; p = p->right) 318 pars[n++] = rhs(p->left); 319 320 tp = &np->type; 321 tmp = tmpnode(tp); 322 code(ASCALL, tmp, fun, NULL); 323 324 for (q = pars; q < &pars[n]; ++q) { 325 op = (q == &pars[n-1]) ? ASPARE : ASPAR; 326 code(op, NULL, *q, tmpnode(&(*q)->type)); 327 } 328 code((np->op == OCALL) ? ASCALLE : ASCALLEX, NULL, NULL, NULL); 329 330 return tmp; 331 } 332 333 static Node * 334 copy(Type *tp, Node *to, Node *from) 335 { 336 int op; 337 338 switch (tp->size) { 339 case 0: 340 return from; 341 case 1: 342 op = ASCOPYB; 343 break; 344 case 2: 345 op = ASCOPYH; 346 break; 347 case 4: 348 op = (tp->flags & FLOATF) ? ASCOPYS : ASCOPYW; 349 break; 350 case 8: 351 op = (tp->flags & FLOATF) ? ASCOPYD : ASCOPYL; 352 break; 353 default: 354 abort(); 355 } 356 code(op, to, from, NULL); 357 return from; 358 } 359 360 static Node * 361 field(Node *np, int islhs) 362 { 363 Node *tmp, *addr; 364 TUINT offset = np->right->u.sym->u.off; 365 366 addr = rhs(np->left); 367 tmp = node(OADD); 368 tmp->type = ptrtype; 369 tmp->left = addr; 370 tmp->right = constnode(NULL, offset, &ptrtype); 371 addr = rhs(tmp); 372 373 if (!islhs) 374 addr = load(&np->type, addr); 375 return addr; 376 } 377 378 static Node * 379 lhs(Node *np) 380 { 381 switch (np->op) { 382 case OREG: 383 case OMEM: 384 case OAUTO: 385 return np; 386 case OPTR: 387 return rhs(np->left); 388 case OFIELD: 389 return field(np, 1); 390 default: 391 abort(); 392 } 393 } 394 395 static void 396 bool(Node *np, Symbol *true, Symbol *false) 397 { 398 Node *l = np->left, *r = np->right; 399 Node ret, ifyes, ifno; 400 Symbol *label; 401 402 switch (np->op) { 403 case ONEG: 404 bool(l, false, true); 405 break; 406 case OAND: 407 label = newlabel(); 408 bool(l, label, false); 409 setlabel(label); 410 bool(r, true, false); 411 break; 412 case OOR: 413 label = newlabel(); 414 bool(l, true, label); 415 setlabel(label); 416 bool(r, true, false); 417 break; 418 default: 419 label2node(&ifyes, true); 420 label2node(&ifno, false); 421 code(ASBRANCH, rhs(np), &ifyes, &ifno); 422 break; 423 } 424 } 425 426 static Node * 427 ternary(Node *np) 428 { 429 Node ifyes, ifno, phi, *colon, *tmp; 430 431 tmp = tmpnode(&np->type); 432 label2node(&ifyes, NULL); 433 label2node(&ifno, NULL); 434 label2node(&phi, NULL); 435 436 colon = np->right; 437 code(ASBRANCH, rhs(np->left), &ifyes, &ifno); 438 439 setlabel(ifyes.u.sym); 440 copy(&tmp->type, tmp, rhs(colon->left)); 441 code(ASJMP, NULL, &phi, NULL); 442 443 setlabel(ifno.u.sym); 444 copy(&tmp->type, tmp, rhs(colon->right)); 445 setlabel(phi.u.sym); 446 447 return tmp; 448 } 449 450 static Node * 451 function(void) 452 { 453 Node aux; 454 Symbol *p; 455 456 /* allocate stack space for parameters */ 457 for (p = locals; p; p = p->next) { 458 if ((p->type.flags & PARF) == 0) 459 continue; 460 if ((p->type.flags & AGGRF) != 0) 461 continue; 462 code(ASALLOC, label2node(&aux, p), NULL, NULL); 463 } 464 465 /* allocate stack space for local variables) */ 466 for (p = locals; p; p = p->next) { 467 if ((p->type.flags & PARF) != 0) 468 continue; 469 if (p->kind != SAUTO || p->id == TMPSYM) 470 continue; 471 code(ASALLOC, label2node(&aux, p), NULL, NULL); 472 } 473 474 /* store formal parameters in parameters */ 475 for (p = locals; p; p = p->next) { 476 if ((p->type.flags & PARF) == 0) 477 continue; 478 if ((p->type.flags & AGGRF) != 0) 479 continue; 480 if ((p->type.flags & (ARRF|AGGRF)) == 0) 481 code(ASFORM, label2node(&aux, p), NULL, NULL); 482 } 483 return NULL; 484 } 485 486 static void 487 swtch(Node *idx) 488 { 489 Node aux1, aux2, *np; 490 Symbol *deflabel = NULL; 491 492 for (;;) { 493 np = delstmt(); 494 setlabel(np->label); 495 496 switch (np->op) { 497 case OESWITCH: 498 if (!deflabel) 499 deflabel = np->u.sym; 500 aux1.op = OJMP; 501 aux1.label = NULL; 502 aux1.u.sym = deflabel; 503 cgen(&aux1); 504 return; 505 case OCASE: 506 aux1 = *np; 507 aux1.op = OBRANCH; 508 aux1.label = NULL; 509 aux1.left = &aux2; 510 511 aux2.op = OEQ; 512 aux2.type = idx->type; 513 aux2.left = np->left; 514 aux2.right = idx; 515 516 cgen(&aux1); 517 break; 518 case ODEFAULT: 519 deflabel = np->u.sym; 520 break; 521 default: 522 abort(); 523 } 524 } 525 } 526 527 static int 528 assignop(Type *tp) 529 { 530 int flags = tp->flags; 531 532 if (flags & (AGGRF|FUNF|ARRF)) 533 return ASSTM; 534 535 switch (tp->size) { 536 case 1: 537 return ASSTB; 538 case 2: 539 return ASSTH; 540 case 4: 541 return (tp->flags & FLOATF) ? ASSTS : ASSTW; 542 case 8: 543 return (tp->flags & FLOATF) ? ASSTD : ASSTL; 544 default: 545 abort(); 546 } 547 } 548 549 static void 550 rhs_rhs(Node **lp, Node **rp) 551 { 552 Node *l = *lp, *r = *rp; 553 554 if (l->complex >= r->complex) { 555 l = rhs(l); 556 r = rhs(r); 557 } else { 558 r = rhs(r); 559 l = rhs(l); 560 } 561 562 *lp = l, *rp = r; 563 } 564 565 static void 566 lhs_rhs(Node **lp, Node **rp) 567 { 568 Node *l = *lp, *r = *rp; 569 570 if (l->complex >= r->complex) { 571 l = lhs(l); 572 r = rhs(r); 573 } else { 574 r = rhs(r); 575 l = lhs(l); 576 } 577 578 *lp = l, *rp = r; 579 } 580 581 static Node * 582 assign(Node *np) 583 { 584 Node *ret, aux; 585 Node *l = np->left, *r = np->right; 586 int op; 587 588 switch (np->u.subop) { 589 break; 590 case OINC: 591 op = OADD; 592 goto post_oper; 593 case ODEC: 594 op = OSUB; 595 post_oper: 596 lhs_rhs(&l, &r); 597 ret = load(&l->type, l); 598 aux.op = op; 599 aux.left = ret; 600 aux.right = r; 601 aux.type = np->type; 602 r = rhs(sethi(&aux)); 603 break; 604 default: 605 /* assign abbreviation */ 606 assert(l->type.size == r->type.size); 607 if (r->type.size < 4) { 608 lhs_rhs(&l, &r); 609 aux.op = np->u.subop; 610 aux.left = load(&r->type, l); 611 aux.right = r; 612 aux.type = int32type; 613 aux.address = np->address; 614 ret = r = sethi(rhs(&aux)); 615 break; 616 } 617 618 aux.op = np->u.subop; 619 aux.left = l; 620 aux.right = r; 621 aux.type = np->type; 622 aux.address = np->address; 623 r = sethi(&aux); 624 case 0: 625 lhs_rhs(&l, &r); 626 ret = r; 627 break; 628 } 629 630 code(assignop(&np->type), l, r, NULL); 631 return ret; 632 } 633 634 static Node * 635 rhs(Node *np) 636 { 637 Node *tmp, aux1, aux2; 638 Node *phi, *l = np->left, *r = np->right; 639 Type *tp; 640 int sign, size, isfloat, op; 641 Symbol *true, *false; 642 643 tp = &np->type; 644 645 switch (np->op) { 646 case OTMP: 647 case OCONST: 648 return np; 649 case OMEM: 650 case OREG: 651 case OAUTO: 652 return load(tp, np); 653 case ONEG: 654 case OAND: 655 case OOR: 656 true = newlabel(); 657 false = newlabel(); 658 phi = label2node(&aux1, NULL); 659 tmp = tmpnode(&int32type); 660 661 bool(np, true, false); 662 663 setlabel(true); 664 code(ASCOPYW, tmp, constnode(&aux2, 1, &int32type), NULL); 665 code(ASJMP, NULL, phi, NULL); 666 667 setlabel(false); 668 code(ASCOPYW, tmp, constnode(&aux2, 0, &int32type), NULL); 669 670 setlabel(phi->u.sym); 671 return tmp; 672 case OMOD: 673 case OSHL: 674 case OBAND: 675 case OBOR: 676 case OBXOR: 677 case OSHR: 678 assert(tp->flags & INTF); 679 case ODIV: 680 case OLT: 681 case OGT: 682 case OLE: 683 case OGE: 684 case OADD: 685 case OSUB: 686 case OMUL: 687 case OEQ: 688 case ONE: 689 assert(tp->size == 4 || tp->size == 8); 690 691 sign = (tp->flags & SIGNF) == 0; 692 size = tp->size == 8; 693 isfloat = (tp->flags & FLOATF) != 0; 694 op = opbin[isfloat][size][np->op][sign]; 695 rhs_rhs(&l, &r); 696 tmp = tmpnode(tp); 697 code(op, tmp, l, r); 698 return tmp; 699 case OCALL: 700 case OCALLE: 701 if (l->op == OPTR) 702 l = rhs(l); 703 return call(np, l); 704 case OCAST: 705 return cast(tp, rhs(l)); 706 case OASSIG: 707 return assign(np); 708 case OASK: 709 return ternary(np); 710 case OCOMMA: 711 rhs(l); 712 return rhs(r); 713 case OSNEG: 714 sign = (tp->flags & SIGNF) == 0; 715 size = tp->size == 8; 716 isfloat = (tp->flags & FLOATF) != 0; 717 op = opbin[isfloat][size][np->op][sign]; 718 tmp = tmpnode(tp); 719 code(op, tmp, rhs(l), NULL); 720 return tmp; 721 case OPTR: 722 return load(tp, rhs(l)); 723 case OADDR: 724 l = lhs(l); 725 l->type = *tp; 726 l->type.flags |= PTRF; 727 return l; 728 case OFIELD: 729 return field(np, 0); 730 case OBUILTIN: 731 switch (np->u.subop) { 732 case BVA_START: 733 l = rhs(l); 734 code(ASVSTAR, NULL, l, NULL); 735 case BVA_END: 736 return NULL; 737 case BVA_ARG: 738 l = rhs(l); 739 tmp = tmpnode(tp); 740 code(ASVARG, tmp, l, NULL); 741 return tmp; 742 default: 743 abort(); 744 } 745 default: 746 abort(); 747 } 748 abort(); 749 } 750 751 static Node * 752 cgen(Node *np) 753 { 754 Node aux, *p, *next; 755 756 setlabel(np->label); 757 switch (np->op) { 758 case OBFUN: 759 return function(); 760 case ONOP: 761 case OBLOOP: 762 case OELOOP: 763 case OEFUN: 764 break; 765 case OJMP: 766 label2node(&aux, np->u.sym); 767 code(ASJMP, NULL, &aux, NULL); 768 break; 769 case OBRANCH: 770 next = np->next; 771 if (!next->label) 772 next->label = newlabel(); 773 bool(np->left, np->u.sym, next->label); 774 break; 775 case ORET: 776 p = (np->left) ? rhs(np->left) : NULL; 777 code(ASRET, NULL, p, NULL); 778 break; 779 case OBSWITCH: 780 p = rhs(np->left); 781 swtch(p); 782 break; 783 default: 784 rhs(np); 785 break; 786 } 787 return NULL; 788 } 789 790 static Node * 791 norm(Node *np) 792 { 793 int op = np->op; 794 Node *p, *dst, *next = np->next; 795 Symbol *sym, *osym; 796 797 switch (op) { 798 case OEFUN: 799 /* 800 * In QBE we need at the end of a basic block 801 * a jump, so we have to ensure that the last 802 * statement of the function is a ret, a jmp 803 * or a branch. In the same way, QBE does 804 * not accept labels at the end of a function 805 * (ONOP is used for labels) so we have to add 806 * a ret there, and in the case of branches 807 * we need a label for the next statement 808 */ 809 op = (np->prev) ? np->prev->op : 0; 810 if (!op || op == ONOP || op == OBRANCH || (op != ORET && op != OJMP)) 811 addstmt(node(ORET), KEEPCUR); 812 break; 813 case OBRANCH: 814 if (!next->label) { 815 sym = getsym(TMPSYM); 816 sym->kind = SLABEL; 817 next->label = sym; 818 } 819 case OJMP: 820 for (;;) { 821 dst = np->u.sym->u.stmt; 822 if (dst->op != OJMP) 823 break; 824 np->u.sym = dst->u.sym; 825 } 826 for (p = np->next; p; p = p->next) { 827 if (p == dst) 828 return NULL; 829 if (p->op == ONOP || 830 p->op == OBLOOP || 831 p->op == OELOOP) { 832 continue; 833 } 834 break; 835 } 836 break; 837 } 838 return np; 839 } 840 841 void 842 genasm(void) 843 { 844 apply(norm); 845 apply(cgen); 846 }