sr_expr.c 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204
  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 _ E X P R . C
  9. *
  10. */
  11. #include <stdio.h>
  12. #include <em_mnem.h>
  13. #include "../share/types.h"
  14. #include "sr.h"
  15. #include "../share/debug.h"
  16. #include "../share/global.h"
  17. #include "../share/aux.h"
  18. #include "sr_aux.h"
  19. #include "../share/lset.h"
  20. #include "sr_iv.h"
  21. #define ME_NONE 0
  22. #define ME_UNAIR 1
  23. #define ME_BINAIR 2
  24. #define ME_LOOPCONST 3
  25. #define ME_IV 4
  26. STATIC iv_p last_iv;
  27. STATIC int iv_sign;
  28. STATIC lset ivars, loopvars;
  29. STATIC bool is_loadiv(lnp)
  30. line_p lnp;
  31. {
  32. /* See if lnp is a LOL iv instruction, where iv is an
  33. * induction variable of the set ivars. If so, set the
  34. * the global variable last_iv to its descriptor.
  35. */
  36. Lindex i;
  37. iv_p iv;
  38. offset off;
  39. if (INSTR(lnp) == op_lol) {
  40. off = off_set(lnp);
  41. for (i = Lfirst(ivars); i != (Lindex) 0; i = Lnext(i,ivars)) {
  42. iv = (iv_p) Lelem(i);
  43. if (iv->iv_off == off) {
  44. last_iv = iv;
  45. return TRUE;
  46. }
  47. }
  48. }
  49. return FALSE;
  50. }
  51. #define size_ok(l) (TYPE(l) == OPSHORT && SHORT(l) == ws)
  52. STATIC int me_kind(l,sign_in,sign_out)
  53. line_p l;
  54. int sign_in, *sign_out;
  55. {
  56. if (l != (line_p) 0) {
  57. switch(INSTR(l)) {
  58. case op_adi:
  59. case op_adu:
  60. if (size_ok(l)) {
  61. *sign_out = sign_in;
  62. return ME_BINAIR;
  63. }
  64. break;
  65. case op_sbi:
  66. case op_sbu:
  67. if (size_ok(l)) {
  68. *sign_out = - sign_in;
  69. return ME_BINAIR;
  70. }
  71. break;
  72. case op_ngi:
  73. if (size_ok(l)) {
  74. *sign_out = - sign_in;
  75. return ME_UNAIR;
  76. }
  77. break;
  78. case op_inc:
  79. case op_dec:
  80. *sign_out = sign_in;
  81. return ME_UNAIR;
  82. case op_loc:
  83. return ME_LOOPCONST;
  84. case op_lol:
  85. if (is_loadiv(l)) {
  86. iv_sign = sign_in;
  87. return ME_IV;
  88. }
  89. if (is_loopconst(l,loopvars)) return ME_LOOPCONST;
  90. }
  91. }
  92. return ME_NONE;
  93. }
  94. STATIC bool match_expr(l,iv_allowed,lbegin,iv_seen,sign)
  95. line_p l,*lbegin;
  96. bool iv_allowed, *iv_seen;
  97. int sign;
  98. {
  99. /* This routine is a top down parser for simple
  100. * EM expressions. It recognizes expressions that
  101. * have as operators + and - (unary - is also allowed)
  102. * and that have as operands a number of loop constants
  103. * (either a constant or a variable that is not
  104. * changed within the loop) and at most one induction
  105. * variable.
  106. * The parameter iv_allowed is propagated downwards
  107. * in the expression tree, indicating whether the
  108. * subexpression may use an induction variable as
  109. * operand. The parameter iv_seen is propagated
  110. * upwards, indicating if the subexpression has used
  111. * an induction variable. The parameter sign is
  112. * propagated downwards; it indicates the sign of
  113. * the subexpression. lbegin will point to the
  114. * beginning of the recognized subexpression
  115. * (it is an out parameter). Note that we scan the
  116. * EM text from right to left (i.e. top down).
  117. */
  118. line_p l1;
  119. bool iv_insubexpr;
  120. int sign2;
  121. switch(me_kind(l,sign,&sign2)) {
  122. case ME_UNAIR:
  123. /* unairy operator, match one subexpression */
  124. if (match_expr(PREV(l),iv_allowed,&l1,&iv_insubexpr,sign2)) {
  125. *lbegin = l1;
  126. *iv_seen = iv_insubexpr;
  127. return TRUE;
  128. }
  129. return FALSE;
  130. case ME_BINAIR:
  131. /* binairy operator, match two subexpressions */
  132. if (match_expr(PREV(l), iv_allowed, &l1, &iv_insubexpr,sign2)) {
  133. l = PREV(l1);
  134. iv_allowed = iv_allowed && !iv_insubexpr;
  135. if (match_expr(l,iv_allowed,&l1,
  136. &iv_insubexpr,sign)) {
  137. *lbegin = l1;
  138. *iv_seen = !iv_allowed || iv_insubexpr;
  139. return TRUE;
  140. }
  141. }
  142. return FALSE; /* subexpression not recognized */
  143. case ME_LOOPCONST:
  144. *lbegin = l; /* expression is a loop constant */
  145. *iv_seen = FALSE;
  146. return TRUE;
  147. case ME_IV:
  148. if (iv_allowed) {
  149. *iv_seen = TRUE;
  150. *lbegin = l;
  151. return TRUE;
  152. }
  153. /* fall through ... */
  154. default:
  155. return FALSE;
  156. }
  157. }
  158. bool is_ivexpr(l,ivs,vars,lbegin_out,iv_out,sign_out)
  159. line_p l, *lbegin_out;
  160. lset ivs,vars;
  161. iv_p *iv_out;
  162. int *sign_out;
  163. {
  164. line_p l2;
  165. bool iv_seen;
  166. loopvars = vars;
  167. ivars = ivs;
  168. if (match_expr(l,TRUE,&l2,&iv_seen,1)) {
  169. if (iv_seen) {
  170. /* recognized a correct expression */
  171. *lbegin_out = l2;
  172. *iv_out = last_iv;
  173. *sign_out = iv_sign;
  174. return TRUE;
  175. }
  176. }
  177. return FALSE;
  178. }