cs_kill.c 8.8 KB

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