Mercurial > hg > CbC > CbC_gcc

comparison gcc/cfgloop.c @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 77e2b8dfacca
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
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
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
342 return loop;
343 }
344
345 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
346 (including the root of the loop tree). */
347
348 static void
349 init_loops_structure (struct loops *loops, unsigned num_loops)
350 {
351 struct loop *root;
352
353 memset (loops, 0, sizeof *loops);
354 loops->larray = VEC_alloc (loop_p, gc, num_loops);
355
356 /* Dummy loop containing whole function. */
357 root = alloc_loop ();
358 root->num_nodes = n_basic_blocks;
359 root->latch = EXIT_BLOCK_PTR;
360 root->header = ENTRY_BLOCK_PTR;
361 ENTRY_BLOCK_PTR->loop_father = root;
362 EXIT_BLOCK_PTR->loop_father = root;
363
364 VEC_quick_push (loop_p, loops->larray, root);
365 loops->tree_root = root;
366 }
367
368 /* Find all the natural loops in the function and save in LOOPS structure and
369 recalculate loop_depth information in basic block structures.
370 Return the number of natural loops found. */
371
372 int
373 flow_loops_find (struct loops *loops)
374 {
375 int b;
376 int num_loops;
377 edge e;
378 sbitmap headers;
379 int *dfs_order;
380 int *rc_order;
381 basic_block header;
382 basic_block bb;
383
384 /* Ensure that the dominators are computed. */
385 calculate_dominance_info (CDI_DOMINATORS);
386
387 /* Taking care of this degenerate case makes the rest of
388 this code simpler. */
389 if (n_basic_blocks == NUM_FIXED_BLOCKS)
390 {
391 init_loops_structure (loops, 1);
392 return 1;
393 }
394
395 dfs_order = NULL;
396 rc_order = NULL;
397
398 /* Count the number of loop headers. This should be the
399 same as the number of natural loops. */
400 headers = sbitmap_alloc (last_basic_block);
401 sbitmap_zero (headers);
402
403 num_loops = 0;
404 FOR_EACH_BB (header)
405 {
406 edge_iterator ei;
407
408 header->loop_depth = 0;
409
410 /* If we have an abnormal predecessor, do not consider the
411 loop (not worth the problems). */
412 FOR_EACH_EDGE (e, ei, header->preds)
413 if (e->flags & EDGE_ABNORMAL)
414 break;
415 if (e)
416 continue;
417
418 FOR_EACH_EDGE (e, ei, header->preds)
419 {
420 basic_block latch = e->src;
421
422 gcc_assert (!(e->flags & EDGE_ABNORMAL));
423
424 /* Look for back edges where a predecessor is dominated
425 by this block. A natural loop has a single entry
426 node (header) that dominates all the nodes in the
427 loop. It also has single back edge to the header
428 from a latch node. */
429 if (latch != ENTRY_BLOCK_PTR
430 && dominated_by_p (CDI_DOMINATORS, latch, header))
431 {
432 /* Shared headers should be eliminated by now. */
433 SET_BIT (headers, header->index);
434 num_loops++;
435 }
436 }
437 }
438
439 /* Allocate loop structures. */
440 init_loops_structure (loops, num_loops + 1);
441
442 /* Find and record information about all the natural loops
443 in the CFG. */
444 FOR_EACH_BB (bb)
445 bb->loop_father = loops->tree_root;
446
447 if (num_loops)
448 {
449 /* Compute depth first search order of the CFG so that outer
450 natural loops will be found before inner natural loops. */
451 dfs_order = XNEWVEC (int, n_basic_blocks);
452 rc_order = XNEWVEC (int, n_basic_blocks);
453 pre_and_rev_post_order_compute (dfs_order, rc_order, false);
454
455 num_loops = 1;
456
457 for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++)
458 {
459 struct loop *loop;
460 edge_iterator ei;
461
462 /* Search the nodes of the CFG in reverse completion order
463 so that we can find outer loops first. */
464 if (!TEST_BIT (headers, rc_order[b]))
465 continue;
466
467 header = BASIC_BLOCK (rc_order[b]);
468
469 loop = alloc_loop ();
470 VEC_quick_push (loop_p, loops->larray, loop);
471
472 loop->header = header;
473 loop->num = num_loops;
474 num_loops++;
475
476 flow_loop_tree_node_add (header->loop_father, loop);
477 loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
478
479 /* Look for the latch for this header block, if it has just a
480 single one. */
481 FOR_EACH_EDGE (e, ei, header->preds)
482 {
483 basic_block latch = e->src;
484
485 if (flow_bb_inside_loop_p (loop, latch))
486 {
487 if (loop->latch != NULL)
488 {
489 /* More than one latch edge. */
490 loop->latch = NULL;
491 break;
492 }
493 loop->latch = latch;
494 }
495 }
496 }
497
498 free (dfs_order);
499 free (rc_order);
500 }
501
502 sbitmap_free (headers);
503
504 loops->exits = NULL;
505 return VEC_length (loop_p, loops->larray);
506 }
507
508 /* Ratio of frequencies of edges so that one of more latch edges is
509 considered to belong to inner loop with same header. */
510 #define HEAVY_EDGE_RATIO 8
511
512 /* Minimum number of samples for that we apply
513 find_subloop_latch_edge_by_profile heuristics. */
514 #define HEAVY_EDGE_MIN_SAMPLES 10
515
516 /* If the profile info is available, finds an edge in LATCHES that much more
517 frequent than the remaining edges. Returns such an edge, or NULL if we do
518 not find one.
519
520 We do not use guessed profile here, only the measured one. The guessed
521 profile is usually too flat and unreliable for this (and it is mostly based
522 on the loop structure of the program, so it does not make much sense to
523 derive the loop structure from it). */
524
525 static edge
526 find_subloop_latch_edge_by_profile (VEC (edge, heap) *latches)
527 {
528 unsigned i;
529 edge e, me = NULL;
530 gcov_type mcount = 0, tcount = 0;
531
532 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
533 {
534 if (e->count > mcount)
535 {
536 me = e;
537 mcount = e->count;
538 }
539 tcount += e->count;
540 }
541
542 if (tcount < HEAVY_EDGE_MIN_SAMPLES
543 || (tcount - mcount) * HEAVY_EDGE_RATIO > tcount)
544 return NULL;
545
546 if (dump_file)
547 fprintf (dump_file,
548 "Found latch edge %d -> %d using profile information.\n",
549 me->src->index, me->dest->index);
550 return me;
551 }
552
553 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
554 on the structure of induction variables. Returns this edge, or NULL if we
555 do not find any.
556
557 We are quite conservative, and look just for an obvious simple innermost
558 loop (which is the case where we would lose the most performance by not
559 disambiguating the loop). More precisely, we look for the following
560 situation: The source of the chosen latch edge dominates sources of all
561 the other latch edges. Additionally, the header does not contain a phi node
562 such that the argument from the chosen edge is equal to the argument from
563 another edge. */
564
565 static edge
566 find_subloop_latch_edge_by_ivs (struct loop *loop ATTRIBUTE_UNUSED, VEC (edge, heap) *latches)
567 {
568 edge e, latch = VEC_index (edge, latches, 0);
569 unsigned i;
570 gimple phi;
571 gimple_stmt_iterator psi;
572 tree lop;
573 basic_block bb;
574
575 /* Find the candidate for the latch edge. */
576 for (i = 1; VEC_iterate (edge, latches, i, e); i++)
577 if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src))
578 latch = e;
579
580 /* Verify that it dominates all the latch edges. */
581 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
582 if (!dominated_by_p (CDI_DOMINATORS, e->src, latch->src))
583 return NULL;
584
585 /* Check for a phi node that would deny that this is a latch edge of
586 a subloop. */
587 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
588 {
589 phi = gsi_stmt (psi);
590 lop = PHI_ARG_DEF_FROM_EDGE (phi, latch);
591
592 /* Ignore the values that are not changed inside the subloop. */
593 if (TREE_CODE (lop) != SSA_NAME
594 || SSA_NAME_DEF_STMT (lop) == phi)
595 continue;
596 bb = gimple_bb (SSA_NAME_DEF_STMT (lop));
597 if (!bb || !flow_bb_inside_loop_p (loop, bb))
598 continue;
599
600 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
601 if (e != latch
602 && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop)
603 return NULL;
604 }
605
606 if (dump_file)
607 fprintf (dump_file,
608 "Found latch edge %d -> %d using iv structure.\n",
609 latch->src->index, latch->dest->index);
610 return latch;
611 }
612
613 /* If we can determine that one of the several latch edges of LOOP behaves
614 as a latch edge of a separate subloop, returns this edge. Otherwise
615 returns NULL. */
616
617 static edge
618 find_subloop_latch_edge (struct loop *loop)
619 {
620 VEC (edge, heap) *latches = get_loop_latch_edges (loop);
621 edge latch = NULL;
622
623 if (VEC_length (edge, latches) > 1)
624 {
625 latch = find_subloop_latch_edge_by_profile (latches);
626
627 if (!latch
628 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
629 should use cfghook for this, but it is hard to imagine it would
630 be useful elsewhere. */
631 && current_ir_type () == IR_GIMPLE)
632 latch = find_subloop_latch_edge_by_ivs (loop, latches);
633 }
634
635 VEC_free (edge, heap, latches);
636 return latch;
637 }
638
639 /* Callback for make_forwarder_block. Returns true if the edge E is marked
640 in the set MFB_REIS_SET. */
641
642 static struct pointer_set_t *mfb_reis_set;
643 static bool
644 mfb_redirect_edges_in_set (edge e)
645 {
646 return pointer_set_contains (mfb_reis_set, e);
647 }
648
649 /* Creates a subloop of LOOP with latch edge LATCH. */
650
651 static void
652 form_subloop (struct loop *loop, edge latch)
653 {
654 edge_iterator ei;
655 edge e, new_entry;
656 struct loop *new_loop;
657
658 mfb_reis_set = pointer_set_create ();
659 FOR_EACH_EDGE (e, ei, loop->header->preds)
660 {
661 if (e != latch)
662 pointer_set_insert (mfb_reis_set, e);
663 }
664 new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
665 NULL);
666 pointer_set_destroy (mfb_reis_set);
667
668 loop->header = new_entry->src;
669
670 /* Find the blocks and subloops that belong to the new loop, and add it to
671 the appropriate place in the loop tree. */
672 new_loop = alloc_loop ();
673 new_loop->header = new_entry->dest;
674 new_loop->latch = latch->src;
675 add_loop (new_loop, loop);
676 }
677
678 /* Make all the latch edges of LOOP to go to a single forwarder block --
679 a new latch of LOOP. */
680
681 static void
682 merge_latch_edges (struct loop *loop)
683 {
684 VEC (edge, heap) *latches = get_loop_latch_edges (loop);
685 edge latch, e;
686 unsigned i;
687
688 gcc_assert (VEC_length (edge, latches) > 0);
689
690 if (VEC_length (edge, latches) == 1)
691 loop->latch = VEC_index (edge, latches, 0)->src;
692 else
693 {
694 if (dump_file)
695 fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num);
696
697 mfb_reis_set = pointer_set_create ();
698 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
699 pointer_set_insert (mfb_reis_set, e);
700 latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
701 NULL);
702 pointer_set_destroy (mfb_reis_set);
703
704 loop->header = latch->dest;
705 loop->latch = latch->src;
706 }
707
708 VEC_free (edge, heap, latches);
709 }
710
711 /* LOOP may have several latch edges. Transform it into (possibly several)
712 loops with single latch edge. */
713
714 static void
715 disambiguate_multiple_latches (struct loop *loop)
716 {
717 edge e;
718
719 /* We eliminate the multiple latches by splitting the header to the forwarder
720 block F and the rest R, and redirecting the edges. There are two cases:
721
722 1) If there is a latch edge E that corresponds to a subloop (we guess
723 that based on profile -- if it is taken much more often than the
724 remaining edges; and on trees, using the information about induction
725 variables of the loops), we redirect E to R, all the remaining edges to
726 F, then rescan the loops and try again for the outer loop.
727 2) If there is no such edge, we redirect all latch edges to F, and the
728 entry edges to R, thus making F the single latch of the loop. */
729
730 if (dump_file)
731 fprintf (dump_file, "Disambiguating loop %d with multiple latches\n",
732 loop->num);
733
734 /* During latch merging, we may need to redirect the entry edges to a new
735 block. This would cause problems if the entry edge was the one from the
736 entry block. To avoid having to handle this case specially, split
737 such entry edge. */
738 e = find_edge (ENTRY_BLOCK_PTR, loop->header);
739 if (e)
740 split_edge (e);
741
742 while (1)
743 {
744 e = find_subloop_latch_edge (loop);
745 if (!e)
746 break;
747
748 form_subloop (loop, e);
749 }
750
751 merge_latch_edges (loop);
752 }
753
754 /* Split loops with multiple latch edges. */
755
756 void
757 disambiguate_loops_with_multiple_latches (void)
758 {
759 loop_iterator li;
760 struct loop *loop;
761
762 FOR_EACH_LOOP (li, loop, 0)
763 {
764 if (!loop->latch)
765 disambiguate_multiple_latches (loop);
766 }
767 }
768
769 /* Return nonzero if basic block BB belongs to LOOP. */
770 bool
771 flow_bb_inside_loop_p (const struct loop *loop, const_basic_block bb)
772 {
773 struct loop *source_loop;
774
775 if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
776 return 0;
777
778 source_loop = bb->loop_father;
779 return loop == source_loop || flow_loop_nested_p (loop, source_loop);
780 }
781
782 /* Enumeration predicate for get_loop_body_with_size. */
783 static bool
784 glb_enum_p (const_basic_block bb, const void *glb_loop)
785 {
786 const struct loop *const loop = (const struct loop *) glb_loop;
787 return (bb != loop->header
788 && dominated_by_p (CDI_DOMINATORS, bb, loop->header));
789 }
790
791 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
792 order against direction of edges from latch. Specially, if
793 header != latch, latch is the 1-st block. LOOP cannot be the fake
794 loop tree root, and its size must be at most MAX_SIZE. The blocks
795 in the LOOP body are stored to BODY, and the size of the LOOP is
796 returned. */
797
798 unsigned
799 get_loop_body_with_size (const struct loop *loop, basic_block *body,
800 unsigned max_size)
801 {
802 return dfs_enumerate_from (loop->header, 1, glb_enum_p,
803 body, max_size, loop);
804 }
805
806 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
807 order against direction of edges from latch. Specially, if
808 header != latch, latch is the 1-st block. */
809
810 basic_block *
811 get_loop_body (const struct loop *loop)
812 {
813 basic_block *body, bb;
814 unsigned tv = 0;
815
816 gcc_assert (loop->num_nodes);
817
818 body = XCNEWVEC (basic_block, loop->num_nodes);
819
820 if (loop->latch == EXIT_BLOCK_PTR)
821 {
822 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
823 special-case the fake loop that contains the whole function. */
824 gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks);
825 body[tv++] = loop->header;
826 body[tv++] = EXIT_BLOCK_PTR;
827 FOR_EACH_BB (bb)
828 body[tv++] = bb;
829 }
830 else
831 tv = get_loop_body_with_size (loop, body, loop->num_nodes);
832
833 gcc_assert (tv == loop->num_nodes);
834 return body;
835 }
836
837 /* Fills dominance descendants inside LOOP of the basic block BB into
838 array TOVISIT from index *TV. */
839
840 static void
841 fill_sons_in_loop (const struct loop *loop, basic_block bb,
842 basic_block *tovisit, int *tv)
843 {
844 basic_block son, postpone = NULL;
845
846 tovisit[(*tv)++] = bb;
847 for (son = first_dom_son (CDI_DOMINATORS, bb);
848 son;
849 son = next_dom_son (CDI_DOMINATORS, son))
850 {
851 if (!flow_bb_inside_loop_p (loop, son))
852 continue;
853
854 if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
855 {
856 postpone = son;
857 continue;
858 }
859 fill_sons_in_loop (loop, son, tovisit, tv);
860 }
861
862 if (postpone)
863 fill_sons_in_loop (loop, postpone, tovisit, tv);
864 }
865
866 /* Gets body of a LOOP (that must be different from the outermost loop)
867 sorted by dominance relation. Additionally, if a basic block s dominates
868 the latch, then only blocks dominated by s are be after it. */
869
870 basic_block *
871 get_loop_body_in_dom_order (const struct loop *loop)
872 {
873 basic_block *tovisit;
874 int tv;
875
876 gcc_assert (loop->num_nodes);
877
878 tovisit = XCNEWVEC (basic_block, loop->num_nodes);
879
880 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
881
882 tv = 0;
883 fill_sons_in_loop (loop, loop->header, tovisit, &tv);
884
885 gcc_assert (tv == (int) loop->num_nodes);
886
887 return tovisit;
888 }
889
890 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
891
892 basic_block *
893 get_loop_body_in_custom_order (const struct loop *loop,
894 int (*bb_comparator) (const void *, const void *))
895 {
896 basic_block *bbs = get_loop_body (loop);
897
898 qsort (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator);
899
900 return bbs;
901 }
902
903 /* Get body of a LOOP in breadth first sort order. */
904
905 basic_block *
906 get_loop_body_in_bfs_order (const struct loop *loop)
907 {
908 basic_block *blocks;
909 basic_block bb;
910 bitmap visited;
911 unsigned int i = 0;
912 unsigned int vc = 1;
913
914 gcc_assert (loop->num_nodes);
915 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
916
917 blocks = XCNEWVEC (basic_block, loop->num_nodes);
918 visited = BITMAP_ALLOC (NULL);
919
920 bb = loop->header;
921 while (i < loop->num_nodes)
922 {
923 edge e;
924 edge_iterator ei;
925
926 if (!bitmap_bit_p (visited, bb->index))
927 {
928 /* This basic block is now visited */
929 bitmap_set_bit (visited, bb->index);
930 blocks[i++] = bb;
931 }
932
933 FOR_EACH_EDGE (e, ei, bb->succs)
934 {
935 if (flow_bb_inside_loop_p (loop, e->dest))
936 {
937 if (!bitmap_bit_p (visited, e->dest->index))
938 {
939 bitmap_set_bit (visited, e->dest->index);
940 blocks[i++] = e->dest;
941 }
942 }
943 }
944
945 gcc_assert (i >= vc);
946
947 bb = blocks[vc++];
948 }
949
950 BITMAP_FREE (visited);
951 return blocks;
952 }
953
954 /* Hash function for struct loop_exit. */
955
956 static hashval_t
957 loop_exit_hash (const void *ex)
958 {
959 const struct loop_exit *const exit = (const struct loop_exit *) ex;
960
961 return htab_hash_pointer (exit->e);
962 }
963
964 /* Equality function for struct loop_exit. Compares with edge. */
965
966 static int
967 loop_exit_eq (const void *ex, const void *e)
968 {
969 const struct loop_exit *const exit = (const struct loop_exit *) ex;
970
971 return exit->e == e;
972 }
973
974 /* Frees the list of loop exit descriptions EX. */
975
976 static void
977 loop_exit_free (void *ex)
978 {
979 struct loop_exit *exit = (struct loop_exit *) ex, *next;
980
981 for (; exit; exit = next)
982 {
983 next = exit->next_e;
984
985 exit->next->prev = exit->prev;
986 exit->prev->next = exit->next;
987
988 ggc_free (exit);
989 }
990 }
991
992 /* Returns the list of records for E as an exit of a loop. */
993
994 static struct loop_exit *
995 get_exit_descriptions (edge e)
996 {
997 return (struct loop_exit *) htab_find_with_hash (current_loops->exits, e,
998 htab_hash_pointer (e));
999 }
1000
1001 /* Updates the lists of loop exits in that E appears.
1002 If REMOVED is true, E is being removed, and we
1003 just remove it from the lists of exits.
1004 If NEW_EDGE is true and E is not a loop exit, we
1005 do not try to remove it from loop exit lists. */
1006
1007 void
1008 rescan_loop_exit (edge e, bool new_edge, bool removed)
1009 {
1010 void **slot;
1011 struct loop_exit *exits = NULL, *exit;
1012 struct loop *aloop, *cloop;
1013
1014 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1015 return;
1016
1017 if (!removed
1018 && e->src->loop_father != NULL
1019 && e->dest->loop_father != NULL
1020 && !flow_bb_inside_loop_p (e->src->loop_father, e->dest))
1021 {
1022 cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
1023 for (aloop = e->src->loop_father;
1024 aloop != cloop;
1025 aloop = loop_outer (aloop))
1026 {
1027 exit = GGC_NEW (struct loop_exit);
1028 exit->e = e;
1029
1030 exit->next = aloop->exits->next;
1031 exit->prev = aloop->exits;
1032 exit->next->prev = exit;
1033 exit->prev->next = exit;
1034
1035 exit->next_e = exits;
1036 exits = exit;
1037 }
1038 }
1039
1040 if (!exits && new_edge)
1041 return;
1042
1043 slot = htab_find_slot_with_hash (current_loops->exits, e,
1044 htab_hash_pointer (e),
1045 exits ? INSERT : NO_INSERT);
1046 if (!slot)
1047 return;
1048
1049 if (exits)
1050 {
1051 if (*slot)
1052 loop_exit_free (*slot);
1053 *slot = exits;
1054 }
1055 else
1056 htab_clear_slot (current_loops->exits, slot);
1057 }
1058
1059 /* For each loop, record list of exit edges, and start maintaining these
1060 lists. */
1061
1062 void
1063 record_loop_exits (void)
1064 {
1065 basic_block bb;
1066 edge_iterator ei;
1067 edge e;
1068
1069 if (!current_loops)
1070 return;
1071
1072 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1073 return;
1074 loops_state_set (LOOPS_HAVE_RECORDED_EXITS);
1075
1076 gcc_assert (current_loops->exits == NULL);
1077 current_loops->exits = htab_create_alloc (2 * number_of_loops (),
1078 loop_exit_hash,
1079 loop_exit_eq,
1080 loop_exit_free,
1081 ggc_calloc, ggc_free);
1082
1083 FOR_EACH_BB (bb)
1084 {
1085 FOR_EACH_EDGE (e, ei, bb->succs)
1086 {
1087 rescan_loop_exit (e, true, false);
1088 }
1089 }
1090 }
1091
1092 /* Dumps information about the exit in *SLOT to FILE.
1093 Callback for htab_traverse. */
1094
1095 static int
1096 dump_recorded_exit (void **slot, void *file)
1097 {
1098 struct loop_exit *exit = (struct loop_exit *) *slot;
1099 unsigned n = 0;
1100 edge e = exit->e;
1101
1102 for (; exit != NULL; exit = exit->next_e)
1103 n++;
1104
1105 fprintf ((FILE*) file, "Edge %d->%d exits %u loops\n",
1106 e->src->index, e->dest->index, n);
1107
1108 return 1;
1109 }
1110
1111 /* Dumps the recorded exits of loops to FILE. */
1112
1113 extern void dump_recorded_exits (FILE *);
1114 void
1115 dump_recorded_exits (FILE *file)
1116 {
1117 if (!current_loops->exits)
1118 return;
1119 htab_traverse (current_loops->exits, dump_recorded_exit, file);
1120 }
1121
1122 /* Releases lists of loop exits. */
1123
1124 void
1125 release_recorded_exits (void)
1126 {
1127 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS));
1128 htab_delete (current_loops->exits);
1129 current_loops->exits = NULL;
1130 loops_state_clear (LOOPS_HAVE_RECORDED_EXITS);
1131 }
1132
1133 /* Returns the list of the exit edges of a LOOP. */
1134
1135 VEC (edge, heap) *
1136 get_loop_exit_edges (const struct loop *loop)
1137 {
1138 VEC (edge, heap) *edges = NULL;
1139 edge e;
1140 unsigned i;
1141 basic_block *body;
1142 edge_iterator ei;
1143 struct loop_exit *exit;
1144
1145 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1146
1147 /* If we maintain the lists of exits, use them. Otherwise we must
1148 scan the body of the loop. */
1149 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1150 {
1151 for (exit = loop->exits->next; exit->e; exit = exit->next)
1152 VEC_safe_push (edge, heap, edges, exit->e);
1153 }
1154 else
1155 {
1156 body = get_loop_body (loop);
1157 for (i = 0; i < loop->num_nodes; i++)
1158 FOR_EACH_EDGE (e, ei, body[i]->succs)
1159 {
1160 if (!flow_bb_inside_loop_p (loop, e->dest))
1161 VEC_safe_push (edge, heap, edges, e);
1162 }
1163 free (body);
1164 }
1165
1166 return edges;
1167 }
1168
1169 /* Counts the number of conditional branches inside LOOP. */
1170
1171 unsigned
1172 num_loop_branches (const struct loop *loop)
1173 {
1174 unsigned i, n;
1175 basic_block * body;
1176
1177 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1178
1179 body = get_loop_body (loop);
1180 n = 0;
1181 for (i = 0; i < loop->num_nodes; i++)
1182 if (EDGE_COUNT (body[i]->succs) >= 2)
1183 n++;
1184 free (body);
1185
1186 return n;
1187 }
1188
1189 /* Adds basic block BB to LOOP. */
1190 void
1191 add_bb_to_loop (basic_block bb, struct loop *loop)
1192 {
1193 unsigned i;
1194 loop_p ploop;
1195 edge_iterator ei;
1196 edge e;
1197
1198 gcc_assert (bb->loop_father == NULL);
1199 bb->loop_father = loop;
1200 bb->loop_depth = loop_depth (loop);
1201 loop->num_nodes++;
1202 for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++)
1203 ploop->num_nodes++;
1204
1205 FOR_EACH_EDGE (e, ei, bb->succs)
1206 {
1207 rescan_loop_exit (e, true, false);
1208 }
1209 FOR_EACH_EDGE (e, ei, bb->preds)
1210 {
1211 rescan_loop_exit (e, true, false);
1212 }
1213 }
1214
1215 /* Remove basic block BB from loops. */
1216 void
1217 remove_bb_from_loops (basic_block bb)
1218 {
1219 int i;
1220 struct loop *loop = bb->loop_father;
1221 loop_p ploop;
1222 edge_iterator ei;
1223 edge e;
1224
1225 gcc_assert (loop != NULL);
1226 loop->num_nodes--;
1227 for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++)
1228 ploop->num_nodes--;
1229 bb->loop_father = NULL;
1230 bb->loop_depth = 0;
1231
1232 FOR_EACH_EDGE (e, ei, bb->succs)
1233 {
1234 rescan_loop_exit (e, false, true);
1235 }
1236 FOR_EACH_EDGE (e, ei, bb->preds)
1237 {
1238 rescan_loop_exit (e, false, true);
1239 }
1240 }
1241
1242 /* Finds nearest common ancestor in loop tree for given loops. */
1243 struct loop *
1244 find_common_loop (struct loop *loop_s, struct loop *loop_d)
1245 {
1246 unsigned sdepth, ddepth;
1247
1248 if (!loop_s) return loop_d;
1249 if (!loop_d) return loop_s;
1250
1251 sdepth = loop_depth (loop_s);
1252 ddepth = loop_depth (loop_d);
1253
1254 if (sdepth < ddepth)
1255 loop_d = VEC_index (loop_p, loop_d->superloops, sdepth);
1256 else if (sdepth > ddepth)
1257 loop_s = VEC_index (loop_p, loop_s->superloops, ddepth);
1258
1259 while (loop_s != loop_d)
1260 {
1261 loop_s = loop_outer (loop_s);
1262 loop_d = loop_outer (loop_d);
1263 }
1264 return loop_s;
1265 }
1266
1267 /* Removes LOOP from structures and frees its data. */
1268
1269 void
1270 delete_loop (struct loop *loop)
1271 {
1272 /* Remove the loop from structure. */
1273 flow_loop_tree_node_remove (loop);
1274
1275 /* Remove loop from loops array. */
1276 VEC_replace (loop_p, current_loops->larray, loop->num, NULL);
1277
1278 /* Free loop data. */
1279 flow_loop_free (loop);
1280 }
1281
1282 /* Cancels the LOOP; it must be innermost one. */
1283
1284 static void
1285 cancel_loop (struct loop *loop)
1286 {
1287 basic_block *bbs;
1288 unsigned i;
1289 struct loop *outer = loop_outer (loop);
1290
1291 gcc_assert (!loop->inner);
1292
1293 /* Move blocks up one level (they should be removed as soon as possible). */
1294 bbs = get_loop_body (loop);
1295 for (i = 0; i < loop->num_nodes; i++)
1296 bbs[i]->loop_father = outer;
1297
1298 delete_loop (loop);
1299 }
1300
1301 /* Cancels LOOP and all its subloops. */
1302 void
1303 cancel_loop_tree (struct loop *loop)
1304 {
1305 while (loop->inner)
1306 cancel_loop_tree (loop->inner);
1307 cancel_loop (loop);
1308 }
1309
1310 /* Checks that information about loops is correct
1311 -- sizes of loops are all right
1312 -- results of get_loop_body really belong to the loop
1313 -- loop header have just single entry edge and single latch edge
1314 -- loop latches have only single successor that is header of their loop
1315 -- irreducible loops are correctly marked
1316 */
1317 void
1318 verify_loop_structure (void)
1319 {
1320 unsigned *sizes, i, j;
1321 sbitmap irreds;
1322 basic_block *bbs, bb;
1323 struct loop *loop;
1324 int err = 0;
1325 edge e;
1326 unsigned num = number_of_loops ();
1327 loop_iterator li;
1328 struct loop_exit *exit, *mexit;
1329
1330 /* Check sizes. */
1331 sizes = XCNEWVEC (unsigned, num);
1332 sizes[0] = 2;
1333
1334 FOR_EACH_BB (bb)
1335 for (loop = bb->loop_father; loop; loop = loop_outer (loop))
1336 sizes[loop->num]++;
1337
1338 FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
1339 {
1340 i = loop->num;
1341
1342 if (loop->num_nodes != sizes[i])
1343 {
1344 error ("size of loop %d should be %d, not %d",
1345 i, sizes[i], loop->num_nodes);
1346 err = 1;
1347 }
1348 }
1349
1350 /* Check get_loop_body. */
1351 FOR_EACH_LOOP (li, loop, 0)
1352 {
1353 bbs = get_loop_body (loop);
1354
1355 for (j = 0; j < loop->num_nodes; j++)
1356 if (!flow_bb_inside_loop_p (loop, bbs[j]))
1357 {
1358 error ("bb %d do not belong to loop %d",
1359 bbs[j]->index, loop->num);
1360 err = 1;
1361 }
1362 free (bbs);
1363 }
1364
1365 /* Check headers and latches. */
1366 FOR_EACH_LOOP (li, loop, 0)
1367 {
1368 i = loop->num;
1369
1370 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
1371 && EDGE_COUNT (loop->header->preds) != 2)
1372 {
1373 error ("loop %d's header does not have exactly 2 entries", i);
1374 err = 1;
1375 }
1376 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
1377 {
1378 if (!single_succ_p (loop->latch))
1379 {
1380 error ("loop %d's latch does not have exactly 1 successor", i);
1381 err = 1;
1382 }
1383 if (single_succ (loop->latch) != loop->header)
1384 {
1385 error ("loop %d's latch does not have header as successor", i);
1386 err = 1;
1387 }
1388 if (loop->latch->loop_father != loop)
1389 {
1390 error ("loop %d's latch does not belong directly to it", i);
1391 err = 1;
1392 }
1393 }
1394 if (loop->header->loop_father != loop)
1395 {
1396 error ("loop %d's header does not belong directly to it", i);
1397 err = 1;
1398 }
1399 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1400 && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
1401 {
1402 error ("loop %d's latch is marked as part of irreducible region", i);
1403 err = 1;
1404 }
1405 }
1406
1407 /* Check irreducible loops. */
1408 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1409 {
1410 /* Record old info. */
1411 irreds = sbitmap_alloc (last_basic_block);
1412 FOR_EACH_BB (bb)
1413 {
1414 edge_iterator ei;
1415 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1416 SET_BIT (irreds, bb->index);
1417 else
1418 RESET_BIT (irreds, bb->index);
1419 FOR_EACH_EDGE (e, ei, bb->succs)
1420 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1421 e->flags |= EDGE_ALL_FLAGS + 1;
1422 }
1423
1424 /* Recount it. */
1425 mark_irreducible_loops ();
1426
1427 /* Compare. */
1428 FOR_EACH_BB (bb)
1429 {
1430 edge_iterator ei;
1431
1432 if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1433 && !TEST_BIT (irreds, bb->index))
1434 {
1435 error ("basic block %d should be marked irreducible", bb->index);
1436 err = 1;
1437 }
1438 else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1439 && TEST_BIT (irreds, bb->index))
1440 {
1441 error ("basic block %d should not be marked irreducible", bb->index);
1442 err = 1;
1443 }
1444 FOR_EACH_EDGE (e, ei, bb->succs)
1445 {
1446 if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1447 && !(e->flags & (EDGE_ALL_FLAGS + 1)))
1448 {
1449 error ("edge from %d to %d should be marked irreducible",
1450 e->src->index, e->dest->index);
1451 err = 1;
1452 }
1453 else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1454 && (e->flags & (EDGE_ALL_FLAGS + 1)))
1455 {
1456 error ("edge from %d to %d should not be marked irreducible",
1457 e->src->index, e->dest->index);
1458 err = 1;
1459 }
1460 e->flags &= ~(EDGE_ALL_FLAGS + 1);
1461 }
1462 }
1463 free (irreds);
1464 }
1465
1466 /* Check the recorded loop exits. */
1467 FOR_EACH_LOOP (li, loop, 0)
1468 {
1469 if (!loop->exits || loop->exits->e != NULL)
1470 {
1471 error ("corrupted head of the exits list of loop %d",
1472 loop->num);
1473 err = 1;
1474 }
1475 else
1476 {
1477 /* Check that the list forms a cycle, and all elements except
1478 for the head are nonnull. */
1479 for (mexit = loop->exits, exit = mexit->next, i = 0;
1480 exit->e && exit != mexit;
1481 exit = exit->next)
1482 {
1483 if (i++ & 1)
1484 mexit = mexit->next;
1485 }
1486
1487 if (exit != loop->exits)
1488 {
1489 error ("corrupted exits list of loop %d", loop->num);
1490 err = 1;
1491 }
1492 }
1493
1494 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1495 {
1496 if (loop->exits->next != loop->exits)
1497 {
1498 error ("nonempty exits list of loop %d, but exits are not recorded",
1499 loop->num);
1500 err = 1;
1501 }
1502 }
1503 }
1504
1505 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1506 {
1507 unsigned n_exits = 0, eloops;
1508
1509 memset (sizes, 0, sizeof (unsigned) * num);
1510 FOR_EACH_BB (bb)
1511 {
1512 edge_iterator ei;
1513 if (bb->loop_father == current_loops->tree_root)
1514 continue;
1515 FOR_EACH_EDGE (e, ei, bb->succs)
1516 {
1517 if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
1518 continue;
1519
1520 n_exits++;
1521 exit = get_exit_descriptions (e);
1522 if (!exit)
1523 {
1524 error ("Exit %d->%d not recorded",
1525 e->src->index, e->dest->index);
1526 err = 1;
1527 }
1528 eloops = 0;
1529 for (; exit; exit = exit->next_e)
1530 eloops++;
1531
1532 for (loop = bb->loop_father;
1533 loop != e->dest->loop_father;
1534 loop = loop_outer (loop))
1535 {
1536 eloops--;
1537 sizes[loop->num]++;
1538 }
1539
1540 if (eloops != 0)
1541 {
1542 error ("Wrong list of exited loops for edge %d->%d",
1543 e->src->index, e->dest->index);
1544 err = 1;
1545 }
1546 }
1547 }
1548
1549 if (n_exits != htab_elements (current_loops->exits))
1550 {
1551 error ("Too many loop exits recorded");
1552 err = 1;
1553 }
1554
1555 FOR_EACH_LOOP (li, loop, 0)
1556 {
1557 eloops = 0;
1558 for (exit = loop->exits->next; exit->e; exit = exit->next)
1559 eloops++;
1560 if (eloops != sizes[loop->num])
1561 {
1562 error ("%d exits recorded for loop %d (having %d exits)",
1563 eloops, loop->num, sizes[loop->num]);
1564 err = 1;
1565 }
1566 }
1567 }
1568
1569 gcc_assert (!err);
1570
1571 free (sizes);
1572 }
1573
1574 /* Returns latch edge of LOOP. */
1575 edge
1576 loop_latch_edge (const struct loop *loop)
1577 {
1578 return find_edge (loop->latch, loop->header);
1579 }
1580
1581 /* Returns preheader edge of LOOP. */
1582 edge
1583 loop_preheader_edge (const struct loop *loop)
1584 {
1585 edge e;
1586 edge_iterator ei;
1587
1588 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS));
1589
1590 FOR_EACH_EDGE (e, ei, loop->header->preds)
1591 if (e->src != loop->latch)
1592 break;
1593
1594 return e;
1595 }
1596
1597 /* Returns true if E is an exit of LOOP. */
1598
1599 bool
1600 loop_exit_edge_p (const struct loop *loop, const_edge e)
1601 {
1602 return (flow_bb_inside_loop_p (loop, e->src)
1603 && !flow_bb_inside_loop_p (loop, e->dest));
1604 }
1605
1606 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1607 or more than one exit. If loops do not have the exits recorded, NULL
1608 is returned always. */
1609
1610 edge
1611 single_exit (const struct loop *loop)
1612 {
1613 struct loop_exit *exit = loop->exits->next;
1614
1615 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1616 return NULL;
1617
1618 if (exit->e && exit->next == loop->exits)
1619 return exit->e;
1620 else
1621 return NULL;
1622 }
1623
1624 /* Returns true when BB has an edge exiting LOOP. */
1625
1626 bool
1627 is_loop_exit (struct loop *loop, basic_block bb)
1628 {
1629 edge e;
1630 edge_iterator ei;
1631
1632 FOR_EACH_EDGE (e, ei, bb->preds)
1633 if (loop_exit_edge_p (loop, e))
1634 return true;
1635
1636 return false;
1637 }