sr_iv.c 3.7 KB

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