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 /* Return the latch block for this header block, if it has just a single one.
392 Otherwise, return NULL. */
395 find_single_latch (struct loop
* loop
)
397 basic_block header
= loop
->header
;
400 basic_block latch
= NULL
;
402 FOR_EACH_EDGE (e
, ei
, header
->preds
)
404 basic_block cand
= e
->src
;
405 if (!flow_bb_inside_loop_p (loop
, cand
))
409 /* More than one latch edge. */
418 /* Find all the natural loops in the function and save in LOOPS structure and
419 recalculate loop_father information in basic block structures.
420 If LOOPS is non-NULL then the loop structures for already recorded loops
421 will be re-used and their number will not change. We assume that no
422 stale loops exist in LOOPS.
423 When LOOPS is NULL it is allocated and re-built from scratch.
424 Return the built LOOPS structure. */
427 flow_loops_find (struct loops
*loops
)
429 bool from_scratch
= (loops
== NULL
);
434 /* Ensure that the dominators are computed. */
435 calculate_dominance_info (CDI_DOMINATORS
);
439 loops
= ggc_cleared_alloc
<struct loops
> ();
440 init_loops_structure (cfun
, loops
, 1);
443 /* Ensure that loop exits were released. */
444 gcc_assert (loops
->exits
== NULL
);
446 /* Taking care of this degenerate case makes the rest of
447 this code simpler. */
448 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
451 /* The root loop node contains all basic-blocks. */
452 loops
->tree_root
->num_nodes
= n_basic_blocks_for_fn (cfun
);
454 /* Compute depth first search order of the CFG so that outer
455 natural loops will be found before inner natural loops. */
456 rc_order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
457 pre_and_rev_post_order_compute (NULL
, rc_order
, false);
459 /* Gather all loop headers in reverse completion order and allocate
460 loop structures for loops that are not already present. */
461 auto_vec
<loop_p
> larray (loops
->larray
->length ());
462 for (b
= 0; b
< n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
; b
++)
464 basic_block header
= BASIC_BLOCK_FOR_FN (cfun
, rc_order
[b
]);
465 if (bb_loop_header_p (header
))
469 /* The current active loop tree has valid loop-fathers for
472 && header
->loop_father
->header
== header
)
474 loop
= header
->loop_father
;
475 /* If we found an existing loop remove it from the
476 loop tree. It is going to be inserted again
478 flow_loop_tree_node_remove (loop
);
482 /* Otherwise allocate a new loop structure for the loop. */
483 loop
= alloc_loop ();
484 /* ??? We could re-use unused loop slots here. */
485 loop
->num
= loops
->larray
->length ();
486 vec_safe_push (loops
->larray
, loop
);
487 loop
->header
= header
;
490 && dump_file
&& (dump_flags
& TDF_DETAILS
))
491 fprintf (dump_file
, "flow_loops_find: discovered new "
492 "loop %d with header %d\n",
493 loop
->num
, header
->index
);
495 /* Reset latch, we recompute it below. */
497 larray
.safe_push (loop
);
500 /* Make blocks part of the loop root node at start. */
501 header
->loop_father
= loops
->tree_root
;
506 /* Now iterate over the loops found, insert them into the loop tree
507 and assign basic-block ownership. */
508 for (i
= 0; i
< larray
.length (); ++i
)
510 struct loop
*loop
= larray
[i
];
511 basic_block header
= loop
->header
;
513 flow_loop_tree_node_add (header
->loop_father
, loop
);
514 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
515 loop
->latch
= find_single_latch (loop
);
521 /* Ratio of frequencies of edges so that one of more latch edges is
522 considered to belong to inner loop with same header. */
523 #define HEAVY_EDGE_RATIO 8
525 /* Minimum number of samples for that we apply
526 find_subloop_latch_edge_by_profile heuristics. */
527 #define HEAVY_EDGE_MIN_SAMPLES 10
529 /* If the profile info is available, finds an edge in LATCHES that much more
530 frequent than the remaining edges. Returns such an edge, or NULL if we do
533 We do not use guessed profile here, only the measured one. The guessed
534 profile is usually too flat and unreliable for this (and it is mostly based
535 on the loop structure of the program, so it does not make much sense to
536 derive the loop structure from it). */
539 find_subloop_latch_edge_by_profile (vec
<edge
> latches
)
543 gcov_type mcount
= 0, tcount
= 0;
545 FOR_EACH_VEC_ELT (latches
, i
, e
)
547 if (e
->count
> mcount
)
555 if (tcount
< HEAVY_EDGE_MIN_SAMPLES
556 || (tcount
- mcount
) * HEAVY_EDGE_RATIO
> tcount
)
561 "Found latch edge %d -> %d using profile information.\n",
562 me
->src
->index
, me
->dest
->index
);
566 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
567 on the structure of induction variables. Returns this edge, or NULL if we
570 We are quite conservative, and look just for an obvious simple innermost
571 loop (which is the case where we would lose the most performance by not
572 disambiguating the loop). More precisely, we look for the following
573 situation: The source of the chosen latch edge dominates sources of all
574 the other latch edges. Additionally, the header does not contain a phi node
575 such that the argument from the chosen edge is equal to the argument from
579 find_subloop_latch_edge_by_ivs (struct loop
*loop ATTRIBUTE_UNUSED
, vec
<edge
> latches
)
581 edge e
, latch
= latches
[0];
588 /* Find the candidate for the latch edge. */
589 for (i
= 1; latches
.iterate (i
, &e
); i
++)
590 if (dominated_by_p (CDI_DOMINATORS
, latch
->src
, e
->src
))
593 /* Verify that it dominates all the latch edges. */
594 FOR_EACH_VEC_ELT (latches
, i
, e
)
595 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, latch
->src
))
598 /* Check for a phi node that would deny that this is a latch edge of
600 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
603 lop
= PHI_ARG_DEF_FROM_EDGE (phi
, latch
);
605 /* Ignore the values that are not changed inside the subloop. */
606 if (TREE_CODE (lop
) != SSA_NAME
607 || SSA_NAME_DEF_STMT (lop
) == phi
)
609 bb
= gimple_bb (SSA_NAME_DEF_STMT (lop
));
610 if (!bb
|| !flow_bb_inside_loop_p (loop
, bb
))
613 FOR_EACH_VEC_ELT (latches
, i
, e
)
615 && PHI_ARG_DEF_FROM_EDGE (phi
, e
) == lop
)
621 "Found latch edge %d -> %d using iv structure.\n",
622 latch
->src
->index
, latch
->dest
->index
);
626 /* If we can determine that one of the several latch edges of LOOP behaves
627 as a latch edge of a separate subloop, returns this edge. Otherwise
631 find_subloop_latch_edge (struct loop
*loop
)
633 vec
<edge
> latches
= get_loop_latch_edges (loop
);
636 if (latches
.length () > 1)
638 latch
= find_subloop_latch_edge_by_profile (latches
);
641 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
642 should use cfghook for this, but it is hard to imagine it would
643 be useful elsewhere. */
644 && current_ir_type () == IR_GIMPLE
)
645 latch
= find_subloop_latch_edge_by_ivs (loop
, latches
);
652 /* Callback for make_forwarder_block. Returns true if the edge E is marked
653 in the set MFB_REIS_SET. */
655 static hash_set
<edge
> *mfb_reis_set
;
657 mfb_redirect_edges_in_set (edge e
)
659 return mfb_reis_set
->contains (e
);
662 /* Creates a subloop of LOOP with latch edge LATCH. */
665 form_subloop (struct loop
*loop
, edge latch
)
669 struct loop
*new_loop
;
671 mfb_reis_set
= new hash_set
<edge
>;
672 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
675 mfb_reis_set
->add (e
);
677 new_entry
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
681 loop
->header
= new_entry
->src
;
683 /* Find the blocks and subloops that belong to the new loop, and add it to
684 the appropriate place in the loop tree. */
685 new_loop
= alloc_loop ();
686 new_loop
->header
= new_entry
->dest
;
687 new_loop
->latch
= latch
->src
;
688 add_loop (new_loop
, loop
);
691 /* Make all the latch edges of LOOP to go to a single forwarder block --
692 a new latch of LOOP. */
695 merge_latch_edges (struct loop
*loop
)
697 vec
<edge
> latches
= get_loop_latch_edges (loop
);
701 gcc_assert (latches
.length () > 0);
703 if (latches
.length () == 1)
704 loop
->latch
= latches
[0]->src
;
708 fprintf (dump_file
, "Merged latch edges of loop %d\n", loop
->num
);
710 mfb_reis_set
= new hash_set
<edge
>;
711 FOR_EACH_VEC_ELT (latches
, i
, e
)
712 mfb_reis_set
->add (e
);
713 latch
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
717 loop
->header
= latch
->dest
;
718 loop
->latch
= latch
->src
;
724 /* LOOP may have several latch edges. Transform it into (possibly several)
725 loops with single latch edge. */
728 disambiguate_multiple_latches (struct loop
*loop
)
732 /* We eliminate the multiple latches by splitting the header to the forwarder
733 block F and the rest R, and redirecting the edges. There are two cases:
735 1) If there is a latch edge E that corresponds to a subloop (we guess
736 that based on profile -- if it is taken much more often than the
737 remaining edges; and on trees, using the information about induction
738 variables of the loops), we redirect E to R, all the remaining edges to
739 F, then rescan the loops and try again for the outer loop.
740 2) If there is no such edge, we redirect all latch edges to F, and the
741 entry edges to R, thus making F the single latch of the loop. */
744 fprintf (dump_file
, "Disambiguating loop %d with multiple latches\n",
747 /* During latch merging, we may need to redirect the entry edges to a new
748 block. This would cause problems if the entry edge was the one from the
749 entry block. To avoid having to handle this case specially, split
751 e
= find_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), loop
->header
);
757 e
= find_subloop_latch_edge (loop
);
761 form_subloop (loop
, e
);
764 merge_latch_edges (loop
);
767 /* Split loops with multiple latch edges. */
770 disambiguate_loops_with_multiple_latches (void)
774 FOR_EACH_LOOP (loop
, 0)
777 disambiguate_multiple_latches (loop
);
781 /* Return nonzero if basic block BB belongs to LOOP. */
783 flow_bb_inside_loop_p (const struct loop
*loop
, const_basic_block bb
)
785 struct loop
*source_loop
;
787 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
788 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
791 source_loop
= bb
->loop_father
;
792 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
795 /* Enumeration predicate for get_loop_body_with_size. */
797 glb_enum_p (const_basic_block bb
, const void *glb_loop
)
799 const struct loop
*const loop
= (const struct loop
*) glb_loop
;
800 return (bb
!= loop
->header
801 && dominated_by_p (CDI_DOMINATORS
, bb
, loop
->header
));
804 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
805 order against direction of edges from latch. Specially, if
806 header != latch, latch is the 1-st block. LOOP cannot be the fake
807 loop tree root, and its size must be at most MAX_SIZE. The blocks
808 in the LOOP body are stored to BODY, and the size of the LOOP is
812 get_loop_body_with_size (const struct loop
*loop
, basic_block
*body
,
815 return dfs_enumerate_from (loop
->header
, 1, glb_enum_p
,
816 body
, max_size
, loop
);
819 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
820 order against direction of edges from latch. Specially, if
821 header != latch, latch is the 1-st block. */
824 get_loop_body (const struct loop
*loop
)
826 basic_block
*body
, bb
;
829 gcc_assert (loop
->num_nodes
);
831 body
= XNEWVEC (basic_block
, loop
->num_nodes
);
833 if (loop
->latch
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
835 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
836 special-case the fake loop that contains the whole function. */
837 gcc_assert (loop
->num_nodes
== (unsigned) n_basic_blocks_for_fn (cfun
));
838 body
[tv
++] = loop
->header
;
839 body
[tv
++] = EXIT_BLOCK_PTR_FOR_FN (cfun
);
840 FOR_EACH_BB_FN (bb
, cfun
)
844 tv
= get_loop_body_with_size (loop
, body
, loop
->num_nodes
);
846 gcc_assert (tv
== loop
->num_nodes
);
850 /* Fills dominance descendants inside LOOP of the basic block BB into
851 array TOVISIT from index *TV. */
854 fill_sons_in_loop (const struct loop
*loop
, basic_block bb
,
855 basic_block
*tovisit
, int *tv
)
857 basic_block son
, postpone
= NULL
;
859 tovisit
[(*tv
)++] = bb
;
860 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
862 son
= next_dom_son (CDI_DOMINATORS
, son
))
864 if (!flow_bb_inside_loop_p (loop
, son
))
867 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, son
))
872 fill_sons_in_loop (loop
, son
, tovisit
, tv
);
876 fill_sons_in_loop (loop
, postpone
, tovisit
, tv
);
879 /* Gets body of a LOOP (that must be different from the outermost loop)
880 sorted by dominance relation. Additionally, if a basic block s dominates
881 the latch, then only blocks dominated by s are be after it. */
884 get_loop_body_in_dom_order (const struct loop
*loop
)
886 basic_block
*tovisit
;
889 gcc_assert (loop
->num_nodes
);
891 tovisit
= XNEWVEC (basic_block
, loop
->num_nodes
);
893 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
896 fill_sons_in_loop (loop
, loop
->header
, tovisit
, &tv
);
898 gcc_assert (tv
== (int) loop
->num_nodes
);
903 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
906 get_loop_body_in_custom_order (const struct loop
*loop
,
907 int (*bb_comparator
) (const void *, const void *))
909 basic_block
*bbs
= get_loop_body (loop
);
911 qsort (bbs
, loop
->num_nodes
, sizeof (basic_block
), bb_comparator
);
916 /* Get body of a LOOP in breadth first sort order. */
919 get_loop_body_in_bfs_order (const struct loop
*loop
)
927 gcc_assert (loop
->num_nodes
);
928 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
930 blocks
= XNEWVEC (basic_block
, loop
->num_nodes
);
931 visited
= BITMAP_ALLOC (NULL
);
932 blocks
[0] = loop
->header
;
933 bitmap_set_bit (visited
, loop
->header
->index
);
934 while (i
< loop
->num_nodes
)
941 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
943 if (flow_bb_inside_loop_p (loop
, e
->dest
))
945 /* This bb is now visited. */
946 if (bitmap_set_bit (visited
, e
->dest
->index
))
947 blocks
[i
++] = e
->dest
;
952 BITMAP_FREE (visited
);
956 /* Hash function for struct loop_exit. */
959 loop_exit_hasher::hash (loop_exit
*exit
)
961 return htab_hash_pointer (exit
->e
);
964 /* Equality function for struct loop_exit. Compares with edge. */
967 loop_exit_hasher::equal (loop_exit
*exit
, edge e
)
972 /* Frees the list of loop exit descriptions EX. */
975 loop_exit_hasher::remove (loop_exit
*exit
)
978 for (; exit
; exit
= next
)
982 exit
->next
->prev
= exit
->prev
;
983 exit
->prev
->next
= exit
->next
;
989 /* Returns the list of records for E as an exit of a loop. */
991 static struct loop_exit
*
992 get_exit_descriptions (edge e
)
994 return current_loops
->exits
->find_with_hash (e
, htab_hash_pointer (e
));
997 /* Updates the lists of loop exits in that E appears.
998 If REMOVED is true, E is being removed, and we
999 just remove it from the lists of exits.
1000 If NEW_EDGE is true and E is not a loop exit, we
1001 do not try to remove it from loop exit lists. */
1004 rescan_loop_exit (edge e
, bool new_edge
, bool removed
)
1006 struct loop_exit
*exits
= NULL
, *exit
;
1007 struct loop
*aloop
, *cloop
;
1009 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1013 && e
->src
->loop_father
!= NULL
1014 && e
->dest
->loop_father
!= NULL
1015 && !flow_bb_inside_loop_p (e
->src
->loop_father
, e
->dest
))
1017 cloop
= find_common_loop (e
->src
->loop_father
, e
->dest
->loop_father
);
1018 for (aloop
= e
->src
->loop_father
;
1020 aloop
= loop_outer (aloop
))
1022 exit
= ggc_alloc
<loop_exit
> ();
1025 exit
->next
= aloop
->exits
->next
;
1026 exit
->prev
= aloop
->exits
;
1027 exit
->next
->prev
= exit
;
1028 exit
->prev
->next
= exit
;
1030 exit
->next_e
= exits
;
1035 if (!exits
&& new_edge
)
1039 = current_loops
->exits
->find_slot_with_hash (e
, htab_hash_pointer (e
),
1040 exits
? INSERT
: NO_INSERT
);
1047 loop_exit_hasher::remove (*slot
);
1051 current_loops
->exits
->clear_slot (slot
);
1054 /* For each loop, record list of exit edges, and start maintaining these
1058 record_loop_exits (void)
1067 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1069 loops_state_set (LOOPS_HAVE_RECORDED_EXITS
);
1071 gcc_assert (current_loops
->exits
== NULL
);
1072 current_loops
->exits
1073 = hash_table
<loop_exit_hasher
>::create_ggc (2 * number_of_loops (cfun
));
1075 FOR_EACH_BB_FN (bb
, cfun
)
1077 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1079 rescan_loop_exit (e
, true, false);
1084 /* Dumps information about the exit in *SLOT to FILE.
1085 Callback for htab_traverse. */
1088 dump_recorded_exit (loop_exit
**slot
, FILE *file
)
1090 struct loop_exit
*exit
= *slot
;
1094 for (; exit
!= NULL
; exit
= exit
->next_e
)
1097 fprintf (file
, "Edge %d->%d exits %u loops\n",
1098 e
->src
->index
, e
->dest
->index
, n
);
1103 /* Dumps the recorded exits of loops to FILE. */
1105 extern void dump_recorded_exits (FILE *);
1107 dump_recorded_exits (FILE *file
)
1109 if (!current_loops
->exits
)
1111 current_loops
->exits
->traverse
<FILE *, dump_recorded_exit
> (file
);
1114 /* Releases lists of loop exits. */
1117 release_recorded_exits (function
*fn
)
1119 gcc_assert (loops_state_satisfies_p (fn
, LOOPS_HAVE_RECORDED_EXITS
));
1120 loops_for_fn (fn
)->exits
->empty ();
1121 loops_for_fn (fn
)->exits
= NULL
;
1122 loops_state_clear (fn
, LOOPS_HAVE_RECORDED_EXITS
);
1125 /* Returns the list of the exit edges of a LOOP. */
1128 get_loop_exit_edges (const struct loop
*loop
)
1130 vec
<edge
> edges
= vNULL
;
1135 struct loop_exit
*exit
;
1137 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1139 /* If we maintain the lists of exits, use them. Otherwise we must
1140 scan the body of the loop. */
1141 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1143 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1144 edges
.safe_push (exit
->e
);
1148 body
= get_loop_body (loop
);
1149 for (i
= 0; i
< loop
->num_nodes
; i
++)
1150 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
1152 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1153 edges
.safe_push (e
);
1161 /* Counts the number of conditional branches inside LOOP. */
1164 num_loop_branches (const struct loop
*loop
)
1169 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1171 body
= get_loop_body (loop
);
1173 for (i
= 0; i
< loop
->num_nodes
; i
++)
1174 if (EDGE_COUNT (body
[i
]->succs
) >= 2)
1181 /* Adds basic block BB to LOOP. */
1183 add_bb_to_loop (basic_block bb
, struct loop
*loop
)
1190 gcc_assert (bb
->loop_father
== NULL
);
1191 bb
->loop_father
= loop
;
1193 FOR_EACH_VEC_SAFE_ELT (loop
->superloops
, i
, ploop
)
1196 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1198 rescan_loop_exit (e
, true, false);
1200 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1202 rescan_loop_exit (e
, true, false);
1206 /* Remove basic block BB from loops. */
1208 remove_bb_from_loops (basic_block bb
)
1211 struct loop
*loop
= bb
->loop_father
;
1216 gcc_assert (loop
!= NULL
);
1218 FOR_EACH_VEC_SAFE_ELT (loop
->superloops
, i
, ploop
)
1220 bb
->loop_father
= NULL
;
1222 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1224 rescan_loop_exit (e
, false, true);
1226 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1228 rescan_loop_exit (e
, false, true);
1232 /* Finds nearest common ancestor in loop tree for given loops. */
1234 find_common_loop (struct loop
*loop_s
, struct loop
*loop_d
)
1236 unsigned sdepth
, ddepth
;
1238 if (!loop_s
) return loop_d
;
1239 if (!loop_d
) return loop_s
;
1241 sdepth
= loop_depth (loop_s
);
1242 ddepth
= loop_depth (loop_d
);
1244 if (sdepth
< ddepth
)
1245 loop_d
= (*loop_d
->superloops
)[sdepth
];
1246 else if (sdepth
> ddepth
)
1247 loop_s
= (*loop_s
->superloops
)[ddepth
];
1249 while (loop_s
!= loop_d
)
1251 loop_s
= loop_outer (loop_s
);
1252 loop_d
= loop_outer (loop_d
);
1257 /* Removes LOOP from structures and frees its data. */
1260 delete_loop (struct loop
*loop
)
1262 /* Remove the loop from structure. */
1263 flow_loop_tree_node_remove (loop
);
1265 /* Remove loop from loops array. */
1266 (*current_loops
->larray
)[loop
->num
] = NULL
;
1268 /* Free loop data. */
1269 flow_loop_free (loop
);
1272 /* Cancels the LOOP; it must be innermost one. */
1275 cancel_loop (struct loop
*loop
)
1279 struct loop
*outer
= loop_outer (loop
);
1281 gcc_assert (!loop
->inner
);
1283 /* Move blocks up one level (they should be removed as soon as possible). */
1284 bbs
= get_loop_body (loop
);
1285 for (i
= 0; i
< loop
->num_nodes
; i
++)
1286 bbs
[i
]->loop_father
= outer
;
1292 /* Cancels LOOP and all its subloops. */
1294 cancel_loop_tree (struct loop
*loop
)
1297 cancel_loop_tree (loop
->inner
);
1301 /* Checks that information about loops is correct
1302 -- sizes of loops are all right
1303 -- results of get_loop_body really belong to the loop
1304 -- loop header have just single entry edge and single latch edge
1305 -- loop latches have only single successor that is header of their loop
1306 -- irreducible loops are correctly marked
1307 -- the cached loop depth and loop father of each bb is correct
1310 verify_loop_structure (void)
1312 unsigned *sizes
, i
, j
;
1314 basic_block bb
, *bbs
;
1318 unsigned num
= number_of_loops (cfun
);
1319 struct loop_exit
*exit
, *mexit
;
1320 bool dom_available
= dom_info_available_p (CDI_DOMINATORS
);
1323 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
1325 error ("loop verification on loop tree that needs fixup");
1329 /* We need up-to-date dominators, compute or verify them. */
1331 calculate_dominance_info (CDI_DOMINATORS
);
1333 verify_dominators (CDI_DOMINATORS
);
1335 /* Check the loop tree root. */
1336 if (current_loops
->tree_root
->header
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1337 || current_loops
->tree_root
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1338 || (current_loops
->tree_root
->num_nodes
1339 != (unsigned) n_basic_blocks_for_fn (cfun
)))
1341 error ("corrupt loop tree root");
1345 /* Check the headers. */
1346 FOR_EACH_BB_FN (bb
, cfun
)
1347 if (bb_loop_header_p (bb
))
1349 if (bb
->loop_father
->header
== NULL
)
1351 error ("loop with header %d marked for removal", bb
->index
);
1354 else if (bb
->loop_father
->header
!= bb
)
1356 error ("loop with header %d not in loop tree", bb
->index
);
1360 else if (bb
->loop_father
->header
== bb
)
1362 error ("non-loop with header %d not marked for removal", bb
->index
);
1366 /* Check the recorded loop father and sizes of loops. */
1367 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1368 bitmap_clear (visited
);
1369 bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
1370 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1374 if (loop
->header
== NULL
)
1376 error ("removed loop %d in loop tree", loop
->num
);
1381 n
= get_loop_body_with_size (loop
, bbs
, n_basic_blocks_for_fn (cfun
));
1382 if (loop
->num_nodes
!= n
)
1384 error ("size of loop %d should be %d, not %d",
1385 loop
->num
, n
, loop
->num_nodes
);
1389 for (j
= 0; j
< n
; j
++)
1393 if (!flow_bb_inside_loop_p (loop
, bb
))
1395 error ("bb %d does not belong to loop %d",
1396 bb
->index
, loop
->num
);
1400 /* Ignore this block if it is in an inner loop. */
1401 if (bitmap_bit_p (visited
, bb
->index
))
1403 bitmap_set_bit (visited
, bb
->index
);
1405 if (bb
->loop_father
!= loop
)
1407 error ("bb %d has father loop %d, should be loop %d",
1408 bb
->index
, bb
->loop_father
->num
, loop
->num
);
1414 sbitmap_free (visited
);
1416 /* Check headers and latches. */
1417 FOR_EACH_LOOP (loop
, 0)
1420 if (loop
->header
== NULL
)
1422 if (!bb_loop_header_p (loop
->header
))
1424 error ("loop %d%'s header is not a loop header", i
);
1427 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
)
1428 && EDGE_COUNT (loop
->header
->preds
) != 2)
1430 error ("loop %d%'s header does not have exactly 2 entries", i
);
1435 if (!find_edge (loop
->latch
, loop
->header
))
1437 error ("loop %d%'s latch does not have an edge to its header", i
);
1440 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, loop
->header
))
1442 error ("loop %d%'s latch is not dominated by its header", i
);
1445 if (find_single_latch (loop
) == NULL
)
1447 error ("loop %d%'s latch is is not the only latch", i
);
1453 if (loops_state_satisfies_p (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
))
1455 if (find_single_latch (loop
) != NULL
)
1457 error ("loop %d%'s latch is missing", i
);
1463 error ("loop %d%'s latch is missing, and loops may not have"
1464 " multiple latches", i
);
1468 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
1470 if (!single_succ_p (loop
->latch
))
1472 error ("loop %d%'s latch does not have exactly 1 successor", i
);
1475 if (single_succ (loop
->latch
) != loop
->header
)
1477 error ("loop %d%'s latch does not have header as successor", i
);
1480 if (loop
->latch
->loop_father
!= loop
)
1482 error ("loop %d%'s latch does not belong directly to it", i
);
1486 if (loop
->header
->loop_father
!= loop
)
1488 error ("loop %d%'s header does not belong directly to it", i
);
1491 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1492 && (loop_latch_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
))
1494 error ("loop %d%'s latch is marked as part of irreducible region", i
);
1499 /* Check irreducible loops. */
1500 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1502 /* Record old info. */
1503 irreds
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1504 FOR_EACH_BB_FN (bb
, cfun
)
1507 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1508 bitmap_set_bit (irreds
, bb
->index
);
1510 bitmap_clear_bit (irreds
, bb
->index
);
1511 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1512 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1513 e
->flags
|= EDGE_ALL_FLAGS
+ 1;
1517 mark_irreducible_loops ();
1520 FOR_EACH_BB_FN (bb
, cfun
)
1524 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1525 && !bitmap_bit_p (irreds
, bb
->index
))
1527 error ("basic block %d should be marked irreducible", bb
->index
);
1530 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1531 && bitmap_bit_p (irreds
, bb
->index
))
1533 error ("basic block %d should not be marked irreducible", bb
->index
);
1536 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1538 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1539 && !(e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1541 error ("edge from %d to %d should be marked irreducible",
1542 e
->src
->index
, e
->dest
->index
);
1545 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1546 && (e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1548 error ("edge from %d to %d should not be marked irreducible",
1549 e
->src
->index
, e
->dest
->index
);
1552 e
->flags
&= ~(EDGE_ALL_FLAGS
+ 1);
1558 /* Check the recorded loop exits. */
1559 FOR_EACH_LOOP (loop
, 0)
1561 if (!loop
->exits
|| loop
->exits
->e
!= NULL
)
1563 error ("corrupted head of the exits list of loop %d",
1569 /* Check that the list forms a cycle, and all elements except
1570 for the head are nonnull. */
1571 for (mexit
= loop
->exits
, exit
= mexit
->next
, i
= 0;
1572 exit
->e
&& exit
!= mexit
;
1576 mexit
= mexit
->next
;
1579 if (exit
!= loop
->exits
)
1581 error ("corrupted exits list of loop %d", loop
->num
);
1586 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1588 if (loop
->exits
->next
!= loop
->exits
)
1590 error ("nonempty exits list of loop %d, but exits are not recorded",
1597 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1599 unsigned n_exits
= 0, eloops
;
1601 sizes
= XCNEWVEC (unsigned, num
);
1602 memset (sizes
, 0, sizeof (unsigned) * num
);
1603 FOR_EACH_BB_FN (bb
, cfun
)
1606 if (bb
->loop_father
== current_loops
->tree_root
)
1608 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1610 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
1614 exit
= get_exit_descriptions (e
);
1617 error ("exit %d->%d not recorded",
1618 e
->src
->index
, e
->dest
->index
);
1622 for (; exit
; exit
= exit
->next_e
)
1625 for (loop
= bb
->loop_father
;
1626 loop
!= e
->dest
->loop_father
1627 /* When a loop exit is also an entry edge which
1628 can happen when avoiding CFG manipulations
1629 then the last loop exited is the outer loop
1630 of the loop entered. */
1631 && loop
!= loop_outer (e
->dest
->loop_father
);
1632 loop
= loop_outer (loop
))
1640 error ("wrong list of exited loops for edge %d->%d",
1641 e
->src
->index
, e
->dest
->index
);
1647 if (n_exits
!= current_loops
->exits
->elements ())
1649 error ("too many loop exits recorded");
1653 FOR_EACH_LOOP (loop
, 0)
1656 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1658 if (eloops
!= sizes
[loop
->num
])
1660 error ("%d exits recorded for loop %d (having %d exits)",
1661 eloops
, loop
->num
, sizes
[loop
->num
]);
1672 free_dominance_info (CDI_DOMINATORS
);
1675 /* Returns latch edge of LOOP. */
1677 loop_latch_edge (const struct loop
*loop
)
1679 return find_edge (loop
->latch
, loop
->header
);
1682 /* Returns preheader edge of LOOP. */
1684 loop_preheader_edge (const struct loop
*loop
)
1689 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
));
1691 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1692 if (e
->src
!= loop
->latch
)
1698 /* Returns true if E is an exit of LOOP. */
1701 loop_exit_edge_p (const struct loop
*loop
, const_edge e
)
1703 return (flow_bb_inside_loop_p (loop
, e
->src
)
1704 && !flow_bb_inside_loop_p (loop
, e
->dest
));
1707 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1708 or more than one exit. If loops do not have the exits recorded, NULL
1709 is returned always. */
1712 single_exit (const struct loop
*loop
)
1714 struct loop_exit
*exit
= loop
->exits
->next
;
1716 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1719 if (exit
->e
&& exit
->next
== loop
->exits
)
1725 /* Returns true when BB has an incoming edge exiting LOOP. */
1728 loop_exits_to_bb_p (struct loop
*loop
, basic_block bb
)
1733 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1734 if (loop_exit_edge_p (loop
, e
))
1740 /* Returns true when BB has an outgoing edge exiting LOOP. */
1743 loop_exits_from_bb_p (struct loop
*loop
, basic_block bb
)
1748 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1749 if (loop_exit_edge_p (loop
, e
))
1755 /* Return location corresponding to the loop control condition if possible. */
1758 get_loop_location (struct loop
*loop
)
1760 rtx_insn
*insn
= NULL
;
1761 struct niter_desc
*desc
= NULL
;
1764 /* For a for or while loop, we would like to return the location
1765 of the for or while statement, if possible. To do this, look
1766 for the branch guarding the loop back-edge. */
1768 /* If this is a simple loop with an in_edge, then the loop control
1769 branch is typically at the end of its source. */
1770 desc
= get_simple_loop_desc (loop
);
1773 FOR_BB_INSNS_REVERSE (desc
->in_edge
->src
, insn
)
1775 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1776 return INSN_LOCATION (insn
);
1779 /* If loop has a single exit, then the loop control branch
1780 must be at the end of its source. */
1781 if ((exit
= single_exit (loop
)))
1783 FOR_BB_INSNS_REVERSE (exit
->src
, insn
)
1785 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1786 return INSN_LOCATION (insn
);
1789 /* Next check the latch, to see if it is non-empty. */
1790 FOR_BB_INSNS_REVERSE (loop
->latch
, insn
)
1792 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1793 return INSN_LOCATION (insn
);
1795 /* Finally, if none of the above identifies the loop control branch,
1796 return the first location in the loop header. */
1797 FOR_BB_INSNS (loop
->header
, insn
)
1799 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1800 return INSN_LOCATION (insn
);
1802 /* If all else fails, simply return the current function location. */
1803 return DECL_SOURCE_LOCATION (current_function_decl
);
1806 /* Records that every statement in LOOP is executed I_BOUND times.
1807 REALISTIC is true if I_BOUND is expected to be close to the real number
1808 of iterations. UPPER is true if we are sure the loop iterates at most
1812 record_niter_bound (struct loop
*loop
, const widest_int
&i_bound
,
1813 bool realistic
, bool upper
)
1815 /* Update the bounds only when there is no previous estimation, or when the
1816 current estimation is smaller. */
1818 && (!loop
->any_upper_bound
1819 || wi::ltu_p (i_bound
, loop
->nb_iterations_upper_bound
)))
1821 loop
->any_upper_bound
= true;
1822 loop
->nb_iterations_upper_bound
= i_bound
;
1825 && (!loop
->any_estimate
1826 || wi::ltu_p (i_bound
, loop
->nb_iterations_estimate
)))
1828 loop
->any_estimate
= true;
1829 loop
->nb_iterations_estimate
= i_bound
;
1832 /* If an upper bound is smaller than the realistic estimate of the
1833 number of iterations, use the upper bound instead. */
1834 if (loop
->any_upper_bound
1835 && loop
->any_estimate
1836 && wi::ltu_p (loop
->nb_iterations_upper_bound
,
1837 loop
->nb_iterations_estimate
))
1838 loop
->nb_iterations_estimate
= loop
->nb_iterations_upper_bound
;
1841 /* Similar to get_estimated_loop_iterations, but returns the estimate only
1842 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1843 on the number of iterations of LOOP could not be derived, returns -1. */
1846 get_estimated_loop_iterations_int (struct loop
*loop
)
1849 HOST_WIDE_INT hwi_nit
;
1851 if (!get_estimated_loop_iterations (loop
, &nit
))
1854 if (!wi::fits_shwi_p (nit
))
1856 hwi_nit
= nit
.to_shwi ();
1858 return hwi_nit
< 0 ? -1 : hwi_nit
;
1861 /* Returns an upper bound on the number of executions of statements
1862 in the LOOP. For statements before the loop exit, this exceeds
1863 the number of execution of the latch by one. */
1866 max_stmt_executions_int (struct loop
*loop
)
1868 HOST_WIDE_INT nit
= get_max_loop_iterations_int (loop
);
1874 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
1876 /* If the computation overflows, return -1. */
1877 return snit
< 0 ? -1 : snit
;
1880 /* Sets NIT to the estimated number of executions of the latch of the
1881 LOOP. If we have no reliable estimate, the function returns false, otherwise
1885 get_estimated_loop_iterations (struct loop
*loop
, widest_int
*nit
)
1887 /* Even if the bound is not recorded, possibly we can derrive one from
1889 if (!loop
->any_estimate
)
1891 if (loop
->header
->count
)
1893 *nit
= gcov_type_to_wide_int
1894 (expected_loop_iterations_unbounded (loop
) + 1);
1900 *nit
= loop
->nb_iterations_estimate
;
1904 /* Sets NIT to an upper bound for the maximum number of executions of the
1905 latch of the LOOP. If we have no reliable estimate, the function returns
1906 false, otherwise returns true. */
1909 get_max_loop_iterations (struct loop
*loop
, widest_int
*nit
)
1911 if (!loop
->any_upper_bound
)
1914 *nit
= loop
->nb_iterations_upper_bound
;
1918 /* Similar to get_max_loop_iterations, but returns the estimate only
1919 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1920 on the number of iterations of LOOP could not be derived, returns -1. */
1923 get_max_loop_iterations_int (struct loop
*loop
)
1926 HOST_WIDE_INT hwi_nit
;
1928 if (!get_max_loop_iterations (loop
, &nit
))
1931 if (!wi::fits_shwi_p (nit
))
1933 hwi_nit
= nit
.to_shwi ();
1935 return hwi_nit
< 0 ? -1 : hwi_nit
;
1938 /* Returns the loop depth of the loop BB belongs to. */
1941 bb_loop_depth (const_basic_block bb
)
1943 return bb
->loop_father
? loop_depth (bb
->loop_father
) : 0;
1946 /* Marks LOOP for removal and sets LOOPS_NEED_FIXUP. */
1949 mark_loop_for_removal (loop_p loop
)
1951 if (loop
->header
== NULL
)
1953 loop
->former_header
= loop
->header
;
1954 loop
->header
= NULL
;
1956 loops_state_set (LOOPS_NEED_FIXUP
);