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