sys/src/cmd/7l/noop.c

   1 #include        "l.h"
   2
   3 Prog    *divuconst(Prog *, uvlong, int, int, int);
   4 Prog    *divconst(Prog *, vlong, int, int, int);
   5 Prog    *modconst(Prog *, vlong, int, int, int);
   6 void    excise(Prog *);
   7
   8 void
   9 noops(void)
  10 {
  11         Prog *p, *p1, *q, *q1, *q2;
  12         int o, curframe, curbecome, maxbecome, shift;
  13
  14         /*
  15          * find leaf subroutines
  16          * become sizes
  17          * frame sizes
  18          * strip NOPs
  19          * expand RET and other macros
  20          * expand BECOME pseudo
  21          * use conditional moves where appropriate
  22          */
  23
  24         if(debug['v'])
  25                 Bprint(&bso, "%5.2f noops\n", cputime());
  26         Bflush(&bso);
  27
  28         curframe = 0;
  29         curbecome = 0;
  30         maxbecome = 0;
  31         curtext = 0;
  32
  33         q = P;
  34         for(p = firstp; p != P; p = p->link) {
  35
  36                 /* find out how much arg space is used in this TEXT */
  37                 if(p->to.type == D_OREG && p->to.reg == REGSP)
  38                         if(p->to.offset > curframe)
  39                                 curframe = p->to.offset;
  40
  41                 switch(p->as) {
  42                 case ATEXT:
  43                         if(curtext && curtext->from.sym) {
  44                                 curtext->from.sym->frame = curframe;
  45                                 curtext->from.sym->become = curbecome;
  46                                 if(curbecome > maxbecome)
  47                                         maxbecome = curbecome;
  48                         }
  49                         curframe = 0;
  50                         curbecome = 0;
  51
  52                         p->mark |= LABEL|LEAF|SYNC;
  53                         if(p->link)
  54                                 p->link->mark |= LABEL;
  55                         curtext = p;
  56                         break;
  57
  58                 /* don't mess with what we don't understand */
  59                 case AWORD:
  60                 case ACALL_PAL:
  61                 /* etc. */
  62                         p->mark |= LABEL;
  63                         for(q1=p->link; q1 != P; q1 = q1->link) {
  64                                 q1->mark |= LABEL;
  65                                 if(q1->as != AXORNOT)           /* used as NOP in PALcode */
  66                                         break;
  67                         }
  68                         break;
  69
  70                 case ARET:
  71                         /* special form of RET is BECOME */
  72                         if(p->from.type == D_CONST)
  73                                 if(p->from.offset > curbecome)
  74                                         curbecome = p->from.offset;
  75
  76                         if(p->link != P)
  77                                 p->link->mark |= LABEL;
  78                         break;
  79
  80                 case ANOP:
  81                         q1 = p->link;
  82                         q->link = q1;           /* q is non-nop */
  83                         q1->mark |= p->mark;
  84                         continue;
  85
  86                 case AJSR:
  87                         if(curtext != P)
  88                                 curtext->mark &= ~LEAF;
  89                 case ABEQ:
  90                 case ABNE:
  91                 case ABGE:
  92                 case ABGT:
  93                 case ABLE:
  94                 case ABLT:
  95                 case ABLBC:
  96                 case ABLBS:
  97                 case AFBEQ:
  98                 case AFBNE:
  99                 case AFBGE:
 100                 case AFBGT:
 101                 case AFBLE:
 102                 case AFBLT:
 103                 case AJMP:
 104                         p->mark |= BRANCH;
 105                         q1 = p->cond;
 106                         if(q1 != P) {
 107                                 while(q1->as == ANOP) {
 108                                         q1 = q1->link;
 109                                         p->cond = q1;
 110                                 }
 111                                 if(!(q1->mark & LEAF)) {
 112                                         if (q1->mark & LABEL)
 113                                                 q1->mark |= LABEL2;
 114                                         else
 115                                                 q1->mark |= LABEL;
 116                                 }
 117                         } else
 118                                 p->mark |= LABEL;
 119                         q1 = p->link;
 120                         if(q1 != P) {
 121                                 if (q1->mark & LABEL)
 122                                         q1->mark |= LABEL2;
 123                                 else
 124                                         q1->mark |= LABEL;
 125                         }
 126                         else
 127                                 p->mark |= LABEL;       /* ??? */
 128                         break;
 129
 130                 case ADIVQ:
 131                 case ADIVQU:
 132                 case AMODQ:
 133                 case AMODQU:
 134                 case ADIVL:
 135                 case ADIVLU:
 136                 case AMODL:
 137                 case AMODLU:
 138                         if(p->from.type == D_CONST /*&& !debug['d']*/)
 139                                 continue;
 140                         if(prog_divq == P)
 141                                 initdiv();
 142                         if(curtext != P)
 143                                 curtext->mark &= ~LEAF;
 144                         break;
 145                 }
 146                 q = p;
 147         }
 148
 149         if(curtext && curtext->from.sym) {
 150                 curtext->from.sym->frame = curframe;
 151                 curtext->from.sym->become = curbecome;
 152                 if(curbecome > maxbecome)
 153                         maxbecome = curbecome;
 154         }
 155
 156         if(debug['b'])
 157                 print("max become = %d\n", maxbecome);
 158         xdefine("ALEFbecome", STEXT, maxbecome);
 159
 160         curtext = 0;
 161         for(p = firstp; p != P; p = p->link) {
 162                 switch(p->as) {
 163                 case ATEXT:
 164                         curtext = p;
 165                         break;
 166                 case AJSR:
 167                         if(curtext != P && curtext->from.sym != S && curtext->to.offset >= 0) {
 168                                 o = maxbecome - curtext->from.sym->frame;
 169                                 if(o <= 0)
 170                                         break;
 171                                 /* calling a become or calling a variable */
 172                                 if(p->to.sym == S || p->to.sym->become) {
 173                                         curtext->to.offset += o;
 174                                         if(debug['b']) {
 175                                                 curp = p;
 176                                                 print("%D calling %D increase %d\n",
 177                                                         &curtext->from, &p->to, o);
 178                                         }
 179                                 }
 180                         }
 181                         break;
 182                 }
 183         }
 184
 185         for(p = firstp; p != P; p = p->link) {
 186                 o = p->as;
 187                 switch(o) {
 188                 case ATEXT:
 189                         curtext = p;
 190                         autosize = p->to.offset + 8;
 191                         if(autosize <= 8)
 192                         if(curtext->mark & LEAF) {
 193                                 p->to.offset = -8;
 194                                 autosize = 0;
 195                         }
 196                         if (autosize & 4)
 197                                 autosize += 4;
 198
 199                         q = p;
 200                         if(autosize)
 201                                 q = genIRR(p, ASUBQ, autosize, NREG, REGSP);
 202                         else if(!(curtext->mark & LEAF)) {
 203                                 if(debug['v'])
 204                                         Bprint(&bso, "save suppressed in: %s\n",
 205                                                 curtext->from.sym->name);
 206                                 Bflush(&bso);
 207                                 curtext->mark |= LEAF;
 208                         }
 209
 210                         if(curtext->mark & LEAF) {
 211                                 if(curtext->from.sym)
 212                                         curtext->from.sym->type = SLEAF;
 213                                 break;
 214                         }
 215
 216                         genstore(q, AMOVL, REGLINK, 0LL, REGSP);
 217                         break;
 218
 219                 case ARET:
 220                         nocache(p);
 221                         if(p->from.type == D_CONST)
 222                                 goto become;
 223                         if(curtext->mark & LEAF) {
 224                                 if(!autosize) {
 225                                         p->as = AJMP;
 226                                         p->from = zprg.from;
 227                                         p->to.type = D_OREG;
 228                                         p->to.offset = 0;
 229                                         p->to.reg = REGLINK;
 230                                         break;
 231                                 }
 232
 233                                 p->as = AADDQ;
 234                                 p->from.type = D_CONST;
 235                                 p->from.offset = autosize;
 236                                 p->to.type = D_REG;
 237                                 p->to.reg = REGSP;
 238
 239                                 q = prg();
 240                                 q->as = AJMP;
 241                                 q->line = p->line;
 242                                 q->to.type = D_OREG;
 243                                 q->to.offset = 0;
 244                                 q->to.reg = REGLINK;
 245                                 q->mark |= BRANCH;
 246
 247                                 q->link = p->link;
 248                                 p->link = q;
 249                                 break;
 250                         }
 251                         p->as = AMOVL;
 252                         p->from.type = D_OREG;
 253                         p->from.offset = 0;
 254                         p->from.reg = REGSP;
 255                         p->to.type = D_REG;
 256                         p->to.reg = REGLINK;
 257
 258                         q = p;
 259                         if(autosize)
 260                                 q = genIRR(p, AADDQ, autosize, NREG, REGSP);
 261
 262                         q1 = prg();
 263                         q1->as = AJMP;
 264                         q1->line = p->line;
 265                         q1->to.type = D_OREG;
 266                         q1->to.offset = 0;
 267                         q1->to.reg = REGLINK;
 268                         q1->mark |= BRANCH;
 269
 270                         q1->link = q->link;
 271                         q->link = q1;
 272                         break;
 273
 274                 become:
 275                         if(curtext->mark & LEAF) {
 276
 277                                 q = prg();
 278                                 q->line = p->line;
 279                                 q->as = AJMP;
 280                                 q->from = zprg.from;
 281                                 q->to = p->to;
 282                                 q->cond = p->cond;
 283                                 q->link = p->link;
 284                                 q->mark |= BRANCH;
 285                                 p->link = q;
 286
 287                                 p->as = AADDQ;
 288                                 p->from = zprg.from;
 289                                 p->from.type = D_CONST;
 290                                 p->from.offset = autosize;
 291                                 p->to = zprg.to;
 292                                 p->to.type = D_REG;
 293                                 p->to.reg = REGSP;
 294
 295                                 break;
 296                         }
 297                         q = prg();
 298                         q->line = p->line;
 299                         q->as = AJMP;
 300                         q->from = zprg.from;
 301                         q->to = p->to;
 302                         q->cond = p->cond;
 303                         q->link = p->link;
 304                         q->mark |= BRANCH;
 305                         p->link = q;
 306
 307                         q = genIRR(p, AADDQ, autosize, NREG, REGSP);
 308
 309                         p->as = AMOVL;
 310                         p->from = zprg.from;
 311                         p->from.type = D_OREG;
 312                         p->from.offset = 0;
 313                         p->from.reg = REGSP;
 314                         p->to = zprg.to;
 315                         p->to.type = D_REG;
 316                         p->to.reg = REGLINK;
 317
 318                         break;
 319
 320
 321                 /* All I wanted was a MOVB... */
 322                 case AMOVB:
 323                 case AMOVW:
 324                         /* rewrite sign extend; could use v3 extension in asmout case 1 */
 325                         if (p->to.type == D_REG) {
 326                                 nocache(p);
 327                                 shift = (p->as == AMOVB) ? (64-8) : (64-16);
 328                                 if (p->from.type == D_REG) {
 329                                         p->as = ASLLQ;
 330                                         p->reg = p->from.reg;
 331                                         p->from.type = D_CONST;
 332                                         p->from.offset = shift;
 333                                         q = genIRR(p, ASRAQ, shift, p->to.reg, p->to.reg);
 334                                         break;
 335                                 }
 336                                 else {
 337                                         p->as = (p->as == AMOVB) ? AMOVBU : AMOVWU;
 338                                         q = genIRR(p, ASLLQ, shift, p->to.reg, p->to.reg);
 339                                         q = genIRR(q, ASRAQ, shift, p->to.reg, p->to.reg);
 340                                 }
 341                         }
 342                         /* fall through... */
 343                 case AMOVBU:
 344                 case AMOVWU:
 345                         if(!debug['x'])
 346                                 break;          /* use BWX extension */
 347                         o = p->as;
 348                         nocache(p);
 349                         if (p->from.type == D_OREG) {
 350                                 if (p->to.type != D_REG)
 351                                         break;
 352                                 p->as = AMOVQU;
 353                                 q = genXXX(p, AEXTBL, &p->to, REGTMP2, &p->to);
 354                                 if (o == AMOVW || o == AMOVWU)
 355                                         q->as = AEXTWL;
 356                                 p->to.reg = REGTMP2;
 357                                 if ((p->from.offset & 7) != 0 || aclass(&p->from) != C_SOREG) {
 358                                         q1 = genXXX(p, AMOVA, &p->from, NREG, &q->to);
 359                                         q1->from.offset &= 7;
 360                                         q->from = q->to;
 361                                 }
 362                                 else
 363                                         q->from.reg = p->from.reg;
 364                                 if (o == AMOVB || o == AMOVW)
 365                                         genXXX(q, o, &q->to, NREG, &q->to);
 366                         }
 367                         else if (p->to.type == D_OREG) {
 368                                 if (aclass(&p->from) == C_ZCON) {
 369                                         p->from.type = D_REG;
 370                                         p->from.reg = REGZERO;
 371                                 }
 372                                 else if (p->from.type != D_REG)
 373                                         break;
 374                                 p->as = AMOVQU;
 375                                 q = genRRR(p, AMSKBL, p->to.reg, REGTMP2, REGTMP2);
 376                                 q1 = genRRR(q, AINSBL, p->to.reg, p->from.reg, REGTMP);
 377                                 if (o == AMOVW || o == AMOVWU) {
 378                                         q->as = AMSKWL;
 379                                         q1->as = AINSWL;
 380                                 }
 381                                 q2 = genXXX(q1, AOR, &q->to, REGTMP, &q->to);
 382                                 genXXX(q2, AMOVQU, &q->to, NREG, &p->to);
 383                                 p->from = p->to;
 384                                 p->to = q->to;
 385                                 if ((p->from.offset & 7) != 0 || aclass(&p->from) != C_SOREG) {
 386                                         q->from.reg = REGTMP;
 387                                         q1->from.reg = REGTMP;
 388                                         q = genXXX(p, AMOVA, &p->from, NREG, &q->from);
 389                                         q->from.offset &= 7;
 390                                 }
 391                         }
 392                         break;
 393
 394                 case ASLLL:
 395                         p->as = ASLLQ;
 396                         p = genXXX(p, AADDL, &p->to, REGZERO, &p->to);
 397                         break;
 398
 399                 case ASRLL:
 400                         if (p->to.type != D_REG) {
 401                                 diag("illegal dest type in %P", p);
 402                                 break;
 403                         }
 404                         if (p->reg == NREG)
 405                                 p->reg = p->to.reg;
 406
 407                         q = genXXX(p, ASRLQ, &p->from, REGTMP, &p->to);
 408
 409                         p->as = AZAP;
 410                         p->from.type = D_CONST;
 411                         p->from.offset = 0xf0;
 412                         p->to.reg = REGTMP;
 413                         p = q;
 414
 415                         p = genXXX(p, AADDL, &p->to, REGZERO, &p->to);
 416                         break;
 417
 418                 case ASRAL:
 419                         p->as = ASRAQ;
 420                         break;
 421
 422                 case ADIVQ:
 423                 case ADIVQU:
 424                 case AMODQ:
 425                 case AMODQU:
 426                 case ADIVL:
 427                 case ADIVLU:
 428                 case AMODL:
 429                 case AMODLU:
 430                         /* if (debug['d'])
 431                                 print("%P\n", p); */
 432                         if(p->to.type != D_REG)
 433                                 break;
 434                         /*if(debug['d'] && p->from.type == D_CONST) {
 435                                 q = genRRR(p, p->as, REGTMP, p->reg, p->to.reg);
 436                                 p->as = AMOVQ;
 437                                 p->reg = NREG;
 438                                 p->to.reg = REGTMP;
 439                                 p = q;
 440                         }*/
 441                         if(p->from.type == D_CONST) {
 442                                 if (p->reg == NREG)
 443                                         p->reg = p->to.reg;
 444                                 switch (p->as) {
 445                                 case ADIVQ:
 446                                         q = divconst(p, p->from.offset, p->reg, p->to.reg, 64);
 447                                         break;
 448                                 case ADIVQU:
 449                                         q = divuconst(p, p->from.offset, p->reg, p->to.reg, 64);
 450                                         break;
 451                                 case AMODQ:
 452                                         q = modconst(p, p->from.offset, p->reg, p->to.reg, 64);
 453                                         break;
 454                                 case AMODQU:
 455                                         q = divuconst(p, p->from.offset, p->reg, REGTMP2, 64);
 456                                         q = genIRR(q, AMULQ, p->from.offset, REGTMP2, REGTMP2);
 457                                         q = genRRR(q, ASUBQ, REGTMP2, p->reg, p->to.reg);
 458                                         break;
 459                                 case ADIVL:
 460                                         q = divconst(p, p->from.offset, p->reg, p->to.reg, 32);
 461                                         break;
 462                                 case ADIVLU:
 463                                         q = divuconst(p, p->from.offset, p->reg, p->to.reg, 32);
 464                                         break;
 465                                 case AMODL:
 466                                         q = modconst(p, p->from.offset, p->reg, p->to.reg, 32);
 467                                         break;
 468                                 case AMODLU:
 469                                         q = divuconst(p, p->from.offset, p->reg, REGTMP2, 32);
 470                                         q = genIRR(q, AMULQ, p->from.offset, REGTMP2, REGTMP2);
 471                                         q = genRRR(q, ASUBQ, REGTMP2, p->reg, p->to.reg);
 472                                         break;
 473                                 }
 474                                 excise(p);
 475                                 p = q;
 476                                 break;
 477                         }
 478                         if(p->from.type != D_REG){
 479                                 diag("bad instruction %P", p);
 480                                 break;
 481                         }
 482                         o = p->as;
 483                         q = genIRR(p, ASUBQ, 16LL, NREG, REGSP);
 484                         q = genstore(q, AMOVQ, p->from.reg, 8LL, REGSP);
 485                         if (o == ADIVL || o == ADIVL || o == AMODL || o == AMODLU)
 486                                 q->as = AMOVL;
 487
 488                         q = genRRR(q, AMOVQ, p->reg, NREG, REGTMP);
 489                         if (p->reg == NREG)
 490                                 q->from.reg = p->to.reg;
 491
 492                         /* CALL appropriate */
 493                         q1 = prg();
 494                         q1->link = q->link;
 495                         q->link = q1;
 496
 497                         q1->as = AJSR;
 498                         q1->line = p->line;
 499                         q1->to.type = D_BRANCH;
 500                         q1->cond = divsubr(o);
 501                         q1->mark |= BRANCH;
 502                         q = q1;
 503
 504                         q = genRRR(q, AMOVQ, REGTMP, NREG, p->to.reg);
 505                         q = genIRR(q, AADDQ, 16LL, NREG, REGSP);
 506                         excise(p);
 507                         p = q;
 508                         break;
 509
 510                 /* Attempt to replace {cond. branch, mov} with a cmov */
 511                 /* XXX warning: this is all a bit experimental */
 512                 case ABEQ:
 513                 case ABNE:
 514                 case ABGE:
 515                 case ABGT:
 516                 case ABLE:
 517                 case ABLT:
 518                 case ABLBC:
 519                 case ABLBS:
 520                         q = p->link;
 521                         if (q == P)
 522                                 break;
 523                         q1 = q->link;
 524                         if (q1 != p->cond || q1 == P)
 525                                 break;
 526 /*print("%P\n", q); /* */
 527                         if (q->to.type != D_REG)
 528                                 break;
 529                         if (q->from.type != D_REG && (q->from.type != D_CONST || q->from.name != D_NONE))
 530                                 break;
 531                         if (q->mark&LABEL2)
 532                                 break;
 533 /* print("%P\n", q); /* */
 534                         if (q->as != AMOVQ)             /* XXX can handle more than this! */
 535                                 break;
 536                         q->as = (p->as^1) + ACMOVEQ-ABEQ;       /* sleazy hack */
 537                         q->reg = p->from.reg;           /* XXX check CMOVx operand order! */
 538                         excise(p);              /* XXX p's LABEL? */
 539                         if (!(q1->mark&LABEL2))
 540                                 q1->mark &= ~LABEL;
 541                         break;
 542                 case AFBEQ:
 543                 case AFBNE:
 544                 case AFBGE:
 545                 case AFBGT:
 546                 case AFBLE:
 547                 case AFBLT:
 548                         q = p->link;
 549                         if (q == P)
 550                                 break;
 551                         q1 = q->link;
 552                         if (q1 != p->cond || q1 == P)
 553                                 break;
 554                         if (q->from.type != D_FREG || q->to.type != D_FREG)
 555                                 break;
 556 /* print("%P\n", q); /* */
 557                         if (q->mark&LABEL2)
 558                                 break;
 559                         if (q->as != AMOVT)             /* XXX can handle more than this! */
 560                                 break;
 561                         q->as = (p->as^1) + AFCMOVEQ-AFBEQ;     /* sleazy hack */
 562                         q->reg = p->from.reg;           /* XXX check CMOVx operand order! */
 563                         excise(p);              /* XXX p's LABEL? */
 564                         if (!(q1->mark&LABEL2))
 565                                 q1->mark &= ~LABEL;
 566                         break;
 567                 }
 568         }
 569
 570         curtext = P;
 571         q = P;          /* p - 1 */
 572         q1 = firstp;    /* top of block */
 573         o = 0;          /* count of instructions */
 574         for(p = firstp; p != P; p = p1) {
 575                 p1 = p->link;
 576                 o++;
 577                 if(p->mark & NOSCHED){
 578                         if(q1 != p){
 579                                 sched(q1, q);
 580                         }
 581                         for(; p != P; p = p->link){
 582                                 if(!(p->mark & NOSCHED))
 583                                         break;
 584                                 q = p;
 585                         }
 586                         p1 = p;
 587                         q1 = p;
 588                         o = 0;
 589                         continue;
 590                 }
 591                 if(p->mark & (LABEL|SYNC)) {
 592                         if(q1 != p)
 593                                 sched(q1, q);
 594                         q1 = p;
 595                         o = 1;
 596                 }
 597                 if(p->mark & (BRANCH|SYNC)) {
 598                         sched(q1, p);
 599                         q1 = p1;
 600                         o = 0;
 601                 }
 602                 if(o >= NSCHED) {
 603                         sched(q1, p);
 604                         q1 = p1;
 605                         o = 0;
 606                 }
 607                 q = p;
 608         }
 609 }
 610
 611 void
 612 nocache(Prog *p)
 613 {
 614         p->optab = 0;
 615         p->from.class = 0;
 616         p->to.class = 0;
 617 }
 618
 619 /* XXX use of this may lose important LABEL flags, check that this isn't happening (or fix) */
 620 void
 621 excise(Prog *p)
 622 {
 623         Prog *q;
 624
 625         q = p->link;
 626         *p = *q;
 627 }
 628
 629 void
 630 initdiv(void)
 631 {
 632         Sym *s1, *s2, *s3, *s4, *s5, *s6, *s7, *s8;
 633         Prog *p;
 634
 635         s1 = lookup("_divq", 0);
 636         s2 = lookup("_divqu", 0);
 637         s3 = lookup("_modq", 0);
 638         s4 = lookup("_modqu", 0);
 639         s5 = lookup("_divl", 0);
 640         s6 = lookup("_divlu", 0);
 641         s7 = lookup("_modl", 0);
 642         s8 = lookup("_modlu", 0);
 643         for(p = firstp; p != P; p = p->link)
 644                 if(p->as == ATEXT) {
 645                         if(p->from.sym == s1)
 646                                 prog_divq = p;
 647                         if(p->from.sym == s2)
 648                                 prog_divqu = p;
 649                         if(p->from.sym == s3)
 650                                 prog_modq = p;
 651                         if(p->from.sym == s4)
 652                                 prog_modqu = p;
 653                         if(p->from.sym == s5)
 654                                 prog_divl = p;
 655                         if(p->from.sym == s6)
 656                                 prog_divlu = p;
 657                         if(p->from.sym == s7)
 658                                 prog_modl = p;
 659                         if(p->from.sym == s8)
 660                                 prog_modlu = p;
 661                 }
 662         if(prog_divq == P) {
 663                 diag("undefined: %s", s1->name);
 664                 prog_divq = curtext;
 665         }
 666         if(prog_divqu == P) {
 667                 diag("undefined: %s", s2->name);
 668                 prog_divqu = curtext;
 669         }
 670         if(prog_modq == P) {
 671                 diag("undefined: %s", s3->name);
 672                 prog_modq = curtext;
 673         }
 674         if(prog_modqu == P) {
 675                 diag("undefined: %s", s4->name);
 676                 prog_modqu = curtext;
 677         }
 678         if(prog_divl == P) {
 679                 diag("undefined: %s", s5->name);
 680                 prog_divl = curtext;
 681         }
 682         if(prog_divlu == P) {
 683                 diag("undefined: %s", s6->name);
 684                 prog_divlu = curtext;
 685         }
 686         if(prog_modl == P) {
 687                 diag("undefined: %s", s7->name);
 688                 prog_modl = curtext;
 689         }
 690         if(prog_modlu == P) {
 691                 diag("undefined: %s", s8->name);
 692                 prog_modlu = curtext;
 693         }
 694 }
 695
 696 Prog *
 697 divsubr(int o)
 698 {
 699         switch(o) {
 700         case ADIVQ:
 701                 return prog_divq;
 702         case ADIVQU:
 703                 return prog_divqu;
 704         case AMODQ:
 705                 return prog_modq;
 706         case AMODQU:
 707                 return prog_modqu;
 708         case ADIVL:
 709                 return prog_divl;
 710         case ADIVLU:
 711                 return prog_divlu;
 712         case AMODL:
 713                 return prog_modl;
 714         case AMODLU:
 715                 return prog_modlu;
 716         default:
 717                 diag("bad op %A in divsubr", o);
 718                 return prog_modlu;
 719         }
 720 }
 721
 722 Prog*
 723 divuconst(Prog *p, uvlong y, int num, int quot, int bits)
 724 {
 725         int logy, i, shift;
 726         uvlong k, m, n, mult, tmp, msb;
 727
 728         if(num == NREG)
 729                 num = quot;
 730         if(y == 0) {
 731                 diag("division by zero");
 732                 return p;
 733         }
 734         if(y == 1)
 735                 return genRRR(p, AMOVQ, num, NREG, quot);
 736
 737         if(num == REGTMP || quot == REGTMP)
 738                 diag("bad register in divuconst");
 739
 740         tmp = y;
 741         for(logy = -1; tmp != 0; logy++)
 742                 tmp >>= 1;
 743
 744         msb = (1LL << (bits-1));
 745         if((y & (y-1)) == 0)            /* power of 2 */
 746                 return genIRR(p, ASRLQ, logy, num, quot);
 747         if(y > msb)
 748                 return genIRR(p, ACMPUGE, y, num, quot);
 749
 750         /* k = (-2^(bits+logy)) % y */
 751         m = msb/y;
 752         n = msb%y;
 753         if(debug['d'])
 754                 Bprint(&bso, "divuconst: y=%lld msb=%lld m=%lld n=%lld\n",
 755                         y, msb, m, n);
 756         for(i = 0; i <= logy; i++) {
 757                 m *= 2LL;
 758                 n *= 2LL;
 759                 if(n > y) {
 760                         m += 1LL;
 761                         n -= y;
 762                 }
 763         }
 764         if(debug['d'])
 765                 Bprint(&bso, "divuconst: y=%lld msb=%lld m=%lld n=%lld\n",
 766                         y, msb, m, n);
 767         k = y - n;
 768         if(k > (1LL << logy)) {
 769                 mult = 2LL*m + 1LL;
 770                 bits++;
 771         } else
 772                 mult = m + 1LL;
 773
 774         shift = bits + logy;
 775         if(debug['d'])
 776                 Bprint(&bso, "divuconst: y=%lld mult=%lld shift=%d bits=%d k=%lld\n",
 777                         y, mult, shift, bits, k);
 778         if(bits <= 32) {
 779                 p = genIRR(p, AMOVQ, mult, NREG, REGTMP);
 780                 p = genRRR(p, AEXTLL, REGZERO, num, quot);
 781                 p = genRRR(p, AMULQ, REGTMP, quot, quot);
 782                 p = genIRR(p, ASRLQ, shift, quot, quot);
 783                 p = genRRR(p, AADDL, quot, REGZERO, quot);
 784                 return p;
 785         }
 786         if(bits == 33) {
 787                 if(shift < 64) {
 788                         mult <<= (64-shift);
 789                         shift = 64;
 790                 }
 791                 p = genIRR(p, AMOVQ, mult, NREG, REGTMP);
 792                 p = genRRR(p, AEXTLL, REGZERO, num, quot);
 793                 p = genRRR(p, AUMULH, REGTMP, quot, quot);
 794                 if(shift != 64)
 795                         p = genIRR(p, ASRLQ, shift-64, quot, quot);
 796                 p = genRRR(p, AADDL, quot, REGZERO, quot);
 797                 return p;
 798         }
 799         if(bits <= 64) {
 800                 if(shift < 64) {
 801                         mult <<= (64-shift);
 802                         shift = 64;
 803                 }
 804                 p = genIRR(p, AMOVQ, mult, NREG, REGTMP);
 805                 p = genRRR(p, AUMULH, REGTMP, num, quot);
 806                 if(shift != 64)
 807                         p = genIRR(p, ASRLQ, shift-64, quot, quot);
 808                 return p;
 809         }
 810
 811         p = genIRR(p, AMOVQ, mult, NREG, REGTMP);
 812         p = genRRR(p, AUMULH, REGTMP, num, REGTMP);
 813         p = genRRR(p, AADDQ, num, REGTMP, quot);
 814         p = genRRR(p, ACMPUGT, REGTMP, quot, REGTMP);
 815         p = genIRR(p, ASLLQ, 128-shift, REGTMP, REGTMP);
 816         p = genIRR(p, ASRLQ, shift-64, quot, quot);
 817         p = genRRR(p, AADDQ, REGTMP, quot, quot);
 818         return p;
 819 }
 820
 821 Prog *
 822 divconst(Prog *p, vlong y, int num, int quot, int bits)
 823 {
 824         vlong yabs;
 825         Prog *q;
 826
 827         yabs = y;
 828         if (y < 0)
 829                 yabs = -y;
 830         q = genRRR(p, ASUBQ, num, REGZERO, REGTMP2);
 831         if (num != quot)
 832                 q = genRRR(q, AMOVQ, num, NREG, quot);
 833         q = genRRR(q, ACMOVGT, REGTMP2, REGTMP2, quot);
 834         q = divuconst(q, yabs, quot, quot, bits-1);
 835         q = genRRR(q, ASUBQ, quot, REGZERO, REGTMP);
 836         q = genRRR(q, (y < 0)? ACMOVLT: ACMOVGT, REGTMP, REGTMP2, quot);
 837         return q;
 838 }
 839
 840 Prog *
 841 modconst(Prog *p, vlong y, int num, int quot, int bits)
 842 {
 843         vlong yabs;
 844         Prog *q;
 845
 846         yabs = y;
 847         if (y < 0)
 848                 yabs = -y;
 849         q = genRRR(p, ASUBQ, num, REGZERO, REGTMP2);
 850         q = genRRR(q, ACMOVLT, num, REGTMP2, REGTMP2);
 851         q = divuconst(q, yabs, REGTMP2, REGTMP2, bits-1);
 852         q = genRRR(q, ASUBQ, REGTMP2, REGZERO, REGTMP);
 853         q = genRRR(q, ACMOVLT, REGTMP, num, REGTMP2);
 854         q = genIRR(q, AMULQ, yabs, REGTMP2, REGTMP2);
 855         q = genRRR(q, ASUBQ, REGTMP2, num, quot);
 856         return q;
 857 }
 858
 859 Prog *
 860 genXXX(Prog *q, int op, Adr *from, int reg, Adr *to)
 861 {
 862         Prog *p;
 863
 864         p = prg();
 865         p->as = op;
 866         p->line = q->line;
 867         p->from = *from;
 868         p->to = *to;
 869         p->reg = reg;
 870         p->link = q->link;
 871         q->link = p;
 872         return p;
 873 }
 874
 875 Prog *
 876 genRRR(Prog *q, int op, int from, int reg, int to)
 877 {
 878         Prog *p;
 879
 880         p = prg();
 881         p->as = op;
 882         p->line = q->line;
 883         p->from.type = D_REG;
 884         p->from.reg = from;
 885         p->to.type = D_REG;
 886         p->to.reg = to;
 887         p->reg = reg;
 888         p->link = q->link;
 889         q->link = p;
 890         return p;
 891 }
 892
 893 Prog *
 894 genIRR(Prog *q, int op, vlong v, int reg, int to)
 895 {
 896         Prog *p;
 897
 898         p = prg();
 899         p->as = op;
 900         p->line = q->line;
 901         p->from.type = D_CONST;
 902         p->from.offset = v;
 903         p->to.type = D_REG;
 904         p->to.reg = to;
 905         p->reg = reg;
 906         p->link = q->link;
 907         q->link = p;
 908         return p;
 909 }
 910
 911 Prog *
 912 genstore(Prog *q, int op, int from, vlong offset, int to)
 913 {
 914         Prog *p;
 915
 916         p = prg();
 917         p->as = op;
 918         p->line = q->line;
 919         p->from.type = D_REG;
 920         p->from.reg = from;
 921         p->to.type = D_OREG;
 922         p->to.reg = to;
 923         p->to.offset = offset;
 924         p->reg = NREG;
 925         p->link = q->link;
 926         q->link = p;
 927         return p;
 928 }
 929
 930 Prog *
 931 genload(Prog *q, int op, vlong offset, int from, int to)
 932 {
 933         Prog *p;
 934
 935         p = prg();
 936         p->as = op;
 937         p->line = q->line;
 938         p->from.type = D_OREG;
 939         p->from.offset = offset;
 940         p->from.reg = from;
 941         p->to.type = D_REG;
 942         p->to.reg = to;
 943         p->reg = NREG;
 944         p->link = q->link;
 945         q->link = p;
 946         return p;
 947 }