gcc/
[official-gcc.git] / gcc / cfgloop.c
blobdcf23ca1fbbf240d3344879dce128bd3c901d2f9
1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
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 3, or (at your option) any later
9 version.
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.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "rtl.h"
25 #include "function.h"
26 #include "basic-block.h"
27 #include "cfgloop.h"
28 #include "diagnostic-core.h"
29 #include "flags.h"
30 #include "tree.h"
31 #include "hash-set.h"
32 #include "tree-ssa-alias.h"
33 #include "internal-fn.h"
34 #include "gimple-expr.h"
35 #include "is-a.h"
36 #include "gimple.h"
37 #include "gimple-iterator.h"
38 #include "gimple-ssa.h"
39 #include "dumpfile.h"
41 static void flow_loops_cfg_dump (FILE *);
43 /* Dump loop related CFG information. */
45 static void
46 flow_loops_cfg_dump (FILE *file)
48 basic_block bb;
50 if (!file)
51 return;
53 FOR_EACH_BB_FN (bb, cfun)
55 edge succ;
56 edge_iterator ei;
58 fprintf (file, ";; %d succs { ", bb->index);
59 FOR_EACH_EDGE (succ, ei, bb->succs)
60 fprintf (file, "%d ", succ->dest->index);
61 fprintf (file, "}\n");
65 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
67 bool
68 flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
70 unsigned odepth = loop_depth (outer);
72 return (loop_depth (loop) > odepth
73 && (*loop->superloops)[odepth] == outer);
76 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
77 loops within LOOP. */
79 struct loop *
80 superloop_at_depth (struct loop *loop, unsigned depth)
82 unsigned ldepth = loop_depth (loop);
84 gcc_assert (depth <= ldepth);
86 if (depth == ldepth)
87 return loop;
89 return (*loop->superloops)[depth];
92 /* Returns the list of the latch edges of LOOP. */
94 static vec<edge>
95 get_loop_latch_edges (const struct loop *loop)
97 edge_iterator ei;
98 edge e;
99 vec<edge> ret = vNULL;
101 FOR_EACH_EDGE (e, ei, loop->header->preds)
103 if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header))
104 ret.safe_push (e);
107 return ret;
110 /* Dump the loop information specified by LOOP to the stream FILE
111 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
113 void
114 flow_loop_dump (const struct loop *loop, FILE *file,
115 void (*loop_dump_aux) (const struct loop *, FILE *, int),
116 int verbose)
118 basic_block *bbs;
119 unsigned i;
120 vec<edge> latches;
121 edge e;
123 if (! loop || ! loop->header)
124 return;
126 fprintf (file, ";;\n;; Loop %d\n", loop->num);
128 fprintf (file, ";; header %d, ", loop->header->index);
129 if (loop->latch)
130 fprintf (file, "latch %d\n", loop->latch->index);
131 else
133 fprintf (file, "multiple latches:");
134 latches = get_loop_latch_edges (loop);
135 FOR_EACH_VEC_ELT (latches, i, e)
136 fprintf (file, " %d", e->src->index);
137 latches.release ();
138 fprintf (file, "\n");
141 fprintf (file, ";; depth %d, outer %ld\n",
142 loop_depth (loop), (long) (loop_outer (loop)
143 ? loop_outer (loop)->num : -1));
145 fprintf (file, ";; nodes:");
146 bbs = get_loop_body (loop);
147 for (i = 0; i < loop->num_nodes; i++)
148 fprintf (file, " %d", bbs[i]->index);
149 free (bbs);
150 fprintf (file, "\n");
152 if (loop_dump_aux)
153 loop_dump_aux (loop, file, verbose);
156 /* Dump the loop information about loops to the stream FILE,
157 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
159 void
160 flow_loops_dump (FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
162 struct loop *loop;
164 if (!current_loops || ! file)
165 return;
167 fprintf (file, ";; %d loops found\n", number_of_loops (cfun));
169 FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT)
171 flow_loop_dump (loop, file, loop_dump_aux, verbose);
174 if (verbose)
175 flow_loops_cfg_dump (file);
178 /* Free data allocated for LOOP. */
180 void
181 flow_loop_free (struct loop *loop)
183 struct loop_exit *exit, *next;
185 vec_free (loop->superloops);
187 /* Break the list of the loop exit records. They will be freed when the
188 corresponding edge is rescanned or removed, and this avoids
189 accessing the (already released) head of the list stored in the
190 loop structure. */
191 for (exit = loop->exits->next; exit != loop->exits; exit = next)
193 next = exit->next;
194 exit->next = exit;
195 exit->prev = exit;
198 ggc_free (loop->exits);
199 ggc_free (loop);
202 /* Free all the memory allocated for LOOPS. */
204 void
205 flow_loops_free (struct loops *loops)
207 if (loops->larray)
209 unsigned i;
210 loop_p loop;
212 /* Free the loop descriptors. */
213 FOR_EACH_VEC_SAFE_ELT (loops->larray, i, loop)
215 if (!loop)
216 continue;
218 flow_loop_free (loop);
221 vec_free (loops->larray);
225 /* Find the nodes contained within the LOOP with header HEADER.
226 Return the number of nodes within the loop. */
229 flow_loop_nodes_find (basic_block header, struct loop *loop)
231 vec<basic_block> stack = vNULL;
232 int num_nodes = 1;
233 edge latch;
234 edge_iterator latch_ei;
236 header->loop_father = loop;
238 FOR_EACH_EDGE (latch, latch_ei, loop->header->preds)
240 if (latch->src->loop_father == loop
241 || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header))
242 continue;
244 num_nodes++;
245 stack.safe_push (latch->src);
246 latch->src->loop_father = loop;
248 while (!stack.is_empty ())
250 basic_block node;
251 edge e;
252 edge_iterator ei;
254 node = stack.pop ();
256 FOR_EACH_EDGE (e, ei, node->preds)
258 basic_block ancestor = e->src;
260 if (ancestor->loop_father != loop)
262 ancestor->loop_father = loop;
263 num_nodes++;
264 stack.safe_push (ancestor);
269 stack.release ();
271 return num_nodes;
274 /* Records the vector of superloops of the loop LOOP, whose immediate
275 superloop is FATHER. */
277 static void
278 establish_preds (struct loop *loop, struct loop *father)
280 loop_p ploop;
281 unsigned depth = loop_depth (father) + 1;
282 unsigned i;
284 loop->superloops = 0;
285 vec_alloc (loop->superloops, depth);
286 FOR_EACH_VEC_SAFE_ELT (father->superloops, i, ploop)
287 loop->superloops->quick_push (ploop);
288 loop->superloops->quick_push (father);
290 for (ploop = loop->inner; ploop; ploop = ploop->next)
291 establish_preds (ploop, loop);
294 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
295 added loop. If LOOP has some children, take care of that their
296 pred field will be initialized correctly. */
298 void
299 flow_loop_tree_node_add (struct loop *father, struct loop *loop)
301 loop->next = father->inner;
302 father->inner = loop;
304 establish_preds (loop, father);
307 /* Remove LOOP from the loop hierarchy tree. */
309 void
310 flow_loop_tree_node_remove (struct loop *loop)
312 struct loop *prev, *father;
314 father = loop_outer (loop);
316 /* Remove loop from the list of sons. */
317 if (father->inner == loop)
318 father->inner = loop->next;
319 else
321 for (prev = father->inner; prev->next != loop; prev = prev->next)
322 continue;
323 prev->next = loop->next;
326 loop->superloops = NULL;
329 /* Allocates and returns new loop structure. */
331 struct loop *
332 alloc_loop (void)
334 struct loop *loop = ggc_cleared_alloc<struct loop> ();
336 loop->exits = ggc_cleared_alloc<loop_exit> ();
337 loop->exits->next = loop->exits->prev = loop->exits;
338 loop->can_be_parallel = false;
339 loop->nb_iterations_upper_bound = 0;
340 loop->nb_iterations_estimate = 0;
341 return loop;
344 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
345 (including the root of the loop tree). */
347 void
348 init_loops_structure (struct function *fn,
349 struct loops *loops, unsigned num_loops)
351 struct loop *root;
353 memset (loops, 0, sizeof *loops);
354 vec_alloc (loops->larray, num_loops);
356 /* Dummy loop containing whole function. */
357 root = alloc_loop ();
358 root->num_nodes = n_basic_blocks_for_fn (fn);
359 root->latch = EXIT_BLOCK_PTR_FOR_FN (fn);
360 root->header = ENTRY_BLOCK_PTR_FOR_FN (fn);
361 ENTRY_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
362 EXIT_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
364 loops->larray->quick_push (root);
365 loops->tree_root = root;
368 /* Returns whether HEADER is a loop header. */
370 bool
371 bb_loop_header_p (basic_block header)
373 edge_iterator ei;
374 edge e;
376 /* If we have an abnormal predecessor, do not consider the
377 loop (not worth the problems). */
378 if (bb_has_abnormal_pred (header))
379 return false;
381 /* Look for back edges where a predecessor is dominated
382 by this block. A natural loop has a single entry
383 node (header) that dominates all the nodes in the
384 loop. It also has single back edge to the header
385 from a latch node. */
386 FOR_EACH_EDGE (e, ei, header->preds)
388 basic_block latch = e->src;
389 if (latch != ENTRY_BLOCK_PTR_FOR_FN (cfun)
390 && dominated_by_p (CDI_DOMINATORS, latch, header))
391 return true;
394 return false;
397 /* Find all the natural loops in the function and save in LOOPS structure and
398 recalculate loop_father information in basic block structures.
399 If LOOPS is non-NULL then the loop structures for already recorded loops
400 will be re-used and their number will not change. We assume that no
401 stale loops exist in LOOPS.
402 When LOOPS is NULL it is allocated and re-built from scratch.
403 Return the built LOOPS structure. */
405 struct loops *
406 flow_loops_find (struct loops *loops)
408 bool from_scratch = (loops == NULL);
409 int *rc_order;
410 int b;
411 unsigned i;
413 /* Ensure that the dominators are computed. */
414 calculate_dominance_info (CDI_DOMINATORS);
416 if (!loops)
418 loops = ggc_cleared_alloc<struct loops> ();
419 init_loops_structure (cfun, loops, 1);
422 /* Ensure that loop exits were released. */
423 gcc_assert (loops->exits == NULL);
425 /* Taking care of this degenerate case makes the rest of
426 this code simpler. */
427 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
428 return loops;
430 /* The root loop node contains all basic-blocks. */
431 loops->tree_root->num_nodes = n_basic_blocks_for_fn (cfun);
433 /* Compute depth first search order of the CFG so that outer
434 natural loops will be found before inner natural loops. */
435 rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
436 pre_and_rev_post_order_compute (NULL, rc_order, false);
438 /* Gather all loop headers in reverse completion order and allocate
439 loop structures for loops that are not already present. */
440 auto_vec<loop_p> larray (loops->larray->length ());
441 for (b = 0; b < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; b++)
443 basic_block header = BASIC_BLOCK_FOR_FN (cfun, rc_order[b]);
444 if (bb_loop_header_p (header))
446 struct loop *loop;
448 /* The current active loop tree has valid loop-fathers for
449 header blocks. */
450 if (!from_scratch
451 && header->loop_father->header == header)
453 loop = header->loop_father;
454 /* If we found an existing loop remove it from the
455 loop tree. It is going to be inserted again
456 below. */
457 flow_loop_tree_node_remove (loop);
459 else
461 /* Otherwise allocate a new loop structure for the loop. */
462 loop = alloc_loop ();
463 /* ??? We could re-use unused loop slots here. */
464 loop->num = loops->larray->length ();
465 vec_safe_push (loops->larray, loop);
466 loop->header = header;
468 if (!from_scratch
469 && dump_file && (dump_flags & TDF_DETAILS))
470 fprintf (dump_file, "flow_loops_find: discovered new "
471 "loop %d with header %d\n",
472 loop->num, header->index);
474 /* Reset latch, we recompute it below. */
475 loop->latch = NULL;
476 larray.safe_push (loop);
479 /* Make blocks part of the loop root node at start. */
480 header->loop_father = loops->tree_root;
483 free (rc_order);
485 /* Now iterate over the loops found, insert them into the loop tree
486 and assign basic-block ownership. */
487 for (i = 0; i < larray.length (); ++i)
489 struct loop *loop = larray[i];
490 basic_block header = loop->header;
491 edge_iterator ei;
492 edge e;
494 flow_loop_tree_node_add (header->loop_father, loop);
495 loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
497 /* Look for the latch for this header block, if it has just a
498 single one. */
499 FOR_EACH_EDGE (e, ei, header->preds)
501 basic_block latch = e->src;
503 if (flow_bb_inside_loop_p (loop, latch))
505 if (loop->latch != NULL)
507 /* More than one latch edge. */
508 loop->latch = NULL;
509 break;
511 loop->latch = latch;
516 return loops;
519 /* Ratio of frequencies of edges so that one of more latch edges is
520 considered to belong to inner loop with same header. */
521 #define HEAVY_EDGE_RATIO 8
523 /* Minimum number of samples for that we apply
524 find_subloop_latch_edge_by_profile heuristics. */
525 #define HEAVY_EDGE_MIN_SAMPLES 10
527 /* If the profile info is available, finds an edge in LATCHES that much more
528 frequent than the remaining edges. Returns such an edge, or NULL if we do
529 not find one.
531 We do not use guessed profile here, only the measured one. The guessed
532 profile is usually too flat and unreliable for this (and it is mostly based
533 on the loop structure of the program, so it does not make much sense to
534 derive the loop structure from it). */
536 static edge
537 find_subloop_latch_edge_by_profile (vec<edge> latches)
539 unsigned i;
540 edge e, me = NULL;
541 gcov_type mcount = 0, tcount = 0;
543 FOR_EACH_VEC_ELT (latches, i, e)
545 if (e->count > mcount)
547 me = e;
548 mcount = e->count;
550 tcount += e->count;
553 if (tcount < HEAVY_EDGE_MIN_SAMPLES
554 || (tcount - mcount) * HEAVY_EDGE_RATIO > tcount)
555 return NULL;
557 if (dump_file)
558 fprintf (dump_file,
559 "Found latch edge %d -> %d using profile information.\n",
560 me->src->index, me->dest->index);
561 return me;
564 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
565 on the structure of induction variables. Returns this edge, or NULL if we
566 do not find any.
568 We are quite conservative, and look just for an obvious simple innermost
569 loop (which is the case where we would lose the most performance by not
570 disambiguating the loop). More precisely, we look for the following
571 situation: The source of the chosen latch edge dominates sources of all
572 the other latch edges. Additionally, the header does not contain a phi node
573 such that the argument from the chosen edge is equal to the argument from
574 another edge. */
576 static edge
577 find_subloop_latch_edge_by_ivs (struct loop *loop ATTRIBUTE_UNUSED, vec<edge> latches)
579 edge e, latch = latches[0];
580 unsigned i;
581 gimple phi;
582 gimple_stmt_iterator psi;
583 tree lop;
584 basic_block bb;
586 /* Find the candidate for the latch edge. */
587 for (i = 1; latches.iterate (i, &e); i++)
588 if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src))
589 latch = e;
591 /* Verify that it dominates all the latch edges. */
592 FOR_EACH_VEC_ELT (latches, i, e)
593 if (!dominated_by_p (CDI_DOMINATORS, e->src, latch->src))
594 return NULL;
596 /* Check for a phi node that would deny that this is a latch edge of
597 a subloop. */
598 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
600 phi = gsi_stmt (psi);
601 lop = PHI_ARG_DEF_FROM_EDGE (phi, latch);
603 /* Ignore the values that are not changed inside the subloop. */
604 if (TREE_CODE (lop) != SSA_NAME
605 || SSA_NAME_DEF_STMT (lop) == phi)
606 continue;
607 bb = gimple_bb (SSA_NAME_DEF_STMT (lop));
608 if (!bb || !flow_bb_inside_loop_p (loop, bb))
609 continue;
611 FOR_EACH_VEC_ELT (latches, i, e)
612 if (e != latch
613 && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop)
614 return NULL;
617 if (dump_file)
618 fprintf (dump_file,
619 "Found latch edge %d -> %d using iv structure.\n",
620 latch->src->index, latch->dest->index);
621 return latch;
624 /* If we can determine that one of the several latch edges of LOOP behaves
625 as a latch edge of a separate subloop, returns this edge. Otherwise
626 returns NULL. */
628 static edge
629 find_subloop_latch_edge (struct loop *loop)
631 vec<edge> latches = get_loop_latch_edges (loop);
632 edge latch = NULL;
634 if (latches.length () > 1)
636 latch = find_subloop_latch_edge_by_profile (latches);
638 if (!latch
639 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
640 should use cfghook for this, but it is hard to imagine it would
641 be useful elsewhere. */
642 && current_ir_type () == IR_GIMPLE)
643 latch = find_subloop_latch_edge_by_ivs (loop, latches);
646 latches.release ();
647 return latch;
650 /* Callback for make_forwarder_block. Returns true if the edge E is marked
651 in the set MFB_REIS_SET. */
653 static hash_set<edge> *mfb_reis_set;
654 static bool
655 mfb_redirect_edges_in_set (edge e)
657 return mfb_reis_set->contains (e);
660 /* Creates a subloop of LOOP with latch edge LATCH. */
662 static void
663 form_subloop (struct loop *loop, edge latch)
665 edge_iterator ei;
666 edge e, new_entry;
667 struct loop *new_loop;
669 mfb_reis_set = new hash_set<edge>;
670 FOR_EACH_EDGE (e, ei, loop->header->preds)
672 if (e != latch)
673 mfb_reis_set->add (e);
675 new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
676 NULL);
677 delete mfb_reis_set;
679 loop->header = new_entry->src;
681 /* Find the blocks and subloops that belong to the new loop, and add it to
682 the appropriate place in the loop tree. */
683 new_loop = alloc_loop ();
684 new_loop->header = new_entry->dest;
685 new_loop->latch = latch->src;
686 add_loop (new_loop, loop);
689 /* Make all the latch edges of LOOP to go to a single forwarder block --
690 a new latch of LOOP. */
692 static void
693 merge_latch_edges (struct loop *loop)
695 vec<edge> latches = get_loop_latch_edges (loop);
696 edge latch, e;
697 unsigned i;
699 gcc_assert (latches.length () > 0);
701 if (latches.length () == 1)
702 loop->latch = latches[0]->src;
703 else
705 if (dump_file)
706 fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num);
708 mfb_reis_set = new hash_set<edge>;
709 FOR_EACH_VEC_ELT (latches, i, e)
710 mfb_reis_set->add (e);
711 latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
712 NULL);
713 delete mfb_reis_set;
715 loop->header = latch->dest;
716 loop->latch = latch->src;
719 latches.release ();
722 /* LOOP may have several latch edges. Transform it into (possibly several)
723 loops with single latch edge. */
725 static void
726 disambiguate_multiple_latches (struct loop *loop)
728 edge e;
730 /* We eliminate the multiple latches by splitting the header to the forwarder
731 block F and the rest R, and redirecting the edges. There are two cases:
733 1) If there is a latch edge E that corresponds to a subloop (we guess
734 that based on profile -- if it is taken much more often than the
735 remaining edges; and on trees, using the information about induction
736 variables of the loops), we redirect E to R, all the remaining edges to
737 F, then rescan the loops and try again for the outer loop.
738 2) If there is no such edge, we redirect all latch edges to F, and the
739 entry edges to R, thus making F the single latch of the loop. */
741 if (dump_file)
742 fprintf (dump_file, "Disambiguating loop %d with multiple latches\n",
743 loop->num);
745 /* During latch merging, we may need to redirect the entry edges to a new
746 block. This would cause problems if the entry edge was the one from the
747 entry block. To avoid having to handle this case specially, split
748 such entry edge. */
749 e = find_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), loop->header);
750 if (e)
751 split_edge (e);
753 while (1)
755 e = find_subloop_latch_edge (loop);
756 if (!e)
757 break;
759 form_subloop (loop, e);
762 merge_latch_edges (loop);
765 /* Split loops with multiple latch edges. */
767 void
768 disambiguate_loops_with_multiple_latches (void)
770 struct loop *loop;
772 FOR_EACH_LOOP (loop, 0)
774 if (!loop->latch)
775 disambiguate_multiple_latches (loop);
779 /* Return nonzero if basic block BB belongs to LOOP. */
780 bool
781 flow_bb_inside_loop_p (const struct loop *loop, const_basic_block bb)
783 struct loop *source_loop;
785 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
786 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
787 return 0;
789 source_loop = bb->loop_father;
790 return loop == source_loop || flow_loop_nested_p (loop, source_loop);
793 /* Enumeration predicate for get_loop_body_with_size. */
794 static bool
795 glb_enum_p (const_basic_block bb, const void *glb_loop)
797 const struct loop *const loop = (const struct loop *) glb_loop;
798 return (bb != loop->header
799 && dominated_by_p (CDI_DOMINATORS, bb, loop->header));
802 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
803 order against direction of edges from latch. Specially, if
804 header != latch, latch is the 1-st block. LOOP cannot be the fake
805 loop tree root, and its size must be at most MAX_SIZE. The blocks
806 in the LOOP body are stored to BODY, and the size of the LOOP is
807 returned. */
809 unsigned
810 get_loop_body_with_size (const struct loop *loop, basic_block *body,
811 unsigned max_size)
813 return dfs_enumerate_from (loop->header, 1, glb_enum_p,
814 body, max_size, loop);
817 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
818 order against direction of edges from latch. Specially, if
819 header != latch, latch is the 1-st block. */
821 basic_block *
822 get_loop_body (const struct loop *loop)
824 basic_block *body, bb;
825 unsigned tv = 0;
827 gcc_assert (loop->num_nodes);
829 body = XNEWVEC (basic_block, loop->num_nodes);
831 if (loop->latch == EXIT_BLOCK_PTR_FOR_FN (cfun))
833 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
834 special-case the fake loop that contains the whole function. */
835 gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks_for_fn (cfun));
836 body[tv++] = loop->header;
837 body[tv++] = EXIT_BLOCK_PTR_FOR_FN (cfun);
838 FOR_EACH_BB_FN (bb, cfun)
839 body[tv++] = bb;
841 else
842 tv = get_loop_body_with_size (loop, body, loop->num_nodes);
844 gcc_assert (tv == loop->num_nodes);
845 return body;
848 /* Fills dominance descendants inside LOOP of the basic block BB into
849 array TOVISIT from index *TV. */
851 static void
852 fill_sons_in_loop (const struct loop *loop, basic_block bb,
853 basic_block *tovisit, int *tv)
855 basic_block son, postpone = NULL;
857 tovisit[(*tv)++] = bb;
858 for (son = first_dom_son (CDI_DOMINATORS, bb);
859 son;
860 son = next_dom_son (CDI_DOMINATORS, son))
862 if (!flow_bb_inside_loop_p (loop, son))
863 continue;
865 if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
867 postpone = son;
868 continue;
870 fill_sons_in_loop (loop, son, tovisit, tv);
873 if (postpone)
874 fill_sons_in_loop (loop, postpone, tovisit, tv);
877 /* Gets body of a LOOP (that must be different from the outermost loop)
878 sorted by dominance relation. Additionally, if a basic block s dominates
879 the latch, then only blocks dominated by s are be after it. */
881 basic_block *
882 get_loop_body_in_dom_order (const struct loop *loop)
884 basic_block *tovisit;
885 int tv;
887 gcc_assert (loop->num_nodes);
889 tovisit = XNEWVEC (basic_block, loop->num_nodes);
891 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
893 tv = 0;
894 fill_sons_in_loop (loop, loop->header, tovisit, &tv);
896 gcc_assert (tv == (int) loop->num_nodes);
898 return tovisit;
901 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
903 basic_block *
904 get_loop_body_in_custom_order (const struct loop *loop,
905 int (*bb_comparator) (const void *, const void *))
907 basic_block *bbs = get_loop_body (loop);
909 qsort (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator);
911 return bbs;
914 /* Get body of a LOOP in breadth first sort order. */
916 basic_block *
917 get_loop_body_in_bfs_order (const struct loop *loop)
919 basic_block *blocks;
920 basic_block bb;
921 bitmap visited;
922 unsigned int i = 0;
923 unsigned int vc = 1;
925 gcc_assert (loop->num_nodes);
926 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
928 blocks = XNEWVEC (basic_block, loop->num_nodes);
929 visited = BITMAP_ALLOC (NULL);
931 bb = loop->header;
932 while (i < loop->num_nodes)
934 edge e;
935 edge_iterator ei;
937 if (bitmap_set_bit (visited, bb->index))
938 /* This basic block is now visited */
939 blocks[i++] = bb;
941 FOR_EACH_EDGE (e, ei, bb->succs)
943 if (flow_bb_inside_loop_p (loop, e->dest))
945 if (bitmap_set_bit (visited, e->dest->index))
946 blocks[i++] = e->dest;
950 gcc_assert (i >= vc);
952 bb = blocks[vc++];
955 BITMAP_FREE (visited);
956 return blocks;
959 /* Hash function for struct loop_exit. */
961 static hashval_t
962 loop_exit_hash (const void *ex)
964 const struct loop_exit *const exit = (const struct loop_exit *) ex;
966 return htab_hash_pointer (exit->e);
969 /* Equality function for struct loop_exit. Compares with edge. */
971 static int
972 loop_exit_eq (const void *ex, const void *e)
974 const struct loop_exit *const exit = (const struct loop_exit *) ex;
976 return exit->e == e;
979 /* Frees the list of loop exit descriptions EX. */
981 static void
982 loop_exit_free (void *ex)
984 struct loop_exit *exit = (struct loop_exit *) ex, *next;
986 for (; exit; exit = next)
988 next = exit->next_e;
990 exit->next->prev = exit->prev;
991 exit->prev->next = exit->next;
993 ggc_free (exit);
997 /* Returns the list of records for E as an exit of a loop. */
999 static struct loop_exit *
1000 get_exit_descriptions (edge e)
1002 return (struct loop_exit *) htab_find_with_hash (current_loops->exits, e,
1003 htab_hash_pointer (e));
1006 /* Updates the lists of loop exits in that E appears.
1007 If REMOVED is true, E is being removed, and we
1008 just remove it from the lists of exits.
1009 If NEW_EDGE is true and E is not a loop exit, we
1010 do not try to remove it from loop exit lists. */
1012 void
1013 rescan_loop_exit (edge e, bool new_edge, bool removed)
1015 void **slot;
1016 struct loop_exit *exits = NULL, *exit;
1017 struct loop *aloop, *cloop;
1019 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1020 return;
1022 if (!removed
1023 && e->src->loop_father != NULL
1024 && e->dest->loop_father != NULL
1025 && !flow_bb_inside_loop_p (e->src->loop_father, e->dest))
1027 cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
1028 for (aloop = e->src->loop_father;
1029 aloop != cloop;
1030 aloop = loop_outer (aloop))
1032 exit = ggc_alloc<loop_exit> ();
1033 exit->e = e;
1035 exit->next = aloop->exits->next;
1036 exit->prev = aloop->exits;
1037 exit->next->prev = exit;
1038 exit->prev->next = exit;
1040 exit->next_e = exits;
1041 exits = exit;
1045 if (!exits && new_edge)
1046 return;
1048 slot = htab_find_slot_with_hash (current_loops->exits, e,
1049 htab_hash_pointer (e),
1050 exits ? INSERT : NO_INSERT);
1051 if (!slot)
1052 return;
1054 if (exits)
1056 if (*slot)
1057 loop_exit_free (*slot);
1058 *slot = exits;
1060 else
1061 htab_clear_slot (current_loops->exits, slot);
1064 /* For each loop, record list of exit edges, and start maintaining these
1065 lists. */
1067 void
1068 record_loop_exits (void)
1070 basic_block bb;
1071 edge_iterator ei;
1072 edge e;
1074 if (!current_loops)
1075 return;
1077 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1078 return;
1079 loops_state_set (LOOPS_HAVE_RECORDED_EXITS);
1081 gcc_assert (current_loops->exits == NULL);
1082 current_loops->exits = htab_create_ggc (2 * number_of_loops (cfun),
1083 loop_exit_hash, loop_exit_eq,
1084 loop_exit_free);
1086 FOR_EACH_BB_FN (bb, cfun)
1088 FOR_EACH_EDGE (e, ei, bb->succs)
1090 rescan_loop_exit (e, true, false);
1095 /* Dumps information about the exit in *SLOT to FILE.
1096 Callback for htab_traverse. */
1098 static int
1099 dump_recorded_exit (void **slot, void *file)
1101 struct loop_exit *exit = (struct loop_exit *) *slot;
1102 unsigned n = 0;
1103 edge e = exit->e;
1105 for (; exit != NULL; exit = exit->next_e)
1106 n++;
1108 fprintf ((FILE*) file, "Edge %d->%d exits %u loops\n",
1109 e->src->index, e->dest->index, n);
1111 return 1;
1114 /* Dumps the recorded exits of loops to FILE. */
1116 extern void dump_recorded_exits (FILE *);
1117 void
1118 dump_recorded_exits (FILE *file)
1120 if (!current_loops->exits)
1121 return;
1122 htab_traverse (current_loops->exits, dump_recorded_exit, file);
1125 /* Releases lists of loop exits. */
1127 void
1128 release_recorded_exits (void)
1130 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS));
1131 htab_delete (current_loops->exits);
1132 current_loops->exits = NULL;
1133 loops_state_clear (LOOPS_HAVE_RECORDED_EXITS);
1136 /* Returns the list of the exit edges of a LOOP. */
1138 vec<edge>
1139 get_loop_exit_edges (const struct loop *loop)
1141 vec<edge> edges = vNULL;
1142 edge e;
1143 unsigned i;
1144 basic_block *body;
1145 edge_iterator ei;
1146 struct loop_exit *exit;
1148 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1150 /* If we maintain the lists of exits, use them. Otherwise we must
1151 scan the body of the loop. */
1152 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1154 for (exit = loop->exits->next; exit->e; exit = exit->next)
1155 edges.safe_push (exit->e);
1157 else
1159 body = get_loop_body (loop);
1160 for (i = 0; i < loop->num_nodes; i++)
1161 FOR_EACH_EDGE (e, ei, body[i]->succs)
1163 if (!flow_bb_inside_loop_p (loop, e->dest))
1164 edges.safe_push (e);
1166 free (body);
1169 return edges;
1172 /* Counts the number of conditional branches inside LOOP. */
1174 unsigned
1175 num_loop_branches (const struct loop *loop)
1177 unsigned i, n;
1178 basic_block * body;
1180 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1182 body = get_loop_body (loop);
1183 n = 0;
1184 for (i = 0; i < loop->num_nodes; i++)
1185 if (EDGE_COUNT (body[i]->succs) >= 2)
1186 n++;
1187 free (body);
1189 return n;
1192 /* Adds basic block BB to LOOP. */
1193 void
1194 add_bb_to_loop (basic_block bb, struct loop *loop)
1196 unsigned i;
1197 loop_p ploop;
1198 edge_iterator ei;
1199 edge e;
1201 gcc_assert (bb->loop_father == NULL);
1202 bb->loop_father = loop;
1203 loop->num_nodes++;
1204 FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
1205 ploop->num_nodes++;
1207 FOR_EACH_EDGE (e, ei, bb->succs)
1209 rescan_loop_exit (e, true, false);
1211 FOR_EACH_EDGE (e, ei, bb->preds)
1213 rescan_loop_exit (e, true, false);
1217 /* Remove basic block BB from loops. */
1218 void
1219 remove_bb_from_loops (basic_block bb)
1221 unsigned i;
1222 struct loop *loop = bb->loop_father;
1223 loop_p ploop;
1224 edge_iterator ei;
1225 edge e;
1227 gcc_assert (loop != NULL);
1228 loop->num_nodes--;
1229 FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
1230 ploop->num_nodes--;
1231 bb->loop_father = NULL;
1233 FOR_EACH_EDGE (e, ei, bb->succs)
1235 rescan_loop_exit (e, false, true);
1237 FOR_EACH_EDGE (e, ei, bb->preds)
1239 rescan_loop_exit (e, false, true);
1243 /* Finds nearest common ancestor in loop tree for given loops. */
1244 struct loop *
1245 find_common_loop (struct loop *loop_s, struct loop *loop_d)
1247 unsigned sdepth, ddepth;
1249 if (!loop_s) return loop_d;
1250 if (!loop_d) return loop_s;
1252 sdepth = loop_depth (loop_s);
1253 ddepth = loop_depth (loop_d);
1255 if (sdepth < ddepth)
1256 loop_d = (*loop_d->superloops)[sdepth];
1257 else if (sdepth > ddepth)
1258 loop_s = (*loop_s->superloops)[ddepth];
1260 while (loop_s != loop_d)
1262 loop_s = loop_outer (loop_s);
1263 loop_d = loop_outer (loop_d);
1265 return loop_s;
1268 /* Removes LOOP from structures and frees its data. */
1270 void
1271 delete_loop (struct loop *loop)
1273 /* Remove the loop from structure. */
1274 flow_loop_tree_node_remove (loop);
1276 /* Remove loop from loops array. */
1277 (*current_loops->larray)[loop->num] = NULL;
1279 /* Free loop data. */
1280 flow_loop_free (loop);
1283 /* Cancels the LOOP; it must be innermost one. */
1285 static void
1286 cancel_loop (struct loop *loop)
1288 basic_block *bbs;
1289 unsigned i;
1290 struct loop *outer = loop_outer (loop);
1292 gcc_assert (!loop->inner);
1294 /* Move blocks up one level (they should be removed as soon as possible). */
1295 bbs = get_loop_body (loop);
1296 for (i = 0; i < loop->num_nodes; i++)
1297 bbs[i]->loop_father = outer;
1299 free (bbs);
1300 delete_loop (loop);
1303 /* Cancels LOOP and all its subloops. */
1304 void
1305 cancel_loop_tree (struct loop *loop)
1307 while (loop->inner)
1308 cancel_loop_tree (loop->inner);
1309 cancel_loop (loop);
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 -- the cached loop depth and loop father of each bb is correct
1320 DEBUG_FUNCTION void
1321 verify_loop_structure (void)
1323 unsigned *sizes, i, j;
1324 sbitmap irreds;
1325 basic_block bb, *bbs;
1326 struct loop *loop;
1327 int err = 0;
1328 edge e;
1329 unsigned num = number_of_loops (cfun);
1330 struct loop_exit *exit, *mexit;
1331 bool dom_available = dom_info_available_p (CDI_DOMINATORS);
1332 sbitmap visited;
1334 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP))
1336 error ("loop verification on loop tree that needs fixup");
1337 err = 1;
1340 /* We need up-to-date dominators, compute or verify them. */
1341 if (!dom_available)
1342 calculate_dominance_info (CDI_DOMINATORS);
1343 else
1344 verify_dominators (CDI_DOMINATORS);
1346 /* Check the headers. */
1347 FOR_EACH_BB_FN (bb, cfun)
1348 if (bb_loop_header_p (bb))
1350 if (bb->loop_father->header == NULL)
1352 error ("loop with header %d marked for removal", bb->index);
1353 err = 1;
1355 else if (bb->loop_father->header != bb)
1357 error ("loop with header %d not in loop tree", bb->index);
1358 err = 1;
1361 else if (bb->loop_father->header == bb)
1363 error ("non-loop with header %d not marked for removal", bb->index);
1364 err = 1;
1367 /* Check the recorded loop father and sizes of loops. */
1368 visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
1369 bitmap_clear (visited);
1370 bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
1371 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1373 unsigned n;
1375 if (loop->header == NULL)
1377 error ("removed loop %d in loop tree", loop->num);
1378 err = 1;
1379 continue;
1382 n = get_loop_body_with_size (loop, bbs, n_basic_blocks_for_fn (cfun));
1383 if (loop->num_nodes != n)
1385 error ("size of loop %d should be %d, not %d",
1386 loop->num, n, loop->num_nodes);
1387 err = 1;
1390 for (j = 0; j < n; j++)
1392 bb = bbs[j];
1394 if (!flow_bb_inside_loop_p (loop, bb))
1396 error ("bb %d does not belong to loop %d",
1397 bb->index, loop->num);
1398 err = 1;
1401 /* Ignore this block if it is in an inner loop. */
1402 if (bitmap_bit_p (visited, bb->index))
1403 continue;
1404 bitmap_set_bit (visited, bb->index);
1406 if (bb->loop_father != loop)
1408 error ("bb %d has father loop %d, should be loop %d",
1409 bb->index, bb->loop_father->num, loop->num);
1410 err = 1;
1414 free (bbs);
1415 sbitmap_free (visited);
1417 /* Check headers and latches. */
1418 FOR_EACH_LOOP (loop, 0)
1420 i = loop->num;
1421 if (loop->header == NULL)
1422 continue;
1423 if (!bb_loop_header_p (loop->header))
1425 error ("loop %d%'s header is not a loop header", i);
1426 err = 1;
1428 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
1429 && EDGE_COUNT (loop->header->preds) != 2)
1431 error ("loop %d%'s header does not have exactly 2 entries", i);
1432 err = 1;
1434 if (loop->latch)
1436 if (!find_edge (loop->latch, loop->header))
1438 error ("loop %d%'s latch does not have an edge to its header", i);
1439 err = 1;
1441 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, loop->header))
1443 error ("loop %d%'s latch is not dominated by its header", i);
1444 err = 1;
1447 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
1449 if (!single_succ_p (loop->latch))
1451 error ("loop %d%'s latch does not have exactly 1 successor", i);
1452 err = 1;
1454 if (single_succ (loop->latch) != loop->header)
1456 error ("loop %d%'s latch does not have header as successor", i);
1457 err = 1;
1459 if (loop->latch->loop_father != loop)
1461 error ("loop %d%'s latch does not belong directly to it", i);
1462 err = 1;
1465 if (loop->header->loop_father != loop)
1467 error ("loop %d%'s header does not belong directly to it", i);
1468 err = 1;
1470 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1471 && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
1473 error ("loop %d%'s latch is marked as part of irreducible region", i);
1474 err = 1;
1478 /* Check irreducible loops. */
1479 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1481 /* Record old info. */
1482 irreds = sbitmap_alloc (last_basic_block_for_fn (cfun));
1483 FOR_EACH_BB_FN (bb, cfun)
1485 edge_iterator ei;
1486 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1487 bitmap_set_bit (irreds, bb->index);
1488 else
1489 bitmap_clear_bit (irreds, bb->index);
1490 FOR_EACH_EDGE (e, ei, bb->succs)
1491 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1492 e->flags |= EDGE_ALL_FLAGS + 1;
1495 /* Recount it. */
1496 mark_irreducible_loops ();
1498 /* Compare. */
1499 FOR_EACH_BB_FN (bb, cfun)
1501 edge_iterator ei;
1503 if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1504 && !bitmap_bit_p (irreds, bb->index))
1506 error ("basic block %d should be marked irreducible", bb->index);
1507 err = 1;
1509 else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1510 && bitmap_bit_p (irreds, bb->index))
1512 error ("basic block %d should not be marked irreducible", bb->index);
1513 err = 1;
1515 FOR_EACH_EDGE (e, ei, bb->succs)
1517 if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1518 && !(e->flags & (EDGE_ALL_FLAGS + 1)))
1520 error ("edge from %d to %d should be marked irreducible",
1521 e->src->index, e->dest->index);
1522 err = 1;
1524 else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1525 && (e->flags & (EDGE_ALL_FLAGS + 1)))
1527 error ("edge from %d to %d should not be marked irreducible",
1528 e->src->index, e->dest->index);
1529 err = 1;
1531 e->flags &= ~(EDGE_ALL_FLAGS + 1);
1534 free (irreds);
1537 /* Check the recorded loop exits. */
1538 FOR_EACH_LOOP (loop, 0)
1540 if (!loop->exits || loop->exits->e != NULL)
1542 error ("corrupted head of the exits list of loop %d",
1543 loop->num);
1544 err = 1;
1546 else
1548 /* Check that the list forms a cycle, and all elements except
1549 for the head are nonnull. */
1550 for (mexit = loop->exits, exit = mexit->next, i = 0;
1551 exit->e && exit != mexit;
1552 exit = exit->next)
1554 if (i++ & 1)
1555 mexit = mexit->next;
1558 if (exit != loop->exits)
1560 error ("corrupted exits list of loop %d", loop->num);
1561 err = 1;
1565 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1567 if (loop->exits->next != loop->exits)
1569 error ("nonempty exits list of loop %d, but exits are not recorded",
1570 loop->num);
1571 err = 1;
1576 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1578 unsigned n_exits = 0, eloops;
1580 sizes = XCNEWVEC (unsigned, num);
1581 memset (sizes, 0, sizeof (unsigned) * num);
1582 FOR_EACH_BB_FN (bb, cfun)
1584 edge_iterator ei;
1585 if (bb->loop_father == current_loops->tree_root)
1586 continue;
1587 FOR_EACH_EDGE (e, ei, bb->succs)
1589 if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
1590 continue;
1592 n_exits++;
1593 exit = get_exit_descriptions (e);
1594 if (!exit)
1596 error ("exit %d->%d not recorded",
1597 e->src->index, e->dest->index);
1598 err = 1;
1600 eloops = 0;
1601 for (; exit; exit = exit->next_e)
1602 eloops++;
1604 for (loop = bb->loop_father;
1605 loop != e->dest->loop_father
1606 /* When a loop exit is also an entry edge which
1607 can happen when avoiding CFG manipulations
1608 then the last loop exited is the outer loop
1609 of the loop entered. */
1610 && loop != loop_outer (e->dest->loop_father);
1611 loop = loop_outer (loop))
1613 eloops--;
1614 sizes[loop->num]++;
1617 if (eloops != 0)
1619 error ("wrong list of exited loops for edge %d->%d",
1620 e->src->index, e->dest->index);
1621 err = 1;
1626 if (n_exits != htab_elements (current_loops->exits))
1628 error ("too many loop exits recorded");
1629 err = 1;
1632 FOR_EACH_LOOP (loop, 0)
1634 eloops = 0;
1635 for (exit = loop->exits->next; exit->e; exit = exit->next)
1636 eloops++;
1637 if (eloops != sizes[loop->num])
1639 error ("%d exits recorded for loop %d (having %d exits)",
1640 eloops, loop->num, sizes[loop->num]);
1641 err = 1;
1645 free (sizes);
1648 gcc_assert (!err);
1650 if (!dom_available)
1651 free_dominance_info (CDI_DOMINATORS);
1654 /* Returns latch edge of LOOP. */
1655 edge
1656 loop_latch_edge (const struct loop *loop)
1658 return find_edge (loop->latch, loop->header);
1661 /* Returns preheader edge of LOOP. */
1662 edge
1663 loop_preheader_edge (const struct loop *loop)
1665 edge e;
1666 edge_iterator ei;
1668 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS));
1670 FOR_EACH_EDGE (e, ei, loop->header->preds)
1671 if (e->src != loop->latch)
1672 break;
1674 return e;
1677 /* Returns true if E is an exit of LOOP. */
1679 bool
1680 loop_exit_edge_p (const struct loop *loop, const_edge e)
1682 return (flow_bb_inside_loop_p (loop, e->src)
1683 && !flow_bb_inside_loop_p (loop, e->dest));
1686 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1687 or more than one exit. If loops do not have the exits recorded, NULL
1688 is returned always. */
1690 edge
1691 single_exit (const struct loop *loop)
1693 struct loop_exit *exit = loop->exits->next;
1695 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1696 return NULL;
1698 if (exit->e && exit->next == loop->exits)
1699 return exit->e;
1700 else
1701 return NULL;
1704 /* Returns true when BB has an incoming edge exiting LOOP. */
1706 bool
1707 loop_exits_to_bb_p (struct loop *loop, basic_block bb)
1709 edge e;
1710 edge_iterator ei;
1712 FOR_EACH_EDGE (e, ei, bb->preds)
1713 if (loop_exit_edge_p (loop, e))
1714 return true;
1716 return false;
1719 /* Returns true when BB has an outgoing edge exiting LOOP. */
1721 bool
1722 loop_exits_from_bb_p (struct loop *loop, basic_block bb)
1724 edge e;
1725 edge_iterator ei;
1727 FOR_EACH_EDGE (e, ei, bb->succs)
1728 if (loop_exit_edge_p (loop, e))
1729 return true;
1731 return false;
1734 /* Return location corresponding to the loop control condition if possible. */
1736 location_t
1737 get_loop_location (struct loop *loop)
1739 rtx_insn *insn = NULL;
1740 struct niter_desc *desc = NULL;
1741 edge exit;
1743 /* For a for or while loop, we would like to return the location
1744 of the for or while statement, if possible. To do this, look
1745 for the branch guarding the loop back-edge. */
1747 /* If this is a simple loop with an in_edge, then the loop control
1748 branch is typically at the end of its source. */
1749 desc = get_simple_loop_desc (loop);
1750 if (desc->in_edge)
1752 FOR_BB_INSNS_REVERSE (desc->in_edge->src, insn)
1754 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1755 return INSN_LOCATION (insn);
1758 /* If loop has a single exit, then the loop control branch
1759 must be at the end of its source. */
1760 if ((exit = single_exit (loop)))
1762 FOR_BB_INSNS_REVERSE (exit->src, insn)
1764 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1765 return INSN_LOCATION (insn);
1768 /* Next check the latch, to see if it is non-empty. */
1769 FOR_BB_INSNS_REVERSE (loop->latch, insn)
1771 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1772 return INSN_LOCATION (insn);
1774 /* Finally, if none of the above identifies the loop control branch,
1775 return the first location in the loop header. */
1776 FOR_BB_INSNS (loop->header, insn)
1778 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1779 return INSN_LOCATION (insn);
1781 /* If all else fails, simply return the current function location. */
1782 return DECL_SOURCE_LOCATION (current_function_decl);
1785 /* Records that every statement in LOOP is executed I_BOUND times.
1786 REALISTIC is true if I_BOUND is expected to be close to the real number
1787 of iterations. UPPER is true if we are sure the loop iterates at most
1788 I_BOUND times. */
1790 void
1791 record_niter_bound (struct loop *loop, const widest_int &i_bound,
1792 bool realistic, bool upper)
1794 /* Update the bounds only when there is no previous estimation, or when the
1795 current estimation is smaller. */
1796 if (upper
1797 && (!loop->any_upper_bound
1798 || wi::ltu_p (i_bound, loop->nb_iterations_upper_bound)))
1800 loop->any_upper_bound = true;
1801 loop->nb_iterations_upper_bound = i_bound;
1803 if (realistic
1804 && (!loop->any_estimate
1805 || wi::ltu_p (i_bound, loop->nb_iterations_estimate)))
1807 loop->any_estimate = true;
1808 loop->nb_iterations_estimate = i_bound;
1811 /* If an upper bound is smaller than the realistic estimate of the
1812 number of iterations, use the upper bound instead. */
1813 if (loop->any_upper_bound
1814 && loop->any_estimate
1815 && wi::ltu_p (loop->nb_iterations_upper_bound,
1816 loop->nb_iterations_estimate))
1817 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
1820 /* Similar to get_estimated_loop_iterations, but returns the estimate only
1821 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1822 on the number of iterations of LOOP could not be derived, returns -1. */
1824 HOST_WIDE_INT
1825 get_estimated_loop_iterations_int (struct loop *loop)
1827 widest_int nit;
1828 HOST_WIDE_INT hwi_nit;
1830 if (!get_estimated_loop_iterations (loop, &nit))
1831 return -1;
1833 if (!wi::fits_shwi_p (nit))
1834 return -1;
1835 hwi_nit = nit.to_shwi ();
1837 return hwi_nit < 0 ? -1 : hwi_nit;
1840 /* Returns an upper bound on the number of executions of statements
1841 in the LOOP. For statements before the loop exit, this exceeds
1842 the number of execution of the latch by one. */
1844 HOST_WIDE_INT
1845 max_stmt_executions_int (struct loop *loop)
1847 HOST_WIDE_INT nit = get_max_loop_iterations_int (loop);
1848 HOST_WIDE_INT snit;
1850 if (nit == -1)
1851 return -1;
1853 snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
1855 /* If the computation overflows, return -1. */
1856 return snit < 0 ? -1 : snit;
1859 /* Sets NIT to the estimated number of executions of the latch of the
1860 LOOP. If we have no reliable estimate, the function returns false, otherwise
1861 returns true. */
1863 bool
1864 get_estimated_loop_iterations (struct loop *loop, widest_int *nit)
1866 /* Even if the bound is not recorded, possibly we can derrive one from
1867 profile. */
1868 if (!loop->any_estimate)
1870 if (loop->header->count)
1872 *nit = gcov_type_to_wide_int
1873 (expected_loop_iterations_unbounded (loop) + 1);
1874 return true;
1876 return false;
1879 *nit = loop->nb_iterations_estimate;
1880 return true;
1883 /* Sets NIT to an upper bound for the maximum number of executions of the
1884 latch of the LOOP. If we have no reliable estimate, the function returns
1885 false, otherwise returns true. */
1887 bool
1888 get_max_loop_iterations (struct loop *loop, widest_int *nit)
1890 if (!loop->any_upper_bound)
1891 return false;
1893 *nit = loop->nb_iterations_upper_bound;
1894 return true;
1897 /* Similar to get_max_loop_iterations, but returns the estimate only
1898 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1899 on the number of iterations of LOOP could not be derived, returns -1. */
1901 HOST_WIDE_INT
1902 get_max_loop_iterations_int (struct loop *loop)
1904 widest_int nit;
1905 HOST_WIDE_INT hwi_nit;
1907 if (!get_max_loop_iterations (loop, &nit))
1908 return -1;
1910 if (!wi::fits_shwi_p (nit))
1911 return -1;
1912 hwi_nit = nit.to_shwi ();
1914 return hwi_nit < 0 ? -1 : hwi_nit;
1917 /* Returns the loop depth of the loop BB belongs to. */
1920 bb_loop_depth (const_basic_block bb)
1922 return bb->loop_father ? loop_depth (bb->loop_father) : 0;