sys/src/cmd/2c/sgen.c

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