]>
Commit | Line | Data |
---|---|---|
402209ff JH |
1 | /* Natural loop discovery code for GNU compiler. |
2 | Copyright (C) 2000, 2001 Free Software Foundation, Inc. | |
3 | ||
4 | This file is part of GCC. | |
5 | ||
6 | GCC is free software; you can redistribute it and/or modify it under | |
7 | the terms of the GNU General Public License as published by the Free | |
8 | Software Foundation; either version 2, or (at your option) any later | |
9 | version. | |
10 | ||
11 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
12 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 | for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
17 | along with GCC; see the file COPYING. If not, write to the Free | |
18 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
19 | 02111-1307, USA. */ | |
20 | ||
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "rtl.h" | |
24 | #include "hard-reg-set.h" | |
25 | #include "basic-block.h" | |
26 | ||
27 | static void flow_loops_cfg_dump PARAMS ((const struct loops *, | |
28 | FILE *)); | |
29 | static int flow_loop_nested_p PARAMS ((struct loop *, | |
30 | struct loop *)); | |
31 | static int flow_loop_entry_edges_find PARAMS ((basic_block, const sbitmap, | |
32 | edge **)); | |
33 | static int flow_loop_exit_edges_find PARAMS ((const sbitmap, edge **)); | |
5f0d2358 RK |
34 | static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, |
35 | sbitmap)); | |
36 | static void flow_loop_pre_header_scan PARAMS ((struct loop *)); | |
402209ff JH |
37 | static basic_block flow_loop_pre_header_find PARAMS ((basic_block, |
38 | const sbitmap *)); | |
5f0d2358 RK |
39 | static void flow_loop_tree_node_add PARAMS ((struct loop *, |
40 | struct loop *)); | |
402209ff JH |
41 | static void flow_loops_tree_build PARAMS ((struct loops *)); |
42 | static int flow_loop_level_compute PARAMS ((struct loop *, int)); | |
43 | static int flow_loops_level_compute PARAMS ((struct loops *)); | |
44 | \f | |
45 | /* Dump loop related CFG information. */ | |
46 | ||
47 | static void | |
48 | flow_loops_cfg_dump (loops, file) | |
49 | const struct loops *loops; | |
50 | FILE *file; | |
51 | { | |
52 | int i; | |
53 | ||
54 | if (! loops->num || ! file || ! loops->cfg.dom) | |
55 | return; | |
56 | ||
0b17ab2f | 57 | for (i = 0; i < n_basic_blocks; i++) |
402209ff JH |
58 | { |
59 | edge succ; | |
60 | ||
0b17ab2f RH |
61 | fprintf (file, ";; %d succs { ", i); |
62 | for (succ = BASIC_BLOCK (i)->succ; succ; succ = succ->succ_next) | |
63 | fprintf (file, "%d ", succ->dest->index); | |
402209ff JH |
64 | flow_nodes_print ("} dom", loops->cfg.dom[i], file); |
65 | } | |
66 | ||
67 | /* Dump the DFS node order. */ | |
68 | if (loops->cfg.dfs_order) | |
69 | { | |
70 | fputs (";; DFS order: ", file); | |
0b17ab2f | 71 | for (i = 0; i < n_basic_blocks; i++) |
402209ff | 72 | fprintf (file, "%d ", loops->cfg.dfs_order[i]); |
5f0d2358 | 73 | |
402209ff JH |
74 | fputs ("\n", file); |
75 | } | |
5f0d2358 | 76 | |
402209ff JH |
77 | /* Dump the reverse completion node order. */ |
78 | if (loops->cfg.rc_order) | |
79 | { | |
80 | fputs (";; RC order: ", file); | |
0b17ab2f | 81 | for (i = 0; i < n_basic_blocks; i++) |
402209ff | 82 | fprintf (file, "%d ", loops->cfg.rc_order[i]); |
5f0d2358 | 83 | |
402209ff JH |
84 | fputs ("\n", file); |
85 | } | |
86 | } | |
87 | ||
88 | /* Return non-zero if the nodes of LOOP are a subset of OUTER. */ | |
89 | ||
90 | static int | |
91 | flow_loop_nested_p (outer, loop) | |
92 | struct loop *outer; | |
93 | struct loop *loop; | |
94 | { | |
95 | return sbitmap_a_subset_b_p (loop->nodes, outer->nodes); | |
96 | } | |
97 | ||
98 | /* Dump the loop information specified by LOOP to the stream FILE | |
99 | using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ | |
100 | ||
101 | void | |
102 | flow_loop_dump (loop, file, loop_dump_aux, verbose) | |
103 | const struct loop *loop; | |
104 | FILE *file; | |
105 | void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int)); | |
106 | int verbose; | |
107 | { | |
108 | if (! loop || ! loop->header) | |
109 | return; | |
110 | ||
111 | if (loop->first->head && loop->last->end) | |
112 | fprintf (file, ";;\n;; Loop %d (%d to %d):%s%s\n", | |
f87c27b4 KH |
113 | loop->num, INSN_UID (loop->first->head), |
114 | INSN_UID (loop->last->end), | |
115 | loop->shared ? " shared" : "", loop->invalid ? " invalid" : ""); | |
402209ff JH |
116 | else |
117 | fprintf (file, ";;\n;; Loop %d:%s%s\n", loop->num, | |
5f0d2358 | 118 | loop->shared ? " shared" : "", loop->invalid ? " invalid" : ""); |
402209ff JH |
119 | |
120 | fprintf (file, ";; header %d, latch %d, pre-header %d, first %d, last %d\n", | |
0b17ab2f RH |
121 | loop->header->index, loop->latch->index, |
122 | loop->pre_header ? loop->pre_header->index : -1, | |
123 | loop->first->index, loop->last->index); | |
402209ff JH |
124 | fprintf (file, ";; depth %d, level %d, outer %ld\n", |
125 | loop->depth, loop->level, | |
126 | (long) (loop->outer ? loop->outer->num : -1)); | |
127 | ||
128 | if (loop->pre_header_edges) | |
129 | flow_edge_list_print (";; pre-header edges", loop->pre_header_edges, | |
130 | loop->num_pre_header_edges, file); | |
5f0d2358 | 131 | |
402209ff JH |
132 | flow_edge_list_print (";; entry edges", loop->entry_edges, |
133 | loop->num_entries, file); | |
134 | fprintf (file, ";; %d", loop->num_nodes); | |
135 | flow_nodes_print (" nodes", loop->nodes, file); | |
136 | flow_edge_list_print (";; exit edges", loop->exit_edges, | |
137 | loop->num_exits, file); | |
5f0d2358 | 138 | |
402209ff JH |
139 | if (loop->exits_doms) |
140 | flow_nodes_print (";; exit doms", loop->exits_doms, file); | |
5f0d2358 | 141 | |
402209ff JH |
142 | if (loop_dump_aux) |
143 | loop_dump_aux (loop, file, verbose); | |
144 | } | |
145 | ||
146 | /* Dump the loop information specified by LOOPS to the stream FILE, | |
147 | using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ | |
148 | ||
149 | void | |
150 | flow_loops_dump (loops, file, loop_dump_aux, verbose) | |
151 | const struct loops *loops; | |
152 | FILE *file; | |
153 | void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int)); | |
154 | int verbose; | |
155 | { | |
5f0d2358 | 156 | int i, j; |
402209ff JH |
157 | int num_loops; |
158 | ||
159 | num_loops = loops->num; | |
160 | if (! num_loops || ! file) | |
161 | return; | |
162 | ||
5f0d2358 | 163 | fprintf (file, ";; %d loops found, %d levels\n", num_loops, loops->levels); |
402209ff JH |
164 | for (i = 0; i < num_loops; i++) |
165 | { | |
166 | struct loop *loop = &loops->array[i]; | |
167 | ||
168 | flow_loop_dump (loop, file, loop_dump_aux, verbose); | |
402209ff | 169 | if (loop->shared) |
5f0d2358 RK |
170 | for (j = 0; j < i; j++) |
171 | { | |
172 | struct loop *oloop = &loops->array[j]; | |
173 | ||
174 | if (loop->header == oloop->header) | |
175 | { | |
176 | int disjoint; | |
177 | int smaller; | |
178 | ||
179 | smaller = loop->num_nodes < oloop->num_nodes; | |
180 | ||
181 | /* If the union of LOOP and OLOOP is different than | |
182 | the larger of LOOP and OLOOP then LOOP and OLOOP | |
183 | must be disjoint. */ | |
184 | disjoint = ! flow_loop_nested_p (smaller ? loop : oloop, | |
185 | smaller ? oloop : loop); | |
186 | fprintf (file, | |
187 | ";; loop header %d shared by loops %d, %d %s\n", | |
0b17ab2f | 188 | loop->header->index, i, j, |
5f0d2358 RK |
189 | disjoint ? "disjoint" : "nested"); |
190 | } | |
191 | } | |
402209ff JH |
192 | } |
193 | ||
194 | if (verbose) | |
195 | flow_loops_cfg_dump (loops, file); | |
196 | } | |
197 | ||
198 | /* Free all the memory allocated for LOOPS. */ | |
199 | ||
200 | void | |
201 | flow_loops_free (loops) | |
202 | struct loops *loops; | |
203 | { | |
204 | if (loops->array) | |
205 | { | |
206 | int i; | |
207 | ||
208 | if (! loops->num) | |
209 | abort (); | |
210 | ||
211 | /* Free the loop descriptors. */ | |
212 | for (i = 0; i < loops->num; i++) | |
213 | { | |
214 | struct loop *loop = &loops->array[i]; | |
215 | ||
216 | if (loop->pre_header_edges) | |
217 | free (loop->pre_header_edges); | |
218 | if (loop->nodes) | |
219 | sbitmap_free (loop->nodes); | |
220 | if (loop->entry_edges) | |
221 | free (loop->entry_edges); | |
222 | if (loop->exit_edges) | |
223 | free (loop->exit_edges); | |
224 | if (loop->exits_doms) | |
225 | sbitmap_free (loop->exits_doms); | |
226 | } | |
5f0d2358 | 227 | |
402209ff JH |
228 | free (loops->array); |
229 | loops->array = NULL; | |
230 | ||
231 | if (loops->cfg.dom) | |
232 | sbitmap_vector_free (loops->cfg.dom); | |
5f0d2358 | 233 | |
402209ff JH |
234 | if (loops->cfg.dfs_order) |
235 | free (loops->cfg.dfs_order); | |
236 | ||
237 | if (loops->shared_headers) | |
238 | sbitmap_free (loops->shared_headers); | |
239 | } | |
240 | } | |
241 | ||
242 | /* Find the entry edges into the loop with header HEADER and nodes | |
243 | NODES and store in ENTRY_EDGES array. Return the number of entry | |
244 | edges from the loop. */ | |
245 | ||
246 | static int | |
247 | flow_loop_entry_edges_find (header, nodes, entry_edges) | |
248 | basic_block header; | |
249 | const sbitmap nodes; | |
250 | edge **entry_edges; | |
251 | { | |
252 | edge e; | |
253 | int num_entries; | |
254 | ||
255 | *entry_edges = NULL; | |
256 | ||
257 | num_entries = 0; | |
258 | for (e = header->pred; e; e = e->pred_next) | |
259 | { | |
260 | basic_block src = e->src; | |
261 | ||
0b17ab2f | 262 | if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index)) |
402209ff JH |
263 | num_entries++; |
264 | } | |
265 | ||
266 | if (! num_entries) | |
267 | abort (); | |
268 | ||
e4ed918f | 269 | *entry_edges = (edge *) xmalloc (num_entries * sizeof (edge)); |
402209ff JH |
270 | |
271 | num_entries = 0; | |
272 | for (e = header->pred; e; e = e->pred_next) | |
273 | { | |
274 | basic_block src = e->src; | |
275 | ||
0b17ab2f | 276 | if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index)) |
402209ff JH |
277 | (*entry_edges)[num_entries++] = e; |
278 | } | |
279 | ||
280 | return num_entries; | |
281 | } | |
282 | ||
283 | /* Find the exit edges from the loop using the bitmap of loop nodes | |
284 | NODES and store in EXIT_EDGES array. Return the number of | |
285 | exit edges from the loop. */ | |
286 | ||
287 | static int | |
288 | flow_loop_exit_edges_find (nodes, exit_edges) | |
289 | const sbitmap nodes; | |
290 | edge **exit_edges; | |
291 | { | |
292 | edge e; | |
293 | int node; | |
294 | int num_exits; | |
295 | ||
296 | *exit_edges = NULL; | |
297 | ||
298 | /* Check all nodes within the loop to see if there are any | |
299 | successors not in the loop. Note that a node may have multiple | |
300 | exiting edges ????? A node can have one jumping edge and one fallthru | |
301 | edge so only one of these can exit the loop. */ | |
302 | num_exits = 0; | |
303 | EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, { | |
304 | for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next) | |
305 | { | |
306 | basic_block dest = e->dest; | |
307 | ||
0b17ab2f | 308 | if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index)) |
402209ff JH |
309 | num_exits++; |
310 | } | |
311 | }); | |
312 | ||
313 | if (! num_exits) | |
314 | return 0; | |
315 | ||
e4ed918f | 316 | *exit_edges = (edge *) xmalloc (num_exits * sizeof (edge)); |
402209ff JH |
317 | |
318 | /* Store all exiting edges into an array. */ | |
319 | num_exits = 0; | |
320 | EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, { | |
321 | for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next) | |
322 | { | |
323 | basic_block dest = e->dest; | |
324 | ||
0b17ab2f | 325 | if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index)) |
402209ff JH |
326 | (*exit_edges)[num_exits++] = e; |
327 | } | |
328 | }); | |
329 | ||
330 | return num_exits; | |
331 | } | |
332 | ||
333 | /* Find the nodes contained within the loop with header HEADER and | |
334 | latch LATCH and store in NODES. Return the number of nodes within | |
335 | the loop. */ | |
336 | ||
337 | static int | |
338 | flow_loop_nodes_find (header, latch, nodes) | |
339 | basic_block header; | |
340 | basic_block latch; | |
341 | sbitmap nodes; | |
342 | { | |
343 | basic_block *stack; | |
344 | int sp; | |
345 | int num_nodes = 0; | |
346 | ||
0b17ab2f | 347 | stack = (basic_block *) xmalloc (n_basic_blocks * sizeof (basic_block)); |
402209ff JH |
348 | sp = 0; |
349 | ||
350 | /* Start with only the loop header in the set of loop nodes. */ | |
351 | sbitmap_zero (nodes); | |
0b17ab2f | 352 | SET_BIT (nodes, header->index); |
402209ff JH |
353 | num_nodes++; |
354 | header->loop_depth++; | |
355 | ||
356 | /* Push the loop latch on to the stack. */ | |
0b17ab2f | 357 | if (! TEST_BIT (nodes, latch->index)) |
402209ff | 358 | { |
0b17ab2f | 359 | SET_BIT (nodes, latch->index); |
402209ff JH |
360 | latch->loop_depth++; |
361 | num_nodes++; | |
362 | stack[sp++] = latch; | |
363 | } | |
364 | ||
365 | while (sp) | |
366 | { | |
367 | basic_block node; | |
368 | edge e; | |
369 | ||
370 | node = stack[--sp]; | |
371 | for (e = node->pred; e; e = e->pred_next) | |
372 | { | |
373 | basic_block ancestor = e->src; | |
374 | ||
375 | /* If each ancestor not marked as part of loop, add to set of | |
376 | loop nodes and push on to stack. */ | |
377 | if (ancestor != ENTRY_BLOCK_PTR | |
0b17ab2f | 378 | && ! TEST_BIT (nodes, ancestor->index)) |
402209ff | 379 | { |
0b17ab2f | 380 | SET_BIT (nodes, ancestor->index); |
402209ff JH |
381 | ancestor->loop_depth++; |
382 | num_nodes++; | |
383 | stack[sp++] = ancestor; | |
384 | } | |
385 | } | |
386 | } | |
387 | free (stack); | |
388 | return num_nodes; | |
389 | } | |
390 | ||
391 | /* Find the root node of the loop pre-header extended basic block and | |
392 | the edges along the trace from the root node to the loop header. */ | |
393 | ||
394 | static void | |
395 | flow_loop_pre_header_scan (loop) | |
396 | struct loop *loop; | |
397 | { | |
5f0d2358 | 398 | int num; |
402209ff | 399 | basic_block ebb; |
5f0d2358 | 400 | edge e; |
402209ff JH |
401 | |
402 | loop->num_pre_header_edges = 0; | |
402209ff | 403 | if (loop->num_entries != 1) |
5f0d2358 | 404 | return; |
402209ff JH |
405 | |
406 | ebb = loop->entry_edges[0]->src; | |
5f0d2358 RK |
407 | if (ebb == ENTRY_BLOCK_PTR) |
408 | return; | |
402209ff | 409 | |
5f0d2358 RK |
410 | /* Count number of edges along trace from loop header to |
411 | root of pre-header extended basic block. Usually this is | |
412 | only one or two edges. */ | |
413 | for (num = 1; ebb->pred->src != ENTRY_BLOCK_PTR && ! ebb->pred->pred_next; | |
414 | num++) | |
415 | ebb = ebb->pred->src; | |
416 | ||
6b6996b8 | 417 | loop->pre_header_edges = (edge *) xmalloc (num * sizeof (edge)); |
5f0d2358 RK |
418 | loop->num_pre_header_edges = num; |
419 | ||
420 | /* Store edges in order that they are followed. The source of the first edge | |
421 | is the root node of the pre-header extended basic block and the | |
422 | destination of the last last edge is the loop header. */ | |
423 | for (e = loop->entry_edges[0]; num; e = e->src->pred) | |
424 | loop->pre_header_edges[--num] = e; | |
402209ff JH |
425 | } |
426 | ||
427 | /* Return the block for the pre-header of the loop with header | |
428 | HEADER where DOM specifies the dominator information. Return NULL if | |
429 | there is no pre-header. */ | |
430 | ||
431 | static basic_block | |
432 | flow_loop_pre_header_find (header, dom) | |
433 | basic_block header; | |
434 | const sbitmap *dom; | |
435 | { | |
436 | basic_block pre_header; | |
437 | edge e; | |
438 | ||
439 | /* If block p is a predecessor of the header and is the only block | |
440 | that the header does not dominate, then it is the pre-header. */ | |
441 | pre_header = NULL; | |
442 | for (e = header->pred; e; e = e->pred_next) | |
443 | { | |
444 | basic_block node = e->src; | |
445 | ||
446 | if (node != ENTRY_BLOCK_PTR | |
0b17ab2f | 447 | && ! TEST_BIT (dom[node->index], header->index)) |
402209ff JH |
448 | { |
449 | if (pre_header == NULL) | |
450 | pre_header = node; | |
451 | else | |
452 | { | |
453 | /* There are multiple edges into the header from outside | |
454 | the loop so there is no pre-header block. */ | |
455 | pre_header = NULL; | |
456 | break; | |
457 | } | |
458 | } | |
459 | } | |
5f0d2358 | 460 | |
402209ff JH |
461 | return pre_header; |
462 | } | |
463 | ||
464 | /* Add LOOP to the loop hierarchy tree where PREVLOOP was the loop | |
465 | previously added. The insertion algorithm assumes that the loops | |
466 | are added in the order found by a depth first search of the CFG. */ | |
467 | ||
468 | static void | |
469 | flow_loop_tree_node_add (prevloop, loop) | |
470 | struct loop *prevloop; | |
471 | struct loop *loop; | |
472 | { | |
473 | ||
474 | if (flow_loop_nested_p (prevloop, loop)) | |
475 | { | |
476 | prevloop->inner = loop; | |
477 | loop->outer = prevloop; | |
478 | return; | |
479 | } | |
480 | ||
5f0d2358 RK |
481 | for (; prevloop->outer; prevloop = prevloop->outer) |
482 | if (flow_loop_nested_p (prevloop->outer, loop)) | |
483 | { | |
484 | prevloop->next = loop; | |
485 | loop->outer = prevloop->outer; | |
486 | return; | |
487 | } | |
402209ff JH |
488 | |
489 | prevloop->next = loop; | |
490 | loop->outer = NULL; | |
491 | } | |
492 | ||
493 | /* Build the loop hierarchy tree for LOOPS. */ | |
494 | ||
495 | static void | |
496 | flow_loops_tree_build (loops) | |
497 | struct loops *loops; | |
498 | { | |
499 | int i; | |
500 | int num_loops; | |
501 | ||
502 | num_loops = loops->num; | |
503 | if (! num_loops) | |
504 | return; | |
505 | ||
506 | /* Root the loop hierarchy tree with the first loop found. | |
507 | Since we used a depth first search this should be the | |
508 | outermost loop. */ | |
509 | loops->tree_root = &loops->array[0]; | |
5f0d2358 RK |
510 | loops->tree_root->outer = loops->tree_root->inner |
511 | = loops->tree_root->next = NULL; | |
402209ff JH |
512 | |
513 | /* Add the remaining loops to the tree. */ | |
514 | for (i = 1; i < num_loops; i++) | |
515 | flow_loop_tree_node_add (&loops->array[i - 1], &loops->array[i]); | |
516 | } | |
517 | ||
518 | /* Helper function to compute loop nesting depth and enclosed loop level | |
519 | for the natural loop specified by LOOP at the loop depth DEPTH. | |
520 | Returns the loop level. */ | |
521 | ||
522 | static int | |
523 | flow_loop_level_compute (loop, depth) | |
524 | struct loop *loop; | |
525 | int depth; | |
526 | { | |
527 | struct loop *inner; | |
528 | int level = 1; | |
529 | ||
530 | if (! loop) | |
531 | return 0; | |
532 | ||
533 | /* Traverse loop tree assigning depth and computing level as the | |
534 | maximum level of all the inner loops of this loop. The loop | |
535 | level is equivalent to the height of the loop in the loop tree | |
536 | and corresponds to the number of enclosed loop levels (including | |
537 | itself). */ | |
538 | for (inner = loop->inner; inner; inner = inner->next) | |
539 | { | |
5f0d2358 | 540 | int ilevel = flow_loop_level_compute (inner, depth + 1) + 1; |
402209ff | 541 | |
5f0d2358 | 542 | level = MAX (ilevel, level); |
402209ff | 543 | } |
5f0d2358 | 544 | |
402209ff JH |
545 | loop->level = level; |
546 | loop->depth = depth; | |
547 | return level; | |
548 | } | |
549 | ||
550 | /* Compute the loop nesting depth and enclosed loop level for the loop | |
eaec9b3d | 551 | hierarchy tree specified by LOOPS. Return the maximum enclosed loop |
402209ff JH |
552 | level. */ |
553 | ||
554 | static int | |
555 | flow_loops_level_compute (loops) | |
556 | struct loops *loops; | |
557 | { | |
5f0d2358 | 558 | int levels = 0; |
402209ff JH |
559 | struct loop *loop; |
560 | int level; | |
402209ff JH |
561 | |
562 | /* Traverse all the outer level loops. */ | |
563 | for (loop = loops->tree_root; loop; loop = loop->next) | |
564 | { | |
565 | level = flow_loop_level_compute (loop, 1); | |
5f0d2358 | 566 | levels = MAX (levels, level); |
402209ff | 567 | } |
5f0d2358 | 568 | |
402209ff JH |
569 | return levels; |
570 | } | |
571 | ||
572 | /* Scan a single natural loop specified by LOOP collecting information | |
573 | about it specified by FLAGS. */ | |
574 | ||
575 | int | |
576 | flow_loop_scan (loops, loop, flags) | |
577 | struct loops *loops; | |
578 | struct loop *loop; | |
579 | int flags; | |
580 | { | |
581 | /* Determine prerequisites. */ | |
582 | if ((flags & LOOP_EXITS_DOMS) && ! loop->exit_edges) | |
583 | flags |= LOOP_EXIT_EDGES; | |
584 | ||
585 | if (flags & LOOP_ENTRY_EDGES) | |
5f0d2358 RK |
586 | /* Find edges which enter the loop header. Note that the entry edges |
587 | should only enter the header of a natural loop. */ | |
588 | loop->num_entries = flow_loop_entry_edges_find (loop->header, loop->nodes, | |
589 | &loop->entry_edges); | |
402209ff JH |
590 | |
591 | if (flags & LOOP_EXIT_EDGES) | |
5f0d2358 RK |
592 | /* Find edges which exit the loop. */ |
593 | loop->num_exits | |
594 | = flow_loop_exit_edges_find (loop->nodes, &loop->exit_edges); | |
402209ff JH |
595 | |
596 | if (flags & LOOP_EXITS_DOMS) | |
597 | { | |
598 | int j; | |
599 | ||
600 | /* Determine which loop nodes dominate all the exits | |
601 | of the loop. */ | |
0b17ab2f | 602 | loop->exits_doms = sbitmap_alloc (n_basic_blocks); |
402209ff JH |
603 | sbitmap_copy (loop->exits_doms, loop->nodes); |
604 | for (j = 0; j < loop->num_exits; j++) | |
605 | sbitmap_a_and_b (loop->exits_doms, loop->exits_doms, | |
0b17ab2f | 606 | loops->cfg.dom[loop->exit_edges[j]->src->index]); |
402209ff JH |
607 | |
608 | /* The header of a natural loop must dominate | |
609 | all exits. */ | |
0b17ab2f | 610 | if (! TEST_BIT (loop->exits_doms, loop->header->index)) |
402209ff JH |
611 | abort (); |
612 | } | |
613 | ||
614 | if (flags & LOOP_PRE_HEADER) | |
615 | { | |
616 | /* Look to see if the loop has a pre-header node. */ | |
617 | loop->pre_header | |
618 | = flow_loop_pre_header_find (loop->header, loops->cfg.dom); | |
619 | ||
620 | /* Find the blocks within the extended basic block of | |
621 | the loop pre-header. */ | |
622 | flow_loop_pre_header_scan (loop); | |
623 | } | |
5f0d2358 | 624 | |
402209ff JH |
625 | return 1; |
626 | } | |
627 | ||
5f0d2358 RK |
628 | /* Find all the natural loops in the function and save in LOOPS structure and |
629 | recalculate loop_depth information in basic block structures. FLAGS | |
630 | controls which loop information is collected. Return the number of natural | |
631 | loops found. */ | |
402209ff JH |
632 | |
633 | int | |
634 | flow_loops_find (loops, flags) | |
635 | struct loops *loops; | |
636 | int flags; | |
637 | { | |
0b17ab2f RH |
638 | int i; |
639 | int b; | |
402209ff JH |
640 | int num_loops; |
641 | edge e; | |
642 | sbitmap headers; | |
643 | sbitmap *dom; | |
644 | int *dfs_order; | |
645 | int *rc_order; | |
646 | ||
647 | /* This function cannot be repeatedly called with different | |
648 | flags to build up the loop information. The loop tree | |
649 | must always be built if this function is called. */ | |
650 | if (! (flags & LOOP_TREE)) | |
651 | abort (); | |
652 | ||
5f0d2358 | 653 | memset (loops, 0, sizeof *loops); |
402209ff JH |
654 | |
655 | /* Taking care of this degenerate case makes the rest of | |
656 | this code simpler. */ | |
0b17ab2f | 657 | if (n_basic_blocks == 0) |
402209ff JH |
658 | return 0; |
659 | ||
660 | dfs_order = NULL; | |
661 | rc_order = NULL; | |
662 | ||
663 | /* Compute the dominators. */ | |
0b17ab2f | 664 | dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks); |
402209ff JH |
665 | calculate_dominance_info (NULL, dom, CDI_DOMINATORS); |
666 | ||
667 | /* Count the number of loop edges (back edges). This should be the | |
668 | same as the number of natural loops. */ | |
402209ff | 669 | num_loops = 0; |
0b17ab2f | 670 | for (b = 0; b < n_basic_blocks; b++) |
402209ff | 671 | { |
0b17ab2f RH |
672 | basic_block header; |
673 | ||
674 | header = BASIC_BLOCK (b); | |
402209ff JH |
675 | header->loop_depth = 0; |
676 | ||
677 | for (e = header->pred; e; e = e->pred_next) | |
678 | { | |
679 | basic_block latch = e->src; | |
680 | ||
681 | /* Look for back edges where a predecessor is dominated | |
682 | by this block. A natural loop has a single entry | |
683 | node (header) that dominates all the nodes in the | |
684 | loop. It also has single back edge to the header | |
685 | from a latch node. Note that multiple natural loops | |
686 | may share the same header. */ | |
0b17ab2f RH |
687 | if (b != header->index) |
688 | abort (); | |
689 | ||
690 | if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], b)) | |
402209ff JH |
691 | num_loops++; |
692 | } | |
693 | } | |
694 | ||
695 | if (num_loops) | |
696 | { | |
697 | /* Compute depth first search order of the CFG so that outer | |
698 | natural loops will be found before inner natural loops. */ | |
0b17ab2f RH |
699 | dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int)); |
700 | rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int)); | |
402209ff JH |
701 | flow_depth_first_order_compute (dfs_order, rc_order); |
702 | ||
703 | /* Save CFG derived information to avoid recomputing it. */ | |
704 | loops->cfg.dom = dom; | |
705 | loops->cfg.dfs_order = dfs_order; | |
706 | loops->cfg.rc_order = rc_order; | |
707 | ||
708 | /* Allocate loop structures. */ | |
709 | loops->array | |
710 | = (struct loop *) xcalloc (num_loops, sizeof (struct loop)); | |
711 | ||
0b17ab2f | 712 | headers = sbitmap_alloc (n_basic_blocks); |
402209ff JH |
713 | sbitmap_zero (headers); |
714 | ||
0b17ab2f | 715 | loops->shared_headers = sbitmap_alloc (n_basic_blocks); |
402209ff JH |
716 | sbitmap_zero (loops->shared_headers); |
717 | ||
718 | /* Find and record information about all the natural loops | |
719 | in the CFG. */ | |
720 | num_loops = 0; | |
0b17ab2f | 721 | for (b = n_basic_blocks - 1; b >= 0; b--) |
402209ff | 722 | { |
b09d108b | 723 | basic_block latch; |
402209ff JH |
724 | |
725 | /* Search the nodes of the CFG in reverse completion order | |
726 | so that we can find outer loops first. */ | |
b09d108b | 727 | latch = BASIC_BLOCK (rc_order[b]); |
402209ff | 728 | |
b09d108b JZ |
729 | /* Look for all the possible headers for this latch block. */ |
730 | for (e = latch->succ; e; e = e->succ_next) | |
402209ff | 731 | { |
b09d108b JZ |
732 | basic_block header = e->dest; |
733 | ||
734 | /* Look for forward edges where this block is dominated by | |
735 | a successor of this block. A natural loop has a single | |
736 | entry node (header) that dominates all the nodes in the | |
737 | loop. It also has single back edge to the header from a | |
738 | latch node. Note that multiple natural loops may share | |
739 | the same header. */ | |
740 | if (header != EXIT_BLOCK_PTR | |
0b17ab2f | 741 | && TEST_BIT (dom[latch->index], header->index)) |
402209ff JH |
742 | { |
743 | struct loop *loop; | |
744 | ||
745 | loop = loops->array + num_loops; | |
746 | ||
747 | loop->header = header; | |
748 | loop->latch = latch; | |
749 | loop->num = num_loops; | |
750 | ||
751 | num_loops++; | |
752 | } | |
753 | } | |
754 | } | |
755 | ||
756 | for (i = 0; i < num_loops; i++) | |
757 | { | |
758 | struct loop *loop = &loops->array[i]; | |
759 | ||
760 | /* Keep track of blocks that are loop headers so | |
761 | that we can tell which loops should be merged. */ | |
0b17ab2f RH |
762 | if (TEST_BIT (headers, loop->header->index)) |
763 | SET_BIT (loops->shared_headers, loop->header->index); | |
764 | SET_BIT (headers, loop->header->index); | |
402209ff JH |
765 | |
766 | /* Find nodes contained within the loop. */ | |
0b17ab2f | 767 | loop->nodes = sbitmap_alloc (n_basic_blocks); |
402209ff JH |
768 | loop->num_nodes |
769 | = flow_loop_nodes_find (loop->header, loop->latch, loop->nodes); | |
770 | ||
771 | /* Compute first and last blocks within the loop. | |
772 | These are often the same as the loop header and | |
773 | loop latch respectively, but this is not always | |
774 | the case. */ | |
775 | loop->first | |
776 | = BASIC_BLOCK (sbitmap_first_set_bit (loop->nodes)); | |
777 | loop->last | |
778 | = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes)); | |
779 | ||
780 | flow_loop_scan (loops, loop, flags); | |
781 | } | |
782 | ||
783 | /* Natural loops with shared headers may either be disjoint or | |
784 | nested. Disjoint loops with shared headers cannot be inner | |
785 | loops and should be merged. For now just mark loops that share | |
786 | headers. */ | |
787 | for (i = 0; i < num_loops; i++) | |
0b17ab2f | 788 | if (TEST_BIT (loops->shared_headers, loops->array[i].header->index)) |
402209ff JH |
789 | loops->array[i].shared = 1; |
790 | ||
791 | sbitmap_free (headers); | |
792 | } | |
793 | else | |
5f0d2358 | 794 | sbitmap_vector_free (dom); |
402209ff JH |
795 | |
796 | loops->num = num_loops; | |
797 | ||
798 | /* Build the loop hierarchy tree. */ | |
799 | flow_loops_tree_build (loops); | |
800 | ||
801 | /* Assign the loop nesting depth and enclosed loop level for each | |
802 | loop. */ | |
803 | loops->levels = flow_loops_level_compute (loops); | |
804 | ||
805 | return num_loops; | |
806 | } | |
807 | ||
808 | /* Update the information regarding the loops in the CFG | |
809 | specified by LOOPS. */ | |
5f0d2358 | 810 | |
402209ff JH |
811 | int |
812 | flow_loops_update (loops, flags) | |
813 | struct loops *loops; | |
814 | int flags; | |
815 | { | |
816 | /* One day we may want to update the current loop data. For now | |
817 | throw away the old stuff and rebuild what we need. */ | |
818 | if (loops->array) | |
819 | flow_loops_free (loops); | |
820 | ||
821 | return flow_loops_find (loops, flags); | |
822 | } | |
823 | ||
824 | /* Return non-zero if edge E enters header of LOOP from outside of LOOP. */ | |
825 | ||
826 | int | |
827 | flow_loop_outside_edge_p (loop, e) | |
828 | const struct loop *loop; | |
829 | edge e; | |
830 | { | |
831 | if (e->dest != loop->header) | |
832 | abort (); | |
5f0d2358 RK |
833 | |
834 | return (e->src == ENTRY_BLOCK_PTR) | |
0b17ab2f | 835 | || ! TEST_BIT (loop->nodes, e->src->index); |
402209ff | 836 | } |