1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000-2016 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));
142 gcov_type nit
= expected_loop_iterations_unbounded (loop
, &read_profile_p
);
143 if (read_profile_p
&& !loop
->any_estimate
)
144 fprintf (file
, ";; profile-based iteration count: %lu\n", nit
);
147 fprintf (file
, ";; nodes:");
148 bbs
= get_loop_body (loop
);
149 for (i
= 0; i
< loop
->num_nodes
; i
++)
150 fprintf (file
, " %d", bbs
[i
]->index
);
152 fprintf (file
, "\n");
155 loop_dump_aux (loop
, file
, verbose
);
158 /* Dump the loop information about loops to the stream FILE,
159 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
162 flow_loops_dump (FILE *file
, void (*loop_dump_aux
) (const struct loop
*, FILE *, int), int verbose
)
166 if (!current_loops
|| ! file
)
169 fprintf (file
, ";; %d loops found\n", number_of_loops (cfun
));
171 FOR_EACH_LOOP (loop
, LI_INCLUDE_ROOT
)
173 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
);
177 flow_loops_cfg_dump (file
);
180 /* Free data allocated for LOOP. */
183 flow_loop_free (struct loop
*loop
)
185 struct loop_exit
*exit
, *next
;
187 vec_free (loop
->superloops
);
189 /* Break the list of the loop exit records. They will be freed when the
190 corresponding edge is rescanned or removed, and this avoids
191 accessing the (already released) head of the list stored in the
193 for (exit
= loop
->exits
->next
; exit
!= loop
->exits
; exit
= next
)
200 ggc_free (loop
->exits
);
204 /* Free all the memory allocated for LOOPS. */
207 flow_loops_free (struct loops
*loops
)
214 /* Free the loop descriptors. */
215 FOR_EACH_VEC_SAFE_ELT (loops
->larray
, i
, loop
)
220 flow_loop_free (loop
);
223 vec_free (loops
->larray
);
227 /* Find the nodes contained within the LOOP with header HEADER.
228 Return the number of nodes within the loop. */
231 flow_loop_nodes_find (basic_block header
, struct loop
*loop
)
233 vec
<basic_block
> stack
= vNULL
;
236 edge_iterator latch_ei
;
238 header
->loop_father
= loop
;
240 FOR_EACH_EDGE (latch
, latch_ei
, loop
->header
->preds
)
242 if (latch
->src
->loop_father
== loop
243 || !dominated_by_p (CDI_DOMINATORS
, latch
->src
, loop
->header
))
247 stack
.safe_push (latch
->src
);
248 latch
->src
->loop_father
= loop
;
250 while (!stack
.is_empty ())
258 FOR_EACH_EDGE (e
, ei
, node
->preds
)
260 basic_block ancestor
= e
->src
;
262 if (ancestor
->loop_father
!= loop
)
264 ancestor
->loop_father
= loop
;
266 stack
.safe_push (ancestor
);
276 /* Records the vector of superloops of the loop LOOP, whose immediate
277 superloop is FATHER. */
280 establish_preds (struct loop
*loop
, struct loop
*father
)
283 unsigned depth
= loop_depth (father
) + 1;
286 loop
->superloops
= 0;
287 vec_alloc (loop
->superloops
, depth
);
288 FOR_EACH_VEC_SAFE_ELT (father
->superloops
, i
, ploop
)
289 loop
->superloops
->quick_push (ploop
);
290 loop
->superloops
->quick_push (father
);
292 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
293 establish_preds (ploop
, loop
);
296 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
297 added loop. If LOOP has some children, take care of that their
298 pred field will be initialized correctly. */
301 flow_loop_tree_node_add (struct loop
*father
, struct loop
*loop
)
303 loop
->next
= father
->inner
;
304 father
->inner
= loop
;
306 establish_preds (loop
, father
);
309 /* Remove LOOP from the loop hierarchy tree. */
312 flow_loop_tree_node_remove (struct loop
*loop
)
314 struct loop
*prev
, *father
;
316 father
= loop_outer (loop
);
318 /* Remove loop from the list of sons. */
319 if (father
->inner
== loop
)
320 father
->inner
= loop
->next
;
323 for (prev
= father
->inner
; prev
->next
!= loop
; prev
= prev
->next
)
325 prev
->next
= loop
->next
;
328 loop
->superloops
= NULL
;
331 /* Allocates and returns new loop structure. */
336 struct loop
*loop
= ggc_cleared_alloc
<struct loop
> ();
338 loop
->exits
= ggc_cleared_alloc
<loop_exit
> ();
339 loop
->exits
->next
= loop
->exits
->prev
= loop
->exits
;
340 loop
->can_be_parallel
= false;
341 loop
->nb_iterations_upper_bound
= 0;
342 loop
->nb_iterations_likely_upper_bound
= 0;
343 loop
->nb_iterations_estimate
= 0;
347 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
348 (including the root of the loop tree). */
351 init_loops_structure (struct function
*fn
,
352 struct loops
*loops
, unsigned num_loops
)
356 memset (loops
, 0, sizeof *loops
);
357 vec_alloc (loops
->larray
, num_loops
);
359 /* Dummy loop containing whole function. */
360 root
= alloc_loop ();
361 root
->num_nodes
= n_basic_blocks_for_fn (fn
);
362 root
->latch
= EXIT_BLOCK_PTR_FOR_FN (fn
);
363 root
->header
= ENTRY_BLOCK_PTR_FOR_FN (fn
);
364 ENTRY_BLOCK_PTR_FOR_FN (fn
)->loop_father
= root
;
365 EXIT_BLOCK_PTR_FOR_FN (fn
)->loop_father
= root
;
367 loops
->larray
->quick_push (root
);
368 loops
->tree_root
= root
;
371 /* Returns whether HEADER is a loop header. */
374 bb_loop_header_p (basic_block header
)
379 /* If we have an abnormal predecessor, do not consider the
380 loop (not worth the problems). */
381 if (bb_has_abnormal_pred (header
))
384 /* Look for back edges where a predecessor is dominated
385 by this block. A natural loop has a single entry
386 node (header) that dominates all the nodes in the
387 loop. It also has single back edge to the header
388 from a latch node. */
389 FOR_EACH_EDGE (e
, ei
, header
->preds
)
391 basic_block latch
= e
->src
;
392 if (latch
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
393 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
400 /* Find all the natural loops in the function and save in LOOPS structure and
401 recalculate loop_father information in basic block structures.
402 If LOOPS is non-NULL then the loop structures for already recorded loops
403 will be re-used and their number will not change. We assume that no
404 stale loops exist in LOOPS.
405 When LOOPS is NULL it is allocated and re-built from scratch.
406 Return the built LOOPS structure. */
409 flow_loops_find (struct loops
*loops
)
411 bool from_scratch
= (loops
== NULL
);
416 /* Ensure that the dominators are computed. */
417 calculate_dominance_info (CDI_DOMINATORS
);
421 loops
= ggc_cleared_alloc
<struct loops
> ();
422 init_loops_structure (cfun
, loops
, 1);
425 /* Ensure that loop exits were released. */
426 gcc_assert (loops
->exits
== NULL
);
428 /* Taking care of this degenerate case makes the rest of
429 this code simpler. */
430 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
433 /* The root loop node contains all basic-blocks. */
434 loops
->tree_root
->num_nodes
= n_basic_blocks_for_fn (cfun
);
436 /* Compute depth first search order of the CFG so that outer
437 natural loops will be found before inner natural loops. */
438 rc_order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
439 pre_and_rev_post_order_compute (NULL
, rc_order
, false);
441 /* Gather all loop headers in reverse completion order and allocate
442 loop structures for loops that are not already present. */
443 auto_vec
<loop_p
> larray (loops
->larray
->length ());
444 for (b
= 0; b
< n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
; b
++)
446 basic_block header
= BASIC_BLOCK_FOR_FN (cfun
, rc_order
[b
]);
447 if (bb_loop_header_p (header
))
451 /* The current active loop tree has valid loop-fathers for
454 && header
->loop_father
->header
== header
)
456 loop
= header
->loop_father
;
457 /* If we found an existing loop remove it from the
458 loop tree. It is going to be inserted again
460 flow_loop_tree_node_remove (loop
);
464 /* Otherwise allocate a new loop structure for the loop. */
465 loop
= alloc_loop ();
466 /* ??? We could re-use unused loop slots here. */
467 loop
->num
= loops
->larray
->length ();
468 vec_safe_push (loops
->larray
, loop
);
469 loop
->header
= header
;
472 && dump_file
&& (dump_flags
& TDF_DETAILS
))
473 fprintf (dump_file
, "flow_loops_find: discovered new "
474 "loop %d with header %d\n",
475 loop
->num
, header
->index
);
477 /* Reset latch, we recompute it below. */
479 larray
.safe_push (loop
);
482 /* Make blocks part of the loop root node at start. */
483 header
->loop_father
= loops
->tree_root
;
488 /* Now iterate over the loops found, insert them into the loop tree
489 and assign basic-block ownership. */
490 for (i
= 0; i
< larray
.length (); ++i
)
492 struct loop
*loop
= larray
[i
];
493 basic_block header
= loop
->header
;
497 flow_loop_tree_node_add (header
->loop_father
, loop
);
498 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
500 /* Look for the latch for this header block, if it has just a
502 FOR_EACH_EDGE (e
, ei
, header
->preds
)
504 basic_block latch
= e
->src
;
506 if (flow_bb_inside_loop_p (loop
, latch
))
508 if (loop
->latch
!= NULL
)
510 /* More than one latch edge. */
522 /* Ratio of frequencies of edges so that one of more latch edges is
523 considered to belong to inner loop with same header. */
524 #define HEAVY_EDGE_RATIO 8
526 /* Minimum number of samples for that we apply
527 find_subloop_latch_edge_by_profile heuristics. */
528 #define HEAVY_EDGE_MIN_SAMPLES 10
530 /* If the profile info is available, finds an edge in LATCHES that much more
531 frequent than the remaining edges. Returns such an edge, or NULL if we do
534 We do not use guessed profile here, only the measured one. The guessed
535 profile is usually too flat and unreliable for this (and it is mostly based
536 on the loop structure of the program, so it does not make much sense to
537 derive the loop structure from it). */
540 find_subloop_latch_edge_by_profile (vec
<edge
> latches
)
544 gcov_type mcount
= 0, tcount
= 0;
546 FOR_EACH_VEC_ELT (latches
, i
, e
)
548 if (e
->count
> mcount
)
556 if (tcount
< HEAVY_EDGE_MIN_SAMPLES
557 || (tcount
- mcount
) * HEAVY_EDGE_RATIO
> tcount
)
562 "Found latch edge %d -> %d using profile information.\n",
563 me
->src
->index
, me
->dest
->index
);
567 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
568 on the structure of induction variables. Returns this edge, or NULL if we
571 We are quite conservative, and look just for an obvious simple innermost
572 loop (which is the case where we would lose the most performance by not
573 disambiguating the loop). More precisely, we look for the following
574 situation: The source of the chosen latch edge dominates sources of all
575 the other latch edges. Additionally, the header does not contain a phi node
576 such that the argument from the chosen edge is equal to the argument from
580 find_subloop_latch_edge_by_ivs (struct loop
*loop ATTRIBUTE_UNUSED
, vec
<edge
> latches
)
582 edge e
, latch
= latches
[0];
589 /* Find the candidate for the latch edge. */
590 for (i
= 1; latches
.iterate (i
, &e
); i
++)
591 if (dominated_by_p (CDI_DOMINATORS
, latch
->src
, e
->src
))
594 /* Verify that it dominates all the latch edges. */
595 FOR_EACH_VEC_ELT (latches
, i
, e
)
596 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, latch
->src
))
599 /* Check for a phi node that would deny that this is a latch edge of
601 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
604 lop
= PHI_ARG_DEF_FROM_EDGE (phi
, latch
);
606 /* Ignore the values that are not changed inside the subloop. */
607 if (TREE_CODE (lop
) != SSA_NAME
608 || SSA_NAME_DEF_STMT (lop
) == phi
)
610 bb
= gimple_bb (SSA_NAME_DEF_STMT (lop
));
611 if (!bb
|| !flow_bb_inside_loop_p (loop
, bb
))
614 FOR_EACH_VEC_ELT (latches
, i
, e
)
616 && PHI_ARG_DEF_FROM_EDGE (phi
, e
) == lop
)
622 "Found latch edge %d -> %d using iv structure.\n",
623 latch
->src
->index
, latch
->dest
->index
);
627 /* If we can determine that one of the several latch edges of LOOP behaves
628 as a latch edge of a separate subloop, returns this edge. Otherwise
632 find_subloop_latch_edge (struct loop
*loop
)
634 vec
<edge
> latches
= get_loop_latch_edges (loop
);
637 if (latches
.length () > 1)
639 latch
= find_subloop_latch_edge_by_profile (latches
);
642 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
643 should use cfghook for this, but it is hard to imagine it would
644 be useful elsewhere. */
645 && current_ir_type () == IR_GIMPLE
)
646 latch
= find_subloop_latch_edge_by_ivs (loop
, latches
);
653 /* Callback for make_forwarder_block. Returns true if the edge E is marked
654 in the set MFB_REIS_SET. */
656 static hash_set
<edge
> *mfb_reis_set
;
658 mfb_redirect_edges_in_set (edge e
)
660 return mfb_reis_set
->contains (e
);
663 /* Creates a subloop of LOOP with latch edge LATCH. */
666 form_subloop (struct loop
*loop
, edge latch
)
670 struct loop
*new_loop
;
672 mfb_reis_set
= new hash_set
<edge
>;
673 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
676 mfb_reis_set
->add (e
);
678 new_entry
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
682 loop
->header
= new_entry
->src
;
684 /* Find the blocks and subloops that belong to the new loop, and add it to
685 the appropriate place in the loop tree. */
686 new_loop
= alloc_loop ();
687 new_loop
->header
= new_entry
->dest
;
688 new_loop
->latch
= latch
->src
;
689 add_loop (new_loop
, loop
);
692 /* Make all the latch edges of LOOP to go to a single forwarder block --
693 a new latch of LOOP. */
696 merge_latch_edges (struct loop
*loop
)
698 vec
<edge
> latches
= get_loop_latch_edges (loop
);
702 gcc_assert (latches
.length () > 0);
704 if (latches
.length () == 1)
705 loop
->latch
= latches
[0]->src
;
709 fprintf (dump_file
, "Merged latch edges of loop %d\n", loop
->num
);
711 mfb_reis_set
= new hash_set
<edge
>;
712 FOR_EACH_VEC_ELT (latches
, i
, e
)
713 mfb_reis_set
->add (e
);
714 latch
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
718 loop
->header
= latch
->dest
;
719 loop
->latch
= latch
->src
;
725 /* LOOP may have several latch edges. Transform it into (possibly several)
726 loops with single latch edge. */
729 disambiguate_multiple_latches (struct loop
*loop
)
733 /* We eliminate the multiple latches by splitting the header to the forwarder
734 block F and the rest R, and redirecting the edges. There are two cases:
736 1) If there is a latch edge E that corresponds to a subloop (we guess
737 that based on profile -- if it is taken much more often than the
738 remaining edges; and on trees, using the information about induction
739 variables of the loops), we redirect E to R, all the remaining edges to
740 F, then rescan the loops and try again for the outer loop.
741 2) If there is no such edge, we redirect all latch edges to F, and the
742 entry edges to R, thus making F the single latch of the loop. */
745 fprintf (dump_file
, "Disambiguating loop %d with multiple latches\n",
748 /* During latch merging, we may need to redirect the entry edges to a new
749 block. This would cause problems if the entry edge was the one from the
750 entry block. To avoid having to handle this case specially, split
752 e
= find_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), loop
->header
);
758 e
= find_subloop_latch_edge (loop
);
762 form_subloop (loop
, e
);
765 merge_latch_edges (loop
);
768 /* Split loops with multiple latch edges. */
771 disambiguate_loops_with_multiple_latches (void)
775 FOR_EACH_LOOP (loop
, 0)
778 disambiguate_multiple_latches (loop
);
782 /* Return nonzero if basic block BB belongs to LOOP. */
784 flow_bb_inside_loop_p (const struct loop
*loop
, const_basic_block bb
)
786 struct loop
*source_loop
;
788 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
789 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
792 source_loop
= bb
->loop_father
;
793 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
796 /* Enumeration predicate for get_loop_body_with_size. */
798 glb_enum_p (const_basic_block bb
, const void *glb_loop
)
800 const struct loop
*const loop
= (const struct loop
*) glb_loop
;
801 return (bb
!= loop
->header
802 && dominated_by_p (CDI_DOMINATORS
, bb
, loop
->header
));
805 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
806 order against direction of edges from latch. Specially, if
807 header != latch, latch is the 1-st block. LOOP cannot be the fake
808 loop tree root, and its size must be at most MAX_SIZE. The blocks
809 in the LOOP body are stored to BODY, and the size of the LOOP is
813 get_loop_body_with_size (const struct loop
*loop
, basic_block
*body
,
816 return dfs_enumerate_from (loop
->header
, 1, glb_enum_p
,
817 body
, max_size
, loop
);
820 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
821 order against direction of edges from latch. Specially, if
822 header != latch, latch is the 1-st block. */
825 get_loop_body (const struct loop
*loop
)
827 basic_block
*body
, bb
;
830 gcc_assert (loop
->num_nodes
);
832 body
= XNEWVEC (basic_block
, loop
->num_nodes
);
834 if (loop
->latch
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
836 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
837 special-case the fake loop that contains the whole function. */
838 gcc_assert (loop
->num_nodes
== (unsigned) n_basic_blocks_for_fn (cfun
));
839 body
[tv
++] = loop
->header
;
840 body
[tv
++] = EXIT_BLOCK_PTR_FOR_FN (cfun
);
841 FOR_EACH_BB_FN (bb
, cfun
)
845 tv
= get_loop_body_with_size (loop
, body
, loop
->num_nodes
);
847 gcc_assert (tv
== loop
->num_nodes
);
851 /* Fills dominance descendants inside LOOP of the basic block BB into
852 array TOVISIT from index *TV. */
855 fill_sons_in_loop (const struct loop
*loop
, basic_block bb
,
856 basic_block
*tovisit
, int *tv
)
858 basic_block son
, postpone
= NULL
;
860 tovisit
[(*tv
)++] = bb
;
861 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
863 son
= next_dom_son (CDI_DOMINATORS
, son
))
865 if (!flow_bb_inside_loop_p (loop
, son
))
868 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, son
))
873 fill_sons_in_loop (loop
, son
, tovisit
, tv
);
877 fill_sons_in_loop (loop
, postpone
, tovisit
, tv
);
880 /* Gets body of a LOOP (that must be different from the outermost loop)
881 sorted by dominance relation. Additionally, if a basic block s dominates
882 the latch, then only blocks dominated by s are be after it. */
885 get_loop_body_in_dom_order (const struct loop
*loop
)
887 basic_block
*tovisit
;
890 gcc_assert (loop
->num_nodes
);
892 tovisit
= XNEWVEC (basic_block
, loop
->num_nodes
);
894 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
897 fill_sons_in_loop (loop
, loop
->header
, tovisit
, &tv
);
899 gcc_assert (tv
== (int) loop
->num_nodes
);
904 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
907 get_loop_body_in_custom_order (const struct loop
*loop
,
908 int (*bb_comparator
) (const void *, const void *))
910 basic_block
*bbs
= get_loop_body (loop
);
912 qsort (bbs
, loop
->num_nodes
, sizeof (basic_block
), bb_comparator
);
917 /* Get body of a LOOP in breadth first sort order. */
920 get_loop_body_in_bfs_order (const struct loop
*loop
)
928 gcc_assert (loop
->num_nodes
);
929 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
931 blocks
= XNEWVEC (basic_block
, loop
->num_nodes
);
932 visited
= BITMAP_ALLOC (NULL
);
933 blocks
[0] = loop
->header
;
934 bitmap_set_bit (visited
, loop
->header
->index
);
935 while (i
< loop
->num_nodes
)
942 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
944 if (flow_bb_inside_loop_p (loop
, e
->dest
))
946 /* This bb is now visited. */
947 if (bitmap_set_bit (visited
, e
->dest
->index
))
948 blocks
[i
++] = e
->dest
;
953 BITMAP_FREE (visited
);
957 /* Hash function for struct loop_exit. */
960 loop_exit_hasher::hash (loop_exit
*exit
)
962 return htab_hash_pointer (exit
->e
);
965 /* Equality function for struct loop_exit. Compares with edge. */
968 loop_exit_hasher::equal (loop_exit
*exit
, edge e
)
973 /* Frees the list of loop exit descriptions EX. */
976 loop_exit_hasher::remove (loop_exit
*exit
)
979 for (; exit
; exit
= next
)
983 exit
->next
->prev
= exit
->prev
;
984 exit
->prev
->next
= exit
->next
;
990 /* Returns the list of records for E as an exit of a loop. */
992 static struct loop_exit
*
993 get_exit_descriptions (edge e
)
995 return current_loops
->exits
->find_with_hash (e
, htab_hash_pointer (e
));
998 /* Updates the lists of loop exits in that E appears.
999 If REMOVED is true, E is being removed, and we
1000 just remove it from the lists of exits.
1001 If NEW_EDGE is true and E is not a loop exit, we
1002 do not try to remove it from loop exit lists. */
1005 rescan_loop_exit (edge e
, bool new_edge
, bool removed
)
1007 struct loop_exit
*exits
= NULL
, *exit
;
1008 struct loop
*aloop
, *cloop
;
1010 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1014 && e
->src
->loop_father
!= NULL
1015 && e
->dest
->loop_father
!= NULL
1016 && !flow_bb_inside_loop_p (e
->src
->loop_father
, e
->dest
))
1018 cloop
= find_common_loop (e
->src
->loop_father
, e
->dest
->loop_father
);
1019 for (aloop
= e
->src
->loop_father
;
1021 aloop
= loop_outer (aloop
))
1023 exit
= ggc_alloc
<loop_exit
> ();
1026 exit
->next
= aloop
->exits
->next
;
1027 exit
->prev
= aloop
->exits
;
1028 exit
->next
->prev
= exit
;
1029 exit
->prev
->next
= exit
;
1031 exit
->next_e
= exits
;
1036 if (!exits
&& new_edge
)
1040 = current_loops
->exits
->find_slot_with_hash (e
, htab_hash_pointer (e
),
1041 exits
? INSERT
: NO_INSERT
);
1048 loop_exit_hasher::remove (*slot
);
1052 current_loops
->exits
->clear_slot (slot
);
1055 /* For each loop, record list of exit edges, and start maintaining these
1059 record_loop_exits (void)
1068 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1070 loops_state_set (LOOPS_HAVE_RECORDED_EXITS
);
1072 gcc_assert (current_loops
->exits
== NULL
);
1073 current_loops
->exits
1074 = hash_table
<loop_exit_hasher
>::create_ggc (2 * number_of_loops (cfun
));
1076 FOR_EACH_BB_FN (bb
, cfun
)
1078 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1080 rescan_loop_exit (e
, true, false);
1085 /* Dumps information about the exit in *SLOT to FILE.
1086 Callback for htab_traverse. */
1089 dump_recorded_exit (loop_exit
**slot
, FILE *file
)
1091 struct loop_exit
*exit
= *slot
;
1095 for (; exit
!= NULL
; exit
= exit
->next_e
)
1098 fprintf (file
, "Edge %d->%d exits %u loops\n",
1099 e
->src
->index
, e
->dest
->index
, n
);
1104 /* Dumps the recorded exits of loops to FILE. */
1106 extern void dump_recorded_exits (FILE *);
1108 dump_recorded_exits (FILE *file
)
1110 if (!current_loops
->exits
)
1112 current_loops
->exits
->traverse
<FILE *, dump_recorded_exit
> (file
);
1115 /* Releases lists of loop exits. */
1118 release_recorded_exits (function
*fn
)
1120 gcc_assert (loops_state_satisfies_p (fn
, LOOPS_HAVE_RECORDED_EXITS
));
1121 loops_for_fn (fn
)->exits
->empty ();
1122 loops_for_fn (fn
)->exits
= NULL
;
1123 loops_state_clear (fn
, LOOPS_HAVE_RECORDED_EXITS
);
1126 /* Returns the list of the exit edges of a LOOP. */
1129 get_loop_exit_edges (const struct loop
*loop
)
1131 vec
<edge
> edges
= vNULL
;
1136 struct loop_exit
*exit
;
1138 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1140 /* If we maintain the lists of exits, use them. Otherwise we must
1141 scan the body of the loop. */
1142 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1144 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1145 edges
.safe_push (exit
->e
);
1149 body
= get_loop_body (loop
);
1150 for (i
= 0; i
< loop
->num_nodes
; i
++)
1151 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
1153 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1154 edges
.safe_push (e
);
1162 /* Counts the number of conditional branches inside LOOP. */
1165 num_loop_branches (const struct loop
*loop
)
1170 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1172 body
= get_loop_body (loop
);
1174 for (i
= 0; i
< loop
->num_nodes
; i
++)
1175 if (EDGE_COUNT (body
[i
]->succs
) >= 2)
1182 /* Adds basic block BB to LOOP. */
1184 add_bb_to_loop (basic_block bb
, struct loop
*loop
)
1191 gcc_assert (bb
->loop_father
== NULL
);
1192 bb
->loop_father
= loop
;
1194 FOR_EACH_VEC_SAFE_ELT (loop
->superloops
, i
, ploop
)
1197 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1199 rescan_loop_exit (e
, true, false);
1201 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1203 rescan_loop_exit (e
, true, false);
1207 /* Remove basic block BB from loops. */
1209 remove_bb_from_loops (basic_block bb
)
1212 struct loop
*loop
= bb
->loop_father
;
1217 gcc_assert (loop
!= NULL
);
1219 FOR_EACH_VEC_SAFE_ELT (loop
->superloops
, i
, ploop
)
1221 bb
->loop_father
= NULL
;
1223 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1225 rescan_loop_exit (e
, false, true);
1227 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1229 rescan_loop_exit (e
, false, true);
1233 /* Finds nearest common ancestor in loop tree for given loops. */
1235 find_common_loop (struct loop
*loop_s
, struct loop
*loop_d
)
1237 unsigned sdepth
, ddepth
;
1239 if (!loop_s
) return loop_d
;
1240 if (!loop_d
) return loop_s
;
1242 sdepth
= loop_depth (loop_s
);
1243 ddepth
= loop_depth (loop_d
);
1245 if (sdepth
< ddepth
)
1246 loop_d
= (*loop_d
->superloops
)[sdepth
];
1247 else if (sdepth
> ddepth
)
1248 loop_s
= (*loop_s
->superloops
)[ddepth
];
1250 while (loop_s
!= loop_d
)
1252 loop_s
= loop_outer (loop_s
);
1253 loop_d
= loop_outer (loop_d
);
1258 /* Removes LOOP from structures and frees its data. */
1261 delete_loop (struct loop
*loop
)
1263 /* Remove the loop from structure. */
1264 flow_loop_tree_node_remove (loop
);
1266 /* Remove loop from loops array. */
1267 (*current_loops
->larray
)[loop
->num
] = NULL
;
1269 /* Free loop data. */
1270 flow_loop_free (loop
);
1273 /* Cancels the LOOP; it must be innermost one. */
1276 cancel_loop (struct loop
*loop
)
1280 struct loop
*outer
= loop_outer (loop
);
1282 gcc_assert (!loop
->inner
);
1284 /* Move blocks up one level (they should be removed as soon as possible). */
1285 bbs
= get_loop_body (loop
);
1286 for (i
= 0; i
< loop
->num_nodes
; i
++)
1287 bbs
[i
]->loop_father
= outer
;
1293 /* Cancels LOOP and all its subloops. */
1295 cancel_loop_tree (struct loop
*loop
)
1298 cancel_loop_tree (loop
->inner
);
1302 /* Checks that information about loops is correct
1303 -- sizes of loops are all right
1304 -- results of get_loop_body really belong to the loop
1305 -- loop header have just single entry edge and single latch edge
1306 -- loop latches have only single successor that is header of their loop
1307 -- irreducible loops are correctly marked
1308 -- the cached loop depth and loop father of each bb is correct
1311 verify_loop_structure (void)
1313 unsigned *sizes
, i
, j
;
1315 basic_block bb
, *bbs
;
1319 unsigned num
= number_of_loops (cfun
);
1320 struct loop_exit
*exit
, *mexit
;
1321 bool dom_available
= dom_info_available_p (CDI_DOMINATORS
);
1324 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
1326 error ("loop verification on loop tree that needs fixup");
1330 /* We need up-to-date dominators, compute or verify them. */
1332 calculate_dominance_info (CDI_DOMINATORS
);
1334 verify_dominators (CDI_DOMINATORS
);
1336 /* Check the loop tree root. */
1337 if (current_loops
->tree_root
->header
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1338 || current_loops
->tree_root
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1339 || (current_loops
->tree_root
->num_nodes
1340 != (unsigned) n_basic_blocks_for_fn (cfun
)))
1342 error ("corrupt loop tree root");
1346 /* Check the headers. */
1347 FOR_EACH_BB_FN (bb
, cfun
)
1348 if (bb_loop_header_p (bb
))
1350 if (bb
->loop_father
->header
== NULL
)
1352 error ("loop with header %d marked for removal", bb
->index
);
1355 else if (bb
->loop_father
->header
!= bb
)
1357 error ("loop with header %d not in loop tree", bb
->index
);
1361 else if (bb
->loop_father
->header
== bb
)
1363 error ("non-loop with header %d not marked for removal", bb
->index
);
1367 /* Check the recorded loop father and sizes of loops. */
1368 visited
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1369 bitmap_clear (visited
);
1370 bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
1371 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
1375 if (loop
->header
== NULL
)
1377 error ("removed loop %d in loop tree", loop
->num
);
1382 n
= get_loop_body_with_size (loop
, bbs
, n_basic_blocks_for_fn (cfun
));
1383 if (loop
->num_nodes
!= n
)
1385 error ("size of loop %d should be %d, not %d",
1386 loop
->num
, n
, loop
->num_nodes
);
1390 for (j
= 0; j
< n
; j
++)
1394 if (!flow_bb_inside_loop_p (loop
, bb
))
1396 error ("bb %d does not belong to loop %d",
1397 bb
->index
, loop
->num
);
1401 /* Ignore this block if it is in an inner loop. */
1402 if (bitmap_bit_p (visited
, bb
->index
))
1404 bitmap_set_bit (visited
, bb
->index
);
1406 if (bb
->loop_father
!= loop
)
1408 error ("bb %d has father loop %d, should be loop %d",
1409 bb
->index
, bb
->loop_father
->num
, loop
->num
);
1415 sbitmap_free (visited
);
1417 /* Check headers and latches. */
1418 FOR_EACH_LOOP (loop
, 0)
1421 if (loop
->header
== NULL
)
1423 if (!bb_loop_header_p (loop
->header
))
1425 error ("loop %d%'s header is not a loop header", i
);
1428 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
)
1429 && EDGE_COUNT (loop
->header
->preds
) != 2)
1431 error ("loop %d%'s header does not have exactly 2 entries", i
);
1436 if (!find_edge (loop
->latch
, loop
->header
))
1438 error ("loop %d%'s latch does not have an edge to its header", i
);
1441 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, loop
->header
))
1443 error ("loop %d%'s latch is not dominated by its header", i
);
1447 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
1449 if (!single_succ_p (loop
->latch
))
1451 error ("loop %d%'s latch does not have exactly 1 successor", i
);
1454 if (single_succ (loop
->latch
) != loop
->header
)
1456 error ("loop %d%'s latch does not have header as successor", i
);
1459 if (loop
->latch
->loop_father
!= loop
)
1461 error ("loop %d%'s latch does not belong directly to it", i
);
1465 if (loop
->header
->loop_father
!= loop
)
1467 error ("loop %d%'s header does not belong directly to it", i
);
1470 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
)
1471 && (loop_latch_edge (loop
)->flags
& EDGE_IRREDUCIBLE_LOOP
))
1473 error ("loop %d%'s latch is marked as part of irreducible region", i
);
1478 /* Check irreducible loops. */
1479 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1481 /* Record old info. */
1482 irreds
= sbitmap_alloc (last_basic_block_for_fn (cfun
));
1483 FOR_EACH_BB_FN (bb
, cfun
)
1486 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1487 bitmap_set_bit (irreds
, bb
->index
);
1489 bitmap_clear_bit (irreds
, bb
->index
);
1490 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1491 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1492 e
->flags
|= EDGE_ALL_FLAGS
+ 1;
1496 mark_irreducible_loops ();
1499 FOR_EACH_BB_FN (bb
, cfun
)
1503 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1504 && !bitmap_bit_p (irreds
, bb
->index
))
1506 error ("basic block %d should be marked irreducible", bb
->index
);
1509 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1510 && bitmap_bit_p (irreds
, bb
->index
))
1512 error ("basic block %d should not be marked irreducible", bb
->index
);
1515 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1517 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1518 && !(e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1520 error ("edge from %d to %d should be marked irreducible",
1521 e
->src
->index
, e
->dest
->index
);
1524 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1525 && (e
->flags
& (EDGE_ALL_FLAGS
+ 1)))
1527 error ("edge from %d to %d should not be marked irreducible",
1528 e
->src
->index
, e
->dest
->index
);
1531 e
->flags
&= ~(EDGE_ALL_FLAGS
+ 1);
1537 /* Check the recorded loop exits. */
1538 FOR_EACH_LOOP (loop
, 0)
1540 if (!loop
->exits
|| loop
->exits
->e
!= NULL
)
1542 error ("corrupted head of the exits list of loop %d",
1548 /* Check that the list forms a cycle, and all elements except
1549 for the head are nonnull. */
1550 for (mexit
= loop
->exits
, exit
= mexit
->next
, i
= 0;
1551 exit
->e
&& exit
!= mexit
;
1555 mexit
= mexit
->next
;
1558 if (exit
!= loop
->exits
)
1560 error ("corrupted exits list of loop %d", loop
->num
);
1565 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1567 if (loop
->exits
->next
!= loop
->exits
)
1569 error ("nonempty exits list of loop %d, but exits are not recorded",
1576 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1578 unsigned n_exits
= 0, eloops
;
1580 sizes
= XCNEWVEC (unsigned, num
);
1581 memset (sizes
, 0, sizeof (unsigned) * num
);
1582 FOR_EACH_BB_FN (bb
, cfun
)
1585 if (bb
->loop_father
== current_loops
->tree_root
)
1587 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1589 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
1593 exit
= get_exit_descriptions (e
);
1596 error ("exit %d->%d not recorded",
1597 e
->src
->index
, e
->dest
->index
);
1601 for (; exit
; exit
= exit
->next_e
)
1604 for (loop
= bb
->loop_father
;
1605 loop
!= e
->dest
->loop_father
1606 /* When a loop exit is also an entry edge which
1607 can happen when avoiding CFG manipulations
1608 then the last loop exited is the outer loop
1609 of the loop entered. */
1610 && loop
!= loop_outer (e
->dest
->loop_father
);
1611 loop
= loop_outer (loop
))
1619 error ("wrong list of exited loops for edge %d->%d",
1620 e
->src
->index
, e
->dest
->index
);
1626 if (n_exits
!= current_loops
->exits
->elements ())
1628 error ("too many loop exits recorded");
1632 FOR_EACH_LOOP (loop
, 0)
1635 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1637 if (eloops
!= sizes
[loop
->num
])
1639 error ("%d exits recorded for loop %d (having %d exits)",
1640 eloops
, loop
->num
, sizes
[loop
->num
]);
1651 free_dominance_info (CDI_DOMINATORS
);
1654 /* Returns latch edge of LOOP. */
1656 loop_latch_edge (const struct loop
*loop
)
1658 return find_edge (loop
->latch
, loop
->header
);
1661 /* Returns preheader edge of LOOP. */
1663 loop_preheader_edge (const struct loop
*loop
)
1668 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
));
1670 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1671 if (e
->src
!= loop
->latch
)
1677 /* Returns true if E is an exit of LOOP. */
1680 loop_exit_edge_p (const struct loop
*loop
, const_edge e
)
1682 return (flow_bb_inside_loop_p (loop
, e
->src
)
1683 && !flow_bb_inside_loop_p (loop
, e
->dest
));
1686 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1687 or more than one exit. If loops do not have the exits recorded, NULL
1688 is returned always. */
1691 single_exit (const struct loop
*loop
)
1693 struct loop_exit
*exit
= loop
->exits
->next
;
1695 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1698 if (exit
->e
&& exit
->next
== loop
->exits
)
1704 /* Returns true when BB has an incoming edge exiting LOOP. */
1707 loop_exits_to_bb_p (struct loop
*loop
, basic_block bb
)
1712 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1713 if (loop_exit_edge_p (loop
, e
))
1719 /* Returns true when BB has an outgoing edge exiting LOOP. */
1722 loop_exits_from_bb_p (struct loop
*loop
, basic_block bb
)
1727 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1728 if (loop_exit_edge_p (loop
, e
))
1734 /* Return location corresponding to the loop control condition if possible. */
1737 get_loop_location (struct loop
*loop
)
1739 rtx_insn
*insn
= NULL
;
1740 struct niter_desc
*desc
= NULL
;
1743 /* For a for or while loop, we would like to return the location
1744 of the for or while statement, if possible. To do this, look
1745 for the branch guarding the loop back-edge. */
1747 /* If this is a simple loop with an in_edge, then the loop control
1748 branch is typically at the end of its source. */
1749 desc
= get_simple_loop_desc (loop
);
1752 FOR_BB_INSNS_REVERSE (desc
->in_edge
->src
, insn
)
1754 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1755 return INSN_LOCATION (insn
);
1758 /* If loop has a single exit, then the loop control branch
1759 must be at the end of its source. */
1760 if ((exit
= single_exit (loop
)))
1762 FOR_BB_INSNS_REVERSE (exit
->src
, insn
)
1764 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1765 return INSN_LOCATION (insn
);
1768 /* Next check the latch, to see if it is non-empty. */
1769 FOR_BB_INSNS_REVERSE (loop
->latch
, insn
)
1771 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1772 return INSN_LOCATION (insn
);
1774 /* Finally, if none of the above identifies the loop control branch,
1775 return the first location in the loop header. */
1776 FOR_BB_INSNS (loop
->header
, insn
)
1778 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1779 return INSN_LOCATION (insn
);
1781 /* If all else fails, simply return the current function location. */
1782 return DECL_SOURCE_LOCATION (current_function_decl
);
1785 /* Records that every statement in LOOP is executed I_BOUND times.
1786 REALISTIC is true if I_BOUND is expected to be close to the real number
1787 of iterations. UPPER is true if we are sure the loop iterates at most
1791 record_niter_bound (struct loop
*loop
, const widest_int
&i_bound
,
1792 bool realistic
, bool upper
)
1794 /* Update the bounds only when there is no previous estimation, or when the
1795 current estimation is smaller. */
1797 && (!loop
->any_upper_bound
1798 || wi::ltu_p (i_bound
, loop
->nb_iterations_upper_bound
)))
1800 loop
->any_upper_bound
= true;
1801 loop
->nb_iterations_upper_bound
= i_bound
;
1802 if (!loop
->any_likely_upper_bound
)
1804 loop
->any_likely_upper_bound
= true;
1805 loop
->nb_iterations_likely_upper_bound
= i_bound
;
1809 && (!loop
->any_estimate
1810 || wi::ltu_p (i_bound
, loop
->nb_iterations_estimate
)))
1812 loop
->any_estimate
= true;
1813 loop
->nb_iterations_estimate
= i_bound
;
1816 && (!loop
->any_likely_upper_bound
1817 || wi::ltu_p (i_bound
, loop
->nb_iterations_likely_upper_bound
)))
1819 loop
->any_likely_upper_bound
= true;
1820 loop
->nb_iterations_likely_upper_bound
= i_bound
;
1823 /* If an upper bound is smaller than the realistic estimate of the
1824 number of iterations, use the upper bound instead. */
1825 if (loop
->any_upper_bound
1826 && loop
->any_estimate
1827 && wi::ltu_p (loop
->nb_iterations_upper_bound
,
1828 loop
->nb_iterations_estimate
))
1829 loop
->nb_iterations_estimate
= loop
->nb_iterations_upper_bound
;
1830 if (loop
->any_upper_bound
1831 && loop
->any_likely_upper_bound
1832 && wi::ltu_p (loop
->nb_iterations_upper_bound
,
1833 loop
->nb_iterations_likely_upper_bound
))
1834 loop
->nb_iterations_likely_upper_bound
= loop
->nb_iterations_upper_bound
;
1837 /* Similar to get_estimated_loop_iterations, but returns the estimate only
1838 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1839 on the number of iterations of LOOP could not be derived, returns -1. */
1842 get_estimated_loop_iterations_int (struct loop
*loop
)
1845 HOST_WIDE_INT hwi_nit
;
1847 if (!get_estimated_loop_iterations (loop
, &nit
))
1850 if (!wi::fits_shwi_p (nit
))
1852 hwi_nit
= nit
.to_shwi ();
1854 return hwi_nit
< 0 ? -1 : hwi_nit
;
1857 /* Returns an upper bound on the number of executions of statements
1858 in the LOOP. For statements before the loop exit, this exceeds
1859 the number of execution of the latch by one. */
1862 max_stmt_executions_int (struct loop
*loop
)
1864 HOST_WIDE_INT nit
= get_max_loop_iterations_int (loop
);
1870 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
1872 /* If the computation overflows, return -1. */
1873 return snit
< 0 ? -1 : snit
;
1876 /* Returns an likely upper bound on the number of executions of statements
1877 in the LOOP. For statements before the loop exit, this exceeds
1878 the number of execution of the latch by one. */
1881 likely_max_stmt_executions_int (struct loop
*loop
)
1883 HOST_WIDE_INT nit
= get_likely_max_loop_iterations_int (loop
);
1889 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
1891 /* If the computation overflows, return -1. */
1892 return snit
< 0 ? -1 : snit
;
1895 /* Sets NIT to the estimated number of executions of the latch of the
1896 LOOP. If we have no reliable estimate, the function returns false, otherwise
1900 get_estimated_loop_iterations (struct loop
*loop
, widest_int
*nit
)
1902 /* Even if the bound is not recorded, possibly we can derrive one from
1904 if (!loop
->any_estimate
)
1906 if (loop
->header
->count
)
1908 *nit
= gcov_type_to_wide_int
1909 (expected_loop_iterations_unbounded (loop
) + 1);
1915 *nit
= loop
->nb_iterations_estimate
;
1919 /* Sets NIT to an upper bound for the maximum number of executions of the
1920 latch of the LOOP. If we have no reliable estimate, the function returns
1921 false, otherwise returns true. */
1924 get_max_loop_iterations (const struct loop
*loop
, widest_int
*nit
)
1926 if (!loop
->any_upper_bound
)
1929 *nit
= loop
->nb_iterations_upper_bound
;
1933 /* Similar to get_max_loop_iterations, but returns the estimate only
1934 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1935 on the number of iterations of LOOP could not be derived, returns -1. */
1938 get_max_loop_iterations_int (const struct loop
*loop
)
1941 HOST_WIDE_INT hwi_nit
;
1943 if (!get_max_loop_iterations (loop
, &nit
))
1946 if (!wi::fits_shwi_p (nit
))
1948 hwi_nit
= nit
.to_shwi ();
1950 return hwi_nit
< 0 ? -1 : hwi_nit
;
1953 /* Sets NIT to an upper bound for the maximum number of executions of the
1954 latch of the LOOP. If we have no reliable estimate, the function returns
1955 false, otherwise returns true. */
1958 get_likely_max_loop_iterations (struct loop
*loop
, widest_int
*nit
)
1960 if (!loop
->any_likely_upper_bound
)
1963 *nit
= loop
->nb_iterations_likely_upper_bound
;
1967 /* Similar to get_max_loop_iterations, but returns the estimate only
1968 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1969 on the number of iterations of LOOP could not be derived, returns -1. */
1972 get_likely_max_loop_iterations_int (struct loop
*loop
)
1975 HOST_WIDE_INT hwi_nit
;
1977 if (!get_likely_max_loop_iterations (loop
, &nit
))
1980 if (!wi::fits_shwi_p (nit
))
1982 hwi_nit
= nit
.to_shwi ();
1984 return hwi_nit
< 0 ? -1 : hwi_nit
;
1987 /* Returns the loop depth of the loop BB belongs to. */
1990 bb_loop_depth (const_basic_block bb
)
1992 return bb
->loop_father
? loop_depth (bb
->loop_father
) : 0;
1995 /* Marks LOOP for removal and sets LOOPS_NEED_FIXUP. */
1998 mark_loop_for_removal (loop_p loop
)
2000 if (loop
->header
== NULL
)
2002 loop
->former_header
= loop
->header
;
2003 loop
->header
= NULL
;
2005 loops_state_set (LOOPS_NEED_FIXUP
);