sr_reduce.c 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735
  1. /* $Id$ */
  2. /*
  3. * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
  4. * See the copyright notice in the ACK home directory, in the file "Copyright".
  5. */
  6. /* S T R E N G T H R E D U C T I O N
  7. *
  8. * S R _ R E D U C E . C
  9. *
  10. */
  11. #include <em_pseu.h>
  12. #include <em_reg.h>
  13. #include <em_mes.h>
  14. #include <em_mnem.h>
  15. #include <em_spec.h>
  16. #include "../share/types.h"
  17. #include "sr.h"
  18. #include "../share/debug.h"
  19. #include "../share/alloc.h"
  20. #include "../share/def.h"
  21. #include "../share/global.h"
  22. #include "../share/aux.h"
  23. #include "sr_aux.h"
  24. #include "../share/lset.h"
  25. #include "sr_xform.h"
  26. #include "sr_reduce.h"
  27. #include "sr_expr.h"
  28. static lset avail;
  29. /* If an expression such as "iv * const" or "A[iv]" is
  30. * used more than once in a loop, we only use one temporary
  31. * local for it and reuse this local each time.
  32. * After the first occurrence, the expression is said to
  33. * be available.
  34. */
  35. static int regtyp(code_p code)
  36. {
  37. switch(code->co_instr) {
  38. case op_mli:
  39. case op_mlu:
  40. case op_sli:
  41. case op_slu:
  42. return reg_any;
  43. default:
  44. return reg_pointer;
  45. }
  46. /* NOTREACHED */
  47. return reg_pointer;
  48. }
  49. static void gen_regmes(offset tmp, int score, code_p code, proc_p p)
  50. {
  51. /* generate a register message for the temporary variable and
  52. * insert it at the start of the procedure.
  53. */
  54. line_p l,pro;
  55. l = reg_mes(tmp,code->co_tmpsize,regtyp(code),score);
  56. pro = p->p_start->b_start; /* every proc. begins with a PRO pseudo */
  57. l->l_next = pro->l_next;
  58. PREV(l->l_next) = l;
  59. pro->l_next = l;
  60. PREV(l) = pro;
  61. }
  62. static line_p newcode(code_p code, offset tmp)
  63. {
  64. /* Construct the EM code that will replace the reducible code,
  65. * e.g. iv * c -> tmp
  66. * a[iv] -> *tmp
  67. */
  68. line_p l = NULL;
  69. switch(code->co_instr) {
  70. case op_mli:
  71. case op_mlu:
  72. case op_sli:
  73. case op_slu:
  74. /* new code is just a LOL tmp */
  75. l = int_line(tmp);
  76. l->l_instr = op_lol;
  77. break;
  78. case op_aar:
  79. /* New code is a LOAD tmp, where tmp is a
  80. * pointer variable, so the actual EM code
  81. * depends on the pointer size.
  82. */
  83. l = move_pointer(tmp,LOAD);
  84. break;
  85. case op_lar:
  86. /* New code is a load-indirect */
  87. l = int_line(tmp);
  88. l->l_instr = op_lil;
  89. break;
  90. case op_sar:
  91. /* New code is a store-indirect */
  92. l = int_line(tmp);
  93. l->l_instr = op_sil;
  94. break;
  95. default:
  96. assert(FALSE);
  97. }
  98. return l;
  99. }
  100. static void replcode(code_p code, line_p text)
  101. {
  102. /* Replace old code (extending from code->co_lfirst to
  103. * code->co_llast) by new code (headed by 'text').
  104. */
  105. line_p l, l1, l2;
  106. for (l = text; l->l_next != (line_p) 0; l = l->l_next);
  107. /* 'l' now points to last instruction of text */
  108. l1 = PREV(code->co_lfirst); /* instruction just before old code */
  109. l2 = code->co_llast->l_next; /* instruction just behind old code */
  110. if (l1 == (line_p) 0) {
  111. code->co_block->b_start = text;
  112. PREV(text) = (line_p) 0;
  113. } else {
  114. l1->l_next = text;
  115. PREV(text) = l1;
  116. }
  117. if (l2 != (line_p) 0) {
  118. PREV(l2) = l;
  119. }
  120. l->l_next = l2;
  121. code->co_llast->l_next = (line_p) 0;
  122. /* Note that the old code is still accessible via code->co_lfirst */
  123. }
  124. static line_p add_code(line_p pl, line_p l)
  125. {
  126. if (! pl) {
  127. PREV(l) = 0;
  128. }
  129. else {
  130. line_p n = pl->l_next;
  131. DLINK(pl, l);
  132. if (n) {
  133. while (l->l_next) l = l->l_next;
  134. DLINK(l, n);
  135. }
  136. l = pl;
  137. }
  138. return l;
  139. }
  140. static void init_code(code_p code, offset tmp)
  141. {
  142. /* Generate code to set up the temporary local.
  143. * For multiplication, its initial value is const*iv_expr,
  144. * for array operations it is &a[iv_expr] (where iv_expr is
  145. * an expression that is a linear function of the induc. var.
  146. * This code is inserted immediately before the loop entry.
  147. * As the initializing code looks very much like the
  148. * reduced code, we reuse that (old) code.
  149. */
  150. line_p l, *p;
  151. l = code->co_llast; /* the mli, lar etc. instruction */
  152. switch(INSTR(l)) {
  153. case op_mli:
  154. case op_mlu:
  155. /* reduced code is: iv_expr * lc (or lc * iv_expr)
  156. * init_code is: tmp = iv_expr * lc (or lc*iv_expr)
  157. * So we just insert a 'STL tmp'.
  158. */
  159. l->l_next = int_line(tmp);
  160. l->l_next->l_instr = op_stl;
  161. break;
  162. case op_sli:
  163. case op_slu:
  164. /* reduced code is: iv_expr << lc
  165. * init_code is: tmp = iv_expr << lc
  166. * So we just insert a 'STL tmp'.
  167. */
  168. l->l_next = int_line(tmp);
  169. l->l_next->l_instr = op_stl;
  170. break;
  171. case op_lar:
  172. case op_sar:
  173. /* reduced code is: ...= A[iv_expr] resp.
  174. * A[iv]_expr = ..
  175. * init_code is: tmp = &A[iv_expr].
  176. * So just change the lar or sar into a aar ...
  177. */
  178. l->l_instr = (byte) op_aar;
  179. /* ... and fall through !! */
  180. case op_aar:
  181. /* append code to store a pointer in temp. local */
  182. l->l_next = move_pointer(tmp,STORE);
  183. break;
  184. default:
  185. assert(FALSE); /* non-reducible instruction */
  186. }
  187. PREV(l->l_next) = l;
  188. /* Now insert the code at the end of the header block */
  189. p = &code->co_loop->LP_INSTR;
  190. if (*p == (line_p) 0 || (PREV((*p)) == 0 && INSTR((*p)) == op_bra)) {
  191. /* LP_INSTR points to last instruction of header block,
  192. * so if it is 0, the header block is empty yet.
  193. */
  194. code->co_loop->LP_HEADER->b_start =
  195. add_code(code->co_loop->LP_HEADER->b_start, code->co_lfirst);
  196. } else if (INSTR((*p)) == op_bra) {
  197. add_code(PREV((*p)), code->co_lfirst);
  198. }
  199. else add_code(*p, code->co_lfirst);
  200. while (l->l_next) l = l->l_next;
  201. *p = l; /* new last instruction */
  202. }
  203. static void incr_code(code_p code, offset tmp)
  204. {
  205. /* Generate code to increment the temporary local variable.
  206. * The variable is incremented by
  207. * 1) multiply --> step value of iv * loop constant
  208. * 2) array --> step value of iv * element size
  209. * This value can be determined statically.
  210. * If the induction variable is used in a linear
  211. * expression in which its sign is negative
  212. * (such as in: "5-(6-(-iv))" ), this value is negated.
  213. * The generated code looks like:
  214. * LOL tmp ; LOC incr ; ADI ws ; STL tmp
  215. * For pointer-increments we generate a "ADP c", rather than
  216. * a "LOC c; ADS ws".
  217. * This code is put just after the code that increments
  218. * the induction variable.
  219. */
  220. line_p load_tmp = NULL, loc = NULL, add = NULL,
  221. store_tmp = NULL, l = NULL;
  222. add = newline(OPSHORT);
  223. SHORT(add) = ws; /* the add instruction, can be ADI,ADU or ADS */
  224. switch(code->co_instr) {
  225. case op_mli:
  226. case op_mlu:
  227. loc = int_line(
  228. code->co_sign *
  229. off_set(code->c_o.co_loadlc) *
  230. code->co_iv->iv_step);
  231. loc->l_instr = op_loc;
  232. add->l_instr = op_adi;
  233. load_tmp = int_line(tmp);
  234. load_tmp->l_instr = op_lol;
  235. store_tmp = int_line(tmp);
  236. store_tmp->l_instr = op_stl;
  237. break;
  238. case op_sli:
  239. case op_slu:
  240. loc = int_line(
  241. code->co_sign *
  242. code->co_iv->iv_step *
  243. (1 << off_set(code->c_o.co_loadlc)));
  244. loc->l_instr = op_loc;
  245. add->l_instr = op_adi;
  246. load_tmp = int_line(tmp);
  247. load_tmp->l_instr = op_lol;
  248. store_tmp = int_line(tmp);
  249. store_tmp->l_instr = op_stl;
  250. break;
  251. case op_lar:
  252. case op_sar:
  253. case op_aar:
  254. loc = (line_p) 0;
  255. add = int_line(
  256. code->co_sign *
  257. code->co_iv->iv_step *
  258. elemsize(code->c_o.co_desc));
  259. add->l_instr = op_adp;
  260. load_tmp = move_pointer(tmp,LOAD);
  261. store_tmp = move_pointer(tmp,STORE);
  262. break;
  263. default:
  264. assert(FALSE);
  265. }
  266. /* Now we've got pieces of code to load the temp. local,
  267. * load the constant, add the two and store the result in
  268. * the local. This code will be put just after the code that
  269. * increments the induction variable.
  270. */
  271. if (loc != (line_p) 0) concatenate(load_tmp,loc);
  272. concatenate(load_tmp,add);
  273. concatenate(load_tmp,store_tmp);
  274. /* Now load_tmp points to a list of EM instructions */
  275. l = code->co_iv->iv_incr;
  276. if (l->l_next != (line_p) 0) {
  277. DLINK(store_tmp,l->l_next);
  278. }
  279. DLINK(l,load_tmp); /* doubly link them */
  280. }
  281. static void remcode(code_p c)
  282. {
  283. line_p l, next;
  284. for (l = c->co_lfirst; l != (line_p) 0; l = next) {
  285. next = l->l_next;
  286. oldline(l);
  287. }
  288. oldcinfo(c);
  289. }
  290. static bool same_address(line_p l1, line_p l2, lset vars)
  291. {
  292. /* See if l1 and l2 load the same address */
  293. if (INSTR(l1) != INSTR(l2)) return FALSE;
  294. switch(INSTR(l1)) {
  295. case op_lae:
  296. return OBJ(l1) == OBJ(l2);
  297. case op_lal:
  298. return off_set(l1) == off_set(l2);
  299. case op_lol:
  300. return ps == ws &&
  301. off_set(l1) == off_set(l2) &&
  302. is_loopconst(l1,vars);
  303. case op_ldl:
  304. return ps == 2*ws &&
  305. off_set(l1) == off_set(l2) &&
  306. is_loopconst(l1,vars);
  307. default:
  308. return FALSE;
  309. }
  310. return FALSE;
  311. }
  312. static bool same_expr(line_p lb1, line_p le1, line_p lb2, line_p le2)
  313. {
  314. /* See if the code from lb1 to le1 is the same
  315. * expression as the code from lb2 to le2.
  316. */
  317. line_p l1,l2;
  318. l1 = lb1;
  319. l2 = lb2;
  320. for (;;) {
  321. if (INSTR(l1) != INSTR(l2)) return FALSE;
  322. switch(TYPE(l1)) {
  323. case OPSHORT:
  324. if (TYPE(l2) != OPSHORT ||
  325. SHORT(l1) != SHORT(l2)) return FALSE;
  326. break;
  327. case OPOFFSET:
  328. if (TYPE(l2) != OPOFFSET ||
  329. OFFSET(l1) != OFFSET(l2)) return FALSE;
  330. break;
  331. case OPNO:
  332. break;
  333. default:
  334. return FALSE;
  335. }
  336. if (l1 == le1 ) return l2 == le2;
  337. if (l2 == le2) return FALSE;
  338. l1 = l1->l_next;
  339. l2 = l2->l_next;
  340. }
  341. }
  342. static bool same_code(code_p c1, code_p c2, lset vars)
  343. {
  344. /* See if c1 and c2 compute the same expression. Two array
  345. * references can be the same even if one is e.g a fetch
  346. * and the other a store.
  347. */
  348. switch(c1->co_instr) {
  349. case op_mli:
  350. case op_mlu:
  351. case op_sli:
  352. case op_slu:
  353. return c1->co_instr == c2->co_instr &&
  354. off_set(c1->c_o.co_loadlc) ==
  355. off_set(c2->c_o.co_loadlc) &&
  356. same_expr(c1->co_ivexpr,c1->co_endexpr,
  357. c2->co_ivexpr,c2->co_endexpr);
  358. case op_aar:
  359. case op_lar:
  360. case op_sar:
  361. return ( c2->co_instr == op_aar ||
  362. c2->co_instr == op_lar ||
  363. c2->co_instr == op_sar) &&
  364. same_expr(c1->co_ivexpr,c1->co_endexpr,
  365. c2->co_ivexpr,c2->co_endexpr) &&
  366. same_address(c1->c_o.co_desc,c2->c_o.co_desc,vars) &&
  367. same_address(c1->co_lfirst,c2->co_lfirst,vars);
  368. default:
  369. assert(FALSE);
  370. }
  371. /* NOTREACHED */
  372. return FALSE;
  373. }
  374. static code_p available(code_p c, lset vars)
  375. {
  376. /* See if the code is already available.
  377. * If so, return a pointer to the first occurrence
  378. * of the code.
  379. */
  380. Lindex i;
  381. code_p cp;
  382. for (i = Lfirst(avail); i != (Lindex) 0; i = Lnext(i,avail)) {
  383. cp = (code_p) Lelem(i);
  384. if (same_code(c,cp,vars)) {
  385. return cp;
  386. }
  387. }
  388. return (code_p) 0;
  389. }
  390. static void fix_header(loop_p lp)
  391. {
  392. /* Check if a header block was added, and if so, add a branch to
  393. * the entry block.
  394. * If it was added, it was added to the end of the procedure, so
  395. * move the END pseudo.
  396. */
  397. bblock_p b = curproc->p_start;
  398. if (lp->LP_HEADER->b_next == 0) {
  399. line_p l = last_instr(lp->LP_HEADER);
  400. line_p e;
  401. assert(l != 0);
  402. if (INSTR(l) != op_bra) {
  403. line_p j = newline(OPINSTRLAB);
  404. assert(INSTR(lp->lp_entry->b_start) == op_lab);
  405. INSTRLAB(j) = INSTRLAB(lp->lp_entry->b_start);
  406. j->l_instr = op_bra;
  407. DLINK(l, j);
  408. l = j;
  409. }
  410. while (b->b_next != lp->LP_HEADER) b = b->b_next;
  411. e = last_instr(b);
  412. assert(INSTR(e) == ps_end);
  413. assert(PREV(e) != 0);
  414. PREV(e)->l_next = 0;
  415. DLINK(l, e);
  416. }
  417. }
  418. static void reduce(code_p code, lset vars)
  419. {
  420. /* Perform the actual transformations. The code on the left
  421. * gets transformed into the code on the right. Note that
  422. * each piece of code is assigned a name, that will be
  423. * used to describe the whole process.
  424. *
  425. * t = iv * 118; (init_code)
  426. * do ---> do
  427. * .. iv * 118 .. .. t .. (new_code)
  428. * iv++; iv++;
  429. * t += 118; (incr_code)
  430. * od od
  431. */
  432. offset tmp;
  433. code_p ac;
  434. OUTTRACE("succeeded!!",0);
  435. if ((ac = available(code,vars)) != (code_p) 0) {
  436. /* The expression is already available, so we
  437. * don't have to generate a new temporary local for it.
  438. */
  439. OUTTRACE("expression was already available",0);
  440. replcode(code,newcode(code,ac->co_temp));
  441. remcode(code);
  442. } else {
  443. make_header(code->co_loop);
  444. /* make sure there's a header block */
  445. tmp = tmplocal(curproc,(offset) code->co_tmpsize);
  446. code->co_temp = tmp;
  447. /* create a new local variable in the stack frame
  448. * of current proc.
  449. */
  450. gen_regmes(tmp,3,code,curproc); /* generate register message */
  451. /* score is set to 3, as TMP is used at least 3 times */
  452. replcode(code,newcode(code,tmp));
  453. OUTTRACE("replaced old code by new code",0);
  454. /* Construct the EM-code that will replace the reducible code
  455. * and replace the old code by the new code.
  456. */
  457. init_code(code,tmp);
  458. OUTTRACE("emitted initializing code",0);
  459. /* Emit code to initialize the temporary local. This code is
  460. * put in the loop header block.
  461. */
  462. incr_code(code,tmp); /* emit code to increment temp. local */
  463. OUTTRACE("emitted increment code",0);
  464. Ladd(code,&avail);
  465. fix_header(code->co_loop);
  466. }
  467. }
  468. static void try_multiply(loop_p lp, lset ivs, lset vars, bblock_p b, line_p mul)
  469. {
  470. /* See if we can reduce the strength of the multiply
  471. * instruction. If so, then set up the global common
  472. * data structure 'c' (containing information about the
  473. * code to be reduced) and call 'reduce'.
  474. */
  475. line_p l2,lbegin;
  476. iv_p iv;
  477. code_p c;
  478. int sign;
  479. VL(mul);
  480. OUTTRACE("trying multiply instruction on line %d",linecount);
  481. if (ovfl_harmful && !IS_STRONG(b)) return;
  482. /* If b is not a strong block, optimization may
  483. * introduce an overflow error in the initializing code.
  484. */
  485. l2 = PREV(mul); /* Instruction before the multiply */
  486. if ( (is_ivexpr(l2,ivs,vars,&lbegin,&iv,&sign)) &&
  487. is_const(PREV(lbegin)) ) {
  488. /* recognized expression "const * iv_expr" */
  489. c = newcinfo();
  490. c->c_o.co_loadlc = PREV(l2);
  491. c->co_endexpr = l2;
  492. c->co_lfirst = PREV(lbegin);
  493. } else {
  494. if (is_const(l2) &&
  495. (is_ivexpr(PREV(l2),ivs,vars,&lbegin,&iv,&sign))) {
  496. /* recognized "iv * const " */
  497. c = newcinfo();
  498. c->c_o.co_loadlc = l2;
  499. c->co_endexpr = PREV(l2);
  500. c->co_lfirst = lbegin;
  501. } else {
  502. OUTTRACE("failed",0);
  503. return;
  504. }
  505. }
  506. /* common part for both patterns */
  507. c->co_iv = iv;
  508. c->co_loop = lp;
  509. c->co_block = b;
  510. c->co_llast = mul;
  511. c->co_ivexpr = lbegin;
  512. c->co_sign = sign;
  513. c->co_tmpsize = ws; /* temp. local is a word */
  514. c->co_instr = INSTR(mul);
  515. OUTVERBOSE("sr: multiply in proc %d loop %d",
  516. curproc->p_id, lp->lp_id);
  517. Ssr++;
  518. reduce(c,vars);
  519. }
  520. static void try_leftshift(loop_p lp, lset ivs, lset vars, bblock_p b, line_p shft)
  521. {
  522. /* See if we can reduce the strength of the leftshift
  523. * instruction. If so, then set up the global common
  524. * data structure 'c' (containing information about the
  525. * code to be reduced) and call 'reduce'.
  526. */
  527. line_p l2,lbegin;
  528. iv_p iv;
  529. code_p c;
  530. int sign;
  531. VL(shft);
  532. OUTTRACE("trying leftshift instruction on line %d",linecount);
  533. if (ovfl_harmful && !IS_STRONG(b)) return;
  534. /* If b is not a strong block, optimization may
  535. * introduce an overflow error in the initializing code.
  536. */
  537. l2 = PREV(shft); /* Instruction before the shift */
  538. if (is_const(l2) && off_set(l2) > sli_threshold &&
  539. (is_ivexpr(PREV(l2),ivs,vars,&lbegin,&iv,&sign))) {
  540. /* recognized "iv << const " */
  541. c = newcinfo();
  542. c->c_o.co_loadlc = l2;
  543. c->co_endexpr = PREV(l2);
  544. c->co_lfirst = lbegin;
  545. } else {
  546. OUTTRACE("failed",0);
  547. return;
  548. }
  549. c->co_iv = iv;
  550. c->co_loop = lp;
  551. c->co_block = b;
  552. c->co_llast = shft;
  553. c->co_ivexpr = lbegin;
  554. c->co_sign = sign;
  555. c->co_tmpsize = ws; /* temp. local is a word */
  556. c->co_instr = INSTR(shft);
  557. OUTVERBOSE("sr: leftshift in proc %d loop %d",
  558. curproc->p_id, lp->lp_id);
  559. Ssr++;
  560. reduce(c,vars);
  561. }
  562. static void try_array(loop_p lp, lset ivs, lset vars, bblock_p b, line_p arr)
  563. {
  564. /* See if we can reduce the strength of the array reference
  565. * instruction 'arr'.
  566. */
  567. line_p l2,l3,lbegin;
  568. iv_p iv;
  569. code_p c;
  570. int sign;
  571. /* Try to recognize the pattern:
  572. * LOAD ADDRES OF A
  573. * LOAD IV
  574. * LOAD ADDRESS OF DESCRIPTOR
  575. */
  576. VL(arr);
  577. OUTTRACE("trying array instruction on line %d",linecount);
  578. if (arrbound_harmful && !IS_STRONG(b)) return;
  579. /* If b is not a strong block, optimization may
  580. * introduce an array bound error in the initializing code.
  581. */
  582. l2 = PREV(arr);
  583. if (is_caddress(l2,vars) &&
  584. (INSTR(arr) == op_aar || elemsize(l2) == ws) &&
  585. (is_ivexpr(PREV(l2),ivs,vars,&lbegin,&iv,&sign)) ) {
  586. l3 = PREV(lbegin);
  587. if (is_caddress(l3,vars)) {
  588. c = newcinfo();
  589. c->co_iv = iv;
  590. c->co_loop = lp;
  591. c->co_block = b;
  592. c->co_lfirst = l3;
  593. c->co_llast = arr;
  594. c->co_ivexpr = lbegin;
  595. c->co_endexpr = PREV(l2);
  596. c->co_sign = sign;
  597. c->co_tmpsize = ps; /* temp. local is pointer */
  598. c->co_instr = INSTR(arr);
  599. c->c_o.co_desc = l2;
  600. OUTVERBOSE("sr: array in proc %d loop %d",
  601. curproc->p_id,lp->lp_id);
  602. Ssr++;
  603. reduce(c,vars);
  604. }
  605. }
  606. }
  607. static void clean_avail()
  608. {
  609. Lindex i;
  610. for (i = Lfirst(avail); i != (Lindex) 0; i = Lnext(i,avail)) {
  611. oldcinfo(Lelem(i));
  612. }
  613. Ldeleteset(avail);
  614. }
  615. /*
  616. * lp ==> description of the loop
  617. * ivs ==> set of induction variables of the loop
  618. * vars ==> set of local variables changed in loop
  619. */
  620. void strength_reduction(loop_p lp, lset ivs, lset vars)
  621. {
  622. /* Find all expensive instructions (leftshift, multiply, array) and see
  623. * if they can be reduced. We branch to several instruction-specific
  624. * routines (try_...) that check if reduction is possible,
  625. * and that set up a common data structure (code_info).
  626. * The actual transformations are done by 'reduce', that is
  627. * essentially instruction-independend.
  628. */
  629. bblock_p b;
  630. line_p l, next;
  631. Lindex i;
  632. avail = Lempty_set();
  633. for (i = Lfirst(lp->LP_BLOCKS); i != (Lindex) 0;
  634. i = Lnext(i,lp->LP_BLOCKS)) {
  635. b = (bblock_p) Lelem(i);
  636. for (l = b->b_start; l != (line_p) 0; l = next) {
  637. next = l->l_next;
  638. if (TYPE(l) == OPSHORT && SHORT(l) == ws) {
  639. switch(INSTR(l)) {
  640. case op_sli:
  641. case op_slu:
  642. try_leftshift(lp,ivs,vars,b,l);
  643. break;
  644. case op_mlu:
  645. case op_mli:
  646. try_multiply(lp,ivs,vars,b,l);
  647. break;
  648. case op_lar:
  649. case op_sar:
  650. case op_aar:
  651. try_array(lp,ivs,vars,b,l);
  652. break;
  653. }
  654. }
  655. }
  656. }
  657. clean_avail();
  658. }