sr_iv.c 3.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188
  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 _ I V . C
  9. *
  10. */
  11. #include <em_mnem.h>
  12. #include <em_pseu.h>
  13. #include "../share/types.h"
  14. #include "sr.h"
  15. #include "../share/lset.h"
  16. #include "../share/cset.h"
  17. #include "../share/debug.h"
  18. #include "../share/global.h"
  19. #include "../share/alloc.h"
  20. #include "../share/aux.h"
  21. #include "sr_aux.h"
  22. #include "sr_cand.h"
  23. #include "sr_iv.h"
  24. STATIC lset ivvars; /* set of induction variables */
  25. STATIC short nature(lnp)
  26. line_p lnp;
  27. {
  28. /* Auxiliary routine used by inc_or_dec, is_add and plus_or_min.
  29. * Determine if lnp had INCREMENT/DECREMENT-nature (1),
  30. * ADD-nature (2), SUBTRACT-nature (3)
  31. * or Buddha-nature (0).
  32. */
  33. bool size_ok;
  34. assert(lnp != (line_p) 0);
  35. size_ok = (TYPE(lnp) == OPSHORT && SHORT(lnp) == ws);
  36. switch(INSTR(lnp)) {
  37. case op_inc:
  38. case op_dec:
  39. return 1;
  40. case op_adi:
  41. case op_adu:
  42. return (size_ok? 2:0);
  43. case op_sbi:
  44. case op_sbu:
  45. return (size_ok? 3:0);
  46. }
  47. return 0;
  48. }
  49. #define is_add(l) (nature(l) == 2)
  50. #define plus_or_min(l) (nature(l) > 1)
  51. #define inc_or_dec(l) (nature(l) == 1)
  52. STATIC bool is_same(l,lnp)
  53. line_p l, lnp;
  54. {
  55. /* lnp is a STL x , where x is a candidate
  56. * induction variable. See if l is a LOL x
  57. * (with the same x as the store-instruction)
  58. */
  59. assert(INSTR(lnp) == op_stl);
  60. return l != (line_p) 0 && INSTR(l) == op_lol &&
  61. off_set(l) == off_set(lnp);
  62. }
  63. STATIC ivar(lnp,step)
  64. line_p lnp;
  65. int step;
  66. {
  67. /* Record the fact that we've found a new induction variable.
  68. * lnp points to the last instruction of the code that
  69. * increments the induction variable, i.e. a STL, DEL or INL.
  70. */
  71. iv_p i;
  72. i = newiv();
  73. i->iv_off = (TYPE(lnp) == OPSHORT ? (offset) SHORT(lnp) : OFFSET(lnp));
  74. i->iv_incr = lnp; /* last instruction of increment code */
  75. i->iv_step = step; /* step value */
  76. Ladd(i,&ivvars);
  77. }
  78. STATIC int sign(lnp)
  79. line_p lnp;
  80. {
  81. switch(INSTR(lnp)) {
  82. case op_inc:
  83. case op_inl:
  84. case op_adi:
  85. case op_adu:
  86. return 1;
  87. case op_dec:
  88. case op_del:
  89. case op_sbi:
  90. case op_sbu:
  91. return (-1);
  92. default:
  93. assert(FALSE);
  94. }
  95. /* NOTREACHED */
  96. }
  97. STATIC try_patterns(lnp)
  98. line_p lnp;
  99. {
  100. /* lnp is a STL x; try to recognize
  101. * one of the patterns:
  102. * 'LOAD const; LOAD x; ADD; STORE x'
  103. * or 'LOAD x; LOAD const; ADD or SUBTRACT;
  104. * STORE x'
  105. * or 'LOAD x; INCREMENT/DECREMENT; STORE x'
  106. */
  107. line_p l, l2;
  108. l = PREV(lnp); /* instruction before lnp*/
  109. if (l == (line_p) 0) return; /* no match possible */
  110. l2 = PREV(l);
  111. if (inc_or_dec(l)) {
  112. if (is_same(l2,lnp)) {
  113. /* e.g. LOL iv ; INC ; STL iv */
  114. ivar(lnp,sign(l));
  115. }
  116. return;
  117. }
  118. if (is_add(lnp)) {
  119. if(is_same(l2,lnp) && is_const(PREV(l2))) {
  120. ivar(lnp,SHORT(PREV(l2)));
  121. return;
  122. }
  123. }
  124. if (plus_or_min(l)) {
  125. if (is_const(l2) && is_same(PREV(l2),lnp)) {
  126. ivar(lnp,sign(l) * SHORT(l2));
  127. }
  128. }
  129. }
  130. induc_vars(loop,ivar_out, vars_out)
  131. loop_p loop;
  132. lset *ivar_out, *vars_out;
  133. {
  134. /* Construct the set of induction variables. We use several
  135. * global variables computed by 'candidates'.
  136. */
  137. Lindex i;
  138. line_p lnp;
  139. lset cand_iv, vars;
  140. ivvars = Lempty_set();
  141. candidates(loop, &cand_iv, &vars);
  142. /* Find the set of all variables that are assigned precisely
  143. * once within the loop, within a firm block.
  144. * Also find all remaining local variables that are changed
  145. * within the loop.
  146. */
  147. if (Lnrelems(cand_iv) > 0) {
  148. for (i = Lfirst(cand_iv); i != (Lindex) 0; i = Lnext(i,cand_iv)) {
  149. lnp = (line_p) Lelem(i);
  150. if (INSTR(lnp) == op_inl || INSTR(lnp) == op_del) {
  151. ivar(lnp,sign(lnp));
  152. } else {
  153. try_patterns(lnp);
  154. }
  155. }
  156. }
  157. Ljoin(cand_iv, &vars);
  158. *ivar_out = ivvars;
  159. *vars_out = vars;
  160. }