sr_cand.c 4.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192
  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 _ C A N D . C
  9. */
  10. #include <em_mnem.h>
  11. #include <em_pseu.h>
  12. #include "../share/types.h"
  13. #include "../share/lset.h"
  14. #include "../share/cset.h"
  15. #include "../share/debug.h"
  16. #include "../share/global.h"
  17. #include "../share/map.h"
  18. #include "../share/aux.h"
  19. #include "sr.h"
  20. #include "sr_aux.h"
  21. #include "sr_cand.h"
  22. /* A candidate induction variable of a loop (hereafter called candidate) is a
  23. * local variable (of the current procedure) that is assigned a value
  24. * precisely once within the loop. Furthermore, this assignment must
  25. * take place in a firm block of the loop.
  26. * We determine those locals that are assigned precisely once, within
  27. * a firm block;
  28. *
  29. * We represent a local variable via an instruction that references it,
  30. * e.g. LOL -6 represents the local variable at offset -6 with size=wordsize.
  31. * We keep track of two sets:
  32. * cand - the set of all candidate variables
  33. * dismiss - a set of variables that may not be made a candidate
  34. * (because they are assigned more than once, or because
  35. * they are assigned outside a firm block).
  36. * Only local variables for which a register message is given are considered.
  37. */
  38. STATIC lset cand, /* set of candidates */
  39. dism; /* set of dismissed variables */
  40. #define ALL_LINES(lnp,list) lnp = list; lnp != (line_p) 0; lnp = lnp->l_next
  41. STATIC un_cand(lnp)
  42. line_p lnp;
  43. {
  44. /* remove the variable stored into by lnp from the list of
  45. * candidates (if it was there anyway).
  46. */
  47. Lindex i, next;
  48. for (i = Lfirst(cand); i != (Lindex) 0; i = next) {
  49. next = Lnext(i,cand);
  50. if (same_local(lnp,Lelem(i))) {
  51. OUTTRACE("remove candidate",0);
  52. Lremove(Lelem(i), &cand);
  53. }
  54. }
  55. }
  56. STATIC bool is_cand(lnp)
  57. line_p lnp;
  58. {
  59. /* see if the variable stored into by lnp is a candate */
  60. Lindex i;
  61. for (i = Lfirst(cand); i != (Lindex) 0; i = Lnext(i,cand)) {
  62. if (same_local(lnp,Lelem(i))) {
  63. return TRUE;
  64. }
  65. }
  66. return FALSE;
  67. }
  68. STATIC make_cand(lnp)
  69. line_p lnp;
  70. {
  71. /* make the variable stored into by lnp a candidate */
  72. OUTTRACE("add a new candidate",0);
  73. Ladd(lnp,&cand);
  74. }
  75. STATIC do_dismiss(lnp)
  76. line_p lnp;
  77. {
  78. Ladd(lnp,&dism);
  79. }
  80. STATIC dismiss(lnp)
  81. line_p lnp;
  82. {
  83. /* The variable referenced by lnp is turned definitely into
  84. * a non-candidate.
  85. */
  86. un_cand(lnp); /* remove it from the candidate set,
  87. * if it was there in the first place.
  88. */
  89. do_dismiss(lnp); /* add it to the set of dismissed variables */
  90. }
  91. STATIC bool not_dismissed(lnp)
  92. line_p lnp;
  93. {
  94. Lindex i;
  95. for (i = Lfirst(dism); i != (Lindex) 0; i = Lnext(i,dism)) {
  96. if (same_local(Lelem(i),lnp)) {
  97. return FALSE; /* variable was dismissed */
  98. }
  99. }
  100. return TRUE;
  101. }
  102. STATIC try_cand(lnp,b)
  103. line_p lnp;
  104. bblock_p b;
  105. {
  106. /* If the variable stored into by lnp was not already a candidate
  107. * and was not dismissed, then it is made a candidate
  108. * (unless the assignment takes places in a block that is not firm).
  109. */
  110. if (!is_regvar(off_set(lnp))) return;
  111. if (is_cand(lnp) || !IS_FIRM(b)) {
  112. dismiss(lnp);
  113. } else {
  114. if (not_dismissed(lnp)) {
  115. make_cand(lnp);
  116. }
  117. }
  118. }
  119. candidates(lp,cand_out,vars_out)
  120. loop_p lp;
  121. lset *cand_out, *vars_out;
  122. {
  123. /* Find the candidate induction variables.
  124. */
  125. bblock_p b;
  126. line_p lnp;
  127. Lindex i;
  128. OUTTRACE("find candidates of loop %d",lp->lp_id);
  129. cand = Lempty_set();
  130. dism = Lempty_set();
  131. for (i = Lfirst(lp->LP_BLOCKS); i != (Lindex) 0;
  132. i = Lnext(i,lp->LP_BLOCKS)) {
  133. b = (bblock_p) Lelem(i);
  134. for ( ALL_LINES(lnp, b->b_start)) {
  135. OUTTRACE("inspect instruction %d",INSTR(lnp));
  136. switch(INSTR(lnp)) {
  137. case op_stl:
  138. case op_inl:
  139. case op_del:
  140. OUTTRACE("it's a store local",0);
  141. try_cand(lnp,b);
  142. break;
  143. case op_zrl:
  144. OUTTRACE("it's a destroy local",0);
  145. if (is_regvar(off_set(lnp))) {
  146. dismiss(lnp);
  147. }
  148. break;
  149. }
  150. }
  151. }
  152. *cand_out = cand;
  153. *vars_out = dism;
  154. }