1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000-2021 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 class loop
*outer
, const class 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 (class 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 class 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 class loop
*loop
, FILE *file
,
109 void (*loop_dump_aux
) (const class 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: %" PRIu64
"\n",
148 fprintf (file
, ";; nodes:");
149 bbs
= get_loop_body (loop
);
150 for (i
= 0; i
< loop
->num_nodes
; i
++)
151 fprintf (file
, " %d", bbs
[i
]->index
);
153 fprintf (file
, "\n");
156 loop_dump_aux (loop
, file
, verbose
);
159 /* Dump the loop information about loops to the stream FILE,
160 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
163 flow_loops_dump (FILE *file
, void (*loop_dump_aux
) (const class loop
*, FILE *, int), int verbose
)
165 if (!current_loops
|| ! file
)
168 fprintf (file
, ";; %d loops found\n", number_of_loops (cfun
));
170 for (auto loop
: loops_list (cfun
, LI_INCLUDE_ROOT
))
172 flow_loop_dump (loop
, file
, loop_dump_aux
, verbose
);
176 flow_loops_cfg_dump (file
);
179 /* Free data allocated for LOOP. */
182 flow_loop_free (class loop
*loop
)
184 struct loop_exit
*exit
, *next
;
186 vec_free (loop
->superloops
);
188 /* Break the list of the loop exit records. They will be freed when the
189 corresponding edge is rescanned or removed, and this avoids
190 accessing the (already released) head of the list stored in the
192 for (exit
= loop
->exits
->next
; exit
!= loop
->exits
; exit
= next
)
199 ggc_free (loop
->exits
);
203 /* Free all the memory allocated for LOOPS. */
206 flow_loops_free (struct loops
*loops
)
213 /* Free the loop descriptors. */
214 FOR_EACH_VEC_SAFE_ELT (loops
->larray
, i
, loop
)
219 flow_loop_free (loop
);
222 vec_free (loops
->larray
);
226 /* Find the nodes contained within the LOOP with header HEADER.
227 Return the number of nodes within the loop. */
230 flow_loop_nodes_find (basic_block header
, class loop
*loop
)
232 vec
<basic_block
> stack
= vNULL
;
235 edge_iterator latch_ei
;
237 header
->loop_father
= loop
;
239 FOR_EACH_EDGE (latch
, latch_ei
, loop
->header
->preds
)
241 if (latch
->src
->loop_father
== loop
242 || !dominated_by_p (CDI_DOMINATORS
, latch
->src
, loop
->header
))
246 stack
.safe_push (latch
->src
);
247 latch
->src
->loop_father
= loop
;
249 while (!stack
.is_empty ())
257 FOR_EACH_EDGE (e
, ei
, node
->preds
)
259 basic_block ancestor
= e
->src
;
261 if (ancestor
->loop_father
!= loop
)
263 ancestor
->loop_father
= loop
;
265 stack
.safe_push (ancestor
);
275 /* Records the vector of superloops of the loop LOOP, whose immediate
276 superloop is FATHER. */
279 establish_preds (class loop
*loop
, class loop
*father
)
282 unsigned depth
= loop_depth (father
) + 1;
285 loop
->superloops
= 0;
286 vec_alloc (loop
->superloops
, depth
);
287 FOR_EACH_VEC_SAFE_ELT (father
->superloops
, i
, ploop
)
288 loop
->superloops
->quick_push (ploop
);
289 loop
->superloops
->quick_push (father
);
291 for (ploop
= loop
->inner
; ploop
; ploop
= ploop
->next
)
292 establish_preds (ploop
, loop
);
295 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
296 added loop. If LOOP has some children, take care of that their
297 pred field will be initialized correctly. If AFTER is non-null
298 then it's expected it's a pointer into FATHERs inner sibling
299 list and LOOP is added behind AFTER, otherwise it's added in front
300 of FATHERs siblings. */
303 flow_loop_tree_node_add (class loop
*father
, class loop
*loop
,
308 loop
->next
= after
->next
;
313 loop
->next
= father
->inner
;
314 father
->inner
= loop
;
317 establish_preds (loop
, father
);
320 /* Remove LOOP from the loop hierarchy tree. */
323 flow_loop_tree_node_remove (class loop
*loop
)
325 class loop
*prev
, *father
;
327 father
= loop_outer (loop
);
329 /* Remove loop from the list of sons. */
330 if (father
->inner
== loop
)
331 father
->inner
= loop
->next
;
334 for (prev
= father
->inner
; prev
->next
!= loop
; prev
= prev
->next
)
336 prev
->next
= loop
->next
;
339 loop
->superloops
= NULL
;
342 /* Allocates and returns new loop structure. */
347 class loop
*loop
= ggc_cleared_alloc
<class loop
> ();
349 loop
->exits
= ggc_cleared_alloc
<loop_exit
> ();
350 loop
->exits
->next
= loop
->exits
->prev
= loop
->exits
;
351 loop
->can_be_parallel
= false;
352 loop
->constraints
= 0;
353 loop
->nb_iterations_upper_bound
= 0;
354 loop
->nb_iterations_likely_upper_bound
= 0;
355 loop
->nb_iterations_estimate
= 0;
359 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
360 (including the root of the loop tree). */
363 init_loops_structure (struct function
*fn
,
364 struct loops
*loops
, unsigned num_loops
)
368 memset (loops
, 0, sizeof *loops
);
369 vec_alloc (loops
->larray
, num_loops
);
371 /* Dummy loop containing whole function. */
372 root
= alloc_loop ();
373 root
->num_nodes
= n_basic_blocks_for_fn (fn
);
374 root
->latch
= EXIT_BLOCK_PTR_FOR_FN (fn
);
375 root
->header
= ENTRY_BLOCK_PTR_FOR_FN (fn
);
376 ENTRY_BLOCK_PTR_FOR_FN (fn
)->loop_father
= root
;
377 EXIT_BLOCK_PTR_FOR_FN (fn
)->loop_father
= root
;
379 loops
->larray
->quick_push (root
);
380 loops
->tree_root
= root
;
383 /* Returns whether HEADER is a loop header. */
386 bb_loop_header_p (basic_block header
)
391 /* If we have an abnormal predecessor, do not consider the
392 loop (not worth the problems). */
393 if (bb_has_abnormal_pred (header
))
396 /* Look for back edges where a predecessor is dominated
397 by this block. A natural loop has a single entry
398 node (header) that dominates all the nodes in the
399 loop. It also has single back edge to the header
400 from a latch node. */
401 FOR_EACH_EDGE (e
, ei
, header
->preds
)
403 basic_block latch
= e
->src
;
404 if (latch
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
405 && dominated_by_p (CDI_DOMINATORS
, latch
, header
))
412 /* Find all the natural loops in the function and save in LOOPS structure and
413 recalculate loop_father information in basic block structures.
414 If LOOPS is non-NULL then the loop structures for already recorded loops
415 will be re-used and their number will not change. We assume that no
416 stale loops exist in LOOPS.
417 When LOOPS is NULL it is allocated and re-built from scratch.
418 Return the built LOOPS structure. */
421 flow_loops_find (struct loops
*loops
)
423 bool from_scratch
= (loops
== NULL
);
428 /* Ensure that the dominators are computed. */
429 calculate_dominance_info (CDI_DOMINATORS
);
433 loops
= ggc_cleared_alloc
<struct loops
> ();
434 init_loops_structure (cfun
, loops
, 1);
437 /* Ensure that loop exits were released. */
438 gcc_assert (loops
->exits
== NULL
);
440 /* Taking care of this degenerate case makes the rest of
441 this code simpler. */
442 if (n_basic_blocks_for_fn (cfun
) == NUM_FIXED_BLOCKS
)
445 /* The root loop node contains all basic-blocks. */
446 loops
->tree_root
->num_nodes
= n_basic_blocks_for_fn (cfun
);
448 /* Compute depth first search order of the CFG so that outer
449 natural loops will be found before inner natural loops. */
450 rc_order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
451 pre_and_rev_post_order_compute (NULL
, rc_order
, false);
453 /* Gather all loop headers in reverse completion order and allocate
454 loop structures for loops that are not already present. */
455 auto_vec
<loop_p
> larray (loops
->larray
->length ());
456 for (b
= 0; b
< n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
; b
++)
458 basic_block header
= BASIC_BLOCK_FOR_FN (cfun
, rc_order
[b
]);
459 if (bb_loop_header_p (header
))
463 /* The current active loop tree has valid loop-fathers for
466 && header
->loop_father
->header
== header
)
468 loop
= header
->loop_father
;
469 /* If we found an existing loop remove it from the
470 loop tree. It is going to be inserted again
472 flow_loop_tree_node_remove (loop
);
476 /* Otherwise allocate a new loop structure for the loop. */
477 loop
= alloc_loop ();
478 /* ??? We could re-use unused loop slots here. */
479 loop
->num
= loops
->larray
->length ();
480 vec_safe_push (loops
->larray
, loop
);
481 loop
->header
= header
;
484 && dump_file
&& (dump_flags
& TDF_DETAILS
))
485 fprintf (dump_file
, "flow_loops_find: discovered new "
486 "loop %d with header %d\n",
487 loop
->num
, header
->index
);
489 /* Reset latch, we recompute it below. */
491 larray
.safe_push (loop
);
494 /* Make blocks part of the loop root node at start. */
495 header
->loop_father
= loops
->tree_root
;
500 /* Now iterate over the loops found, insert them into the loop tree
501 and assign basic-block ownership. */
502 for (i
= 0; i
< larray
.length (); ++i
)
504 class loop
*loop
= larray
[i
];
505 basic_block header
= loop
->header
;
509 flow_loop_tree_node_add (header
->loop_father
, loop
);
510 loop
->num_nodes
= flow_loop_nodes_find (loop
->header
, loop
);
512 /* Look for the latch for this header block, if it has just a
514 FOR_EACH_EDGE (e
, ei
, header
->preds
)
516 basic_block latch
= e
->src
;
518 if (flow_bb_inside_loop_p (loop
, latch
))
520 if (loop
->latch
!= NULL
)
522 /* More than one latch edge. */
534 /* qsort helper for sort_sibling_loops. */
536 static int *sort_sibling_loops_cmp_rpo
;
538 sort_sibling_loops_cmp (const void *la_
, const void *lb_
)
540 const class loop
*la
= *(const class loop
* const *)la_
;
541 const class loop
*lb
= *(const class loop
* const *)lb_
;
542 return (sort_sibling_loops_cmp_rpo
[la
->header
->index
]
543 - sort_sibling_loops_cmp_rpo
[lb
->header
->index
]);
546 /* Sort sibling loops in RPO order. */
549 sort_sibling_loops (function
*fn
)
551 /* Match flow_loops_find in the order we sort sibling loops. */
552 sort_sibling_loops_cmp_rpo
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
553 int *rc_order
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
));
554 pre_and_rev_post_order_compute_fn (fn
, NULL
, rc_order
, false);
555 for (int i
= 0; i
< n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
; ++i
)
556 sort_sibling_loops_cmp_rpo
[rc_order
[i
]] = i
;
559 auto_vec
<loop_p
, 3> siblings
;
560 for (auto loop
: loops_list (fn
, LI_INCLUDE_ROOT
))
561 if (loop
->inner
&& loop
->inner
->next
)
563 loop_p sibling
= loop
->inner
;
566 siblings
.safe_push (sibling
);
567 sibling
= sibling
->next
;
570 siblings
.qsort (sort_sibling_loops_cmp
);
571 loop_p
*siblingp
= &loop
->inner
;
572 for (unsigned i
= 0; i
< siblings
.length (); ++i
)
574 *siblingp
= siblings
[i
];
575 siblingp
= &(*siblingp
)->next
;
578 siblings
.truncate (0);
581 free (sort_sibling_loops_cmp_rpo
);
582 sort_sibling_loops_cmp_rpo
= NULL
;
585 /* Ratio of frequencies of edges so that one of more latch edges is
586 considered to belong to inner loop with same header. */
587 #define HEAVY_EDGE_RATIO 8
589 /* Minimum number of samples for that we apply
590 find_subloop_latch_edge_by_profile heuristics. */
591 #define HEAVY_EDGE_MIN_SAMPLES 10
593 /* If the profile info is available, finds an edge in LATCHES that much more
594 frequent than the remaining edges. Returns such an edge, or NULL if we do
597 We do not use guessed profile here, only the measured one. The guessed
598 profile is usually too flat and unreliable for this (and it is mostly based
599 on the loop structure of the program, so it does not make much sense to
600 derive the loop structure from it). */
603 find_subloop_latch_edge_by_profile (vec
<edge
> latches
)
607 profile_count mcount
= profile_count::zero (), tcount
= profile_count::zero ();
609 FOR_EACH_VEC_ELT (latches
, i
, e
)
611 if (e
->count ()> mcount
)
616 tcount
+= e
->count();
619 if (!tcount
.initialized_p () || !(tcount
.ipa () > HEAVY_EDGE_MIN_SAMPLES
)
620 || (tcount
- mcount
).apply_scale (HEAVY_EDGE_RATIO
, 1) > tcount
)
625 "Found latch edge %d -> %d using profile information.\n",
626 me
->src
->index
, me
->dest
->index
);
630 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
631 on the structure of induction variables. Returns this edge, or NULL if we
634 We are quite conservative, and look just for an obvious simple innermost
635 loop (which is the case where we would lose the most performance by not
636 disambiguating the loop). More precisely, we look for the following
637 situation: The source of the chosen latch edge dominates sources of all
638 the other latch edges. Additionally, the header does not contain a phi node
639 such that the argument from the chosen edge is equal to the argument from
643 find_subloop_latch_edge_by_ivs (class loop
*loop ATTRIBUTE_UNUSED
, vec
<edge
> latches
)
645 edge e
, latch
= latches
[0];
652 /* Find the candidate for the latch edge. */
653 for (i
= 1; latches
.iterate (i
, &e
); i
++)
654 if (dominated_by_p (CDI_DOMINATORS
, latch
->src
, e
->src
))
657 /* Verify that it dominates all the latch edges. */
658 FOR_EACH_VEC_ELT (latches
, i
, e
)
659 if (!dominated_by_p (CDI_DOMINATORS
, e
->src
, latch
->src
))
662 /* Check for a phi node that would deny that this is a latch edge of
664 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); gsi_next (&psi
))
667 lop
= PHI_ARG_DEF_FROM_EDGE (phi
, latch
);
669 /* Ignore the values that are not changed inside the subloop. */
670 if (TREE_CODE (lop
) != SSA_NAME
671 || SSA_NAME_DEF_STMT (lop
) == phi
)
673 bb
= gimple_bb (SSA_NAME_DEF_STMT (lop
));
674 if (!bb
|| !flow_bb_inside_loop_p (loop
, bb
))
677 FOR_EACH_VEC_ELT (latches
, i
, e
)
679 && PHI_ARG_DEF_FROM_EDGE (phi
, e
) == lop
)
685 "Found latch edge %d -> %d using iv structure.\n",
686 latch
->src
->index
, latch
->dest
->index
);
690 /* If we can determine that one of the several latch edges of LOOP behaves
691 as a latch edge of a separate subloop, returns this edge. Otherwise
695 find_subloop_latch_edge (class loop
*loop
)
697 vec
<edge
> latches
= get_loop_latch_edges (loop
);
700 if (latches
.length () > 1)
702 latch
= find_subloop_latch_edge_by_profile (latches
);
705 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
706 should use cfghook for this, but it is hard to imagine it would
707 be useful elsewhere. */
708 && current_ir_type () == IR_GIMPLE
)
709 latch
= find_subloop_latch_edge_by_ivs (loop
, latches
);
716 /* Callback for make_forwarder_block. Returns true if the edge E is marked
717 in the set MFB_REIS_SET. */
719 static hash_set
<edge
> *mfb_reis_set
;
721 mfb_redirect_edges_in_set (edge e
)
723 return mfb_reis_set
->contains (e
);
726 /* Creates a subloop of LOOP with latch edge LATCH. */
729 form_subloop (class loop
*loop
, edge latch
)
733 class loop
*new_loop
;
735 mfb_reis_set
= new hash_set
<edge
>;
736 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
739 mfb_reis_set
->add (e
);
741 new_entry
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
745 loop
->header
= new_entry
->src
;
747 /* Find the blocks and subloops that belong to the new loop, and add it to
748 the appropriate place in the loop tree. */
749 new_loop
= alloc_loop ();
750 new_loop
->header
= new_entry
->dest
;
751 new_loop
->latch
= latch
->src
;
752 add_loop (new_loop
, loop
);
755 /* Make all the latch edges of LOOP to go to a single forwarder block --
756 a new latch of LOOP. */
759 merge_latch_edges (class loop
*loop
)
761 vec
<edge
> latches
= get_loop_latch_edges (loop
);
765 gcc_assert (latches
.length () > 0);
767 if (latches
.length () == 1)
768 loop
->latch
= latches
[0]->src
;
772 fprintf (dump_file
, "Merged latch edges of loop %d\n", loop
->num
);
774 mfb_reis_set
= new hash_set
<edge
>;
775 FOR_EACH_VEC_ELT (latches
, i
, e
)
776 mfb_reis_set
->add (e
);
777 latch
= make_forwarder_block (loop
->header
, mfb_redirect_edges_in_set
,
781 loop
->header
= latch
->dest
;
782 loop
->latch
= latch
->src
;
788 /* LOOP may have several latch edges. Transform it into (possibly several)
789 loops with single latch edge. */
792 disambiguate_multiple_latches (class loop
*loop
)
796 /* We eliminate the multiple latches by splitting the header to the forwarder
797 block F and the rest R, and redirecting the edges. There are two cases:
799 1) If there is a latch edge E that corresponds to a subloop (we guess
800 that based on profile -- if it is taken much more often than the
801 remaining edges; and on trees, using the information about induction
802 variables of the loops), we redirect E to R, all the remaining edges to
803 F, then rescan the loops and try again for the outer loop.
804 2) If there is no such edge, we redirect all latch edges to F, and the
805 entry edges to R, thus making F the single latch of the loop. */
808 fprintf (dump_file
, "Disambiguating loop %d with multiple latches\n",
811 /* During latch merging, we may need to redirect the entry edges to a new
812 block. This would cause problems if the entry edge was the one from the
813 entry block. To avoid having to handle this case specially, split
815 e
= find_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
), loop
->header
);
821 e
= find_subloop_latch_edge (loop
);
825 form_subloop (loop
, e
);
828 merge_latch_edges (loop
);
831 /* Split loops with multiple latch edges. */
834 disambiguate_loops_with_multiple_latches (void)
836 for (auto loop
: loops_list (cfun
, 0))
839 disambiguate_multiple_latches (loop
);
843 /* Return nonzero if basic block BB belongs to LOOP. */
845 flow_bb_inside_loop_p (const class loop
*loop
, const_basic_block bb
)
847 class loop
*source_loop
;
849 if (bb
== ENTRY_BLOCK_PTR_FOR_FN (cfun
)
850 || bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
853 source_loop
= bb
->loop_father
;
854 return loop
== source_loop
|| flow_loop_nested_p (loop
, source_loop
);
857 /* Enumeration predicate for get_loop_body_with_size. */
859 glb_enum_p (const_basic_block bb
, const void *glb_loop
)
861 const class loop
*const loop
= (const class loop
*) glb_loop
;
862 return (bb
!= loop
->header
863 && dominated_by_p (CDI_DOMINATORS
, bb
, loop
->header
));
866 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
867 order against direction of edges from latch. Specially, if
868 header != latch, latch is the 1-st block. LOOP cannot be the fake
869 loop tree root, and its size must be at most MAX_SIZE. The blocks
870 in the LOOP body are stored to BODY, and the size of the LOOP is
874 get_loop_body_with_size (const class loop
*loop
, basic_block
*body
,
877 return dfs_enumerate_from (loop
->header
, 1, glb_enum_p
,
878 body
, max_size
, loop
);
881 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
882 order against direction of edges from latch. Specially, if
883 header != latch, latch is the 1-st block. */
886 get_loop_body (const class loop
*loop
)
888 basic_block
*body
, bb
;
891 gcc_assert (loop
->num_nodes
);
893 body
= XNEWVEC (basic_block
, loop
->num_nodes
);
895 if (loop
->latch
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
897 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
898 special-case the fake loop that contains the whole function. */
899 gcc_assert (loop
->num_nodes
== (unsigned) n_basic_blocks_for_fn (cfun
));
900 body
[tv
++] = loop
->header
;
901 body
[tv
++] = EXIT_BLOCK_PTR_FOR_FN (cfun
);
902 FOR_EACH_BB_FN (bb
, cfun
)
906 tv
= get_loop_body_with_size (loop
, body
, loop
->num_nodes
);
908 gcc_assert (tv
== loop
->num_nodes
);
912 /* Fills dominance descendants inside LOOP of the basic block BB into
913 array TOVISIT from index *TV. */
916 fill_sons_in_loop (const class loop
*loop
, basic_block bb
,
917 basic_block
*tovisit
, int *tv
)
919 basic_block son
, postpone
= NULL
;
921 tovisit
[(*tv
)++] = bb
;
922 for (son
= first_dom_son (CDI_DOMINATORS
, bb
);
924 son
= next_dom_son (CDI_DOMINATORS
, son
))
926 if (!flow_bb_inside_loop_p (loop
, son
))
929 if (dominated_by_p (CDI_DOMINATORS
, loop
->latch
, son
))
934 fill_sons_in_loop (loop
, son
, tovisit
, tv
);
938 fill_sons_in_loop (loop
, postpone
, tovisit
, tv
);
941 /* Gets body of a LOOP (that must be different from the outermost loop)
942 sorted by dominance relation. Additionally, if a basic block s dominates
943 the latch, then only blocks dominated by s are be after it. */
946 get_loop_body_in_dom_order (const class loop
*loop
)
948 basic_block
*tovisit
;
951 gcc_assert (loop
->num_nodes
);
953 tovisit
= XNEWVEC (basic_block
, loop
->num_nodes
);
955 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
958 fill_sons_in_loop (loop
, loop
->header
, tovisit
, &tv
);
960 gcc_assert (tv
== (int) loop
->num_nodes
);
965 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
968 get_loop_body_in_custom_order (const class loop
*loop
,
969 int (*bb_comparator
) (const void *, const void *))
971 basic_block
*bbs
= get_loop_body (loop
);
973 qsort (bbs
, loop
->num_nodes
, sizeof (basic_block
), bb_comparator
);
978 /* Same as above, but use gcc_sort_r instead of qsort. */
981 get_loop_body_in_custom_order (const class loop
*loop
, void *data
,
982 int (*bb_comparator
) (const void *, const void *, void *))
984 basic_block
*bbs
= get_loop_body (loop
);
986 gcc_sort_r (bbs
, loop
->num_nodes
, sizeof (basic_block
), bb_comparator
, data
);
991 /* Get body of a LOOP in breadth first sort order. */
994 get_loop_body_in_bfs_order (const class loop
*loop
)
1001 gcc_assert (loop
->num_nodes
);
1002 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1004 blocks
= XNEWVEC (basic_block
, loop
->num_nodes
);
1005 auto_bitmap visited
;
1006 blocks
[0] = loop
->header
;
1007 bitmap_set_bit (visited
, loop
->header
->index
);
1008 while (i
< loop
->num_nodes
)
1012 gcc_assert (i
> vc
);
1015 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1017 if (flow_bb_inside_loop_p (loop
, e
->dest
))
1019 /* This bb is now visited. */
1020 if (bitmap_set_bit (visited
, e
->dest
->index
))
1021 blocks
[i
++] = e
->dest
;
1029 /* Hash function for struct loop_exit. */
1032 loop_exit_hasher::hash (loop_exit
*exit
)
1034 return htab_hash_pointer (exit
->e
);
1037 /* Equality function for struct loop_exit. Compares with edge. */
1040 loop_exit_hasher::equal (loop_exit
*exit
, edge e
)
1042 return exit
->e
== e
;
1045 /* Frees the list of loop exit descriptions EX. */
1048 loop_exit_hasher::remove (loop_exit
*exit
)
1051 for (; exit
; exit
= next
)
1053 next
= exit
->next_e
;
1055 exit
->next
->prev
= exit
->prev
;
1056 exit
->prev
->next
= exit
->next
;
1062 /* Returns the list of records for E as an exit of a loop. */
1064 static struct loop_exit
*
1065 get_exit_descriptions (edge e
)
1067 return current_loops
->exits
->find_with_hash (e
, htab_hash_pointer (e
));
1070 /* Updates the lists of loop exits in that E appears.
1071 If REMOVED is true, E is being removed, and we
1072 just remove it from the lists of exits.
1073 If NEW_EDGE is true and E is not a loop exit, we
1074 do not try to remove it from loop exit lists. */
1077 rescan_loop_exit (edge e
, bool new_edge
, bool removed
)
1079 struct loop_exit
*exits
= NULL
, *exit
;
1080 class loop
*aloop
, *cloop
;
1082 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1086 && e
->src
->loop_father
!= NULL
1087 && e
->dest
->loop_father
!= NULL
1088 && !flow_bb_inside_loop_p (e
->src
->loop_father
, e
->dest
))
1090 cloop
= find_common_loop (e
->src
->loop_father
, e
->dest
->loop_father
);
1091 for (aloop
= e
->src
->loop_father
;
1093 aloop
= loop_outer (aloop
))
1095 exit
= ggc_alloc
<loop_exit
> ();
1098 exit
->next
= aloop
->exits
->next
;
1099 exit
->prev
= aloop
->exits
;
1100 exit
->next
->prev
= exit
;
1101 exit
->prev
->next
= exit
;
1103 exit
->next_e
= exits
;
1108 if (!exits
&& new_edge
)
1112 = current_loops
->exits
->find_slot_with_hash (e
, htab_hash_pointer (e
),
1113 exits
? INSERT
: NO_INSERT
);
1120 loop_exit_hasher::remove (*slot
);
1124 current_loops
->exits
->clear_slot (slot
);
1127 /* For each loop, record list of exit edges, and start maintaining these
1131 record_loop_exits (void)
1140 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1142 loops_state_set (LOOPS_HAVE_RECORDED_EXITS
);
1144 gcc_assert (current_loops
->exits
== NULL
);
1145 current_loops
->exits
1146 = hash_table
<loop_exit_hasher
>::create_ggc (2 * number_of_loops (cfun
));
1148 FOR_EACH_BB_FN (bb
, cfun
)
1150 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1152 rescan_loop_exit (e
, true, false);
1157 /* Dumps information about the exit in *SLOT to FILE.
1158 Callback for htab_traverse. */
1161 dump_recorded_exit (loop_exit
**slot
, FILE *file
)
1163 struct loop_exit
*exit
= *slot
;
1167 for (; exit
!= NULL
; exit
= exit
->next_e
)
1170 fprintf (file
, "Edge %d->%d exits %u loops\n",
1171 e
->src
->index
, e
->dest
->index
, n
);
1176 /* Dumps the recorded exits of loops to FILE. */
1178 extern void dump_recorded_exits (FILE *);
1180 dump_recorded_exits (FILE *file
)
1182 if (!current_loops
->exits
)
1184 current_loops
->exits
->traverse
<FILE *, dump_recorded_exit
> (file
);
1187 /* Releases lists of loop exits. */
1190 release_recorded_exits (function
*fn
)
1192 gcc_assert (loops_state_satisfies_p (fn
, LOOPS_HAVE_RECORDED_EXITS
));
1193 loops_for_fn (fn
)->exits
->empty ();
1194 loops_for_fn (fn
)->exits
= NULL
;
1195 loops_state_clear (fn
, LOOPS_HAVE_RECORDED_EXITS
);
1198 /* Returns the list of the exit edges of a LOOP. */
1201 get_loop_exit_edges (const class loop
*loop
, basic_block
*body
)
1203 auto_vec
<edge
> edges
;
1207 struct loop_exit
*exit
;
1209 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1211 /* If we maintain the lists of exits, use them. Otherwise we must
1212 scan the body of the loop. */
1213 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1215 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1216 edges
.safe_push (exit
->e
);
1220 bool body_from_caller
= true;
1223 body
= get_loop_body (loop
);
1224 body_from_caller
= false;
1226 for (i
= 0; i
< loop
->num_nodes
; i
++)
1227 FOR_EACH_EDGE (e
, ei
, body
[i
]->succs
)
1229 if (!flow_bb_inside_loop_p (loop
, e
->dest
))
1230 edges
.safe_push (e
);
1232 if (!body_from_caller
)
1239 /* Counts the number of conditional branches inside LOOP. */
1242 num_loop_branches (const class loop
*loop
)
1247 gcc_assert (loop
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
1249 body
= get_loop_body (loop
);
1251 for (i
= 0; i
< loop
->num_nodes
; i
++)
1252 if (EDGE_COUNT (body
[i
]->succs
) >= 2)
1259 /* Adds basic block BB to LOOP. */
1261 add_bb_to_loop (basic_block bb
, class loop
*loop
)
1268 gcc_assert (bb
->loop_father
== NULL
);
1269 bb
->loop_father
= loop
;
1271 FOR_EACH_VEC_SAFE_ELT (loop
->superloops
, i
, ploop
)
1274 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1276 rescan_loop_exit (e
, true, false);
1278 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1280 rescan_loop_exit (e
, true, false);
1284 /* Remove basic block BB from loops. */
1286 remove_bb_from_loops (basic_block bb
)
1289 class loop
*loop
= bb
->loop_father
;
1294 gcc_assert (loop
!= NULL
);
1296 FOR_EACH_VEC_SAFE_ELT (loop
->superloops
, i
, ploop
)
1298 bb
->loop_father
= NULL
;
1300 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1302 rescan_loop_exit (e
, false, true);
1304 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1306 rescan_loop_exit (e
, false, true);
1310 /* Finds nearest common ancestor in loop tree for given loops. */
1312 find_common_loop (class loop
*loop_s
, class loop
*loop_d
)
1314 unsigned sdepth
, ddepth
;
1316 if (!loop_s
) return loop_d
;
1317 if (!loop_d
) return loop_s
;
1319 sdepth
= loop_depth (loop_s
);
1320 ddepth
= loop_depth (loop_d
);
1322 if (sdepth
< ddepth
)
1323 loop_d
= (*loop_d
->superloops
)[sdepth
];
1324 else if (sdepth
> ddepth
)
1325 loop_s
= (*loop_s
->superloops
)[ddepth
];
1327 while (loop_s
!= loop_d
)
1329 loop_s
= loop_outer (loop_s
);
1330 loop_d
= loop_outer (loop_d
);
1335 /* Removes LOOP from structures and frees its data. */
1338 delete_loop (class loop
*loop
)
1340 /* Remove the loop from structure. */
1341 flow_loop_tree_node_remove (loop
);
1343 /* Remove loop from loops array. */
1344 (*current_loops
->larray
)[loop
->num
] = NULL
;
1346 /* Free loop data. */
1347 flow_loop_free (loop
);
1350 /* Cancels the LOOP; it must be innermost one. */
1353 cancel_loop (class loop
*loop
)
1357 class loop
*outer
= loop_outer (loop
);
1359 gcc_assert (!loop
->inner
);
1361 /* Move blocks up one level (they should be removed as soon as possible). */
1362 bbs
= get_loop_body (loop
);
1363 for (i
= 0; i
< loop
->num_nodes
; i
++)
1364 bbs
[i
]->loop_father
= outer
;
1370 /* Cancels LOOP and all its subloops. */
1372 cancel_loop_tree (class loop
*loop
)
1375 cancel_loop_tree (loop
->inner
);
1379 /* Disable warnings about missing quoting in GCC diagnostics for
1380 the verification errors. Their format strings don't follow GCC
1381 diagnostic conventions and the calls are ultimately followed by
1382 a deliberate ICE triggered by a failed assertion. */
1384 # pragma GCC diagnostic push
1385 # pragma GCC diagnostic ignored "-Wformat-diag"
1388 /* Checks that information about loops is correct
1389 -- sizes of loops are all right
1390 -- results of get_loop_body really belong to the loop
1391 -- loop header have just single entry edge and single latch edge
1392 -- loop latches have only single successor that is header of their loop
1393 -- irreducible loops are correctly marked
1394 -- the cached loop depth and loop father of each bb is correct
1397 verify_loop_structure (void)
1399 unsigned *sizes
, i
, j
;
1400 basic_block bb
, *bbs
;
1404 unsigned num
= number_of_loops (cfun
);
1405 struct loop_exit
*exit
, *mexit
;
1406 bool dom_available
= dom_info_available_p (CDI_DOMINATORS
);
1408 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
1410 error ("loop verification on loop tree that needs fixup");
1414 /* We need up-to-date dominators, compute or verify them. */
1416 calculate_dominance_info (CDI_DOMINATORS
);
1418 verify_dominators (CDI_DOMINATORS
);
1420 /* Check the loop tree root. */
1421 if (current_loops
->tree_root
->header
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1422 || current_loops
->tree_root
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1423 || (current_loops
->tree_root
->num_nodes
1424 != (unsigned) n_basic_blocks_for_fn (cfun
)))
1426 error ("corrupt loop tree root");
1430 /* Check the headers. */
1431 FOR_EACH_BB_FN (bb
, cfun
)
1432 if (bb_loop_header_p (bb
))
1434 if (bb
->loop_father
->header
== NULL
)
1436 error ("loop with header %d marked for removal", bb
->index
);
1439 else if (bb
->loop_father
->header
!= bb
)
1441 error ("loop with header %d not in loop tree", bb
->index
);
1445 else if (bb
->loop_father
->header
== bb
)
1447 error ("non-loop with header %d not marked for removal", bb
->index
);
1451 /* Check the recorded loop father and sizes of loops. */
1452 auto_sbitmap
visited (last_basic_block_for_fn (cfun
));
1453 bitmap_clear (visited
);
1454 bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
1455 for (auto loop
: loops_list (cfun
, LI_FROM_INNERMOST
))
1459 if (loop
->header
== NULL
)
1461 error ("removed loop %d in loop tree", loop
->num
);
1466 n
= get_loop_body_with_size (loop
, bbs
, n_basic_blocks_for_fn (cfun
));
1467 if (loop
->num_nodes
!= n
)
1469 error ("size of loop %d should be %d, not %d",
1470 loop
->num
, n
, loop
->num_nodes
);
1474 for (j
= 0; j
< n
; j
++)
1478 if (!flow_bb_inside_loop_p (loop
, bb
))
1480 error ("bb %d does not belong to loop %d",
1481 bb
->index
, loop
->num
);
1485 /* Ignore this block if it is in an inner loop. */
1486 if (bitmap_bit_p (visited
, bb
->index
))
1488 bitmap_set_bit (visited
, bb
->index
);
1490 if (bb
->loop_father
!= loop
)
1492 error ("bb %d has father loop %d, should be loop %d",
1493 bb
->index
, bb
->loop_father
->num
, loop
->num
);
1500 /* Check headers and latches. */
1501 for (auto loop
: loops_list (cfun
, 0))
1504 if (loop
->header
== NULL
)
1506 if (!bb_loop_header_p (loop
->header
))
1508 error ("loop %d%'s header is not a loop header", i
);
1511 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
)
1512 && EDGE_COUNT (loop
->header
->preds
) != 2)
1514 error ("loop %d%'s header does not have exactly 2 entries", i
);
1519 if (!find_edge (loop
->latch
, loop
->header
))
1521 error ("loop %d%'s latch does not have an edge to its header", i
);
1524 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, loop
->header
))
1526 error ("loop %d%'s latch is not dominated by its header", i
);
1530 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
1532 if (!single_succ_p (loop
->latch
))
1534 error ("loop %d%'s latch does not have exactly 1 successor", i
);
1537 if (single_succ (loop
->latch
) != loop
->header
)
1539 error ("loop %d%'s latch does not have header as successor", i
);
1542 if (loop
->latch
->loop_father
!= loop
)
1544 error ("loop %d%'s latch does not belong directly to it", i
);
1548 if (loop
->header
->loop_father
!= loop
)
1550 error ("loop %d%'s header does not belong directly to it", i
);
1553 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1556 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1557 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, loop
->header
)
1558 && e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1560 error ("loop %d%'s latch is marked as part of irreducible"
1567 /* Check irreducible loops. */
1568 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1570 auto_edge_flag
saved_irr_mask (cfun
);
1571 /* Record old info. */
1572 auto_sbitmap
irreds (last_basic_block_for_fn (cfun
));
1573 FOR_EACH_BB_FN (bb
, cfun
)
1576 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1577 bitmap_set_bit (irreds
, bb
->index
);
1579 bitmap_clear_bit (irreds
, bb
->index
);
1580 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1581 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1582 e
->flags
|= saved_irr_mask
;
1586 mark_irreducible_loops ();
1589 FOR_EACH_BB_FN (bb
, cfun
)
1593 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1594 && !bitmap_bit_p (irreds
, bb
->index
))
1596 error ("basic block %d should be marked irreducible", bb
->index
);
1599 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1600 && bitmap_bit_p (irreds
, bb
->index
))
1602 error ("basic block %d should not be marked irreducible", bb
->index
);
1605 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1607 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1608 && !(e
->flags
& saved_irr_mask
))
1610 error ("edge from %d to %d should be marked irreducible",
1611 e
->src
->index
, e
->dest
->index
);
1614 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1615 && (e
->flags
& saved_irr_mask
))
1617 error ("edge from %d to %d should not be marked irreducible",
1618 e
->src
->index
, e
->dest
->index
);
1621 e
->flags
&= ~saved_irr_mask
;
1626 /* Check the recorded loop exits. */
1627 for (auto loop
: loops_list (cfun
, 0))
1629 if (!loop
->exits
|| loop
->exits
->e
!= NULL
)
1631 error ("corrupted head of the exits list of loop %d",
1637 /* Check that the list forms a cycle, and all elements except
1638 for the head are nonnull. */
1639 for (mexit
= loop
->exits
, exit
= mexit
->next
, i
= 0;
1640 exit
->e
&& exit
!= mexit
;
1644 mexit
= mexit
->next
;
1647 if (exit
!= loop
->exits
)
1649 error ("corrupted exits list of loop %d", loop
->num
);
1654 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1656 if (loop
->exits
->next
!= loop
->exits
)
1658 error ("nonempty exits list of loop %d, but exits are not recorded",
1665 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1667 unsigned n_exits
= 0, eloops
;
1669 sizes
= XCNEWVEC (unsigned, num
);
1670 memset (sizes
, 0, sizeof (unsigned) * num
);
1671 FOR_EACH_BB_FN (bb
, cfun
)
1674 if (bb
->loop_father
== current_loops
->tree_root
)
1676 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1678 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
1682 exit
= get_exit_descriptions (e
);
1685 error ("exit %d->%d not recorded",
1686 e
->src
->index
, e
->dest
->index
);
1690 for (; exit
; exit
= exit
->next_e
)
1693 for (loop
= bb
->loop_father
;
1694 loop
!= e
->dest
->loop_father
1695 /* When a loop exit is also an entry edge which
1696 can happen when avoiding CFG manipulations
1697 then the last loop exited is the outer loop
1698 of the loop entered. */
1699 && loop
!= loop_outer (e
->dest
->loop_father
);
1700 loop
= loop_outer (loop
))
1708 error ("wrong list of exited loops for edge %d->%d",
1709 e
->src
->index
, e
->dest
->index
);
1715 if (n_exits
!= current_loops
->exits
->elements ())
1717 error ("too many loop exits recorded");
1721 for (auto loop
: loops_list (cfun
, 0))
1724 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1726 if (eloops
!= sizes
[loop
->num
])
1728 error ("%d exits recorded for loop %d (having %d exits)",
1729 eloops
, loop
->num
, sizes
[loop
->num
]);
1740 free_dominance_info (CDI_DOMINATORS
);
1744 # pragma GCC diagnostic pop
1747 /* Returns latch edge of LOOP. */
1749 loop_latch_edge (const class loop
*loop
)
1751 return find_edge (loop
->latch
, loop
->header
);
1754 /* Returns preheader edge of LOOP. */
1756 loop_preheader_edge (const class loop
*loop
)
1761 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
)
1762 && ! loops_state_satisfies_p (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
));
1764 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1765 if (e
->src
!= loop
->latch
)
1770 gcc_assert (! loop_outer (loop
));
1771 return single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1777 /* Returns true if E is an exit of LOOP. */
1780 loop_exit_edge_p (const class loop
*loop
, const_edge e
)
1782 return (flow_bb_inside_loop_p (loop
, e
->src
)
1783 && !flow_bb_inside_loop_p (loop
, e
->dest
));
1786 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1787 or more than one exit. If loops do not have the exits recorded, NULL
1788 is returned always. */
1791 single_exit (const class loop
*loop
)
1793 struct loop_exit
*exit
= loop
->exits
->next
;
1795 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1798 if (exit
->e
&& exit
->next
== loop
->exits
)
1804 /* Returns true when BB has an incoming edge exiting LOOP. */
1807 loop_exits_to_bb_p (class loop
*loop
, basic_block bb
)
1812 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1813 if (loop_exit_edge_p (loop
, e
))
1819 /* Returns true when BB has an outgoing edge exiting LOOP. */
1822 loop_exits_from_bb_p (class loop
*loop
, basic_block bb
)
1827 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1828 if (loop_exit_edge_p (loop
, e
))
1834 /* Return location corresponding to the loop control condition if possible. */
1836 dump_user_location_t
1837 get_loop_location (class loop
*loop
)
1839 rtx_insn
*insn
= NULL
;
1840 class niter_desc
*desc
= NULL
;
1843 /* For a for or while loop, we would like to return the location
1844 of the for or while statement, if possible. To do this, look
1845 for the branch guarding the loop back-edge. */
1847 /* If this is a simple loop with an in_edge, then the loop control
1848 branch is typically at the end of its source. */
1849 desc
= get_simple_loop_desc (loop
);
1852 FOR_BB_INSNS_REVERSE (desc
->in_edge
->src
, insn
)
1854 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1858 /* If loop has a single exit, then the loop control branch
1859 must be at the end of its source. */
1860 if ((exit
= single_exit (loop
)))
1862 FOR_BB_INSNS_REVERSE (exit
->src
, insn
)
1864 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1868 /* Next check the latch, to see if it is non-empty. */
1869 FOR_BB_INSNS_REVERSE (loop
->latch
, insn
)
1871 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1874 /* Finally, if none of the above identifies the loop control branch,
1875 return the first location in the loop header. */
1876 FOR_BB_INSNS (loop
->header
, insn
)
1878 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1881 /* If all else fails, simply return the current function location. */
1882 return dump_user_location_t::from_function_decl (current_function_decl
);
1885 /* Records that every statement in LOOP is executed I_BOUND times.
1886 REALISTIC is true if I_BOUND is expected to be close to the real number
1887 of iterations. UPPER is true if we are sure the loop iterates at most
1891 record_niter_bound (class loop
*loop
, const widest_int
&i_bound
,
1892 bool realistic
, bool upper
)
1894 /* Update the bounds only when there is no previous estimation, or when the
1895 current estimation is smaller. */
1897 && (!loop
->any_upper_bound
1898 || wi::ltu_p (i_bound
, loop
->nb_iterations_upper_bound
)))
1900 loop
->any_upper_bound
= true;
1901 loop
->nb_iterations_upper_bound
= i_bound
;
1902 if (!loop
->any_likely_upper_bound
)
1904 loop
->any_likely_upper_bound
= true;
1905 loop
->nb_iterations_likely_upper_bound
= i_bound
;
1909 && (!loop
->any_estimate
1910 || wi::ltu_p (i_bound
, loop
->nb_iterations_estimate
)))
1912 loop
->any_estimate
= true;
1913 loop
->nb_iterations_estimate
= i_bound
;
1916 && (!loop
->any_likely_upper_bound
1917 || wi::ltu_p (i_bound
, loop
->nb_iterations_likely_upper_bound
)))
1919 loop
->any_likely_upper_bound
= true;
1920 loop
->nb_iterations_likely_upper_bound
= i_bound
;
1923 /* If an upper bound is smaller than the realistic estimate of the
1924 number of iterations, use the upper bound instead. */
1925 if (loop
->any_upper_bound
1926 && loop
->any_estimate
1927 && wi::ltu_p (loop
->nb_iterations_upper_bound
,
1928 loop
->nb_iterations_estimate
))
1929 loop
->nb_iterations_estimate
= loop
->nb_iterations_upper_bound
;
1930 if (loop
->any_upper_bound
1931 && loop
->any_likely_upper_bound
1932 && wi::ltu_p (loop
->nb_iterations_upper_bound
,
1933 loop
->nb_iterations_likely_upper_bound
))
1934 loop
->nb_iterations_likely_upper_bound
= loop
->nb_iterations_upper_bound
;
1937 /* Similar to get_estimated_loop_iterations, but returns the estimate only
1938 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1939 on the number of iterations of LOOP could not be derived, returns -1. */
1942 get_estimated_loop_iterations_int (class loop
*loop
)
1945 HOST_WIDE_INT hwi_nit
;
1947 if (!get_estimated_loop_iterations (loop
, &nit
))
1950 if (!wi::fits_shwi_p (nit
))
1952 hwi_nit
= nit
.to_shwi ();
1954 return hwi_nit
< 0 ? -1 : hwi_nit
;
1957 /* Returns an upper bound on the number of executions of statements
1958 in the LOOP. For statements before the loop exit, this exceeds
1959 the number of execution of the latch by one. */
1962 max_stmt_executions_int (class loop
*loop
)
1964 HOST_WIDE_INT nit
= get_max_loop_iterations_int (loop
);
1970 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
1972 /* If the computation overflows, return -1. */
1973 return snit
< 0 ? -1 : snit
;
1976 /* Returns an likely upper bound on the number of executions of statements
1977 in the LOOP. For statements before the loop exit, this exceeds
1978 the number of execution of the latch by one. */
1981 likely_max_stmt_executions_int (class loop
*loop
)
1983 HOST_WIDE_INT nit
= get_likely_max_loop_iterations_int (loop
);
1989 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
1991 /* If the computation overflows, return -1. */
1992 return snit
< 0 ? -1 : snit
;
1995 /* Sets NIT to the estimated number of executions of the latch of the
1996 LOOP. If we have no reliable estimate, the function returns false, otherwise
2000 get_estimated_loop_iterations (class loop
*loop
, widest_int
*nit
)
2002 /* Even if the bound is not recorded, possibly we can derrive one from
2004 if (!loop
->any_estimate
)
2006 if (loop
->header
->count
.reliable_p ())
2008 *nit
= gcov_type_to_wide_int
2009 (expected_loop_iterations_unbounded (loop
) + 1);
2015 *nit
= loop
->nb_iterations_estimate
;
2019 /* Sets NIT to an upper bound for the maximum number of executions of the
2020 latch of the LOOP. If we have no reliable estimate, the function returns
2021 false, otherwise returns true. */
2024 get_max_loop_iterations (const class loop
*loop
, widest_int
*nit
)
2026 if (!loop
->any_upper_bound
)
2029 *nit
= loop
->nb_iterations_upper_bound
;
2033 /* Similar to get_max_loop_iterations, but returns the estimate only
2034 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
2035 on the number of iterations of LOOP could not be derived, returns -1. */
2038 get_max_loop_iterations_int (const class loop
*loop
)
2041 HOST_WIDE_INT hwi_nit
;
2043 if (!get_max_loop_iterations (loop
, &nit
))
2046 if (!wi::fits_shwi_p (nit
))
2048 hwi_nit
= nit
.to_shwi ();
2050 return hwi_nit
< 0 ? -1 : hwi_nit
;
2053 /* Sets NIT to an upper bound for the maximum number of executions of the
2054 latch of the LOOP. If we have no reliable estimate, the function returns
2055 false, otherwise returns true. */
2058 get_likely_max_loop_iterations (class loop
*loop
, widest_int
*nit
)
2060 if (!loop
->any_likely_upper_bound
)
2063 *nit
= loop
->nb_iterations_likely_upper_bound
;
2067 /* Similar to get_max_loop_iterations, but returns the estimate only
2068 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
2069 on the number of iterations of LOOP could not be derived, returns -1. */
2072 get_likely_max_loop_iterations_int (class loop
*loop
)
2075 HOST_WIDE_INT hwi_nit
;
2077 if (!get_likely_max_loop_iterations (loop
, &nit
))
2080 if (!wi::fits_shwi_p (nit
))
2082 hwi_nit
= nit
.to_shwi ();
2084 return hwi_nit
< 0 ? -1 : hwi_nit
;
2087 /* Returns the loop depth of the loop BB belongs to. */
2090 bb_loop_depth (const_basic_block bb
)
2092 return bb
->loop_father
? loop_depth (bb
->loop_father
) : 0;
2095 /* Marks LOOP for removal and sets LOOPS_NEED_FIXUP. */
2098 mark_loop_for_removal (loop_p loop
)
2100 if (loop
->header
== NULL
)
2102 loop
->former_header
= loop
->header
;
2103 loop
->header
= NULL
;
2105 loops_state_set (LOOPS_NEED_FIXUP
);
2108 /* Starting from loop tree ROOT, walk loop tree as the visiting
2109 order specified by FLAGS. The supported visiting orders
2113 - Preorder (if neither of above is specified) */
2116 loops_list::walk_loop_tree (class loop
*root
, unsigned flags
)
2118 bool only_innermost_p
= flags
& LI_ONLY_INNERMOST
;
2119 bool from_innermost_p
= flags
& LI_FROM_INNERMOST
;
2120 bool preorder_p
= !(only_innermost_p
|| from_innermost_p
);
2122 /* Early handle root without any inner loops, make later
2123 processing simpler, that is all loops processed in the
2124 following while loop are impossible to be root. */
2127 if (flags
& LI_INCLUDE_ROOT
)
2128 this->to_visit
.quick_push (root
->num
);
2131 else if (preorder_p
&& flags
& LI_INCLUDE_ROOT
)
2132 this->to_visit
.quick_push (root
->num
);
2135 for (aloop
= root
->inner
;
2136 aloop
->inner
!= NULL
;
2137 aloop
= aloop
->inner
)
2140 this->to_visit
.quick_push (aloop
->num
);
2146 gcc_assert (aloop
!= root
);
2147 if (from_innermost_p
|| aloop
->inner
== NULL
)
2148 this->to_visit
.quick_push (aloop
->num
);
2152 for (aloop
= aloop
->next
;
2153 aloop
->inner
!= NULL
;
2154 aloop
= aloop
->inner
)
2157 this->to_visit
.quick_push (aloop
->num
);
2161 else if (loop_outer (aloop
) == root
)
2164 aloop
= loop_outer (aloop
);
2167 /* When visiting from innermost, we need to consider root here
2168 since the previous while loop doesn't handle it. */
2169 if (from_innermost_p
&& flags
& LI_INCLUDE_ROOT
)
2170 this->to_visit
.quick_push (root
->num
);