cs_elim.c 7.1 KB

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