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"
30 #include "hard-reg-set.h"
34 #include "dominance.h"
37 #include "basic-block.h"
39 #include "diagnostic-core.h"
42 #include "fold-const.h"
43 #include "tree-ssa-alias.h"
44 #include "internal-fn.h"
45 #include "gimple-expr.h"
48 #include "gimple-iterator.h"
49 #include "gimple-ssa.h"
52 static void flow_loops_cfg_dump (FILE *);
54 /* Dump loop related CFG information. */
57 flow_loops_cfg_dump (FILE *file
)
64 FOR_EACH_BB_FN (bb
, cfun
)
69 fprintf (file
, ";; %d succs { ", bb
->index
);
70 FOR_EACH_EDGE (succ
, ei
, bb
->succs
)
71 fprintf (file
, "%d ", succ
->dest
->index
);
72 fprintf (file
, "}\n");
76 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
79 flow_loop_nested_p (const struct loop
*outer
, const struct loop
*loop
)
81 unsigned odepth
= loop_depth (outer
);
83 return (loop_depth (loop
) > odepth
84 && (*loop
->superloops
)[odepth
] == outer
);
87 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
91 superloop_at_depth (struct loop
*loop
, unsigned depth
)
93 unsigned ldepth
= loop_depth (loop
);
95 gcc_assert (depth
<= ldepth
);
100 return (*loop
->superloops
)[depth
];
103 /* Returns the list of the latch edges of LOOP. */
106 get_loop_latch_edges (const struct loop
*loop
)
110 vec
<edge
> ret
= vNULL
;
112 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
114 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, loop
->header
))
121 /* Dump the loop information specified by LOOP to the stream FILE
122 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
125 flow_loop_dump (const struct loop
*loop
, FILE *file
,
126 void (*loop_dump_aux
) (const struct loop
*, FILE *, int),
134 if (! loop
|| ! loop
->header
)
137 fprintf (file
, ";;\n;; Loop %d\n", loop
->num
);
139 fprintf (file
, ";; header %d, ", loop
->header
->index
);
141 fprintf (file
, "latch %d\n", loop
->latch
->index
);
144 fprintf (file
, "multiple latches:");
145 latches
= get_loop_latch_edges (loop
);
146 FOR_EACH_VEC_ELT (latches
, i
, e
)
147 fprintf (file
, " %d", e
->src
->index
);
149 fprintf (file
, "\n");
152 fprintf (file
, ";; depth %d, outer %ld\n",
153 loop_depth (loop
), (long) (loop_outer (loop
)
154 ? loop_outer (loop
)->num
: -1));
156 fprintf (file
, ";; nodes:");
157 bbs
= get_loop_body (loop
);
158 for (i
= 0; i
< loop
->num_nodes
; i
++)
159 fprintf (file
, " %d", bbs
[i
]->index
);
161 fprintf (file
, "\n");
164 loop_dump_aux (loop
, file
, verbose
);
167 /* Dump the loop information about loops to the stream FILE,
168 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
171 flow_loops_dump (FILE *file
, void (*loop_dump_aux
) (const struct loop
*, FILE *, int), int verbose
)
175 if (!current_loops
|| ! file
)
178 fprintf (file
, ";; %d loops found\n", number_of_loops (cfun
));
180 FOR_EACH_LOOP (loop
, LI_INCLUDE_ROOT
)
182 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
);
186 flow_loops_cfg_dump (file
);
189 /* Free data allocated for LOOP. */
192 flow_loop_free (struct loop
*loop
)
194 struct loop_exit
*exit
, *next
;
196 vec_free (loop
->superloops
);
198 /* Break the list of the loop exit records. They will be freed when the
199 corresponding edge is rescanned or removed, and this avoids
200 accessing the (already released) head of the list stored in the
202 for (exit
= loop
->exits
->next
; exit
!= loop
->exits
; exit
= next
)
209 ggc_free (loop
->exits
);
213 /* Free all the memory allocated for LOOPS. */
216 flow_loops_free (struct loops
*loops
)
223 /* Free the loop descriptors. */
224 FOR_EACH_VEC_SAFE_ELT (loops
->larray
, i
, loop
)
229 flow_loop_free (loop
);
232 vec_free (loops
->larray
);
236 /* Find the nodes contained within the LOOP with header HEADER.
237 Return the number of nodes within the loop. */
240 flow_loop_nodes_find (basic_block header
, struct loop
*loop
)
242 vec
<basic_block
> stack
= vNULL
;
245 edge_iterator latch_ei
;
247 header
->loop_father
= loop
;
249 FOR_EACH_EDGE (latch
, latch_ei
, loop
->header
->preds
)
251 if (latch
->src
->loop_father
== loop
252 || !dominated_by_p (CDI_DOMINATORS
, latch
->src
, loop
->header
))
256 stack
.safe_push (latch
->src
);
257 latch
->src
->loop_father
= loop
;
259 while (!stack
.is_empty ())
267 FOR_EACH_EDGE (e
, ei
, node
->preds
)
269 basic_block ancestor
= e
->src
;
271 if (ancestor
->loop_father
!= loop
)
273 ancestor
->loop_father
= loop
;
275 stack
.safe_push (ancestor
);
285 /* Records the vector of superloops of the loop LOOP, whose immediate
286 superloop is FATHER. */
289 establish_preds (struct loop
*loop
, struct loop
*father
)
292 unsigned depth
= loop_depth (father
) + 1;
295 loop
->superloops
= 0;
296 vec_alloc (loop
->superloops
, depth
);
297 FOR_EACH_VEC_SAFE_ELT (father
->superloops
, i
, ploop
)
298 loop
->superloops
->quick_push (ploop
);
299 loop
->superloops
->quick_push (father
);
301 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
302 establish_preds (ploop
, loop
);
305 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
306 added loop. If LOOP has some children, take care of that their
307 pred field will be initialized correctly. */
310 flow_loop_tree_node_add (struct loop
*father
, struct loop
*loop
)
312 loop
->next
= father
->inner
;
313 father
->inner
= loop
;
315 establish_preds (loop
, father
);
318 /* Remove LOOP from the loop hierarchy tree. */
321 flow_loop_tree_node_remove (struct loop
*loop
)
323 struct loop
*prev
, *father
;
325 father
= loop_outer (loop
);
327 /* Remove loop from the list of sons. */
328 if (father
->inner
== loop
)
329 father
->inner
= loop
->next
;
332 for (prev
= father
->inner
; prev
->next
!= loop
; prev
= prev
->next
)
334 prev
->next
= loop
->next
;
337 loop
->superloops
= NULL
;
340 /* Allocates and returns new loop structure. */
345 struct loop
*loop
= ggc_cleared_alloc
<struct loop
> ();
347 loop
->exits
= ggc_cleared_alloc
<loop_exit
> ();
348 loop
->exits
->next
= loop
->exits
->prev
= loop
->exits
;
349 loop
->can_be_parallel
= false;
350 loop
->nb_iterations_upper_bound
= 0;
351 loop
->nb_iterations_estimate
= 0;
355 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
356 (including the root of the loop tree). */
359 init_loops_structure (struct function
*fn
,
360 struct loops
*loops
, unsigned num_loops
)
364 memset (loops
, 0, sizeof *loops
);
365 vec_alloc (loops
->larray
, num_loops
);
367 /* Dummy loop containing whole function. */
368 root
= alloc_loop ();
369 root
->num_nodes
= n_basic_blocks_for_fn (fn
);
370 root
->latch
= EXIT_BLOCK_PTR_FOR_FN (fn
);
371 root
->header
= ENTRY_BLOCK_PTR_FOR_FN (fn
);
372 ENTRY_BLOCK_PTR_FOR_FN (fn
)->loop_father
= root
;
373 EXIT_BLOCK_PTR_FOR_FN (fn
)->loop_father
= root
;
375 loops
->larray
->quick_push (root
);
376 loops
->tree_root
= root
;
379 /* Returns whether HEADER is a loop header. */
382 bb_loop_header_p (basic_block header
)
387 /* If we have an abnormal predecessor, do not consider the
388 loop (not worth the problems). */
389 if (bb_has_abnormal_pred (header
))
392 /* Look for back edges where a predecessor is dominated
393 by this block. A natural loop has a single entry
394 node (header) that dominates all the nodes in the
395 loop. It also has single back edge to the header
396 from a latch node. */
397 FOR_EACH_EDGE (e
, ei
, header
->preds
)
399 basic_block latch
= e
->src
;
400 if (latch
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
401 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
408 /* Find all the natural loops in the function and save in LOOPS structure and
409 recalculate loop_father information in basic block structures.
410 If LOOPS is non-NULL then the loop structures for already recorded loops
411 will be re-used and their number will not change. We assume that no
412 stale loops exist in LOOPS.
413 When LOOPS is NULL it is allocated and re-built from scratch.
414 Return the built LOOPS structure. */
417 flow_loops_find (struct loops
*loops
)
419 bool from_scratch
= (loops
== NULL
);
424 /* Ensure that the dominators are computed. */
425 calculate_dominance_info (CDI_DOMINATORS
);
429 loops
= ggc_cleared_alloc
<struct loops
> ();
430 init_loops_structure (cfun
, loops
, 1);
433 /* Ensure that loop exits were released. */
434 gcc_assert (loops
->exits
== NULL
);
436 /* Taking care of this degenerate case makes the rest of
437 this code simpler. */
438 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
441 /* The root loop node contains all basic-blocks. */
442 loops
->tree_root
->num_nodes
= n_basic_blocks_for_fn (cfun
);
444 /* Compute depth first search order of the CFG so that outer
445 natural loops will be found before inner natural loops. */
446 rc_order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
447 pre_and_rev_post_order_compute (NULL
, rc_order
, false);
449 /* Gather all loop headers in reverse completion order and allocate
450 loop structures for loops that are not already present. */
451 auto_vec
<loop_p
> larray (loops
->larray
->length ());
452 for (b
= 0; b
< n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
; b
++)
454 basic_block header
= BASIC_BLOCK_FOR_FN (cfun
, rc_order
[b
]);
455 if (bb_loop_header_p (header
))
459 /* The current active loop tree has valid loop-fathers for
462 && header
->loop_father
->header
== header
)
464 loop
= header
->loop_father
;
465 /* If we found an existing loop remove it from the
466 loop tree. It is going to be inserted again
468 flow_loop_tree_node_remove (loop
);
472 /* Otherwise allocate a new loop structure for the loop. */
473 loop
= alloc_loop ();
474 /* ??? We could re-use unused loop slots here. */
475 loop
->num
= loops
->larray
->length ();
476 vec_safe_push (loops
->larray
, loop
);
477 loop
->header
= header
;
480 && dump_file
&& (dump_flags
& TDF_DETAILS
))
481 fprintf (dump_file
, "flow_loops_find: discovered new "
482 "loop %d with header %d\n",
483 loop
->num
, header
->index
);
485 /* Reset latch, we recompute it below. */
487 larray
.safe_push (loop
);
490 /* Make blocks part of the loop root node at start. */
491 header
->loop_father
= loops
->tree_root
;
496 /* Now iterate over the loops found, insert them into the loop tree
497 and assign basic-block ownership. */
498 for (i
= 0; i
< larray
.length (); ++i
)
500 struct loop
*loop
= larray
[i
];
501 basic_block header
= loop
->header
;
505 flow_loop_tree_node_add (header
->loop_father
, loop
);
506 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
508 /* Look for the latch for this header block, if it has just a
510 FOR_EACH_EDGE (e
, ei
, header
->preds
)
512 basic_block latch
= e
->src
;
514 if (flow_bb_inside_loop_p (loop
, latch
))
516 if (loop
->latch
!= NULL
)
518 /* More than one latch edge. */
530 /* Ratio of frequencies of edges so that one of more latch edges is
531 considered to belong to inner loop with same header. */
532 #define HEAVY_EDGE_RATIO 8
534 /* Minimum number of samples for that we apply
535 find_subloop_latch_edge_by_profile heuristics. */
536 #define HEAVY_EDGE_MIN_SAMPLES 10
538 /* If the profile info is available, finds an edge in LATCHES that much more
539 frequent than the remaining edges. Returns such an edge, or NULL if we do
542 We do not use guessed profile here, only the measured one. The guessed
543 profile is usually too flat and unreliable for this (and it is mostly based
544 on the loop structure of the program, so it does not make much sense to
545 derive the loop structure from it). */
548 find_subloop_latch_edge_by_profile (vec
<edge
> latches
)
552 gcov_type mcount
= 0, tcount
= 0;
554 FOR_EACH_VEC_ELT (latches
, i
, e
)
556 if (e
->count
> mcount
)
564 if (tcount
< HEAVY_EDGE_MIN_SAMPLES
565 || (tcount
- mcount
) * HEAVY_EDGE_RATIO
> tcount
)
570 "Found latch edge %d -> %d using profile information.\n",
571 me
->src
->index
, me
->dest
->index
);
575 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
576 on the structure of induction variables. Returns this edge, or NULL if we
579 We are quite conservative, and look just for an obvious simple innermost
580 loop (which is the case where we would lose the most performance by not
581 disambiguating the loop). More precisely, we look for the following
582 situation: The source of the chosen latch edge dominates sources of all
583 the other latch edges. Additionally, the header does not contain a phi node
584 such that the argument from the chosen edge is equal to the argument from
588 find_subloop_latch_edge_by_ivs (struct loop
*loop ATTRIBUTE_UNUSED
, vec
<edge
> latches
)
590 edge e
, latch
= latches
[0];
597 /* Find the candidate for the latch edge. */
598 for (i
= 1; latches
.iterate (i
, &e
); i
++)
599 if (dominated_by_p (CDI_DOMINATORS
, latch
->src
, e
->src
))
602 /* Verify that it dominates all the latch edges. */
603 FOR_EACH_VEC_ELT (latches
, i
, e
)
604 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, latch
->src
))
607 /* Check for a phi node that would deny that this is a latch edge of
609 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
612 lop
= PHI_ARG_DEF_FROM_EDGE (phi
, latch
);
614 /* Ignore the values that are not changed inside the subloop. */
615 if (TREE_CODE (lop
) != SSA_NAME
616 || SSA_NAME_DEF_STMT (lop
) == phi
)
618 bb
= gimple_bb (SSA_NAME_DEF_STMT (lop
));
619 if (!bb
|| !flow_bb_inside_loop_p (loop
, bb
))
622 FOR_EACH_VEC_ELT (latches
, i
, e
)
624 && PHI_ARG_DEF_FROM_EDGE (phi
, e
) == lop
)
630 "Found latch edge %d -> %d using iv structure.\n",
631 latch
->src
->index
, latch
->dest
->index
);
635 /* If we can determine that one of the several latch edges of LOOP behaves
636 as a latch edge of a separate subloop, returns this edge. Otherwise
640 find_subloop_latch_edge (struct loop
*loop
)
642 vec
<edge
> latches
= get_loop_latch_edges (loop
);
645 if (latches
.length () > 1)
647 latch
= find_subloop_latch_edge_by_profile (latches
);
650 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
651 should use cfghook for this, but it is hard to imagine it would
652 be useful elsewhere. */
653 && current_ir_type () == IR_GIMPLE
)
654 latch
= find_subloop_latch_edge_by_ivs (loop
, latches
);
661 /* Callback for make_forwarder_block. Returns true if the edge E is marked
662 in the set MFB_REIS_SET. */
664 static hash_set
<edge
> *mfb_reis_set
;
666 mfb_redirect_edges_in_set (edge e
)
668 return mfb_reis_set
->contains (e
);
671 /* Creates a subloop of LOOP with latch edge LATCH. */
674 form_subloop (struct loop
*loop
, edge latch
)
678 struct loop
*new_loop
;
680 mfb_reis_set
= new hash_set
<edge
>;
681 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
684 mfb_reis_set
->add (e
);
686 new_entry
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
690 loop
->header
= new_entry
->src
;
692 /* Find the blocks and subloops that belong to the new loop, and add it to
693 the appropriate place in the loop tree. */
694 new_loop
= alloc_loop ();
695 new_loop
->header
= new_entry
->dest
;
696 new_loop
->latch
= latch
->src
;
697 add_loop (new_loop
, loop
);
700 /* Make all the latch edges of LOOP to go to a single forwarder block --
701 a new latch of LOOP. */
704 merge_latch_edges (struct loop
*loop
)
706 vec
<edge
> latches
= get_loop_latch_edges (loop
);
710 gcc_assert (latches
.length () > 0);
712 if (latches
.length () == 1)
713 loop
->latch
= latches
[0]->src
;
717 fprintf (dump_file
, "Merged latch edges of loop %d\n", loop
->num
);
719 mfb_reis_set
= new hash_set
<edge
>;
720 FOR_EACH_VEC_ELT (latches
, i
, e
)
721 mfb_reis_set
->add (e
);
722 latch
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
726 loop
->header
= latch
->dest
;
727 loop
->latch
= latch
->src
;
733 /* LOOP may have several latch edges. Transform it into (possibly several)
734 loops with single latch edge. */
737 disambiguate_multiple_latches (struct loop
*loop
)
741 /* We eliminate the multiple latches by splitting the header to the forwarder
742 block F and the rest R, and redirecting the edges. There are two cases:
744 1) If there is a latch edge E that corresponds to a subloop (we guess
745 that based on profile -- if it is taken much more often than the
746 remaining edges; and on trees, using the information about induction
747 variables of the loops), we redirect E to R, all the remaining edges to
748 F, then rescan the loops and try again for the outer loop.
749 2) If there is no such edge, we redirect all latch edges to F, and the
750 entry edges to R, thus making F the single latch of the loop. */
753 fprintf (dump_file
, "Disambiguating loop %d with multiple latches\n",
756 /* During latch merging, we may need to redirect the entry edges to a new
757 block. This would cause problems if the entry edge was the one from the
758 entry block. To avoid having to handle this case specially, split
760 e
= find_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), loop
->header
);
766 e
= find_subloop_latch_edge (loop
);
770 form_subloop (loop
, e
);
773 merge_latch_edges (loop
);
776 /* Split loops with multiple latch edges. */
779 disambiguate_loops_with_multiple_latches (void)
783 FOR_EACH_LOOP (loop
, 0)
786 disambiguate_multiple_latches (loop
);
790 /* Return nonzero if basic block BB belongs to LOOP. */
792 flow_bb_inside_loop_p (const struct loop
*loop
, const_basic_block bb
)
794 struct loop
*source_loop
;
796 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
797 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
800 source_loop
= bb
->loop_father
;
801 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
804 /* Enumeration predicate for get_loop_body_with_size. */
806 glb_enum_p (const_basic_block bb
, const void *glb_loop
)
808 const struct loop
*const loop
= (const struct loop
*) glb_loop
;
809 return (bb
!= loop
->header
810 && dominated_by_p (CDI_DOMINATORS
, bb
, loop
->header
));
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. LOOP cannot be the fake
816 loop tree root, and its size must be at most MAX_SIZE. The blocks
817 in the LOOP body are stored to BODY, and the size of the LOOP is
821 get_loop_body_with_size (const struct loop
*loop
, basic_block
*body
,
824 return dfs_enumerate_from (loop
->header
, 1, glb_enum_p
,
825 body
, max_size
, loop
);
828 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
829 order against direction of edges from latch. Specially, if
830 header != latch, latch is the 1-st block. */
833 get_loop_body (const struct loop
*loop
)
835 basic_block
*body
, bb
;
838 gcc_assert (loop
->num_nodes
);
840 body
= XNEWVEC (basic_block
, loop
->num_nodes
);
842 if (loop
->latch
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
844 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
845 special-case the fake loop that contains the whole function. */
846 gcc_assert (loop
->num_nodes
== (unsigned) n_basic_blocks_for_fn (cfun
));
847 body
[tv
++] = loop
->header
;
848 body
[tv
++] = EXIT_BLOCK_PTR_FOR_FN (cfun
);
849 FOR_EACH_BB_FN (bb
, cfun
)
853 tv
= get_loop_body_with_size (loop
, body
, loop
->num_nodes
);
855 gcc_assert (tv
== loop
->num_nodes
);
859 /* Fills dominance descendants inside LOOP of the basic block BB into
860 array TOVISIT from index *TV. */
863 fill_sons_in_loop (const struct loop
*loop
, basic_block bb
,
864 basic_block
*tovisit
, int *tv
)
866 basic_block son
, postpone
= NULL
;
868 tovisit
[(*tv
)++] = bb
;
869 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
871 son
= next_dom_son (CDI_DOMINATORS
, son
))
873 if (!flow_bb_inside_loop_p (loop
, son
))
876 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, son
))
881 fill_sons_in_loop (loop
, son
, tovisit
, tv
);
885 fill_sons_in_loop (loop
, postpone
, tovisit
, tv
);
888 /* Gets body of a LOOP (that must be different from the outermost loop)
889 sorted by dominance relation. Additionally, if a basic block s dominates
890 the latch, then only blocks dominated by s are be after it. */
893 get_loop_body_in_dom_order (const struct loop
*loop
)
895 basic_block
*tovisit
;
898 gcc_assert (loop
->num_nodes
);
900 tovisit
= XNEWVEC (basic_block
, loop
->num_nodes
);
902 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
905 fill_sons_in_loop (loop
, loop
->header
, tovisit
, &tv
);
907 gcc_assert (tv
== (int) loop
->num_nodes
);
912 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
915 get_loop_body_in_custom_order (const struct loop
*loop
,
916 int (*bb_comparator
) (const void *, const void *))
918 basic_block
*bbs
= get_loop_body (loop
);
920 qsort (bbs
, loop
->num_nodes
, sizeof (basic_block
), bb_comparator
);
925 /* Get body of a LOOP in breadth first sort order. */
928 get_loop_body_in_bfs_order (const struct loop
*loop
)
936 gcc_assert (loop
->num_nodes
);
937 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
939 blocks
= XNEWVEC (basic_block
, loop
->num_nodes
);
940 visited
= BITMAP_ALLOC (NULL
);
943 while (i
< loop
->num_nodes
)
948 if (bitmap_set_bit (visited
, bb
->index
))
949 /* This basic block is now visited */
952 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
954 if (flow_bb_inside_loop_p (loop
, e
->dest
))
956 if (bitmap_set_bit (visited
, e
->dest
->index
))
957 blocks
[i
++] = e
->dest
;
961 gcc_assert (i
>= vc
);
966 BITMAP_FREE (visited
);
970 /* Hash function for struct loop_exit. */
973 loop_exit_hasher::hash (loop_exit
*exit
)
975 return htab_hash_pointer (exit
->e
);
978 /* Equality function for struct loop_exit. Compares with edge. */
981 loop_exit_hasher::equal (loop_exit
*exit
, edge e
)
986 /* Frees the list of loop exit descriptions EX. */
989 loop_exit_hasher::remove (loop_exit
*exit
)
992 for (; exit
; exit
= next
)
996 exit
->next
->prev
= exit
->prev
;
997 exit
->prev
->next
= exit
->next
;
1003 /* Returns the list of records for E as an exit of a loop. */
1005 static struct loop_exit
*
1006 get_exit_descriptions (edge e
)
1008 return current_loops
->exits
->find_with_hash (e
, htab_hash_pointer (e
));
1011 /* Updates the lists of loop exits in that E appears.
1012 If REMOVED is true, E is being removed, and we
1013 just remove it from the lists of exits.
1014 If NEW_EDGE is true and E is not a loop exit, we
1015 do not try to remove it from loop exit lists. */
1018 rescan_loop_exit (edge e
, bool new_edge
, bool removed
)
1020 struct loop_exit
*exits
= NULL
, *exit
;
1021 struct loop
*aloop
, *cloop
;
1023 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1027 && e
->src
->loop_father
!= NULL
1028 && e
->dest
->loop_father
!= NULL
1029 && !flow_bb_inside_loop_p (e
->src
->loop_father
, e
->dest
))
1031 cloop
= find_common_loop (e
->src
->loop_father
, e
->dest
->loop_father
);
1032 for (aloop
= e
->src
->loop_father
;
1034 aloop
= loop_outer (aloop
))
1036 exit
= ggc_alloc
<loop_exit
> ();
1039 exit
->next
= aloop
->exits
->next
;
1040 exit
->prev
= aloop
->exits
;
1041 exit
->next
->prev
= exit
;
1042 exit
->prev
->next
= exit
;
1044 exit
->next_e
= exits
;
1049 if (!exits
&& new_edge
)
1053 = current_loops
->exits
->find_slot_with_hash (e
, htab_hash_pointer (e
),
1054 exits
? INSERT
: NO_INSERT
);
1061 loop_exit_hasher::remove (*slot
);
1065 current_loops
->exits
->clear_slot (slot
);
1068 /* For each loop, record list of exit edges, and start maintaining these
1072 record_loop_exits (void)
1081 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1083 loops_state_set (LOOPS_HAVE_RECORDED_EXITS
);
1085 gcc_assert (current_loops
->exits
== NULL
);
1086 current_loops
->exits
1087 = hash_table
<loop_exit_hasher
>::create_ggc (2 * number_of_loops (cfun
));
1089 FOR_EACH_BB_FN (bb
, cfun
)
1091 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1093 rescan_loop_exit (e
, true, false);
1098 /* Dumps information about the exit in *SLOT to FILE.
1099 Callback for htab_traverse. */
1102 dump_recorded_exit (loop_exit
**slot
, FILE *file
)
1104 struct loop_exit
*exit
= *slot
;
1108 for (; exit
!= NULL
; exit
= exit
->next_e
)
1111 fprintf (file
, "Edge %d->%d exits %u loops\n",
1112 e
->src
->index
, e
->dest
->index
, n
);
1117 /* Dumps the recorded exits of loops to FILE. */
1119 extern void dump_recorded_exits (FILE *);
1121 dump_recorded_exits (FILE *file
)
1123 if (!current_loops
->exits
)
1125 current_loops
->exits
->traverse
<FILE *, dump_recorded_exit
> (file
);
1128 /* Releases lists of loop exits. */
1131 release_recorded_exits (void)
1133 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
));
1134 current_loops
->exits
->empty ();
1135 current_loops
->exits
= NULL
;
1136 loops_state_clear (LOOPS_HAVE_RECORDED_EXITS
);
1139 /* Returns the list of the exit edges of a LOOP. */
1142 get_loop_exit_edges (const struct loop
*loop
)
1144 vec
<edge
> edges
= vNULL
;
1149 struct loop_exit
*exit
;
1151 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1153 /* If we maintain the lists of exits, use them. Otherwise we must
1154 scan the body of the loop. */
1155 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1157 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1158 edges
.safe_push (exit
->e
);
1162 body
= get_loop_body (loop
);
1163 for (i
= 0; i
< loop
->num_nodes
; i
++)
1164 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
1166 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1167 edges
.safe_push (e
);
1175 /* Counts the number of conditional branches inside LOOP. */
1178 num_loop_branches (const struct loop
*loop
)
1183 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1185 body
= get_loop_body (loop
);
1187 for (i
= 0; i
< loop
->num_nodes
; i
++)
1188 if (EDGE_COUNT (body
[i
]->succs
) >= 2)
1195 /* Adds basic block BB to LOOP. */
1197 add_bb_to_loop (basic_block bb
, struct loop
*loop
)
1204 gcc_assert (bb
->loop_father
== NULL
);
1205 bb
->loop_father
= loop
;
1207 FOR_EACH_VEC_SAFE_ELT (loop
->superloops
, i
, ploop
)
1210 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1212 rescan_loop_exit (e
, true, false);
1214 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1216 rescan_loop_exit (e
, true, false);
1220 /* Remove basic block BB from loops. */
1222 remove_bb_from_loops (basic_block bb
)
1225 struct loop
*loop
= bb
->loop_father
;
1230 gcc_assert (loop
!= NULL
);
1232 FOR_EACH_VEC_SAFE_ELT (loop
->superloops
, i
, ploop
)
1234 bb
->loop_father
= NULL
;
1236 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1238 rescan_loop_exit (e
, false, true);
1240 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1242 rescan_loop_exit (e
, false, true);
1246 /* Finds nearest common ancestor in loop tree for given loops. */
1248 find_common_loop (struct loop
*loop_s
, struct loop
*loop_d
)
1250 unsigned sdepth
, ddepth
;
1252 if (!loop_s
) return loop_d
;
1253 if (!loop_d
) return loop_s
;
1255 sdepth
= loop_depth (loop_s
);
1256 ddepth
= loop_depth (loop_d
);
1258 if (sdepth
< ddepth
)
1259 loop_d
= (*loop_d
->superloops
)[sdepth
];
1260 else if (sdepth
> ddepth
)
1261 loop_s
= (*loop_s
->superloops
)[ddepth
];
1263 while (loop_s
!= loop_d
)
1265 loop_s
= loop_outer (loop_s
);
1266 loop_d
= loop_outer (loop_d
);
1271 /* Removes LOOP from structures and frees its data. */
1274 delete_loop (struct loop
*loop
)
1276 /* Remove the loop from structure. */
1277 flow_loop_tree_node_remove (loop
);
1279 /* Remove loop from loops array. */
1280 (*current_loops
->larray
)[loop
->num
] = NULL
;
1282 /* Free loop data. */
1283 flow_loop_free (loop
);
1286 /* Cancels the LOOP; it must be innermost one. */
1289 cancel_loop (struct loop
*loop
)
1293 struct loop
*outer
= loop_outer (loop
);
1295 gcc_assert (!loop
->inner
);
1297 /* Move blocks up one level (they should be removed as soon as possible). */
1298 bbs
= get_loop_body (loop
);
1299 for (i
= 0; i
< loop
->num_nodes
; i
++)
1300 bbs
[i
]->loop_father
= outer
;
1306 /* Cancels LOOP and all its subloops. */
1308 cancel_loop_tree (struct loop
*loop
)
1311 cancel_loop_tree (loop
->inner
);
1315 /* Checks that information about loops is correct
1316 -- sizes of loops are all right
1317 -- results of get_loop_body really belong to the loop
1318 -- loop header have just single entry edge and single latch edge
1319 -- loop latches have only single successor that is header of their loop
1320 -- irreducible loops are correctly marked
1321 -- the cached loop depth and loop father of each bb is correct
1324 verify_loop_structure (void)
1326 unsigned *sizes
, i
, j
;
1328 basic_block bb
, *bbs
;
1332 unsigned num
= number_of_loops (cfun
);
1333 struct loop_exit
*exit
, *mexit
;
1334 bool dom_available
= dom_info_available_p (CDI_DOMINATORS
);
1337 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
1339 error ("loop verification on loop tree that needs fixup");
1343 /* We need up-to-date dominators, compute or verify them. */
1345 calculate_dominance_info (CDI_DOMINATORS
);
1347 verify_dominators (CDI_DOMINATORS
);
1349 /* Check the loop tree root. */
1350 if (current_loops
->tree_root
->header
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1351 || current_loops
->tree_root
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1352 || (current_loops
->tree_root
->num_nodes
1353 != (unsigned) n_basic_blocks_for_fn (cfun
)))
1355 error ("corrupt loop tree root");
1359 /* Check the headers. */
1360 FOR_EACH_BB_FN (bb
, cfun
)
1361 if (bb_loop_header_p (bb
))
1363 if (bb
->loop_father
->header
== NULL
)
1365 error ("loop with header %d marked for removal", bb
->index
);
1368 else if (bb
->loop_father
->header
!= bb
)
1370 error ("loop with header %d not in loop tree", bb
->index
);
1374 else if (bb
->loop_father
->header
== bb
)
1376 error ("non-loop with header %d not marked for removal", bb
->index
);
1380 /* Check the recorded loop father and sizes of loops. */
1381 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1382 bitmap_clear (visited
);
1383 bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
1384 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1388 if (loop
->header
== NULL
)
1390 error ("removed loop %d in loop tree", loop
->num
);
1395 n
= get_loop_body_with_size (loop
, bbs
, n_basic_blocks_for_fn (cfun
));
1396 if (loop
->num_nodes
!= n
)
1398 error ("size of loop %d should be %d, not %d",
1399 loop
->num
, n
, loop
->num_nodes
);
1403 for (j
= 0; j
< n
; j
++)
1407 if (!flow_bb_inside_loop_p (loop
, bb
))
1409 error ("bb %d does not belong to loop %d",
1410 bb
->index
, loop
->num
);
1414 /* Ignore this block if it is in an inner loop. */
1415 if (bitmap_bit_p (visited
, bb
->index
))
1417 bitmap_set_bit (visited
, bb
->index
);
1419 if (bb
->loop_father
!= loop
)
1421 error ("bb %d has father loop %d, should be loop %d",
1422 bb
->index
, bb
->loop_father
->num
, loop
->num
);
1428 sbitmap_free (visited
);
1430 /* Check headers and latches. */
1431 FOR_EACH_LOOP (loop
, 0)
1434 if (loop
->header
== NULL
)
1436 if (!bb_loop_header_p (loop
->header
))
1438 error ("loop %d%'s header is not a loop header", i
);
1441 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
)
1442 && EDGE_COUNT (loop
->header
->preds
) != 2)
1444 error ("loop %d%'s header does not have exactly 2 entries", i
);
1449 if (!find_edge (loop
->latch
, loop
->header
))
1451 error ("loop %d%'s latch does not have an edge to its header", i
);
1454 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, loop
->header
))
1456 error ("loop %d%'s latch is not dominated by its header", i
);
1460 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
1462 if (!single_succ_p (loop
->latch
))
1464 error ("loop %d%'s latch does not have exactly 1 successor", i
);
1467 if (single_succ (loop
->latch
) != loop
->header
)
1469 error ("loop %d%'s latch does not have header as successor", i
);
1472 if (loop
->latch
->loop_father
!= loop
)
1474 error ("loop %d%'s latch does not belong directly to it", i
);
1478 if (loop
->header
->loop_father
!= loop
)
1480 error ("loop %d%'s header does not belong directly to it", i
);
1483 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1484 && (loop_latch_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
))
1486 error ("loop %d%'s latch is marked as part of irreducible region", i
);
1491 /* Check irreducible loops. */
1492 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1494 /* Record old info. */
1495 irreds
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1496 FOR_EACH_BB_FN (bb
, cfun
)
1499 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1500 bitmap_set_bit (irreds
, bb
->index
);
1502 bitmap_clear_bit (irreds
, bb
->index
);
1503 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1504 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1505 e
->flags
|= EDGE_ALL_FLAGS
+ 1;
1509 mark_irreducible_loops ();
1512 FOR_EACH_BB_FN (bb
, cfun
)
1516 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1517 && !bitmap_bit_p (irreds
, bb
->index
))
1519 error ("basic block %d should be marked irreducible", bb
->index
);
1522 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1523 && bitmap_bit_p (irreds
, bb
->index
))
1525 error ("basic block %d should not be marked irreducible", bb
->index
);
1528 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1530 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1531 && !(e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1533 error ("edge from %d to %d should be marked irreducible",
1534 e
->src
->index
, e
->dest
->index
);
1537 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1538 && (e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1540 error ("edge from %d to %d should not be marked irreducible",
1541 e
->src
->index
, e
->dest
->index
);
1544 e
->flags
&= ~(EDGE_ALL_FLAGS
+ 1);
1550 /* Check the recorded loop exits. */
1551 FOR_EACH_LOOP (loop
, 0)
1553 if (!loop
->exits
|| loop
->exits
->e
!= NULL
)
1555 error ("corrupted head of the exits list of loop %d",
1561 /* Check that the list forms a cycle, and all elements except
1562 for the head are nonnull. */
1563 for (mexit
= loop
->exits
, exit
= mexit
->next
, i
= 0;
1564 exit
->e
&& exit
!= mexit
;
1568 mexit
= mexit
->next
;
1571 if (exit
!= loop
->exits
)
1573 error ("corrupted exits list of loop %d", loop
->num
);
1578 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1580 if (loop
->exits
->next
!= loop
->exits
)
1582 error ("nonempty exits list of loop %d, but exits are not recorded",
1589 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1591 unsigned n_exits
= 0, eloops
;
1593 sizes
= XCNEWVEC (unsigned, num
);
1594 memset (sizes
, 0, sizeof (unsigned) * num
);
1595 FOR_EACH_BB_FN (bb
, cfun
)
1598 if (bb
->loop_father
== current_loops
->tree_root
)
1600 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1602 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
1606 exit
= get_exit_descriptions (e
);
1609 error ("exit %d->%d not recorded",
1610 e
->src
->index
, e
->dest
->index
);
1614 for (; exit
; exit
= exit
->next_e
)
1617 for (loop
= bb
->loop_father
;
1618 loop
!= e
->dest
->loop_father
1619 /* When a loop exit is also an entry edge which
1620 can happen when avoiding CFG manipulations
1621 then the last loop exited is the outer loop
1622 of the loop entered. */
1623 && loop
!= loop_outer (e
->dest
->loop_father
);
1624 loop
= loop_outer (loop
))
1632 error ("wrong list of exited loops for edge %d->%d",
1633 e
->src
->index
, e
->dest
->index
);
1639 if (n_exits
!= current_loops
->exits
->elements ())
1641 error ("too many loop exits recorded");
1645 FOR_EACH_LOOP (loop
, 0)
1648 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1650 if (eloops
!= sizes
[loop
->num
])
1652 error ("%d exits recorded for loop %d (having %d exits)",
1653 eloops
, loop
->num
, sizes
[loop
->num
]);
1664 free_dominance_info (CDI_DOMINATORS
);
1667 /* Returns latch edge of LOOP. */
1669 loop_latch_edge (const struct loop
*loop
)
1671 return find_edge (loop
->latch
, loop
->header
);
1674 /* Returns preheader edge of LOOP. */
1676 loop_preheader_edge (const struct loop
*loop
)
1681 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
));
1683 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1684 if (e
->src
!= loop
->latch
)
1690 /* Returns true if E is an exit of LOOP. */
1693 loop_exit_edge_p (const struct loop
*loop
, const_edge e
)
1695 return (flow_bb_inside_loop_p (loop
, e
->src
)
1696 && !flow_bb_inside_loop_p (loop
, e
->dest
));
1699 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1700 or more than one exit. If loops do not have the exits recorded, NULL
1701 is returned always. */
1704 single_exit (const struct loop
*loop
)
1706 struct loop_exit
*exit
= loop
->exits
->next
;
1708 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1711 if (exit
->e
&& exit
->next
== loop
->exits
)
1717 /* Returns true when BB has an incoming edge exiting LOOP. */
1720 loop_exits_to_bb_p (struct loop
*loop
, basic_block bb
)
1725 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1726 if (loop_exit_edge_p (loop
, e
))
1732 /* Returns true when BB has an outgoing edge exiting LOOP. */
1735 loop_exits_from_bb_p (struct loop
*loop
, basic_block bb
)
1740 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1741 if (loop_exit_edge_p (loop
, e
))
1747 /* Return location corresponding to the loop control condition if possible. */
1750 get_loop_location (struct loop
*loop
)
1752 rtx_insn
*insn
= NULL
;
1753 struct niter_desc
*desc
= NULL
;
1756 /* For a for or while loop, we would like to return the location
1757 of the for or while statement, if possible. To do this, look
1758 for the branch guarding the loop back-edge. */
1760 /* If this is a simple loop with an in_edge, then the loop control
1761 branch is typically at the end of its source. */
1762 desc
= get_simple_loop_desc (loop
);
1765 FOR_BB_INSNS_REVERSE (desc
->in_edge
->src
, insn
)
1767 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1768 return INSN_LOCATION (insn
);
1771 /* If loop has a single exit, then the loop control branch
1772 must be at the end of its source. */
1773 if ((exit
= single_exit (loop
)))
1775 FOR_BB_INSNS_REVERSE (exit
->src
, insn
)
1777 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1778 return INSN_LOCATION (insn
);
1781 /* Next check the latch, to see if it is non-empty. */
1782 FOR_BB_INSNS_REVERSE (loop
->latch
, insn
)
1784 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1785 return INSN_LOCATION (insn
);
1787 /* Finally, if none of the above identifies the loop control branch,
1788 return the first location in the loop header. */
1789 FOR_BB_INSNS (loop
->header
, insn
)
1791 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1792 return INSN_LOCATION (insn
);
1794 /* If all else fails, simply return the current function location. */
1795 return DECL_SOURCE_LOCATION (current_function_decl
);
1798 /* Records that every statement in LOOP is executed I_BOUND times.
1799 REALISTIC is true if I_BOUND is expected to be close to the real number
1800 of iterations. UPPER is true if we are sure the loop iterates at most
1804 record_niter_bound (struct loop
*loop
, const widest_int
&i_bound
,
1805 bool realistic
, bool upper
)
1807 /* Update the bounds only when there is no previous estimation, or when the
1808 current estimation is smaller. */
1810 && (!loop
->any_upper_bound
1811 || wi::ltu_p (i_bound
, loop
->nb_iterations_upper_bound
)))
1813 loop
->any_upper_bound
= true;
1814 loop
->nb_iterations_upper_bound
= i_bound
;
1817 && (!loop
->any_estimate
1818 || wi::ltu_p (i_bound
, loop
->nb_iterations_estimate
)))
1820 loop
->any_estimate
= true;
1821 loop
->nb_iterations_estimate
= i_bound
;
1824 /* If an upper bound is smaller than the realistic estimate of the
1825 number of iterations, use the upper bound instead. */
1826 if (loop
->any_upper_bound
1827 && loop
->any_estimate
1828 && wi::ltu_p (loop
->nb_iterations_upper_bound
,
1829 loop
->nb_iterations_estimate
))
1830 loop
->nb_iterations_estimate
= loop
->nb_iterations_upper_bound
;
1833 /* Similar to get_estimated_loop_iterations, but returns the estimate only
1834 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1835 on the number of iterations of LOOP could not be derived, returns -1. */
1838 get_estimated_loop_iterations_int (struct loop
*loop
)
1841 HOST_WIDE_INT hwi_nit
;
1843 if (!get_estimated_loop_iterations (loop
, &nit
))
1846 if (!wi::fits_shwi_p (nit
))
1848 hwi_nit
= nit
.to_shwi ();
1850 return hwi_nit
< 0 ? -1 : hwi_nit
;
1853 /* Returns an upper bound on the number of executions of statements
1854 in the LOOP. For statements before the loop exit, this exceeds
1855 the number of execution of the latch by one. */
1858 max_stmt_executions_int (struct loop
*loop
)
1860 HOST_WIDE_INT nit
= get_max_loop_iterations_int (loop
);
1866 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
1868 /* If the computation overflows, return -1. */
1869 return snit
< 0 ? -1 : snit
;
1872 /* Sets NIT to the estimated number of executions of the latch of the
1873 LOOP. If we have no reliable estimate, the function returns false, otherwise
1877 get_estimated_loop_iterations (struct loop
*loop
, widest_int
*nit
)
1879 /* Even if the bound is not recorded, possibly we can derrive one from
1881 if (!loop
->any_estimate
)
1883 if (loop
->header
->count
)
1885 *nit
= gcov_type_to_wide_int
1886 (expected_loop_iterations_unbounded (loop
) + 1);
1892 *nit
= loop
->nb_iterations_estimate
;
1896 /* Sets NIT to an upper bound for the maximum number of executions of the
1897 latch of the LOOP. If we have no reliable estimate, the function returns
1898 false, otherwise returns true. */
1901 get_max_loop_iterations (struct loop
*loop
, widest_int
*nit
)
1903 if (!loop
->any_upper_bound
)
1906 *nit
= loop
->nb_iterations_upper_bound
;
1910 /* Similar to get_max_loop_iterations, but returns the estimate only
1911 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1912 on the number of iterations of LOOP could not be derived, returns -1. */
1915 get_max_loop_iterations_int (struct loop
*loop
)
1918 HOST_WIDE_INT hwi_nit
;
1920 if (!get_max_loop_iterations (loop
, &nit
))
1923 if (!wi::fits_shwi_p (nit
))
1925 hwi_nit
= nit
.to_shwi ();
1927 return hwi_nit
< 0 ? -1 : hwi_nit
;
1930 /* Returns the loop depth of the loop BB belongs to. */
1933 bb_loop_depth (const_basic_block bb
)
1935 return bb
->loop_father
? loop_depth (bb
->loop_father
) : 0;
1938 /* Marks LOOP for removal and sets LOOPS_NEED_FIXUP. */
1941 mark_loop_for_removal (loop_p loop
)
1943 if (loop
->header
== NULL
)
1945 loop
->former_header
= loop
->header
;
1946 loop
->header
= NULL
;
1948 loops_state_set (LOOPS_NEED_FIXUP
);