bo.c 6.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318
  1. /* B R A N C H O P T I M I Z A T I O N
  2. *
  3. * B O . C
  4. */
  5. #include <stdio.h>
  6. #include "../share/types.h"
  7. #include "../share/debug.h"
  8. #include "../share/global.h"
  9. #include "../share/files.h"
  10. #include "../share/get.h"
  11. #include "../share/put.h"
  12. #include "../share/lset.h"
  13. #include "../share/map.h"
  14. #include "../share/alloc.h"
  15. #include "../share/aux.h"
  16. #include "../share/def.h"
  17. #include "../share/go.h"
  18. #include "../../../h/em_mnem.h"
  19. #include "../../../h/em_pseu.h"
  20. #include "../../../h/em_spec.h"
  21. #define LP_BLOCKS lp_extend->lpx_ra.lpx_blocks
  22. #define newbolpx() (lpext_p) newstruct(lpext_ra)
  23. #define oldbolpx(x) oldstruct(lpext_ra,x)
  24. STATIC int Sbo; /* #optimizations found */
  25. #define DLINK(l1,l2) l1->l_next=l2; l2->l_prev=l1
  26. /* This module performs some very simple branch optimizations.
  27. *
  28. * I) Look for pairs of basic blocks (B1,B2), such that
  29. * SUCC(b1) = {B2} and
  30. * PRED(B2) = {B1}.
  31. * In this case B1 and B2 can be combined into one block.
  32. * This optimization is mainly succesful:
  33. * 1) for switch statements in C, as the C compiler generates a branch
  34. * over the entire switch.
  35. * 2) for return statements, if the only way to return from a procedure
  36. * is via a return statement somewhere in the middle of the procedure.
  37. * II) Optimize while statements. Transformations like:
  38. * 1: jmp 2
  39. * tst cond 1:
  40. * beq 2f S
  41. * S 2:
  42. * jmp 1 tst cond
  43. * 2: bneq 1
  44. * are done by this optimization.
  45. */
  46. STATIC line_p last_code(lines,skip_pseu)
  47. line_p lines;
  48. bool skip_pseu;
  49. {
  50. /* Determine the last line of a list */
  51. register line_p l;
  52. for (l = lines; l->l_next != (line_p) 0; l = l->l_next);
  53. if (skip_pseu) {
  54. while (INSTR(l) < sp_fmnem || INSTR(l) > sp_lmnem) l = PREV(l);
  55. }
  56. return l;
  57. }
  58. STATIC short cc_tab[12] =
  59. {op_blt,op_zlt,op_ble,op_zle,op_beq,op_zeq,
  60. op_zne,op_bne,op_zgt,op_bgt,op_zge,op_bge};
  61. STATIC short rev_cond(cond)
  62. short cond;
  63. {
  64. register i;
  65. for (i = 0; i < 12; i++) {
  66. if (cond == cc_tab[i]) return cc_tab[11-i];
  67. }
  68. return op_nop;
  69. }
  70. STATIC bool is_bcc(l)
  71. line_p l;
  72. {
  73. return rev_cond(INSTR(l)) != op_nop;
  74. }
  75. STATIC bo_optloop(p,b,x,bra,bcc)
  76. proc_p p;
  77. bblock_p b,x;
  78. line_p bra,bcc;
  79. {
  80. bblock_p prevb,n;
  81. line_p l;
  82. if (b->b_start == bra) {
  83. b->b_start = (line_p) 0;
  84. } else {
  85. PREV(bra)->l_next = (line_p) 0;
  86. }
  87. PREV(bra) = (line_p) 0;
  88. bcc->l_instr = rev_cond(INSTR(bcc));
  89. n = x->b_next;
  90. l = n->b_start;
  91. if (l == (line_p) 0 || INSTR(l) != op_lab) {
  92. l = newline(OPINSTRLAB);
  93. l->l_instr = op_lab;
  94. INSTRLAB(l) = freshlabel();
  95. if (n->b_start != (line_p) 0) {
  96. DLINK(l,n->b_start);
  97. }
  98. n->b_start = l;
  99. }
  100. INSTRLAB(bcc) = INSTRLAB(l);
  101. for (prevb = p->p_start; prevb != (bblock_p) 0 && prevb->b_next != x;
  102. prevb = prevb->b_next);
  103. if (prevb == (bblock_p) 0) {
  104. p->p_start = x->b_next;
  105. } else {
  106. prevb->b_next = x->b_next;
  107. l = last_instr(prevb);
  108. if (l == (line_p) 0) {
  109. prevb->b_start = bra;
  110. } else {
  111. if (INSTR(l) == op_bra &&
  112. INSTRLAB(l) == INSTRLAB(bra)) {
  113. oldline(bra);
  114. } else {
  115. appnd_line(bra,l);
  116. }
  117. }
  118. }
  119. x->b_next = b->b_next;
  120. b->b_next = x;
  121. }
  122. STATIC bo_tryloop(p,loop)
  123. proc_p p;
  124. lset loop;
  125. {
  126. Lindex i,j;
  127. bblock_p b,x;
  128. line_p bra,bcc;
  129. for (i = Lfirst(loop); i != (Lindex) 0; i = Lnext(i,loop)) {
  130. b = (bblock_p) Lelem(i);
  131. if (b->b_next != (bblock_p) 0 && !Lis_elem(b->b_next,loop)) {
  132. j = Lfirst(b->b_succ);
  133. if (j != (Lindex) 0 &&
  134. (bra = last_instr(b)) != (line_p) 0 &&
  135. INSTR(bra) == op_bra) {
  136. x = (bblock_p) Lelem(j); /* single successor */
  137. if (Lis_elem(b->b_next,x->b_succ) &&
  138. is_bcc((bcc = last_instr(x)))) {
  139. OUTVERBOSE("branch optimization proc %d block %d\n", curproc->p_id,x->b_id);
  140. Sbo++;
  141. bo_optloop(p,b,x,bra,bcc);
  142. return;
  143. }
  144. }
  145. }
  146. }
  147. }
  148. STATIC bo_loops(p)
  149. proc_p p;
  150. {
  151. Lindex i;
  152. loop_p lp;
  153. for (i = Lfirst(p->p_loops); i != (Lindex) 0; i = Lnext(i,p->p_loops)) {
  154. lp = (loop_p) (Lelem(i));
  155. bo_tryloop(p,lp->LP_BLOCKS);
  156. }
  157. }
  158. STATIC mv_code(b1,b2)
  159. bblock_p b1,b2;
  160. {
  161. line_p l,x;
  162. l = last_code(b2->b_start,TRUE);
  163. DLINK(l,b1->b_start);
  164. x = l->l_next;
  165. if (INSTR(l) == op_bra) {
  166. rm_line(l,b2);
  167. }
  168. if (INSTR(x) == op_lab) {
  169. rm_line(x,b2);
  170. }
  171. }
  172. bo_switch(b)
  173. bblock_p b;
  174. {
  175. bblock_p s,x;
  176. Lindex i;
  177. line_p l;
  178. if (Lnrelems(b->b_succ) == 1) {
  179. s = (bblock_p) Lelem(Lfirst(b->b_succ));
  180. if (b->b_start != (line_p) 0 &&
  181. s->b_start != (line_p) 0 &&
  182. Lnrelems(s->b_pred) == 1 &&
  183. (s->b_next == (bblock_p) 0 ||
  184. !Lis_elem(s->b_next,s->b_succ))) {
  185. l = last_code(s->b_start,FALSE);
  186. if (INSTR(l) == ps_end) {
  187. if (PREV(l) == (line_p) 0) return;
  188. PREV(l)->l_next = (line_p) 0;
  189. PREV(l) = (line_p) 0;
  190. } else {
  191. l = (line_p) 0;
  192. }
  193. OUTVERBOSE("branch optimization in proc %d, block %d",curproc->p_id,b->b_id);
  194. Sbo++;
  195. Ldeleteset(b->b_succ);
  196. b->b_succ = s->b_succ;
  197. Ldeleteset(s->b_pred);
  198. s->b_succ = Lempty_set();
  199. s->b_pred = Lempty_set();
  200. for (i = Lfirst(b->b_succ); i != (Lindex) 0;
  201. i = Lnext(i,b->b_succ)) {
  202. x = (bblock_p) Lelem(i);
  203. Lremove(s,&x->b_pred);
  204. Ladd(b,&x->b_pred);
  205. if (x->b_idom == s) {
  206. x->b_idom = b;
  207. }
  208. }
  209. mv_code(s,b);
  210. s->b_start = l;
  211. }
  212. }
  213. }
  214. STATIC bo_extproc(p)
  215. proc_p p;
  216. {
  217. /* Allocate the extended data structures for procedure p */
  218. register loop_p lp;
  219. register Lindex pi;
  220. for (pi = Lfirst(p->p_loops); pi != (Lindex) 0;
  221. pi = Lnext(pi,p->p_loops)) {
  222. lp = (loop_p) Lelem(pi);
  223. lp->lp_extend = newbolpx();
  224. }
  225. }
  226. STATIC loop_blocks(p)
  227. proc_p p;
  228. {
  229. /* Compute the LP_BLOCKS sets for all loops of p */
  230. register bblock_p b;
  231. register Lindex i;
  232. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  233. for (i = Lfirst(b->b_loops); i != (Lindex) 0;
  234. i = Lnext(i,b->b_loops)) {
  235. Ladd(b,&(((loop_p) Lelem(i))->LP_BLOCKS));
  236. }
  237. }
  238. }
  239. STATIC bo_cleanproc(p)
  240. proc_p p;
  241. {
  242. /* Allocate the extended data structures for procedure p */
  243. register loop_p lp;
  244. register Lindex pi;
  245. register bblock_p b;
  246. for (pi = Lfirst(p->p_loops); pi != (Lindex) 0;
  247. pi = Lnext(pi,p->p_loops)) {
  248. lp = (loop_p) Lelem(pi);
  249. oldbolpx(lp->lp_extend);
  250. }
  251. }
  252. bo_optimize(p)
  253. proc_p p;
  254. {
  255. bblock_p b;
  256. bo_extproc(p);
  257. loop_blocks(p);
  258. bo_loops(p);
  259. for (b = p->p_start; b != 0; b = b->b_next) {
  260. bo_switch(b);
  261. }
  262. bo_cleanproc(p);
  263. }
  264. main(argc,argv)
  265. int argc;
  266. char *argv[];
  267. {
  268. go(argc,argv,no_action,bo_optimize,no_action,no_action);
  269. report("branch optimizations", Sbo);
  270. exit(0);
  271. }