sr_reduce.c 18 KB

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