cs_kill.c 8.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368
  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_mnem.h>
  7. #include "../share/types.h"
  8. #include "../share/debug.h"
  9. #include "../share/global.h"
  10. #include "../share/lset.h"
  11. #include "../share/cset.h"
  12. #include "../share/aux.h"
  13. #include "../share/map.h"
  14. #include "cs.h"
  15. #include "cs_aux.h"
  16. #include "cs_debug.h"
  17. #include "cs_avail.h"
  18. #include "cs_entity.h"
  19. #include "cs_kill.h"
  20. static int base_valno(entity_p enp)
  21. {
  22. /* Return the value number of the (base) address of an indirectly
  23. * accessed entity.
  24. */
  25. switch (enp->en_kind) {
  26. default:
  27. assert(FALSE);
  28. break;
  29. case ENINDIR:
  30. return enp->en_ind;
  31. case ENOFFSETTED:
  32. return enp->en_base;
  33. case ENARRELEM:
  34. return enp->en_arbase;
  35. }
  36. /* NOTREACHED */
  37. return 0;
  38. }
  39. static entity_p find_base(valnum vn)
  40. {
  41. /* Vn is the valuenumber of the (base) address of an indirectly
  42. * accessed entity. Return the entity that holds this address
  43. * recursively.
  44. */
  45. Lindex i;
  46. avail_p ravp;
  47. for (i = Lfirst(entities); i != (Lindex) 0; i = Lnext(i, entities)) {
  48. register entity_p renp = en_elem(i);
  49. if (renp->en_vn == vn) {
  50. switch (renp->en_kind) {
  51. case ENAEXTERNAL:
  52. case ENALOCAL:
  53. case ENALOCBASE:
  54. case ENAARGBASE:
  55. return renp;
  56. case ENAOFFSETTED:
  57. return find_base(renp->en_base);
  58. }
  59. }
  60. }
  61. /* We couldn't find it among the entities.
  62. * Let's try the available expressions.
  63. */
  64. for (ravp = avails; ravp != (avail_p) 0; ravp = ravp->av_before) {
  65. if (ravp->av_result == vn) {
  66. if (ravp->av_instr == (byte) op_aar)
  67. return find_base(ravp->av_ofirst);
  68. if (ravp->av_instr == (byte) op_ads)
  69. return find_base(ravp->av_oleft);
  70. }
  71. }
  72. /* Bad luck. */
  73. return (entity_p) 0;
  74. }
  75. static bool obj_overlap(obj_p op1, obj_p op2)
  76. {
  77. /* Op1 and op2 point to two objects in the same datablock.
  78. * Obj_overlap returns whether these objects might overlap.
  79. */
  80. obj_p tmp;
  81. if (op1->o_off > op2->o_off) {
  82. /* Exchange them. */
  83. tmp = op1; op1 = op2; op2 = tmp;
  84. }
  85. return op1->o_size == UNKNOWN_SIZE ||
  86. op1->o_off + op1->o_size > op2->o_off;
  87. }
  88. #define same_datablock(o1, o2) ((o1)->o_dblock == (o2)->o_dblock)
  89. static bool addr_local(entity_p enp)
  90. {
  91. /* Is enp the address of a stack item. */
  92. if (enp == (entity_p) 0) return FALSE;
  93. return enp->en_kind == ENALOCAL || enp->en_kind == ENALOCBASE ||
  94. enp->en_kind == ENAARGBASE;
  95. }
  96. static bool addr_external(entity_p enp)
  97. {
  98. /* Is enp the address of an external. */
  99. return enp != (entity_p) 0 && enp->en_kind == ENAEXTERNAL;
  100. }
  101. static void kill_external(obj_p obp, int indir)
  102. {
  103. /* A store is done via the object in obp. If this store is direct
  104. * we kill directly accessed entities in the same data block only
  105. * if they overlap with obp, otherwise we kill everything in the
  106. * data block. Indirectly accessed entities of which it can not be
  107. * proven taht they are not in the same data block, are killed in
  108. * both cases.
  109. */
  110. Lindex i;
  111. OUTTRACE("kill external", 0);
  112. for (i = Lfirst(entities); i != (Lindex) 0; i = Lnext(i, entities)) {
  113. entity_p enp = en_elem(i);
  114. entity_p base;
  115. switch (enp->en_kind) {
  116. case ENEXTERNAL:
  117. if (!same_datablock(enp->en_ext, obp))
  118. break;
  119. if (!indir && !obj_overlap(enp->en_ext, obp))
  120. break;
  121. OUTTRACE("kill %d", enp->en_vn);
  122. enp->en_vn = newvalnum();
  123. break;
  124. case ENINDIR:
  125. case ENOFFSETTED:
  126. case ENARRELEM:
  127. /* We spare its value number if we are sure
  128. * that its (base) address points into the
  129. * stack or into another data block.
  130. */
  131. base = find_base(base_valno(enp));
  132. if (addr_local(base))
  133. break;
  134. if (addr_external(base) &&
  135. !same_datablock(base->en_ext, obp)
  136. )
  137. break;
  138. OUTTRACE("kill %d", enp->en_vn);
  139. enp->en_vn = newvalnum();
  140. break;
  141. }
  142. }
  143. }
  144. static bool loc_overlap(entity_p enp1, entity_p enp2)
  145. {
  146. /* Enp1 and enp2 point to two locals. Loc_overlap returns whether
  147. * they overlap.
  148. */
  149. entity_p tmp;
  150. assert(enp1->en_kind == ENLOCAL && enp2->en_kind == ENLOCAL);
  151. if (enp1->en_loc > enp2->en_loc) {
  152. /* Exchange them. */
  153. tmp = enp1; enp1 = enp2; enp2 = tmp;
  154. }
  155. if (enp1->en_loc < 0 && enp2->en_loc >= 0)
  156. return FALSE; /* Locals and parameters do not overlap. */
  157. else return enp1->en_size == UNKNOWN_SIZE ||
  158. enp1->en_loc + enp1->en_size > enp2->en_loc;
  159. }
  160. static void kill_local(entity_p enp, bool indir)
  161. {
  162. /* This time a store is done into an ENLOCAL. */
  163. Lindex i;
  164. OUTTRACE("kill local", 0);
  165. for (i = Lfirst(entities); i != (Lindex) 0; i = Lnext(i, entities)) {
  166. entity_p rep = en_elem(i);
  167. entity_p base;
  168. switch (rep->en_kind) {
  169. case ENLOCAL:
  170. if (indir) {
  171. /* Kill locals that might be stored into
  172. * via a pointer. Note: enp not used.
  173. */
  174. if (!is_regvar(rep->en_loc)) {
  175. OUTTRACE("kill %d", rep->en_vn);
  176. rep->en_vn = newvalnum();
  177. }
  178. } else if (loc_overlap(rep, enp)) {
  179. /* Only kill overlapping locals. */
  180. OUTTRACE("kill %d", rep->en_vn);
  181. rep->en_vn = newvalnum();
  182. }
  183. break;
  184. case ENINDIR:
  185. case ENOFFSETTED:
  186. case ENARRELEM:
  187. if (!is_regvar(enp->en_loc)) {
  188. base = find_base(base_valno(rep));
  189. if (!addr_external(base)) {
  190. OUTTRACE("kill %d", rep->en_vn);
  191. rep->en_vn = newvalnum();
  192. }
  193. }
  194. break;
  195. case ENALOCBASE:
  196. case ENAARGBASE:
  197. if (enp->en_loc == 0 && rep->en_levels >= 1) {
  198. rep->en_vn = newvalnum();
  199. }
  200. break;
  201. }
  202. }
  203. }
  204. static void kill_sim()
  205. {
  206. /* A store is done into the ENIGNMASK. */
  207. Lindex i;
  208. OUTTRACE("kill sim", 0);
  209. for (i = Lfirst(entities); i != (Lindex) 0; i = Lnext(i, entities)) {
  210. entity_p rep = en_elem(i);
  211. if (rep->en_kind == ENIGNMASK) {
  212. OUTTRACE("kill %d", rep->en_vn);
  213. rep->en_vn = newvalnum();
  214. return; /* There is only one ignoremask. */
  215. }
  216. }
  217. }
  218. void kill_direct(entity_p enp)
  219. {
  220. /* A store will be done into enp. We must forget the values of all the
  221. * entities this one may overlap with.
  222. */
  223. switch (enp->en_kind) {
  224. default:
  225. assert(FALSE);
  226. break;
  227. case ENEXTERNAL:
  228. kill_external(enp->en_ext, FALSE);
  229. break;
  230. case ENLOCAL:
  231. kill_local(enp, FALSE);
  232. break;
  233. case ENIGNMASK:
  234. kill_sim();
  235. break;
  236. }
  237. }
  238. void kill_indir(entity_p enp)
  239. {
  240. /* An indirect store is done, in an ENINDIR,
  241. * an ENOFFSETTED or an ENARRELEM.
  242. */
  243. entity_p p;
  244. /* If we can find the (base) address of this entity, then we can spare
  245. * the entities that are provably not pointed to by the address.
  246. * We will also make use of the MES 3 pseudo's, generated by
  247. * the front-end. When a MES 3 is generated for a local, this local
  248. * will not be referenced indirectly.
  249. */
  250. if ((p = find_base(base_valno(enp))) == (entity_p) 0) {
  251. kill_much(); /* Kill all entities without registermessage. */
  252. } else {
  253. switch (p->en_kind) {
  254. case ENAEXTERNAL:
  255. /* An indirect store into global data. */
  256. kill_external(p->en_ext, TRUE);
  257. break;
  258. case ENALOCAL:
  259. case ENALOCBASE:
  260. case ENAARGBASE:
  261. /* An indirect store into stack data. */
  262. kill_local(p, TRUE);
  263. break;
  264. }
  265. }
  266. }
  267. void kill_much()
  268. {
  269. /* Kills all killable entities,
  270. * except the locals for which a registermessage was generated.
  271. */
  272. register Lindex i;
  273. OUTTRACE("kill much", 0);
  274. for (i = Lfirst(entities); i != (Lindex) 0; i = Lnext(i, entities)) {
  275. register entity_p rep = en_elem(i);
  276. if (rep->en_static) continue;
  277. if (rep->en_kind == ENLOCAL && is_regvar(rep->en_loc)) continue;
  278. OUTTRACE("kill %d", rep->en_vn);
  279. rep->en_vn = newvalnum();
  280. }
  281. }
  282. static bool bad_procflags(proc_p pp)
  283. {
  284. /* Return whether the flags about the procedure in pp indicate
  285. * that we have little information about it. It might be that
  286. * we haven't seen the text of pp, or that we have seen that pp
  287. * calls a procedure which we haven't seen the text of.
  288. */
  289. return !(pp->p_flags1 & PF_BODYSEEN) || (pp->p_flags1 & PF_CALUNKNOWN);
  290. }
  291. static void kill_globset(cset s)
  292. {
  293. /* S is a set of global variables that might be changed.
  294. * We act as if a direct store is done into each of them.
  295. */
  296. Cindex i;
  297. OUTTRACE("kill globset", 0);
  298. for (i = Cfirst(s); i != (Cindex) 0; i = Cnext(i,s)) {
  299. kill_external(omap[Celem(i)], FALSE);
  300. }
  301. }
  302. void kill_call(proc_p pp)
  303. {
  304. /* Kill everything that might be destroyed by calling
  305. * the procedure in pp.
  306. */
  307. if (bad_procflags(pp)) {
  308. /* We don't know enough about this procedure. */
  309. kill_much();
  310. } else if (pp->p_change->c_flags & CF_INDIR) {
  311. /* The procedure does an indirect store. */
  312. kill_much();
  313. } else {
  314. /* Procedure might affect global data. */
  315. kill_globset(pp->p_change->c_ext);
  316. }
  317. }
  318. void kill_all()
  319. {
  320. /* Kills all entities. */
  321. Lindex i;
  322. OUTTRACE("kill all entities", 0);
  323. for (i = Lfirst(entities); i != (Lindex) i; i = Lnext(i, entities)) {
  324. entity_p enp = en_elem(i);
  325. OUTTRACE("kill %d", enp->en_vn);
  326. enp->en_vn = newvalnum();
  327. }
  328. }