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"
28 #include "gimple-ssa.h"
29 #include "diagnostic-core.h"
32 #include "gimple-iterator.h"
35 static void flow_loops_cfg_dump (FILE *);
37 /* Dump loop related CFG information. */
40 flow_loops_cfg_dump (FILE *file
)
47 FOR_EACH_BB_FN (bb
, cfun
)
52 fprintf (file
, ";; %d succs { ", bb
->index
);
53 FOR_EACH_EDGE (succ
, ei
, bb
->succs
)
54 fprintf (file
, "%d ", succ
->dest
->index
);
55 fprintf (file
, "}\n");
59 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
62 flow_loop_nested_p (const struct loop
*outer
, const struct loop
*loop
)
64 unsigned odepth
= loop_depth (outer
);
66 return (loop_depth (loop
) > odepth
67 && (*loop
->superloops
)[odepth
] == outer
);
70 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
74 superloop_at_depth (struct loop
*loop
, unsigned depth
)
76 unsigned ldepth
= loop_depth (loop
);
78 gcc_assert (depth
<= ldepth
);
83 return (*loop
->superloops
)[depth
];
86 /* Returns the list of the latch edges of LOOP. */
89 get_loop_latch_edges (const struct loop
*loop
)
93 vec
<edge
> ret
= vNULL
;
95 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
97 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, loop
->header
))
104 /* Dump the loop information specified by LOOP to the stream FILE
105 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
108 flow_loop_dump (const struct loop
*loop
, FILE *file
,
109 void (*loop_dump_aux
) (const struct loop
*, FILE *, int),
117 if (! loop
|| ! loop
->header
)
120 fprintf (file
, ";;\n;; Loop %d\n", loop
->num
);
122 fprintf (file
, ";; header %d, ", loop
->header
->index
);
124 fprintf (file
, "latch %d\n", loop
->latch
->index
);
127 fprintf (file
, "multiple latches:");
128 latches
= get_loop_latch_edges (loop
);
129 FOR_EACH_VEC_ELT (latches
, i
, e
)
130 fprintf (file
, " %d", e
->src
->index
);
132 fprintf (file
, "\n");
135 fprintf (file
, ";; depth %d, outer %ld\n",
136 loop_depth (loop
), (long) (loop_outer (loop
)
137 ? loop_outer (loop
)->num
: -1));
139 fprintf (file
, ";; nodes:");
140 bbs
= get_loop_body (loop
);
141 for (i
= 0; i
< loop
->num_nodes
; i
++)
142 fprintf (file
, " %d", bbs
[i
]->index
);
144 fprintf (file
, "\n");
147 loop_dump_aux (loop
, file
, verbose
);
150 /* Dump the loop information about loops to the stream FILE,
151 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
154 flow_loops_dump (FILE *file
, void (*loop_dump_aux
) (const struct loop
*, FILE *, int), int verbose
)
158 if (!current_loops
|| ! file
)
161 fprintf (file
, ";; %d loops found\n", number_of_loops (cfun
));
163 FOR_EACH_LOOP (loop
, LI_INCLUDE_ROOT
)
165 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
);
169 flow_loops_cfg_dump (file
);
172 /* Free data allocated for LOOP. */
175 flow_loop_free (struct loop
*loop
)
177 struct loop_exit
*exit
, *next
;
179 vec_free (loop
->superloops
);
181 /* Break the list of the loop exit records. They will be freed when the
182 corresponding edge is rescanned or removed, and this avoids
183 accessing the (already released) head of the list stored in the
185 for (exit
= loop
->exits
->next
; exit
!= loop
->exits
; exit
= next
)
192 ggc_free (loop
->exits
);
196 /* Free all the memory allocated for LOOPS. */
199 flow_loops_free (struct loops
*loops
)
206 /* Free the loop descriptors. */
207 FOR_EACH_VEC_SAFE_ELT (loops
->larray
, i
, loop
)
212 flow_loop_free (loop
);
215 vec_free (loops
->larray
);
219 /* Find the nodes contained within the LOOP with header HEADER.
220 Return the number of nodes within the loop. */
223 flow_loop_nodes_find (basic_block header
, struct loop
*loop
)
225 vec
<basic_block
> stack
= vNULL
;
228 edge_iterator latch_ei
;
230 header
->loop_father
= loop
;
232 FOR_EACH_EDGE (latch
, latch_ei
, loop
->header
->preds
)
234 if (latch
->src
->loop_father
== loop
235 || !dominated_by_p (CDI_DOMINATORS
, latch
->src
, loop
->header
))
239 stack
.safe_push (latch
->src
);
240 latch
->src
->loop_father
= loop
;
242 while (!stack
.is_empty ())
250 FOR_EACH_EDGE (e
, ei
, node
->preds
)
252 basic_block ancestor
= e
->src
;
254 if (ancestor
->loop_father
!= loop
)
256 ancestor
->loop_father
= loop
;
258 stack
.safe_push (ancestor
);
268 /* Records the vector of superloops of the loop LOOP, whose immediate
269 superloop is FATHER. */
272 establish_preds (struct loop
*loop
, struct loop
*father
)
275 unsigned depth
= loop_depth (father
) + 1;
278 loop
->superloops
= 0;
279 vec_alloc (loop
->superloops
, depth
);
280 FOR_EACH_VEC_SAFE_ELT (father
->superloops
, i
, ploop
)
281 loop
->superloops
->quick_push (ploop
);
282 loop
->superloops
->quick_push (father
);
284 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
285 establish_preds (ploop
, loop
);
288 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
289 added loop. If LOOP has some children, take care of that their
290 pred field will be initialized correctly. */
293 flow_loop_tree_node_add (struct loop
*father
, struct loop
*loop
)
295 loop
->next
= father
->inner
;
296 father
->inner
= loop
;
298 establish_preds (loop
, father
);
301 /* Remove LOOP from the loop hierarchy tree. */
304 flow_loop_tree_node_remove (struct loop
*loop
)
306 struct loop
*prev
, *father
;
308 father
= loop_outer (loop
);
310 /* Remove loop from the list of sons. */
311 if (father
->inner
== loop
)
312 father
->inner
= loop
->next
;
315 for (prev
= father
->inner
; prev
->next
!= loop
; prev
= prev
->next
)
317 prev
->next
= loop
->next
;
320 loop
->superloops
= NULL
;
323 /* Allocates and returns new loop structure. */
328 struct loop
*loop
= ggc_cleared_alloc
<struct loop
> ();
330 loop
->exits
= ggc_cleared_alloc
<loop_exit
> ();
331 loop
->exits
->next
= loop
->exits
->prev
= loop
->exits
;
332 loop
->can_be_parallel
= false;
333 loop
->nb_iterations_upper_bound
= 0;
334 loop
->nb_iterations_estimate
= 0;
338 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
339 (including the root of the loop tree). */
342 init_loops_structure (struct function
*fn
,
343 struct loops
*loops
, unsigned num_loops
)
347 memset (loops
, 0, sizeof *loops
);
348 vec_alloc (loops
->larray
, num_loops
);
350 /* Dummy loop containing whole function. */
351 root
= alloc_loop ();
352 root
->num_nodes
= n_basic_blocks_for_fn (fn
);
353 root
->latch
= EXIT_BLOCK_PTR_FOR_FN (fn
);
354 root
->header
= ENTRY_BLOCK_PTR_FOR_FN (fn
);
355 ENTRY_BLOCK_PTR_FOR_FN (fn
)->loop_father
= root
;
356 EXIT_BLOCK_PTR_FOR_FN (fn
)->loop_father
= root
;
358 loops
->larray
->quick_push (root
);
359 loops
->tree_root
= root
;
362 /* Returns whether HEADER is a loop header. */
365 bb_loop_header_p (basic_block header
)
370 /* If we have an abnormal predecessor, do not consider the
371 loop (not worth the problems). */
372 if (bb_has_abnormal_pred (header
))
375 /* Look for back edges where a predecessor is dominated
376 by this block. A natural loop has a single entry
377 node (header) that dominates all the nodes in the
378 loop. It also has single back edge to the header
379 from a latch node. */
380 FOR_EACH_EDGE (e
, ei
, header
->preds
)
382 basic_block latch
= e
->src
;
383 if (latch
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
384 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
391 /* Find all the natural loops in the function and save in LOOPS structure and
392 recalculate loop_father information in basic block structures.
393 If LOOPS is non-NULL then the loop structures for already recorded loops
394 will be re-used and their number will not change. We assume that no
395 stale loops exist in LOOPS.
396 When LOOPS is NULL it is allocated and re-built from scratch.
397 Return the built LOOPS structure. */
400 flow_loops_find (struct loops
*loops
)
402 bool from_scratch
= (loops
== NULL
);
407 /* Ensure that the dominators are computed. */
408 calculate_dominance_info (CDI_DOMINATORS
);
412 loops
= ggc_cleared_alloc
<struct loops
> ();
413 init_loops_structure (cfun
, loops
, 1);
416 /* Ensure that loop exits were released. */
417 gcc_assert (loops
->exits
== NULL
);
419 /* Taking care of this degenerate case makes the rest of
420 this code simpler. */
421 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
424 /* The root loop node contains all basic-blocks. */
425 loops
->tree_root
->num_nodes
= n_basic_blocks_for_fn (cfun
);
427 /* Compute depth first search order of the CFG so that outer
428 natural loops will be found before inner natural loops. */
429 rc_order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
430 pre_and_rev_post_order_compute (NULL
, rc_order
, false);
432 /* Gather all loop headers in reverse completion order and allocate
433 loop structures for loops that are not already present. */
434 auto_vec
<loop_p
> larray (loops
->larray
->length ());
435 for (b
= 0; b
< n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
; b
++)
437 basic_block header
= BASIC_BLOCK_FOR_FN (cfun
, rc_order
[b
]);
438 if (bb_loop_header_p (header
))
442 /* The current active loop tree has valid loop-fathers for
445 && header
->loop_father
->header
== header
)
447 loop
= header
->loop_father
;
448 /* If we found an existing loop remove it from the
449 loop tree. It is going to be inserted again
451 flow_loop_tree_node_remove (loop
);
455 /* Otherwise allocate a new loop structure for the loop. */
456 loop
= alloc_loop ();
457 /* ??? We could re-use unused loop slots here. */
458 loop
->num
= loops
->larray
->length ();
459 vec_safe_push (loops
->larray
, loop
);
460 loop
->header
= header
;
463 && dump_file
&& (dump_flags
& TDF_DETAILS
))
464 fprintf (dump_file
, "flow_loops_find: discovered new "
465 "loop %d with header %d\n",
466 loop
->num
, header
->index
);
468 /* Reset latch, we recompute it below. */
470 larray
.safe_push (loop
);
473 /* Make blocks part of the loop root node at start. */
474 header
->loop_father
= loops
->tree_root
;
479 /* Now iterate over the loops found, insert them into the loop tree
480 and assign basic-block ownership. */
481 for (i
= 0; i
< larray
.length (); ++i
)
483 struct loop
*loop
= larray
[i
];
484 basic_block header
= loop
->header
;
488 flow_loop_tree_node_add (header
->loop_father
, loop
);
489 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
491 /* Look for the latch for this header block, if it has just a
493 FOR_EACH_EDGE (e
, ei
, header
->preds
)
495 basic_block latch
= e
->src
;
497 if (flow_bb_inside_loop_p (loop
, latch
))
499 if (loop
->latch
!= NULL
)
501 /* More than one latch edge. */
513 /* Ratio of frequencies of edges so that one of more latch edges is
514 considered to belong to inner loop with same header. */
515 #define HEAVY_EDGE_RATIO 8
517 /* Minimum number of samples for that we apply
518 find_subloop_latch_edge_by_profile heuristics. */
519 #define HEAVY_EDGE_MIN_SAMPLES 10
521 /* If the profile info is available, finds an edge in LATCHES that much more
522 frequent than the remaining edges. Returns such an edge, or NULL if we do
525 We do not use guessed profile here, only the measured one. The guessed
526 profile is usually too flat and unreliable for this (and it is mostly based
527 on the loop structure of the program, so it does not make much sense to
528 derive the loop structure from it). */
531 find_subloop_latch_edge_by_profile (vec
<edge
> latches
)
535 gcov_type mcount
= 0, tcount
= 0;
537 FOR_EACH_VEC_ELT (latches
, i
, e
)
539 if (e
->count
> mcount
)
547 if (tcount
< HEAVY_EDGE_MIN_SAMPLES
548 || (tcount
- mcount
) * HEAVY_EDGE_RATIO
> tcount
)
553 "Found latch edge %d -> %d using profile information.\n",
554 me
->src
->index
, me
->dest
->index
);
558 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
559 on the structure of induction variables. Returns this edge, or NULL if we
562 We are quite conservative, and look just for an obvious simple innermost
563 loop (which is the case where we would lose the most performance by not
564 disambiguating the loop). More precisely, we look for the following
565 situation: The source of the chosen latch edge dominates sources of all
566 the other latch edges. Additionally, the header does not contain a phi node
567 such that the argument from the chosen edge is equal to the argument from
571 find_subloop_latch_edge_by_ivs (struct loop
*loop ATTRIBUTE_UNUSED
, vec
<edge
> latches
)
573 edge e
, latch
= latches
[0];
580 /* Find the candidate for the latch edge. */
581 for (i
= 1; latches
.iterate (i
, &e
); i
++)
582 if (dominated_by_p (CDI_DOMINATORS
, latch
->src
, e
->src
))
585 /* Verify that it dominates all the latch edges. */
586 FOR_EACH_VEC_ELT (latches
, i
, e
)
587 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, latch
->src
))
590 /* Check for a phi node that would deny that this is a latch edge of
592 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
595 lop
= PHI_ARG_DEF_FROM_EDGE (phi
, latch
);
597 /* Ignore the values that are not changed inside the subloop. */
598 if (TREE_CODE (lop
) != SSA_NAME
599 || SSA_NAME_DEF_STMT (lop
) == phi
)
601 bb
= gimple_bb (SSA_NAME_DEF_STMT (lop
));
602 if (!bb
|| !flow_bb_inside_loop_p (loop
, bb
))
605 FOR_EACH_VEC_ELT (latches
, i
, e
)
607 && PHI_ARG_DEF_FROM_EDGE (phi
, e
) == lop
)
613 "Found latch edge %d -> %d using iv structure.\n",
614 latch
->src
->index
, latch
->dest
->index
);
618 /* If we can determine that one of the several latch edges of LOOP behaves
619 as a latch edge of a separate subloop, returns this edge. Otherwise
623 find_subloop_latch_edge (struct loop
*loop
)
625 vec
<edge
> latches
= get_loop_latch_edges (loop
);
628 if (latches
.length () > 1)
630 latch
= find_subloop_latch_edge_by_profile (latches
);
633 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
634 should use cfghook for this, but it is hard to imagine it would
635 be useful elsewhere. */
636 && current_ir_type () == IR_GIMPLE
)
637 latch
= find_subloop_latch_edge_by_ivs (loop
, latches
);
644 /* Callback for make_forwarder_block. Returns true if the edge E is marked
645 in the set MFB_REIS_SET. */
647 static hash_set
<edge
> *mfb_reis_set
;
649 mfb_redirect_edges_in_set (edge e
)
651 return mfb_reis_set
->contains (e
);
654 /* Creates a subloop of LOOP with latch edge LATCH. */
657 form_subloop (struct loop
*loop
, edge latch
)
661 struct loop
*new_loop
;
663 mfb_reis_set
= new hash_set
<edge
>;
664 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
667 mfb_reis_set
->add (e
);
669 new_entry
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
673 loop
->header
= new_entry
->src
;
675 /* Find the blocks and subloops that belong to the new loop, and add it to
676 the appropriate place in the loop tree. */
677 new_loop
= alloc_loop ();
678 new_loop
->header
= new_entry
->dest
;
679 new_loop
->latch
= latch
->src
;
680 add_loop (new_loop
, loop
);
683 /* Make all the latch edges of LOOP to go to a single forwarder block --
684 a new latch of LOOP. */
687 merge_latch_edges (struct loop
*loop
)
689 vec
<edge
> latches
= get_loop_latch_edges (loop
);
693 gcc_assert (latches
.length () > 0);
695 if (latches
.length () == 1)
696 loop
->latch
= latches
[0]->src
;
700 fprintf (dump_file
, "Merged latch edges of loop %d\n", loop
->num
);
702 mfb_reis_set
= new hash_set
<edge
>;
703 FOR_EACH_VEC_ELT (latches
, i
, e
)
704 mfb_reis_set
->add (e
);
705 latch
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
709 loop
->header
= latch
->dest
;
710 loop
->latch
= latch
->src
;
716 /* LOOP may have several latch edges. Transform it into (possibly several)
717 loops with single latch edge. */
720 disambiguate_multiple_latches (struct loop
*loop
)
724 /* We eliminate the multiple latches by splitting the header to the forwarder
725 block F and the rest R, and redirecting the edges. There are two cases:
727 1) If there is a latch edge E that corresponds to a subloop (we guess
728 that based on profile -- if it is taken much more often than the
729 remaining edges; and on trees, using the information about induction
730 variables of the loops), we redirect E to R, all the remaining edges to
731 F, then rescan the loops and try again for the outer loop.
732 2) If there is no such edge, we redirect all latch edges to F, and the
733 entry edges to R, thus making F the single latch of the loop. */
736 fprintf (dump_file
, "Disambiguating loop %d with multiple latches\n",
739 /* During latch merging, we may need to redirect the entry edges to a new
740 block. This would cause problems if the entry edge was the one from the
741 entry block. To avoid having to handle this case specially, split
743 e
= find_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), loop
->header
);
749 e
= find_subloop_latch_edge (loop
);
753 form_subloop (loop
, e
);
756 merge_latch_edges (loop
);
759 /* Split loops with multiple latch edges. */
762 disambiguate_loops_with_multiple_latches (void)
766 FOR_EACH_LOOP (loop
, 0)
769 disambiguate_multiple_latches (loop
);
773 /* Return nonzero if basic block BB belongs to LOOP. */
775 flow_bb_inside_loop_p (const struct loop
*loop
, const_basic_block bb
)
777 struct loop
*source_loop
;
779 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
780 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
783 source_loop
= bb
->loop_father
;
784 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
787 /* Enumeration predicate for get_loop_body_with_size. */
789 glb_enum_p (const_basic_block bb
, const void *glb_loop
)
791 const struct loop
*const loop
= (const struct loop
*) glb_loop
;
792 return (bb
!= loop
->header
793 && dominated_by_p (CDI_DOMINATORS
, bb
, loop
->header
));
796 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
797 order against direction of edges from latch. Specially, if
798 header != latch, latch is the 1-st block. LOOP cannot be the fake
799 loop tree root, and its size must be at most MAX_SIZE. The blocks
800 in the LOOP body are stored to BODY, and the size of the LOOP is
804 get_loop_body_with_size (const struct loop
*loop
, basic_block
*body
,
807 return dfs_enumerate_from (loop
->header
, 1, glb_enum_p
,
808 body
, max_size
, loop
);
811 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
812 order against direction of edges from latch. Specially, if
813 header != latch, latch is the 1-st block. */
816 get_loop_body (const struct loop
*loop
)
818 basic_block
*body
, bb
;
821 gcc_assert (loop
->num_nodes
);
823 body
= XNEWVEC (basic_block
, loop
->num_nodes
);
825 if (loop
->latch
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
827 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
828 special-case the fake loop that contains the whole function. */
829 gcc_assert (loop
->num_nodes
== (unsigned) n_basic_blocks_for_fn (cfun
));
830 body
[tv
++] = loop
->header
;
831 body
[tv
++] = EXIT_BLOCK_PTR_FOR_FN (cfun
);
832 FOR_EACH_BB_FN (bb
, cfun
)
836 tv
= get_loop_body_with_size (loop
, body
, loop
->num_nodes
);
838 gcc_assert (tv
== loop
->num_nodes
);
842 /* Fills dominance descendants inside LOOP of the basic block BB into
843 array TOVISIT from index *TV. */
846 fill_sons_in_loop (const struct loop
*loop
, basic_block bb
,
847 basic_block
*tovisit
, int *tv
)
849 basic_block son
, postpone
= NULL
;
851 tovisit
[(*tv
)++] = bb
;
852 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
854 son
= next_dom_son (CDI_DOMINATORS
, son
))
856 if (!flow_bb_inside_loop_p (loop
, son
))
859 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, son
))
864 fill_sons_in_loop (loop
, son
, tovisit
, tv
);
868 fill_sons_in_loop (loop
, postpone
, tovisit
, tv
);
871 /* Gets body of a LOOP (that must be different from the outermost loop)
872 sorted by dominance relation. Additionally, if a basic block s dominates
873 the latch, then only blocks dominated by s are be after it. */
876 get_loop_body_in_dom_order (const struct loop
*loop
)
878 basic_block
*tovisit
;
881 gcc_assert (loop
->num_nodes
);
883 tovisit
= XNEWVEC (basic_block
, loop
->num_nodes
);
885 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
888 fill_sons_in_loop (loop
, loop
->header
, tovisit
, &tv
);
890 gcc_assert (tv
== (int) loop
->num_nodes
);
895 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
898 get_loop_body_in_custom_order (const struct loop
*loop
,
899 int (*bb_comparator
) (const void *, const void *))
901 basic_block
*bbs
= get_loop_body (loop
);
903 qsort (bbs
, loop
->num_nodes
, sizeof (basic_block
), bb_comparator
);
908 /* Get body of a LOOP in breadth first sort order. */
911 get_loop_body_in_bfs_order (const struct loop
*loop
)
919 gcc_assert (loop
->num_nodes
);
920 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
922 blocks
= XNEWVEC (basic_block
, loop
->num_nodes
);
923 visited
= BITMAP_ALLOC (NULL
);
926 while (i
< loop
->num_nodes
)
931 if (bitmap_set_bit (visited
, bb
->index
))
932 /* This basic block is now visited */
935 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
937 if (flow_bb_inside_loop_p (loop
, e
->dest
))
939 if (bitmap_set_bit (visited
, e
->dest
->index
))
940 blocks
[i
++] = e
->dest
;
949 BITMAP_FREE (visited
);
953 /* Hash function for struct loop_exit. */
956 loop_exit_hasher::hash (loop_exit
*exit
)
958 return htab_hash_pointer (exit
->e
);
961 /* Equality function for struct loop_exit. Compares with edge. */
964 loop_exit_hasher::equal (loop_exit
*exit
, edge e
)
969 /* Frees the list of loop exit descriptions EX. */
972 loop_exit_hasher::remove (loop_exit
*exit
)
975 for (; exit
; exit
= next
)
979 exit
->next
->prev
= exit
->prev
;
980 exit
->prev
->next
= exit
->next
;
986 /* Returns the list of records for E as an exit of a loop. */
988 static struct loop_exit
*
989 get_exit_descriptions (edge e
)
991 return current_loops
->exits
->find_with_hash (e
, htab_hash_pointer (e
));
994 /* Updates the lists of loop exits in that E appears.
995 If REMOVED is true, E is being removed, and we
996 just remove it from the lists of exits.
997 If NEW_EDGE is true and E is not a loop exit, we
998 do not try to remove it from loop exit lists. */
1001 rescan_loop_exit (edge e
, bool new_edge
, bool removed
)
1003 struct loop_exit
*exits
= NULL
, *exit
;
1004 struct loop
*aloop
, *cloop
;
1006 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1010 && e
->src
->loop_father
!= NULL
1011 && e
->dest
->loop_father
!= NULL
1012 && !flow_bb_inside_loop_p (e
->src
->loop_father
, e
->dest
))
1014 cloop
= find_common_loop (e
->src
->loop_father
, e
->dest
->loop_father
);
1015 for (aloop
= e
->src
->loop_father
;
1017 aloop
= loop_outer (aloop
))
1019 exit
= ggc_alloc
<loop_exit
> ();
1022 exit
->next
= aloop
->exits
->next
;
1023 exit
->prev
= aloop
->exits
;
1024 exit
->next
->prev
= exit
;
1025 exit
->prev
->next
= exit
;
1027 exit
->next_e
= exits
;
1032 if (!exits
&& new_edge
)
1036 = current_loops
->exits
->find_slot_with_hash (e
, htab_hash_pointer (e
),
1037 exits
? INSERT
: NO_INSERT
);
1044 loop_exit_hasher::remove (*slot
);
1048 current_loops
->exits
->clear_slot (slot
);
1051 /* For each loop, record list of exit edges, and start maintaining these
1055 record_loop_exits (void)
1064 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1066 loops_state_set (LOOPS_HAVE_RECORDED_EXITS
);
1068 gcc_assert (current_loops
->exits
== NULL
);
1069 current_loops
->exits
1070 = hash_table
<loop_exit_hasher
>::create_ggc (2 * number_of_loops (cfun
));
1072 FOR_EACH_BB_FN (bb
, cfun
)
1074 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1076 rescan_loop_exit (e
, true, false);
1081 /* Dumps information about the exit in *SLOT to FILE.
1082 Callback for htab_traverse. */
1085 dump_recorded_exit (loop_exit
**slot
, FILE *file
)
1087 struct loop_exit
*exit
= *slot
;
1091 for (; exit
!= NULL
; exit
= exit
->next_e
)
1094 fprintf (file
, "Edge %d->%d exits %u loops\n",
1095 e
->src
->index
, e
->dest
->index
, n
);
1100 /* Dumps the recorded exits of loops to FILE. */
1102 extern void dump_recorded_exits (FILE *);
1104 dump_recorded_exits (FILE *file
)
1106 if (!current_loops
->exits
)
1108 current_loops
->exits
->traverse
<FILE *, dump_recorded_exit
> (file
);
1111 /* Releases lists of loop exits. */
1114 release_recorded_exits (function
*fn
)
1116 gcc_assert (loops_state_satisfies_p (fn
, LOOPS_HAVE_RECORDED_EXITS
));
1117 loops_for_fn (fn
)->exits
->empty ();
1118 loops_for_fn (fn
)->exits
= NULL
;
1119 loops_state_clear (fn
, LOOPS_HAVE_RECORDED_EXITS
);
1122 /* Returns the list of the exit edges of a LOOP. */
1125 get_loop_exit_edges (const struct loop
*loop
)
1127 vec
<edge
> edges
= vNULL
;
1132 struct loop_exit
*exit
;
1134 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1136 /* If we maintain the lists of exits, use them. Otherwise we must
1137 scan the body of the loop. */
1138 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1140 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1141 edges
.safe_push (exit
->e
);
1145 body
= get_loop_body (loop
);
1146 for (i
= 0; i
< loop
->num_nodes
; i
++)
1147 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
1149 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1150 edges
.safe_push (e
);
1158 /* Counts the number of conditional branches inside LOOP. */
1161 num_loop_branches (const struct loop
*loop
)
1166 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1168 body
= get_loop_body (loop
);
1170 for (i
= 0; i
< loop
->num_nodes
; i
++)
1171 if (EDGE_COUNT (body
[i
]->succs
) >= 2)
1178 /* Adds basic block BB to LOOP. */
1180 add_bb_to_loop (basic_block bb
, struct loop
*loop
)
1187 gcc_assert (bb
->loop_father
== NULL
);
1188 bb
->loop_father
= loop
;
1190 FOR_EACH_VEC_SAFE_ELT (loop
->superloops
, i
, ploop
)
1193 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1195 rescan_loop_exit (e
, true, false);
1197 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1199 rescan_loop_exit (e
, true, false);
1203 /* Remove basic block BB from loops. */
1205 remove_bb_from_loops (basic_block bb
)
1208 struct loop
*loop
= bb
->loop_father
;
1213 gcc_assert (loop
!= NULL
);
1215 FOR_EACH_VEC_SAFE_ELT (loop
->superloops
, i
, ploop
)
1217 bb
->loop_father
= NULL
;
1219 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1221 rescan_loop_exit (e
, false, true);
1223 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1225 rescan_loop_exit (e
, false, true);
1229 /* Finds nearest common ancestor in loop tree for given loops. */
1231 find_common_loop (struct loop
*loop_s
, struct loop
*loop_d
)
1233 unsigned sdepth
, ddepth
;
1235 if (!loop_s
) return loop_d
;
1236 if (!loop_d
) return loop_s
;
1238 sdepth
= loop_depth (loop_s
);
1239 ddepth
= loop_depth (loop_d
);
1241 if (sdepth
< ddepth
)
1242 loop_d
= (*loop_d
->superloops
)[sdepth
];
1243 else if (sdepth
> ddepth
)
1244 loop_s
= (*loop_s
->superloops
)[ddepth
];
1246 while (loop_s
!= loop_d
)
1248 loop_s
= loop_outer (loop_s
);
1249 loop_d
= loop_outer (loop_d
);
1254 /* Removes LOOP from structures and frees its data. */
1257 delete_loop (struct loop
*loop
)
1259 /* Remove the loop from structure. */
1260 flow_loop_tree_node_remove (loop
);
1262 /* Remove loop from loops array. */
1263 (*current_loops
->larray
)[loop
->num
] = NULL
;
1265 /* Free loop data. */
1266 flow_loop_free (loop
);
1269 /* Cancels the LOOP; it must be innermost one. */
1272 cancel_loop (struct loop
*loop
)
1276 struct loop
*outer
= loop_outer (loop
);
1278 gcc_assert (!loop
->inner
);
1280 /* Move blocks up one level (they should be removed as soon as possible). */
1281 bbs
= get_loop_body (loop
);
1282 for (i
= 0; i
< loop
->num_nodes
; i
++)
1283 bbs
[i
]->loop_father
= outer
;
1289 /* Cancels LOOP and all its subloops. */
1291 cancel_loop_tree (struct loop
*loop
)
1294 cancel_loop_tree (loop
->inner
);
1298 /* Checks that information about loops is correct
1299 -- sizes of loops are all right
1300 -- results of get_loop_body really belong to the loop
1301 -- loop header have just single entry edge and single latch edge
1302 -- loop latches have only single successor that is header of their loop
1303 -- irreducible loops are correctly marked
1304 -- the cached loop depth and loop father of each bb is correct
1307 verify_loop_structure (void)
1309 unsigned *sizes
, i
, j
;
1311 basic_block bb
, *bbs
;
1315 unsigned num
= number_of_loops (cfun
);
1316 struct loop_exit
*exit
, *mexit
;
1317 bool dom_available
= dom_info_available_p (CDI_DOMINATORS
);
1320 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
1322 error ("loop verification on loop tree that needs fixup");
1326 /* We need up-to-date dominators, compute or verify them. */
1328 calculate_dominance_info (CDI_DOMINATORS
);
1330 verify_dominators (CDI_DOMINATORS
);
1332 /* Check the loop tree root. */
1333 if (current_loops
->tree_root
->header
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1334 || current_loops
->tree_root
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1335 || (current_loops
->tree_root
->num_nodes
1336 != (unsigned) n_basic_blocks_for_fn (cfun
)))
1338 error ("corrupt loop tree root");
1342 /* Check the headers. */
1343 FOR_EACH_BB_FN (bb
, cfun
)
1344 if (bb_loop_header_p (bb
))
1346 if (bb
->loop_father
->header
== NULL
)
1348 error ("loop with header %d marked for removal", bb
->index
);
1351 else if (bb
->loop_father
->header
!= bb
)
1353 error ("loop with header %d not in loop tree", bb
->index
);
1357 else if (bb
->loop_father
->header
== bb
)
1359 error ("non-loop with header %d not marked for removal", bb
->index
);
1363 /* Check the recorded loop father and sizes of loops. */
1364 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1365 bitmap_clear (visited
);
1366 bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
1367 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1371 if (loop
->header
== NULL
)
1373 error ("removed loop %d in loop tree", loop
->num
);
1378 n
= get_loop_body_with_size (loop
, bbs
, n_basic_blocks_for_fn (cfun
));
1379 if (loop
->num_nodes
!= n
)
1381 error ("size of loop %d should be %d, not %d",
1382 loop
->num
, n
, loop
->num_nodes
);
1386 for (j
= 0; j
< n
; j
++)
1390 if (!flow_bb_inside_loop_p (loop
, bb
))
1392 error ("bb %d does not belong to loop %d",
1393 bb
->index
, loop
->num
);
1397 /* Ignore this block if it is in an inner loop. */
1398 if (bitmap_bit_p (visited
, bb
->index
))
1400 bitmap_set_bit (visited
, bb
->index
);
1402 if (bb
->loop_father
!= loop
)
1404 error ("bb %d has father loop %d, should be loop %d",
1405 bb
->index
, bb
->loop_father
->num
, loop
->num
);
1411 sbitmap_free (visited
);
1413 /* Check headers and latches. */
1414 FOR_EACH_LOOP (loop
, 0)
1417 if (loop
->header
== NULL
)
1419 if (!bb_loop_header_p (loop
->header
))
1421 error ("loop %d%'s header is not a loop header", i
);
1424 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
)
1425 && EDGE_COUNT (loop
->header
->preds
) != 2)
1427 error ("loop %d%'s header does not have exactly 2 entries", i
);
1432 if (!find_edge (loop
->latch
, loop
->header
))
1434 error ("loop %d%'s latch does not have an edge to its header", i
);
1437 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, loop
->header
))
1439 error ("loop %d%'s latch is not dominated by its header", i
);
1443 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
1445 if (!single_succ_p (loop
->latch
))
1447 error ("loop %d%'s latch does not have exactly 1 successor", i
);
1450 if (single_succ (loop
->latch
) != loop
->header
)
1452 error ("loop %d%'s latch does not have header as successor", i
);
1455 if (loop
->latch
->loop_father
!= loop
)
1457 error ("loop %d%'s latch does not belong directly to it", i
);
1461 if (loop
->header
->loop_father
!= loop
)
1463 error ("loop %d%'s header does not belong directly to it", i
);
1466 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1467 && (loop_latch_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
))
1469 error ("loop %d%'s latch is marked as part of irreducible region", i
);
1474 /* Check irreducible loops. */
1475 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1477 /* Record old info. */
1478 irreds
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1479 FOR_EACH_BB_FN (bb
, cfun
)
1482 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1483 bitmap_set_bit (irreds
, bb
->index
);
1485 bitmap_clear_bit (irreds
, bb
->index
);
1486 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1487 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1488 e
->flags
|= EDGE_ALL_FLAGS
+ 1;
1492 mark_irreducible_loops ();
1495 FOR_EACH_BB_FN (bb
, cfun
)
1499 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1500 && !bitmap_bit_p (irreds
, bb
->index
))
1502 error ("basic block %d should be marked irreducible", bb
->index
);
1505 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1506 && bitmap_bit_p (irreds
, bb
->index
))
1508 error ("basic block %d should not be marked irreducible", bb
->index
);
1511 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1513 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1514 && !(e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1516 error ("edge from %d to %d should be marked irreducible",
1517 e
->src
->index
, e
->dest
->index
);
1520 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1521 && (e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1523 error ("edge from %d to %d should not be marked irreducible",
1524 e
->src
->index
, e
->dest
->index
);
1527 e
->flags
&= ~(EDGE_ALL_FLAGS
+ 1);
1533 /* Check the recorded loop exits. */
1534 FOR_EACH_LOOP (loop
, 0)
1536 if (!loop
->exits
|| loop
->exits
->e
!= NULL
)
1538 error ("corrupted head of the exits list of loop %d",
1544 /* Check that the list forms a cycle, and all elements except
1545 for the head are nonnull. */
1546 for (mexit
= loop
->exits
, exit
= mexit
->next
, i
= 0;
1547 exit
->e
&& exit
!= mexit
;
1551 mexit
= mexit
->next
;
1554 if (exit
!= loop
->exits
)
1556 error ("corrupted exits list of loop %d", loop
->num
);
1561 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1563 if (loop
->exits
->next
!= loop
->exits
)
1565 error ("nonempty exits list of loop %d, but exits are not recorded",
1572 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1574 unsigned n_exits
= 0, eloops
;
1576 sizes
= XCNEWVEC (unsigned, num
);
1577 memset (sizes
, 0, sizeof (unsigned) * num
);
1578 FOR_EACH_BB_FN (bb
, cfun
)
1581 if (bb
->loop_father
== current_loops
->tree_root
)
1583 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1585 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
1589 exit
= get_exit_descriptions (e
);
1592 error ("exit %d->%d not recorded",
1593 e
->src
->index
, e
->dest
->index
);
1597 for (; exit
; exit
= exit
->next_e
)
1600 for (loop
= bb
->loop_father
;
1601 loop
!= e
->dest
->loop_father
1602 /* When a loop exit is also an entry edge which
1603 can happen when avoiding CFG manipulations
1604 then the last loop exited is the outer loop
1605 of the loop entered. */
1606 && loop
!= loop_outer (e
->dest
->loop_father
);
1607 loop
= loop_outer (loop
))
1615 error ("wrong list of exited loops for edge %d->%d",
1616 e
->src
->index
, e
->dest
->index
);
1622 if (n_exits
!= current_loops
->exits
->elements ())
1624 error ("too many loop exits recorded");
1628 FOR_EACH_LOOP (loop
, 0)
1631 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1633 if (eloops
!= sizes
[loop
->num
])
1635 error ("%d exits recorded for loop %d (having %d exits)",
1636 eloops
, loop
->num
, sizes
[loop
->num
]);
1647 free_dominance_info (CDI_DOMINATORS
);
1650 /* Returns latch edge of LOOP. */
1652 loop_latch_edge (const struct loop
*loop
)
1654 return find_edge (loop
->latch
, loop
->header
);
1657 /* Returns preheader edge of LOOP. */
1659 loop_preheader_edge (const struct loop
*loop
)
1664 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
));
1666 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1667 if (e
->src
!= loop
->latch
)
1673 /* Returns true if E is an exit of LOOP. */
1676 loop_exit_edge_p (const struct loop
*loop
, const_edge e
)
1678 return (flow_bb_inside_loop_p (loop
, e
->src
)
1679 && !flow_bb_inside_loop_p (loop
, e
->dest
));
1682 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1683 or more than one exit. If loops do not have the exits recorded, NULL
1684 is returned always. */
1687 single_exit (const struct loop
*loop
)
1689 struct loop_exit
*exit
= loop
->exits
->next
;
1691 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1694 if (exit
->e
&& exit
->next
== loop
->exits
)
1700 /* Returns true when BB has an incoming edge exiting LOOP. */
1703 loop_exits_to_bb_p (struct loop
*loop
, basic_block bb
)
1708 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1709 if (loop_exit_edge_p (loop
, e
))
1715 /* Returns true when BB has an outgoing edge exiting LOOP. */
1718 loop_exits_from_bb_p (struct loop
*loop
, basic_block bb
)
1723 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1724 if (loop_exit_edge_p (loop
, e
))
1730 /* Return location corresponding to the loop control condition if possible. */
1733 get_loop_location (struct loop
*loop
)
1735 rtx_insn
*insn
= NULL
;
1736 struct niter_desc
*desc
= NULL
;
1739 /* For a for or while loop, we would like to return the location
1740 of the for or while statement, if possible. To do this, look
1741 for the branch guarding the loop back-edge. */
1743 /* If this is a simple loop with an in_edge, then the loop control
1744 branch is typically at the end of its source. */
1745 desc
= get_simple_loop_desc (loop
);
1748 FOR_BB_INSNS_REVERSE (desc
->in_edge
->src
, insn
)
1750 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1751 return INSN_LOCATION (insn
);
1754 /* If loop has a single exit, then the loop control branch
1755 must be at the end of its source. */
1756 if ((exit
= single_exit (loop
)))
1758 FOR_BB_INSNS_REVERSE (exit
->src
, insn
)
1760 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1761 return INSN_LOCATION (insn
);
1764 /* Next check the latch, to see if it is non-empty. */
1765 FOR_BB_INSNS_REVERSE (loop
->latch
, insn
)
1767 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1768 return INSN_LOCATION (insn
);
1770 /* Finally, if none of the above identifies the loop control branch,
1771 return the first location in the loop header. */
1772 FOR_BB_INSNS (loop
->header
, insn
)
1774 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1775 return INSN_LOCATION (insn
);
1777 /* If all else fails, simply return the current function location. */
1778 return DECL_SOURCE_LOCATION (current_function_decl
);
1781 /* Records that every statement in LOOP is executed I_BOUND times.
1782 REALISTIC is true if I_BOUND is expected to be close to the real number
1783 of iterations. UPPER is true if we are sure the loop iterates at most
1787 record_niter_bound (struct loop
*loop
, const widest_int
&i_bound
,
1788 bool realistic
, bool upper
)
1790 /* Update the bounds only when there is no previous estimation, or when the
1791 current estimation is smaller. */
1793 && (!loop
->any_upper_bound
1794 || wi::ltu_p (i_bound
, loop
->nb_iterations_upper_bound
)))
1796 loop
->any_upper_bound
= true;
1797 loop
->nb_iterations_upper_bound
= i_bound
;
1800 && (!loop
->any_estimate
1801 || wi::ltu_p (i_bound
, loop
->nb_iterations_estimate
)))
1803 loop
->any_estimate
= true;
1804 loop
->nb_iterations_estimate
= i_bound
;
1807 /* If an upper bound is smaller than the realistic estimate of the
1808 number of iterations, use the upper bound instead. */
1809 if (loop
->any_upper_bound
1810 && loop
->any_estimate
1811 && wi::ltu_p (loop
->nb_iterations_upper_bound
,
1812 loop
->nb_iterations_estimate
))
1813 loop
->nb_iterations_estimate
= loop
->nb_iterations_upper_bound
;
1816 /* Similar to get_estimated_loop_iterations, but returns the estimate only
1817 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1818 on the number of iterations of LOOP could not be derived, returns -1. */
1821 get_estimated_loop_iterations_int (struct loop
*loop
)
1824 HOST_WIDE_INT hwi_nit
;
1826 if (!get_estimated_loop_iterations (loop
, &nit
))
1829 if (!wi::fits_shwi_p (nit
))
1831 hwi_nit
= nit
.to_shwi ();
1833 return hwi_nit
< 0 ? -1 : hwi_nit
;
1836 /* Returns an upper bound on the number of executions of statements
1837 in the LOOP. For statements before the loop exit, this exceeds
1838 the number of execution of the latch by one. */
1841 max_stmt_executions_int (struct loop
*loop
)
1843 HOST_WIDE_INT nit
= get_max_loop_iterations_int (loop
);
1849 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
1851 /* If the computation overflows, return -1. */
1852 return snit
< 0 ? -1 : snit
;
1855 /* Sets NIT to the estimated number of executions of the latch of the
1856 LOOP. If we have no reliable estimate, the function returns false, otherwise
1860 get_estimated_loop_iterations (struct loop
*loop
, widest_int
*nit
)
1862 /* Even if the bound is not recorded, possibly we can derrive one from
1864 if (!loop
->any_estimate
)
1866 if (loop
->header
->count
)
1868 *nit
= gcov_type_to_wide_int
1869 (expected_loop_iterations_unbounded (loop
) + 1);
1875 *nit
= loop
->nb_iterations_estimate
;
1879 /* Sets NIT to an upper bound for the maximum number of executions of the
1880 latch of the LOOP. If we have no reliable estimate, the function returns
1881 false, otherwise returns true. */
1884 get_max_loop_iterations (struct loop
*loop
, widest_int
*nit
)
1886 if (!loop
->any_upper_bound
)
1889 *nit
= loop
->nb_iterations_upper_bound
;
1893 /* Similar to get_max_loop_iterations, but returns the estimate only
1894 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1895 on the number of iterations of LOOP could not be derived, returns -1. */
1898 get_max_loop_iterations_int (struct loop
*loop
)
1901 HOST_WIDE_INT hwi_nit
;
1903 if (!get_max_loop_iterations (loop
, &nit
))
1906 if (!wi::fits_shwi_p (nit
))
1908 hwi_nit
= nit
.to_shwi ();
1910 return hwi_nit
< 0 ? -1 : hwi_nit
;
1913 /* Returns the loop depth of the loop BB belongs to. */
1916 bb_loop_depth (const_basic_block bb
)
1918 return bb
->loop_father
? loop_depth (bb
->loop_father
) : 0;
1921 /* Marks LOOP for removal and sets LOOPS_NEED_FIXUP. */
1924 mark_loop_for_removal (loop_p loop
)
1926 if (loop
->header
== NULL
)
1928 loop
->former_header
= loop
->header
;
1929 loop
->header
= NULL
;
1931 loops_state_set (LOOPS_NEED_FIXUP
);