sr_reduce.c 18 KB

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