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