bo.c 6.8 KB

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