peephole.c 18 KB

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