cj.c 8.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363
  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 R O S S J U M P I N G
  7. *
  8. * CJ.H
  9. *
  10. */
  11. #include <stdlib.h>
  12. #include <stdio.h>
  13. #include <em_mnem.h>
  14. #include <em_spec.h>
  15. #include "../share/types.h"
  16. #include "../share/debug.h"
  17. #include "../share/global.h"
  18. #include "../share/files.h"
  19. #include "../share/get.h"
  20. #include "../share/put.h"
  21. #include "../share/lset.h"
  22. #include "../share/map.h"
  23. #include "../share/alloc.h"
  24. #include "../share/aux.h"
  25. #include "../share/def.h"
  26. #include "../share/stack_chg.h"
  27. #include "../share/go.h"
  28. /* Cross jumping performs optimzations like:
  29. *
  30. * if cond then goto L1; if cond then goto L1
  31. * S1; -----> S1;
  32. * S2; goto L3;
  33. * goto L2; L1:
  34. * L1: S3;
  35. * S3; L3:
  36. * S2; S2;
  37. * L2:
  38. *
  39. * CJ looks for two basic blocks b1 and b2 with the following properties:
  40. * - there exists a basic block S such that SUCC(b1) = SUCC(b2) = {S}
  41. * (so both have only 1 successor)
  42. * - the last N (N > 0) instructions of b1 and b2, not counting a possible
  43. * BRAnch instruction, are the same.
  44. * As a result of the first condition, at least of the two blocks must end
  45. * on an (unconditional) BRAnch instruction. If both end on a BRA, one block
  46. * is chosen at random. Assume this block is b1. A new label L is put just
  47. * before the N common instructions of block b2 (so this block is split
  48. * into two). The BRA of b1 is changed into a BRA L. So dynamically the same
  49. * instructions are executed in a slightly different order; yet the size of
  50. * the code has become smaller.
  51. */
  52. STATIC int Scj; /* number of optimizations found */
  53. STATIC showinstr();
  54. #define DLINK(l1,l2) l1->l_next=l2; l2->l_prev=l1
  55. STATIC bool same_instr(l1,l2)
  56. line_p l1,l2;
  57. {
  58. /* See if l1 and l2 are the same instruction */
  59. if (l1 == 0 || l2 == 0 || TYPE(l1) != TYPE(l2)) return FALSE;
  60. if (INSTR(l1) != INSTR(l2)) return FALSE;
  61. switch(TYPE(l1)) {
  62. case OPSHORT: return SHORT(l1) == SHORT(l2);
  63. case OPOFFSET: return OFFSET(l1) == OFFSET(l2);
  64. case OPPROC: return PROC(l1) == PROC(l2);
  65. case OPOBJECT: return OBJ(l1) == OBJ(l2);
  66. case OPINSTRLAB: return INSTRLAB(l1) == INSTRLAB(l2);
  67. case OPNO: return TRUE;
  68. default: return FALSE;
  69. }
  70. }
  71. STATIC line_p last_mnem(b)
  72. bblock_p b;
  73. {
  74. /* Determine the last line of a list */
  75. register line_p l;
  76. for (l = b->b_start; l->l_next != (line_p) 0; l = l->l_next);
  77. while (l != (line_p) 0 && (INSTR(l) < sp_fmnem || INSTR(l) > sp_lmnem)) {
  78. l = PREV(l);
  79. }
  80. return l;
  81. }
  82. STATIC bool is_desirable(text)
  83. line_p text;
  84. {
  85. /* We avoid to generate a BRAnch in the middle of some expression,
  86. * as the code generator will write the contents of the fakestack
  87. * to the real stack if it encounters a BRA. We do not avoid to
  88. * split the parameter-pushing code of a subroutine call into two,
  89. * as the parameters are pushed on the real stack anyway.
  90. * So e.g. "LOL a ; LOL b; ADI" will not be split, but
  91. * "LOL a; LOL b; CAL f" may be split.
  92. */
  93. line_p l;
  94. bool ok;
  95. int stack_diff,pop,push;
  96. stack_diff = 0;
  97. for (l = text; l != (line_p) 0; l = l->l_next) {
  98. switch(INSTR(l)) {
  99. case op_cal:
  100. case op_asp:
  101. case op_bra:
  102. return TRUE;
  103. }
  104. line_change(l,&ok,&pop,&push);
  105. /* printf("instr %d, pop %d, push %d, ok %d\n",INSTR(l),pop,push,ok); */
  106. if (!ok || (stack_diff -= pop) < 0) {
  107. return FALSE;
  108. } else {
  109. stack_diff += push;
  110. }
  111. }
  112. return TRUE;
  113. }
  114. STATIC cp_loops(b1,b2)
  115. bblock_p b1,b2;
  116. {
  117. /* Copy the loopset of b2 to b1 */
  118. Lindex i;
  119. loop_p lp;
  120. for (i = Lfirst(b2->b_loops); i != (Lindex) 0;
  121. i = Lnext(i,b2->b_loops)) {
  122. lp = (loop_p) Lelem(i);
  123. Ladd(lp,&b1->b_loops);
  124. }
  125. }
  126. STATIC jump_cross(l1,l2,b1,b2)
  127. line_p l1,l2;
  128. bblock_p b1,b2;
  129. {
  130. /* A cross-jump from block b2 to block b1 is found; the code in
  131. * block b2 from line l2 up to the BRAnch is removed; block b1 is
  132. * split into two; the second part consists of a new label
  133. * followed by the code from l1 till the end of the block.
  134. */
  135. line_p l;
  136. bblock_p b;
  137. bblock_p s;
  138. /* First adjust the control flow graph */
  139. b = freshblock(); /* create a new basic block */
  140. b->b_succ = b1->b_succ;
  141. /* SUCC(b1) = {b} */
  142. b1->b_succ = Lempty_set(); Ladd(b,&b1->b_succ);
  143. /* SUCC(b2) = {b} */
  144. Ldeleteset(b2->b_succ); b2->b_succ = Lempty_set(); Ladd(b,&b2->b_succ);
  145. /* PRED(b) = {b1,b2} */
  146. b->b_pred = Lempty_set(); Ladd(b1,&b->b_pred); Ladd(b2,&b->b_pred);
  147. /* PRED(SUCC(b)) := PRED(SUCC(b)) - {b1,b2} + {b} */
  148. assert(Lnrelems(b->b_succ) == 1);
  149. s = (bblock_p) Lelem(Lfirst(b->b_succ));
  150. Lremove(b1,&s->b_pred); Lremove(b2,&s->b_pred); Ladd(b,&s->b_pred);
  151. cp_loops(b,b1);
  152. b->b_idom = common_dom(b1,b2);
  153. b->b_flags = b1->b_flags;
  154. b->b_next = b1->b_next;
  155. b1->b_next = b;
  156. /* Now adjust the EM text */
  157. l = PREV(l1);
  158. while (l && INSTR(l) == op_lab) {
  159. l1 = l;
  160. l = PREV(l);
  161. }
  162. if (l == (line_p) 0) {
  163. b1->b_start = (line_p) 0;
  164. } else {
  165. l->l_next = (line_p) 0;
  166. }
  167. if (INSTR(l1) == op_lab) {
  168. l = l1;
  169. }
  170. else {
  171. l = newline(OPINSTRLAB);
  172. l->l_instr = op_lab;
  173. INSTRLAB(l) = freshlabel();
  174. DLINK(l,l1);
  175. }
  176. b->b_start = l;
  177. for (l = l2; INSTR(l) != op_bra;) {
  178. line_p next = l->l_next;
  179. assert (l != (line_p) 0);
  180. rm_line(l,b2);
  181. l = next;
  182. }
  183. INSTRLAB(l) = INSTRLAB(b->b_start);
  184. }
  185. STATIC bool try_tail(b1,b2)
  186. bblock_p b1,b2;
  187. {
  188. /* See if b1 and b2 end on the same sequence of instructions */
  189. line_p l1,l2;
  190. bblock_p b = (bblock_p) 0;
  191. int cnt = 0;
  192. /* printf("try block %d and %d\n",b1->b_id,b2->b_id); */
  193. if (b1->b_start == (line_p) 0 || b2->b_start == (line_p) 0) return FALSE;
  194. l1 = last_mnem(b1);
  195. l2 = last_mnem(b2);
  196. if (l1 == (line_p) 0 || l2 == (line_p) 0) return FALSE;
  197. /* printf("consider:\n"); showinstr(l1); showinstr(l2); */
  198. if (INSTR(l1) == op_bra) {
  199. b = b1;
  200. l1 = PREV(l1);
  201. }
  202. if (INSTR(l2) == op_bra) {
  203. b = b2;
  204. l2 = PREV(l2);
  205. }
  206. assert(b != (bblock_p) 0);
  207. while(same_instr(l1,l2)) {
  208. cnt++;
  209. l1 = PREV(l1);
  210. l2 = PREV(l2);
  211. /* printf("consider:\n"); showinstr(l1); showinstr(l2); */
  212. }
  213. if (cnt >= 1) {
  214. l1 = (l1 == 0 ? b1->b_start : l1->l_next);
  215. l2 = (l2 == 0 ? b2->b_start : l2->l_next);
  216. if (is_desirable(l1)) {
  217. if (b == b1) {
  218. jump_cross(l2,l1,b2,b1);
  219. Scj++;
  220. } else {
  221. jump_cross(l1,l2,b1,b2);
  222. Scj++;
  223. }
  224. return TRUE;
  225. }
  226. }
  227. return FALSE;
  228. }
  229. STATIC bool try_pred(b)
  230. bblock_p b;
  231. {
  232. /* See if there is any pair (b1,b2), both in PRED(b) for
  233. * which we can perform cross jumping.
  234. */
  235. register bblock_p b1,b2;
  236. register Lindex i,j;
  237. lset s = b->b_pred;
  238. for (i = Lfirst(s); i != (Lindex) 0; i = Lnext(i,s)) {
  239. b1 = (bblock_p) Lelem(i);
  240. if (Lnrelems(b1->b_succ) != 1) continue;
  241. for (j = Lfirst(s); j != (Lindex) 0; j = Lnext(j,s)) {
  242. b2 = (bblock_p) Lelem(j);
  243. if (b1 != b2 && Lnrelems(b2->b_succ) == 1) {
  244. if (try_tail(b1,b2)) return TRUE;
  245. }
  246. }
  247. }
  248. return FALSE;
  249. }
  250. cj_optimize(p)
  251. proc_p p;
  252. {
  253. /* Perform cross jumping for procedure p.
  254. * In case cases a cross-jumping optimization which give
  255. * new opportunities for further cross-jumping optimizations.
  256. * Hence we repeat the whole process for the entire procedure,
  257. * untill we find no further optimizations.
  258. */
  259. bblock_p b;
  260. bool changes = TRUE;
  261. if (IS_ENTERED_WITH_GTO(p)) return;
  262. while(changes) {
  263. changes = FALSE;
  264. b = p->p_start;
  265. while (b != (bblock_p) 0) {
  266. if (try_pred(b)) {
  267. changes = TRUE;
  268. } else {
  269. b = b->b_next;
  270. }
  271. }
  272. }
  273. }
  274. main(argc,argv)
  275. int argc;
  276. char *argv[];
  277. {
  278. go(argc,argv,no_action,cj_optimize,no_action,no_action);
  279. report("cross jumps",Scj);
  280. exit(0);
  281. }
  282. /******
  283. * Debugging stuff
  284. */
  285. extern char em_mnem[]; /* The mnemonics of the EM instructions. */
  286. STATIC showinstr(lnp) line_p lnp; {
  287. /* Makes the instruction in `lnp' human readable. Only lines that
  288. * can occur in expressions that are going to be eliminated are
  289. * properly handled.
  290. */
  291. if (lnp == 0) return;
  292. if (INSTR(lnp) < sp_fmnem || INSTR(lnp) > sp_lmnem) {
  293. printf("\t*** ?\n");
  294. return;
  295. }
  296. printf("\t%s", &em_mnem[4 * (INSTR(lnp)-sp_fmnem)]);
  297. switch (TYPE(lnp)) {
  298. case OPNO:
  299. break;
  300. case OPSHORT:
  301. printf(" %d", SHORT(lnp)); break;
  302. case OPOBJECT:
  303. printf(" %d", OBJ(lnp)->o_id); break;
  304. case OPOFFSET:
  305. printf(" %ld", OFFSET(lnp)); break;
  306. default:
  307. printf(" ?"); break;
  308. }
  309. printf("\n");
  310. } /* showinstr */