1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000-2015 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"
29 #include "diagnostic-core.h"
31 #include "fold-const.h"
32 #include "internal-fn.h"
33 #include "gimple-iterator.h"
34 #include "gimple-ssa.h"
37 static void flow_loops_cfg_dump (FILE *);
39 /* Dump loop related CFG information. */
42 flow_loops_cfg_dump (FILE *file
)
49 FOR_EACH_BB_FN (bb
, cfun
)
54 fprintf (file
, ";; %d succs { ", bb
->index
);
55 FOR_EACH_EDGE (succ
, ei
, bb
->succs
)
56 fprintf (file
, "%d ", succ
->dest
->index
);
57 fprintf (file
, "}\n");
61 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
64 flow_loop_nested_p (const struct loop
*outer
, const struct loop
*loop
)
66 unsigned odepth
= loop_depth (outer
);
68 return (loop_depth (loop
) > odepth
69 && (*loop
->superloops
)[odepth
] == outer
);
72 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
76 superloop_at_depth (struct loop
*loop
, unsigned depth
)
78 unsigned ldepth
= loop_depth (loop
);
80 gcc_assert (depth
<= ldepth
);
85 return (*loop
->superloops
)[depth
];
88 /* Returns the list of the latch edges of LOOP. */
91 get_loop_latch_edges (const struct loop
*loop
)
95 vec
<edge
> ret
= vNULL
;
97 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
99 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, loop
->header
))
106 /* Dump the loop information specified by LOOP to the stream FILE
107 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
110 flow_loop_dump (const struct loop
*loop
, FILE *file
,
111 void (*loop_dump_aux
) (const struct loop
*, FILE *, int),
119 if (! loop
|| ! loop
->header
)
122 fprintf (file
, ";;\n;; Loop %d\n", loop
->num
);
124 fprintf (file
, ";; header %d, ", loop
->header
->index
);
126 fprintf (file
, "latch %d\n", loop
->latch
->index
);
129 fprintf (file
, "multiple latches:");
130 latches
= get_loop_latch_edges (loop
);
131 FOR_EACH_VEC_ELT (latches
, i
, e
)
132 fprintf (file
, " %d", e
->src
->index
);
134 fprintf (file
, "\n");
137 fprintf (file
, ";; depth %d, outer %ld\n",
138 loop_depth (loop
), (long) (loop_outer (loop
)
139 ? loop_outer (loop
)->num
: -1));
141 fprintf (file
, ";; nodes:");
142 bbs
= get_loop_body (loop
);
143 for (i
= 0; i
< loop
->num_nodes
; i
++)
144 fprintf (file
, " %d", bbs
[i
]->index
);
146 fprintf (file
, "\n");
149 loop_dump_aux (loop
, file
, verbose
);
152 /* Dump the loop information about loops to the stream FILE,
153 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
156 flow_loops_dump (FILE *file
, void (*loop_dump_aux
) (const struct loop
*, FILE *, int), int verbose
)
160 if (!current_loops
|| ! file
)
163 fprintf (file
, ";; %d loops found\n", number_of_loops (cfun
));
165 FOR_EACH_LOOP (loop
, LI_INCLUDE_ROOT
)
167 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
);
171 flow_loops_cfg_dump (file
);
174 /* Free data allocated for LOOP. */
177 flow_loop_free (struct loop
*loop
)
179 struct loop_exit
*exit
, *next
;
181 vec_free (loop
->superloops
);
183 /* Break the list of the loop exit records. They will be freed when the
184 corresponding edge is rescanned or removed, and this avoids
185 accessing the (already released) head of the list stored in the
187 for (exit
= loop
->exits
->next
; exit
!= loop
->exits
; exit
= next
)
194 ggc_free (loop
->exits
);
198 /* Free all the memory allocated for LOOPS. */
201 flow_loops_free (struct loops
*loops
)
208 /* Free the loop descriptors. */
209 FOR_EACH_VEC_SAFE_ELT (loops
->larray
, i
, loop
)
214 flow_loop_free (loop
);
217 vec_free (loops
->larray
);
221 /* Find the nodes contained within the LOOP with header HEADER.
222 Return the number of nodes within the loop. */
225 flow_loop_nodes_find (basic_block header
, struct loop
*loop
)
227 vec
<basic_block
> stack
= vNULL
;
230 edge_iterator latch_ei
;
232 header
->loop_father
= loop
;
234 FOR_EACH_EDGE (latch
, latch_ei
, loop
->header
->preds
)
236 if (latch
->src
->loop_father
== loop
237 || !dominated_by_p (CDI_DOMINATORS
, latch
->src
, loop
->header
))
241 stack
.safe_push (latch
->src
);
242 latch
->src
->loop_father
= loop
;
244 while (!stack
.is_empty ())
252 FOR_EACH_EDGE (e
, ei
, node
->preds
)
254 basic_block ancestor
= e
->src
;
256 if (ancestor
->loop_father
!= loop
)
258 ancestor
->loop_father
= loop
;
260 stack
.safe_push (ancestor
);
270 /* Records the vector of superloops of the loop LOOP, whose immediate
271 superloop is FATHER. */
274 establish_preds (struct loop
*loop
, struct loop
*father
)
277 unsigned depth
= loop_depth (father
) + 1;
280 loop
->superloops
= 0;
281 vec_alloc (loop
->superloops
, depth
);
282 FOR_EACH_VEC_SAFE_ELT (father
->superloops
, i
, ploop
)
283 loop
->superloops
->quick_push (ploop
);
284 loop
->superloops
->quick_push (father
);
286 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
287 establish_preds (ploop
, loop
);
290 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
291 added loop. If LOOP has some children, take care of that their
292 pred field will be initialized correctly. */
295 flow_loop_tree_node_add (struct loop
*father
, struct loop
*loop
)
297 loop
->next
= father
->inner
;
298 father
->inner
= loop
;
300 establish_preds (loop
, father
);
303 /* Remove LOOP from the loop hierarchy tree. */
306 flow_loop_tree_node_remove (struct loop
*loop
)
308 struct loop
*prev
, *father
;
310 father
= loop_outer (loop
);
312 /* Remove loop from the list of sons. */
313 if (father
->inner
== loop
)
314 father
->inner
= loop
->next
;
317 for (prev
= father
->inner
; prev
->next
!= loop
; prev
= prev
->next
)
319 prev
->next
= loop
->next
;
322 loop
->superloops
= NULL
;
325 /* Allocates and returns new loop structure. */
330 struct loop
*loop
= ggc_cleared_alloc
<struct loop
> ();
332 loop
->exits
= ggc_cleared_alloc
<loop_exit
> ();
333 loop
->exits
->next
= loop
->exits
->prev
= loop
->exits
;
334 loop
->can_be_parallel
= false;
335 loop
->nb_iterations_upper_bound
= 0;
336 loop
->nb_iterations_estimate
= 0;
340 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
341 (including the root of the loop tree). */
344 init_loops_structure (struct function
*fn
,
345 struct loops
*loops
, unsigned num_loops
)
349 memset (loops
, 0, sizeof *loops
);
350 vec_alloc (loops
->larray
, num_loops
);
352 /* Dummy loop containing whole function. */
353 root
= alloc_loop ();
354 root
->num_nodes
= n_basic_blocks_for_fn (fn
);
355 root
->latch
= EXIT_BLOCK_PTR_FOR_FN (fn
);
356 root
->header
= ENTRY_BLOCK_PTR_FOR_FN (fn
);
357 ENTRY_BLOCK_PTR_FOR_FN (fn
)->loop_father
= root
;
358 EXIT_BLOCK_PTR_FOR_FN (fn
)->loop_father
= root
;
360 loops
->larray
->quick_push (root
);
361 loops
->tree_root
= root
;
364 /* Returns whether HEADER is a loop header. */
367 bb_loop_header_p (basic_block header
)
372 /* If we have an abnormal predecessor, do not consider the
373 loop (not worth the problems). */
374 if (bb_has_abnormal_pred (header
))
377 /* Look for back edges where a predecessor is dominated
378 by this block. A natural loop has a single entry
379 node (header) that dominates all the nodes in the
380 loop. It also has single back edge to the header
381 from a latch node. */
382 FOR_EACH_EDGE (e
, ei
, header
->preds
)
384 basic_block latch
= e
->src
;
385 if (latch
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
386 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
393 /* Find all the natural loops in the function and save in LOOPS structure and
394 recalculate loop_father information in basic block structures.
395 If LOOPS is non-NULL then the loop structures for already recorded loops
396 will be re-used and their number will not change. We assume that no
397 stale loops exist in LOOPS.
398 When LOOPS is NULL it is allocated and re-built from scratch.
399 Return the built LOOPS structure. */
402 flow_loops_find (struct loops
*loops
)
404 bool from_scratch
= (loops
== NULL
);
409 /* Ensure that the dominators are computed. */
410 calculate_dominance_info (CDI_DOMINATORS
);
414 loops
= ggc_cleared_alloc
<struct loops
> ();
415 init_loops_structure (cfun
, loops
, 1);
418 /* Ensure that loop exits were released. */
419 gcc_assert (loops
->exits
== NULL
);
421 /* Taking care of this degenerate case makes the rest of
422 this code simpler. */
423 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
426 /* The root loop node contains all basic-blocks. */
427 loops
->tree_root
->num_nodes
= n_basic_blocks_for_fn (cfun
);
429 /* Compute depth first search order of the CFG so that outer
430 natural loops will be found before inner natural loops. */
431 rc_order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
432 pre_and_rev_post_order_compute (NULL
, rc_order
, false);
434 /* Gather all loop headers in reverse completion order and allocate
435 loop structures for loops that are not already present. */
436 auto_vec
<loop_p
> larray (loops
->larray
->length ());
437 for (b
= 0; b
< n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
; b
++)
439 basic_block header
= BASIC_BLOCK_FOR_FN (cfun
, rc_order
[b
]);
440 if (bb_loop_header_p (header
))
444 /* The current active loop tree has valid loop-fathers for
447 && header
->loop_father
->header
== header
)
449 loop
= header
->loop_father
;
450 /* If we found an existing loop remove it from the
451 loop tree. It is going to be inserted again
453 flow_loop_tree_node_remove (loop
);
457 /* Otherwise allocate a new loop structure for the loop. */
458 loop
= alloc_loop ();
459 /* ??? We could re-use unused loop slots here. */
460 loop
->num
= loops
->larray
->length ();
461 vec_safe_push (loops
->larray
, loop
);
462 loop
->header
= header
;
465 && dump_file
&& (dump_flags
& TDF_DETAILS
))
466 fprintf (dump_file
, "flow_loops_find: discovered new "
467 "loop %d with header %d\n",
468 loop
->num
, header
->index
);
470 /* Reset latch, we recompute it below. */
472 larray
.safe_push (loop
);
475 /* Make blocks part of the loop root node at start. */
476 header
->loop_father
= loops
->tree_root
;
481 /* Now iterate over the loops found, insert them into the loop tree
482 and assign basic-block ownership. */
483 for (i
= 0; i
< larray
.length (); ++i
)
485 struct loop
*loop
= larray
[i
];
486 basic_block header
= loop
->header
;
490 flow_loop_tree_node_add (header
->loop_father
, loop
);
491 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
493 /* Look for the latch for this header block, if it has just a
495 FOR_EACH_EDGE (e
, ei
, header
->preds
)
497 basic_block latch
= e
->src
;
499 if (flow_bb_inside_loop_p (loop
, latch
))
501 if (loop
->latch
!= NULL
)
503 /* More than one latch edge. */
515 /* Ratio of frequencies of edges so that one of more latch edges is
516 considered to belong to inner loop with same header. */
517 #define HEAVY_EDGE_RATIO 8
519 /* Minimum number of samples for that we apply
520 find_subloop_latch_edge_by_profile heuristics. */
521 #define HEAVY_EDGE_MIN_SAMPLES 10
523 /* If the profile info is available, finds an edge in LATCHES that much more
524 frequent than the remaining edges. Returns such an edge, or NULL if we do
527 We do not use guessed profile here, only the measured one. The guessed
528 profile is usually too flat and unreliable for this (and it is mostly based
529 on the loop structure of the program, so it does not make much sense to
530 derive the loop structure from it). */
533 find_subloop_latch_edge_by_profile (vec
<edge
> latches
)
537 gcov_type mcount
= 0, tcount
= 0;
539 FOR_EACH_VEC_ELT (latches
, i
, e
)
541 if (e
->count
> mcount
)
549 if (tcount
< HEAVY_EDGE_MIN_SAMPLES
550 || (tcount
- mcount
) * HEAVY_EDGE_RATIO
> tcount
)
555 "Found latch edge %d -> %d using profile information.\n",
556 me
->src
->index
, me
->dest
->index
);
560 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
561 on the structure of induction variables. Returns this edge, or NULL if we
564 We are quite conservative, and look just for an obvious simple innermost
565 loop (which is the case where we would lose the most performance by not
566 disambiguating the loop). More precisely, we look for the following
567 situation: The source of the chosen latch edge dominates sources of all
568 the other latch edges. Additionally, the header does not contain a phi node
569 such that the argument from the chosen edge is equal to the argument from
573 find_subloop_latch_edge_by_ivs (struct loop
*loop ATTRIBUTE_UNUSED
, vec
<edge
> latches
)
575 edge e
, latch
= latches
[0];
582 /* Find the candidate for the latch edge. */
583 for (i
= 1; latches
.iterate (i
, &e
); i
++)
584 if (dominated_by_p (CDI_DOMINATORS
, latch
->src
, e
->src
))
587 /* Verify that it dominates all the latch edges. */
588 FOR_EACH_VEC_ELT (latches
, i
, e
)
589 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, latch
->src
))
592 /* Check for a phi node that would deny that this is a latch edge of
594 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
597 lop
= PHI_ARG_DEF_FROM_EDGE (phi
, latch
);
599 /* Ignore the values that are not changed inside the subloop. */
600 if (TREE_CODE (lop
) != SSA_NAME
601 || SSA_NAME_DEF_STMT (lop
) == phi
)
603 bb
= gimple_bb (SSA_NAME_DEF_STMT (lop
));
604 if (!bb
|| !flow_bb_inside_loop_p (loop
, bb
))
607 FOR_EACH_VEC_ELT (latches
, i
, e
)
609 && PHI_ARG_DEF_FROM_EDGE (phi
, e
) == lop
)
615 "Found latch edge %d -> %d using iv structure.\n",
616 latch
->src
->index
, latch
->dest
->index
);
620 /* If we can determine that one of the several latch edges of LOOP behaves
621 as a latch edge of a separate subloop, returns this edge. Otherwise
625 find_subloop_latch_edge (struct loop
*loop
)
627 vec
<edge
> latches
= get_loop_latch_edges (loop
);
630 if (latches
.length () > 1)
632 latch
= find_subloop_latch_edge_by_profile (latches
);
635 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
636 should use cfghook for this, but it is hard to imagine it would
637 be useful elsewhere. */
638 && current_ir_type () == IR_GIMPLE
)
639 latch
= find_subloop_latch_edge_by_ivs (loop
, latches
);
646 /* Callback for make_forwarder_block. Returns true if the edge E is marked
647 in the set MFB_REIS_SET. */
649 static hash_set
<edge
> *mfb_reis_set
;
651 mfb_redirect_edges_in_set (edge e
)
653 return mfb_reis_set
->contains (e
);
656 /* Creates a subloop of LOOP with latch edge LATCH. */
659 form_subloop (struct loop
*loop
, edge latch
)
663 struct loop
*new_loop
;
665 mfb_reis_set
= new hash_set
<edge
>;
666 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
669 mfb_reis_set
->add (e
);
671 new_entry
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
675 loop
->header
= new_entry
->src
;
677 /* Find the blocks and subloops that belong to the new loop, and add it to
678 the appropriate place in the loop tree. */
679 new_loop
= alloc_loop ();
680 new_loop
->header
= new_entry
->dest
;
681 new_loop
->latch
= latch
->src
;
682 add_loop (new_loop
, loop
);
685 /* Make all the latch edges of LOOP to go to a single forwarder block --
686 a new latch of LOOP. */
689 merge_latch_edges (struct loop
*loop
)
691 vec
<edge
> latches
= get_loop_latch_edges (loop
);
695 gcc_assert (latches
.length () > 0);
697 if (latches
.length () == 1)
698 loop
->latch
= latches
[0]->src
;
702 fprintf (dump_file
, "Merged latch edges of loop %d\n", loop
->num
);
704 mfb_reis_set
= new hash_set
<edge
>;
705 FOR_EACH_VEC_ELT (latches
, i
, e
)
706 mfb_reis_set
->add (e
);
707 latch
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
711 loop
->header
= latch
->dest
;
712 loop
->latch
= latch
->src
;
718 /* LOOP may have several latch edges. Transform it into (possibly several)
719 loops with single latch edge. */
722 disambiguate_multiple_latches (struct loop
*loop
)
726 /* We eliminate the multiple latches by splitting the header to the forwarder
727 block F and the rest R, and redirecting the edges. There are two cases:
729 1) If there is a latch edge E that corresponds to a subloop (we guess
730 that based on profile -- if it is taken much more often than the
731 remaining edges; and on trees, using the information about induction
732 variables of the loops), we redirect E to R, all the remaining edges to
733 F, then rescan the loops and try again for the outer loop.
734 2) If there is no such edge, we redirect all latch edges to F, and the
735 entry edges to R, thus making F the single latch of the loop. */
738 fprintf (dump_file
, "Disambiguating loop %d with multiple latches\n",
741 /* During latch merging, we may need to redirect the entry edges to a new
742 block. This would cause problems if the entry edge was the one from the
743 entry block. To avoid having to handle this case specially, split
745 e
= find_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), loop
->header
);
751 e
= find_subloop_latch_edge (loop
);
755 form_subloop (loop
, e
);
758 merge_latch_edges (loop
);
761 /* Split loops with multiple latch edges. */
764 disambiguate_loops_with_multiple_latches (void)
768 FOR_EACH_LOOP (loop
, 0)
771 disambiguate_multiple_latches (loop
);
775 /* Return nonzero if basic block BB belongs to LOOP. */
777 flow_bb_inside_loop_p (const struct loop
*loop
, const_basic_block bb
)
779 struct loop
*source_loop
;
781 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
782 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
785 source_loop
= bb
->loop_father
;
786 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
789 /* Enumeration predicate for get_loop_body_with_size. */
791 glb_enum_p (const_basic_block bb
, const void *glb_loop
)
793 const struct loop
*const loop
= (const struct loop
*) glb_loop
;
794 return (bb
!= loop
->header
795 && dominated_by_p (CDI_DOMINATORS
, bb
, loop
->header
));
798 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
799 order against direction of edges from latch. Specially, if
800 header != latch, latch is the 1-st block. LOOP cannot be the fake
801 loop tree root, and its size must be at most MAX_SIZE. The blocks
802 in the LOOP body are stored to BODY, and the size of the LOOP is
806 get_loop_body_with_size (const struct loop
*loop
, basic_block
*body
,
809 return dfs_enumerate_from (loop
->header
, 1, glb_enum_p
,
810 body
, max_size
, loop
);
813 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
814 order against direction of edges from latch. Specially, if
815 header != latch, latch is the 1-st block. */
818 get_loop_body (const struct loop
*loop
)
820 basic_block
*body
, bb
;
823 gcc_assert (loop
->num_nodes
);
825 body
= XNEWVEC (basic_block
, loop
->num_nodes
);
827 if (loop
->latch
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
829 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
830 special-case the fake loop that contains the whole function. */
831 gcc_assert (loop
->num_nodes
== (unsigned) n_basic_blocks_for_fn (cfun
));
832 body
[tv
++] = loop
->header
;
833 body
[tv
++] = EXIT_BLOCK_PTR_FOR_FN (cfun
);
834 FOR_EACH_BB_FN (bb
, cfun
)
838 tv
= get_loop_body_with_size (loop
, body
, loop
->num_nodes
);
840 gcc_assert (tv
== loop
->num_nodes
);
844 /* Fills dominance descendants inside LOOP of the basic block BB into
845 array TOVISIT from index *TV. */
848 fill_sons_in_loop (const struct loop
*loop
, basic_block bb
,
849 basic_block
*tovisit
, int *tv
)
851 basic_block son
, postpone
= NULL
;
853 tovisit
[(*tv
)++] = bb
;
854 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
856 son
= next_dom_son (CDI_DOMINATORS
, son
))
858 if (!flow_bb_inside_loop_p (loop
, son
))
861 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, son
))
866 fill_sons_in_loop (loop
, son
, tovisit
, tv
);
870 fill_sons_in_loop (loop
, postpone
, tovisit
, tv
);
873 /* Gets body of a LOOP (that must be different from the outermost loop)
874 sorted by dominance relation. Additionally, if a basic block s dominates
875 the latch, then only blocks dominated by s are be after it. */
878 get_loop_body_in_dom_order (const struct loop
*loop
)
880 basic_block
*tovisit
;
883 gcc_assert (loop
->num_nodes
);
885 tovisit
= XNEWVEC (basic_block
, loop
->num_nodes
);
887 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
890 fill_sons_in_loop (loop
, loop
->header
, tovisit
, &tv
);
892 gcc_assert (tv
== (int) loop
->num_nodes
);
897 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
900 get_loop_body_in_custom_order (const struct loop
*loop
,
901 int (*bb_comparator
) (const void *, const void *))
903 basic_block
*bbs
= get_loop_body (loop
);
905 qsort (bbs
, loop
->num_nodes
, sizeof (basic_block
), bb_comparator
);
910 /* Get body of a LOOP in breadth first sort order. */
913 get_loop_body_in_bfs_order (const struct loop
*loop
)
921 gcc_assert (loop
->num_nodes
);
922 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
924 blocks
= XNEWVEC (basic_block
, loop
->num_nodes
);
925 visited
= BITMAP_ALLOC (NULL
);
928 while (i
< loop
->num_nodes
)
933 if (bitmap_set_bit (visited
, bb
->index
))
934 /* This basic block is now visited */
937 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
939 if (flow_bb_inside_loop_p (loop
, e
->dest
))
941 if (bitmap_set_bit (visited
, e
->dest
->index
))
942 blocks
[i
++] = e
->dest
;
951 BITMAP_FREE (visited
);
955 /* Hash function for struct loop_exit. */
958 loop_exit_hasher::hash (loop_exit
*exit
)
960 return htab_hash_pointer (exit
->e
);
963 /* Equality function for struct loop_exit. Compares with edge. */
966 loop_exit_hasher::equal (loop_exit
*exit
, edge e
)
971 /* Frees the list of loop exit descriptions EX. */
974 loop_exit_hasher::remove (loop_exit
*exit
)
977 for (; exit
; exit
= next
)
981 exit
->next
->prev
= exit
->prev
;
982 exit
->prev
->next
= exit
->next
;
988 /* Returns the list of records for E as an exit of a loop. */
990 static struct loop_exit
*
991 get_exit_descriptions (edge e
)
993 return current_loops
->exits
->find_with_hash (e
, htab_hash_pointer (e
));
996 /* Updates the lists of loop exits in that E appears.
997 If REMOVED is true, E is being removed, and we
998 just remove it from the lists of exits.
999 If NEW_EDGE is true and E is not a loop exit, we
1000 do not try to remove it from loop exit lists. */
1003 rescan_loop_exit (edge e
, bool new_edge
, bool removed
)
1005 struct loop_exit
*exits
= NULL
, *exit
;
1006 struct loop
*aloop
, *cloop
;
1008 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1012 && e
->src
->loop_father
!= NULL
1013 && e
->dest
->loop_father
!= NULL
1014 && !flow_bb_inside_loop_p (e
->src
->loop_father
, e
->dest
))
1016 cloop
= find_common_loop (e
->src
->loop_father
, e
->dest
->loop_father
);
1017 for (aloop
= e
->src
->loop_father
;
1019 aloop
= loop_outer (aloop
))
1021 exit
= ggc_alloc
<loop_exit
> ();
1024 exit
->next
= aloop
->exits
->next
;
1025 exit
->prev
= aloop
->exits
;
1026 exit
->next
->prev
= exit
;
1027 exit
->prev
->next
= exit
;
1029 exit
->next_e
= exits
;
1034 if (!exits
&& new_edge
)
1038 = current_loops
->exits
->find_slot_with_hash (e
, htab_hash_pointer (e
),
1039 exits
? INSERT
: NO_INSERT
);
1046 loop_exit_hasher::remove (*slot
);
1050 current_loops
->exits
->clear_slot (slot
);
1053 /* For each loop, record list of exit edges, and start maintaining these
1057 record_loop_exits (void)
1066 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1068 loops_state_set (LOOPS_HAVE_RECORDED_EXITS
);
1070 gcc_assert (current_loops
->exits
== NULL
);
1071 current_loops
->exits
1072 = hash_table
<loop_exit_hasher
>::create_ggc (2 * number_of_loops (cfun
));
1074 FOR_EACH_BB_FN (bb
, cfun
)
1076 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1078 rescan_loop_exit (e
, true, false);
1083 /* Dumps information about the exit in *SLOT to FILE.
1084 Callback for htab_traverse. */
1087 dump_recorded_exit (loop_exit
**slot
, FILE *file
)
1089 struct loop_exit
*exit
= *slot
;
1093 for (; exit
!= NULL
; exit
= exit
->next_e
)
1096 fprintf (file
, "Edge %d->%d exits %u loops\n",
1097 e
->src
->index
, e
->dest
->index
, n
);
1102 /* Dumps the recorded exits of loops to FILE. */
1104 extern void dump_recorded_exits (FILE *);
1106 dump_recorded_exits (FILE *file
)
1108 if (!current_loops
->exits
)
1110 current_loops
->exits
->traverse
<FILE *, dump_recorded_exit
> (file
);
1113 /* Releases lists of loop exits. */
1116 release_recorded_exits (void)
1118 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
));
1119 current_loops
->exits
->empty ();
1120 current_loops
->exits
= NULL
;
1121 loops_state_clear (LOOPS_HAVE_RECORDED_EXITS
);
1124 /* Returns the list of the exit edges of a LOOP. */
1127 get_loop_exit_edges (const struct loop
*loop
)
1129 vec
<edge
> edges
= vNULL
;
1134 struct loop_exit
*exit
;
1136 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1138 /* If we maintain the lists of exits, use them. Otherwise we must
1139 scan the body of the loop. */
1140 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1142 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1143 edges
.safe_push (exit
->e
);
1147 body
= get_loop_body (loop
);
1148 for (i
= 0; i
< loop
->num_nodes
; i
++)
1149 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
1151 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1152 edges
.safe_push (e
);
1160 /* Counts the number of conditional branches inside LOOP. */
1163 num_loop_branches (const struct loop
*loop
)
1168 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1170 body
= get_loop_body (loop
);
1172 for (i
= 0; i
< loop
->num_nodes
; i
++)
1173 if (EDGE_COUNT (body
[i
]->succs
) >= 2)
1180 /* Adds basic block BB to LOOP. */
1182 add_bb_to_loop (basic_block bb
, struct loop
*loop
)
1189 gcc_assert (bb
->loop_father
== NULL
);
1190 bb
->loop_father
= loop
;
1192 FOR_EACH_VEC_SAFE_ELT (loop
->superloops
, i
, ploop
)
1195 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1197 rescan_loop_exit (e
, true, false);
1199 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1201 rescan_loop_exit (e
, true, false);
1205 /* Remove basic block BB from loops. */
1207 remove_bb_from_loops (basic_block bb
)
1210 struct loop
*loop
= bb
->loop_father
;
1215 gcc_assert (loop
!= NULL
);
1217 FOR_EACH_VEC_SAFE_ELT (loop
->superloops
, i
, ploop
)
1219 bb
->loop_father
= NULL
;
1221 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1223 rescan_loop_exit (e
, false, true);
1225 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1227 rescan_loop_exit (e
, false, true);
1231 /* Finds nearest common ancestor in loop tree for given loops. */
1233 find_common_loop (struct loop
*loop_s
, struct loop
*loop_d
)
1235 unsigned sdepth
, ddepth
;
1237 if (!loop_s
) return loop_d
;
1238 if (!loop_d
) return loop_s
;
1240 sdepth
= loop_depth (loop_s
);
1241 ddepth
= loop_depth (loop_d
);
1243 if (sdepth
< ddepth
)
1244 loop_d
= (*loop_d
->superloops
)[sdepth
];
1245 else if (sdepth
> ddepth
)
1246 loop_s
= (*loop_s
->superloops
)[ddepth
];
1248 while (loop_s
!= loop_d
)
1250 loop_s
= loop_outer (loop_s
);
1251 loop_d
= loop_outer (loop_d
);
1256 /* Removes LOOP from structures and frees its data. */
1259 delete_loop (struct loop
*loop
)
1261 /* Remove the loop from structure. */
1262 flow_loop_tree_node_remove (loop
);
1264 /* Remove loop from loops array. */
1265 (*current_loops
->larray
)[loop
->num
] = NULL
;
1267 /* Free loop data. */
1268 flow_loop_free (loop
);
1271 /* Cancels the LOOP; it must be innermost one. */
1274 cancel_loop (struct loop
*loop
)
1278 struct loop
*outer
= loop_outer (loop
);
1280 gcc_assert (!loop
->inner
);
1282 /* Move blocks up one level (they should be removed as soon as possible). */
1283 bbs
= get_loop_body (loop
);
1284 for (i
= 0; i
< loop
->num_nodes
; i
++)
1285 bbs
[i
]->loop_father
= outer
;
1291 /* Cancels LOOP and all its subloops. */
1293 cancel_loop_tree (struct loop
*loop
)
1296 cancel_loop_tree (loop
->inner
);
1300 /* Checks that information about loops is correct
1301 -- sizes of loops are all right
1302 -- results of get_loop_body really belong to the loop
1303 -- loop header have just single entry edge and single latch edge
1304 -- loop latches have only single successor that is header of their loop
1305 -- irreducible loops are correctly marked
1306 -- the cached loop depth and loop father of each bb is correct
1309 verify_loop_structure (void)
1311 unsigned *sizes
, i
, j
;
1313 basic_block bb
, *bbs
;
1317 unsigned num
= number_of_loops (cfun
);
1318 struct loop_exit
*exit
, *mexit
;
1319 bool dom_available
= dom_info_available_p (CDI_DOMINATORS
);
1322 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
1324 error ("loop verification on loop tree that needs fixup");
1328 /* We need up-to-date dominators, compute or verify them. */
1330 calculate_dominance_info (CDI_DOMINATORS
);
1332 verify_dominators (CDI_DOMINATORS
);
1334 /* Check the loop tree root. */
1335 if (current_loops
->tree_root
->header
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1336 || current_loops
->tree_root
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1337 || (current_loops
->tree_root
->num_nodes
1338 != (unsigned) n_basic_blocks_for_fn (cfun
)))
1340 error ("corrupt loop tree root");
1344 /* Check the headers. */
1345 FOR_EACH_BB_FN (bb
, cfun
)
1346 if (bb_loop_header_p (bb
))
1348 if (bb
->loop_father
->header
== NULL
)
1350 error ("loop with header %d marked for removal", bb
->index
);
1353 else if (bb
->loop_father
->header
!= bb
)
1355 error ("loop with header %d not in loop tree", bb
->index
);
1359 else if (bb
->loop_father
->header
== bb
)
1361 error ("non-loop with header %d not marked for removal", bb
->index
);
1365 /* Check the recorded loop father and sizes of loops. */
1366 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1367 bitmap_clear (visited
);
1368 bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
1369 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1373 if (loop
->header
== NULL
)
1375 error ("removed loop %d in loop tree", loop
->num
);
1380 n
= get_loop_body_with_size (loop
, bbs
, n_basic_blocks_for_fn (cfun
));
1381 if (loop
->num_nodes
!= n
)
1383 error ("size of loop %d should be %d, not %d",
1384 loop
->num
, n
, loop
->num_nodes
);
1388 for (j
= 0; j
< n
; j
++)
1392 if (!flow_bb_inside_loop_p (loop
, bb
))
1394 error ("bb %d does not belong to loop %d",
1395 bb
->index
, loop
->num
);
1399 /* Ignore this block if it is in an inner loop. */
1400 if (bitmap_bit_p (visited
, bb
->index
))
1402 bitmap_set_bit (visited
, bb
->index
);
1404 if (bb
->loop_father
!= loop
)
1406 error ("bb %d has father loop %d, should be loop %d",
1407 bb
->index
, bb
->loop_father
->num
, loop
->num
);
1413 sbitmap_free (visited
);
1415 /* Check headers and latches. */
1416 FOR_EACH_LOOP (loop
, 0)
1419 if (loop
->header
== NULL
)
1421 if (!bb_loop_header_p (loop
->header
))
1423 error ("loop %d%'s header is not a loop header", i
);
1426 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
)
1427 && EDGE_COUNT (loop
->header
->preds
) != 2)
1429 error ("loop %d%'s header does not have exactly 2 entries", i
);
1434 if (!find_edge (loop
->latch
, loop
->header
))
1436 error ("loop %d%'s latch does not have an edge to its header", i
);
1439 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, loop
->header
))
1441 error ("loop %d%'s latch is not dominated by its header", i
);
1445 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
1447 if (!single_succ_p (loop
->latch
))
1449 error ("loop %d%'s latch does not have exactly 1 successor", i
);
1452 if (single_succ (loop
->latch
) != loop
->header
)
1454 error ("loop %d%'s latch does not have header as successor", i
);
1457 if (loop
->latch
->loop_father
!= loop
)
1459 error ("loop %d%'s latch does not belong directly to it", i
);
1463 if (loop
->header
->loop_father
!= loop
)
1465 error ("loop %d%'s header does not belong directly to it", i
);
1468 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1469 && (loop_latch_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
))
1471 error ("loop %d%'s latch is marked as part of irreducible region", i
);
1476 /* Check irreducible loops. */
1477 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1479 /* Record old info. */
1480 irreds
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1481 FOR_EACH_BB_FN (bb
, cfun
)
1484 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1485 bitmap_set_bit (irreds
, bb
->index
);
1487 bitmap_clear_bit (irreds
, bb
->index
);
1488 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1489 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1490 e
->flags
|= EDGE_ALL_FLAGS
+ 1;
1494 mark_irreducible_loops ();
1497 FOR_EACH_BB_FN (bb
, cfun
)
1501 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1502 && !bitmap_bit_p (irreds
, bb
->index
))
1504 error ("basic block %d should be marked irreducible", bb
->index
);
1507 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1508 && bitmap_bit_p (irreds
, bb
->index
))
1510 error ("basic block %d should not be marked irreducible", bb
->index
);
1513 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1515 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1516 && !(e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1518 error ("edge from %d to %d should be marked irreducible",
1519 e
->src
->index
, e
->dest
->index
);
1522 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1523 && (e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1525 error ("edge from %d to %d should not be marked irreducible",
1526 e
->src
->index
, e
->dest
->index
);
1529 e
->flags
&= ~(EDGE_ALL_FLAGS
+ 1);
1535 /* Check the recorded loop exits. */
1536 FOR_EACH_LOOP (loop
, 0)
1538 if (!loop
->exits
|| loop
->exits
->e
!= NULL
)
1540 error ("corrupted head of the exits list of loop %d",
1546 /* Check that the list forms a cycle, and all elements except
1547 for the head are nonnull. */
1548 for (mexit
= loop
->exits
, exit
= mexit
->next
, i
= 0;
1549 exit
->e
&& exit
!= mexit
;
1553 mexit
= mexit
->next
;
1556 if (exit
!= loop
->exits
)
1558 error ("corrupted exits list of loop %d", loop
->num
);
1563 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1565 if (loop
->exits
->next
!= loop
->exits
)
1567 error ("nonempty exits list of loop %d, but exits are not recorded",
1574 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1576 unsigned n_exits
= 0, eloops
;
1578 sizes
= XCNEWVEC (unsigned, num
);
1579 memset (sizes
, 0, sizeof (unsigned) * num
);
1580 FOR_EACH_BB_FN (bb
, cfun
)
1583 if (bb
->loop_father
== current_loops
->tree_root
)
1585 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1587 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
1591 exit
= get_exit_descriptions (e
);
1594 error ("exit %d->%d not recorded",
1595 e
->src
->index
, e
->dest
->index
);
1599 for (; exit
; exit
= exit
->next_e
)
1602 for (loop
= bb
->loop_father
;
1603 loop
!= e
->dest
->loop_father
1604 /* When a loop exit is also an entry edge which
1605 can happen when avoiding CFG manipulations
1606 then the last loop exited is the outer loop
1607 of the loop entered. */
1608 && loop
!= loop_outer (e
->dest
->loop_father
);
1609 loop
= loop_outer (loop
))
1617 error ("wrong list of exited loops for edge %d->%d",
1618 e
->src
->index
, e
->dest
->index
);
1624 if (n_exits
!= current_loops
->exits
->elements ())
1626 error ("too many loop exits recorded");
1630 FOR_EACH_LOOP (loop
, 0)
1633 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1635 if (eloops
!= sizes
[loop
->num
])
1637 error ("%d exits recorded for loop %d (having %d exits)",
1638 eloops
, loop
->num
, sizes
[loop
->num
]);
1649 free_dominance_info (CDI_DOMINATORS
);
1652 /* Returns latch edge of LOOP. */
1654 loop_latch_edge (const struct loop
*loop
)
1656 return find_edge (loop
->latch
, loop
->header
);
1659 /* Returns preheader edge of LOOP. */
1661 loop_preheader_edge (const struct loop
*loop
)
1666 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
));
1668 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1669 if (e
->src
!= loop
->latch
)
1675 /* Returns true if E is an exit of LOOP. */
1678 loop_exit_edge_p (const struct loop
*loop
, const_edge e
)
1680 return (flow_bb_inside_loop_p (loop
, e
->src
)
1681 && !flow_bb_inside_loop_p (loop
, e
->dest
));
1684 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1685 or more than one exit. If loops do not have the exits recorded, NULL
1686 is returned always. */
1689 single_exit (const struct loop
*loop
)
1691 struct loop_exit
*exit
= loop
->exits
->next
;
1693 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1696 if (exit
->e
&& exit
->next
== loop
->exits
)
1702 /* Returns true when BB has an incoming edge exiting LOOP. */
1705 loop_exits_to_bb_p (struct loop
*loop
, basic_block bb
)
1710 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1711 if (loop_exit_edge_p (loop
, e
))
1717 /* Returns true when BB has an outgoing edge exiting LOOP. */
1720 loop_exits_from_bb_p (struct loop
*loop
, basic_block bb
)
1725 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1726 if (loop_exit_edge_p (loop
, e
))
1732 /* Return location corresponding to the loop control condition if possible. */
1735 get_loop_location (struct loop
*loop
)
1737 rtx_insn
*insn
= NULL
;
1738 struct niter_desc
*desc
= NULL
;
1741 /* For a for or while loop, we would like to return the location
1742 of the for or while statement, if possible. To do this, look
1743 for the branch guarding the loop back-edge. */
1745 /* If this is a simple loop with an in_edge, then the loop control
1746 branch is typically at the end of its source. */
1747 desc
= get_simple_loop_desc (loop
);
1750 FOR_BB_INSNS_REVERSE (desc
->in_edge
->src
, insn
)
1752 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1753 return INSN_LOCATION (insn
);
1756 /* If loop has a single exit, then the loop control branch
1757 must be at the end of its source. */
1758 if ((exit
= single_exit (loop
)))
1760 FOR_BB_INSNS_REVERSE (exit
->src
, insn
)
1762 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1763 return INSN_LOCATION (insn
);
1766 /* Next check the latch, to see if it is non-empty. */
1767 FOR_BB_INSNS_REVERSE (loop
->latch
, insn
)
1769 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1770 return INSN_LOCATION (insn
);
1772 /* Finally, if none of the above identifies the loop control branch,
1773 return the first location in the loop header. */
1774 FOR_BB_INSNS (loop
->header
, insn
)
1776 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1777 return INSN_LOCATION (insn
);
1779 /* If all else fails, simply return the current function location. */
1780 return DECL_SOURCE_LOCATION (current_function_decl
);
1783 /* Records that every statement in LOOP is executed I_BOUND times.
1784 REALISTIC is true if I_BOUND is expected to be close to the real number
1785 of iterations. UPPER is true if we are sure the loop iterates at most
1789 record_niter_bound (struct loop
*loop
, const widest_int
&i_bound
,
1790 bool realistic
, bool upper
)
1792 /* Update the bounds only when there is no previous estimation, or when the
1793 current estimation is smaller. */
1795 && (!loop
->any_upper_bound
1796 || wi::ltu_p (i_bound
, loop
->nb_iterations_upper_bound
)))
1798 loop
->any_upper_bound
= true;
1799 loop
->nb_iterations_upper_bound
= i_bound
;
1802 && (!loop
->any_estimate
1803 || wi::ltu_p (i_bound
, loop
->nb_iterations_estimate
)))
1805 loop
->any_estimate
= true;
1806 loop
->nb_iterations_estimate
= i_bound
;
1809 /* If an upper bound is smaller than the realistic estimate of the
1810 number of iterations, use the upper bound instead. */
1811 if (loop
->any_upper_bound
1812 && loop
->any_estimate
1813 && wi::ltu_p (loop
->nb_iterations_upper_bound
,
1814 loop
->nb_iterations_estimate
))
1815 loop
->nb_iterations_estimate
= loop
->nb_iterations_upper_bound
;
1818 /* Similar to get_estimated_loop_iterations, but returns the estimate only
1819 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1820 on the number of iterations of LOOP could not be derived, returns -1. */
1823 get_estimated_loop_iterations_int (struct loop
*loop
)
1826 HOST_WIDE_INT hwi_nit
;
1828 if (!get_estimated_loop_iterations (loop
, &nit
))
1831 if (!wi::fits_shwi_p (nit
))
1833 hwi_nit
= nit
.to_shwi ();
1835 return hwi_nit
< 0 ? -1 : hwi_nit
;
1838 /* Returns an upper bound on the number of executions of statements
1839 in the LOOP. For statements before the loop exit, this exceeds
1840 the number of execution of the latch by one. */
1843 max_stmt_executions_int (struct loop
*loop
)
1845 HOST_WIDE_INT nit
= get_max_loop_iterations_int (loop
);
1851 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
1853 /* If the computation overflows, return -1. */
1854 return snit
< 0 ? -1 : snit
;
1857 /* Sets NIT to the estimated number of executions of the latch of the
1858 LOOP. If we have no reliable estimate, the function returns false, otherwise
1862 get_estimated_loop_iterations (struct loop
*loop
, widest_int
*nit
)
1864 /* Even if the bound is not recorded, possibly we can derrive one from
1866 if (!loop
->any_estimate
)
1868 if (loop
->header
->count
)
1870 *nit
= gcov_type_to_wide_int
1871 (expected_loop_iterations_unbounded (loop
) + 1);
1877 *nit
= loop
->nb_iterations_estimate
;
1881 /* Sets NIT to an upper bound for the maximum number of executions of the
1882 latch of the LOOP. If we have no reliable estimate, the function returns
1883 false, otherwise returns true. */
1886 get_max_loop_iterations (struct loop
*loop
, widest_int
*nit
)
1888 if (!loop
->any_upper_bound
)
1891 *nit
= loop
->nb_iterations_upper_bound
;
1895 /* Similar to get_max_loop_iterations, but returns the estimate only
1896 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1897 on the number of iterations of LOOP could not be derived, returns -1. */
1900 get_max_loop_iterations_int (struct loop
*loop
)
1903 HOST_WIDE_INT hwi_nit
;
1905 if (!get_max_loop_iterations (loop
, &nit
))
1908 if (!wi::fits_shwi_p (nit
))
1910 hwi_nit
= nit
.to_shwi ();
1912 return hwi_nit
< 0 ? -1 : hwi_nit
;
1915 /* Returns the loop depth of the loop BB belongs to. */
1918 bb_loop_depth (const_basic_block bb
)
1920 return bb
->loop_father
? loop_depth (bb
->loop_father
) : 0;
1923 /* Marks LOOP for removal and sets LOOPS_NEED_FIXUP. */
1926 mark_loop_for_removal (loop_p loop
)
1928 if (loop
->header
== NULL
)
1930 loop
->former_header
= loop
->header
;
1931 loop
->header
= NULL
;
1933 loops_state_set (LOOPS_NEED_FIXUP
);