sr_reduce.c 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734
  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;
  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, loc, add, store_tmp, l;
  221. add = newline(OPSHORT);
  222. SHORT(add) = ws; /* the add instruction, can be ADI,ADU or ADS */
  223. switch(code->co_instr) {
  224. case op_mli:
  225. case op_mlu:
  226. loc = int_line(
  227. code->co_sign *
  228. off_set(code->c_o.co_loadlc) *
  229. code->co_iv->iv_step);
  230. loc->l_instr = op_loc;
  231. add->l_instr = op_adi;
  232. load_tmp = int_line(tmp);
  233. load_tmp->l_instr = op_lol;
  234. store_tmp = int_line(tmp);
  235. store_tmp->l_instr = op_stl;
  236. break;
  237. case op_sli:
  238. case op_slu:
  239. loc = int_line(
  240. code->co_sign *
  241. code->co_iv->iv_step *
  242. (1 << off_set(code->c_o.co_loadlc)));
  243. loc->l_instr = op_loc;
  244. add->l_instr = op_adi;
  245. load_tmp = int_line(tmp);
  246. load_tmp->l_instr = op_lol;
  247. store_tmp = int_line(tmp);
  248. store_tmp->l_instr = op_stl;
  249. break;
  250. case op_lar:
  251. case op_sar:
  252. case op_aar:
  253. loc = (line_p) 0;
  254. add = int_line(
  255. code->co_sign *
  256. code->co_iv->iv_step *
  257. elemsize(code->c_o.co_desc));
  258. add->l_instr = op_adp;
  259. load_tmp = move_pointer(tmp,LOAD);
  260. store_tmp = move_pointer(tmp,STORE);
  261. break;
  262. default:
  263. assert(FALSE);
  264. }
  265. /* Now we've got pieces of code to load the temp. local,
  266. * load the constant, add the two and store the result in
  267. * the local. This code will be put just after the code that
  268. * increments the induction variable.
  269. */
  270. if (loc != (line_p) 0) concatenate(load_tmp,loc);
  271. concatenate(load_tmp,add);
  272. concatenate(load_tmp,store_tmp);
  273. /* Now load_tmp points to a list of EM instructions */
  274. l = code->co_iv->iv_incr;
  275. if (l->l_next != (line_p) 0) {
  276. DLINK(store_tmp,l->l_next);
  277. }
  278. DLINK(l,load_tmp); /* doubly link them */
  279. }
  280. static void remcode(code_p c)
  281. {
  282. line_p l, next;
  283. for (l = c->co_lfirst; l != (line_p) 0; l = next) {
  284. next = l->l_next;
  285. oldline(l);
  286. }
  287. oldcinfo(c);
  288. }
  289. static bool same_address(line_p l1, line_p l2, lset vars)
  290. {
  291. /* See if l1 and l2 load the same address */
  292. if (INSTR(l1) != INSTR(l2)) return FALSE;
  293. switch(INSTR(l1)) {
  294. case op_lae:
  295. return OBJ(l1) == OBJ(l2);
  296. case op_lal:
  297. return off_set(l1) == off_set(l2);
  298. case op_lol:
  299. return ps == ws &&
  300. off_set(l1) == off_set(l2) &&
  301. is_loopconst(l1,vars);
  302. case op_ldl:
  303. return ps == 2*ws &&
  304. off_set(l1) == off_set(l2) &&
  305. is_loopconst(l1,vars);
  306. default:
  307. return FALSE;
  308. }
  309. return FALSE;
  310. }
  311. static bool same_expr(line_p lb1, line_p le1, line_p lb2, line_p le2)
  312. {
  313. /* See if the code from lb1 to le1 is the same
  314. * expression as the code from lb2 to le2.
  315. */
  316. line_p l1,l2;
  317. l1 = lb1;
  318. l2 = lb2;
  319. for (;;) {
  320. if (INSTR(l1) != INSTR(l2)) return FALSE;
  321. switch(TYPE(l1)) {
  322. case OPSHORT:
  323. if (TYPE(l2) != OPSHORT ||
  324. SHORT(l1) != SHORT(l2)) return FALSE;
  325. break;
  326. case OPOFFSET:
  327. if (TYPE(l2) != OPOFFSET ||
  328. OFFSET(l1) != OFFSET(l2)) return FALSE;
  329. break;
  330. case OPNO:
  331. break;
  332. default:
  333. return FALSE;
  334. }
  335. if (l1 == le1 ) return l2 == le2;
  336. if (l2 == le2) return FALSE;
  337. l1 = l1->l_next;
  338. l2 = l2->l_next;
  339. }
  340. }
  341. static bool same_code(code_p c1, code_p c2, lset vars)
  342. {
  343. /* See if c1 and c2 compute the same expression. Two array
  344. * references can be the same even if one is e.g a fetch
  345. * and the other a store.
  346. */
  347. switch(c1->co_instr) {
  348. case op_mli:
  349. case op_mlu:
  350. case op_sli:
  351. case op_slu:
  352. return c1->co_instr == c2->co_instr &&
  353. off_set(c1->c_o.co_loadlc) ==
  354. off_set(c2->c_o.co_loadlc) &&
  355. same_expr(c1->co_ivexpr,c1->co_endexpr,
  356. c2->co_ivexpr,c2->co_endexpr);
  357. case op_aar:
  358. case op_lar:
  359. case op_sar:
  360. return ( c2->co_instr == op_aar ||
  361. c2->co_instr == op_lar ||
  362. c2->co_instr == op_sar) &&
  363. same_expr(c1->co_ivexpr,c1->co_endexpr,
  364. c2->co_ivexpr,c2->co_endexpr) &&
  365. same_address(c1->c_o.co_desc,c2->c_o.co_desc,vars) &&
  366. same_address(c1->co_lfirst,c2->co_lfirst,vars);
  367. default:
  368. assert(FALSE);
  369. }
  370. /* NOTREACHED */
  371. return FALSE;
  372. }
  373. static code_p available(code_p c, lset vars)
  374. {
  375. /* See if the code is already available.
  376. * If so, return a pointer to the first occurrence
  377. * of the code.
  378. */
  379. Lindex i;
  380. code_p cp;
  381. for (i = Lfirst(avail); i != (Lindex) 0; i = Lnext(i,avail)) {
  382. cp = (code_p) Lelem(i);
  383. if (same_code(c,cp,vars)) {
  384. return cp;
  385. }
  386. }
  387. return (code_p) 0;
  388. }
  389. static void fix_header(loop_p lp)
  390. {
  391. /* Check if a header block was added, and if so, add a branch to
  392. * the entry block.
  393. * If it was added, it was added to the end of the procedure, so
  394. * move the END pseudo.
  395. */
  396. bblock_p b = curproc->p_start;
  397. if (lp->LP_HEADER->b_next == 0) {
  398. line_p l = last_instr(lp->LP_HEADER);
  399. line_p e;
  400. assert(l != 0);
  401. if (INSTR(l) != op_bra) {
  402. line_p j = newline(OPINSTRLAB);
  403. assert(INSTR(lp->lp_entry->b_start) == op_lab);
  404. INSTRLAB(j) = INSTRLAB(lp->lp_entry->b_start);
  405. j->l_instr = op_bra;
  406. DLINK(l, j);
  407. l = j;
  408. }
  409. while (b->b_next != lp->LP_HEADER) b = b->b_next;
  410. e = last_instr(b);
  411. assert(INSTR(e) == ps_end);
  412. assert(PREV(e) != 0);
  413. PREV(e)->l_next = 0;
  414. DLINK(l, e);
  415. }
  416. }
  417. static void reduce(code_p code, lset vars)
  418. {
  419. /* Perform the actual transformations. The code on the left
  420. * gets transformed into the code on the right. Note that
  421. * each piece of code is assigned a name, that will be
  422. * used to describe the whole process.
  423. *
  424. * t = iv * 118; (init_code)
  425. * do ---> do
  426. * .. iv * 118 .. .. t .. (new_code)
  427. * iv++; iv++;
  428. * t += 118; (incr_code)
  429. * od od
  430. */
  431. offset tmp;
  432. code_p ac;
  433. OUTTRACE("succeeded!!",0);
  434. if ((ac = available(code,vars)) != (code_p) 0) {
  435. /* The expression is already available, so we
  436. * don't have to generate a new temporary local for it.
  437. */
  438. OUTTRACE("expression was already available",0);
  439. replcode(code,newcode(code,ac->co_temp));
  440. remcode(code);
  441. } else {
  442. make_header(code->co_loop);
  443. /* make sure there's a header block */
  444. tmp = tmplocal(curproc,(offset) code->co_tmpsize);
  445. code->co_temp = tmp;
  446. /* create a new local variable in the stack frame
  447. * of current proc.
  448. */
  449. gen_regmes(tmp,3,code,curproc); /* generate register message */
  450. /* score is set to 3, as TMP is used at least 3 times */
  451. replcode(code,newcode(code,tmp));
  452. OUTTRACE("replaced old code by new code",0);
  453. /* Construct the EM-code that will replace the reducible code
  454. * and replace the old code by the new code.
  455. */
  456. init_code(code,tmp);
  457. OUTTRACE("emitted initializing code",0);
  458. /* Emit code to initialize the temporary local. This code is
  459. * put in the loop header block.
  460. */
  461. incr_code(code,tmp); /* emit code to increment temp. local */
  462. OUTTRACE("emitted increment code",0);
  463. Ladd(code,&avail);
  464. fix_header(code->co_loop);
  465. }
  466. }
  467. static void try_multiply(loop_p lp, lset ivs, lset vars, bblock_p b, line_p mul)
  468. {
  469. /* See if we can reduce the strength of the multiply
  470. * instruction. If so, then set up the global common
  471. * data structure 'c' (containing information about the
  472. * code to be reduced) and call 'reduce'.
  473. */
  474. line_p l2,lbegin;
  475. iv_p iv;
  476. code_p c;
  477. int sign;
  478. VL(mul);
  479. OUTTRACE("trying multiply instruction on line %d",linecount);
  480. if (ovfl_harmful && !IS_STRONG(b)) return;
  481. /* If b is not a strong block, optimization may
  482. * introduce an overflow error in the initializing code.
  483. */
  484. l2 = PREV(mul); /* Instruction before the multiply */
  485. if ( (is_ivexpr(l2,ivs,vars,&lbegin,&iv,&sign)) &&
  486. is_const(PREV(lbegin)) ) {
  487. /* recognized expression "const * iv_expr" */
  488. c = newcinfo();
  489. c->c_o.co_loadlc = PREV(l2);
  490. c->co_endexpr = l2;
  491. c->co_lfirst = PREV(lbegin);
  492. } else {
  493. if (is_const(l2) &&
  494. (is_ivexpr(PREV(l2),ivs,vars,&lbegin,&iv,&sign))) {
  495. /* recognized "iv * const " */
  496. c = newcinfo();
  497. c->c_o.co_loadlc = l2;
  498. c->co_endexpr = PREV(l2);
  499. c->co_lfirst = lbegin;
  500. } else {
  501. OUTTRACE("failed",0);
  502. return;
  503. }
  504. }
  505. /* common part for both patterns */
  506. c->co_iv = iv;
  507. c->co_loop = lp;
  508. c->co_block = b;
  509. c->co_llast = mul;
  510. c->co_ivexpr = lbegin;
  511. c->co_sign = sign;
  512. c->co_tmpsize = ws; /* temp. local is a word */
  513. c->co_instr = INSTR(mul);
  514. OUTVERBOSE("sr: multiply in proc %d loop %d",
  515. curproc->p_id, lp->lp_id);
  516. Ssr++;
  517. reduce(c,vars);
  518. }
  519. static void try_leftshift(loop_p lp, lset ivs, lset vars, bblock_p b, line_p shft)
  520. {
  521. /* See if we can reduce the strength of the leftshift
  522. * instruction. If so, then set up the global common
  523. * data structure 'c' (containing information about the
  524. * code to be reduced) and call 'reduce'.
  525. */
  526. line_p l2,lbegin;
  527. iv_p iv;
  528. code_p c;
  529. int sign;
  530. VL(shft);
  531. OUTTRACE("trying leftshift instruction on line %d",linecount);
  532. if (ovfl_harmful && !IS_STRONG(b)) return;
  533. /* If b is not a strong block, optimization may
  534. * introduce an overflow error in the initializing code.
  535. */
  536. l2 = PREV(shft); /* Instruction before the shift */
  537. if (is_const(l2) && off_set(l2) > sli_threshold &&
  538. (is_ivexpr(PREV(l2),ivs,vars,&lbegin,&iv,&sign))) {
  539. /* recognized "iv << const " */
  540. c = newcinfo();
  541. c->c_o.co_loadlc = l2;
  542. c->co_endexpr = PREV(l2);
  543. c->co_lfirst = lbegin;
  544. } else {
  545. OUTTRACE("failed",0);
  546. return;
  547. }
  548. c->co_iv = iv;
  549. c->co_loop = lp;
  550. c->co_block = b;
  551. c->co_llast = shft;
  552. c->co_ivexpr = lbegin;
  553. c->co_sign = sign;
  554. c->co_tmpsize = ws; /* temp. local is a word */
  555. c->co_instr = INSTR(shft);
  556. OUTVERBOSE("sr: leftshift in proc %d loop %d",
  557. curproc->p_id, lp->lp_id);
  558. Ssr++;
  559. reduce(c,vars);
  560. }
  561. static void try_array(loop_p lp, lset ivs, lset vars, bblock_p b, line_p arr)
  562. {
  563. /* See if we can reduce the strength of the array reference
  564. * instruction 'arr'.
  565. */
  566. line_p l2,l3,lbegin;
  567. iv_p iv;
  568. code_p c;
  569. int sign;
  570. /* Try to recognize the pattern:
  571. * LOAD ADDRES OF A
  572. * LOAD IV
  573. * LOAD ADDRESS OF DESCRIPTOR
  574. */
  575. VL(arr);
  576. OUTTRACE("trying array instruction on line %d",linecount);
  577. if (arrbound_harmful && !IS_STRONG(b)) return;
  578. /* If b is not a strong block, optimization may
  579. * introduce an array bound error in the initializing code.
  580. */
  581. l2 = PREV(arr);
  582. if (is_caddress(l2,vars) &&
  583. (INSTR(arr) == op_aar || elemsize(l2) == ws) &&
  584. (is_ivexpr(PREV(l2),ivs,vars,&lbegin,&iv,&sign)) ) {
  585. l3 = PREV(lbegin);
  586. if (is_caddress(l3,vars)) {
  587. c = newcinfo();
  588. c->co_iv = iv;
  589. c->co_loop = lp;
  590. c->co_block = b;
  591. c->co_lfirst = l3;
  592. c->co_llast = arr;
  593. c->co_ivexpr = lbegin;
  594. c->co_endexpr = PREV(l2);
  595. c->co_sign = sign;
  596. c->co_tmpsize = ps; /* temp. local is pointer */
  597. c->co_instr = INSTR(arr);
  598. c->c_o.co_desc = l2;
  599. OUTVERBOSE("sr: array in proc %d loop %d",
  600. curproc->p_id,lp->lp_id);
  601. Ssr++;
  602. reduce(c,vars);
  603. }
  604. }
  605. }
  606. static void clean_avail()
  607. {
  608. Lindex i;
  609. for (i = Lfirst(avail); i != (Lindex) 0; i = Lnext(i,avail)) {
  610. oldcinfo(Lelem(i));
  611. }
  612. Ldeleteset(avail);
  613. }
  614. /*
  615. * lp ==> description of the loop
  616. * ivs ==> set of induction variables of the loop
  617. * vars ==> set of local variables changed in loop
  618. */
  619. void strength_reduction(loop_p lp, lset ivs, lset vars)
  620. {
  621. /* Find all expensive instructions (leftshift, multiply, array) and see
  622. * if they can be reduced. We branch to several instruction-specific
  623. * routines (try_...) that check if reduction is possible,
  624. * and that set up a common data structure (code_info).
  625. * The actual transformations are done by 'reduce', that is
  626. * essentially instruction-independend.
  627. */
  628. bblock_p b;
  629. line_p l, next;
  630. Lindex i;
  631. avail = Lempty_set();
  632. for (i = Lfirst(lp->LP_BLOCKS); i != (Lindex) 0;
  633. i = Lnext(i,lp->LP_BLOCKS)) {
  634. b = (bblock_p) Lelem(i);
  635. for (l = b->b_start; l != (line_p) 0; l = next) {
  636. next = l->l_next;
  637. if (TYPE(l) == OPSHORT && SHORT(l) == ws) {
  638. switch(INSTR(l)) {
  639. case op_sli:
  640. case op_slu:
  641. try_leftshift(lp,ivs,vars,b,l);
  642. break;
  643. case op_mlu:
  644. case op_mli:
  645. try_multiply(lp,ivs,vars,b,l);
  646. break;
  647. case op_lar:
  648. case op_sar:
  649. case op_aar:
  650. try_array(lp,ivs,vars,b,l);
  651. break;
  652. }
  653. }
  654. }
  655. }
  656. clean_avail();
  657. }