Remove trailing white spaces.
[gcc.git] / gcc / cfgloop.c
1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008
3 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "hard-reg-set.h"
27 #include "obstack.h"
28 #include "function.h"
29 #include "basic-block.h"
30 #include "toplev.h"
31 #include "cfgloop.h"
32 #include "flags.h"
33 #include "tree.h"
34 #include "tree-flow.h"
35 #include "pointer-set.h"
36 #include "output.h"
37 #include "ggc.h"
38
39 static void flow_loops_cfg_dump (FILE *);
40 \f
41 /* Dump loop related CFG information. */
42
43 static void
44 flow_loops_cfg_dump (FILE *file)
45 {
46 basic_block bb;
47
48 if (!file)
49 return;
50
51 FOR_EACH_BB (bb)
52 {
53 edge succ;
54 edge_iterator ei;
55
56 fprintf (file, ";; %d succs { ", bb->index);
57 FOR_EACH_EDGE (succ, ei, bb->succs)
58 fprintf (file, "%d ", succ->dest->index);
59 fprintf (file, "}\n");
60 }
61 }
62
63 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
64
65 bool
66 flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
67 {
68 unsigned odepth = loop_depth (outer);
69
70 return (loop_depth (loop) > odepth
71 && VEC_index (loop_p, loop->superloops, odepth) == outer);
72 }
73
74 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
75 loops within LOOP. */
76
77 struct loop *
78 superloop_at_depth (struct loop *loop, unsigned depth)
79 {
80 unsigned ldepth = loop_depth (loop);
81
82 gcc_assert (depth <= ldepth);
83
84 if (depth == ldepth)
85 return loop;
86
87 return VEC_index (loop_p, loop->superloops, depth);
88 }
89
90 /* Returns the list of the latch edges of LOOP. */
91
92 static VEC (edge, heap) *
93 get_loop_latch_edges (const struct loop *loop)
94 {
95 edge_iterator ei;
96 edge e;
97 VEC (edge, heap) *ret = NULL;
98
99 FOR_EACH_EDGE (e, ei, loop->header->preds)
100 {
101 if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header))
102 VEC_safe_push (edge, heap, ret, e);
103 }
104
105 return ret;
106 }
107
108 /* Dump the loop information specified by LOOP to the stream FILE
109 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
110
111 void
112 flow_loop_dump (const struct loop *loop, FILE *file,
113 void (*loop_dump_aux) (const struct loop *, FILE *, int),
114 int verbose)
115 {
116 basic_block *bbs;
117 unsigned i;
118 VEC (edge, heap) *latches;
119 edge e;
120
121 if (! loop || ! loop->header)
122 return;
123
124 fprintf (file, ";;\n;; Loop %d\n", loop->num);
125
126 fprintf (file, ";; header %d, ", loop->header->index);
127 if (loop->latch)
128 fprintf (file, "latch %d\n", loop->latch->index);
129 else
130 {
131 fprintf (file, "multiple latches:");
132 latches = get_loop_latch_edges (loop);
133 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
134 fprintf (file, " %d", e->src->index);
135 VEC_free (edge, heap, latches);
136 fprintf (file, "\n");
137 }
138
139 fprintf (file, ";; depth %d, outer %ld\n",
140 loop_depth (loop), (long) (loop_outer (loop)
141 ? loop_outer (loop)->num : -1));
142
143 fprintf (file, ";; nodes:");
144 bbs = get_loop_body (loop);
145 for (i = 0; i < loop->num_nodes; i++)
146 fprintf (file, " %d", bbs[i]->index);
147 free (bbs);
148 fprintf (file, "\n");
149
150 if (loop_dump_aux)
151 loop_dump_aux (loop, file, verbose);
152 }
153
154 /* Dump the loop information about loops to the stream FILE,
155 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
156
157 void
158 flow_loops_dump (FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
159 {
160 loop_iterator li;
161 struct loop *loop;
162
163 if (!current_loops || ! file)
164 return;
165
166 fprintf (file, ";; %d loops found\n", number_of_loops ());
167
168 FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
169 {
170 flow_loop_dump (loop, file, loop_dump_aux, verbose);
171 }
172
173 if (verbose)
174 flow_loops_cfg_dump (file);
175 }
176
177 /* Free data allocated for LOOP. */
178
179 void
180 flow_loop_free (struct loop *loop)
181 {
182 struct loop_exit *exit, *next;
183
184 VEC_free (loop_p, gc, loop->superloops);
185
186 /* Break the list of the loop exit records. They will be freed when the
187 corresponding edge is rescanned or removed, and this avoids
188 accessing the (already released) head of the list stored in the
189 loop structure. */
190 for (exit = loop->exits->next; exit != loop->exits; exit = next)
191 {
192 next = exit->next;
193 exit->next = exit;
194 exit->prev = exit;
195 }
196
197 ggc_free (loop->exits);
198 ggc_free (loop);
199 }
200
201 /* Free all the memory allocated for LOOPS. */
202
203 void
204 flow_loops_free (struct loops *loops)
205 {
206 if (loops->larray)
207 {
208 unsigned i;
209 loop_p loop;
210
211 /* Free the loop descriptors. */
212 for (i = 0; VEC_iterate (loop_p, loops->larray, i, loop); i++)
213 {
214 if (!loop)
215 continue;
216
217 flow_loop_free (loop);
218 }
219
220 VEC_free (loop_p, gc, loops->larray);
221 }
222 }
223
224 /* Find the nodes contained within the LOOP with header HEADER.
225 Return the number of nodes within the loop. */
226
227 int
228 flow_loop_nodes_find (basic_block header, struct loop *loop)
229 {
230 VEC (basic_block, heap) *stack = NULL;
231 int num_nodes = 1;
232 edge latch;
233 edge_iterator latch_ei;
234 unsigned depth = loop_depth (loop);
235
236 header->loop_father = loop;
237 header->loop_depth = depth;
238
239 FOR_EACH_EDGE (latch, latch_ei, loop->header->preds)
240 {
241 if (latch->src->loop_father == loop
242 || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header))
243 continue;
244
245 num_nodes++;
246 VEC_safe_push (basic_block, heap, stack, latch->src);
247 latch->src->loop_father = loop;
248 latch->src->loop_depth = depth;
249
250 while (!VEC_empty (basic_block, stack))
251 {
252 basic_block node;
253 edge e;
254 edge_iterator ei;
255
256 node = VEC_pop (basic_block, stack);
257
258 FOR_EACH_EDGE (e, ei, node->preds)
259 {
260 basic_block ancestor = e->src;
261
262 if (ancestor->loop_father != loop)
263 {
264 ancestor->loop_father = loop;
265 ancestor->loop_depth = depth;
266 num_nodes++;
267 VEC_safe_push (basic_block, heap, stack, ancestor);
268 }
269 }
270 }
271 }
272 VEC_free (basic_block, heap, stack);
273
274 return num_nodes;
275 }
276
277 /* Records the vector of superloops of the loop LOOP, whose immediate
278 superloop is FATHER. */
279
280 static void
281 establish_preds (struct loop *loop, struct loop *father)
282 {
283 loop_p ploop;
284 unsigned depth = loop_depth (father) + 1;
285 unsigned i;
286
287 VEC_truncate (loop_p, loop->superloops, 0);
288 VEC_reserve (loop_p, gc, loop->superloops, depth);
289 for (i = 0; VEC_iterate (loop_p, father->superloops, i, ploop); i++)
290 VEC_quick_push (loop_p, loop->superloops, ploop);
291 VEC_quick_push (loop_p, loop->superloops, father);
292
293 for (ploop = loop->inner; ploop; ploop = ploop->next)
294 establish_preds (ploop, loop);
295 }
296
297 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
298 added loop. If LOOP has some children, take care of that their
299 pred field will be initialized correctly. */
300
301 void
302 flow_loop_tree_node_add (struct loop *father, struct loop *loop)
303 {
304 loop->next = father->inner;
305 father->inner = loop;
306
307 establish_preds (loop, father);
308 }
309
310 /* Remove LOOP from the loop hierarchy tree. */
311
312 void
313 flow_loop_tree_node_remove (struct loop *loop)
314 {
315 struct loop *prev, *father;
316
317 father = loop_outer (loop);
318
319 /* Remove loop from the list of sons. */
320 if (father->inner == loop)
321 father->inner = loop->next;
322 else
323 {
324 for (prev = father->inner; prev->next != loop; prev = prev->next)
325 continue;
326 prev->next = loop->next;
327 }
328
329 VEC_truncate (loop_p, loop->superloops, 0);
330 }
331
332 /* Allocates and returns new loop structure. */
333
334 struct loop *
335 alloc_loop (void)
336 {
337 struct loop *loop = GGC_CNEW (struct loop);
338
339 loop->exits = GGC_CNEW (struct loop_exit);
340 loop->exits->next = loop->exits->prev = loop->exits;
341 loop->can_be_parallel = false;
342 loop->single_iv = NULL_TREE;
343
344 return loop;
345 }
346
347 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
348 (including the root of the loop tree). */
349
350 static void
351 init_loops_structure (struct loops *loops, unsigned num_loops)
352 {
353 struct loop *root;
354
355 memset (loops, 0, sizeof *loops);
356 loops->larray = VEC_alloc (loop_p, gc, num_loops);
357
358 /* Dummy loop containing whole function. */
359 root = alloc_loop ();
360 root->num_nodes = n_basic_blocks;
361 root->latch = EXIT_BLOCK_PTR;
362 root->header = ENTRY_BLOCK_PTR;
363 ENTRY_BLOCK_PTR->loop_father = root;
364 EXIT_BLOCK_PTR->loop_father = root;
365
366 VEC_quick_push (loop_p, loops->larray, root);
367 loops->tree_root = root;
368 }
369
370 /* Find all the natural loops in the function and save in LOOPS structure and
371 recalculate loop_depth information in basic block structures.
372 Return the number of natural loops found. */
373
374 int
375 flow_loops_find (struct loops *loops)
376 {
377 int b;
378 int num_loops;
379 edge e;
380 sbitmap headers;
381 int *dfs_order;
382 int *rc_order;
383 basic_block header;
384 basic_block bb;
385
386 /* Ensure that the dominators are computed. */
387 calculate_dominance_info (CDI_DOMINATORS);
388
389 /* Taking care of this degenerate case makes the rest of
390 this code simpler. */
391 if (n_basic_blocks == NUM_FIXED_BLOCKS)
392 {
393 init_loops_structure (loops, 1);
394 return 1;
395 }
396
397 dfs_order = NULL;
398 rc_order = NULL;
399
400 /* Count the number of loop headers. This should be the
401 same as the number of natural loops. */
402 headers = sbitmap_alloc (last_basic_block);
403 sbitmap_zero (headers);
404
405 num_loops = 0;
406 FOR_EACH_BB (header)
407 {
408 edge_iterator ei;
409
410 header->loop_depth = 0;
411
412 /* If we have an abnormal predecessor, do not consider the
413 loop (not worth the problems). */
414 FOR_EACH_EDGE (e, ei, header->preds)
415 if (e->flags & EDGE_ABNORMAL)
416 break;
417 if (e)
418 continue;
419
420 FOR_EACH_EDGE (e, ei, header->preds)
421 {
422 basic_block latch = e->src;
423
424 gcc_assert (!(e->flags & EDGE_ABNORMAL));
425
426 /* Look for back edges where a predecessor is dominated
427 by this block. A natural loop has a single entry
428 node (header) that dominates all the nodes in the
429 loop. It also has single back edge to the header
430 from a latch node. */
431 if (latch != ENTRY_BLOCK_PTR
432 && dominated_by_p (CDI_DOMINATORS, latch, header))
433 {
434 /* Shared headers should be eliminated by now. */
435 SET_BIT (headers, header->index);
436 num_loops++;
437 }
438 }
439 }
440
441 /* Allocate loop structures. */
442 init_loops_structure (loops, num_loops + 1);
443
444 /* Find and record information about all the natural loops
445 in the CFG. */
446 FOR_EACH_BB (bb)
447 bb->loop_father = loops->tree_root;
448
449 if (num_loops)
450 {
451 /* Compute depth first search order of the CFG so that outer
452 natural loops will be found before inner natural loops. */
453 dfs_order = XNEWVEC (int, n_basic_blocks);
454 rc_order = XNEWVEC (int, n_basic_blocks);
455 pre_and_rev_post_order_compute (dfs_order, rc_order, false);
456
457 num_loops = 1;
458
459 for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++)
460 {
461 struct loop *loop;
462 edge_iterator ei;
463
464 /* Search the nodes of the CFG in reverse completion order
465 so that we can find outer loops first. */
466 if (!TEST_BIT (headers, rc_order[b]))
467 continue;
468
469 header = BASIC_BLOCK (rc_order[b]);
470
471 loop = alloc_loop ();
472 VEC_quick_push (loop_p, loops->larray, loop);
473
474 loop->header = header;
475 loop->num = num_loops;
476 num_loops++;
477
478 flow_loop_tree_node_add (header->loop_father, loop);
479 loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
480
481 /* Look for the latch for this header block, if it has just a
482 single one. */
483 FOR_EACH_EDGE (e, ei, header->preds)
484 {
485 basic_block latch = e->src;
486
487 if (flow_bb_inside_loop_p (loop, latch))
488 {
489 if (loop->latch != NULL)
490 {
491 /* More than one latch edge. */
492 loop->latch = NULL;
493 break;
494 }
495 loop->latch = latch;
496 }
497 }
498 }
499
500 free (dfs_order);
501 free (rc_order);
502 }
503
504 sbitmap_free (headers);
505
506 loops->exits = NULL;
507 return VEC_length (loop_p, loops->larray);
508 }
509
510 /* Ratio of frequencies of edges so that one of more latch edges is
511 considered to belong to inner loop with same header. */
512 #define HEAVY_EDGE_RATIO 8
513
514 /* Minimum number of samples for that we apply
515 find_subloop_latch_edge_by_profile heuristics. */
516 #define HEAVY_EDGE_MIN_SAMPLES 10
517
518 /* If the profile info is available, finds an edge in LATCHES that much more
519 frequent than the remaining edges. Returns such an edge, or NULL if we do
520 not find one.
521
522 We do not use guessed profile here, only the measured one. The guessed
523 profile is usually too flat and unreliable for this (and it is mostly based
524 on the loop structure of the program, so it does not make much sense to
525 derive the loop structure from it). */
526
527 static edge
528 find_subloop_latch_edge_by_profile (VEC (edge, heap) *latches)
529 {
530 unsigned i;
531 edge e, me = NULL;
532 gcov_type mcount = 0, tcount = 0;
533
534 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
535 {
536 if (e->count > mcount)
537 {
538 me = e;
539 mcount = e->count;
540 }
541 tcount += e->count;
542 }
543
544 if (tcount < HEAVY_EDGE_MIN_SAMPLES
545 || (tcount - mcount) * HEAVY_EDGE_RATIO > tcount)
546 return NULL;
547
548 if (dump_file)
549 fprintf (dump_file,
550 "Found latch edge %d -> %d using profile information.\n",
551 me->src->index, me->dest->index);
552 return me;
553 }
554
555 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
556 on the structure of induction variables. Returns this edge, or NULL if we
557 do not find any.
558
559 We are quite conservative, and look just for an obvious simple innermost
560 loop (which is the case where we would lose the most performance by not
561 disambiguating the loop). More precisely, we look for the following
562 situation: The source of the chosen latch edge dominates sources of all
563 the other latch edges. Additionally, the header does not contain a phi node
564 such that the argument from the chosen edge is equal to the argument from
565 another edge. */
566
567 static edge
568 find_subloop_latch_edge_by_ivs (struct loop *loop ATTRIBUTE_UNUSED, VEC (edge, heap) *latches)
569 {
570 edge e, latch = VEC_index (edge, latches, 0);
571 unsigned i;
572 gimple phi;
573 gimple_stmt_iterator psi;
574 tree lop;
575 basic_block bb;
576
577 /* Find the candidate for the latch edge. */
578 for (i = 1; VEC_iterate (edge, latches, i, e); i++)
579 if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src))
580 latch = e;
581
582 /* Verify that it dominates all the latch edges. */
583 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
584 if (!dominated_by_p (CDI_DOMINATORS, e->src, latch->src))
585 return NULL;
586
587 /* Check for a phi node that would deny that this is a latch edge of
588 a subloop. */
589 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
590 {
591 phi = gsi_stmt (psi);
592 lop = PHI_ARG_DEF_FROM_EDGE (phi, latch);
593
594 /* Ignore the values that are not changed inside the subloop. */
595 if (TREE_CODE (lop) != SSA_NAME
596 || SSA_NAME_DEF_STMT (lop) == phi)
597 continue;
598 bb = gimple_bb (SSA_NAME_DEF_STMT (lop));
599 if (!bb || !flow_bb_inside_loop_p (loop, bb))
600 continue;
601
602 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
603 if (e != latch
604 && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop)
605 return NULL;
606 }
607
608 if (dump_file)
609 fprintf (dump_file,
610 "Found latch edge %d -> %d using iv structure.\n",
611 latch->src->index, latch->dest->index);
612 return latch;
613 }
614
615 /* If we can determine that one of the several latch edges of LOOP behaves
616 as a latch edge of a separate subloop, returns this edge. Otherwise
617 returns NULL. */
618
619 static edge
620 find_subloop_latch_edge (struct loop *loop)
621 {
622 VEC (edge, heap) *latches = get_loop_latch_edges (loop);
623 edge latch = NULL;
624
625 if (VEC_length (edge, latches) > 1)
626 {
627 latch = find_subloop_latch_edge_by_profile (latches);
628
629 if (!latch
630 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
631 should use cfghook for this, but it is hard to imagine it would
632 be useful elsewhere. */
633 && current_ir_type () == IR_GIMPLE)
634 latch = find_subloop_latch_edge_by_ivs (loop, latches);
635 }
636
637 VEC_free (edge, heap, latches);
638 return latch;
639 }
640
641 /* Callback for make_forwarder_block. Returns true if the edge E is marked
642 in the set MFB_REIS_SET. */
643
644 static struct pointer_set_t *mfb_reis_set;
645 static bool
646 mfb_redirect_edges_in_set (edge e)
647 {
648 return pointer_set_contains (mfb_reis_set, e);
649 }
650
651 /* Creates a subloop of LOOP with latch edge LATCH. */
652
653 static void
654 form_subloop (struct loop *loop, edge latch)
655 {
656 edge_iterator ei;
657 edge e, new_entry;
658 struct loop *new_loop;
659
660 mfb_reis_set = pointer_set_create ();
661 FOR_EACH_EDGE (e, ei, loop->header->preds)
662 {
663 if (e != latch)
664 pointer_set_insert (mfb_reis_set, e);
665 }
666 new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
667 NULL);
668 pointer_set_destroy (mfb_reis_set);
669
670 loop->header = new_entry->src;
671
672 /* Find the blocks and subloops that belong to the new loop, and add it to
673 the appropriate place in the loop tree. */
674 new_loop = alloc_loop ();
675 new_loop->header = new_entry->dest;
676 new_loop->latch = latch->src;
677 add_loop (new_loop, loop);
678 }
679
680 /* Make all the latch edges of LOOP to go to a single forwarder block --
681 a new latch of LOOP. */
682
683 static void
684 merge_latch_edges (struct loop *loop)
685 {
686 VEC (edge, heap) *latches = get_loop_latch_edges (loop);
687 edge latch, e;
688 unsigned i;
689
690 gcc_assert (VEC_length (edge, latches) > 0);
691
692 if (VEC_length (edge, latches) == 1)
693 loop->latch = VEC_index (edge, latches, 0)->src;
694 else
695 {
696 if (dump_file)
697 fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num);
698
699 mfb_reis_set = pointer_set_create ();
700 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
701 pointer_set_insert (mfb_reis_set, e);
702 latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
703 NULL);
704 pointer_set_destroy (mfb_reis_set);
705
706 loop->header = latch->dest;
707 loop->latch = latch->src;
708 }
709
710 VEC_free (edge, heap, latches);
711 }
712
713 /* LOOP may have several latch edges. Transform it into (possibly several)
714 loops with single latch edge. */
715
716 static void
717 disambiguate_multiple_latches (struct loop *loop)
718 {
719 edge e;
720
721 /* We eliminate the multiple latches by splitting the header to the forwarder
722 block F and the rest R, and redirecting the edges. There are two cases:
723
724 1) If there is a latch edge E that corresponds to a subloop (we guess
725 that based on profile -- if it is taken much more often than the
726 remaining edges; and on trees, using the information about induction
727 variables of the loops), we redirect E to R, all the remaining edges to
728 F, then rescan the loops and try again for the outer loop.
729 2) If there is no such edge, we redirect all latch edges to F, and the
730 entry edges to R, thus making F the single latch of the loop. */
731
732 if (dump_file)
733 fprintf (dump_file, "Disambiguating loop %d with multiple latches\n",
734 loop->num);
735
736 /* During latch merging, we may need to redirect the entry edges to a new
737 block. This would cause problems if the entry edge was the one from the
738 entry block. To avoid having to handle this case specially, split
739 such entry edge. */
740 e = find_edge (ENTRY_BLOCK_PTR, loop->header);
741 if (e)
742 split_edge (e);
743
744 while (1)
745 {
746 e = find_subloop_latch_edge (loop);
747 if (!e)
748 break;
749
750 form_subloop (loop, e);
751 }
752
753 merge_latch_edges (loop);
754 }
755
756 /* Split loops with multiple latch edges. */
757
758 void
759 disambiguate_loops_with_multiple_latches (void)
760 {
761 loop_iterator li;
762 struct loop *loop;
763
764 FOR_EACH_LOOP (li, loop, 0)
765 {
766 if (!loop->latch)
767 disambiguate_multiple_latches (loop);
768 }
769 }
770
771 /* Return nonzero if basic block BB belongs to LOOP. */
772 bool
773 flow_bb_inside_loop_p (const struct loop *loop, const_basic_block bb)
774 {
775 struct loop *source_loop;
776
777 if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
778 return 0;
779
780 source_loop = bb->loop_father;
781 return loop == source_loop || flow_loop_nested_p (loop, source_loop);
782 }
783
784 /* Enumeration predicate for get_loop_body_with_size. */
785 static bool
786 glb_enum_p (const_basic_block bb, const void *glb_loop)
787 {
788 const struct loop *const loop = (const struct loop *) glb_loop;
789 return (bb != loop->header
790 && dominated_by_p (CDI_DOMINATORS, bb, loop->header));
791 }
792
793 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
794 order against direction of edges from latch. Specially, if
795 header != latch, latch is the 1-st block. LOOP cannot be the fake
796 loop tree root, and its size must be at most MAX_SIZE. The blocks
797 in the LOOP body are stored to BODY, and the size of the LOOP is
798 returned. */
799
800 unsigned
801 get_loop_body_with_size (const struct loop *loop, basic_block *body,
802 unsigned max_size)
803 {
804 return dfs_enumerate_from (loop->header, 1, glb_enum_p,
805 body, max_size, loop);
806 }
807
808 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
809 order against direction of edges from latch. Specially, if
810 header != latch, latch is the 1-st block. */
811
812 basic_block *
813 get_loop_body (const struct loop *loop)
814 {
815 basic_block *body, bb;
816 unsigned tv = 0;
817
818 gcc_assert (loop->num_nodes);
819
820 body = XCNEWVEC (basic_block, loop->num_nodes);
821
822 if (loop->latch == EXIT_BLOCK_PTR)
823 {
824 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
825 special-case the fake loop that contains the whole function. */
826 gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks);
827 body[tv++] = loop->header;
828 body[tv++] = EXIT_BLOCK_PTR;
829 FOR_EACH_BB (bb)
830 body[tv++] = bb;
831 }
832 else
833 tv = get_loop_body_with_size (loop, body, loop->num_nodes);
834
835 gcc_assert (tv == loop->num_nodes);
836 return body;
837 }
838
839 /* Fills dominance descendants inside LOOP of the basic block BB into
840 array TOVISIT from index *TV. */
841
842 static void
843 fill_sons_in_loop (const struct loop *loop, basic_block bb,
844 basic_block *tovisit, int *tv)
845 {
846 basic_block son, postpone = NULL;
847
848 tovisit[(*tv)++] = bb;
849 for (son = first_dom_son (CDI_DOMINATORS, bb);
850 son;
851 son = next_dom_son (CDI_DOMINATORS, son))
852 {
853 if (!flow_bb_inside_loop_p (loop, son))
854 continue;
855
856 if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
857 {
858 postpone = son;
859 continue;
860 }
861 fill_sons_in_loop (loop, son, tovisit, tv);
862 }
863
864 if (postpone)
865 fill_sons_in_loop (loop, postpone, tovisit, tv);
866 }
867
868 /* Gets body of a LOOP (that must be different from the outermost loop)
869 sorted by dominance relation. Additionally, if a basic block s dominates
870 the latch, then only blocks dominated by s are be after it. */
871
872 basic_block *
873 get_loop_body_in_dom_order (const struct loop *loop)
874 {
875 basic_block *tovisit;
876 int tv;
877
878 gcc_assert (loop->num_nodes);
879
880 tovisit = XCNEWVEC (basic_block, loop->num_nodes);
881
882 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
883
884 tv = 0;
885 fill_sons_in_loop (loop, loop->header, tovisit, &tv);
886
887 gcc_assert (tv == (int) loop->num_nodes);
888
889 return tovisit;
890 }
891
892 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
893
894 basic_block *
895 get_loop_body_in_custom_order (const struct loop *loop,
896 int (*bb_comparator) (const void *, const void *))
897 {
898 basic_block *bbs = get_loop_body (loop);
899
900 qsort (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator);
901
902 return bbs;
903 }
904
905 /* Get body of a LOOP in breadth first sort order. */
906
907 basic_block *
908 get_loop_body_in_bfs_order (const struct loop *loop)
909 {
910 basic_block *blocks;
911 basic_block bb;
912 bitmap visited;
913 unsigned int i = 0;
914 unsigned int vc = 1;
915
916 gcc_assert (loop->num_nodes);
917 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
918
919 blocks = XCNEWVEC (basic_block, loop->num_nodes);
920 visited = BITMAP_ALLOC (NULL);
921
922 bb = loop->header;
923 while (i < loop->num_nodes)
924 {
925 edge e;
926 edge_iterator ei;
927
928 if (!bitmap_bit_p (visited, bb->index))
929 {
930 /* This basic block is now visited */
931 bitmap_set_bit (visited, bb->index);
932 blocks[i++] = bb;
933 }
934
935 FOR_EACH_EDGE (e, ei, bb->succs)
936 {
937 if (flow_bb_inside_loop_p (loop, e->dest))
938 {
939 if (!bitmap_bit_p (visited, e->dest->index))
940 {
941 bitmap_set_bit (visited, e->dest->index);
942 blocks[i++] = e->dest;
943 }
944 }
945 }
946
947 gcc_assert (i >= vc);
948
949 bb = blocks[vc++];
950 }
951
952 BITMAP_FREE (visited);
953 return blocks;
954 }
955
956 /* Hash function for struct loop_exit. */
957
958 static hashval_t
959 loop_exit_hash (const void *ex)
960 {
961 const struct loop_exit *const exit = (const struct loop_exit *) ex;
962
963 return htab_hash_pointer (exit->e);
964 }
965
966 /* Equality function for struct loop_exit. Compares with edge. */
967
968 static int
969 loop_exit_eq (const void *ex, const void *e)
970 {
971 const struct loop_exit *const exit = (const struct loop_exit *) ex;
972
973 return exit->e == e;
974 }
975
976 /* Frees the list of loop exit descriptions EX. */
977
978 static void
979 loop_exit_free (void *ex)
980 {
981 struct loop_exit *exit = (struct loop_exit *) ex, *next;
982
983 for (; exit; exit = next)
984 {
985 next = exit->next_e;
986
987 exit->next->prev = exit->prev;
988 exit->prev->next = exit->next;
989
990 ggc_free (exit);
991 }
992 }
993
994 /* Returns the list of records for E as an exit of a loop. */
995
996 static struct loop_exit *
997 get_exit_descriptions (edge e)
998 {
999 return (struct loop_exit *) htab_find_with_hash (current_loops->exits, e,
1000 htab_hash_pointer (e));
1001 }
1002
1003 /* Updates the lists of loop exits in that E appears.
1004 If REMOVED is true, E is being removed, and we
1005 just remove it from the lists of exits.
1006 If NEW_EDGE is true and E is not a loop exit, we
1007 do not try to remove it from loop exit lists. */
1008
1009 void
1010 rescan_loop_exit (edge e, bool new_edge, bool removed)
1011 {
1012 void **slot;
1013 struct loop_exit *exits = NULL, *exit;
1014 struct loop *aloop, *cloop;
1015
1016 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1017 return;
1018
1019 if (!removed
1020 && e->src->loop_father != NULL
1021 && e->dest->loop_father != NULL
1022 && !flow_bb_inside_loop_p (e->src->loop_father, e->dest))
1023 {
1024 cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
1025 for (aloop = e->src->loop_father;
1026 aloop != cloop;
1027 aloop = loop_outer (aloop))
1028 {
1029 exit = GGC_NEW (struct loop_exit);
1030 exit->e = e;
1031
1032 exit->next = aloop->exits->next;
1033 exit->prev = aloop->exits;
1034 exit->next->prev = exit;
1035 exit->prev->next = exit;
1036
1037 exit->next_e = exits;
1038 exits = exit;
1039 }
1040 }
1041
1042 if (!exits && new_edge)
1043 return;
1044
1045 slot = htab_find_slot_with_hash (current_loops->exits, e,
1046 htab_hash_pointer (e),
1047 exits ? INSERT : NO_INSERT);
1048 if (!slot)
1049 return;
1050
1051 if (exits)
1052 {
1053 if (*slot)
1054 loop_exit_free (*slot);
1055 *slot = exits;
1056 }
1057 else
1058 htab_clear_slot (current_loops->exits, slot);
1059 }
1060
1061 /* For each loop, record list of exit edges, and start maintaining these
1062 lists. */
1063
1064 void
1065 record_loop_exits (void)
1066 {
1067 basic_block bb;
1068 edge_iterator ei;
1069 edge e;
1070
1071 if (!current_loops)
1072 return;
1073
1074 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1075 return;
1076 loops_state_set (LOOPS_HAVE_RECORDED_EXITS);
1077
1078 gcc_assert (current_loops->exits == NULL);
1079 current_loops->exits = htab_create_alloc (2 * number_of_loops (),
1080 loop_exit_hash,
1081 loop_exit_eq,
1082 loop_exit_free,
1083 ggc_calloc, ggc_free);
1084
1085 FOR_EACH_BB (bb)
1086 {
1087 FOR_EACH_EDGE (e, ei, bb->succs)
1088 {
1089 rescan_loop_exit (e, true, false);
1090 }
1091 }
1092 }
1093
1094 /* Dumps information about the exit in *SLOT to FILE.
1095 Callback for htab_traverse. */
1096
1097 static int
1098 dump_recorded_exit (void **slot, void *file)
1099 {
1100 struct loop_exit *exit = (struct loop_exit *) *slot;
1101 unsigned n = 0;
1102 edge e = exit->e;
1103
1104 for (; exit != NULL; exit = exit->next_e)
1105 n++;
1106
1107 fprintf ((FILE*) file, "Edge %d->%d exits %u loops\n",
1108 e->src->index, e->dest->index, n);
1109
1110 return 1;
1111 }
1112
1113 /* Dumps the recorded exits of loops to FILE. */
1114
1115 extern void dump_recorded_exits (FILE *);
1116 void
1117 dump_recorded_exits (FILE *file)
1118 {
1119 if (!current_loops->exits)
1120 return;
1121 htab_traverse (current_loops->exits, dump_recorded_exit, file);
1122 }
1123
1124 /* Releases lists of loop exits. */
1125
1126 void
1127 release_recorded_exits (void)
1128 {
1129 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS));
1130 htab_delete (current_loops->exits);
1131 current_loops->exits = NULL;
1132 loops_state_clear (LOOPS_HAVE_RECORDED_EXITS);
1133 }
1134
1135 /* Returns the list of the exit edges of a LOOP. */
1136
1137 VEC (edge, heap) *
1138 get_loop_exit_edges (const struct loop *loop)
1139 {
1140 VEC (edge, heap) *edges = NULL;
1141 edge e;
1142 unsigned i;
1143 basic_block *body;
1144 edge_iterator ei;
1145 struct loop_exit *exit;
1146
1147 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1148
1149 /* If we maintain the lists of exits, use them. Otherwise we must
1150 scan the body of the loop. */
1151 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1152 {
1153 for (exit = loop->exits->next; exit->e; exit = exit->next)
1154 VEC_safe_push (edge, heap, edges, exit->e);
1155 }
1156 else
1157 {
1158 body = get_loop_body (loop);
1159 for (i = 0; i < loop->num_nodes; i++)
1160 FOR_EACH_EDGE (e, ei, body[i]->succs)
1161 {
1162 if (!flow_bb_inside_loop_p (loop, e->dest))
1163 VEC_safe_push (edge, heap, edges, e);
1164 }
1165 free (body);
1166 }
1167
1168 return edges;
1169 }
1170
1171 /* Counts the number of conditional branches inside LOOP. */
1172
1173 unsigned
1174 num_loop_branches (const struct loop *loop)
1175 {
1176 unsigned i, n;
1177 basic_block * body;
1178
1179 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1180
1181 body = get_loop_body (loop);
1182 n = 0;
1183 for (i = 0; i < loop->num_nodes; i++)
1184 if (EDGE_COUNT (body[i]->succs) >= 2)
1185 n++;
1186 free (body);
1187
1188 return n;
1189 }
1190
1191 /* Adds basic block BB to LOOP. */
1192 void
1193 add_bb_to_loop (basic_block bb, struct loop *loop)
1194 {
1195 unsigned i;
1196 loop_p ploop;
1197 edge_iterator ei;
1198 edge e;
1199
1200 gcc_assert (bb->loop_father == NULL);
1201 bb->loop_father = loop;
1202 bb->loop_depth = loop_depth (loop);
1203 loop->num_nodes++;
1204 for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++)
1205 ploop->num_nodes++;
1206
1207 FOR_EACH_EDGE (e, ei, bb->succs)
1208 {
1209 rescan_loop_exit (e, true, false);
1210 }
1211 FOR_EACH_EDGE (e, ei, bb->preds)
1212 {
1213 rescan_loop_exit (e, true, false);
1214 }
1215 }
1216
1217 /* Remove basic block BB from loops. */
1218 void
1219 remove_bb_from_loops (basic_block bb)
1220 {
1221 int i;
1222 struct loop *loop = bb->loop_father;
1223 loop_p ploop;
1224 edge_iterator ei;
1225 edge e;
1226
1227 gcc_assert (loop != NULL);
1228 loop->num_nodes--;
1229 for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++)
1230 ploop->num_nodes--;
1231 bb->loop_father = NULL;
1232 bb->loop_depth = 0;
1233
1234 FOR_EACH_EDGE (e, ei, bb->succs)
1235 {
1236 rescan_loop_exit (e, false, true);
1237 }
1238 FOR_EACH_EDGE (e, ei, bb->preds)
1239 {
1240 rescan_loop_exit (e, false, true);
1241 }
1242 }
1243
1244 /* Finds nearest common ancestor in loop tree for given loops. */
1245 struct loop *
1246 find_common_loop (struct loop *loop_s, struct loop *loop_d)
1247 {
1248 unsigned sdepth, ddepth;
1249
1250 if (!loop_s) return loop_d;
1251 if (!loop_d) return loop_s;
1252
1253 sdepth = loop_depth (loop_s);
1254 ddepth = loop_depth (loop_d);
1255
1256 if (sdepth < ddepth)
1257 loop_d = VEC_index (loop_p, loop_d->superloops, sdepth);
1258 else if (sdepth > ddepth)
1259 loop_s = VEC_index (loop_p, loop_s->superloops, ddepth);
1260
1261 while (loop_s != loop_d)
1262 {
1263 loop_s = loop_outer (loop_s);
1264 loop_d = loop_outer (loop_d);
1265 }
1266 return loop_s;
1267 }
1268
1269 /* Removes LOOP from structures and frees its data. */
1270
1271 void
1272 delete_loop (struct loop *loop)
1273 {
1274 /* Remove the loop from structure. */
1275 flow_loop_tree_node_remove (loop);
1276
1277 /* Remove loop from loops array. */
1278 VEC_replace (loop_p, current_loops->larray, loop->num, NULL);
1279
1280 /* Free loop data. */
1281 flow_loop_free (loop);
1282 }
1283
1284 /* Cancels the LOOP; it must be innermost one. */
1285
1286 static void
1287 cancel_loop (struct loop *loop)
1288 {
1289 basic_block *bbs;
1290 unsigned i;
1291 struct loop *outer = loop_outer (loop);
1292
1293 gcc_assert (!loop->inner);
1294
1295 /* Move blocks up one level (they should be removed as soon as possible). */
1296 bbs = get_loop_body (loop);
1297 for (i = 0; i < loop->num_nodes; i++)
1298 bbs[i]->loop_father = outer;
1299
1300 delete_loop (loop);
1301 }
1302
1303 /* Cancels LOOP and all its subloops. */
1304 void
1305 cancel_loop_tree (struct loop *loop)
1306 {
1307 while (loop->inner)
1308 cancel_loop_tree (loop->inner);
1309 cancel_loop (loop);
1310 }
1311
1312 /* Checks that information about loops is correct
1313 -- sizes of loops are all right
1314 -- results of get_loop_body really belong to the loop
1315 -- loop header have just single entry edge and single latch edge
1316 -- loop latches have only single successor that is header of their loop
1317 -- irreducible loops are correctly marked
1318 */
1319 void
1320 verify_loop_structure (void)
1321 {
1322 unsigned *sizes, i, j;
1323 sbitmap irreds;
1324 basic_block *bbs, bb;
1325 struct loop *loop;
1326 int err = 0;
1327 edge e;
1328 unsigned num = number_of_loops ();
1329 loop_iterator li;
1330 struct loop_exit *exit, *mexit;
1331
1332 /* Check sizes. */
1333 sizes = XCNEWVEC (unsigned, num);
1334 sizes[0] = 2;
1335
1336 FOR_EACH_BB (bb)
1337 for (loop = bb->loop_father; loop; loop = loop_outer (loop))
1338 sizes[loop->num]++;
1339
1340 FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
1341 {
1342 i = loop->num;
1343
1344 if (loop->num_nodes != sizes[i])
1345 {
1346 error ("size of loop %d should be %d, not %d",
1347 i, sizes[i], loop->num_nodes);
1348 err = 1;
1349 }
1350 }
1351
1352 /* Check get_loop_body. */
1353 FOR_EACH_LOOP (li, loop, 0)
1354 {
1355 bbs = get_loop_body (loop);
1356
1357 for (j = 0; j < loop->num_nodes; j++)
1358 if (!flow_bb_inside_loop_p (loop, bbs[j]))
1359 {
1360 error ("bb %d do not belong to loop %d",
1361 bbs[j]->index, loop->num);
1362 err = 1;
1363 }
1364 free (bbs);
1365 }
1366
1367 /* Check headers and latches. */
1368 FOR_EACH_LOOP (li, loop, 0)
1369 {
1370 i = loop->num;
1371
1372 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
1373 && EDGE_COUNT (loop->header->preds) != 2)
1374 {
1375 error ("loop %d's header does not have exactly 2 entries", i);
1376 err = 1;
1377 }
1378 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
1379 {
1380 if (!single_succ_p (loop->latch))
1381 {
1382 error ("loop %d's latch does not have exactly 1 successor", i);
1383 err = 1;
1384 }
1385 if (single_succ (loop->latch) != loop->header)
1386 {
1387 error ("loop %d's latch does not have header as successor", i);
1388 err = 1;
1389 }
1390 if (loop->latch->loop_father != loop)
1391 {
1392 error ("loop %d's latch does not belong directly to it", i);
1393 err = 1;
1394 }
1395 }
1396 if (loop->header->loop_father != loop)
1397 {
1398 error ("loop %d's header does not belong directly to it", i);
1399 err = 1;
1400 }
1401 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1402 && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
1403 {
1404 error ("loop %d's latch is marked as part of irreducible region", i);
1405 err = 1;
1406 }
1407 }
1408
1409 /* Check irreducible loops. */
1410 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1411 {
1412 /* Record old info. */
1413 irreds = sbitmap_alloc (last_basic_block);
1414 FOR_EACH_BB (bb)
1415 {
1416 edge_iterator ei;
1417 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1418 SET_BIT (irreds, bb->index);
1419 else
1420 RESET_BIT (irreds, bb->index);
1421 FOR_EACH_EDGE (e, ei, bb->succs)
1422 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1423 e->flags |= EDGE_ALL_FLAGS + 1;
1424 }
1425
1426 /* Recount it. */
1427 mark_irreducible_loops ();
1428
1429 /* Compare. */
1430 FOR_EACH_BB (bb)
1431 {
1432 edge_iterator ei;
1433
1434 if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1435 && !TEST_BIT (irreds, bb->index))
1436 {
1437 error ("basic block %d should be marked irreducible", bb->index);
1438 err = 1;
1439 }
1440 else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1441 && TEST_BIT (irreds, bb->index))
1442 {
1443 error ("basic block %d should not be marked irreducible", bb->index);
1444 err = 1;
1445 }
1446 FOR_EACH_EDGE (e, ei, bb->succs)
1447 {
1448 if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1449 && !(e->flags & (EDGE_ALL_FLAGS + 1)))
1450 {
1451 error ("edge from %d to %d should be marked irreducible",
1452 e->src->index, e->dest->index);
1453 err = 1;
1454 }
1455 else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1456 && (e->flags & (EDGE_ALL_FLAGS + 1)))
1457 {
1458 error ("edge from %d to %d should not be marked irreducible",
1459 e->src->index, e->dest->index);
1460 err = 1;
1461 }
1462 e->flags &= ~(EDGE_ALL_FLAGS + 1);
1463 }
1464 }
1465 free (irreds);
1466 }
1467
1468 /* Check the recorded loop exits. */
1469 FOR_EACH_LOOP (li, loop, 0)
1470 {
1471 if (!loop->exits || loop->exits->e != NULL)
1472 {
1473 error ("corrupted head of the exits list of loop %d",
1474 loop->num);
1475 err = 1;
1476 }
1477 else
1478 {
1479 /* Check that the list forms a cycle, and all elements except
1480 for the head are nonnull. */
1481 for (mexit = loop->exits, exit = mexit->next, i = 0;
1482 exit->e && exit != mexit;
1483 exit = exit->next)
1484 {
1485 if (i++ & 1)
1486 mexit = mexit->next;
1487 }
1488
1489 if (exit != loop->exits)
1490 {
1491 error ("corrupted exits list of loop %d", loop->num);
1492 err = 1;
1493 }
1494 }
1495
1496 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1497 {
1498 if (loop->exits->next != loop->exits)
1499 {
1500 error ("nonempty exits list of loop %d, but exits are not recorded",
1501 loop->num);
1502 err = 1;
1503 }
1504 }
1505 }
1506
1507 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1508 {
1509 unsigned n_exits = 0, eloops;
1510
1511 memset (sizes, 0, sizeof (unsigned) * num);
1512 FOR_EACH_BB (bb)
1513 {
1514 edge_iterator ei;
1515 if (bb->loop_father == current_loops->tree_root)
1516 continue;
1517 FOR_EACH_EDGE (e, ei, bb->succs)
1518 {
1519 if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
1520 continue;
1521
1522 n_exits++;
1523 exit = get_exit_descriptions (e);
1524 if (!exit)
1525 {
1526 error ("Exit %d->%d not recorded",
1527 e->src->index, e->dest->index);
1528 err = 1;
1529 }
1530 eloops = 0;
1531 for (; exit; exit = exit->next_e)
1532 eloops++;
1533
1534 for (loop = bb->loop_father;
1535 loop != e->dest->loop_father;
1536 loop = loop_outer (loop))
1537 {
1538 eloops--;
1539 sizes[loop->num]++;
1540 }
1541
1542 if (eloops != 0)
1543 {
1544 error ("Wrong list of exited loops for edge %d->%d",
1545 e->src->index, e->dest->index);
1546 err = 1;
1547 }
1548 }
1549 }
1550
1551 if (n_exits != htab_elements (current_loops->exits))
1552 {
1553 error ("Too many loop exits recorded");
1554 err = 1;
1555 }
1556
1557 FOR_EACH_LOOP (li, loop, 0)
1558 {
1559 eloops = 0;
1560 for (exit = loop->exits->next; exit->e; exit = exit->next)
1561 eloops++;
1562 if (eloops != sizes[loop->num])
1563 {
1564 error ("%d exits recorded for loop %d (having %d exits)",
1565 eloops, loop->num, sizes[loop->num]);
1566 err = 1;
1567 }
1568 }
1569 }
1570
1571 gcc_assert (!err);
1572
1573 free (sizes);
1574 }
1575
1576 /* Returns latch edge of LOOP. */
1577 edge
1578 loop_latch_edge (const struct loop *loop)
1579 {
1580 return find_edge (loop->latch, loop->header);
1581 }
1582
1583 /* Returns preheader edge of LOOP. */
1584 edge
1585 loop_preheader_edge (const struct loop *loop)
1586 {
1587 edge e;
1588 edge_iterator ei;
1589
1590 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS));
1591
1592 FOR_EACH_EDGE (e, ei, loop->header->preds)
1593 if (e->src != loop->latch)
1594 break;
1595
1596 return e;
1597 }
1598
1599 /* Returns true if E is an exit of LOOP. */
1600
1601 bool
1602 loop_exit_edge_p (const struct loop *loop, const_edge e)
1603 {
1604 return (flow_bb_inside_loop_p (loop, e->src)
1605 && !flow_bb_inside_loop_p (loop, e->dest));
1606 }
1607
1608 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1609 or more than one exit. If loops do not have the exits recorded, NULL
1610 is returned always. */
1611
1612 edge
1613 single_exit (const struct loop *loop)
1614 {
1615 struct loop_exit *exit = loop->exits->next;
1616
1617 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1618 return NULL;
1619
1620 if (exit->e && exit->next == loop->exits)
1621 return exit->e;
1622 else
1623 return NULL;
1624 }
1625
1626 /* Returns true when BB has an edge exiting LOOP. */
1627
1628 bool
1629 is_loop_exit (struct loop *loop, basic_block bb)
1630 {
1631 edge e;
1632 edge_iterator ei;
1633
1634 FOR_EACH_EDGE (e, ei, bb->preds)
1635 if (loop_exit_edge_p (loop, e))
1636 return true;
1637
1638 return false;
1639 }