1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000-2022 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
;
1403 unsigned num
= number_of_loops (cfun
);
1404 struct loop_exit
*exit
, *mexit
;
1405 bool dom_available
= dom_info_available_p (CDI_DOMINATORS
);
1407 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
1409 error ("loop verification on loop tree that needs fixup");
1413 /* We need up-to-date dominators, compute or verify them. */
1415 calculate_dominance_info (CDI_DOMINATORS
);
1417 verify_dominators (CDI_DOMINATORS
);
1419 /* Check the loop tree root. */
1420 if (current_loops
->tree_root
->header
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1421 || current_loops
->tree_root
->latch
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1422 || (current_loops
->tree_root
->num_nodes
1423 != (unsigned) n_basic_blocks_for_fn (cfun
)))
1425 error ("corrupt loop tree root");
1429 /* Check the headers. */
1430 FOR_EACH_BB_FN (bb
, cfun
)
1431 if (bb_loop_header_p (bb
))
1433 if (bb
->loop_father
->header
== NULL
)
1435 error ("loop with header %d marked for removal", bb
->index
);
1438 else if (bb
->loop_father
->header
!= bb
)
1440 error ("loop with header %d not in loop tree", bb
->index
);
1444 else if (bb
->loop_father
->header
== bb
)
1446 error ("non-loop with header %d not marked for removal", bb
->index
);
1450 /* Check the recorded loop father and sizes of loops. */
1451 auto_sbitmap
visited (last_basic_block_for_fn (cfun
));
1452 bitmap_clear (visited
);
1453 bbs
= XNEWVEC (basic_block
, n_basic_blocks_for_fn (cfun
));
1454 for (auto loop
: loops_list (cfun
, LI_FROM_INNERMOST
))
1458 if (loop
->header
== NULL
)
1460 error ("removed loop %d in loop tree", loop
->num
);
1465 n
= get_loop_body_with_size (loop
, bbs
, n_basic_blocks_for_fn (cfun
));
1466 if (loop
->num_nodes
!= n
)
1468 error ("size of loop %d should be %d, not %d",
1469 loop
->num
, n
, loop
->num_nodes
);
1473 for (j
= 0; j
< n
; j
++)
1477 if (!flow_bb_inside_loop_p (loop
, bb
))
1479 error ("bb %d does not belong to loop %d",
1480 bb
->index
, loop
->num
);
1484 /* Ignore this block if it is in an inner loop. */
1485 if (bitmap_bit_p (visited
, bb
->index
))
1487 bitmap_set_bit (visited
, bb
->index
);
1489 if (bb
->loop_father
!= loop
)
1491 error ("bb %d has father loop %d, should be loop %d",
1492 bb
->index
, bb
->loop_father
->num
, loop
->num
);
1499 /* Check headers and latches. */
1500 for (auto loop
: loops_list (cfun
, 0))
1503 if (loop
->header
== NULL
)
1505 if (!bb_loop_header_p (loop
->header
))
1507 error ("loop %d%'s header is not a loop header", i
);
1510 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
)
1511 && EDGE_COUNT (loop
->header
->preds
) != 2)
1513 error ("loop %d%'s header does not have exactly 2 entries", i
);
1518 if (!find_edge (loop
->latch
, loop
->header
))
1520 error ("loop %d%'s latch does not have an edge to its header", i
);
1523 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, loop
->header
))
1525 error ("loop %d%'s latch is not dominated by its header", i
);
1529 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES
))
1531 if (!single_succ_p (loop
->latch
))
1533 error ("loop %d%'s latch does not have exactly 1 successor", i
);
1536 if (single_succ (loop
->latch
) != loop
->header
)
1538 error ("loop %d%'s latch does not have header as successor", i
);
1541 if (loop
->latch
->loop_father
!= loop
)
1543 error ("loop %d%'s latch does not belong directly to it", i
);
1547 if (loop
->header
->loop_father
!= loop
)
1549 error ("loop %d%'s header does not belong directly to it", i
);
1552 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1555 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1556 if (dominated_by_p (CDI_DOMINATORS
, e
->src
, loop
->header
)
1557 && e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1559 error ("loop %d%'s latch is marked as part of irreducible"
1566 /* Check irreducible loops. */
1567 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS
))
1569 auto_edge_flag
saved_edge_irr (cfun
);
1570 auto_bb_flag
saved_bb_irr (cfun
);
1571 /* Save old info. */
1572 FOR_EACH_BB_FN (bb
, cfun
)
1575 if (bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1576 bb
->flags
|= saved_bb_irr
;
1577 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1578 if (e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1579 e
->flags
|= saved_edge_irr
;
1583 mark_irreducible_loops ();
1586 FOR_EACH_BB_FN (bb
, cfun
)
1590 if ((bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1591 && !(bb
->flags
& saved_bb_irr
))
1593 error ("basic block %d should be marked irreducible", bb
->index
);
1596 else if (!(bb
->flags
& BB_IRREDUCIBLE_LOOP
)
1597 && (bb
->flags
& saved_bb_irr
))
1599 error ("basic block %d should not be marked irreducible", bb
->index
);
1602 bb
->flags
&= ~saved_bb_irr
;
1603 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1605 if ((e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1606 && !(e
->flags
& saved_edge_irr
))
1608 error ("edge from %d to %d should be marked irreducible",
1609 e
->src
->index
, e
->dest
->index
);
1612 else if (!(e
->flags
& EDGE_IRREDUCIBLE_LOOP
)
1613 && (e
->flags
& saved_edge_irr
))
1615 error ("edge from %d to %d should not be marked irreducible",
1616 e
->src
->index
, e
->dest
->index
);
1619 e
->flags
&= ~saved_edge_irr
;
1624 /* Check the recorded loop exits. */
1625 for (auto loop
: loops_list (cfun
, 0))
1627 if (!loop
->exits
|| loop
->exits
->e
!= NULL
)
1629 error ("corrupted head of the exits list of loop %d",
1635 /* Check that the list forms a cycle, and all elements except
1636 for the head are nonnull. */
1637 for (mexit
= loop
->exits
, exit
= mexit
->next
, i
= 0;
1638 exit
->e
&& exit
!= mexit
;
1642 mexit
= mexit
->next
;
1645 if (exit
!= loop
->exits
)
1647 error ("corrupted exits list of loop %d", loop
->num
);
1652 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1654 if (loop
->exits
->next
!= loop
->exits
)
1656 error ("nonempty exits list of loop %d, but exits are not recorded",
1663 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1665 unsigned n_exits
= 0, eloops
;
1667 sizes
= XCNEWVEC (unsigned, num
);
1668 memset (sizes
, 0, sizeof (unsigned) * num
);
1669 FOR_EACH_BB_FN (bb
, cfun
)
1672 if (bb
->loop_father
== current_loops
->tree_root
)
1674 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1676 if (flow_bb_inside_loop_p (bb
->loop_father
, e
->dest
))
1680 exit
= get_exit_descriptions (e
);
1683 error ("exit %d->%d not recorded",
1684 e
->src
->index
, e
->dest
->index
);
1688 for (; exit
; exit
= exit
->next_e
)
1691 for (class loop
*loop
= bb
->loop_father
;
1692 loop
!= e
->dest
->loop_father
1693 /* When a loop exit is also an entry edge which
1694 can happen when avoiding CFG manipulations
1695 then the last loop exited is the outer loop
1696 of the loop entered. */
1697 && loop
!= loop_outer (e
->dest
->loop_father
);
1698 loop
= loop_outer (loop
))
1706 error ("wrong list of exited loops for edge %d->%d",
1707 e
->src
->index
, e
->dest
->index
);
1713 if (n_exits
!= current_loops
->exits
->elements ())
1715 error ("too many loop exits recorded");
1719 for (auto loop
: loops_list (cfun
, 0))
1722 for (exit
= loop
->exits
->next
; exit
->e
; exit
= exit
->next
)
1724 if (eloops
!= sizes
[loop
->num
])
1726 error ("%d exits recorded for loop %d (having %d exits)",
1727 eloops
, loop
->num
, sizes
[loop
->num
]);
1738 free_dominance_info (CDI_DOMINATORS
);
1742 # pragma GCC diagnostic pop
1745 /* Returns latch edge of LOOP. */
1747 loop_latch_edge (const class loop
*loop
)
1749 return find_edge (loop
->latch
, loop
->header
);
1752 /* Returns preheader edge of LOOP. */
1754 loop_preheader_edge (const class loop
*loop
)
1759 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS
)
1760 && ! loops_state_satisfies_p (LOOPS_MAY_HAVE_MULTIPLE_LATCHES
));
1762 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
1763 if (e
->src
!= loop
->latch
)
1768 gcc_assert (! loop_outer (loop
));
1769 return single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
1775 /* Returns true if E is an exit of LOOP. */
1778 loop_exit_edge_p (const class loop
*loop
, const_edge e
)
1780 return (flow_bb_inside_loop_p (loop
, e
->src
)
1781 && !flow_bb_inside_loop_p (loop
, e
->dest
));
1784 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1785 or more than one exit. If loops do not have the exits recorded, NULL
1786 is returned always. */
1789 single_exit (const class loop
*loop
)
1791 struct loop_exit
*exit
= loop
->exits
->next
;
1793 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS
))
1796 if (exit
->e
&& exit
->next
== loop
->exits
)
1802 /* Returns true when BB has an incoming edge exiting LOOP. */
1805 loop_exits_to_bb_p (class loop
*loop
, basic_block bb
)
1810 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1811 if (loop_exit_edge_p (loop
, e
))
1817 /* Returns true when BB has an outgoing edge exiting LOOP. */
1820 loop_exits_from_bb_p (class loop
*loop
, basic_block bb
)
1825 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1826 if (loop_exit_edge_p (loop
, e
))
1832 /* Return location corresponding to the loop control condition if possible. */
1834 dump_user_location_t
1835 get_loop_location (class loop
*loop
)
1837 rtx_insn
*insn
= NULL
;
1838 class niter_desc
*desc
= NULL
;
1841 /* For a for or while loop, we would like to return the location
1842 of the for or while statement, if possible. To do this, look
1843 for the branch guarding the loop back-edge. */
1845 /* If this is a simple loop with an in_edge, then the loop control
1846 branch is typically at the end of its source. */
1847 desc
= get_simple_loop_desc (loop
);
1850 FOR_BB_INSNS_REVERSE (desc
->in_edge
->src
, insn
)
1852 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1856 /* If loop has a single exit, then the loop control branch
1857 must be at the end of its source. */
1858 if ((exit
= single_exit (loop
)))
1860 FOR_BB_INSNS_REVERSE (exit
->src
, insn
)
1862 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1866 /* Next check the latch, to see if it is non-empty. */
1867 FOR_BB_INSNS_REVERSE (loop
->latch
, insn
)
1869 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1872 /* Finally, if none of the above identifies the loop control branch,
1873 return the first location in the loop header. */
1874 FOR_BB_INSNS (loop
->header
, insn
)
1876 if (INSN_P (insn
) && INSN_HAS_LOCATION (insn
))
1879 /* If all else fails, simply return the current function location. */
1880 return dump_user_location_t::from_function_decl (current_function_decl
);
1883 /* Records that every statement in LOOP is executed I_BOUND times.
1884 REALISTIC is true if I_BOUND is expected to be close to the real number
1885 of iterations. UPPER is true if we are sure the loop iterates at most
1889 record_niter_bound (class loop
*loop
, const widest_int
&i_bound
,
1890 bool realistic
, bool upper
)
1892 /* Update the bounds only when there is no previous estimation, or when the
1893 current estimation is smaller. */
1895 && (!loop
->any_upper_bound
1896 || wi::ltu_p (i_bound
, loop
->nb_iterations_upper_bound
)))
1898 loop
->any_upper_bound
= true;
1899 loop
->nb_iterations_upper_bound
= i_bound
;
1900 if (!loop
->any_likely_upper_bound
)
1902 loop
->any_likely_upper_bound
= true;
1903 loop
->nb_iterations_likely_upper_bound
= i_bound
;
1907 && (!loop
->any_estimate
1908 || wi::ltu_p (i_bound
, loop
->nb_iterations_estimate
)))
1910 loop
->any_estimate
= true;
1911 loop
->nb_iterations_estimate
= i_bound
;
1914 && (!loop
->any_likely_upper_bound
1915 || wi::ltu_p (i_bound
, loop
->nb_iterations_likely_upper_bound
)))
1917 loop
->any_likely_upper_bound
= true;
1918 loop
->nb_iterations_likely_upper_bound
= i_bound
;
1921 /* If an upper bound is smaller than the realistic estimate of the
1922 number of iterations, use the upper bound instead. */
1923 if (loop
->any_upper_bound
1924 && loop
->any_estimate
1925 && wi::ltu_p (loop
->nb_iterations_upper_bound
,
1926 loop
->nb_iterations_estimate
))
1927 loop
->nb_iterations_estimate
= loop
->nb_iterations_upper_bound
;
1928 if (loop
->any_upper_bound
1929 && loop
->any_likely_upper_bound
1930 && wi::ltu_p (loop
->nb_iterations_upper_bound
,
1931 loop
->nb_iterations_likely_upper_bound
))
1932 loop
->nb_iterations_likely_upper_bound
= loop
->nb_iterations_upper_bound
;
1935 /* Similar to get_estimated_loop_iterations, but returns the estimate only
1936 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1937 on the number of iterations of LOOP could not be derived, returns -1. */
1940 get_estimated_loop_iterations_int (class loop
*loop
)
1943 HOST_WIDE_INT hwi_nit
;
1945 if (!get_estimated_loop_iterations (loop
, &nit
))
1948 if (!wi::fits_shwi_p (nit
))
1950 hwi_nit
= nit
.to_shwi ();
1952 return hwi_nit
< 0 ? -1 : hwi_nit
;
1955 /* Returns an upper bound on the number of executions of statements
1956 in the LOOP. For statements before the loop exit, this exceeds
1957 the number of execution of the latch by one. */
1960 max_stmt_executions_int (class loop
*loop
)
1962 HOST_WIDE_INT nit
= get_max_loop_iterations_int (loop
);
1968 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
1970 /* If the computation overflows, return -1. */
1971 return snit
< 0 ? -1 : snit
;
1974 /* Returns an likely upper bound on the number of executions of statements
1975 in the LOOP. For statements before the loop exit, this exceeds
1976 the number of execution of the latch by one. */
1979 likely_max_stmt_executions_int (class loop
*loop
)
1981 HOST_WIDE_INT nit
= get_likely_max_loop_iterations_int (loop
);
1987 snit
= (HOST_WIDE_INT
) ((unsigned HOST_WIDE_INT
) nit
+ 1);
1989 /* If the computation overflows, return -1. */
1990 return snit
< 0 ? -1 : snit
;
1993 /* Sets NIT to the estimated number of executions of the latch of the
1994 LOOP. If we have no reliable estimate, the function returns false, otherwise
1998 get_estimated_loop_iterations (class loop
*loop
, widest_int
*nit
)
2000 /* Even if the bound is not recorded, possibly we can derrive one from
2002 if (!loop
->any_estimate
)
2004 if (loop
->header
->count
.reliable_p ())
2006 *nit
= gcov_type_to_wide_int
2007 (expected_loop_iterations_unbounded (loop
) + 1);
2013 *nit
= loop
->nb_iterations_estimate
;
2017 /* Sets NIT to an upper bound for the maximum number of executions of the
2018 latch of the LOOP. If we have no reliable estimate, the function returns
2019 false, otherwise returns true. */
2022 get_max_loop_iterations (const class loop
*loop
, widest_int
*nit
)
2024 if (!loop
->any_upper_bound
)
2027 *nit
= loop
->nb_iterations_upper_bound
;
2031 /* Similar to get_max_loop_iterations, but returns the estimate only
2032 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
2033 on the number of iterations of LOOP could not be derived, returns -1. */
2036 get_max_loop_iterations_int (const class loop
*loop
)
2039 HOST_WIDE_INT hwi_nit
;
2041 if (!get_max_loop_iterations (loop
, &nit
))
2044 if (!wi::fits_shwi_p (nit
))
2046 hwi_nit
= nit
.to_shwi ();
2048 return hwi_nit
< 0 ? -1 : hwi_nit
;
2051 /* Sets NIT to an upper bound for the maximum number of executions of the
2052 latch of the LOOP. If we have no reliable estimate, the function returns
2053 false, otherwise returns true. */
2056 get_likely_max_loop_iterations (class loop
*loop
, widest_int
*nit
)
2058 if (!loop
->any_likely_upper_bound
)
2061 *nit
= loop
->nb_iterations_likely_upper_bound
;
2065 /* Similar to get_max_loop_iterations, but returns the estimate only
2066 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
2067 on the number of iterations of LOOP could not be derived, returns -1. */
2070 get_likely_max_loop_iterations_int (class loop
*loop
)
2073 HOST_WIDE_INT hwi_nit
;
2075 if (!get_likely_max_loop_iterations (loop
, &nit
))
2078 if (!wi::fits_shwi_p (nit
))
2080 hwi_nit
= nit
.to_shwi ();
2082 return hwi_nit
< 0 ? -1 : hwi_nit
;
2085 /* Returns the loop depth of the loop BB belongs to. */
2088 bb_loop_depth (const_basic_block bb
)
2090 return bb
->loop_father
? loop_depth (bb
->loop_father
) : 0;
2093 /* Marks LOOP for removal and sets LOOPS_NEED_FIXUP. */
2096 mark_loop_for_removal (loop_p loop
)
2098 if (loop
->header
== NULL
)
2100 loop
->former_header
= loop
->header
;
2101 loop
->header
= NULL
;
2103 loops_state_set (LOOPS_NEED_FIXUP
);
2106 /* Starting from loop tree ROOT, walk loop tree as the visiting
2107 order specified by FLAGS. The supported visiting orders
2111 - Preorder (if neither of above is specified) */
2114 loops_list::walk_loop_tree (class loop
*root
, unsigned flags
)
2116 bool only_innermost_p
= flags
& LI_ONLY_INNERMOST
;
2117 bool from_innermost_p
= flags
& LI_FROM_INNERMOST
;
2118 bool preorder_p
= !(only_innermost_p
|| from_innermost_p
);
2120 /* Early handle root without any inner loops, make later
2121 processing simpler, that is all loops processed in the
2122 following while loop are impossible to be root. */
2125 if (flags
& LI_INCLUDE_ROOT
)
2126 this->to_visit
.quick_push (root
->num
);
2129 else if (preorder_p
&& flags
& LI_INCLUDE_ROOT
)
2130 this->to_visit
.quick_push (root
->num
);
2133 for (aloop
= root
->inner
;
2134 aloop
->inner
!= NULL
;
2135 aloop
= aloop
->inner
)
2138 this->to_visit
.quick_push (aloop
->num
);
2144 gcc_assert (aloop
!= root
);
2145 if (from_innermost_p
|| aloop
->inner
== NULL
)
2146 this->to_visit
.quick_push (aloop
->num
);
2150 for (aloop
= aloop
->next
;
2151 aloop
->inner
!= NULL
;
2152 aloop
= aloop
->inner
)
2155 this->to_visit
.quick_push (aloop
->num
);
2159 else if (loop_outer (aloop
) == root
)
2162 aloop
= loop_outer (aloop
);
2165 /* When visiting from innermost, we need to consider root here
2166 since the previous while loop doesn't handle it. */
2167 if (from_innermost_p
&& flags
& LI_INCLUDE_ROOT
)
2168 this->to_visit
.quick_push (root
->num
);