]>
Commit | Line | Data |
---|---|---|
402209ff | 1 | /* Natural loop discovery code for GNU compiler. |
c8d3e15a | 2 | Copyright (C) 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc. |
402209ff JH |
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 | |
366ccddb KC |
18 | Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA |
19 | 02110-1301, USA. */ | |
402209ff JH |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
4977bab6 ZW |
23 | #include "coretypes.h" |
24 | #include "tm.h" | |
402209ff JH |
25 | #include "rtl.h" |
26 | #include "hard-reg-set.h" | |
7932a3db | 27 | #include "obstack.h" |
a310245f | 28 | #include "function.h" |
402209ff | 29 | #include "basic-block.h" |
2ecfd709 | 30 | #include "toplev.h" |
3d436d2a ZD |
31 | #include "cfgloop.h" |
32 | #include "flags.h" | |
6de9cd9a DN |
33 | #include "tree.h" |
34 | #include "tree-flow.h" | |
2ecfd709 ZD |
35 | |
36 | /* Ratio of frequencies of edges so that one of more latch edges is | |
37 | considered to belong to inner loop with same header. */ | |
38 | #define HEAVY_EDGE_RATIO 8 | |
402209ff | 39 | |
f470c378 ZD |
40 | #define HEADER_BLOCK(B) (* (int *) (B)->aux) |
41 | #define LATCH_EDGE(E) (*(int *) (E)->aux) | |
42 | ||
d329e058 | 43 | static void flow_loops_cfg_dump (const struct loops *, FILE *); |
d329e058 | 44 | static void establish_preds (struct loop *); |
d329e058 AJ |
45 | static void canonicalize_loop_headers (void); |
46 | static bool glb_enum_p (basic_block, void *); | |
402209ff JH |
47 | \f |
48 | /* Dump loop related CFG information. */ | |
49 | ||
50 | static void | |
d329e058 | 51 | flow_loops_cfg_dump (const struct loops *loops, FILE *file) |
402209ff | 52 | { |
e0082a72 | 53 | basic_block bb; |
402209ff | 54 | |
d47cc544 | 55 | if (! loops->num || ! file) |
402209ff JH |
56 | return; |
57 | ||
e0082a72 | 58 | FOR_EACH_BB (bb) |
402209ff JH |
59 | { |
60 | edge succ; | |
628f6a4e | 61 | edge_iterator ei; |
402209ff | 62 | |
e0082a72 | 63 | fprintf (file, ";; %d succs { ", bb->index); |
628f6a4e | 64 | FOR_EACH_EDGE (succ, ei, bb->succs) |
0b17ab2f | 65 | fprintf (file, "%d ", succ->dest->index); |
2ecfd709 | 66 | fprintf (file, "}\n"); |
402209ff | 67 | } |
402209ff JH |
68 | } |
69 | ||
da7d8304 | 70 | /* Return nonzero if the nodes of LOOP are a subset of OUTER. */ |
402209ff | 71 | |
2ecfd709 | 72 | bool |
d329e058 | 73 | flow_loop_nested_p (const struct loop *outer, const struct loop *loop) |
402209ff | 74 | { |
7ea7e058 RK |
75 | return (loop->depth > outer->depth |
76 | && loop->pred[outer->depth] == outer); | |
402209ff JH |
77 | } |
78 | ||
1ad03593 SP |
79 | /* Returns the loop such that LOOP is nested DEPTH (indexed from zero) |
80 | loops within LOOP. */ | |
a7e5372d ZD |
81 | |
82 | struct loop * | |
83 | superloop_at_depth (struct loop *loop, unsigned depth) | |
84 | { | |
341c100f | 85 | gcc_assert (depth <= (unsigned) loop->depth); |
a7e5372d ZD |
86 | |
87 | if (depth == (unsigned) loop->depth) | |
88 | return loop; | |
89 | ||
90 | return loop->pred[depth]; | |
91 | } | |
92 | ||
402209ff JH |
93 | /* Dump the loop information specified by LOOP to the stream FILE |
94 | using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ | |
95 | ||
96 | void | |
d329e058 AJ |
97 | flow_loop_dump (const struct loop *loop, FILE *file, |
98 | void (*loop_dump_aux) (const struct loop *, FILE *, int), | |
99 | int verbose) | |
402209ff | 100 | { |
2ecfd709 | 101 | basic_block *bbs; |
3d436d2a | 102 | unsigned i; |
2ecfd709 | 103 | |
402209ff JH |
104 | if (! loop || ! loop->header) |
105 | return; | |
106 | ||
7490e6c4 | 107 | fprintf (file, ";;\n;; Loop %d\n", loop->num); |
402209ff | 108 | |
70388d94 ZD |
109 | fprintf (file, ";; header %d, latch %d\n", |
110 | loop->header->index, loop->latch->index); | |
99f8a411 ZD |
111 | fprintf (file, ";; depth %d, outer %ld\n", |
112 | loop->depth, (long) (loop->outer ? loop->outer->num : -1)); | |
402209ff | 113 | |
2ecfd709 ZD |
114 | fprintf (file, ";; nodes:"); |
115 | bbs = get_loop_body (loop); | |
116 | for (i = 0; i < loop->num_nodes; i++) | |
117 | fprintf (file, " %d", bbs[i]->index); | |
118 | free (bbs); | |
119 | fprintf (file, "\n"); | |
5f0d2358 | 120 | |
402209ff JH |
121 | if (loop_dump_aux) |
122 | loop_dump_aux (loop, file, verbose); | |
123 | } | |
124 | ||
125 | /* Dump the loop information specified by LOOPS to the stream FILE, | |
126 | using auxiliary dump callback function LOOP_DUMP_AUX if non null. */ | |
127 | ||
128 | void | |
d329e058 | 129 | flow_loops_dump (const struct loops *loops, FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose) |
402209ff | 130 | { |
2ecfd709 | 131 | int i; |
402209ff JH |
132 | int num_loops; |
133 | ||
134 | num_loops = loops->num; | |
135 | if (! num_loops || ! file) | |
136 | return; | |
137 | ||
43a613f7 | 138 | fprintf (file, ";; %d loops found\n", num_loops); |
2ecfd709 | 139 | |
402209ff JH |
140 | for (i = 0; i < num_loops; i++) |
141 | { | |
2ecfd709 | 142 | struct loop *loop = loops->parray[i]; |
402209ff | 143 | |
2ecfd709 ZD |
144 | if (!loop) |
145 | continue; | |
5f0d2358 | 146 | |
2ecfd709 | 147 | flow_loop_dump (loop, file, loop_dump_aux, verbose); |
402209ff JH |
148 | } |
149 | ||
150 | if (verbose) | |
151 | flow_loops_cfg_dump (loops, file); | |
152 | } | |
153 | ||
2ecfd709 | 154 | /* Free data allocated for LOOP. */ |
35b07080 | 155 | void |
d329e058 | 156 | flow_loop_free (struct loop *loop) |
2ecfd709 | 157 | { |
2ecfd709 ZD |
158 | if (loop->pred) |
159 | free (loop->pred); | |
160 | free (loop); | |
161 | } | |
162 | ||
402209ff JH |
163 | /* Free all the memory allocated for LOOPS. */ |
164 | ||
165 | void | |
d329e058 | 166 | flow_loops_free (struct loops *loops) |
402209ff | 167 | { |
2ecfd709 | 168 | if (loops->parray) |
402209ff | 169 | { |
3d436d2a | 170 | unsigned i; |
402209ff | 171 | |
341c100f | 172 | gcc_assert (loops->num); |
402209ff JH |
173 | |
174 | /* Free the loop descriptors. */ | |
175 | for (i = 0; i < loops->num; i++) | |
176 | { | |
2ecfd709 ZD |
177 | struct loop *loop = loops->parray[i]; |
178 | ||
179 | if (!loop) | |
180 | continue; | |
181 | ||
182 | flow_loop_free (loop); | |
402209ff | 183 | } |
5f0d2358 | 184 | |
2ecfd709 ZD |
185 | free (loops->parray); |
186 | loops->parray = NULL; | |
402209ff JH |
187 | } |
188 | } | |
189 | ||
2ecfd709 ZD |
190 | /* Find the nodes contained within the LOOP with header HEADER. |
191 | Return the number of nodes within the loop. */ | |
402209ff | 192 | |
2b271002 | 193 | int |
d329e058 | 194 | flow_loop_nodes_find (basic_block header, struct loop *loop) |
402209ff JH |
195 | { |
196 | basic_block *stack; | |
197 | int sp; | |
2ecfd709 | 198 | int num_nodes = 1; |
402209ff | 199 | |
2ecfd709 ZD |
200 | header->loop_father = loop; |
201 | header->loop_depth = loop->depth; | |
402209ff | 202 | |
2ecfd709 | 203 | if (loop->latch->loop_father != loop) |
402209ff | 204 | { |
5ed6ace5 | 205 | stack = XNEWVEC (basic_block, n_basic_blocks); |
2ecfd709 | 206 | sp = 0; |
402209ff | 207 | num_nodes++; |
2ecfd709 ZD |
208 | stack[sp++] = loop->latch; |
209 | loop->latch->loop_father = loop; | |
210 | loop->latch->loop_depth = loop->depth; | |
d329e058 | 211 | |
2ecfd709 | 212 | while (sp) |
402209ff | 213 | { |
2ecfd709 ZD |
214 | basic_block node; |
215 | edge e; | |
628f6a4e | 216 | edge_iterator ei; |
402209ff | 217 | |
2ecfd709 | 218 | node = stack[--sp]; |
d329e058 | 219 | |
628f6a4e | 220 | FOR_EACH_EDGE (e, ei, node->preds) |
402209ff | 221 | { |
2ecfd709 ZD |
222 | basic_block ancestor = e->src; |
223 | ||
224 | if (ancestor != ENTRY_BLOCK_PTR | |
225 | && ancestor->loop_father != loop) | |
226 | { | |
227 | ancestor->loop_father = loop; | |
228 | ancestor->loop_depth = loop->depth; | |
229 | num_nodes++; | |
230 | stack[sp++] = ancestor; | |
231 | } | |
402209ff JH |
232 | } |
233 | } | |
2ecfd709 | 234 | free (stack); |
402209ff | 235 | } |
402209ff JH |
236 | return num_nodes; |
237 | } | |
238 | ||
82b85a85 ZD |
239 | /* For each loop in the lOOPS tree that has just a single exit |
240 | record the exit edge. */ | |
241 | ||
242 | void | |
243 | mark_single_exit_loops (struct loops *loops) | |
244 | { | |
245 | basic_block bb; | |
246 | edge e; | |
247 | struct loop *loop; | |
248 | unsigned i; | |
249 | ||
250 | for (i = 1; i < loops->num; i++) | |
251 | { | |
252 | loop = loops->parray[i]; | |
253 | if (loop) | |
ac8f6c69 | 254 | set_single_exit (loop, NULL); |
82b85a85 ZD |
255 | } |
256 | ||
257 | FOR_EACH_BB (bb) | |
258 | { | |
628f6a4e | 259 | edge_iterator ei; |
82b85a85 ZD |
260 | if (bb->loop_father == loops->tree_root) |
261 | continue; | |
628f6a4e | 262 | FOR_EACH_EDGE (e, ei, bb->succs) |
82b85a85 ZD |
263 | { |
264 | if (e->dest == EXIT_BLOCK_PTR) | |
265 | continue; | |
266 | ||
267 | if (flow_bb_inside_loop_p (bb->loop_father, e->dest)) | |
268 | continue; | |
269 | ||
270 | for (loop = bb->loop_father; | |
271 | loop != e->dest->loop_father; | |
272 | loop = loop->outer) | |
273 | { | |
274 | /* If we have already seen an exit, mark this by the edge that | |
275 | surely does not occur as any exit. */ | |
ac8f6c69 ZD |
276 | if (single_exit (loop)) |
277 | set_single_exit (loop, single_succ_edge (ENTRY_BLOCK_PTR)); | |
82b85a85 | 278 | else |
ac8f6c69 | 279 | set_single_exit (loop, e); |
82b85a85 ZD |
280 | } |
281 | } | |
282 | } | |
283 | ||
284 | for (i = 1; i < loops->num; i++) | |
285 | { | |
286 | loop = loops->parray[i]; | |
287 | if (!loop) | |
288 | continue; | |
289 | ||
ac8f6c69 ZD |
290 | if (single_exit (loop) == single_succ_edge (ENTRY_BLOCK_PTR)) |
291 | set_single_exit (loop, NULL); | |
82b85a85 ZD |
292 | } |
293 | ||
294 | loops->state |= LOOPS_HAVE_MARKED_SINGLE_EXITS; | |
295 | } | |
296 | ||
35b07080 | 297 | static void |
d329e058 | 298 | establish_preds (struct loop *loop) |
35b07080 ZD |
299 | { |
300 | struct loop *ploop, *father = loop->outer; | |
301 | ||
302 | loop->depth = father->depth + 1; | |
a310245f SB |
303 | |
304 | /* Remember the current loop depth if it is the largest seen so far. */ | |
305 | cfun->max_loop_depth = MAX (cfun->max_loop_depth, loop->depth); | |
306 | ||
35b07080 ZD |
307 | if (loop->pred) |
308 | free (loop->pred); | |
5ed6ace5 | 309 | loop->pred = XNEWVEC (struct loop *, loop->depth); |
35b07080 ZD |
310 | memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth); |
311 | loop->pred[father->depth] = father; | |
312 | ||
313 | for (ploop = loop->inner; ploop; ploop = ploop->next) | |
314 | establish_preds (ploop); | |
315 | } | |
316 | ||
2ecfd709 | 317 | /* Add LOOP to the loop hierarchy tree where FATHER is father of the |
35b07080 ZD |
318 | added loop. If LOOP has some children, take care of that their |
319 | pred field will be initialized correctly. */ | |
402209ff | 320 | |
2ecfd709 | 321 | void |
d329e058 | 322 | flow_loop_tree_node_add (struct loop *father, struct loop *loop) |
402209ff | 323 | { |
2ecfd709 ZD |
324 | loop->next = father->inner; |
325 | father->inner = loop; | |
326 | loop->outer = father; | |
327 | ||
35b07080 | 328 | establish_preds (loop); |
402209ff JH |
329 | } |
330 | ||
2ecfd709 | 331 | /* Remove LOOP from the loop hierarchy tree. */ |
402209ff | 332 | |
2ecfd709 | 333 | void |
d329e058 | 334 | flow_loop_tree_node_remove (struct loop *loop) |
402209ff | 335 | { |
2ecfd709 | 336 | struct loop *prev, *father; |
402209ff | 337 | |
2ecfd709 ZD |
338 | father = loop->outer; |
339 | loop->outer = NULL; | |
402209ff | 340 | |
2ecfd709 ZD |
341 | /* Remove loop from the list of sons. */ |
342 | if (father->inner == loop) | |
343 | father->inner = loop->next; | |
344 | else | |
345 | { | |
346 | for (prev = father->inner; prev->next != loop; prev = prev->next); | |
347 | prev->next = loop->next; | |
348 | } | |
402209ff | 349 | |
2ecfd709 ZD |
350 | loop->depth = -1; |
351 | free (loop->pred); | |
352 | loop->pred = NULL; | |
402209ff JH |
353 | } |
354 | ||
f470c378 ZD |
355 | /* A callback to update latch and header info for basic block JUMP created |
356 | by redirecting an edge. */ | |
2ecfd709 | 357 | |
2ecfd709 | 358 | static void |
f470c378 | 359 | update_latch_info (basic_block jump) |
2ecfd709 | 360 | { |
f470c378 ZD |
361 | alloc_aux_for_block (jump, sizeof (int)); |
362 | HEADER_BLOCK (jump) = 0; | |
c5cbcccf ZD |
363 | alloc_aux_for_edge (single_pred_edge (jump), sizeof (int)); |
364 | LATCH_EDGE (single_pred_edge (jump)) = 0; | |
365 | set_immediate_dominator (CDI_DOMINATORS, jump, single_pred (jump)); | |
2ecfd709 ZD |
366 | } |
367 | ||
f470c378 ZD |
368 | /* A callback for make_forwarder block, to redirect all edges except for |
369 | MFB_KJ_EDGE to the entry part. E is the edge for that we should decide | |
370 | whether to redirect it. */ | |
2ecfd709 | 371 | |
f470c378 ZD |
372 | static edge mfb_kj_edge; |
373 | static bool | |
374 | mfb_keep_just (edge e) | |
2ecfd709 | 375 | { |
f470c378 ZD |
376 | return e != mfb_kj_edge; |
377 | } | |
2ecfd709 | 378 | |
f470c378 ZD |
379 | /* A callback for make_forwarder block, to redirect the latch edges into an |
380 | entry part. E is the edge for that we should decide whether to redirect | |
381 | it. */ | |
2ecfd709 | 382 | |
f470c378 ZD |
383 | static bool |
384 | mfb_keep_nonlatch (edge e) | |
385 | { | |
386 | return LATCH_EDGE (e); | |
2ecfd709 ZD |
387 | } |
388 | ||
389 | /* Takes care of merging natural loops with shared headers. */ | |
f470c378 | 390 | |
2ecfd709 | 391 | static void |
d329e058 | 392 | canonicalize_loop_headers (void) |
2ecfd709 | 393 | { |
2ecfd709 ZD |
394 | basic_block header; |
395 | edge e; | |
d329e058 | 396 | |
2ecfd709 ZD |
397 | alloc_aux_for_blocks (sizeof (int)); |
398 | alloc_aux_for_edges (sizeof (int)); | |
399 | ||
400 | /* Split blocks so that each loop has only single latch. */ | |
401 | FOR_EACH_BB (header) | |
402 | { | |
628f6a4e | 403 | edge_iterator ei; |
2ecfd709 ZD |
404 | int num_latches = 0; |
405 | int have_abnormal_edge = 0; | |
406 | ||
628f6a4e | 407 | FOR_EACH_EDGE (e, ei, header->preds) |
2ecfd709 ZD |
408 | { |
409 | basic_block latch = e->src; | |
410 | ||
411 | if (e->flags & EDGE_ABNORMAL) | |
412 | have_abnormal_edge = 1; | |
413 | ||
414 | if (latch != ENTRY_BLOCK_PTR | |
d47cc544 | 415 | && dominated_by_p (CDI_DOMINATORS, latch, header)) |
2ecfd709 ZD |
416 | { |
417 | num_latches++; | |
418 | LATCH_EDGE (e) = 1; | |
419 | } | |
420 | } | |
421 | if (have_abnormal_edge) | |
422 | HEADER_BLOCK (header) = 0; | |
423 | else | |
424 | HEADER_BLOCK (header) = num_latches; | |
425 | } | |
426 | ||
c5cbcccf | 427 | if (HEADER_BLOCK (single_succ (ENTRY_BLOCK_PTR))) |
2ecfd709 ZD |
428 | { |
429 | basic_block bb; | |
430 | ||
431 | /* We could not redirect edges freely here. On the other hand, | |
432 | we can simply split the edge from entry block. */ | |
c5cbcccf | 433 | bb = split_edge (single_succ_edge (ENTRY_BLOCK_PTR)); |
d329e058 | 434 | |
c5cbcccf ZD |
435 | alloc_aux_for_edge (single_succ_edge (bb), sizeof (int)); |
436 | LATCH_EDGE (single_succ_edge (bb)) = 0; | |
2ecfd709 ZD |
437 | alloc_aux_for_block (bb, sizeof (int)); |
438 | HEADER_BLOCK (bb) = 0; | |
439 | } | |
440 | ||
441 | FOR_EACH_BB (header) | |
442 | { | |
2ecfd709 | 443 | int max_freq, is_heavy; |
f470c378 | 444 | edge heavy, tmp_edge; |
628f6a4e | 445 | edge_iterator ei; |
2ecfd709 | 446 | |
f470c378 | 447 | if (HEADER_BLOCK (header) <= 1) |
2ecfd709 ZD |
448 | continue; |
449 | ||
450 | /* Find a heavy edge. */ | |
451 | is_heavy = 1; | |
452 | heavy = NULL; | |
453 | max_freq = 0; | |
628f6a4e | 454 | FOR_EACH_EDGE (e, ei, header->preds) |
2ecfd709 ZD |
455 | if (LATCH_EDGE (e) && |
456 | EDGE_FREQUENCY (e) > max_freq) | |
457 | max_freq = EDGE_FREQUENCY (e); | |
628f6a4e | 458 | FOR_EACH_EDGE (e, ei, header->preds) |
2ecfd709 ZD |
459 | if (LATCH_EDGE (e) && |
460 | EDGE_FREQUENCY (e) >= max_freq / HEAVY_EDGE_RATIO) | |
461 | { | |
462 | if (heavy) | |
463 | { | |
464 | is_heavy = 0; | |
465 | break; | |
466 | } | |
467 | else | |
468 | heavy = e; | |
469 | } | |
470 | ||
471 | if (is_heavy) | |
472 | { | |
f470c378 ZD |
473 | /* Split out the heavy edge, and create inner loop for it. */ |
474 | mfb_kj_edge = heavy; | |
475 | tmp_edge = make_forwarder_block (header, mfb_keep_just, | |
476 | update_latch_info); | |
477 | alloc_aux_for_block (tmp_edge->dest, sizeof (int)); | |
478 | HEADER_BLOCK (tmp_edge->dest) = 1; | |
479 | alloc_aux_for_edge (tmp_edge, sizeof (int)); | |
480 | LATCH_EDGE (tmp_edge) = 0; | |
481 | HEADER_BLOCK (header)--; | |
482 | } | |
483 | ||
484 | if (HEADER_BLOCK (header) > 1) | |
485 | { | |
486 | /* Create a new latch block. */ | |
487 | tmp_edge = make_forwarder_block (header, mfb_keep_nonlatch, | |
488 | update_latch_info); | |
489 | alloc_aux_for_block (tmp_edge->dest, sizeof (int)); | |
490 | HEADER_BLOCK (tmp_edge->src) = 0; | |
491 | HEADER_BLOCK (tmp_edge->dest) = 1; | |
492 | alloc_aux_for_edge (tmp_edge, sizeof (int)); | |
493 | LATCH_EDGE (tmp_edge) = 1; | |
2ecfd709 | 494 | } |
2ecfd709 ZD |
495 | } |
496 | ||
497 | free_aux_for_blocks (); | |
498 | free_aux_for_edges (); | |
e7bd94cc ZD |
499 | |
500 | #ifdef ENABLE_CHECKING | |
501 | verify_dominators (CDI_DOMINATORS); | |
502 | #endif | |
2ecfd709 ZD |
503 | } |
504 | ||
86df10e3 SP |
505 | /* Initialize all the parallel_p fields of the loops structure to true. */ |
506 | ||
507 | static void | |
508 | initialize_loops_parallel_p (struct loops *loops) | |
509 | { | |
510 | unsigned int i; | |
511 | ||
512 | for (i = 0; i < loops->num; i++) | |
513 | { | |
514 | struct loop *loop = loops->parray[i]; | |
515 | loop->parallel_p = true; | |
516 | } | |
517 | } | |
518 | ||
5f0d2358 | 519 | /* Find all the natural loops in the function and save in LOOPS structure and |
70388d94 ZD |
520 | recalculate loop_depth information in basic block structures. |
521 | Return the number of natural loops found. */ | |
402209ff JH |
522 | |
523 | int | |
70388d94 | 524 | flow_loops_find (struct loops *loops) |
402209ff | 525 | { |
0b17ab2f | 526 | int b; |
402209ff JH |
527 | int num_loops; |
528 | edge e; | |
529 | sbitmap headers; | |
402209ff JH |
530 | int *dfs_order; |
531 | int *rc_order; | |
355be0dc JH |
532 | basic_block header; |
533 | basic_block bb; | |
402209ff | 534 | |
5f0d2358 | 535 | memset (loops, 0, sizeof *loops); |
402209ff | 536 | |
a310245f SB |
537 | /* We are going to recount the maximum loop depth, |
538 | so throw away the last count. */ | |
539 | cfun->max_loop_depth = 0; | |
540 | ||
402209ff JH |
541 | /* Taking care of this degenerate case makes the rest of |
542 | this code simpler. */ | |
24bd1a0b | 543 | if (n_basic_blocks == NUM_FIXED_BLOCKS) |
402209ff JH |
544 | return 0; |
545 | ||
546 | dfs_order = NULL; | |
547 | rc_order = NULL; | |
548 | ||
e7bd94cc ZD |
549 | /* Ensure that the dominators are computed. */ |
550 | calculate_dominance_info (CDI_DOMINATORS); | |
551 | ||
2ecfd709 ZD |
552 | /* Join loops with shared headers. */ |
553 | canonicalize_loop_headers (); | |
554 | ||
2ecfd709 | 555 | /* Count the number of loop headers. This should be the |
402209ff | 556 | same as the number of natural loops. */ |
2ecfd709 ZD |
557 | headers = sbitmap_alloc (last_basic_block); |
558 | sbitmap_zero (headers); | |
559 | ||
402209ff | 560 | num_loops = 0; |
e0082a72 | 561 | FOR_EACH_BB (header) |
402209ff | 562 | { |
628f6a4e | 563 | edge_iterator ei; |
2ecfd709 | 564 | int more_latches = 0; |
d329e058 | 565 | |
402209ff JH |
566 | header->loop_depth = 0; |
567 | ||
16f2b86a ZD |
568 | /* If we have an abnormal predecessor, do not consider the |
569 | loop (not worth the problems). */ | |
628f6a4e | 570 | FOR_EACH_EDGE (e, ei, header->preds) |
16f2b86a ZD |
571 | if (e->flags & EDGE_ABNORMAL) |
572 | break; | |
573 | if (e) | |
574 | continue; | |
575 | ||
628f6a4e | 576 | FOR_EACH_EDGE (e, ei, header->preds) |
402209ff JH |
577 | { |
578 | basic_block latch = e->src; | |
579 | ||
341c100f | 580 | gcc_assert (!(e->flags & EDGE_ABNORMAL)); |
2ecfd709 | 581 | |
402209ff JH |
582 | /* Look for back edges where a predecessor is dominated |
583 | by this block. A natural loop has a single entry | |
584 | node (header) that dominates all the nodes in the | |
585 | loop. It also has single back edge to the header | |
2ecfd709 | 586 | from a latch node. */ |
d47cc544 SB |
587 | if (latch != ENTRY_BLOCK_PTR |
588 | && dominated_by_p (CDI_DOMINATORS, latch, header)) | |
2ecfd709 ZD |
589 | { |
590 | /* Shared headers should be eliminated by now. */ | |
341c100f | 591 | gcc_assert (!more_latches); |
2ecfd709 ZD |
592 | more_latches = 1; |
593 | SET_BIT (headers, header->index); | |
594 | num_loops++; | |
595 | } | |
402209ff JH |
596 | } |
597 | } | |
598 | ||
2ecfd709 | 599 | /* Allocate loop structures. */ |
5ed6ace5 | 600 | loops->parray = XCNEWVEC (struct loop *, num_loops + 1); |
2ecfd709 ZD |
601 | |
602 | /* Dummy loop containing whole function. */ | |
5ed6ace5 | 603 | loops->parray[0] = XCNEW (struct loop); |
2ecfd709 ZD |
604 | loops->parray[0]->next = NULL; |
605 | loops->parray[0]->inner = NULL; | |
606 | loops->parray[0]->outer = NULL; | |
607 | loops->parray[0]->depth = 0; | |
608 | loops->parray[0]->pred = NULL; | |
24bd1a0b | 609 | loops->parray[0]->num_nodes = n_basic_blocks; |
2ecfd709 ZD |
610 | loops->parray[0]->latch = EXIT_BLOCK_PTR; |
611 | loops->parray[0]->header = ENTRY_BLOCK_PTR; | |
612 | ENTRY_BLOCK_PTR->loop_father = loops->parray[0]; | |
613 | EXIT_BLOCK_PTR->loop_father = loops->parray[0]; | |
614 | ||
615 | loops->tree_root = loops->parray[0]; | |
616 | ||
617 | /* Find and record information about all the natural loops | |
618 | in the CFG. */ | |
619 | loops->num = 1; | |
620 | FOR_EACH_BB (bb) | |
621 | bb->loop_father = loops->tree_root; | |
622 | ||
402209ff JH |
623 | if (num_loops) |
624 | { | |
625 | /* Compute depth first search order of the CFG so that outer | |
626 | natural loops will be found before inner natural loops. */ | |
5ed6ace5 MD |
627 | dfs_order = XNEWVEC (int, n_basic_blocks); |
628 | rc_order = XNEWVEC (int, n_basic_blocks); | |
f91a0beb | 629 | pre_and_rev_post_order_compute (dfs_order, rc_order, false); |
402209ff | 630 | |
2ecfd709 | 631 | num_loops = 1; |
402209ff | 632 | |
24bd1a0b | 633 | for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++) |
402209ff | 634 | { |
2ecfd709 | 635 | struct loop *loop; |
628f6a4e | 636 | edge_iterator ei; |
402209ff JH |
637 | |
638 | /* Search the nodes of the CFG in reverse completion order | |
639 | so that we can find outer loops first. */ | |
2ecfd709 ZD |
640 | if (!TEST_BIT (headers, rc_order[b])) |
641 | continue; | |
642 | ||
643 | header = BASIC_BLOCK (rc_order[b]); | |
d329e058 | 644 | |
5ed6ace5 | 645 | loop = loops->parray[num_loops] = XCNEW (struct loop); |
402209ff | 646 | |
2ecfd709 ZD |
647 | loop->header = header; |
648 | loop->num = num_loops; | |
649 | num_loops++; | |
650 | ||
651 | /* Look for the latch for this header block. */ | |
628f6a4e | 652 | FOR_EACH_EDGE (e, ei, header->preds) |
402209ff | 653 | { |
2ecfd709 ZD |
654 | basic_block latch = e->src; |
655 | ||
656 | if (latch != ENTRY_BLOCK_PTR | |
d47cc544 | 657 | && dominated_by_p (CDI_DOMINATORS, latch, header)) |
402209ff | 658 | { |
402209ff | 659 | loop->latch = latch; |
2ecfd709 | 660 | break; |
402209ff JH |
661 | } |
662 | } | |
402209ff | 663 | |
2ecfd709 ZD |
664 | flow_loop_tree_node_add (header->loop_father, loop); |
665 | loop->num_nodes = flow_loop_nodes_find (loop->header, loop); | |
402209ff JH |
666 | } |
667 | ||
2ecfd709 | 668 | loops->num = num_loops; |
86df10e3 | 669 | initialize_loops_parallel_p (loops); |
598ec7bd ZD |
670 | |
671 | free (dfs_order); | |
672 | free (rc_order); | |
2ecfd709 | 673 | } |
3d436d2a | 674 | |
36579663 AP |
675 | sbitmap_free (headers); |
676 | ||
3d436d2a | 677 | loops->state = 0; |
2ecfd709 | 678 | return loops->num; |
402209ff JH |
679 | } |
680 | ||
da7d8304 | 681 | /* Return nonzero if basic block BB belongs to LOOP. */ |
2ecfd709 | 682 | bool |
d329e058 | 683 | flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb) |
2ecfd709 ZD |
684 | { |
685 | struct loop *source_loop; | |
686 | ||
687 | if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR) | |
688 | return 0; | |
689 | ||
690 | source_loop = bb->loop_father; | |
691 | return loop == source_loop || flow_loop_nested_p (loop, source_loop); | |
692 | } | |
693 | ||
2ecfd709 ZD |
694 | /* Enumeration predicate for get_loop_body. */ |
695 | static bool | |
d329e058 | 696 | glb_enum_p (basic_block bb, void *glb_header) |
2ecfd709 ZD |
697 | { |
698 | return bb != (basic_block) glb_header; | |
699 | } | |
700 | ||
8d28e87d ZD |
701 | /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs |
702 | order against direction of edges from latch. Specially, if | |
703 | header != latch, latch is the 1-st block. */ | |
2ecfd709 | 704 | basic_block * |
d329e058 | 705 | get_loop_body (const struct loop *loop) |
2ecfd709 ZD |
706 | { |
707 | basic_block *tovisit, bb; | |
3d436d2a | 708 | unsigned tv = 0; |
2ecfd709 | 709 | |
341c100f | 710 | gcc_assert (loop->num_nodes); |
2ecfd709 | 711 | |
5ed6ace5 | 712 | tovisit = XCNEWVEC (basic_block, loop->num_nodes); |
2ecfd709 ZD |
713 | tovisit[tv++] = loop->header; |
714 | ||
715 | if (loop->latch == EXIT_BLOCK_PTR) | |
716 | { | |
717 | /* There may be blocks unreachable from EXIT_BLOCK. */ | |
24bd1a0b | 718 | gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks); |
2ecfd709 ZD |
719 | FOR_EACH_BB (bb) |
720 | tovisit[tv++] = bb; | |
721 | tovisit[tv++] = EXIT_BLOCK_PTR; | |
722 | } | |
723 | else if (loop->latch != loop->header) | |
724 | { | |
725 | tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p, | |
726 | tovisit + 1, loop->num_nodes - 1, | |
727 | loop->header) + 1; | |
728 | } | |
729 | ||
341c100f | 730 | gcc_assert (tv == loop->num_nodes); |
2ecfd709 ZD |
731 | return tovisit; |
732 | } | |
733 | ||
50654f6c ZD |
734 | /* Fills dominance descendants inside LOOP of the basic block BB into |
735 | array TOVISIT from index *TV. */ | |
736 | ||
737 | static void | |
738 | fill_sons_in_loop (const struct loop *loop, basic_block bb, | |
739 | basic_block *tovisit, int *tv) | |
740 | { | |
741 | basic_block son, postpone = NULL; | |
742 | ||
743 | tovisit[(*tv)++] = bb; | |
744 | for (son = first_dom_son (CDI_DOMINATORS, bb); | |
745 | son; | |
746 | son = next_dom_son (CDI_DOMINATORS, son)) | |
747 | { | |
748 | if (!flow_bb_inside_loop_p (loop, son)) | |
749 | continue; | |
750 | ||
751 | if (dominated_by_p (CDI_DOMINATORS, loop->latch, son)) | |
752 | { | |
753 | postpone = son; | |
754 | continue; | |
755 | } | |
756 | fill_sons_in_loop (loop, son, tovisit, tv); | |
757 | } | |
758 | ||
759 | if (postpone) | |
760 | fill_sons_in_loop (loop, postpone, tovisit, tv); | |
761 | } | |
762 | ||
763 | /* Gets body of a LOOP (that must be different from the outermost loop) | |
764 | sorted by dominance relation. Additionally, if a basic block s dominates | |
765 | the latch, then only blocks dominated by s are be after it. */ | |
766 | ||
767 | basic_block * | |
768 | get_loop_body_in_dom_order (const struct loop *loop) | |
769 | { | |
770 | basic_block *tovisit; | |
771 | int tv; | |
772 | ||
341c100f | 773 | gcc_assert (loop->num_nodes); |
50654f6c | 774 | |
5ed6ace5 | 775 | tovisit = XCNEWVEC (basic_block, loop->num_nodes); |
50654f6c | 776 | |
341c100f | 777 | gcc_assert (loop->latch != EXIT_BLOCK_PTR); |
50654f6c ZD |
778 | |
779 | tv = 0; | |
780 | fill_sons_in_loop (loop, loop->header, tovisit, &tv); | |
781 | ||
341c100f | 782 | gcc_assert (tv == (int) loop->num_nodes); |
50654f6c ZD |
783 | |
784 | return tovisit; | |
785 | } | |
786 | ||
40923b20 DP |
787 | /* Get body of a LOOP in breadth first sort order. */ |
788 | ||
789 | basic_block * | |
790 | get_loop_body_in_bfs_order (const struct loop *loop) | |
791 | { | |
792 | basic_block *blocks; | |
793 | basic_block bb; | |
794 | bitmap visited; | |
795 | unsigned int i = 0; | |
796 | unsigned int vc = 1; | |
797 | ||
341c100f NS |
798 | gcc_assert (loop->num_nodes); |
799 | gcc_assert (loop->latch != EXIT_BLOCK_PTR); | |
40923b20 | 800 | |
5ed6ace5 | 801 | blocks = XCNEWVEC (basic_block, loop->num_nodes); |
8bdbfff5 | 802 | visited = BITMAP_ALLOC (NULL); |
40923b20 DP |
803 | |
804 | bb = loop->header; | |
805 | while (i < loop->num_nodes) | |
806 | { | |
807 | edge e; | |
628f6a4e | 808 | edge_iterator ei; |
c22cacf3 | 809 | |
40923b20 | 810 | if (!bitmap_bit_p (visited, bb->index)) |
c22cacf3 MS |
811 | { |
812 | /* This basic block is now visited */ | |
813 | bitmap_set_bit (visited, bb->index); | |
814 | blocks[i++] = bb; | |
815 | } | |
816 | ||
628f6a4e | 817 | FOR_EACH_EDGE (e, ei, bb->succs) |
c22cacf3 MS |
818 | { |
819 | if (flow_bb_inside_loop_p (loop, e->dest)) | |
820 | { | |
821 | if (!bitmap_bit_p (visited, e->dest->index)) | |
822 | { | |
823 | bitmap_set_bit (visited, e->dest->index); | |
824 | blocks[i++] = e->dest; | |
825 | } | |
826 | } | |
827 | } | |
828 | ||
341c100f | 829 | gcc_assert (i >= vc); |
c22cacf3 | 830 | |
40923b20 DP |
831 | bb = blocks[vc++]; |
832 | } | |
c22cacf3 | 833 | |
8bdbfff5 | 834 | BITMAP_FREE (visited); |
40923b20 DP |
835 | return blocks; |
836 | } | |
837 | ||
ca83d385 ZD |
838 | /* Returns the list of the exit edges of a LOOP. */ |
839 | ||
840 | VEC (edge, heap) * | |
841 | get_loop_exit_edges (const struct loop *loop) | |
35b07080 | 842 | { |
ca83d385 ZD |
843 | VEC (edge, heap) *edges = NULL; |
844 | edge e; | |
845 | unsigned i; | |
846 | basic_block *body; | |
628f6a4e | 847 | edge_iterator ei; |
35b07080 | 848 | |
341c100f | 849 | gcc_assert (loop->latch != EXIT_BLOCK_PTR); |
35b07080 ZD |
850 | |
851 | body = get_loop_body (loop); | |
35b07080 | 852 | for (i = 0; i < loop->num_nodes; i++) |
628f6a4e | 853 | FOR_EACH_EDGE (e, ei, body[i]->succs) |
35b07080 | 854 | if (!flow_bb_inside_loop_p (loop, e->dest)) |
ca83d385 | 855 | VEC_safe_push (edge, heap, edges, e); |
35b07080 ZD |
856 | free (body); |
857 | ||
858 | return edges; | |
859 | } | |
860 | ||
50654f6c ZD |
861 | /* Counts the number of conditional branches inside LOOP. */ |
862 | ||
863 | unsigned | |
864 | num_loop_branches (const struct loop *loop) | |
865 | { | |
866 | unsigned i, n; | |
867 | basic_block * body; | |
868 | ||
341c100f | 869 | gcc_assert (loop->latch != EXIT_BLOCK_PTR); |
50654f6c ZD |
870 | |
871 | body = get_loop_body (loop); | |
872 | n = 0; | |
873 | for (i = 0; i < loop->num_nodes; i++) | |
628f6a4e | 874 | if (EDGE_COUNT (body[i]->succs) >= 2) |
50654f6c ZD |
875 | n++; |
876 | free (body); | |
877 | ||
878 | return n; | |
879 | } | |
880 | ||
2ecfd709 ZD |
881 | /* Adds basic block BB to LOOP. */ |
882 | void | |
d329e058 AJ |
883 | add_bb_to_loop (basic_block bb, struct loop *loop) |
884 | { | |
2ecfd709 | 885 | int i; |
d329e058 | 886 | |
598ec7bd | 887 | gcc_assert (bb->loop_father == NULL); |
2ecfd709 ZD |
888 | bb->loop_father = loop; |
889 | bb->loop_depth = loop->depth; | |
890 | loop->num_nodes++; | |
891 | for (i = 0; i < loop->depth; i++) | |
892 | loop->pred[i]->num_nodes++; | |
598ec7bd | 893 | } |
2ecfd709 ZD |
894 | |
895 | /* Remove basic block BB from loops. */ | |
896 | void | |
d329e058 AJ |
897 | remove_bb_from_loops (basic_block bb) |
898 | { | |
2ecfd709 ZD |
899 | int i; |
900 | struct loop *loop = bb->loop_father; | |
901 | ||
598ec7bd | 902 | gcc_assert (loop != NULL); |
2ecfd709 ZD |
903 | loop->num_nodes--; |
904 | for (i = 0; i < loop->depth; i++) | |
905 | loop->pred[i]->num_nodes--; | |
906 | bb->loop_father = NULL; | |
907 | bb->loop_depth = 0; | |
a310245f | 908 | } |
2ecfd709 ZD |
909 | |
910 | /* Finds nearest common ancestor in loop tree for given loops. */ | |
911 | struct loop * | |
d329e058 | 912 | find_common_loop (struct loop *loop_s, struct loop *loop_d) |
2ecfd709 ZD |
913 | { |
914 | if (!loop_s) return loop_d; | |
915 | if (!loop_d) return loop_s; | |
d329e058 | 916 | |
2ecfd709 ZD |
917 | if (loop_s->depth < loop_d->depth) |
918 | loop_d = loop_d->pred[loop_s->depth]; | |
919 | else if (loop_s->depth > loop_d->depth) | |
920 | loop_s = loop_s->pred[loop_d->depth]; | |
921 | ||
922 | while (loop_s != loop_d) | |
923 | { | |
924 | loop_s = loop_s->outer; | |
925 | loop_d = loop_d->outer; | |
926 | } | |
927 | return loop_s; | |
928 | } | |
929 | ||
3d436d2a | 930 | /* Cancels the LOOP; it must be innermost one. */ |
b00bf166 KH |
931 | |
932 | static void | |
d329e058 | 933 | cancel_loop (struct loops *loops, struct loop *loop) |
3d436d2a ZD |
934 | { |
935 | basic_block *bbs; | |
936 | unsigned i; | |
937 | ||
341c100f | 938 | gcc_assert (!loop->inner); |
3d436d2a ZD |
939 | |
940 | /* Move blocks up one level (they should be removed as soon as possible). */ | |
941 | bbs = get_loop_body (loop); | |
942 | for (i = 0; i < loop->num_nodes; i++) | |
943 | bbs[i]->loop_father = loop->outer; | |
944 | ||
945 | /* Remove the loop from structure. */ | |
946 | flow_loop_tree_node_remove (loop); | |
947 | ||
948 | /* Remove loop from loops array. */ | |
949 | loops->parray[loop->num] = NULL; | |
950 | ||
951 | /* Free loop data. */ | |
952 | flow_loop_free (loop); | |
953 | } | |
954 | ||
955 | /* Cancels LOOP and all its subloops. */ | |
956 | void | |
d329e058 | 957 | cancel_loop_tree (struct loops *loops, struct loop *loop) |
3d436d2a ZD |
958 | { |
959 | while (loop->inner) | |
960 | cancel_loop_tree (loops, loop->inner); | |
961 | cancel_loop (loops, loop); | |
962 | } | |
963 | ||
e0bb17a8 KH |
964 | /* Checks that LOOPS are all right: |
965 | -- sizes of loops are all right | |
2ecfd709 ZD |
966 | -- results of get_loop_body really belong to the loop |
967 | -- loop header have just single entry edge and single latch edge | |
968 | -- loop latches have only single successor that is header of their loop | |
3d436d2a | 969 | -- irreducible loops are correctly marked |
2ecfd709 ZD |
970 | */ |
971 | void | |
d329e058 | 972 | verify_loop_structure (struct loops *loops) |
2ecfd709 | 973 | { |
3d436d2a ZD |
974 | unsigned *sizes, i, j; |
975 | sbitmap irreds; | |
2ecfd709 ZD |
976 | basic_block *bbs, bb; |
977 | struct loop *loop; | |
978 | int err = 0; | |
35b07080 | 979 | edge e; |
2ecfd709 ZD |
980 | |
981 | /* Check sizes. */ | |
5ed6ace5 | 982 | sizes = XCNEWVEC (unsigned, loops->num); |
2ecfd709 ZD |
983 | sizes[0] = 2; |
984 | ||
985 | FOR_EACH_BB (bb) | |
986 | for (loop = bb->loop_father; loop; loop = loop->outer) | |
987 | sizes[loop->num]++; | |
988 | ||
989 | for (i = 0; i < loops->num; i++) | |
990 | { | |
991 | if (!loops->parray[i]) | |
c22cacf3 | 992 | continue; |
2ecfd709 ZD |
993 | |
994 | if (loops->parray[i]->num_nodes != sizes[i]) | |
995 | { | |
ab532386 | 996 | error ("size of loop %d should be %d, not %d", |
2ecfd709 ZD |
997 | i, sizes[i], loops->parray[i]->num_nodes); |
998 | err = 1; | |
999 | } | |
1000 | } | |
1001 | ||
2ecfd709 ZD |
1002 | /* Check get_loop_body. */ |
1003 | for (i = 1; i < loops->num; i++) | |
1004 | { | |
1005 | loop = loops->parray[i]; | |
1006 | if (!loop) | |
1007 | continue; | |
1008 | bbs = get_loop_body (loop); | |
1009 | ||
1010 | for (j = 0; j < loop->num_nodes; j++) | |
1011 | if (!flow_bb_inside_loop_p (loop, bbs[j])) | |
1012 | { | |
ab532386 | 1013 | error ("bb %d do not belong to loop %d", |
2ecfd709 ZD |
1014 | bbs[j]->index, i); |
1015 | err = 1; | |
1016 | } | |
1017 | free (bbs); | |
1018 | } | |
1019 | ||
1020 | /* Check headers and latches. */ | |
1021 | for (i = 1; i < loops->num; i++) | |
1022 | { | |
1023 | loop = loops->parray[i]; | |
1024 | if (!loop) | |
1025 | continue; | |
1026 | ||
3d436d2a | 1027 | if ((loops->state & LOOPS_HAVE_PREHEADERS) |
628f6a4e | 1028 | && EDGE_COUNT (loop->header->preds) != 2) |
2ecfd709 | 1029 | { |
ab532386 | 1030 | error ("loop %d's header does not have exactly 2 entries", i); |
2ecfd709 ZD |
1031 | err = 1; |
1032 | } | |
3d436d2a | 1033 | if (loops->state & LOOPS_HAVE_SIMPLE_LATCHES) |
2ecfd709 | 1034 | { |
c5cbcccf | 1035 | if (!single_succ_p (loop->latch)) |
2ecfd709 | 1036 | { |
ab532386 | 1037 | error ("loop %d's latch does not have exactly 1 successor", i); |
2ecfd709 ZD |
1038 | err = 1; |
1039 | } | |
c5cbcccf | 1040 | if (single_succ (loop->latch) != loop->header) |
2ecfd709 | 1041 | { |
ab532386 | 1042 | error ("loop %d's latch does not have header as successor", i); |
2ecfd709 ZD |
1043 | err = 1; |
1044 | } | |
1045 | if (loop->latch->loop_father != loop) | |
1046 | { | |
ab532386 | 1047 | error ("loop %d's latch does not belong directly to it", i); |
2ecfd709 ZD |
1048 | err = 1; |
1049 | } | |
1050 | } | |
1051 | if (loop->header->loop_father != loop) | |
1052 | { | |
ab532386 | 1053 | error ("loop %d's header does not belong directly to it", i); |
2ecfd709 ZD |
1054 | err = 1; |
1055 | } | |
35b07080 ZD |
1056 | if ((loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) |
1057 | && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP)) | |
1058 | { | |
ab532386 | 1059 | error ("loop %d's latch is marked as part of irreducible region", i); |
35b07080 ZD |
1060 | err = 1; |
1061 | } | |
2ecfd709 ZD |
1062 | } |
1063 | ||
3d436d2a ZD |
1064 | /* Check irreducible loops. */ |
1065 | if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS) | |
1066 | { | |
1067 | /* Record old info. */ | |
1068 | irreds = sbitmap_alloc (last_basic_block); | |
1069 | FOR_EACH_BB (bb) | |
35b07080 | 1070 | { |
628f6a4e | 1071 | edge_iterator ei; |
35b07080 ZD |
1072 | if (bb->flags & BB_IRREDUCIBLE_LOOP) |
1073 | SET_BIT (irreds, bb->index); | |
1074 | else | |
1075 | RESET_BIT (irreds, bb->index); | |
628f6a4e | 1076 | FOR_EACH_EDGE (e, ei, bb->succs) |
35b07080 | 1077 | if (e->flags & EDGE_IRREDUCIBLE_LOOP) |
d329e058 | 1078 | e->flags |= EDGE_ALL_FLAGS + 1; |
35b07080 | 1079 | } |
3d436d2a ZD |
1080 | |
1081 | /* Recount it. */ | |
1082 | mark_irreducible_loops (loops); | |
1083 | ||
1084 | /* Compare. */ | |
1085 | FOR_EACH_BB (bb) | |
1086 | { | |
628f6a4e BE |
1087 | edge_iterator ei; |
1088 | ||
3d436d2a ZD |
1089 | if ((bb->flags & BB_IRREDUCIBLE_LOOP) |
1090 | && !TEST_BIT (irreds, bb->index)) | |
1091 | { | |
ab532386 | 1092 | error ("basic block %d should be marked irreducible", bb->index); |
3d436d2a ZD |
1093 | err = 1; |
1094 | } | |
1095 | else if (!(bb->flags & BB_IRREDUCIBLE_LOOP) | |
1096 | && TEST_BIT (irreds, bb->index)) | |
1097 | { | |
ab532386 | 1098 | error ("basic block %d should not be marked irreducible", bb->index); |
3d436d2a ZD |
1099 | err = 1; |
1100 | } | |
628f6a4e | 1101 | FOR_EACH_EDGE (e, ei, bb->succs) |
35b07080 ZD |
1102 | { |
1103 | if ((e->flags & EDGE_IRREDUCIBLE_LOOP) | |
1104 | && !(e->flags & (EDGE_ALL_FLAGS + 1))) | |
1105 | { | |
ab532386 | 1106 | error ("edge from %d to %d should be marked irreducible", |
35b07080 ZD |
1107 | e->src->index, e->dest->index); |
1108 | err = 1; | |
1109 | } | |
1110 | else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP) | |
1111 | && (e->flags & (EDGE_ALL_FLAGS + 1))) | |
1112 | { | |
ab532386 | 1113 | error ("edge from %d to %d should not be marked irreducible", |
35b07080 ZD |
1114 | e->src->index, e->dest->index); |
1115 | err = 1; | |
1116 | } | |
1117 | e->flags &= ~(EDGE_ALL_FLAGS + 1); | |
1118 | } | |
3d436d2a ZD |
1119 | } |
1120 | free (irreds); | |
1121 | } | |
1122 | ||
82b85a85 ZD |
1123 | /* Check the single_exit. */ |
1124 | if (loops->state & LOOPS_HAVE_MARKED_SINGLE_EXITS) | |
1125 | { | |
1126 | memset (sizes, 0, sizeof (unsigned) * loops->num); | |
1127 | FOR_EACH_BB (bb) | |
1128 | { | |
628f6a4e | 1129 | edge_iterator ei; |
82b85a85 ZD |
1130 | if (bb->loop_father == loops->tree_root) |
1131 | continue; | |
628f6a4e | 1132 | FOR_EACH_EDGE (e, ei, bb->succs) |
82b85a85 ZD |
1133 | { |
1134 | if (e->dest == EXIT_BLOCK_PTR) | |
1135 | continue; | |
1136 | ||
1137 | if (flow_bb_inside_loop_p (bb->loop_father, e->dest)) | |
1138 | continue; | |
1139 | ||
1140 | for (loop = bb->loop_father; | |
1141 | loop != e->dest->loop_father; | |
1142 | loop = loop->outer) | |
1143 | { | |
1144 | sizes[loop->num]++; | |
ac8f6c69 ZD |
1145 | if (single_exit (loop) |
1146 | && single_exit (loop) != e) | |
82b85a85 | 1147 | { |
ab532386 | 1148 | error ("wrong single exit %d->%d recorded for loop %d", |
ac8f6c69 ZD |
1149 | single_exit (loop)->src->index, |
1150 | single_exit (loop)->dest->index, | |
82b85a85 | 1151 | loop->num); |
ab532386 | 1152 | error ("right exit is %d->%d", |
82b85a85 ZD |
1153 | e->src->index, e->dest->index); |
1154 | err = 1; | |
1155 | } | |
1156 | } | |
1157 | } | |
1158 | } | |
1159 | ||
1160 | for (i = 1; i < loops->num; i++) | |
1161 | { | |
1162 | loop = loops->parray[i]; | |
1163 | if (!loop) | |
1164 | continue; | |
1165 | ||
1166 | if (sizes[i] == 1 | |
ac8f6c69 | 1167 | && !single_exit (loop)) |
82b85a85 | 1168 | { |
ab532386 | 1169 | error ("single exit not recorded for loop %d", loop->num); |
82b85a85 ZD |
1170 | err = 1; |
1171 | } | |
1172 | ||
1173 | if (sizes[i] != 1 | |
ac8f6c69 | 1174 | && single_exit (loop)) |
82b85a85 | 1175 | { |
ab532386 | 1176 | error ("loop %d should not have single exit (%d -> %d)", |
82b85a85 | 1177 | loop->num, |
ac8f6c69 ZD |
1178 | single_exit (loop)->src->index, |
1179 | single_exit (loop)->dest->index); | |
82b85a85 ZD |
1180 | err = 1; |
1181 | } | |
1182 | } | |
1183 | } | |
1184 | ||
341c100f | 1185 | gcc_assert (!err); |
82b85a85 ZD |
1186 | |
1187 | free (sizes); | |
2ecfd709 ZD |
1188 | } |
1189 | ||
1190 | /* Returns latch edge of LOOP. */ | |
1191 | edge | |
d329e058 | 1192 | loop_latch_edge (const struct loop *loop) |
2ecfd709 | 1193 | { |
9ff3d2de | 1194 | return find_edge (loop->latch, loop->header); |
402209ff | 1195 | } |
2ecfd709 ZD |
1196 | |
1197 | /* Returns preheader edge of LOOP. */ | |
1198 | edge | |
d329e058 | 1199 | loop_preheader_edge (const struct loop *loop) |
2ecfd709 ZD |
1200 | { |
1201 | edge e; | |
628f6a4e | 1202 | edge_iterator ei; |
2ecfd709 | 1203 | |
628f6a4e BE |
1204 | FOR_EACH_EDGE (e, ei, loop->header->preds) |
1205 | if (e->src != loop->latch) | |
1206 | break; | |
2ecfd709 ZD |
1207 | |
1208 | return e; | |
1209 | } | |
70388d94 ZD |
1210 | |
1211 | /* Returns true if E is an exit of LOOP. */ | |
1212 | ||
1213 | bool | |
1214 | loop_exit_edge_p (const struct loop *loop, edge e) | |
1215 | { | |
1216 | return (flow_bb_inside_loop_p (loop, e->src) | |
1217 | && !flow_bb_inside_loop_p (loop, e->dest)); | |
1218 | } | |
ac8f6c69 ZD |
1219 | |
1220 | /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit | |
1221 | or more than one exit. */ | |
1222 | ||
1223 | edge | |
1224 | single_exit (const struct loop *loop) | |
1225 | { | |
1226 | return loop->single_exit_; | |
1227 | } | |
1228 | ||
1229 | /* Records E as a single exit edge of LOOP. */ | |
1230 | ||
1231 | void | |
1232 | set_single_exit (struct loop *loop, edge e) | |
1233 | { | |
1234 | loop->single_exit_ = e; | |
1235 | } |