cs_elim.c 7.2 KB

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