peephole.c 18 KB

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