util/opt/peephole.c

   1 #ifndef NORCSID
   2 static char rcsid[] = "$Id: peephole.c,v 2.17 1994/06/24 10:40:38 ceriel Exp $";
   3 #endif
   4
   5 #include "param.h"
   6 #include "types.h"
   7 #include "tes.h"
   8 #include "assert.h"
   9 #include "line.h"
  10 #include "lookup.h"
  11 #include "proinf.h"
  12 #include "alloc.h"
  13 #include "pattern.h"
  14 #include <em_spec.h>
  15 #include <em_mnem.h>
  16 #include "optim.h"
  17 #include "ext.h"
  18
  19 /*
  20  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  21  * See the copyright notice in the ACK home directory, in the file "Copyright".
  22  *
  23  * Author: Hans van Staveren
  24  */
  25
  26 #undef CHK_HASH /* print numbers patterns are hashed to */
  27 #ifdef CHK_HASH
  28 #include <stdio.h>
  29 #endif
  30
  31 #define ILLHASH 0177777
  32 short pathash[256];     /* table of indices into pattern[] */
  33
  34 int opind = 0;          /* second index of next matrix */
  35 byte transl[op_plast-op_pfirst+1][3] = {
  36         /* LLP */       { op_LLP, op_lol, op_ldl },
  37         /* LEP */       { op_LEP, op_loe, op_lde },
  38         /* SLP */       { op_SLP, op_stl, op_sdl },
  39         /* SEP */       { op_SEP, op_ste, op_sde }
  40 };
  41
  42 opcheck(bp) register byte *bp; {
  43
  44         if (((*bp)&BMASK) >= op_pfirst)
  45                 *bp = transl[((*bp)&BMASK)-op_pfirst][opind];
  46 }
  47
  48 /*
  49  * The hashing method used is believed to be reasonably efficient.
  50  * A minor speed improvement could be obtained by keeping a boolean
  51  * array telling which opcode has any patterns starting with it.
  52  * Currently only about one third of the opcodes actually have a
  53  * pattern starting with it, but they are the most common ones.
  54  * Estimated improvement possible: about 2%
  55  */
  56
  57 hashpatterns() {
  58         short index;
  59         register byte *bp,*tp;
  60         register short i;
  61         unsigned short hashvalue;
  62         byte *save;
  63         int patlen;
  64
  65         if (pointersize == wordsize)
  66                 opind=1;
  67         else if (pointersize == 2*wordsize)
  68                 opind=2;
  69         index = lastind;        /* set by mktab */
  70         while (index != 0) {
  71                 bp = &pattern[index];
  72                 tp = &bp[PO_MATCH];
  73                 i = *tp++&BMASK;
  74                 if (i==BMASK) {
  75                         i = *tp++&BMASK;
  76                         i |= (*tp++&BMASK)<<8;
  77                 }
  78                 save = tp;
  79                 patlen = i;
  80                 while (i--)
  81                         opcheck(tp++);
  82                 if ((*tp++&BMASK)==BMASK)
  83                         tp += 2;
  84                 i = *tp++&BMASK;
  85                 if (i==BMASK) {
  86                         i = *tp++&BMASK;
  87                         i |= (*tp++&BMASK)<<8;
  88                 }
  89                 while (i--) {
  90                         opcheck(tp++);
  91                         if ((*tp++&BMASK)==BMASK)
  92                                 tp += 2;
  93                 }
  94
  95                 /*
  96                  * Now the special opcodes are filled
  97                  * in properly, we can hash the pattern
  98                  */
  99
 100                 hashvalue = 0;
 101                 tp = save;
 102                 switch(patlen) {
 103                 default:        /* 3 or more */
 104                         hashvalue = (hashvalue<<4)^(*tp++&BMASK);
 105                 case 2:
 106                         hashvalue = (hashvalue<<4)^(*tp++&BMASK);
 107                 case 1:
 108                         hashvalue = (hashvalue<<4)^(*tp++&BMASK);
 109                 }
 110                 assert(hashvalue!= ILLHASH);
 111                 i=index;
 112                 index = (bp[PO_NEXT]&BMASK)|(bp[PO_NEXT+1]<<8);
 113                 bp[PO_HASH] = hashvalue>>8;
 114                 hashvalue &= BMASK;
 115                 bp[PO_NEXT] = pathash[hashvalue]&BMASK;
 116                 bp[PO_NEXT+1] = pathash[hashvalue]>>8;
 117                 pathash[hashvalue] = i;
 118 #ifdef CHK_HASH
 119                 fprintf(stderr,"%d\n",hashvalue);
 120 #endif
 121         }
 122 }
 123
 124 peephole() {
 125         static bool phashed = FALSE;
 126
 127         if (!phashed) {
 128                 hashpatterns();
 129                 phashed=TRUE;
 130         }
 131         return optimize();
 132 }
 133
 134 optimize() {
 135         register num_p *npp,np;
 136         register instr;
 137         bool madeopt;
 138
 139         madeopt = basicblock(&instrs);
 140         for (npp=curpro.numhash;npp< &curpro.numhash[NNUMHASH]; npp++)
 141                 for (np = *npp; np != (num_p) 0; np=np->n_next) {
 142                         if (! np->n_line) continue;
 143                         if(np->n_line->l_next == (line_p) 0)
 144                                 continue;
 145                         instr = np->n_line->l_next->l_instr&BMASK;
 146                         if (instr == op_lab || instr == op_bra)
 147                                 np->n_repl = np->n_line->l_next->l_a.la_np;
 148                         else
 149                                 if (basicblock(&np->n_line->l_next))
 150                                         madeopt = TRUE;
 151                 }
 152         return madeopt;
 153 }
 154
 155 offset oabs(off) offset off; {
 156
 157         return(off >= 0 ? off : -off);
 158 }
 159
 160 line_p repline(ev,patlen) eval_t ev; {
 161         register line_p lp;
 162         register iarg_p iap;
 163         register sym_p sp;
 164         offset diff,newdiff;
 165
 166         assert(ev.e_typ != EV_UNDEF);
 167         switch(ev.e_typ) {
 168         case EV_CONST:
 169                 if ((short) ev.e_v.e_con == ev.e_v.e_con) {
 170                         if (CANMINI((short) ev.e_v.e_con))
 171                                 lp = newline((short) (ev.e_v.e_con)+Z_OPMINI);
 172                         else {
 173                                 lp = newline(OPSHORT);
 174                                 lp->l_a.la_short = (short) ev.e_v.e_con;
 175                         }
 176                 } else {
 177                         lp = newline(OPOFFSET);
 178                         lp->l_a.la_offset = ev.e_v.e_con;
 179                 }
 180                 return(lp);
 181         case EV_NUMLAB:
 182                 lp = newline(OPNUMLAB);
 183                 lp->l_a.la_np = ev.e_v.e_np;
 184                 return(lp);
 185         default:        /* fragment + offset */
 186                 /*
 187                  * There is a slight problem here, because we have to
 188                  * map fragment+offset to symbol+offset.
 189                  * Fortunately the fragment we have must be the fragment
 190                  * of one of the symbols in the matchpattern.
 191                  * So a short search should do the job.
 192                  */
 193                 sp = (sym_p) 0;
 194                 for (iap= &iargs[patlen-1]; iap >= iargs; iap--)
 195                         if (iap->ia_ev.e_typ == ev.e_typ) {
 196                                 /*
 197                                  * Although lint complains, diff is not used
 198                                  * before set.
 199                                  *
 200                                  * The proof is left as an exercise to the
 201                                  * reader.
 202                                  */
 203                                 newdiff = oabs(iap->ia_sp->s_value-ev.e_v.e_con);
 204                                 if (sp==(sym_p) 0 || newdiff < diff) {
 205                                         sp = iap->ia_sp;
 206                                         diff = newdiff;
 207                                 }
 208                         }
 209                 assert(sp != (sym_p) 0);
 210                 if (diff == 0) {
 211                         lp = newline(OPSYMBOL);
 212                         lp->l_a.la_sp = sp;
 213                 } else {
 214                         diff = ev.e_v.e_con - sp->s_value;
 215                         if ((short) diff == diff) {
 216                                 lp = newline(OPSVAL);
 217                                 lp->l_a.la_sval.lasv_short = (short) diff;
 218                                 lp->l_a.la_sval.lasv_sp = sp;
 219                         } else {
 220                                 lp = newline(OPLVAL);
 221                                 lp->l_a.la_lval.lalv_offset = diff;
 222                                 lp->l_a.la_lval.lalv_sp = sp;
 223                         }
 224                 }
 225                 return(lp);
 226         }
 227 }
 228
 229 offset rotate(w,amount) offset w,amount; {
 230         offset highmask,lowmask;
 231
 232 #ifndef LONGOFF
 233         assert(wordsize<=4);
 234 #endif
 235         highmask = (offset)(-1) << amount;
 236         lowmask = ~highmask;
 237         if (wordsize != 4)
 238                 highmask &= wordsize==2 ? 0xFFFF : 0xFF;
 239         return(((w<<amount)&highmask)|((w>>(8*wordsize-amount))&lowmask));
 240 }
 241
 242 eval_t undefres = { EV_UNDEF };
 243
 244 eval_t compute(pexp) register expr_p pexp; {
 245         eval_t leaf1,leaf2,res;
 246         register i;
 247         register sym_p sp;
 248         offset mask;
 249
 250         switch(nparam[pexp->ex_operator]) {
 251         default:
 252                 assert(FALSE);
 253         case 2:
 254                 leaf2 = compute(&enodes[pexp->ex_rnode]);
 255                 if (leaf2.e_typ == EV_UNDEF ||
 256                     nonumlab[pexp->ex_operator] && leaf2.e_typ == EV_NUMLAB ||
 257                     onlyconst[pexp->ex_operator] && leaf2.e_typ != EV_CONST)
 258                         return(undefres);
 259         case 1:
 260                 leaf1 = compute(&enodes[pexp->ex_lnode]);
 261                 if (leaf1.e_typ == EV_UNDEF ||
 262                     nonumlab[pexp->ex_operator] && leaf1.e_typ == EV_NUMLAB ||
 263                     onlyconst[pexp->ex_operator] && leaf1.e_typ != EV_CONST)
 264                         return(undefres);
 265         case 0:
 266                 break;
 267         }
 268
 269         res.e_typ = EV_CONST;
 270         res.e_v.e_con = 0;
 271         switch(pexp->ex_operator) {
 272         default:
 273                 assert(FALSE);
 274         case EX_CON:
 275                 res.e_v.e_con = (offset) pexp->ex_lnode;
 276                 break;
 277         case EX_ARG:
 278                 return(iargs[pexp->ex_lnode - 1].ia_ev);
 279         case EX_CMPEQ:
 280                 if (leaf1.e_typ != leaf2.e_typ)
 281                         return(undefres);
 282                 if (leaf1.e_typ == EV_NUMLAB) {
 283                         if (leaf1.e_v.e_np == leaf2.e_v.e_np)
 284                                 res.e_v.e_con = 1;
 285                         break;
 286                 }
 287                 if (leaf1.e_v.e_con == leaf2.e_v.e_con)
 288                         res.e_v.e_con = 1;
 289                 break;
 290         case EX_CMPNE:
 291                 if (leaf1.e_typ != leaf2.e_typ) {
 292                         res.e_v.e_con = 1;
 293                         break;
 294                 }
 295                 if (leaf1.e_typ == EV_NUMLAB) {
 296                         if (leaf1.e_v.e_np != leaf2.e_v.e_np)
 297                                 res.e_v.e_con = 1;
 298                         break;
 299                 }
 300                 if (leaf1.e_v.e_con != leaf2.e_v.e_con)
 301                         res.e_v.e_con = 1;
 302                 break;
 303         case EX_CMPGT:
 304                 if (leaf1.e_typ != leaf2.e_typ)
 305                         return(undefres);
 306                 res.e_v.e_con = leaf1.e_v.e_con > leaf2.e_v.e_con;
 307                 break;
 308         case EX_CMPGE:
 309                 if (leaf1.e_typ != leaf2.e_typ)
 310                         return(undefres);
 311                 res.e_v.e_con = leaf1.e_v.e_con >= leaf2.e_v.e_con;
 312                 break;
 313         case EX_CMPLT:
 314                 if (leaf1.e_typ != leaf2.e_typ)
 315                         return(undefres);
 316                 res.e_v.e_con = leaf1.e_v.e_con < leaf2.e_v.e_con;
 317                 break;
 318         case EX_CMPLE:
 319                 if (leaf1.e_typ != leaf2.e_typ)
 320                         return(undefres);
 321                 res.e_v.e_con = leaf1.e_v.e_con <= leaf2.e_v.e_con;
 322                 break;
 323         case EX_OR2:
 324                 if (leaf1.e_v.e_con != 0)
 325                         return(leaf1);
 326                 leaf2 = compute(&enodes[pexp->ex_rnode]);
 327                 if (leaf2.e_typ != EV_CONST)
 328                         return(undefres);
 329                 return(leaf2);
 330         case EX_AND2:
 331                 if (leaf1.e_v.e_con == 0)
 332                         return(leaf1);
 333                 leaf2 = compute(&enodes[pexp->ex_rnode]);
 334                 if (leaf2.e_typ != EV_CONST)
 335                         return(undefres);
 336                 return(leaf2);
 337         case EX_OR1:
 338                 res.e_v.e_con = leaf1.e_v.e_con | leaf2.e_v.e_con;
 339                 break;
 340         case EX_XOR1:
 341                 res.e_v.e_con = leaf1.e_v.e_con ^ leaf2.e_v.e_con;
 342                 break;
 343         case EX_AND1:
 344                 res.e_v.e_con = leaf1.e_v.e_con & leaf2.e_v.e_con;
 345                 break;
 346         case EX_TIMES:
 347                 res.e_v.e_con = leaf1.e_v.e_con * leaf2.e_v.e_con;
 348                 break;
 349         case EX_DIVIDE:
 350                 res.e_v.e_con = leaf1.e_v.e_con / leaf2.e_v.e_con;
 351                 break;
 352         case EX_MOD:
 353                 res.e_v.e_con = leaf1.e_v.e_con % leaf2.e_v.e_con;
 354                 break;
 355         case EX_LSHIFT:
 356                 res.e_v.e_con = leaf1.e_v.e_con << leaf2.e_v.e_con;
 357                 break;
 358         case EX_RSHIFT:
 359                 res.e_v.e_con = leaf1.e_v.e_con >> leaf2.e_v.e_con;
 360                 break;
 361         case EX_UMINUS:
 362                 res.e_v.e_con = -leaf1.e_v.e_con;
 363                 break;
 364         case EX_NOT:
 365                 res.e_v.e_con = !leaf1.e_v.e_con;
 366                 break;
 367         case EX_COMP:
 368                 res.e_v.e_con = ~leaf1.e_v.e_con;
 369                 break;
 370         case EX_PLUS:
 371                 if (leaf1.e_typ >= EV_FRAG) {
 372                         if (leaf2.e_typ >= EV_FRAG)
 373                                 return(undefres);
 374                         res.e_typ = leaf1.e_typ;
 375                 } else
 376                         res.e_typ = leaf2.e_typ;
 377                 res.e_v.e_con = leaf1.e_v.e_con + leaf2.e_v.e_con;
 378                 break;
 379         case EX_MINUS:
 380                 if (leaf1.e_typ >= EV_FRAG) {
 381                         if (leaf2.e_typ == EV_CONST)
 382                                 res.e_typ = leaf1.e_typ;
 383                         else if (leaf2.e_typ != leaf1.e_typ)
 384                                 return(undefres);
 385                 } else if (leaf2.e_typ >= EV_FRAG)
 386                         return(undefres);
 387                 res.e_v.e_con = leaf1.e_v.e_con - leaf2.e_v.e_con;
 388                 break;
 389         case EX_POINTERSIZE:
 390                 res.e_v.e_con = pointersize;
 391                 break;
 392         case EX_WORDSIZE:
 393                 res.e_v.e_con = wordsize;
 394                 break;
 395         case EX_NOTREG:
 396                 res.e_v.e_con = !inreg(leaf1.e_v.e_con);
 397                 break;
 398         case EX_DEFINED:
 399                 leaf1 = compute(&enodes[pexp->ex_lnode]);
 400                 res.e_v.e_con = leaf1.e_typ != EV_UNDEF;
 401                 break;
 402         case EX_SAMESIGN:
 403                 res.e_v.e_con = (leaf1.e_v.e_con ^ leaf2.e_v.e_con) >= 0;
 404                 break;
 405         case EX_ROM:
 406                 if ((sp = iargs[pexp->ex_lnode - 1].ia_sp) != (sym_p) 0 &&
 407                     sp->s_rom != (offset *) 0) {
 408                         leaf2 = compute(&enodes[pexp->ex_rnode]);
 409                         if (leaf2.e_typ != EV_CONST ||
 410                             leaf2.e_v.e_con < 0 ||
 411                             leaf2.e_v.e_con >= MAXROM)
 412                                 return(undefres);
 413                         res.e_v.e_con = sp->s_rom[(int)(leaf2.e_v.e_con)];
 414                         break;
 415                 } else
 416                         return(undefres);
 417         case EX_SFIT:
 418                 mask = 0;
 419                 for (i=leaf2.e_v.e_con - 1;i < 8*sizeof(offset); i++)
 420                         mask |= ((offset)1)<<i;
 421                 res.e_v.e_con = (leaf1.e_v.e_con&mask) == 0 ||
 422                                        (leaf1.e_v.e_con&mask) == mask;
 423                 break;
 424         case EX_UFIT:
 425                 mask = 0;
 426                 for (i=leaf2.e_v.e_con;i < 8*sizeof(offset); i++)
 427                         mask |= ((offset)1)<<i;
 428                 res.e_v.e_con = (leaf1.e_v.e_con&mask) == 0;
 429                 break;
 430         case EX_ROTATE:
 431                 res.e_v.e_con = rotate(leaf1.e_v.e_con,leaf2.e_v.e_con);
 432                 break;
 433         }
 434         return(res);
 435 }
 436
 437 #ifdef ALLOWSPECIAL
 438 extern bool special();
 439 #endif
 440
 441 bool tryrepl(lpp,bp,patlen)
 442 line_p *lpp;
 443 register byte *bp;
 444 int patlen;
 445 {
 446         int rpllen,instr,rplval;
 447         register line_p lp;
 448         line_p replacement,*rlpp,tp;
 449
 450         rpllen = *bp++&BMASK;
 451         if (rpllen == BMASK) {
 452                 rpllen = *bp++&BMASK;
 453                 rpllen |= (*bp++&BMASK)<<8;
 454         }
 455 #ifdef ALLOWSPECIAL
 456         if (rpllen == 1 && *bp == 0)
 457                 return(special(lpp,bp+1,patlen));
 458 #endif
 459         replacement = (line_p) 0;
 460         rlpp = &replacement;
 461         while (rpllen--) {
 462                 instr = *bp++&BMASK;
 463                 rplval = *bp++&BMASK;
 464                 if (rplval == BMASK) {
 465                         rplval = (*bp++&BMASK);
 466                         rplval |= (*bp++&BMASK)<<8;
 467                 }
 468                 if (rplval)
 469                         lp = repline(compute(&enodes[rplval]),patlen);
 470                 else
 471                         lp = newline(OPNO);
 472
 473                 /*
 474                  * One replacement instruction is generated,
 475                  * link in list and proceed with the next one.
 476                  */
 477
 478                 if (instr == op_lab)
 479                         lp->l_a.la_np->n_line = lp;
 480                 *rlpp = lp;
 481                 rlpp = &lp->l_next;
 482                 lp->l_instr = instr;
 483         }
 484
 485         /*
 486          * Replace instructions matched by the created replacement
 487          */
 488
 489
 490         OPTIM((bp[0]&BMASK)|(bp[1]&BMASK)<<8);
 491         for (lp= *lpp;patlen>0;patlen--,tp=lp,lp=lp->l_next)
 492                 ;
 493         tp->l_next = (line_p) 0;
 494         *rlpp = lp;
 495         lp = *lpp;
 496         *lpp = replacement;
 497         while ( lp != (line_p) 0 ) {
 498                 tp = lp->l_next;
 499                 oldline(lp);
 500                 lp = tp;
 501         }
 502         return(TRUE);
 503 }
 504
 505 bool trypat(lpp,bp,len)
 506 line_p *lpp;
 507 register byte *bp;
 508 int len;
 509 {
 510         register iarg_p iap;
 511         int i,patlen;
 512         register line_p lp;
 513         eval_t result;
 514
 515         patlen = *bp++&BMASK;
 516         if (patlen == BMASK) {
 517                 patlen = *bp++&BMASK;
 518                 patlen |= (*bp++&BMASK)<<8;
 519         }
 520         if (len == 3) {
 521                 if (patlen<3)
 522                         return(FALSE);
 523         } else {
 524                 if (patlen != len)
 525                         return(FALSE);
 526         }
 527
 528         /*
 529          * Length is ok, now check opcodes
 530          */
 531
 532         for (i=0,lp= *lpp;i<patlen && lp != (line_p) 0;i++,lp=lp->l_next)
 533                 if (lp->l_instr != *bp++)
 534                         return(FALSE);
 535         if (i != patlen)
 536                 return(FALSE);
 537
 538         /*
 539          * opcodes are also correct, now comes the hard part
 540          */
 541
 542         for(i=0,lp= *lpp,iap= iargs; i<patlen;i++,iap++,lp=lp->l_next) {
 543                 switch(lp->l_optyp) {
 544                 case OPNO:
 545                         iap->ia_ev.e_typ = EV_UNDEF;
 546                         break;
 547                 default:
 548                         iap->ia_ev.e_typ = EV_CONST;
 549                         iap->ia_ev.e_v.e_con = (lp->l_optyp&BMASK)-Z_OPMINI;
 550                         break;
 551                 case OPSHORT:
 552                         iap->ia_ev.e_typ = EV_CONST;
 553                         iap->ia_ev.e_v.e_con = lp->l_a.la_short;
 554                         break;
 555 #ifdef LONGOFF
 556                 case OPOFFSET:
 557                         iap->ia_ev.e_typ = EV_CONST;
 558                         iap->ia_ev.e_v.e_con = lp->l_a.la_offset;
 559                         break;
 560 #endif
 561                 case OPNUMLAB:
 562                         iap->ia_ev.e_typ = EV_NUMLAB;
 563                         iap->ia_ev.e_v.e_np = lp->l_a.la_np;
 564                         break;
 565                 case OPSYMBOL:
 566                         iap->ia_ev.e_typ = lp->l_a.la_sp->s_frag;
 567                         iap->ia_sp = lp->l_a.la_sp;
 568                         iap->ia_ev.e_v.e_con = lp->l_a.la_sp->s_value;
 569                         break;
 570                 case OPSVAL:
 571                         iap->ia_ev.e_typ = lp->l_a.la_sval.lasv_sp->s_frag;
 572                         iap->ia_sp = lp->l_a.la_sval.lasv_sp;
 573                         iap->ia_ev.e_v.e_con = lp->l_a.la_sval.lasv_sp->s_value + lp->l_a.la_sval.lasv_short;
 574                         break;
 575 #ifdef LONGOFF
 576                 case OPLVAL:
 577                         iap->ia_ev.e_typ = lp->l_a.la_lval.lalv_sp->s_frag;
 578                         iap->ia_sp = lp->l_a.la_lval.lalv_sp;
 579                         iap->ia_ev.e_v.e_con = lp->l_a.la_lval.lalv_sp->s_value + lp->l_a.la_lval.lalv_offset;
 580                         break;
 581 #endif
 582                 }
 583         }
 584         i = *bp++&BMASK;
 585         if ( i==BMASK ) {
 586                 i = *bp++&BMASK;
 587                 i |= (*bp++&BMASK)<<8;
 588         }
 589         if ( i != 0) {
 590                 /* there is a condition */
 591                 result = compute(&enodes[i]);
 592                 if (result.e_typ != EV_CONST || result.e_v.e_con == 0)
 593                         return(FALSE);
 594         }
 595         return(tryrepl(lpp,bp,patlen));
 596 }
 597
 598 int
 599 basicblock(alpp) line_p *alpp; {
 600         register line_p *lpp,lp;
 601         unsigned short hash[3];
 602         line_p *next;
 603         register byte *bp;
 604         int i;
 605         short index;
 606         bool madeopt;
 607         int count = 0;
 608
 609         lpp = alpp; madeopt = FALSE;
 610         while ((*lpp) != (line_p) 0 && ((*lpp)->l_instr&BMASK) != op_lab) {
 611                 lp = *lpp;
 612                 next = &lp->l_next;
 613                 hash[0] = lp->l_instr&BMASK;
 614                 lp=lp->l_next;
 615                 if (lp != (line_p) 0) {
 616                         hash[1] = (hash[0]<<4)^(lp->l_instr&BMASK);
 617                         lp=lp->l_next;
 618                         if (lp != (line_p) 0)
 619                                 hash[2] = (hash[1]<<4)^(lp->l_instr&BMASK);
 620                         else
 621                                 hash[2] = ILLHASH;
 622                 } else {
 623                         hash[1] = ILLHASH;
 624                         hash[2] = ILLHASH;
 625                 }
 626
 627                 /*
 628                  * hashvalues computed. Try for longest pattern first
 629                  */
 630
 631                 for (i=2;i>=0;i--) {
 632                     index = pathash[hash[i]&BMASK];
 633                     while (index != 0) {
 634                         bp = &pattern[index];
 635                         if((bp[PO_HASH]&BMASK) == (hash[i]>>8))
 636                             if(trypat(lpp,&bp[PO_MATCH],i+1)) {
 637                                 madeopt = TRUE;
 638                                 next = lpp;
 639                                 i = 0;  /* dirty way of double break */
 640                                 break;
 641                             }
 642                         index=(bp[PO_NEXT]&BMASK)|(bp[PO_NEXT+1]<<8);
 643                     }
 644                 }
 645                 if (lpp == next) {
 646                         count++;
 647                         if (count > 1000) {
 648                                 /* probably loop in table */
 649                                 fprintf(stderr, "Warning: possible loop in patterns; call an expert\n");
 650                                 next = &((*lpp)->l_next);
 651                                 count = 0;
 652                         }
 653                 }
 654                 else    count = 0;
 655                 lpp = next;
 656         }
 657         lpp = alpp;
 658         if (repl_muls) {
 659             while ((lp = *lpp) != (line_p) 0 && (lp->l_instr&BMASK) != op_lab) {
 660                 line_p b_repl, e_repl;
 661                 int cnt;
 662
 663                 if ((cnt = (lp->l_instr & BMASK)) != op_loc && cnt != op_ldc) {
 664                         lpp = &lp->l_next;
 665                         continue;
 666                 }
 667
 668                 cnt = repl_mul(lp, &b_repl, &e_repl);
 669
 670                 lp = *lpp;
 671                 if (cnt > 0 && cnt <= repl_muls) {
 672                         *lpp = b_repl;
 673                         e_repl->l_next = lp->l_next->l_next;
 674                         oldline(lp->l_next);
 675                         oldline(lp);
 676                         lpp = &e_repl->l_next;
 677                         madeopt = TRUE;
 678                 }
 679                 else {
 680                         while (b_repl != (line_p) 0) {
 681                                 line_p n = b_repl->l_next;
 682
 683                                 oldline(b_repl);
 684                                 b_repl = n;
 685                         }
 686                         lpp = &lp->l_next;
 687                 }
 688             }
 689         }
 690         return madeopt;
 691 }
 692
 693 repl_mul(lp, b, e)
 694         register line_p lp;
 695         line_p  *b, *e;
 696 {
 697         register line_p next = lp->l_next;
 698         int     ins;
 699         int     sz;
 700         unsigned long   n;
 701         int     n0, n1;
 702         int     virgin = 1;
 703         int     retval = 0;
 704
 705         *b = 0;
 706         if (! next) return 0;
 707         if ((ins = (next->l_instr & BMASK)) != op_mli && ins != op_mlu) {
 708                 return 0;
 709         }
 710         switch(next->l_optyp) {
 711         case OPNO:
 712                 return 0;
 713         case OPSHORT:
 714                 sz = next->l_a.la_short;
 715                 break;
 716 #ifdef LONGOFF
 717         case OPOFFSET:
 718                 sz = next->l_a.la_offset;
 719                 break;
 720 #endif
 721         default:
 722                 sz = (next->l_optyp & BMASK) - Z_OPMINI;
 723                 break;
 724         }
 725         if (ins == op_loc && sz != wordsize) return 0;
 726         if (ins == op_ldc && sz != 2*wordsize) return 0;
 727         if (! repl_longmuls && sz != wordsize) return 0;
 728         switch(lp->l_optyp) {
 729         case OPSHORT:
 730                 n = (long) lp->l_a.la_short;
 731                 break;
 732 #ifdef LONGOFF
 733         case OPOFFSET:
 734                 n = lp->l_a.la_offset;
 735                 break;
 736 #endif
 737         default:
 738                 n = (long)((lp->l_optyp & BMASK) - Z_OPMINI);
 739                 break;
 740         }
 741
 742 #define newinstr(res, opcode, val)      (*(res) = newline((short)(val)+Z_OPMINI), (*(res))->l_instr = (opcode))
 743
 744         while (n) {
 745                 /* first find "0*1*$" in n */
 746                 for (n1 = 0; n & 1; n>>=1) ++n1;        /* count "1" bits */
 747                 if (n)
 748                         for (n0 = 0; !(n & 1); n>>=1)   /* count "0" bits */
 749                                 ++n0;
 750                 else
 751                         n0 = 0;
 752
 753                 if (n1 == 0) {
 754                         if (n0) {
 755                                 newinstr(b, op_loc, n0); b = &((*b)->l_next);
 756                                 newinstr(b, op_slu, sz); b = &((*b)->l_next);
 757                                 retval++;
 758                         }
 759                 } else if (n1 == 1) {
 760                         if (virgin) {
 761                                 newinstr(b, op_dup, sz); b = &((*b)->l_next);
 762                                 virgin = 0;
 763                         }
 764                         else {
 765                                 newinstr(b, op_exg, sz); b = &((*b)->l_next);
 766                                 newinstr(b, op_dup, 2*sz); b = &((*b)->l_next);
 767                                 newinstr(b, op_asp, sz); b = &((*b)->l_next);
 768                                 newinstr(b, op_adu, sz); b = &((*b)->l_next);
 769                                 newinstr(b, op_exg, sz); b = &((*b)->l_next);
 770                                 retval++;
 771                         }
 772                         if (n) {
 773                                 newinstr(b, op_loc, n0+n1); b = &((*b)->l_next);
 774                                 newinstr(b, op_slu, sz); b = &((*b)->l_next);
 775                                 retval++;
 776                         }
 777                 } else {
 778                         if (virgin) {
 779                                 newinstr(b, op_dup, sz); b = &((*b)->l_next);
 780                                 if (sz == wordsize) {
 781                                     newinstr(b, op_loc, 0); b = &((*b)->l_next);
 782                                 }
 783                                 else {
 784                                     newinstr(b, op_ldc, 0); b = &((*b)->l_next);
 785                                 }
 786                                 newinstr(b, op_exg, sz); b = &((*b)->l_next);
 787                                 virgin = 0;
 788                         }
 789                         else {
 790                                 newinstr(b, op_exg, sz); b = &((*b)->l_next);
 791                                 newinstr(b, op_dup, 2*sz); b = &((*b)->l_next);
 792                                 newinstr(b, op_asp, sz); b = &((*b)->l_next);
 793                         }
 794                         newinstr(b, op_sbu, sz); b = &((*b)->l_next);
 795                         newinstr(b, op_exg, sz); b = &((*b)->l_next);
 796                         retval++;
 797                         if (n1 != 8*sz) {
 798                                 newinstr(b, op_loc, n1); b = &((*b)->l_next);
 799                                 newinstr(b, op_slu, sz); b = &((*b)->l_next);
 800                                 retval++;
 801                                 newinstr(b, op_exg, sz); b = &((*b)->l_next);
 802                                 newinstr(b, op_dup, 2*sz); b = &((*b)->l_next);
 803                                 newinstr(b, op_asp, sz); b = &((*b)->l_next);
 804                                 newinstr(b, op_adu, sz); b = &((*b)->l_next);
 805                                 newinstr(b, op_exg, sz); b = &((*b)->l_next);
 806                                 retval++;
 807                         }
 808                         if (n0) {
 809                                 newinstr(b, op_loc, n0); b = &((*b)->l_next);
 810                                 newinstr(b, op_slu, sz); b = &((*b)->l_next);
 811                                 retval++;
 812                         }
 813                 }
 814         }
 815         newinstr(b, op_asp, sz);
 816         if (virgin) {
 817                 b = &((*b)->l_next);
 818                 newinstr(b, sz == wordsize ? op_loc : op_ldc, 0);
 819         }
 820         *e = *b;
 821         return retval == 0 ? 1 : retval;
 822 #undef newinstr
 823 }