ud_defs.c 7.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366
  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. /* U S E - D E F I N I T I O N A N A L Y S I S
  7. *
  8. * U D _ D E F S . C
  9. */
  10. #include <em_mnem.h>
  11. #include "../share/types.h"
  12. #include "ud.h"
  13. #include "../share/debug.h"
  14. #include "../share/global.h"
  15. #include "../share/lset.h"
  16. #include "../share/cset.h"
  17. #include "../share/map.h"
  18. #include "../share/locals.h"
  19. #include "ud_defs.h"
  20. #include "../share/alloc.h"
  21. #include "../share/aux.h"
  22. short nrdefs; /* total number of definitions */
  23. short nrexpldefs; /* number of explicit definitions */
  24. line_p *defs;
  25. cset *vardefs;
  26. static cset all_globl_defs, all_indir_defs;
  27. /* auxiliary sets, used by gen_sets */
  28. bool does_expl_def(line_p l)
  29. {
  30. /* See if instruction l does an explicit definition */
  31. switch(INSTR(l)) {
  32. case op_stl:
  33. case op_sdl:
  34. case op_ste:
  35. case op_sde:
  36. case op_inl:
  37. case op_del:
  38. case op_ine:
  39. case op_dee:
  40. case op_zrl:
  41. case op_zre:
  42. return TRUE;
  43. default:
  44. return FALSE;
  45. }
  46. /* NOTREACHED */
  47. return FALSE;
  48. }
  49. bool does_impl_def(line_p l)
  50. {
  51. /* See if instruction l does an implicit definition */
  52. switch(INSTR(l)) {
  53. case op_cal:
  54. case op_cai:
  55. case op_sil:
  56. case op_stf:
  57. case op_sti:
  58. case op_sts:
  59. case op_sdf:
  60. case op_sar:
  61. case op_blm:
  62. case op_bls:
  63. case op_zrf:
  64. return TRUE;
  65. default:
  66. return FALSE;
  67. }
  68. return FALSE;
  69. }
  70. void make_defs(proc_p p)
  71. {
  72. /* Make a map of all explicit definitions
  73. * occurring in p.
  74. * Determine the set of explicit definitions
  75. * of variable v (i.e. vardefs[v]), for all
  76. * v from 1 to nrvars.
  77. * For every basic block b, compute CHGVARS(b),
  78. * i.e. the set of variables changed in b by an
  79. * explicit definition.
  80. */
  81. bblock_p b;
  82. line_p l;
  83. short v, i, cnt = 0;
  84. bool found;
  85. /* first count the number of definitions */
  86. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  87. for (l = b->b_start; l != (line_p) 0 ; l = l->l_next) {
  88. if (does_expl_def(l)) {
  89. var_nr(l,&v,&found);
  90. if (!found) continue; /* no ud for this var */
  91. cnt++;
  92. }
  93. }
  94. }
  95. nrexpldefs = cnt;
  96. /* now allocate the defs table and the vardefs table*/
  97. defs = (line_p *) newmap(nrexpldefs);
  98. vardefs = (cset *) newmap(nrvars);
  99. for (i = 1; i <= nrvars; i++) {
  100. vardefs[i] = Cempty_set(nrexpldefs);
  101. }
  102. cnt = 1;
  103. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  104. CHGVARS(b) =Cempty_set(nrvars);
  105. for (l = b->b_start; l != (line_p) 0 ; l = l->l_next) {
  106. if (does_expl_def(l)) {
  107. var_nr(l,&v,&found);
  108. if (!found) continue;
  109. assert (v <= nrvars);
  110. Cadd(v,&CHGVARS(b));
  111. defs[cnt] = l;
  112. Cadd(cnt,&vardefs[v]);
  113. cnt++;
  114. }
  115. }
  116. }
  117. }
  118. static void init_gen(short nrdefs)
  119. {
  120. /* Initializing routine of gen_sets. Compute the set
  121. * of all implicit definitions to global variables
  122. * (all_globl_defs) and the set of all implicit
  123. * definition generated by an indirect assignment
  124. * through a pointer (all_indir_defs).
  125. */
  126. short v;
  127. all_globl_defs = Cempty_set(nrdefs);
  128. all_indir_defs = Cempty_set(nrdefs);
  129. for (v = 1; v <= nrglobals; v++) {
  130. Cadd(IMPLICIT_DEF(GLOB_TO_VARNR(v)), &all_globl_defs);
  131. Cadd(IMPLICIT_DEF(GLOB_TO_VARNR(v)), &all_indir_defs);
  132. }
  133. for (v = 1; v <= nrlocals; v++) {
  134. if (!IS_REGVAR(locals[v])) {
  135. Cadd(IMPLICIT_DEF(LOC_TO_VARNR(v)), &all_indir_defs);
  136. }
  137. }
  138. }
  139. static void clean_gen()
  140. {
  141. Cdeleteset(all_globl_defs);
  142. Cdeleteset(all_indir_defs);
  143. }
  144. static bool same_target(line_p l, short defnr)
  145. {
  146. /* See if l defines the same variable as def */
  147. line_p def;
  148. short v;
  149. if (IS_IMPL_DEF(defnr)) {
  150. /* An implicitly generated definition */
  151. v = IMPL_VAR(TO_IMPLICIT(defnr));
  152. if (IS_GLOBAL(v)) {
  153. return TYPE(l) == OPOBJECT &&
  154. OBJ(l)->o_globnr == TO_GLOBAL(v);
  155. } else {
  156. return TYPE(l) != OPOBJECT &&
  157. locals[TO_LOCAL(v)]->lc_off == off_set(l);
  158. }
  159. }
  160. /* explicit definition */
  161. def = defs[TO_EXPLICIT(defnr)];
  162. if (TYPE(l) == OPOBJECT) {
  163. return TYPE(def) == OPOBJECT && OBJ(def) == OBJ(l);
  164. } else {
  165. return TYPE(def) != OPOBJECT && off_set(def) == off_set(l);
  166. }
  167. }
  168. static void rem_prev_defs(line_p l, cset *gen_p)
  169. {
  170. /* Remove all definitions in gen that define the
  171. * same variable as l.
  172. */
  173. cset gen;
  174. Cindex i,next;
  175. gen = *gen_p;
  176. for (i = Cfirst(gen); i != (Cindex) 0; i = next) {
  177. next = Cnext(i,gen);
  178. if (same_target(l,Celem(i))) {
  179. Cremove(Celem(i),gen_p);
  180. }
  181. }
  182. }
  183. static void impl_globl_defs(proc_p p, cset *gen_p)
  184. {
  185. /* Add all definitions of global variables
  186. * that are generated implicitly by a call
  187. * to p to the set gen_p.
  188. */
  189. Cindex i;
  190. short v;
  191. cset ext = p->p_change->c_ext;
  192. for (i = Cfirst(ext); i != (Cindex) 0; i = Cnext(i,ext)) {
  193. if (( v = omap[Celem(i)]->o_globnr) != (short) 0) {
  194. /* the global variable v, for which we do
  195. * maintain ud-info is changed by p, so a
  196. * definition of v is generated implicitly.
  197. */
  198. Cadd(IMPLICIT_DEF(GLOB_TO_VARNR(v)),gen_p);
  199. }
  200. }
  201. }
  202. static void impl_gen_defs(line_p l, cset *gen_p)
  203. {
  204. /* Add all definitions generated implicitly by instruction l
  205. * to gen_p. l may be a call or some kind of indirect
  206. * assignment.
  207. */
  208. proc_p p;
  209. switch(INSTR(l)) {
  210. case op_cal:
  211. p = PROC(l);
  212. if (BODY_KNOWN(p)) {
  213. impl_globl_defs(p,gen_p);
  214. if (!CHANGE_INDIR(p)) return;
  215. break;
  216. }
  217. /* else fall through ... */
  218. case op_cai:
  219. /* Indirect subroutine call or call to
  220. * a subroutine whose body is not available.
  221. * Assume worst case; all global
  222. * variables are changed and
  223. * the called proc. does a store-
  224. * indirect.
  225. */
  226. Cjoin(all_globl_defs,gen_p);
  227. break;
  228. /* default: indir. assignment */
  229. }
  230. Cjoin(all_indir_defs,gen_p);
  231. }
  232. void gen_sets(proc_p p)
  233. {
  234. /* Compute for every basic block b of p the
  235. * set GEN(b) of definitions in b (explicit as
  236. * well as implicit) that reach the end of b.
  237. */
  238. bblock_p b;
  239. line_p l;
  240. short defnr = 1;
  241. init_gen(nrdefs); /* compute all_globl_defs and all_indir_defs */
  242. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  243. GEN(b) = Cempty_set(nrdefs);
  244. for (l = b->b_start; l != (line_p) 0; l = l->l_next) {
  245. if (does_impl_def(l)) {
  246. impl_gen_defs(l,&GEN(b));
  247. /* add definitions implicitly
  248. * generated by subroutine call
  249. * or indir. pointer assignment.
  250. */
  251. } else {
  252. if (does_expl_def(l)) {
  253. if (defnr <= nrdefs && defs[defnr] == l) {
  254. rem_prev_defs(l,&GEN(b));
  255. /* previous defs. of same var
  256. * don't reach the end of b.
  257. */
  258. Cadd(EXPL_TO_DEFNR(defnr),&GEN(b));
  259. defnr++;
  260. }
  261. }
  262. }
  263. }
  264. }
  265. clean_gen(); /* clean up */
  266. }
  267. static void killed_defs(short v, bblock_p b)
  268. {
  269. /* Put all definitions of v occurring outside b
  270. * in KILL(b). In fact, we also put explicit
  271. * definitions occurring in b, but not reaching the
  272. * end of b, in KILL(b). This causes no harm.
  273. */
  274. Cindex i;
  275. short d;
  276. for (i = Cfirst(vardefs[v]); i != (Cindex) 0; i = Cnext(i,vardefs[v])) {
  277. d = Celem(i); /* d is an explicit definition of v */
  278. if (!Cis_elem(EXPL_TO_DEFNR(d),GEN(b))) {
  279. Cadd(EXPL_TO_DEFNR(d),&KILL(b));
  280. }
  281. }
  282. /* Also add implicit definition of v to KILL(b) */
  283. Cadd(IMPLICIT_DEF(v),&KILL(b));
  284. }
  285. void kill_sets(proc_p p)
  286. {
  287. /* For every basic block b of p compute the set
  288. * KILL(b) of definitions outside b that define
  289. * variables redefined by b.
  290. * KILL(b) contains explicit as well as implicit
  291. * definitions.
  292. */
  293. bblock_p b;
  294. Cindex i;
  295. short v;
  296. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  297. KILL(b) = Cempty_set(nrdefs);
  298. for (i = Cfirst(CHGVARS(b)); i != (Cindex) 0;
  299. i = Cnext(i,CHGVARS(b))) {
  300. v = Celem(i); /* v is a variable changed in b */
  301. killed_defs(v,b);
  302. }
  303. }
  304. }