cf_loop.c 9.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409
  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. /* Lnext(li2,*loops_p) must happen before
  145. * Lremove(lp2,loops_p) releases the memory for li2.
  146. */
  147. for (li2 = Lfirst(*loops_p); li2 != (Lindex) 0;) {
  148. lp2 = (loop_p) Lelem(li2);
  149. li2 = Lnext(li2,*loops_p);
  150. if (lp1 != lp2 && lp1->lp_entry == lp2->lp_entry) {
  151. Ljoin(lp2->LP_BLOCKS,&lp1->LP_BLOCKS);
  152. oldcflpx(lp2->lp_extend);
  153. Lremove(lp2,loops_p);
  154. }
  155. }
  156. }
  157. }
  158. STATIC loop_per_block(lp)
  159. loop_p lp;
  160. {
  161. bblock_p b;
  162. /* Update the b_loops sets */
  163. register Lindex bi;
  164. for (bi = Lfirst(lp->LP_BLOCKS); bi != (Lindex) 0;
  165. bi = Lnext(bi,lp->LP_BLOCKS)) {
  166. b = (bblock_p) Lelem(bi);
  167. Ladd(lp,&(b->b_loops));
  168. }
  169. }
  170. STATIC loop_attrib(loops)
  171. lset loops;
  172. {
  173. /* Compute several attributes */
  174. register Lindex li;
  175. register loop_p lp;
  176. loop_id lastlpid = 0;
  177. for (li = Lfirst(loops); li != (Lindex) 0; li = Lnext(li,loops)) {
  178. lp = (loop_p) Lelem(li);
  179. lp->lp_id = ++lastlpid;
  180. loop_per_block(lp);
  181. }
  182. }
  183. STATIC nest_levels(loops)
  184. lset loops;
  185. {
  186. /* Compute the nesting levels of all loops of
  187. * the current procedure. For every loop we just count
  188. * all loops of which the former is an inner loop.
  189. * The running time is quadratic in the number of loops
  190. * of the current procedure. As this number tends to be
  191. * very small, there is no cause for alarm.
  192. */
  193. register Lindex li1, li2;
  194. register loop_p lp;
  195. for (li1 = Lfirst(loops); li1 != (Lindex) 0; li1 = Lnext(li1,loops)) {
  196. lp = (loop_p) Lelem(li1);
  197. lp->lp_level = (short) 0;
  198. for (li2 = Lfirst(loops); li2 != (Lindex) 0;
  199. li2 = Lnext(li2,loops)) {
  200. if (inner_loop(lp,(loop_p) Lelem(li2))) {
  201. lp->lp_level++;
  202. }
  203. }
  204. }
  205. }
  206. STATIC cleanup(loops)
  207. lset loops;
  208. {
  209. /* Throw away the LP_BLOCKS sets */
  210. register Lindex i;
  211. for (i = Lfirst(loops); i != (Lindex) 0; i = Lnext(i,loops)) {
  212. Ldeleteset(((loop_p) Lelem(i))->LP_BLOCKS);
  213. }
  214. }
  215. STATIC bool does_exit(b,lp)
  216. bblock_p b;
  217. loop_p lp;
  218. {
  219. /* See if b may exit the loop, i.e. if it
  220. * has a successor outside the loop
  221. */
  222. Lindex i;
  223. for (i = Lfirst(b->b_succ); i != (Lindex) 0; i = Lnext(i,b->b_succ)) {
  224. if (!INSIDE_LOOP(Lelem(i),lp)) return TRUE;
  225. }
  226. return FALSE;
  227. }
  228. STATIC mark_succ(b,lp)
  229. bblock_p b;
  230. loop_p lp;
  231. {
  232. Lindex i;
  233. bblock_p succ;
  234. for (i = Lfirst(b->b_succ); i != (Lindex) 0; i = Lnext(i,b->b_succ)) {
  235. succ = (bblock_p) Lelem(i);
  236. if (succ != b && succ != lp->lp_entry && INSIDE_LOOP(succ,lp) &&
  237. !MARKED(succ)) {
  238. MARK(succ);
  239. mark_succ(succ,lp);
  240. }
  241. }
  242. }
  243. STATIC mark_blocks(lp)
  244. loop_p lp;
  245. {
  246. /* Mark the strong and firm blocks of a loop.
  247. * The last set of blocks consists of the end-block
  248. * of the loop (i.e. the head of the back edge
  249. * of the natural loop) and its dominators
  250. * (including the loop entry block, i.e. the
  251. * tail of the back edge).
  252. */
  253. register bblock_p b;
  254. /* First mark all blocks that are the successor of a
  255. * block that may exit the loop (i.e. contains a
  256. * -possibly conditional- jump to somewhere outside
  257. * the loop.
  258. */
  259. if (lp->LP_MESSY) return; /* messy loops are hopeless cases */
  260. for (b = lp->lp_entry; b != (bblock_p) 0; b = b->b_next) {
  261. if (!MARKED(b) && does_exit(b,lp)) {
  262. mark_succ(b,lp);
  263. }
  264. }
  265. /* Now find all firm blocks. A block is strong
  266. * if it is firm and not marked.
  267. */
  268. for (b = lp->lp_end; ; b = b->b_idom) {
  269. MARK_FIRM(b);
  270. if (!MARKED(b)) {
  271. MARK_STRONG(b);
  272. }
  273. if (b == lp->lp_entry) break;
  274. }
  275. }
  276. STATIC mark_loopblocks(loops)
  277. lset loops;
  278. {
  279. /* Determine for all loops which basic blocks
  280. * of the loop are strong (i.e. are executed
  281. * during every iteration) and which blocks are
  282. * firm (i.e. executed during every iteration with
  283. * the only possible exception of the last one).
  284. */
  285. Lindex i;
  286. loop_p lp;
  287. for (i = Lfirst(loops); i != (Lindex) 0; i = Lnext(i,loops)) {
  288. lp = (loop_p) Lelem(i);
  289. mark_blocks(lp);
  290. }
  291. }
  292. loop_detection(p)
  293. proc_p p;
  294. {
  295. /* Find all natural loops of procedure p. Every loop is
  296. * assigned a unique identifying number, a set of basic
  297. * blocks, a loop entry block and a nesting level number.
  298. * Every basic block is assigned a nesting level number
  299. * and a set of loops it is part of.
  300. */
  301. lset loops; /* the set of all loops */
  302. loop_p lp,org;
  303. register bblock_p b;
  304. bblock_p s;
  305. Lindex si;
  306. loops = Lempty_set();
  307. for (b = p->p_start; b != (bblock_p) 0; b = b->b_next) {
  308. for (si = Lfirst(b->b_succ); si != (Lindex) 0;
  309. si = Lnext(si,b->b_succ)) {
  310. s = (bblock_p) Lelem(si);
  311. if (dom(s,b)) {
  312. /* 'b->s' is a back edge */
  313. lp = natural_loop(s,b);
  314. if ((org = org_loop(lp,loops)) == (loop_p) 0) {
  315. /* new loop */
  316. Ladd(lp,&loops);
  317. } else {
  318. /* Same loop, generated by several back
  319. * edges; such a loop is called a messy
  320. * loop.
  321. */
  322. org->LP_MESSY = TRUE;
  323. Ldeleteset(lp->LP_BLOCKS);
  324. oldcflpx(lp->lp_extend);
  325. oldloop(lp);
  326. }
  327. }
  328. }
  329. }
  330. collapse_loops(&loops);
  331. loop_attrib(loops);
  332. nest_levels(loops);
  333. mark_loopblocks(loops); /* determine firm and strong blocks */
  334. cleanup(loops);
  335. p->p_loops = loops;
  336. }