cf_loop.c 9.0 KB

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