cj.c 8.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352
  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 void showinstr(line_p lnp);
  54. #define DLINK(l1,l2) l1->l_next=l2; l2->l_prev=l1
  55. static bool same_instr(line_p l1, line_p l2)
  56. {
  57. /* See if l1 and l2 are the same instruction */
  58. if (l1 == 0 || l2 == 0 || TYPE(l1) != TYPE(l2)) return FALSE;
  59. if (INSTR(l1) != INSTR(l2)) return FALSE;
  60. switch(TYPE(l1)) {
  61. case OPSHORT: return SHORT(l1) == SHORT(l2);
  62. case OPOFFSET: return OFFSET(l1) == OFFSET(l2);
  63. case OPPROC: return PROC(l1) == PROC(l2);
  64. case OPOBJECT: return OBJ(l1) == OBJ(l2);
  65. case OPINSTRLAB: return INSTRLAB(l1) == INSTRLAB(l2);
  66. case OPNO: return TRUE;
  67. default: return FALSE;
  68. }
  69. }
  70. static line_p last_mnem(bblock_p b)
  71. {
  72. /* Determine the last line of a list */
  73. line_p l;
  74. for (l = b->b_start; l->l_next != (line_p) 0; l = l->l_next);
  75. while (l != (line_p) 0 && (INSTR(l) < sp_fmnem || INSTR(l) > sp_lmnem)) {
  76. l = PREV(l);
  77. }
  78. return l;
  79. }
  80. static bool is_desirable(line_p text)
  81. {
  82. /* We avoid to generate a BRAnch in the middle of some expression,
  83. * as the code generator will write the contents of the fakestack
  84. * to the real stack if it encounters a BRA. We do not avoid to
  85. * split the parameter-pushing code of a subroutine call into two,
  86. * as the parameters are pushed on the real stack anyway.
  87. * So e.g. "LOL a ; LOL b; ADI" will not be split, but
  88. * "LOL a; LOL b; CAL f" may be split.
  89. */
  90. line_p l;
  91. bool ok;
  92. int stack_diff,pop,push;
  93. stack_diff = 0;
  94. for (l = text; l != (line_p) 0; l = l->l_next) {
  95. switch(INSTR(l)) {
  96. case op_cal:
  97. case op_asp:
  98. case op_bra:
  99. return TRUE;
  100. }
  101. line_change(l,&ok,&pop,&push);
  102. /* printf("instr %d, pop %d, push %d, ok %d\n",INSTR(l),pop,push,ok); */
  103. if (!ok || (stack_diff -= pop) < 0) {
  104. return FALSE;
  105. } else {
  106. stack_diff += push;
  107. }
  108. }
  109. return TRUE;
  110. }
  111. static void cp_loops(bblock_p b1, bblock_p b2)
  112. {
  113. /* Copy the loopset of b2 to b1 */
  114. Lindex i;
  115. loop_p lp;
  116. for (i = Lfirst(b2->b_loops); i != (Lindex) 0;
  117. i = Lnext(i,b2->b_loops)) {
  118. lp = (loop_p) Lelem(i);
  119. Ladd(lp,&b1->b_loops);
  120. }
  121. }
  122. static void jump_cross(line_p l1, line_p l2, bblock_p b1, bblock_p b2)
  123. {
  124. /* A cross-jump from block b2 to block b1 is found; the code in
  125. * block b2 from line l2 up to the BRAnch is removed; block b1 is
  126. * split into two; the second part consists of a new label
  127. * followed by the code from l1 till the end of the block.
  128. */
  129. line_p l;
  130. bblock_p b;
  131. bblock_p s;
  132. /* First adjust the control flow graph */
  133. b = freshblock(); /* create a new basic block */
  134. b->b_succ = b1->b_succ;
  135. /* SUCC(b1) = {b} */
  136. b1->b_succ = Lempty_set(); Ladd(b,&b1->b_succ);
  137. /* SUCC(b2) = {b} */
  138. Ldeleteset(b2->b_succ); b2->b_succ = Lempty_set(); Ladd(b,&b2->b_succ);
  139. /* PRED(b) = {b1,b2} */
  140. b->b_pred = Lempty_set(); Ladd(b1,&b->b_pred); Ladd(b2,&b->b_pred);
  141. /* PRED(SUCC(b)) := PRED(SUCC(b)) - {b1,b2} + {b} */
  142. assert(Lnrelems(b->b_succ) == 1);
  143. s = (bblock_p) Lelem(Lfirst(b->b_succ));
  144. Lremove(b1,&s->b_pred); Lremove(b2,&s->b_pred); Ladd(b,&s->b_pred);
  145. cp_loops(b,b1);
  146. b->b_idom = common_dom(b1,b2);
  147. b->b_flags = b1->b_flags;
  148. b->b_next = b1->b_next;
  149. b1->b_next = b;
  150. /* Now adjust the EM text */
  151. l = PREV(l1);
  152. while (l && INSTR(l) == op_lab) {
  153. l1 = l;
  154. l = PREV(l);
  155. }
  156. if (l == (line_p) 0) {
  157. b1->b_start = (line_p) 0;
  158. } else {
  159. l->l_next = (line_p) 0;
  160. }
  161. if (INSTR(l1) == op_lab) {
  162. l = l1;
  163. }
  164. else {
  165. l = newline(OPINSTRLAB);
  166. l->l_instr = op_lab;
  167. INSTRLAB(l) = freshlabel();
  168. DLINK(l,l1);
  169. }
  170. b->b_start = l;
  171. for (l = l2; INSTR(l) != op_bra;) {
  172. line_p next = l->l_next;
  173. assert (l != (line_p) 0);
  174. rm_line(l,b2);
  175. l = next;
  176. }
  177. INSTRLAB(l) = INSTRLAB(b->b_start);
  178. }
  179. static bool try_tail(bblock_p b1, bblock_p b2)
  180. {
  181. /* See if b1 and b2 end on the same sequence of instructions */
  182. line_p l1,l2;
  183. bblock_p b = (bblock_p) 0;
  184. int cnt = 0;
  185. /* printf("try block %d and %d\n",b1->b_id,b2->b_id); */
  186. if (b1->b_start == (line_p) 0 || b2->b_start == (line_p) 0) return FALSE;
  187. l1 = last_mnem(b1);
  188. l2 = last_mnem(b2);
  189. if (l1 == (line_p) 0 || l2 == (line_p) 0) return FALSE;
  190. /* printf("consider:\n"); showinstr(l1); showinstr(l2); */
  191. if (INSTR(l1) == op_bra) {
  192. b = b1;
  193. l1 = PREV(l1);
  194. }
  195. if (INSTR(l2) == op_bra) {
  196. b = b2;
  197. l2 = PREV(l2);
  198. }
  199. assert(b != (bblock_p) 0);
  200. while(same_instr(l1,l2)) {
  201. cnt++;
  202. l1 = PREV(l1);
  203. l2 = PREV(l2);
  204. /* printf("consider:\n"); showinstr(l1); showinstr(l2); */
  205. }
  206. if (cnt >= 1) {
  207. l1 = (l1 == 0 ? b1->b_start : l1->l_next);
  208. l2 = (l2 == 0 ? b2->b_start : l2->l_next);
  209. if (is_desirable(l1)) {
  210. if (b == b1) {
  211. jump_cross(l2,l1,b2,b1);
  212. Scj++;
  213. } else {
  214. jump_cross(l1,l2,b1,b2);
  215. Scj++;
  216. }
  217. return TRUE;
  218. }
  219. }
  220. return FALSE;
  221. }
  222. static bool try_pred(bblock_p b)
  223. {
  224. /* See if there is any pair (b1,b2), both in PRED(b) for
  225. * which we can perform cross jumping.
  226. */
  227. register bblock_p b1,b2;
  228. register Lindex i,j;
  229. lset s = b->b_pred;
  230. for (i = Lfirst(s); i != (Lindex) 0; i = Lnext(i,s)) {
  231. b1 = (bblock_p) Lelem(i);
  232. if (Lnrelems(b1->b_succ) != 1) continue;
  233. for (j = Lfirst(s); j != (Lindex) 0; j = Lnext(j,s)) {
  234. b2 = (bblock_p) Lelem(j);
  235. if (b1 != b2 && Lnrelems(b2->b_succ) == 1) {
  236. if (try_tail(b1,b2)) return TRUE;
  237. }
  238. }
  239. }
  240. return FALSE;
  241. }
  242. int cj_optimize(void *param)
  243. {
  244. /* Perform cross jumping for procedure p.
  245. * In case cases a cross-jumping optimization which give
  246. * new opportunities for further cross-jumping optimizations.
  247. * Hence we repeat the whole process for the entire procedure,
  248. * untill we find no further optimizations.
  249. */
  250. proc_p p = (proc_p)param;
  251. bblock_p b;
  252. bool changes = TRUE;
  253. if (IS_ENTERED_WITH_GTO(p)) return 0;
  254. while(changes) {
  255. changes = FALSE;
  256. b = p->p_start;
  257. while (b != (bblock_p) 0) {
  258. if (try_pred(b)) {
  259. changes = TRUE;
  260. } else {
  261. b = b->b_next;
  262. }
  263. }
  264. }
  265. return 0;
  266. }
  267. int main(int argc, char *argv[])
  268. {
  269. go(argc,argv,no_action,cj_optimize,no_action,no_action);
  270. report("cross jumps",Scj);
  271. exit(0);
  272. }
  273. /******
  274. * Debugging stuff
  275. */
  276. extern char em_mnem[]; /* The mnemonics of the EM instructions. */
  277. static void showinstr(line_p lnp)
  278. {
  279. /* Makes the instruction in `lnp' human readable. Only lines that
  280. * can occur in expressions that are going to be eliminated are
  281. * properly handled.
  282. */
  283. if (lnp == 0) return;
  284. if (INSTR(lnp) < sp_fmnem || INSTR(lnp) > sp_lmnem) {
  285. printf("\t*** ?\n");
  286. return;
  287. }
  288. printf("\t%s", &em_mnem[4 * (INSTR(lnp)-sp_fmnem)]);
  289. switch (TYPE(lnp)) {
  290. case OPNO:
  291. break;
  292. case OPSHORT:
  293. printf(" %d", SHORT(lnp)); break;
  294. case OPOBJECT:
  295. printf(" %d", OBJ(lnp)->o_id); break;
  296. case OPOFFSET:
  297. printf(" %ld", OFFSET(lnp)); break;
  298. default:
  299. printf(" ?"); break;
  300. }
  301. printf("\n");
  302. } /* showinstr */