sys/src/cmd/5c/peep.c

   1 #include "gc.h"
   2
   3 int xtramodes(Reg*, Adr*);
   4
   5 void
   6 peep(void)
   7 {
   8         Reg *r, *r1, *r2;
   9         Prog *p, *p1;
  10         int t;
  11 /*
  12  * complete R structure
  13  */
  14         t = 0;
  15         for(r=firstr; r!=R; r=r1) {
  16                 r1 = r->link;
  17                 if(r1 == R)
  18                         break;
  19                 p = r->prog->link;
  20                 while(p != r1->prog)
  21                 switch(p->as) {
  22                 default:
  23                         r2 = rega();
  24                         r->link = r2;
  25                         r2->link = r1;
  26
  27                         r2->prog = p;
  28                         r2->p1 = r;
  29                         r->s1 = r2;
  30                         r2->s1 = r1;
  31                         r1->p1 = r2;
  32
  33                         r = r2;
  34                         t++;
  35
  36                 case ADATA:
  37                 case AGLOBL:
  38                 case ANAME:
  39                 case ASIGNAME:
  40                         p = p->link;
  41                 }
  42         }
  43
  44 loop1:
  45         t = 0;
  46         for(r=firstr; r!=R; r=r->link) {
  47                 p = r->prog;
  48                 if(p->as == ASLL || p->as == ASRL || p->as == ASRA) {
  49                         /*
  50                          * elide shift into D_SHIFT operand of subsequent instruction
  51                          */
  52                         if(shiftprop(r)) {
  53                                 excise(r);
  54                                 t++;
  55                         }
  56                 }
  57                 if(p->as == AMOVW || p->as == AMOVF || p->as == AMOVD)
  58                 if(regtyp(&p->to)) {
  59                         if(p->from.type == D_CONST)
  60                                 constprop(&p->from, &p->to, r->s1);
  61                         else if(regtyp(&p->from))
  62                         if(p->from.type == p->to.type) {
  63                                 if(copyprop(r)) {
  64                                         excise(r);
  65                                         t++;
  66                                 } else
  67                                 if(subprop(r) && copyprop(r)) {
  68                                         excise(r);
  69                                         t++;
  70                                 }
  71                         }
  72                 }
  73         }
  74         if(t)
  75                 goto loop1;
  76         /*
  77          * look for MOVB x,R; MOVB R,R
  78          */
  79         for(r=firstr; r!=R; r=r->link) {
  80                 p = r->prog;
  81                 switch(p->as) {
  82                 default:
  83                         continue;
  84                 case AEOR:
  85                         /*
  86                          * EOR -1,x,y => MVN x,y
  87                          */
  88                         if(p->from.type == D_CONST && p->from.offset == -1) {
  89                                 p->as = AMVN;
  90                                 p->from.type = D_REG;
  91                                 if(p->reg != NREG)
  92                                         p->from.reg = p->reg;
  93                                 else
  94                                         p->from.reg = p->to.reg;
  95                                 p->reg = NREG;
  96                         }
  97                         continue;
  98                 case AMOVH:
  99                 case AMOVHU:
 100                 case AMOVB:
 101                 case AMOVBU:
 102                         if(p->to.type != D_REG)
 103                                 continue;
 104                         break;
 105                 }
 106                 r1 = r->link;
 107                 if(r1 == R)
 108                         continue;
 109                 p1 = r1->prog;
 110                 if(p1->as != p->as)
 111                         continue;
 112                 if(p1->from.type != D_REG || p1->from.reg != p->to.reg)
 113                         continue;
 114                 if(p1->to.type != D_REG || p1->to.reg != p->to.reg)
 115                         continue;
 116                 excise(r1);
 117         }
 118
 119         for(r=firstr; r!=R; r=r->link) {
 120                 p = r->prog;
 121                 switch(p->as) {
 122                 case AMOVW:
 123                 case AMOVB:
 124                 case AMOVBU:
 125                         if(p->from.type == D_OREG && p->from.offset == 0)
 126                                 xtramodes(r, &p->from);
 127                         else if(p->to.type == D_OREG && p->to.offset == 0)
 128                                 xtramodes(r, &p->to);
 129                         else
 130                                 continue;
 131                         break;
 132                 case ACMP:
 133                         /*
 134                          * elide CMP $0,x if calculation of x can set condition codes
 135                          */
 136                         if(p->from.type != D_CONST || p->from.offset != 0)
 137                                 continue;
 138                         r2 = r->s1;
 139                         if(r2 == R)
 140                                 continue;
 141                         t = r2->prog->as;
 142                         switch(t) {
 143                         default:
 144                                 continue;
 145                         case ABEQ:
 146                         case ABNE:
 147                         case ABMI:
 148                         case ABPL:
 149                                 break;
 150                         case ABGE:
 151                                 t = ABPL;
 152                                 break;
 153                         case ABLT:
 154                                 t = ABMI;
 155                                 break;
 156                         case ABHI:
 157                                 t = ABNE;
 158                                 break;
 159                         case ABLS:
 160                                 t = ABEQ;
 161                                 break;
 162                         }
 163                         r1 = r;
 164                         do
 165                                 r1 = uniqp(r1);
 166                         while (r1 != R && r1->prog->as == ANOP);
 167                         if(r1 == R)
 168                                 continue;
 169                         p1 = r1->prog;
 170                         if(p1->to.type != D_REG)
 171                                 continue;
 172                         if(p1->to.reg != p->reg)
 173                         if(!(p1->as == AMOVW && p1->from.type == D_REG && p1->from.reg == p->reg))
 174                                 continue;
 175                         switch(p1->as) {
 176                         default:
 177                                 continue;
 178                         case AMOVW:
 179                                 if(p1->from.type != D_REG)
 180                                         continue;
 181                         case AAND:
 182                         case AEOR:
 183                         case AORR:
 184                         case ABIC:
 185                         case AMVN:
 186                         case ASUB:
 187                         case ARSB:
 188                         case AADD:
 189                         case AADC:
 190                         case ASBC:
 191                         case ARSC:
 192                                 break;
 193                         }
 194                         p1->scond |= C_SBIT;
 195                         r2->prog->as = t;
 196                         excise(r);
 197                         continue;
 198                 }
 199         }
 200
 201         predicate();
 202 }
 203
 204 void
 205 excise(Reg *r)
 206 {
 207         Prog *p;
 208
 209         p = r->prog;
 210         p->as = ANOP;
 211         p->scond = zprog.scond;
 212         p->from = zprog.from;
 213         p->to = zprog.to;
 214         p->reg = zprog.reg; /**/
 215 }
 216
 217 Reg*
 218 uniqp(Reg *r)
 219 {
 220         Reg *r1;
 221
 222         r1 = r->p1;
 223         if(r1 == R) {
 224                 r1 = r->p2;
 225                 if(r1 == R || r1->p2link != R)
 226                         return R;
 227         } else
 228                 if(r->p2 != R)
 229                         return R;
 230         return r1;
 231 }
 232
 233 Reg*
 234 uniqs(Reg *r)
 235 {
 236         Reg *r1;
 237
 238         r1 = r->s1;
 239         if(r1 == R) {
 240                 r1 = r->s2;
 241                 if(r1 == R)
 242                         return R;
 243         } else
 244                 if(r->s2 != R)
 245                         return R;
 246         return r1;
 247 }
 248
 249 int
 250 regtyp(Adr *a)
 251 {
 252
 253         if(a->type == D_REG)
 254                 return 1;
 255         if(a->type == D_FREG)
 256                 return 1;
 257         return 0;
 258 }
 259
 260 /*
 261  * the idea is to substitute
 262  * one register for another
 263  * from one MOV to another
 264  *      MOV     a, R0
 265  *      ADD     b, R0   / no use of R1
 266  *      MOV     R0, R1
 267  * would be converted to
 268  *      MOV     a, R1
 269  *      ADD     b, R1
 270  *      MOV     R1, R0
 271  * hopefully, then the former or latter MOV
 272  * will be eliminated by copy propagation.
 273  */
 274 int
 275 subprop(Reg *r0)
 276 {
 277         Prog *p;
 278         Adr *v1, *v2;
 279         Reg *r;
 280         int t;
 281
 282         p = r0->prog;
 283         v1 = &p->from;
 284         if(!regtyp(v1))
 285                 return 0;
 286         v2 = &p->to;
 287         if(!regtyp(v2))
 288                 return 0;
 289         for(r=uniqp(r0); r!=R; r=uniqp(r)) {
 290                 if(uniqs(r) == R)
 291                         break;
 292                 p = r->prog;
 293                 switch(p->as) {
 294                 case ABL:
 295                         return 0;
 296
 297                 case ACMP:
 298                 case ACMN:
 299                 case AADD:
 300                 case ASUB:
 301                 case ARSB:
 302                 case ASLL:
 303                 case ASRL:
 304                 case ASRA:
 305                 case AORR:
 306                 case AAND:
 307                 case AEOR:
 308                 case AMUL:
 309                 case ADIV:
 310                 case ADIVU:
 311
 312                 case ACMPF:
 313                 case ACMPD:
 314                 case AADDD:
 315                 case AADDF:
 316                 case ASUBD:
 317                 case ASUBF:
 318                 case AMULD:
 319                 case AMULF:
 320                 case ADIVD:
 321                 case ADIVF:
 322                         if(p->to.type == v1->type)
 323                         if(p->to.reg == v1->reg) {
 324                                 if(p->reg == NREG)
 325                                         p->reg = p->to.reg;
 326                                 goto gotit;
 327                         }
 328                         break;
 329
 330                 case AMOVF:
 331                 case AMOVD:
 332                 case AMOVW:
 333                         if(p->to.type == v1->type)
 334                         if(p->to.reg == v1->reg)
 335                                 goto gotit;
 336                         break;
 337
 338                 case AMOVM:
 339                         t = 1<<v2->reg;
 340                         if((p->from.type == D_CONST && (p->from.offset&t)) ||
 341                            (p->to.type == D_CONST && (p->to.offset&t)))
 342                                 return 0;
 343                         break;
 344                 }
 345                 if(copyau(&p->from, v2) ||
 346                    copyau1(p, v2) ||
 347                    copyau(&p->to, v2))
 348                         break;
 349                 if(copysub(&p->from, v1, v2, 0) ||
 350                    copysub1(p, v1, v2, 0) ||
 351                    copysub(&p->to, v1, v2, 0))
 352                         break;
 353         }
 354         return 0;
 355
 356 gotit:
 357         copysub(&p->to, v1, v2, 1);
 358         if(debug['P']) {
 359                 print("gotit: %D->%D\n%P", v1, v2, r->prog);
 360                 if(p->from.type == v2->type)
 361                         print(" excise");
 362                 print("\n");
 363         }
 364         for(r=uniqs(r); r!=r0; r=uniqs(r)) {
 365                 p = r->prog;
 366                 copysub(&p->from, v1, v2, 1);
 367                 copysub1(p, v1, v2, 1);
 368                 copysub(&p->to, v1, v2, 1);
 369                 if(debug['P'])
 370                         print("%P\n", r->prog);
 371         }
 372         t = v1->reg;
 373         v1->reg = v2->reg;
 374         v2->reg = t;
 375         if(debug['P'])
 376                 print("%P last\n", r->prog);
 377         return 1;
 378 }
 379
 380 /*
 381  * The idea is to remove redundant copies.
 382  *      v1->v2  F=0
 383  *      (use v2 s/v2/v1/)*
 384  *      set v1  F=1
 385  *      use v2  return fail
 386  *      -----------------
 387  *      v1->v2  F=0
 388  *      (use v2 s/v2/v1/)*
 389  *      set v1  F=1
 390  *      set v2  return success
 391  */
 392 int
 393 copyprop(Reg *r0)
 394 {
 395         Prog *p;
 396         Adr *v1, *v2;
 397         Reg *r;
 398
 399         p = r0->prog;
 400         v1 = &p->from;
 401         v2 = &p->to;
 402         if(copyas(v1, v2))
 403                 return 1;
 404         for(r=firstr; r!=R; r=r->link)
 405                 r->active = 0;
 406         return copy1(v1, v2, r0->s1, 0);
 407 }
 408
 409 int
 410 copy1(Adr *v1, Adr *v2, Reg *r, int f)
 411 {
 412         int t;
 413         Prog *p;
 414
 415         if(r->active) {
 416                 if(debug['P'])
 417                         print("act set; return 1\n");
 418                 return 1;
 419         }
 420         r->active = 1;
 421         if(debug['P'])
 422                 print("copy %D->%D f=%d\n", v1, v2, f);
 423         for(; r != R; r = r->s1) {
 424                 p = r->prog;
 425                 if(debug['P'])
 426                         print("%P", p);
 427                 if(!f && uniqp(r) == R) {
 428                         f = 1;
 429                         if(debug['P'])
 430                                 print("; merge; f=%d", f);
 431                 }
 432                 t = copyu(p, v2, A);
 433                 switch(t) {
 434                 case 2: /* rar, cant split */
 435                         if(debug['P'])
 436                                 print("; %Drar; return 0\n", v2);
 437                         return 0;
 438
 439                 case 3: /* set */
 440                         if(debug['P'])
 441                                 print("; %Dset; return 1\n", v2);
 442                         return 1;
 443
 444                 case 1: /* used, substitute */
 445                 case 4: /* use and set */
 446                         if(f) {
 447                                 if(!debug['P'])
 448                                         return 0;
 449                                 if(t == 4)
 450                                         print("; %Dused+set and f=%d; return 0\n", v2, f);
 451                                 else
 452                                         print("; %Dused and f=%d; return 0\n", v2, f);
 453                                 return 0;
 454                         }
 455                         if(copyu(p, v2, v1)) {
 456                                 if(debug['P'])
 457                                         print("; sub fail; return 0\n");
 458                                 return 0;
 459                         }
 460                         if(debug['P'])
 461                                 print("; sub%D/%D", v2, v1);
 462                         if(t == 4) {
 463                                 if(debug['P'])
 464                                         print("; %Dused+set; return 1\n", v2);
 465                                 return 1;
 466                         }
 467                         break;
 468                 }
 469                 if(!f) {
 470                         t = copyu(p, v1, A);
 471                         if(!f && (t == 2 || t == 3 || t == 4)) {
 472                                 f = 1;
 473                                 if(debug['P'])
 474                                         print("; %Dset and !f; f=%d", v1, f);
 475                         }
 476                 }
 477                 if(debug['P'])
 478                         print("\n");
 479                 if(r->s2)
 480                         if(!copy1(v1, v2, r->s2, f))
 481                                 return 0;
 482         }
 483         return 1;
 484 }
 485
 486 /*
 487  * The idea is to remove redundant constants.
 488  *      $c1->v1
 489  *      ($c1->v2 s/$c1/v1)*
 490  *      set v1  return
 491  * The v1->v2 should be eliminated by copy propagation.
 492  */
 493 void
 494 constprop(Adr *c1, Adr *v1, Reg *r)
 495 {
 496         Prog *p;
 497
 498         if(debug['C'])
 499                 print("constprop %D->%D\n", c1, v1);
 500         for(; r != R; r = r->s1) {
 501                 p = r->prog;
 502                 if(debug['C'])
 503                         print("%P", p);
 504                 if(uniqp(r) == R) {
 505                         if(debug['C'])
 506                                 print("; merge; return\n");
 507                         return;
 508                 }
 509                 if(p->as == AMOVW && copyas(&p->from, c1)) {
 510                                 if(debug['C'])
 511                                         print("; sub%D/%D", &p->from, v1);
 512                                 p->from = *v1;
 513                 } else if(copyu(p, v1, A) > 1) {
 514                         if(debug['C'])
 515                                 print("; %Dset; return\n", v1);
 516                         return;
 517                 }
 518                 if(debug['C'])
 519                         print("\n");
 520                 if(r->s2)
 521                         constprop(c1, v1, r->s2);
 522         }
 523 }
 524
 525 /*
 526  * ASLL x,y,w
 527  * .. (not use w, not set x y w)
 528  * AXXX w,a,b (a != w)
 529  * .. (not use w)
 530  * (set w)
 531  * ----------- changed to
 532  * ..
 533  * AXXX (x<<y),a,b
 534  * ..
 535  */
 536 #define FAIL(msg) { if(debug['H']) print("\t%s; FAILURE\n", msg); return 0; }
 537 int
 538 shiftprop(Reg *r)
 539 {
 540         Reg *r1;
 541         Prog *p, *p1, *p2;
 542         int n, o;
 543         Adr a;
 544
 545         p = r->prog;
 546         if(p->to.type != D_REG)
 547                 FAIL("BOTCH: result not reg");
 548         n = p->to.reg;
 549         a = zprog.from;
 550         if(p->reg != NREG && p->reg != p->to.reg) {
 551                 a.type = D_REG;
 552                 a.reg = p->reg;
 553         }
 554         if(debug['H'])
 555                 print("shiftprop\n%P", p);
 556         r1 = r;
 557         for(;;) {
 558                 /* find first use of shift result; abort if shift operands or result are changed */
 559                 r1 = uniqs(r1);
 560                 if(r1 == R)
 561                         FAIL("branch");
 562                 if(uniqp(r1) == R)
 563                         FAIL("merge");
 564                 p1 = r1->prog;
 565                 if(debug['H'])
 566                         print("\n%P", p1);
 567                 switch(copyu(p1, &p->to, A)) {
 568                 case 0: /* not used or set */
 569                         if((p->from.type == D_REG && copyu(p1, &p->from, A) > 1) ||
 570                            (a.type == D_REG && copyu(p1, &a, A) > 1))
 571                                 FAIL("args modified");
 572                         continue;
 573                 case 3: /* set, not used */
 574                         FAIL("BOTCH: noref");
 575                 }
 576                 break;
 577         }
 578         /* check whether substitution can be done */
 579         switch(p1->as) {
 580         default:
 581                 FAIL("non-dpi");
 582         case AAND:
 583         case AEOR:
 584         case AADD:
 585         case AADC:
 586         case AORR:
 587         case ASUB:
 588         case ARSB:
 589         case ASBC:
 590         case ARSC:
 591                 if(p1->reg == n || (p1->reg == NREG && p1->to.type == D_REG && p1->to.reg == n)) {
 592                         if(p1->from.type != D_REG)
 593                                 FAIL("can't swap");
 594                         p1->reg = p1->from.reg;
 595                         p1->from.reg = n;
 596                         switch(p1->as) {
 597                         case ASUB:
 598                                 p1->as = ARSB;
 599                                 break;
 600                         case ARSB:
 601                                 p1->as = ASUB;
 602                                 break;
 603                         case ASBC:
 604                                 p1->as = ARSC;
 605                                 break;
 606                         case ARSC:
 607                                 p1->as = ASBC;
 608                                 break;
 609                         }
 610                         if(debug['H'])
 611                                 print("\t=>%P", p1);
 612                 }
 613         case ABIC:
 614         case ACMP:
 615         case ACMN:
 616                 if(p1->reg == n)
 617                         FAIL("can't swap");
 618                 if(p1->reg == NREG && p1->to.reg == n)
 619                         FAIL("shift result used twice");
 620         case AMVN:
 621                 if(p1->from.type == D_SHIFT)
 622                         FAIL("shift result used in shift");
 623                 if(p1->from.type != D_REG || p1->from.reg != n)
 624                         FAIL("BOTCH: where is it used?");
 625                 break;
 626         }
 627         /* check whether shift result is used subsequently */
 628         p2 = p1;
 629         if(p1->to.reg != n)
 630         for (;;) {
 631                 r1 = uniqs(r1);
 632                 if(r1 == R)
 633                         FAIL("inconclusive");
 634                 p1 = r1->prog;
 635                 if(debug['H'])
 636                         print("\n%P", p1);
 637                 switch(copyu(p1, &p->to, A)) {
 638                 case 0: /* not used or set */
 639                         continue;
 640                 case 3: /* set, not used */
 641                         break;
 642                 default:/* used */
 643                         FAIL("reused");
 644                 }
 645                 break;
 646         }
 647         /* make the substitution */
 648         p2->from.type = D_SHIFT;
 649         p2->from.reg = NREG;
 650         o = p->reg;
 651         if(o == NREG)
 652                 o = p->to.reg;
 653         switch(p->from.type){
 654         case D_CONST:
 655                 o |= (p->from.offset&0x1f)<<7;
 656                 break;
 657         case D_REG:
 658                 o |= (1<<4) | (p->from.reg<<8);
 659                 break;
 660         }
 661         switch(p->as){
 662         case ASLL:
 663                 o |= 0<<5;
 664                 break;
 665         case ASRL:
 666                 o |= 1<<5;
 667                 break;
 668         case ASRA:
 669                 o |= 2<<5;
 670                 break;
 671         }
 672         p2->from.offset = o;
 673         if(debug['H'])
 674                 print("\t=>%P\tSUCCEED\n", p2);
 675         return 1;
 676 }
 677
 678 Reg*
 679 findpre(Reg *r, Adr *v)
 680 {
 681         Reg *r1;
 682
 683         for(r1=uniqp(r); r1!=R; r=r1,r1=uniqp(r)) {
 684                 if(uniqs(r1) != r)
 685                         return R;
 686                 switch(copyu(r1->prog, v, A)) {
 687                 case 1: /* used */
 688                 case 2: /* read-alter-rewrite */
 689                         return R;
 690                 case 3: /* set */
 691                 case 4: /* set and used */
 692                         return r1;
 693                 }
 694         }
 695         return R;
 696 }
 697
 698 Reg*
 699 findinc(Reg *r, Reg *r2, Adr *v)
 700 {
 701         Reg *r1;
 702         Prog *p;
 703
 704
 705         for(r1=uniqs(r); r1!=R && r1!=r2; r=r1,r1=uniqs(r)) {
 706                 if(uniqp(r1) != r)
 707                         return R;
 708                 switch(copyu(r1->prog, v, A)) {
 709                 case 0: /* not touched */
 710                         continue;
 711                 case 4: /* set and used */
 712                         p = r1->prog;
 713                         if(p->as == AADD)
 714                         if(p->from.type == D_CONST)
 715                         if(p->from.offset > -4096 && p->from.offset < 4096)
 716                                 return r1;
 717                 default:
 718                         return R;
 719                 }
 720         }
 721         return R;
 722 }
 723
 724 int
 725 nochange(Reg *r, Reg *r2, Prog *p)
 726 {
 727         Adr a[3];
 728         int i, n;
 729
 730         if(r == r2)
 731                 return 1;
 732         n = 0;
 733         if(p->reg != NREG && p->reg != p->to.reg) {
 734                 a[n].type = D_REG;
 735                 a[n++].reg = p->reg;
 736         }
 737         switch(p->from.type) {
 738         case D_SHIFT:
 739                 a[n].type = D_REG;
 740                 a[n++].reg = p->from.offset&0xf;
 741         case D_REG:
 742                 a[n].type = D_REG;
 743                 a[n++].reg = p->from.reg;
 744         }
 745         if(n == 0)
 746                 return 1;
 747         for(; r!=R && r!=r2; r=uniqs(r)) {
 748                 p = r->prog;
 749                 for(i=0; i<n; i++)
 750                         if(copyu(p, &a[i], A) > 1)
 751                                 return 0;
 752         }
 753         return 1;
 754 }
 755
 756 int
 757 findu1(Reg *r, Adr *v)
 758 {
 759         for(; r != R; r = r->s1) {
 760                 if(r->active)
 761                         return 0;
 762                 r->active = 1;
 763                 switch(copyu(r->prog, v, A)) {
 764                 case 1: /* used */
 765                 case 2: /* read-alter-rewrite */
 766                 case 4: /* set and used */
 767                         return 1;
 768                 case 3: /* set */
 769                         return 0;
 770                 }
 771                 if(r->s2)
 772                         if (findu1(r->s2, v))
 773                                 return 1;
 774         }
 775         return 0;
 776 }
 777
 778 int
 779 finduse(Reg *r, Adr *v)
 780 {
 781         Reg *r1;
 782
 783         for(r1=firstr; r1!=R; r1=r1->link)
 784                 r1->active = 0;
 785         return findu1(r, v);
 786 }
 787
 788 int
 789 xtramodes(Reg *r, Adr *a)
 790 {
 791         Reg *r1, *r2, *r3;
 792         Prog *p, *p1;
 793         Adr v;
 794
 795         p = r->prog;
 796         if(debug['h'] && p->as == AMOVB && p->from.type == D_OREG)      /* byte load */
 797                 return 0;
 798         v = *a;
 799         v.type = D_REG;
 800         r1 = findpre(r, &v);
 801         if(r1 != R) {
 802                 p1 = r1->prog;
 803                 if(p1->to.type == D_REG && p1->to.reg == v.reg)
 804                 switch(p1->as) {
 805                 case AADD:
 806                         if(p1->from.type == D_REG ||
 807                            (p1->from.type == D_SHIFT && (p1->from.offset&(1<<4)) == 0 &&
 808                             (p->as != AMOVB || (a == &p->from && (p1->from.offset&~0xf) == 0))) ||
 809                            (p1->from.type == D_CONST &&
 810                             p1->from.offset > -4096 && p1->from.offset < 4096))
 811                         if(nochange(uniqs(r1), r, p1)) {
 812                                 if(a != &p->from || v.reg != p->to.reg)
 813                                 if (finduse(r->s1, &v)) {
 814                                         if(p1->reg == NREG || p1->reg == v.reg)
 815                                                 /* pre-indexing */
 816                                                 p->scond |= C_WBIT;
 817                                         else return 0;
 818                                 }
 819                                 switch (p1->from.type) {
 820                                 case D_REG:
 821                                         /* register offset */
 822                                         a->type = D_SHIFT;
 823                                         a->offset = p1->from.reg;
 824                                         break;
 825                                 case D_SHIFT:
 826                                         /* scaled register offset */
 827                                         a->type = D_SHIFT;
 828                                 case D_CONST:
 829                                         /* immediate offset */
 830                                         a->offset = p1->from.offset;
 831                                         break;
 832                                 }
 833                                 if(p1->reg != NREG)
 834                                         a->reg = p1->reg;
 835                                 excise(r1);
 836                                 return 1;
 837                         }
 838                         break;
 839                 case AMOVW:
 840                         if(p1->from.type == D_REG)
 841                         if((r2 = findinc(r1, r, &p1->from)) != R) {
 842                         for(r3=uniqs(r2); r3->prog->as==ANOP; r3=uniqs(r3))
 843                                 ;
 844                         if(r3 == r) {
 845                                 /* post-indexing */
 846                                 p1 = r2->prog;
 847                                 a->reg = p1->to.reg;
 848                                 a->offset = p1->from.offset;
 849                                 p->scond |= C_PBIT;
 850                                 if(!finduse(r, &r1->prog->to))
 851                                         excise(r1);
 852                                 excise(r2);
 853                                 return 1;
 854                         }
 855                         }
 856                         break;
 857                 }
 858         }
 859         if(a != &p->from || a->reg != p->to.reg)
 860         if((r1 = findinc(r, R, &v)) != R) {
 861                 /* post-indexing */
 862                 p1 = r1->prog;
 863                 a->offset = p1->from.offset;
 864                 p->scond |= C_PBIT;
 865                 excise(r1);
 866                 return 1;
 867         }
 868         return 0;
 869 }
 870
 871 /*
 872  * return
 873  * 1 if v only used (and substitute),
 874  * 2 if read-alter-rewrite
 875  * 3 if set
 876  * 4 if set and used
 877  * 0 otherwise (not touched)
 878  */
 879 int
 880 copyu(Prog *p, Adr *v, Adr *s)
 881 {
 882
 883         switch(p->as) {
 884
 885         default:
 886                 if(debug['P'])
 887                         print(" (???)");
 888                 return 2;
 889
 890         case AMOVM:
 891                 if(v->type != D_REG)
 892                         return 0;
 893                 if(p->from.type == D_CONST) {   /* read reglist, read/rar */
 894                         if(s != A) {
 895                                 if(p->from.offset&(1<<v->reg))
 896                                         return 1;
 897                                 if(copysub(&p->to, v, s, 1))
 898                                         return 1;
 899                                 return 0;
 900                         }
 901                         if(copyau(&p->to, v)) {
 902                                 if(p->scond&C_WBIT)
 903                                         return 2;
 904                                 return 1;
 905                         }
 906                         if(p->from.offset&(1<<v->reg))
 907                                 return 1;
 908                 } else {                        /* read/rar, write reglist */
 909                         if(s != A) {
 910                                 if(p->to.offset&(1<<v->reg))
 911                                         return 1;
 912                                 if(copysub(&p->from, v, s, 1))
 913                                         return 1;
 914                                 return 0;
 915                         }
 916                         if(copyau(&p->from, v)) {
 917                                 if(p->scond&C_WBIT)
 918                                         return 2;
 919                                 if(p->to.offset&(1<<v->reg))
 920                                         return 4;
 921                                 return 1;
 922                         }
 923                         if(p->to.offset&(1<<v->reg))
 924                                 return 3;
 925                 }
 926                 return 0;
 927
 928         case ANOP:      /* read, write */
 929         case AMOVW:
 930         case AMOVF:
 931         case AMOVD:
 932         case AMOVH:
 933         case AMOVHU:
 934         case AMOVB:
 935         case AMOVBU:
 936         case AMOVDW:
 937         case AMOVWD:
 938         case AMOVFD:
 939         case AMOVDF:
 940                 if(p->scond&(C_WBIT|C_PBIT))
 941                 if(v->type == D_REG) {
 942                         if(p->from.type == D_OREG || p->from.type == D_SHIFT) {
 943                                 if(p->from.reg == v->reg)
 944                                         return 2;
 945                         } else {
 946                                 if(p->to.reg == v->reg)
 947                                 return 2;
 948                         }
 949                 }
 950                 if(s != A) {
 951                         if(copysub(&p->from, v, s, 1))
 952                                 return 1;
 953                         if(!copyas(&p->to, v))
 954                                 if(copysub(&p->to, v, s, 1))
 955                                         return 1;
 956                         return 0;
 957                 }
 958                 if(copyas(&p->to, v)) {
 959                         if(copyau(&p->from, v))
 960                                 return 4;
 961                         return 3;
 962                 }
 963                 if(copyau(&p->from, v))
 964                         return 1;
 965                 if(copyau(&p->to, v))
 966                         return 1;
 967                 return 0;
 968
 969
 970         case AADD:      /* read, read, write */
 971         case ASUB:
 972         case ARSB:
 973         case ASLL:
 974         case ASRL:
 975         case ASRA:
 976         case AORR:
 977         case AAND:
 978         case AEOR:
 979         case AMUL:
 980         case ADIV:
 981         case ADIVU:
 982         case AADDF:
 983         case AADDD:
 984         case ASUBF:
 985         case ASUBD:
 986         case AMULF:
 987         case AMULD:
 988         case ADIVF:
 989         case ADIVD:
 990
 991         case ACMPF:
 992         case ACMPD:
 993         case ACMP:
 994         case ACMN:
 995         case ACASE:
 996                 if(s != A) {
 997                         if(copysub(&p->from, v, s, 1))
 998                                 return 1;
 999                         if(copysub1(p, v, s, 1))
1000                                 return 1;
1001                         if(!copyas(&p->to, v))
1002                                 if(copysub(&p->to, v, s, 1))
1003                                         return 1;
1004                         return 0;
1005                 }
1006                 if(copyas(&p->to, v)) {
1007                         if(p->reg == NREG)
1008                                 p->reg = p->to.reg;
1009                         if(copyau(&p->from, v))
1010                                 return 4;
1011                         if(copyau1(p, v))
1012                                 return 4;
1013                         return 3;
1014                 }
1015                 if(copyau(&p->from, v))
1016                         return 1;
1017                 if(copyau1(p, v))
1018                         return 1;
1019                 if(copyau(&p->to, v))
1020                         return 1;
1021                 return 0;
1022
1023         case ABEQ:      /* read, read */
1024         case ABNE:
1025         case ABCS:
1026         case ABHS:
1027         case ABCC:
1028         case ABLO:
1029         case ABMI:
1030         case ABPL:
1031         case ABVS:
1032         case ABVC:
1033         case ABHI:
1034         case ABLS:
1035         case ABGE:
1036         case ABLT:
1037         case ABGT:
1038         case ABLE:
1039                 if(s != A) {
1040                         if(copysub(&p->from, v, s, 1))
1041                                 return 1;
1042                         return copysub1(p, v, s, 1);
1043                 }
1044                 if(copyau(&p->from, v))
1045                         return 1;
1046                 if(copyau1(p, v))
1047                         return 1;
1048                 return 0;
1049
1050         case AB:        /* funny */
1051                 if(s != A) {
1052                         if(copysub(&p->to, v, s, 1))
1053                                 return 1;
1054                         return 0;
1055                 }
1056                 if(copyau(&p->to, v))
1057                         return 1;
1058                 return 0;
1059
1060         case ARET:      /* funny */
1061                 if(v->type == D_REG)
1062                 if(v->reg == REGRET)
1063                         return 2;
1064                 if(v->type == D_FREG)
1065                 if(v->reg == FREGRET)
1066                         return 2;
1067
1068         case ABL:       /* funny */
1069                 if(v->type == D_REG) {
1070                         if(v->reg <= REGEXT && v->reg > exregoffset)
1071                                 return 2;
1072                         if(v->reg == (uchar)REGARG)
1073                                 return 2;
1074                 }
1075                 if(v->type == D_FREG)
1076                         if(v->reg <= FREGEXT && v->reg > exfregoffset)
1077                                 return 2;
1078
1079                 if(s != A) {
1080                         if(copysub(&p->to, v, s, 1))
1081                                 return 1;
1082                         return 0;
1083                 }
1084                 if(copyau(&p->to, v))
1085                         return 4;
1086                 return 3;
1087
1088         case ATEXT:     /* funny */
1089                 if(v->type == D_REG)
1090                         if(v->reg == (uchar)REGARG)
1091                                 return 3;
1092                 return 0;
1093         }
1094 }
1095
1096 int
1097 a2type(Prog *p)
1098 {
1099
1100         switch(p->as) {
1101
1102         case ACMP:
1103         case ACMN:
1104
1105         case AADD:
1106         case ASUB:
1107         case ARSB:
1108         case ASLL:
1109         case ASRL:
1110         case ASRA:
1111         case AORR:
1112         case AAND:
1113         case AEOR:
1114         case AMUL:
1115         case ADIV:
1116         case ADIVU:
1117                 return D_REG;
1118
1119         case ACMPF:
1120         case ACMPD:
1121
1122         case AADDF:
1123         case AADDD:
1124         case ASUBF:
1125         case ASUBD:
1126         case AMULF:
1127         case AMULD:
1128         case ADIVF:
1129         case ADIVD:
1130                 return D_FREG;
1131         }
1132         return D_NONE;
1133 }
1134
1135 /*
1136  * direct reference,
1137  * could be set/use depending on
1138  * semantics
1139  */
1140 int
1141 copyas(Adr *a, Adr *v)
1142 {
1143
1144         if(regtyp(v)) {
1145                 if(a->type == v->type)
1146                 if(a->reg == v->reg)
1147                         return 1;
1148         } else if(v->type == D_CONST) {         /* for constprop */
1149                 if(a->type == v->type)
1150                 if(a->name == v->name)
1151                 if(a->sym == v->sym)
1152                 if(a->reg == v->reg)
1153                 if(a->offset == v->offset)
1154                         return 1;
1155         }
1156         return 0;
1157 }
1158
1159 /*
1160  * either direct or indirect
1161  */
1162 int
1163 copyau(Adr *a, Adr *v)
1164 {
1165
1166         if(copyas(a, v))
1167                 return 1;
1168         if(v->type == D_REG) {
1169                 if(a->type == D_OREG) {
1170                         if(v->reg == a->reg)
1171                                 return 1;
1172                 } else if(a->type == D_SHIFT) {
1173                         if((a->offset&0xf) == v->reg)
1174                                 return 1;
1175                         if((a->offset&(1<<4)) && (a->offset>>8) == v->reg)
1176                                 return 1;
1177                 }
1178         }
1179         return 0;
1180 }
1181
1182 int
1183 copyau1(Prog *p, Adr *v)
1184 {
1185
1186         if(regtyp(v)) {
1187                 if(a2type(p) == v->type)
1188                 if(p->reg == v->reg) {
1189                         if(a2type(p) != v->type)
1190                                 print("botch a2type %P\n", p);
1191                         return 1;
1192                 }
1193         }
1194         return 0;
1195 }
1196
1197 /*
1198  * substitute s for v in a
1199  * return failure to substitute
1200  */
1201 int
1202 copysub(Adr *a, Adr *v, Adr *s, int f)
1203 {
1204
1205         if(f)
1206         if(copyau(a, v)) {
1207                 if(a->type == D_SHIFT) {
1208                         if((a->offset&0xf) == v->reg)
1209                                 a->offset = (a->offset&~0xf)|s->reg;
1210                         if((a->offset&(1<<4)) && (a->offset>>8) == v->reg)
1211                                 a->offset = (a->offset&~(0xf<<8))|(s->reg<<8);
1212                 } else
1213                         a->reg = s->reg;
1214         }
1215         return 0;
1216 }
1217
1218 int
1219 copysub1(Prog *p1, Adr *v, Adr *s, int f)
1220 {
1221
1222         if(f)
1223         if(copyau1(p1, v))
1224                 p1->reg = s->reg;
1225         return 0;
1226 }
1227
1228 struct {
1229         int opcode;
1230         int notopcode;
1231         int scond;
1232         int notscond;
1233 } predinfo[]  = {
1234         { ABEQ, ABNE,   0x0,    0x1, },
1235         { ABNE, ABEQ,   0x1,    0x0, },
1236         { ABCS, ABCC,   0x2,    0x3, },
1237         { ABHS, ABLO,   0x2,    0x3, },
1238         { ABCC, ABCS,   0x3,    0x2, },
1239         { ABLO, ABHS,   0x3,    0x2, },
1240         { ABMI, ABPL,   0x4,    0x5, },
1241         { ABPL, ABMI,   0x5,    0x4, },
1242         { ABVS, ABVC,   0x6,    0x7, },
1243         { ABVC, ABVS,   0x7,    0x6, },
1244         { ABHI, ABLS,   0x8,    0x9, },
1245         { ABLS, ABHI,   0x9,    0x8, },
1246         { ABGE, ABLT,   0xA,    0xB, },
1247         { ABLT, ABGE,   0xB,    0xA, },
1248         { ABGT, ABLE,   0xC,    0xD, },
1249         { ABLE, ABGT,   0xD,    0xC, },
1250 };
1251
1252 typedef struct {
1253         Reg *start;
1254         Reg *last;
1255         Reg *end;
1256         int len;
1257 } Joininfo;
1258
1259 enum {
1260         Join,
1261         Split,
1262         End,
1263         Branch,
1264         Setcond,
1265         Toolong
1266 };
1267
1268 enum {
1269         Falsecond,
1270         Truecond,
1271         Delbranch,
1272         Keepbranch
1273 };
1274
1275 int
1276 isbranch(Prog *p)
1277 {
1278         return (ABEQ <= p->as) && (p->as <= ABLE);
1279 }
1280
1281 int
1282 predicable(Prog *p)
1283 {
1284         if (isbranch(p)
1285                 || p->as == ANOP
1286                 || p->as == AXXX
1287                 || p->as == ADATA
1288                 || p->as == AGLOBL
1289                 || p->as == AGOK
1290                 || p->as == AHISTORY
1291                 || p->as == ANAME
1292                 || p->as == ASIGNAME
1293                 || p->as == ATEXT
1294                 || p->as == AWORD
1295                 || p->as == ADYNT
1296                 || p->as == AINIT
1297                 || p->as == ABCASE
1298                 || p->as == ACASE)
1299                 return 0;
1300         return 1;
1301 }
1302
1303 /*
1304  * Depends on an analysis of the encodings performed by 5l.
1305  * These seem to be all of the opcodes that lead to the "S" bit
1306  * being set in the instruction encodings.
1307  *
1308  * C_SBIT may also have been set explicitly in p->scond.
1309  */
1310 int
1311 modifiescpsr(Prog *p)
1312 {
1313         return (p->scond&C_SBIT)
1314                 || p->as == ATST
1315                 || p->as == ATEQ
1316                 || p->as == ACMN
1317                 || p->as == ACMP
1318                 || p->as == AMULU
1319                 || p->as == ADIVU
1320                 || p->as == AMUL
1321                 || p->as == ADIV
1322                 || p->as == AMOD
1323                 || p->as == AMODU
1324                 || p->as == ABL;
1325 }
1326
1327 /*
1328  * Find the maximal chain of instructions starting with r which could
1329  * be executed conditionally
1330  */
1331 int
1332 joinsplit(Reg *r, Joininfo *j)
1333 {
1334         j->start = r;
1335         j->last = r;
1336         j->len = 0;
1337         do {
1338                 if (r->p2 && (r->p1 || r->p2->p2link)) {
1339                         j->end = r;
1340                         return Join;
1341                 }
1342                 if (r->s1 && r->s2) {
1343                         j->end = r;
1344                         return Split;
1345                 }
1346                 j->last = r;
1347                 if (r->prog->as != ANOP)
1348                         j->len++;
1349                 if (!r->s1 && !r->s2) {
1350                         j->end = r->link;
1351                         return End;
1352                 }
1353                 if (r->s2) {
1354                         j->end = r->s2;
1355                         return Branch;
1356                 }
1357                 if (modifiescpsr(r->prog)) {
1358                         j->end = r->s1;
1359                         return Setcond;
1360                 }
1361                 r = r->s1;
1362         } while (j->len < 4);
1363         j->end = r;
1364         return Toolong;
1365 }
1366
1367 Reg *
1368 successor(Reg *r)
1369 {
1370         if (r->s1)
1371                 return r->s1;
1372         else
1373                 return r->s2;
1374 }
1375
1376 void
1377 applypred(Reg *rstart, Joininfo *j, int cond, int branch)
1378 {
1379         int pred;
1380         Reg *r;
1381
1382         if(j->len == 0)
1383                 return;
1384         if (cond == Truecond)
1385                 pred = predinfo[rstart->prog->as - ABEQ].scond;
1386         else
1387                 pred = predinfo[rstart->prog->as - ABEQ].notscond;
1388
1389         for (r = j->start; ; r = successor(r)) {
1390                 if (r->prog->as == AB) {
1391                         if (r != j->last || branch == Delbranch)
1392                                 excise(r);
1393                         else {
1394                           if (cond == Truecond)
1395                                 r->prog->as = predinfo[rstart->prog->as - ABEQ].opcode;
1396                           else
1397                                 r->prog->as = predinfo[rstart->prog->as - ABEQ].notopcode;
1398                         }
1399                 }
1400                 else if (predicable(r->prog))
1401                         r->prog->scond = (r->prog->scond&~C_SCOND)|pred;
1402                 if (r->s1 != r->link) {
1403                         r->s1 = r->link;
1404                         r->link->p1 = r;
1405                 }
1406                 if (r == j->last)
1407                         break;
1408         }
1409 }
1410
1411 void
1412 predicate(void)
1413 {
1414         Reg *r;
1415         int t1, t2;
1416         Joininfo j1, j2;
1417
1418         for(r=firstr; r!=R; r=r->link) {
1419                 if (isbranch(r->prog)) {
1420                         t1 = joinsplit(r->s1, &j1);
1421                         t2 = joinsplit(r->s2, &j2);
1422                         if(j1.last->link != j2.start)
1423                                 continue;
1424                         if(j1.end == j2.end)
1425                         if((t1 == Branch && (t2 == Join || t2 == Setcond)) ||
1426                            (t2 == Join && (t1 == Join || t1 == Setcond))) {
1427                                 applypred(r, &j1, Falsecond, Delbranch);
1428                                 applypred(r, &j2, Truecond, Delbranch);
1429                                 excise(r);
1430                                 continue;
1431                         }
1432                         if(t1 == End || t1 == Branch) {
1433                                 applypred(r, &j1, Falsecond, Keepbranch);
1434                                 excise(r);
1435                                 continue;
1436                         }
1437                 }
1438         }
1439 }