cf_loop.c 9.1 KB

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