cs_elim.c 7.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266
  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. #include <em_reg.h>
  7. #include <em_mnem.h>
  8. #include "../share/types.h"
  9. #include "../share/alloc.h"
  10. #include "../share/lset.h"
  11. #include "../share/aux.h"
  12. #include "../share/global.h"
  13. #include "../share/debug.h"
  14. #include "cs.h"
  15. #include "cs_avail.h"
  16. #include "cs_alloc.h"
  17. #include "cs_aux.h"
  18. #include "cs_debug.h"
  19. #include "cs_profit.h"
  20. #include "cs_partit.h"
  21. #include "cs_debug.h"
  22. static void dlink(line_p l1, line_p l2)
  23. {
  24. /* Doubly link the lines in l1 and l2. */
  25. if (l1 != (line_p) 0)
  26. l1->l_next = l2;
  27. if (l2 != (line_p) 0)
  28. l2->l_prev = l1;
  29. }
  30. static void remove_lines(line_p first, line_p last)
  31. {
  32. /* Throw away the lines between and including first and last.
  33. * Don't worry about any pointers; the (must) have been taken care of.
  34. */
  35. line_p lnp, next;
  36. last->l_next = (line_p) 0; /* Delimit the list. */
  37. for (lnp = first; lnp != (line_p) 0; lnp = next) {
  38. next = lnp->l_next;
  39. oldline(lnp);
  40. }
  41. }
  42. static bool contained(occur_p ocp1, occur_p ocp2)
  43. {
  44. /* Determine whether ocp1 is contained within ocp2. */
  45. line_p lnp, next;
  46. for (lnp = ocp2->oc_lfirst; lnp != (line_p) 0; lnp = next) {
  47. next = lnp != ocp2->oc_llast ? lnp->l_next : (line_p) 0;
  48. if (lnp == ocp1->oc_llast) return TRUE;
  49. }
  50. return FALSE;
  51. }
  52. static void delete(occur_p ocp, avail_p start)
  53. {
  54. /* Delete all occurrences that are contained within ocp.
  55. * They must have been entered in the list before start:
  56. * if an expression is contained with an other, its operator line
  57. * appears before the operator line of the other because EM-expressions
  58. * are postfix.
  59. */
  60. avail_p ravp;
  61. Lindex i, next;
  62. for (ravp = start; ravp != (avail_p) 0; ravp = ravp->av_before) {
  63. for (i = Lfirst(ravp->av_occurs); i != (Lindex) 0; i = next) {
  64. next = Lnext(i, ravp->av_occurs);
  65. if (contained(occ_elem(i), ocp)) {
  66. OUTTRACE("delete contained occurrence", 0);
  67. # ifdef TRACE
  68. SHOWOCCUR(occ_elem(i));
  69. # endif
  70. oldoccur(occ_elem(i));
  71. Lremove(Lelem(i), &ravp->av_occurs);
  72. }
  73. }
  74. }
  75. }
  76. static void complete_aar(line_p lnp, int instr, valnum descr_vn)
  77. {
  78. /* Lnp is an instruction that loads the address of an array-element.
  79. * Instr tells us what effect we should achieve; load (instr is op_lar)
  80. * or store (instr is op_sar) this array-element. Descr_vn is the
  81. * valuenumber of the address of the descriptor of this array.
  82. * We append a loi or sti of the correct number of bytes.
  83. */
  84. line_p lindir;
  85. lindir = int_line(array_elemsize(descr_vn));
  86. lindir->l_instr = instr == op_lar ? op_loi : op_sti;
  87. dlink(lindir, lnp->l_next);
  88. dlink(lnp, lindir);
  89. }
  90. static void replace(occur_p ocp, offset tmp, avail_p avp)
  91. {
  92. /* Replace the lines in the occurrence in ocp by a load of the
  93. * temporary with offset tmp.
  94. */
  95. line_p lol, first, last;
  96. assert(avp->av_size == ws || avp->av_size == 2*ws);
  97. first = ocp->oc_lfirst; last = ocp->oc_llast;
  98. lol = int_line(tmp);
  99. lol->l_instr = avp->av_size == ws ? op_lol : op_ldl;
  100. dlink(lol, last->l_next);
  101. if (first->l_prev == (line_p) 0) ocp->oc_belongs->b_start = lol;
  102. dlink(first->l_prev, lol);
  103. if (avp->av_instr == (byte) op_aar) {
  104. /* There may actually be a LAR or a SAR instruction; in that
  105. * case we have to complete the array-instruction.
  106. */
  107. int instr = INSTR(last);
  108. if (instr != op_aar) complete_aar(lol, instr, avp->av_othird);
  109. }
  110. /* Throw away the by now useless lines. */
  111. remove_lines(first, last);
  112. }
  113. static void append(avail_p avp, offset tmp)
  114. {
  115. /* Avp->av_found points to a line with an operator in it. This
  116. * routine emits a sequence of instructions that saves the result
  117. * in a local with offset tmp. In most cases we just append
  118. * avp->av_found with stl/sdl tmp and lol/ldl tmp depending on
  119. * avp->av_size. If however the operator is an aar contained
  120. * within a lar or sar, we must first generate the aar.
  121. */
  122. line_p stl, lol;
  123. assert(avp->av_size == ws || avp->av_size == 2*ws);
  124. stl = int_line(tmp);
  125. stl->l_instr = avp->av_size == ws ? op_stl : op_sdl;
  126. lol = int_line(tmp);
  127. lol->l_instr = avp->av_size == ws ? op_lol : op_ldl;
  128. dlink(lol, avp->av_found->l_next);
  129. dlink(stl, lol);
  130. dlink(avp->av_found, stl);
  131. if (avp->av_instr == (byte) op_aar) {
  132. int instr = INSTR(avp->av_found);
  133. if (instr != op_aar) {
  134. complete_aar(lol, instr, avp->av_othird);
  135. avp->av_found->l_instr = op_aar;
  136. }
  137. }
  138. }
  139. static void set_replace(avail_p avp, offset tmp)
  140. {
  141. /* Avp->av_occurs is now a set of occurrences, each of which will be
  142. * replaced by a reference to a local.
  143. * Each time we eliminate an expression, we delete from our
  144. * list those expressions that are physically contained in them,
  145. * because we cannot eliminate them again.
  146. */
  147. Lindex i;
  148. lset s = avp->av_occurs;
  149. for (i = Lfirst(s); i != (Lindex) 0; i = Lnext(i, s)) {
  150. OUTVERBOSE("eliminate duplicate", 0);
  151. SHOWOCCUR(occ_elem(i));
  152. Scs++;
  153. delete(occ_elem(i), avp->av_before);
  154. replace(occ_elem(i), tmp, avp);
  155. }
  156. }
  157. static int reg_score(entity_p enp)
  158. {
  159. /* Enp is a local that will go into a register.
  160. * We return its score upto now.
  161. */
  162. assert(is_regvar(enp->en_loc));
  163. return regv_arg(enp->en_loc, 4);
  164. }
  165. static line_p gen_mesreg(offset off, avail_p avp, proc_p pp)
  166. {
  167. /* Generate a register message for the local that will hold the
  168. * result of the expression in avp, at the appropriate place in
  169. * the procedure in pp.
  170. */
  171. line_p reg;
  172. reg = reg_mes(off, (short) avp->av_size, regtype(avp->av_instr), 0);
  173. appnd_line(reg, pp->p_start->b_start);
  174. return reg;
  175. }
  176. static void change_score(line_p mes, int score)
  177. {
  178. /* Change the score in the register message in mes to score. */
  179. arg_p ap = ARG(mes);
  180. ap = ap->a_next; /* Offset. */
  181. ap = ap->a_next; /* Size. */
  182. ap = ap->a_next; /* Type. */
  183. ap = ap->a_next; /* Score. */
  184. ap->a_a.a_offset = score;
  185. }
  186. void eliminate(proc_p pp)
  187. {
  188. /* Eliminate costly common subexpressions within procedure pp.
  189. * We scan the available expressions in - with respect to time found -
  190. * reverse order, to find largest first, e.g. `A + B + C' before
  191. * `A + B'.
  192. * We do not eliminate an expression when the size
  193. * is not one of ws or 2*ws, because then we cannot use lol or ldl.
  194. * Code is appended to the first occurrence of the expression
  195. * to store the result into a local.
  196. */
  197. avail_p ravp;
  198. int score;
  199. offset tmp;
  200. line_p mes;
  201. for (ravp = avails; ravp != (avail_p) 0; ravp = ravp->av_before) {
  202. if (ravp->av_size != ws && ravp->av_size != 2*ws) continue;
  203. if (ravp->av_saveloc == (entity_p) 0) {
  204. /* We save it ourselves. */
  205. score = 2; /* Stl and lol. */
  206. } else {
  207. score = reg_score(ravp->av_saveloc);
  208. }
  209. if (desirable(ravp)) {
  210. score += Lnrelems(ravp->av_occurs);
  211. OUTTRACE("temporary local score %d", score);
  212. if (ravp->av_saveloc != (entity_p) 0) {
  213. tmp = ravp->av_saveloc->en_loc;
  214. mes = find_mesreg(tmp);
  215. OUTVERBOSE("re-using %ld(LB)", tmp);
  216. } else {
  217. tmp = tmplocal(pp, ravp->av_size);
  218. mes = gen_mesreg(tmp, ravp, pp);
  219. append(ravp, tmp);
  220. }
  221. change_score(mes, score);
  222. set_replace(ravp, tmp);
  223. }
  224. }
  225. }