ud_copy.c 8.6 KB

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