1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000-2013 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
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
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/>. */
22 #include "coretypes.h"
26 #include "basic-block.h"
28 #include "diagnostic-core.h"
32 #include "gimple-iterator.h"
33 #include "gimple-ssa.h"
34 #include "pointer-set.h"
38 static void flow_loops_cfg_dump (FILE *);
40 /* Dump loop related CFG information. */
43 flow_loops_cfg_dump (FILE *file
)
55 fprintf (file
, ";; %d succs { ", bb
->index
);
56 FOR_EACH_EDGE (succ
, ei
, bb
->succs
)
57 fprintf (file
, "%d ", succ
->dest
->index
);
58 fprintf (file
, "}\n");
62 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
65 flow_loop_nested_p (const struct loop
*outer
, const struct loop
*loop
)
67 unsigned odepth
= loop_depth (outer
);
69 return (loop_depth (loop
) > odepth
70 && (*loop
->superloops
)[odepth
] == outer
);
73 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
77 superloop_at_depth (struct loop
*loop
, unsigned depth
)
79 unsigned ldepth
= loop_depth (loop
);
81 gcc_assert (depth
<= ldepth
);
86 return (*loop
->superloops
)[depth
];
89 /* Returns the list of the latch edges of LOOP. */
92 get_loop_latch_edges (const struct loop
*loop
)
96 vec
<edge
> ret
= vNULL
;
98 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
100 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, loop
->header
))
107 /* Dump the loop information specified by LOOP to the stream FILE
108 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
111 flow_loop_dump (const struct loop
*loop
, FILE *file
,
112 void (*loop_dump_aux
) (const struct loop
*, FILE *, int),
120 if (! loop
|| ! loop
->header
)
123 fprintf (file
, ";;\n;; Loop %d\n", loop
->num
);
125 fprintf (file
, ";; header %d, ", loop
->header
->index
);
127 fprintf (file
, "latch %d\n", loop
->latch
->index
);
130 fprintf (file
, "multiple latches:");
131 latches
= get_loop_latch_edges (loop
);
132 FOR_EACH_VEC_ELT (latches
, i
, e
)
133 fprintf (file
, " %d", e
->src
->index
);
135 fprintf (file
, "\n");
138 fprintf (file
, ";; depth %d, outer %ld\n",
139 loop_depth (loop
), (long) (loop_outer (loop
)
140 ? loop_outer (loop
)->num
: -1));
142 fprintf (file
, ";; nodes:");
143 bbs
= get_loop_body (loop
);
144 for (i
= 0; i
< loop
->num_nodes
; i
++)
145 fprintf (file
, " %d", bbs
[i
]->index
);
147 fprintf (file
, "\n");
150 loop_dump_aux (loop
, file
, verbose
);
153 /* Dump the loop information about loops to the stream FILE,
154 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
157 flow_loops_dump (FILE *file
, void (*loop_dump_aux
) (const struct loop
*, FILE *, int), int verbose
)
162 if (!current_loops
|| ! file
)
165 fprintf (file
, ";; %d loops found\n", number_of_loops (cfun
));
167 FOR_EACH_LOOP (li
, loop
, LI_INCLUDE_ROOT
)
169 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
);
173 flow_loops_cfg_dump (file
);
176 /* Free data allocated for LOOP. */
179 flow_loop_free (struct loop
*loop
)
181 struct loop_exit
*exit
, *next
;
183 vec_free (loop
->superloops
);
185 /* Break the list of the loop exit records. They will be freed when the
186 corresponding edge is rescanned or removed, and this avoids
187 accessing the (already released) head of the list stored in the
189 for (exit
= loop
->exits
->next
; exit
!= loop
->exits
; exit
= next
)
196 ggc_free (loop
->exits
);
200 /* Free all the memory allocated for LOOPS. */
203 flow_loops_free (struct loops
*loops
)
210 /* Free the loop descriptors. */
211 FOR_EACH_VEC_SAFE_ELT (loops
->larray
, i
, loop
)
216 flow_loop_free (loop
);
219 vec_free (loops
->larray
);
223 /* Find the nodes contained within the LOOP with header HEADER.
224 Return the number of nodes within the loop. */
227 flow_loop_nodes_find (basic_block header
, struct loop
*loop
)
229 vec
<basic_block
> stack
= vNULL
;
232 edge_iterator latch_ei
;
234 header
->loop_father
= loop
;
236 FOR_EACH_EDGE (latch
, latch_ei
, loop
->header
->preds
)
238 if (latch
->src
->loop_father
== loop
239 || !dominated_by_p (CDI_DOMINATORS
, latch
->src
, loop
->header
))
243 stack
.safe_push (latch
->src
);
244 latch
->src
->loop_father
= loop
;
246 while (!stack
.is_empty ())
254 FOR_EACH_EDGE (e
, ei
, node
->preds
)
256 basic_block ancestor
= e
->src
;
258 if (ancestor
->loop_father
!= loop
)
260 ancestor
->loop_father
= loop
;
262 stack
.safe_push (ancestor
);
272 /* Records the vector of superloops of the loop LOOP, whose immediate
273 superloop is FATHER. */
276 establish_preds (struct loop
*loop
, struct loop
*father
)
279 unsigned depth
= loop_depth (father
) + 1;
282 loop
->superloops
= 0;
283 vec_alloc (loop
->superloops
, depth
);
284 FOR_EACH_VEC_SAFE_ELT (father
->superloops
, i
, ploop
)
285 loop
->superloops
->quick_push (ploop
);
286 loop
->superloops
->quick_push (father
);
288 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
289 establish_preds (ploop
, loop
);
292 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
293 added loop. If LOOP has some children, take care of that their
294 pred field will be initialized correctly. */
297 flow_loop_tree_node_add (struct loop
*father
, struct loop
*loop
)
299 loop
->next
= father
->inner
;
300 father
->inner
= loop
;
302 establish_preds (loop
, father
);
305 /* Remove LOOP from the loop hierarchy tree. */
308 flow_loop_tree_node_remove (struct loop
*loop
)
310 struct loop
*prev
, *father
;
312 father
= loop_outer (loop
);
314 /* Remove loop from the list of sons. */
315 if (father
->inner
== loop
)
316 father
->inner
= loop
->next
;
319 for (prev
= father
->inner
; prev
->next
!= loop
; prev
= prev
->next
)
321 prev
->next
= loop
->next
;
324 loop
->superloops
= NULL
;
327 /* Allocates and returns new loop structure. */
332 struct loop
*loop
= ggc_alloc_cleared_loop ();
334 loop
->exits
= ggc_alloc_cleared_loop_exit ();
335 loop
->exits
->next
= loop
->exits
->prev
= loop
->exits
;
336 loop
->can_be_parallel
= false;
337 loop
->nb_iterations_upper_bound
= 0;
338 loop
->nb_iterations_estimate
= 0;
342 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
343 (including the root of the loop tree). */
346 init_loops_structure (struct function
*fn
,
347 struct loops
*loops
, unsigned num_loops
)
351 memset (loops
, 0, sizeof *loops
);
352 vec_alloc (loops
->larray
, num_loops
);
354 /* Dummy loop containing whole function. */
355 root
= alloc_loop ();
356 root
->num_nodes
= n_basic_blocks_for_function (fn
);
357 root
->latch
= EXIT_BLOCK_PTR_FOR_FUNCTION (fn
);
358 root
->header
= ENTRY_BLOCK_PTR_FOR_FUNCTION (fn
);
359 ENTRY_BLOCK_PTR_FOR_FUNCTION (fn
)->loop_father
= root
;
360 EXIT_BLOCK_PTR_FOR_FUNCTION (fn
)->loop_father
= root
;
362 loops
->larray
->quick_push (root
);
363 loops
->tree_root
= root
;
366 /* Returns whether HEADER is a loop header. */
369 bb_loop_header_p (basic_block header
)
374 /* If we have an abnormal predecessor, do not consider the
375 loop (not worth the problems). */
376 if (bb_has_abnormal_pred (header
))
379 /* Look for back edges where a predecessor is dominated
380 by this block. A natural loop has a single entry
381 node (header) that dominates all the nodes in the
382 loop. It also has single back edge to the header
383 from a latch node. */
384 FOR_EACH_EDGE (e
, ei
, header
->preds
)
386 basic_block latch
= e
->src
;
387 if (latch
!= ENTRY_BLOCK_PTR
388 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
395 /* Find all the natural loops in the function and save in LOOPS structure and
396 recalculate loop_father information in basic block structures.
397 If LOOPS is non-NULL then the loop structures for already recorded loops
398 will be re-used and their number will not change. We assume that no
399 stale loops exist in LOOPS.
400 When LOOPS is NULL it is allocated and re-built from scratch.
401 Return the built LOOPS structure. */
404 flow_loops_find (struct loops
*loops
)
406 bool from_scratch
= (loops
== NULL
);
412 /* Ensure that the dominators are computed. */
413 calculate_dominance_info (CDI_DOMINATORS
);
417 loops
= ggc_alloc_cleared_loops ();
418 init_loops_structure (cfun
, loops
, 1);
421 /* Ensure that loop exits were released. */
422 gcc_assert (loops
->exits
== NULL
);
424 /* Taking care of this degenerate case makes the rest of
425 this code simpler. */
426 if (n_basic_blocks
== NUM_FIXED_BLOCKS
)
429 /* The root loop node contains all basic-blocks. */
430 loops
->tree_root
->num_nodes
= n_basic_blocks
;
432 /* Compute depth first search order of the CFG so that outer
433 natural loops will be found before inner natural loops. */
434 rc_order
= XNEWVEC (int, n_basic_blocks
);
435 pre_and_rev_post_order_compute (NULL
, rc_order
, false);
437 /* Gather all loop headers in reverse completion order and allocate
438 loop structures for loops that are not already present. */
439 larray
.create (loops
->larray
->length ());
440 for (b
= 0; b
< n_basic_blocks
- NUM_FIXED_BLOCKS
; b
++)
442 basic_block header
= BASIC_BLOCK (rc_order
[b
]);
443 if (bb_loop_header_p (header
))
447 /* The current active loop tree has valid loop-fathers for
450 && header
->loop_father
->header
== header
)
452 loop
= header
->loop_father
;
453 /* If we found an existing loop remove it from the
454 loop tree. It is going to be inserted again
456 flow_loop_tree_node_remove (loop
);
460 /* Otherwise allocate a new loop structure for the loop. */
461 loop
= alloc_loop ();
462 /* ??? We could re-use unused loop slots here. */
463 loop
->num
= loops
->larray
->length ();
464 vec_safe_push (loops
->larray
, loop
);
465 loop
->header
= header
;
468 && dump_file
&& (dump_flags
& TDF_DETAILS
))
469 fprintf (dump_file
, "flow_loops_find: discovered new "
470 "loop %d with header %d\n",
471 loop
->num
, header
->index
);
473 /* Reset latch, we recompute it below. */
475 larray
.safe_push (loop
);
478 /* Make blocks part of the loop root node at start. */
479 header
->loop_father
= loops
->tree_root
;
484 /* Now iterate over the loops found, insert them into the loop tree
485 and assign basic-block ownership. */
486 for (i
= 0; i
< larray
.length (); ++i
)
488 struct loop
*loop
= larray
[i
];
489 basic_block header
= loop
->header
;
493 flow_loop_tree_node_add (header
->loop_father
, loop
);
494 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
496 /* Look for the latch for this header block, if it has just a
498 FOR_EACH_EDGE (e
, ei
, header
->preds
)
500 basic_block latch
= e
->src
;
502 if (flow_bb_inside_loop_p (loop
, latch
))
504 if (loop
->latch
!= NULL
)
506 /* More than one latch edge. */
520 /* Ratio of frequencies of edges so that one of more latch edges is
521 considered to belong to inner loop with same header. */
522 #define HEAVY_EDGE_RATIO 8
524 /* Minimum number of samples for that we apply
525 find_subloop_latch_edge_by_profile heuristics. */
526 #define HEAVY_EDGE_MIN_SAMPLES 10
528 /* If the profile info is available, finds an edge in LATCHES that much more
529 frequent than the remaining edges. Returns such an edge, or NULL if we do
532 We do not use guessed profile here, only the measured one. The guessed
533 profile is usually too flat and unreliable for this (and it is mostly based
534 on the loop structure of the program, so it does not make much sense to
535 derive the loop structure from it). */
538 find_subloop_latch_edge_by_profile (vec
<edge
> latches
)
542 gcov_type mcount
= 0, tcount
= 0;
544 FOR_EACH_VEC_ELT (latches
, i
, e
)
546 if (e
->count
> mcount
)
554 if (tcount
< HEAVY_EDGE_MIN_SAMPLES
555 || (tcount
- mcount
) * HEAVY_EDGE_RATIO
> tcount
)
560 "Found latch edge %d -> %d using profile information.\n",
561 me
->src
->index
, me
->dest
->index
);
565 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
566 on the structure of induction variables. Returns this edge, or NULL if we
569 We are quite conservative, and look just for an obvious simple innermost
570 loop (which is the case where we would lose the most performance by not
571 disambiguating the loop). More precisely, we look for the following
572 situation: The source of the chosen latch edge dominates sources of all
573 the other latch edges. Additionally, the header does not contain a phi node
574 such that the argument from the chosen edge is equal to the argument from
578 find_subloop_latch_edge_by_ivs (struct loop
*loop ATTRIBUTE_UNUSED
, vec
<edge
> latches
)
580 edge e
, latch
= latches
[0];
583 gimple_stmt_iterator psi
;
587 /* Find the candidate for the latch edge. */
588 for (i
= 1; latches
.iterate (i
, &e
); i
++)
589 if (dominated_by_p (CDI_DOMINATORS
, latch
->src
, e
->src
))
592 /* Verify that it dominates all the latch edges. */
593 FOR_EACH_VEC_ELT (latches
, i
, e
)
594 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, latch
->src
))
597 /* Check for a phi node that would deny that this is a latch edge of
599 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
601 phi
= gsi_stmt (psi
);
602 lop
= PHI_ARG_DEF_FROM_EDGE (phi
, latch
);
604 /* Ignore the values that are not changed inside the subloop. */
605 if (TREE_CODE (lop
) != SSA_NAME
606 || SSA_NAME_DEF_STMT (lop
) == phi
)
608 bb
= gimple_bb (SSA_NAME_DEF_STMT (lop
));
609 if (!bb
|| !flow_bb_inside_loop_p (loop
, bb
))
612 FOR_EACH_VEC_ELT (latches
, i
, e
)
614 && PHI_ARG_DEF_FROM_EDGE (phi
, e
) == lop
)
620 "Found latch edge %d -> %d using iv structure.\n",
621 latch
->src
->index
, latch
->dest
->index
);
625 /* If we can determine that one of the several latch edges of LOOP behaves
626 as a latch edge of a separate subloop, returns this edge. Otherwise
630 find_subloop_latch_edge (struct loop
*loop
)
632 vec
<edge
> latches
= get_loop_latch_edges (loop
);
635 if (latches
.length () > 1)
637 latch
= find_subloop_latch_edge_by_profile (latches
);
640 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
641 should use cfghook for this, but it is hard to imagine it would
642 be useful elsewhere. */
643 && current_ir_type () == IR_GIMPLE
)
644 latch
= find_subloop_latch_edge_by_ivs (loop
, latches
);
651 /* Callback for make_forwarder_block. Returns true if the edge E is marked
652 in the set MFB_REIS_SET. */
654 static struct pointer_set_t
*mfb_reis_set
;
656 mfb_redirect_edges_in_set (edge e
)
658 return pointer_set_contains (mfb_reis_set
, e
);
661 /* Creates a subloop of LOOP with latch edge LATCH. */
664 form_subloop (struct loop
*loop
, edge latch
)
668 struct loop
*new_loop
;
670 mfb_reis_set
= pointer_set_create ();
671 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
674 pointer_set_insert (mfb_reis_set
, e
);
676 new_entry
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
678 pointer_set_destroy (mfb_reis_set
);
680 loop
->header
= new_entry
->src
;
682 /* Find the blocks and subloops that belong to the new loop, and add it to
683 the appropriate place in the loop tree. */
684 new_loop
= alloc_loop ();
685 new_loop
->header
= new_entry
->dest
;
686 new_loop
->latch
= latch
->src
;
687 add_loop (new_loop
, loop
);
690 /* Make all the latch edges of LOOP to go to a single forwarder block --
691 a new latch of LOOP. */
694 merge_latch_edges (struct loop
*loop
)
696 vec
<edge
> latches
= get_loop_latch_edges (loop
);
700 gcc_assert (latches
.length () > 0);
702 if (latches
.length () == 1)
703 loop
->latch
= latches
[0]->src
;
707 fprintf (dump_file
, "Merged latch edges of loop %d\n", loop
->num
);
709 mfb_reis_set
= pointer_set_create ();
710 FOR_EACH_VEC_ELT (latches
, i
, e
)
711 pointer_set_insert (mfb_reis_set
, e
);
712 latch
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
714 pointer_set_destroy (mfb_reis_set
);
716 loop
->header
= latch
->dest
;
717 loop
->latch
= latch
->src
;
723 /* LOOP may have several latch edges. Transform it into (possibly several)
724 loops with single latch edge. */
727 disambiguate_multiple_latches (struct loop
*loop
)
731 /* We eliminate the multiple latches by splitting the header to the forwarder
732 block F and the rest R, and redirecting the edges. There are two cases:
734 1) If there is a latch edge E that corresponds to a subloop (we guess
735 that based on profile -- if it is taken much more often than the
736 remaining edges; and on trees, using the information about induction
737 variables of the loops), we redirect E to R, all the remaining edges to
738 F, then rescan the loops and try again for the outer loop.
739 2) If there is no such edge, we redirect all latch edges to F, and the
740 entry edges to R, thus making F the single latch of the loop. */
743 fprintf (dump_file
, "Disambiguating loop %d with multiple latches\n",
746 /* During latch merging, we may need to redirect the entry edges to a new
747 block. This would cause problems if the entry edge was the one from the
748 entry block. To avoid having to handle this case specially, split
750 e
= find_edge (ENTRY_BLOCK_PTR
, loop
->header
);
756 e
= find_subloop_latch_edge (loop
);
760 form_subloop (loop
, e
);
763 merge_latch_edges (loop
);
766 /* Split loops with multiple latch edges. */
769 disambiguate_loops_with_multiple_latches (void)
774 FOR_EACH_LOOP (li
, loop
, 0)
777 disambiguate_multiple_latches (loop
);
781 /* Return nonzero if basic block BB belongs to LOOP. */
783 flow_bb_inside_loop_p (const struct loop
*loop
, const_basic_block bb
)
785 struct loop
*source_loop
;
787 if (bb
== ENTRY_BLOCK_PTR
|| bb
== EXIT_BLOCK_PTR
)
790 source_loop
= bb
->loop_father
;
791 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
794 /* Enumeration predicate for get_loop_body_with_size. */
796 glb_enum_p (const_basic_block bb
, const void *glb_loop
)
798 const struct loop
*const loop
= (const struct loop
*) glb_loop
;
799 return (bb
!= loop
->header
800 && dominated_by_p (CDI_DOMINATORS
, bb
, loop
->header
));
803 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
804 order against direction of edges from latch. Specially, if
805 header != latch, latch is the 1-st block. LOOP cannot be the fake
806 loop tree root, and its size must be at most MAX_SIZE. The blocks
807 in the LOOP body are stored to BODY, and the size of the LOOP is
811 get_loop_body_with_size (const struct loop
*loop
, basic_block
*body
,
814 return dfs_enumerate_from (loop
->header
, 1, glb_enum_p
,
815 body
, max_size
, loop
);
818 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
819 order against direction of edges from latch. Specially, if
820 header != latch, latch is the 1-st block. */
823 get_loop_body (const struct loop
*loop
)
825 basic_block
*body
, bb
;
828 gcc_assert (loop
->num_nodes
);
830 body
= XNEWVEC (basic_block
, loop
->num_nodes
);
832 if (loop
->latch
== EXIT_BLOCK_PTR
)
834 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
835 special-case the fake loop that contains the whole function. */
836 gcc_assert (loop
->num_nodes
== (unsigned) n_basic_blocks
);
837 body
[tv
++] = loop
->header
;
838 body
[tv
++] = EXIT_BLOCK_PTR
;
843 tv
= get_loop_body_with_size (loop
, body
, loop
->num_nodes
);
845 gcc_assert (tv
== loop
->num_nodes
);
849 /* Fills dominance descendants inside LOOP of the basic block BB into
850 array TOVISIT from index *TV. */
853 fill_sons_in_loop (const struct loop
*loop
, basic_block bb
,
854 basic_block
*tovisit
, int *tv
)
856 basic_block son
, postpone
= NULL
;
858 tovisit
[(*tv
)++] = bb
;
859 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
861 son
= next_dom_son (CDI_DOMINATORS
, son
))
863 if (!flow_bb_inside_loop_p (loop
, son
))
866 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, son
))
871 fill_sons_in_loop (loop
, son
, tovisit
, tv
);
875 fill_sons_in_loop (loop
, postpone
, tovisit
, tv
);
878 /* Gets body of a LOOP (that must be different from the outermost loop)
879 sorted by dominance relation. Additionally, if a basic block s dominates
880 the latch, then only blocks dominated by s are be after it. */
883 get_loop_body_in_dom_order (const struct loop
*loop
)
885 basic_block
*tovisit
;
888 gcc_assert (loop
->num_nodes
);
890 tovisit
= XNEWVEC (basic_block
, loop
->num_nodes
);
892 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
895 fill_sons_in_loop (loop
, loop
->header
, tovisit
, &tv
);
897 gcc_assert (tv
== (int) loop
->num_nodes
);
902 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
905 get_loop_body_in_custom_order (const struct loop
*loop
,
906 int (*bb_comparator
) (const void *, const void *))
908 basic_block
*bbs
= get_loop_body (loop
);
910 qsort (bbs
, loop
->num_nodes
, sizeof (basic_block
), bb_comparator
);
915 /* Get body of a LOOP in breadth first sort order. */
918 get_loop_body_in_bfs_order (const struct loop
*loop
)
926 gcc_assert (loop
->num_nodes
);
927 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
929 blocks
= XNEWVEC (basic_block
, loop
->num_nodes
);
930 visited
= BITMAP_ALLOC (NULL
);
933 while (i
< loop
->num_nodes
)
938 if (bitmap_set_bit (visited
, bb
->index
))
939 /* This basic block is now visited */
942 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
944 if (flow_bb_inside_loop_p (loop
, e
->dest
))
946 if (bitmap_set_bit (visited
, e
->dest
->index
))
947 blocks
[i
++] = e
->dest
;
951 gcc_assert (i
>= vc
);
956 BITMAP_FREE (visited
);
960 /* Hash function for struct loop_exit. */
963 loop_exit_hash (const void *ex
)
965 const struct loop_exit
*const exit
= (const struct loop_exit
*) ex
;
967 return htab_hash_pointer (exit
->e
);
970 /* Equality function for struct loop_exit. Compares with edge. */
973 loop_exit_eq (const void *ex
, const void *e
)
975 const struct loop_exit
*const exit
= (const struct loop_exit
*) ex
;
980 /* Frees the list of loop exit descriptions EX. */
983 loop_exit_free (void *ex
)
985 struct loop_exit
*exit
= (struct loop_exit
*) ex
, *next
;
987 for (; exit
; exit
= next
)
991 exit
->next
->prev
= exit
->prev
;
992 exit
->prev
->next
= exit
->next
;
998 /* Returns the list of records for E as an exit of a loop. */
1000 static struct loop_exit
*
1001 get_exit_descriptions (edge e
)
1003 return (struct loop_exit
*) htab_find_with_hash (current_loops
->exits
, e
,
1004 htab_hash_pointer (e
));
1007 /* Updates the lists of loop exits in that E appears.
1008 If REMOVED is true, E is being removed, and we
1009 just remove it from the lists of exits.
1010 If NEW_EDGE is true and E is not a loop exit, we
1011 do not try to remove it from loop exit lists. */
1014 rescan_loop_exit (edge e
, bool new_edge
, bool removed
)
1017 struct loop_exit
*exits
= NULL
, *exit
;
1018 struct loop
*aloop
, *cloop
;
1020 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1024 && e
->src
->loop_father
!= NULL
1025 && e
->dest
->loop_father
!= NULL
1026 && !flow_bb_inside_loop_p (e
->src
->loop_father
, e
->dest
))
1028 cloop
= find_common_loop (e
->src
->loop_father
, e
->dest
->loop_father
);
1029 for (aloop
= e
->src
->loop_father
;
1031 aloop
= loop_outer (aloop
))
1033 exit
= ggc_alloc_loop_exit ();
1036 exit
->next
= aloop
->exits
->next
;
1037 exit
->prev
= aloop
->exits
;
1038 exit
->next
->prev
= exit
;
1039 exit
->prev
->next
= exit
;
1041 exit
->next_e
= exits
;
1046 if (!exits
&& new_edge
)
1049 slot
= htab_find_slot_with_hash (current_loops
->exits
, e
,
1050 htab_hash_pointer (e
),
1051 exits
? INSERT
: NO_INSERT
);
1058 loop_exit_free (*slot
);
1062 htab_clear_slot (current_loops
->exits
, slot
);
1065 /* For each loop, record list of exit edges, and start maintaining these
1069 record_loop_exits (void)
1078 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1080 loops_state_set (LOOPS_HAVE_RECORDED_EXITS
);
1082 gcc_assert (current_loops
->exits
== NULL
);
1083 current_loops
->exits
= htab_create_ggc (2 * number_of_loops (cfun
),
1084 loop_exit_hash
, loop_exit_eq
,
1089 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1091 rescan_loop_exit (e
, true, false);
1096 /* Dumps information about the exit in *SLOT to FILE.
1097 Callback for htab_traverse. */
1100 dump_recorded_exit (void **slot
, void *file
)
1102 struct loop_exit
*exit
= (struct loop_exit
*) *slot
;
1106 for (; exit
!= NULL
; exit
= exit
->next_e
)
1109 fprintf ((FILE*) file
, "Edge %d->%d exits %u loops\n",
1110 e
->src
->index
, e
->dest
->index
, n
);
1115 /* Dumps the recorded exits of loops to FILE. */
1117 extern void dump_recorded_exits (FILE *);
1119 dump_recorded_exits (FILE *file
)
1121 if (!current_loops
->exits
)
1123 htab_traverse (current_loops
->exits
, dump_recorded_exit
, file
);
1126 /* Releases lists of loop exits. */
1129 release_recorded_exits (void)
1131 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
));
1132 htab_delete (current_loops
->exits
);
1133 current_loops
->exits
= NULL
;
1134 loops_state_clear (LOOPS_HAVE_RECORDED_EXITS
);
1137 /* Returns the list of the exit edges of a LOOP. */
1140 get_loop_exit_edges (const struct loop
*loop
)
1142 vec
<edge
> edges
= vNULL
;
1147 struct loop_exit
*exit
;
1149 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
1151 /* If we maintain the lists of exits, use them. Otherwise we must
1152 scan the body of the loop. */
1153 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1155 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1156 edges
.safe_push (exit
->e
);
1160 body
= get_loop_body (loop
);
1161 for (i
= 0; i
< loop
->num_nodes
; i
++)
1162 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
1164 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1165 edges
.safe_push (e
);
1173 /* Counts the number of conditional branches inside LOOP. */
1176 num_loop_branches (const struct loop
*loop
)
1181 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR
);
1183 body
= get_loop_body (loop
);
1185 for (i
= 0; i
< loop
->num_nodes
; i
++)
1186 if (EDGE_COUNT (body
[i
]->succs
) >= 2)
1193 /* Adds basic block BB to LOOP. */
1195 add_bb_to_loop (basic_block bb
, struct loop
*loop
)
1202 gcc_assert (bb
->loop_father
== NULL
);
1203 bb
->loop_father
= loop
;
1205 FOR_EACH_VEC_SAFE_ELT (loop
->superloops
, i
, ploop
)
1208 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1210 rescan_loop_exit (e
, true, false);
1212 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1214 rescan_loop_exit (e
, true, false);
1218 /* Remove basic block BB from loops. */
1220 remove_bb_from_loops (basic_block bb
)
1223 struct loop
*loop
= bb
->loop_father
;
1228 gcc_assert (loop
!= NULL
);
1230 FOR_EACH_VEC_SAFE_ELT (loop
->superloops
, i
, ploop
)
1232 bb
->loop_father
= NULL
;
1234 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1236 rescan_loop_exit (e
, false, true);
1238 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1240 rescan_loop_exit (e
, false, true);
1244 /* Finds nearest common ancestor in loop tree for given loops. */
1246 find_common_loop (struct loop
*loop_s
, struct loop
*loop_d
)
1248 unsigned sdepth
, ddepth
;
1250 if (!loop_s
) return loop_d
;
1251 if (!loop_d
) return loop_s
;
1253 sdepth
= loop_depth (loop_s
);
1254 ddepth
= loop_depth (loop_d
);
1256 if (sdepth
< ddepth
)
1257 loop_d
= (*loop_d
->superloops
)[sdepth
];
1258 else if (sdepth
> ddepth
)
1259 loop_s
= (*loop_s
->superloops
)[ddepth
];
1261 while (loop_s
!= loop_d
)
1263 loop_s
= loop_outer (loop_s
);
1264 loop_d
= loop_outer (loop_d
);
1269 /* Removes LOOP from structures and frees its data. */
1272 delete_loop (struct loop
*loop
)
1274 /* Remove the loop from structure. */
1275 flow_loop_tree_node_remove (loop
);
1277 /* Remove loop from loops array. */
1278 (*current_loops
->larray
)[loop
->num
] = NULL
;
1280 /* Free loop data. */
1281 flow_loop_free (loop
);
1284 /* Cancels the LOOP; it must be innermost one. */
1287 cancel_loop (struct loop
*loop
)
1291 struct loop
*outer
= loop_outer (loop
);
1293 gcc_assert (!loop
->inner
);
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
;
1304 /* Cancels LOOP and all its subloops. */
1306 cancel_loop_tree (struct loop
*loop
)
1309 cancel_loop_tree (loop
->inner
);
1313 /* Checks that information about loops is correct
1314 -- sizes of loops are all right
1315 -- results of get_loop_body really belong to the loop
1316 -- loop header have just single entry edge and single latch edge
1317 -- loop latches have only single successor that is header of their loop
1318 -- irreducible loops are correctly marked
1319 -- the cached loop depth and loop father of each bb is correct
1322 verify_loop_structure (void)
1324 unsigned *sizes
, i
, j
;
1326 basic_block bb
, *bbs
;
1330 unsigned num
= number_of_loops (cfun
);
1332 struct loop_exit
*exit
, *mexit
;
1333 bool dom_available
= dom_info_available_p (CDI_DOMINATORS
);
1336 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
1338 error ("loop verification on loop tree that needs fixup");
1342 /* We need up-to-date dominators, compute or verify them. */
1344 calculate_dominance_info (CDI_DOMINATORS
);
1346 verify_dominators (CDI_DOMINATORS
);
1348 /* Check the headers. */
1350 if (bb_loop_header_p (bb
))
1352 if (bb
->loop_father
->header
== NULL
)
1354 error ("loop with header %d marked for removal", bb
->index
);
1357 else if (bb
->loop_father
->header
!= bb
)
1359 error ("loop with header %d not in loop tree", bb
->index
);
1363 else if (bb
->loop_father
->header
== bb
)
1365 error ("non-loop with header %d not marked for removal", bb
->index
);
1369 /* Check the recorded loop father and sizes of loops. */
1370 visited
= sbitmap_alloc (last_basic_block
);
1371 bitmap_clear (visited
);
1372 bbs
= XNEWVEC (basic_block
, n_basic_blocks
);
1373 FOR_EACH_LOOP (li
, loop
, LI_FROM_INNERMOST
)
1377 if (loop
->header
== NULL
)
1379 error ("removed loop %d in loop tree", loop
->num
);
1384 n
= get_loop_body_with_size (loop
, bbs
, n_basic_blocks
);
1385 if (loop
->num_nodes
!= n
)
1387 error ("size of loop %d should be %d, not %d",
1388 loop
->num
, n
, loop
->num_nodes
);
1392 for (j
= 0; j
< n
; j
++)
1396 if (!flow_bb_inside_loop_p (loop
, bb
))
1398 error ("bb %d does not belong to loop %d",
1399 bb
->index
, loop
->num
);
1403 /* Ignore this block if it is in an inner loop. */
1404 if (bitmap_bit_p (visited
, bb
->index
))
1406 bitmap_set_bit (visited
, bb
->index
);
1408 if (bb
->loop_father
!= loop
)
1410 error ("bb %d has father loop %d, should be loop %d",
1411 bb
->index
, bb
->loop_father
->num
, loop
->num
);
1417 sbitmap_free (visited
);
1419 /* Check headers and latches. */
1420 FOR_EACH_LOOP (li
, loop
, 0)
1423 if (loop
->header
== NULL
)
1425 if (!bb_loop_header_p (loop
->header
))
1427 error ("loop %d%'s header is not a loop header", i
);
1430 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
)
1431 && EDGE_COUNT (loop
->header
->preds
) != 2)
1433 error ("loop %d%'s header does not have exactly 2 entries", i
);
1438 if (!find_edge (loop
->latch
, loop
->header
))
1440 error ("loop %d%'s latch does not have an edge to its header", i
);
1443 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, loop
->header
))
1445 error ("loop %d%'s latch is not dominated by its header", i
);
1449 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
1451 if (!single_succ_p (loop
->latch
))
1453 error ("loop %d%'s latch does not have exactly 1 successor", i
);
1456 if (single_succ (loop
->latch
) != loop
->header
)
1458 error ("loop %d%'s latch does not have header as successor", i
);
1461 if (loop
->latch
->loop_father
!= loop
)
1463 error ("loop %d%'s latch does not belong directly to it", i
);
1467 if (loop
->header
->loop_father
!= loop
)
1469 error ("loop %d%'s header does not belong directly to it", i
);
1472 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1473 && (loop_latch_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
))
1475 error ("loop %d%'s latch is marked as part of irreducible region", i
);
1480 /* Check irreducible loops. */
1481 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1483 /* Record old info. */
1484 irreds
= sbitmap_alloc (last_basic_block
);
1488 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1489 bitmap_set_bit (irreds
, bb
->index
);
1491 bitmap_clear_bit (irreds
, bb
->index
);
1492 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1493 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1494 e
->flags
|= EDGE_ALL_FLAGS
+ 1;
1498 mark_irreducible_loops ();
1505 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1506 && !bitmap_bit_p (irreds
, bb
->index
))
1508 error ("basic block %d should be marked irreducible", bb
->index
);
1511 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1512 && bitmap_bit_p (irreds
, bb
->index
))
1514 error ("basic block %d should not be marked irreducible", bb
->index
);
1517 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1519 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1520 && !(e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1522 error ("edge from %d to %d should be marked irreducible",
1523 e
->src
->index
, e
->dest
->index
);
1526 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1527 && (e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1529 error ("edge from %d to %d should not be marked irreducible",
1530 e
->src
->index
, e
->dest
->index
);
1533 e
->flags
&= ~(EDGE_ALL_FLAGS
+ 1);
1539 /* Check the recorded loop exits. */
1540 FOR_EACH_LOOP (li
, loop
, 0)
1542 if (!loop
->exits
|| loop
->exits
->e
!= NULL
)
1544 error ("corrupted head of the exits list of loop %d",
1550 /* Check that the list forms a cycle, and all elements except
1551 for the head are nonnull. */
1552 for (mexit
= loop
->exits
, exit
= mexit
->next
, i
= 0;
1553 exit
->e
&& exit
!= mexit
;
1557 mexit
= mexit
->next
;
1560 if (exit
!= loop
->exits
)
1562 error ("corrupted exits list of loop %d", loop
->num
);
1567 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1569 if (loop
->exits
->next
!= loop
->exits
)
1571 error ("nonempty exits list of loop %d, but exits are not recorded",
1578 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1580 unsigned n_exits
= 0, eloops
;
1582 sizes
= XCNEWVEC (unsigned, num
);
1583 memset (sizes
, 0, sizeof (unsigned) * num
);
1587 if (bb
->loop_father
== current_loops
->tree_root
)
1589 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1591 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
1595 exit
= get_exit_descriptions (e
);
1598 error ("exit %d->%d not recorded",
1599 e
->src
->index
, e
->dest
->index
);
1603 for (; exit
; exit
= exit
->next_e
)
1606 for (loop
= bb
->loop_father
;
1607 loop
!= e
->dest
->loop_father
1608 /* When a loop exit is also an entry edge which
1609 can happen when avoiding CFG manipulations
1610 then the last loop exited is the outer loop
1611 of the loop entered. */
1612 && loop
!= loop_outer (e
->dest
->loop_father
);
1613 loop
= loop_outer (loop
))
1621 error ("wrong list of exited loops for edge %d->%d",
1622 e
->src
->index
, e
->dest
->index
);
1628 if (n_exits
!= htab_elements (current_loops
->exits
))
1630 error ("too many loop exits recorded");
1634 FOR_EACH_LOOP (li
, loop
, 0)
1637 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1639 if (eloops
!= sizes
[loop
->num
])
1641 error ("%d exits recorded for loop %d (having %d exits)",
1642 eloops
, loop
->num
, sizes
[loop
->num
]);
1653 free_dominance_info (CDI_DOMINATORS
);
1656 /* Returns latch edge of LOOP. */
1658 loop_latch_edge (const struct loop
*loop
)
1660 return find_edge (loop
->latch
, loop
->header
);
1663 /* Returns preheader edge of LOOP. */
1665 loop_preheader_edge (const struct loop
*loop
)
1670 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
));
1672 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1673 if (e
->src
!= loop
->latch
)
1679 /* Returns true if E is an exit of LOOP. */
1682 loop_exit_edge_p (const struct loop
*loop
, const_edge e
)
1684 return (flow_bb_inside_loop_p (loop
, e
->src
)
1685 && !flow_bb_inside_loop_p (loop
, e
->dest
));
1688 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1689 or more than one exit. If loops do not have the exits recorded, NULL
1690 is returned always. */
1693 single_exit (const struct loop
*loop
)
1695 struct loop_exit
*exit
= loop
->exits
->next
;
1697 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1700 if (exit
->e
&& exit
->next
== loop
->exits
)
1706 /* Returns true when BB has an incoming edge exiting LOOP. */
1709 loop_exits_to_bb_p (struct loop
*loop
, basic_block bb
)
1714 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1715 if (loop_exit_edge_p (loop
, e
))
1721 /* Returns true when BB has an outgoing edge exiting LOOP. */
1724 loop_exits_from_bb_p (struct loop
*loop
, basic_block bb
)
1729 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1730 if (loop_exit_edge_p (loop
, e
))
1736 /* Return location corresponding to the loop control condition if possible. */
1739 get_loop_location (struct loop
*loop
)
1742 struct niter_desc
*desc
= NULL
;
1745 /* For a for or while loop, we would like to return the location
1746 of the for or while statement, if possible. To do this, look
1747 for the branch guarding the loop back-edge. */
1749 /* If this is a simple loop with an in_edge, then the loop control
1750 branch is typically at the end of its source. */
1751 desc
= get_simple_loop_desc (loop
);
1754 FOR_BB_INSNS_REVERSE (desc
->in_edge
->src
, insn
)
1756 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1757 return INSN_LOCATION (insn
);
1760 /* If loop has a single exit, then the loop control branch
1761 must be at the end of its source. */
1762 if ((exit
= single_exit (loop
)))
1764 FOR_BB_INSNS_REVERSE (exit
->src
, insn
)
1766 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1767 return INSN_LOCATION (insn
);
1770 /* Next check the latch, to see if it is non-empty. */
1771 FOR_BB_INSNS_REVERSE (loop
->latch
, insn
)
1773 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1774 return INSN_LOCATION (insn
);
1776 /* Finally, if none of the above identifies the loop control branch,
1777 return the first location in the loop header. */
1778 FOR_BB_INSNS (loop
->header
, insn
)
1780 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1781 return INSN_LOCATION (insn
);
1783 /* If all else fails, simply return the current function location. */
1784 return DECL_SOURCE_LOCATION (current_function_decl
);
1787 /* Records that every statement in LOOP is executed I_BOUND times.
1788 REALISTIC is true if I_BOUND is expected to be close to the real number
1789 of iterations. UPPER is true if we are sure the loop iterates at most
1793 record_niter_bound (struct loop
*loop
, const widest_int
&i_bound
,
1794 bool realistic
, bool upper
)
1796 /* Update the bounds only when there is no previous estimation, or when the
1797 current estimation is smaller. */
1799 && (!loop
->any_upper_bound
1800 || wi::ltu_p (i_bound
, loop
->nb_iterations_upper_bound
)))
1802 loop
->any_upper_bound
= true;
1803 loop
->nb_iterations_upper_bound
= i_bound
;
1806 && (!loop
->any_estimate
1807 || wi::ltu_p (i_bound
, loop
->nb_iterations_estimate
)))
1809 loop
->any_estimate
= true;
1810 loop
->nb_iterations_estimate
= i_bound
;
1813 /* If an upper bound is smaller than the realistic estimate of the
1814 number of iterations, use the upper bound instead. */
1815 if (loop
->any_upper_bound
1816 && loop
->any_estimate
1817 && wi::ltu_p (loop
->nb_iterations_upper_bound
,
1818 loop
->nb_iterations_estimate
))
1819 loop
->nb_iterations_estimate
= loop
->nb_iterations_upper_bound
;
1822 /* Similar to get_estimated_loop_iterations, but returns the estimate only
1823 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1824 on the number of iterations of LOOP could not be derived, returns -1. */
1827 get_estimated_loop_iterations_int (struct loop
*loop
)
1830 HOST_WIDE_INT hwi_nit
;
1832 if (!get_estimated_loop_iterations (loop
, &nit
))
1835 if (!wi::fits_shwi_p (nit
))
1837 hwi_nit
= nit
.to_shwi ();
1839 return hwi_nit
< 0 ? -1 : hwi_nit
;
1842 /* Returns an upper bound on the number of executions of statements
1843 in the LOOP. For statements before the loop exit, this exceeds
1844 the number of execution of the latch by one. */
1847 max_stmt_executions_int (struct loop
*loop
)
1849 HOST_WIDE_INT nit
= get_max_loop_iterations_int (loop
);
1855 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
1857 /* If the computation overflows, return -1. */
1858 return snit
< 0 ? -1 : snit
;
1861 /* Sets NIT to the estimated number of executions of the latch of the
1862 LOOP. If we have no reliable estimate, the function returns false, otherwise
1866 get_estimated_loop_iterations (struct loop
*loop
, widest_int
*nit
)
1868 /* Even if the bound is not recorded, possibly we can derrive one from
1870 if (!loop
->any_estimate
)
1872 if (loop
->header
->count
)
1874 *nit
= gcov_type_to_wide_int
1875 (expected_loop_iterations_unbounded (loop
) + 1);
1881 *nit
= loop
->nb_iterations_estimate
;
1885 /* Sets NIT to an upper bound for the maximum number of executions of the
1886 latch of the LOOP. If we have no reliable estimate, the function returns
1887 false, otherwise returns true. */
1890 get_max_loop_iterations (struct loop
*loop
, widest_int
*nit
)
1892 if (!loop
->any_upper_bound
)
1895 *nit
= loop
->nb_iterations_upper_bound
;
1899 /* Similar to get_max_loop_iterations, but returns the estimate only
1900 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1901 on the number of iterations of LOOP could not be derived, returns -1. */
1904 get_max_loop_iterations_int (struct loop
*loop
)
1907 HOST_WIDE_INT hwi_nit
;
1909 if (!get_max_loop_iterations (loop
, &nit
))
1912 if (!wi::fits_shwi_p (nit
))
1914 hwi_nit
= nit
.to_shwi ();
1916 return hwi_nit
< 0 ? -1 : hwi_nit
;
1919 /* Returns the loop depth of the loop BB belongs to. */
1922 bb_loop_depth (const_basic_block bb
)
1924 return bb
->loop_father
? loop_depth (bb
->loop_father
) : 0;