sys/src/cmd/7c/peep.c

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