cf_loop.c 9.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405
  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 O N T R O L F L O W
  7. *
  8. * C F _ L O O P . C
  9. */
  10. #include "../share/types.h"
  11. #include "../share/debug.h"
  12. #include "../share/lset.h"
  13. #include "../share/alloc.h"
  14. #include "../share/aux.h"
  15. #include "cf.h"
  16. #define MARK_STRONG(b) b->b_flags |= BF_STRONG
  17. #define MARK_FIRM(b) b->b_flags |= BF_FIRM
  18. #define BF_MARK 04
  19. #define MARK(b) b->b_flags |= BF_MARK
  20. #define MARKED(b) (b->b_flags&BF_MARK)
  21. #define INSIDE_LOOP(b,lp) Lis_elem(b,lp->LP_BLOCKS)
  22. /* The algorithm to detect loops that is used here is taken
  23. * from: Aho & Ullman, Principles of Compiler Design, section 13.1.
  24. * The algorithm uses the dominator relation between nodes
  25. * of the control flow graph:
  26. * d DOM n => every path from the initial node to n goes through d.
  27. * The dominator relation is recorded via the immediate dominator tree
  28. * (b_idom field of bblock struct) from which the dominator relation
  29. * can be easily computed (see procedure 'dom' below).
  30. * The algorithm first finds 'back edges'. A back edge is an edge
  31. * a->b in the flow graph whose head (b) dominates its tail (a).
  32. * The 'natural loop' of back edge n->d consists of those nodes
  33. * that can reach n without going through d. These nodes, plus d
  34. * form the loop.
  35. * The whole process is rather complex, because different back edges
  36. * may result in the same loop and because loops may partly overlap
  37. * each other (without one being nested inside the other).
  38. */
  39. STATIC bool same_loop(l1,l2)
  40. loop_p l1,l2;
  41. {
  42. /* Two loops are the same if:
  43. * (1) they have the same number of basic blocks, and
  44. * (2) the head of the back edge of the first loop
  45. * also is part of the second loop, and
  46. * (3) the tail of the back edge of the first loop
  47. * also is part of the second loop.
  48. */
  49. return (l1->LP_COUNT == l2->LP_COUNT &&
  50. Lis_elem(l1->lp_entry, l2->LP_BLOCKS) &&
  51. Lis_elem(l1->lp_end, l2->LP_BLOCKS));
  52. }
  53. STATIC bool inner_loop(l1,l2)
  54. loop_p l1,l2;
  55. {
  56. /* Loop l1 is an inner loop of l2 if:
  57. * (1) the first loop has fewer basic blocks than
  58. * the second one, and
  59. * (2) the head of the back edge of the first loop
  60. * also is part of the second loop, and
  61. * (3) the tail of the back edge of the first loop
  62. * also is part of the second loop.
  63. */
  64. return (l1->LP_COUNT < l2->LP_COUNT &&
  65. Lis_elem(l1->lp_entry, l2->LP_BLOCKS) &&
  66. Lis_elem(l1->lp_end, l2->LP_BLOCKS));
  67. }
  68. STATIC insrt(b,lpb,s_p)
  69. bblock_p b;
  70. lset *lpb;
  71. lset *s_p;
  72. {
  73. /* Auxiliary routine used by 'natural_loop'.
  74. * Note that we use a set rather than a stack,
  75. * as Aho & Ullman do.
  76. */
  77. if (!Lis_elem(b,*lpb)) {
  78. Ladd(b,lpb);
  79. Ladd(b,s_p);
  80. }
  81. }
  82. STATIC loop_p natural_loop(d,n)
  83. bblock_p d,n;
  84. {
  85. /* Find the basic blocks of the natural loop of the
  86. * back edge 'n->d' (i.e. n->d is an edge in the control
  87. * flow graph and d dominates n). The natural loop consists
  88. * of those blocks which can reach n without going through d.
  89. * We find these blocks by finding all predecessors of n,
  90. * up to d.
  91. */
  92. loop_p lp;
  93. bblock_p m;
  94. lset loopblocks;
  95. Lindex pi;
  96. lset s;
  97. lp = newloop();
  98. lp->lp_extend = newcflpx();
  99. lp->lp_entry = d; /* loop entry block */
  100. lp->lp_end = n; /* tail of back edge */
  101. s = Lempty_set();
  102. loopblocks = Lempty_set();
  103. Ladd(d,&loopblocks);
  104. insrt(n,&loopblocks,&s);
  105. while ((pi = Lfirst(s)) != (Lindex) 0) {
  106. m = (bblock_p) Lelem(pi);
  107. Lremove(m,&s);
  108. for (pi = Lfirst(m->b_pred); pi != (Lindex) 0;
  109. pi = Lnext(pi,m->b_pred)) {
  110. insrt((bblock_p) Lelem(pi),&loopblocks,&s);
  111. }
  112. }
  113. lp->LP_BLOCKS = loopblocks;
  114. lp->LP_COUNT = Lnrelems(loopblocks);
  115. return lp;
  116. }
  117. STATIC loop_p org_loop(lp,loops)
  118. loop_p lp;
  119. lset loops;
  120. {
  121. /* See if the loop lp was already found via another
  122. * back edge; if so return this loop; else return 0.
  123. */
  124. register Lindex li;
  125. for (li = Lfirst(loops); li != (Lindex) 0; li = Lnext(li,loops)) {
  126. if (same_loop((loop_p) Lelem(li), lp)) {
  127. #ifdef DEBUG
  128. /* printf("messy loop found\n"); */
  129. #endif
  130. return (loop_p) Lelem(li);
  131. }
  132. }
  133. return (loop_p) 0;
  134. }
  135. STATIC collapse_loops(loops_p)
  136. lset *loops_p;
  137. {
  138. register Lindex li1, li2;
  139. register loop_p lp1,lp2;
  140. for (li1 = Lfirst(*loops_p); li1 != (Lindex) 0; li1 = Lnext(li1,*loops_p)) {
  141. lp1 = (loop_p) Lelem(li1);
  142. lp1->lp_level = (short) 0;
  143. for (li2 = Lfirst(*loops_p); li2 != (Lindex) 0;
  144. li2 = Lnext(li2,*loops_p)) {
  145. lp2 = (loop_p) Lelem(li2);
  146. if (lp1 != lp2 && lp1->lp_entry == lp2->lp_entry) {
  147. Ljoin(lp2->LP_BLOCKS,&lp1->LP_BLOCKS);
  148. oldcflpx(lp2->lp_extend);
  149. Lremove(lp2,loops_p);
  150. }
  151. }
  152. }
  153. }
  154. STATIC loop_per_block(lp)
  155. loop_p lp;
  156. {
  157. bblock_p b;
  158. /* Update the b_loops sets */
  159. register Lindex bi;
  160. for (bi = Lfirst(lp->LP_BLOCKS); bi != (Lindex) 0;
  161. bi = Lnext(bi,lp->LP_BLOCKS)) {
  162. b = (bblock_p) Lelem(bi);
  163. Ladd(lp,&(b->b_loops));
  164. }
  165. }
  166. STATIC loop_attrib(loops)
  167. lset loops;
  168. {
  169. /* Compute several attributes */
  170. register Lindex li;
  171. register loop_p lp;
  172. loop_id lastlpid = 0;
  173. for (li = Lfirst(loops); li != (Lindex) 0; li = Lnext(li,loops)) {
  174. lp = (loop_p) Lelem(li);
  175. lp->lp_id = ++lastlpid;
  176. loop_per_block(lp);
  177. }
  178. }
  179. STATIC nest_levels(loops)
  180. lset loops;
  181. {
  182. /* Compute the nesting levels of all loops of
  183. * the current procedure. For every loop we just count
  184. * all loops of which the former is an inner loop.
  185. * The running time is quadratic in the number of loops
  186. * of the current procedure. As this number tends to be
  187. * very small, there is no cause for alarm.
  188. */
  189. register Lindex li1, li2;
  190. register loop_p lp;
  191. for (li1 = Lfirst(loops); li1 != (Lindex) 0; li1 = Lnext(li1,loops)) {
  192. lp = (loop_p) Lelem(li1);
  193. lp->lp_level = (short) 0;
  194. for (li2 = Lfirst(loops); li2 != (Lindex) 0;
  195. li2 = Lnext(li2,loops)) {
  196. if (inner_loop(lp,(loop_p) Lelem(li2))) {
  197. lp->lp_level++;
  198. }
  199. }
  200. }
  201. }
  202. STATIC cleanup(loops)
  203. lset loops;
  204. {
  205. /* Throw away the LP_BLOCKS sets */
  206. register Lindex i;
  207. for (i = Lfirst(loops); i != (Lindex) 0; i = Lnext(i,loops)) {
  208. Ldeleteset(((loop_p) Lelem(i))->LP_BLOCKS);
  209. }
  210. }
  211. STATIC bool does_exit(b,lp)
  212. bblock_p b;
  213. loop_p lp;
  214. {
  215. /* See if b may exit the loop, i.e. if it
  216. * has a successor outside the loop
  217. */
  218. Lindex i;
  219. for (i = Lfirst(b->b_succ); i != (Lindex) 0; i = Lnext(i,b->b_succ)) {
  220. if (!INSIDE_LOOP(Lelem(i),lp)) return TRUE;
  221. }
  222. return FALSE;
  223. }
  224. STATIC mark_succ(b,lp)
  225. bblock_p b;
  226. loop_p lp;
  227. {
  228. Lindex i;
  229. bblock_p succ;
  230. for (i = Lfirst(b->b_succ); i != (Lindex) 0; i = Lnext(i,b->b_succ)) {
  231. succ = (bblock_p) Lelem(i);
  232. if (succ != b && succ != lp->lp_entry && INSIDE_LOOP(succ,lp) &&
  233. !MARKED(succ)) {
  234. MARK(succ);
  235. mark_succ(succ,lp);
  236. }
  237. }
  238. }
  239. STATIC mark_blocks(lp)
  240. loop_p lp;
  241. {
  242. /* Mark the strong and firm blocks of a loop.
  243. * The last set of blocks consists of the end-block
  244. * of the loop (i.e. the head of the back edge
  245. * of the natural loop) and its dominators
  246. * (including the loop entry block, i.e. the
  247. * tail of the back edge).
  248. */
  249. register bblock_p b;
  250. /* First mark all blocks that are the successor of a
  251. * block that may exit the loop (i.e. contains a
  252. * -possibly conditional- jump to somewhere outside
  253. * the loop.
  254. */
  255. if (lp->LP_MESSY) return; /* messy loops are hopeless cases */
  256. for (b = lp->lp_entry; b != (bblock_p) 0; b = b->b_next) {
  257. if (!MARKED(b) && does_exit(b,lp)) {
  258. mark_succ(b,lp);
  259. }
  260. }
  261. /* Now find all firm blocks. A block is strong
  262. * if it is firm and not marked.
  263. */
  264. for (b = lp->lp_end; ; b = b->b_idom) {
  265. MARK_FIRM(b);
  266. if (!MARKED(b)) {
  267. MARK_STRONG(b);
  268. }
  269. if (b == lp->lp_entry) break;
  270. }
  271. }
  272. STATIC mark_loopblocks(loops)
  273. lset loops;
  274. {
  275. /* Determine for all loops which basic blocks
  276. * of the loop are strong (i.e. are executed
  277. * during every iteration) and which blocks are
  278. * firm (i.e. executed during every iteration with
  279. * the only possible exception of the last one).
  280. */
  281. Lindex i;
  282. loop_p lp;
  283. for (i = Lfirst(loops); i != (Lindex) 0; i = Lnext(i,loops)) {
  284. lp = (loop_p) Lelem(i);
  285. mark_blocks(lp);
  286. }
  287. }
  288. loop_detection(p)
  289. proc_p p;
  290. {
  291. /* Find all natural loops of procedure p. Every loop is
  292. * assigned a unique identifying number, a set of basic
  293. * blocks, a loop entry block and a nesting level number.
  294. * Every basic block is assigned a nesting level number
  295. * and a set of loops it is part of.
  296. */
  297. lset loops; /* the set of all loops */
  298. loop_p lp,org;
  299. register bblock_p b;
  300. bblock_p s;
  301. Lindex si;
  302. loops = Lempty_set();
  303. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  304. for (si = Lfirst(b->b_succ); si != (Lindex) 0;
  305. si = Lnext(si,b->b_succ)) {
  306. s = (bblock_p) Lelem(si);
  307. if (dom(s,b)) {
  308. /* 'b->s' is a back edge */
  309. lp = natural_loop(s,b);
  310. if ((org = org_loop(lp,loops)) == (loop_p) 0) {
  311. /* new loop */
  312. Ladd(lp,&loops);
  313. } else {
  314. /* Same loop, generated by several back
  315. * edges; such a loop is called a messy
  316. * loop.
  317. */
  318. org->LP_MESSY = TRUE;
  319. Ldeleteset(lp->LP_BLOCKS);
  320. oldcflpx(lp->lp_extend);
  321. oldloop(lp);
  322. }
  323. }
  324. }
  325. }
  326. collapse_loops(&loops);
  327. loop_attrib(loops);
  328. nest_levels(loops);
  329. mark_loopblocks(loops); /* determine firm and strong blocks */
  330. cleanup(loops);
  331. p->p_loops = loops;
  332. }