ud_copy.c 8.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395
  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. /* C O P Y P R O P A G A T I O N */
  7. #include <em_mnem.h>
  8. #include <em_pseu.h>
  9. #include <em_spec.h>
  10. #include "../share/types.h"
  11. #include "ud.h"
  12. #include "../share/debug.h"
  13. #include "../share/global.h"
  14. #include "../share/alloc.h"
  15. #include "../share/lset.h"
  16. #include "../share/cset.h"
  17. #include "../share/def.h"
  18. #include "../share/aux.h"
  19. #include "../share/locals.h"
  20. #include "../ud/ud_defs.h"
  21. #include "ud_copy.h"
  22. #include "ud_const.h"
  23. #include "ud_aux.h"
  24. line_p *copies; /* table of copies; every entry points to the
  25. * store-instruction.
  26. */
  27. short *def_to_copynr; /* table that maps a 'definition'-number to a
  28. * 'copy' number.
  29. */
  30. short nrcopies; /* number of copies in the current procedure
  31. * (length of copies-table)
  32. */
  33. #define COPY_NR(c) def_to_copynr[c]
  34. #define CHANGED(v,b) (Cis_elem(v,CHGVARS(b)) || Cis_elem(IMPLICIT_DEF(v),GEN(b)))
  35. #define COUNT 0
  36. #define MAP 1
  37. STATIC traverse_defs(p,action)
  38. proc_p p;
  39. int action;
  40. {
  41. bblock_p b;
  42. line_p l;
  43. bool found;
  44. short defcnt,v,cnt;
  45. defcnt = 1;
  46. if (action == COUNT) {
  47. nrcopies = 0;
  48. } else {
  49. copies = (line_p *) newmap(nrcopies);
  50. def_to_copynr = newtable(nrdefs);
  51. cnt = 1;
  52. }
  53. if (defcnt > nrdefs) return;
  54. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  55. for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
  56. if (defs[defcnt] == l) {
  57. if (is_copy(l)) {
  58. var_nr(PREV(l),&v,&found);
  59. if (found) {
  60. if (action == COUNT) {
  61. nrcopies++;
  62. } else {
  63. copies[cnt] = l;
  64. def_to_copynr[defcnt] =
  65. cnt++;
  66. }
  67. }
  68. }
  69. if (++defcnt > nrdefs) return;
  70. }
  71. }
  72. }
  73. }
  74. STATIC make_copytab(p)
  75. proc_p p;
  76. {
  77. /* Make a table of all copies appearing in procedure p.
  78. * We first count how many there are, because we
  79. * have to allocate a dynamic array of the correct size.
  80. */
  81. traverse_defs(p,COUNT);
  82. traverse_defs(p,MAP);
  83. }
  84. STATIC bool is_changed(varl,start,stop)
  85. line_p varl, start, stop;
  86. {
  87. /* See if the variable used by instruction varl
  88. * is changed anywhere between 'start' and 'stop'
  89. */
  90. register line_p l;
  91. short v;
  92. bool found;
  93. var_nr(varl,&v,&found);
  94. if (!found) {
  95. return TRUE; /* We don't maintain ud-info for this variable */
  96. }
  97. for (l = start; l != (line_p) 0 && l != stop; l = l->l_next) {
  98. if (does_expl_def(l) && same_var(varl,l)) return TRUE;
  99. if (does_impl_def(l) && affected(varl,v,l)) return TRUE;
  100. }
  101. return FALSE;
  102. }
  103. STATIC gen_kill_copies(p)
  104. proc_p p;
  105. {
  106. /* Compute C_GEN and C_KILL for every basic block
  107. * of p.
  108. */
  109. register line_p l;
  110. register bblock_p b,n;
  111. short v;
  112. bool found;
  113. short copycnt = 1, defcnt = 1;
  114. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  115. C_GEN(b) = Cempty_set(nrcopies);
  116. C_KILL(b) = Cempty_set(nrcopies);
  117. }
  118. if (nrcopies == 0) return;
  119. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  120. for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
  121. if (copies[copycnt] == l) {
  122. var_nr(PREV(l),&v,&found);
  123. assert(found);
  124. for (n = p->p_start; n != (bblock_p) 0;
  125. n = n->b_next) {
  126. if (n != b && CHANGED(v,n) &&
  127. Cis_elem(EXPL_TO_DEFNR(defcnt),IN(n))) {
  128. Cadd(copycnt,&C_KILL(n));
  129. }
  130. }
  131. if (is_changed(PREV(l),l,(line_p) 0)) {
  132. Cadd(copycnt,&C_KILL(b));
  133. } else {
  134. Cadd(copycnt,&C_GEN(b));
  135. }
  136. if (++copycnt > nrcopies) return;
  137. }
  138. if (defs[defcnt] == l) defcnt++;
  139. }
  140. }
  141. }
  142. STATIC intersect_outs(bbset,setp,full_set)
  143. lset bbset;
  144. cset *setp,full_set;
  145. {
  146. /* Take the intersection of C_OUT(b), for all b in bbset,
  147. * and put the result in setp.
  148. */
  149. Lindex i;
  150. Ccopy_set(full_set,setp);
  151. for (i = Lfirst(bbset); i != (Lindex) 0; i = Lnext(i,bbset)) {
  152. Cintersect(C_OUT((bblock_p) Lelem(i)), setp);
  153. }
  154. }
  155. STATIC init_cin(p,full_set)
  156. proc_p p;
  157. cset full_set;
  158. {
  159. /* Initialize C_IN(b) and C_OUT(b), for every basic block b.
  160. * C_IN of the root of the CFG (i.e. the procedure entry block)
  161. * will contain every copy, as it trivially holds that for
  162. * every copy "s: A := B" there is no assignment to B on any
  163. * path from s to the beginning of the root (because PRED(root)=empty).
  164. * C_IN and C_OUT of the root will never be changed.
  165. * For all remaining blocks b, C_IN(b) is initialized to the set of
  166. * all copies, and C_OUT is set to all copies but those killed in b.
  167. */
  168. bblock_p b;
  169. bblock_p root = p->p_start;
  170. C_IN(root) = Cempty_set(nrcopies);
  171. Ccopy_set(full_set,&C_IN(root)); /* full_set is the set of all copies */
  172. /* C_OUT(root) = {all copies} - C_KILL(root) + C_GEN(root) */
  173. C_OUT(root) = Cempty_set(nrcopies);
  174. Ccopy_set(full_set,&C_OUT(root));
  175. Csubtract(C_KILL(root),&C_OUT(root));
  176. Cjoin(C_GEN(root),&C_OUT(root));
  177. for (b = root->b_next; b != (bblock_p) 0; b = b->b_next) {
  178. C_IN(b) = Cempty_set(nrcopies);
  179. Ccopy_set(full_set,&C_IN(b));
  180. C_OUT(b) = Cempty_set(nrcopies);
  181. Ccopy_set(full_set,&C_OUT(b));
  182. Csubtract(C_KILL(b),&C_OUT(b));
  183. }
  184. }
  185. STATIC solve_cin(p)
  186. proc_p p;
  187. {
  188. /* Solve the data flow equations for reaching
  189. * definitions of procedure p.
  190. * These equations are:
  191. * (1) C_OUT(b) = C_IN(b) - C_KILL(b) + C_GEN(b)
  192. * (2) C_IN(b) = C_OUT(p1) * .. * C_OUT(pn)
  193. * (3) C_IN(root) = {all copies} ;
  194. * where PRED(b) = {p1, .. , pn}
  195. * and '*' denotes set intersection.
  196. * We use the iterative algorithm of Aho&Ullman to
  197. * solve the equations.
  198. */
  199. register bblock_p b;
  200. bool change;
  201. cset newin,full_set;
  202. short n;
  203. /* initializations */
  204. full_set = Cempty_set(nrcopies);
  205. for (n = 1; n <= nrcopies; n++) {
  206. Cadd(n,&full_set);
  207. }
  208. newin = Cempty_set(nrcopies);
  209. init_cin(p,full_set);
  210. change = TRUE;
  211. /* main loop */
  212. while (change) {
  213. change = FALSE;
  214. for (b = p->p_start->b_next; b != (bblock_p) 0; b = b->b_next) {
  215. intersect_outs(b->b_pred, &newin,full_set);
  216. /* newin = C_OUT(p1) * .. * C_OUT(pn) */
  217. if (!Cequal(newin,C_IN(b))) {
  218. change = TRUE;
  219. Ccopy_set(newin, &C_IN(b));
  220. Ccopy_set(C_IN(b), &C_OUT(b));
  221. Csubtract(C_KILL(b), &C_OUT(b));
  222. Cjoin(C_GEN(b), &C_OUT(b));
  223. }
  224. }
  225. }
  226. Cdeleteset(newin);
  227. Cdeleteset(full_set);
  228. }
  229. copy_analysis(p)
  230. proc_p p;
  231. {
  232. /* Determine which copies procedure p has. Compute C_IN(b),
  233. * for every basic block b.
  234. */
  235. make_copytab(p); /* Make a table of all copies */
  236. gen_kill_copies(p); /* Compute C_GEN(b) and C_KILL(b), for every b */
  237. solve_cin(p); /* Solve equations for C_IN(b) */
  238. }
  239. bool is_copy(def)
  240. line_p def;
  241. {
  242. /* See if the definition def is also a 'copy', i.e. an
  243. * statement of the form 'A := B' (or, in EM terminology:
  244. * a sequence 'Load Variable; Store Variable').
  245. */
  246. line_p lhs;
  247. int instr;
  248. lhs = PREV(def);
  249. if (lhs == (line_p) 0) return FALSE;
  250. instr = INSTR(def);
  251. switch(INSTR(lhs)) {
  252. case op_lol:
  253. case op_loe:
  254. return instr == op_stl || instr == op_ste;
  255. case op_ldl:
  256. case op_lde:
  257. return instr == op_sdl || instr == op_sde;
  258. default:
  259. return FALSE;
  260. }
  261. /* NOTREACHED */
  262. }
  263. fold_var(old,new,b)
  264. line_p old, new;
  265. bblock_p b;
  266. {
  267. /* The variable referenced by the EM instruction 'old'
  268. * must be replaced by the variable referenced by 'new'.
  269. */
  270. line_p l;
  271. /* DEBUGGING:
  272. local_p loc;
  273. short nr;
  274. bool ok;
  275. if (TYPE(old) == OPOBJECT) {
  276. printf("global var.");
  277. } else {
  278. printf("local var. with off. %ld",off_set(old));
  279. find_local(off_set(old),&nr,&ok);
  280. assert(ok);
  281. loc = locals[nr];
  282. printf(",score %ld",loc->lc_score);
  283. }
  284. printf(" replaced by ");
  285. if (TYPE(new) == OPOBJECT) {
  286. printf("global var.");
  287. } else {
  288. printf("local var. with off. %ld",off_set(new));
  289. find_local(off_set(new),&nr,&ok);
  290. assert(ok);
  291. loc = locals[nr];
  292. printf(",score %ld",loc->lc_score);
  293. }
  294. printf("\n");
  295. END DEBUG */
  296. l = old;
  297. if (TYPE(l) != TYPE(new)) {
  298. l = newline(TYPE(new));
  299. l->l_instr = INSTR(new);
  300. repl_line(old,l,b);
  301. }
  302. switch(TYPE(new)) {
  303. case OPOBJECT:
  304. OBJ(l) = OBJ(new);
  305. break;
  306. case OPSHORT:
  307. SHORT(l) = SHORT(new);
  308. break;
  309. case OPOFFSET:
  310. OFFSET(l) = OFFSET(new);
  311. break;
  312. default:
  313. assert(FALSE);
  314. }
  315. }
  316. bool value_retained(copy,defnr,use,b)
  317. line_p copy,use;
  318. short defnr;
  319. bblock_p b;
  320. {
  321. /* See if the right hand side variable of the
  322. * copy still has the same value at 'use'.
  323. * If the copy and the use are in the same
  324. * basic block (defnr = 0), search from the
  325. * copy to the use, to see if the rhs variable
  326. * is changed. If the copy is in another block,
  327. * defnr is the definition-number of the copy.
  328. * Search from the beginning of the block to
  329. * the use, to see if the rhs is changed; if not,
  330. * check that the copy is in C_IN(b).
  331. */
  332. line_p rhs, start;
  333. rhs = PREV(copy);
  334. start = (defnr == 0 ? copy : b->b_start);
  335. return !is_changed(rhs,start,use) &&
  336. (defnr == 0 || Cis_elem(COPY_NR(defnr), C_IN(b)));
  337. }