cf_loop.c 9.2 KB

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