Daily bump.
[official-gcc.git] / gcc / cfgloop.c
blob20c24c13c365a2298431fe8d2d077d7b7155e14e
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
9 version.
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
14 for more details.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "rtl.h"
25 #include "tree.h"
26 #include "gimple.h"
27 #include "cfghooks.h"
28 #include "gimple-ssa.h"
29 #include "diagnostic-core.h"
30 #include "cfganal.h"
31 #include "cfgloop.h"
32 #include "gimple-iterator.h"
33 #include "dumpfile.h"
35 static void flow_loops_cfg_dump (FILE *);
37 /* Dump loop related CFG information. */
39 static void
40 flow_loops_cfg_dump (FILE *file)
42 basic_block bb;
44 if (!file)
45 return;
47 FOR_EACH_BB_FN (bb, cfun)
49 edge succ;
50 edge_iterator ei;
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. */
61 bool
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)
71 loops within LOOP. */
73 class loop *
74 superloop_at_depth (class loop *loop, unsigned depth)
76 unsigned ldepth = loop_depth (loop);
78 gcc_assert (depth <= ldepth);
80 if (depth == ldepth)
81 return loop;
83 return (*loop->superloops)[depth];
86 /* Returns the list of the latch edges of LOOP. */
88 static vec<edge>
89 get_loop_latch_edges (const class loop *loop)
91 edge_iterator ei;
92 edge e;
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))
98 ret.safe_push (e);
101 return ret;
104 /* Dump the loop information specified by LOOP to the stream FILE
105 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
107 void
108 flow_loop_dump (const class loop *loop, FILE *file,
109 void (*loop_dump_aux) (const class loop *, FILE *, int),
110 int verbose)
112 basic_block *bbs;
113 unsigned i;
114 vec<edge> latches;
115 edge e;
117 if (! loop || ! loop->header)
118 return;
120 fprintf (file, ";;\n;; Loop %d\n", loop->num);
122 fprintf (file, ";; header %d, ", loop->header->index);
123 if (loop->latch)
124 fprintf (file, "latch %d\n", loop->latch->index);
125 else
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);
131 latches.release ();
132 fprintf (file, "\n");
135 fprintf (file, ";; depth %d, outer %ld\n",
136 loop_depth (loop), (long) (loop_outer (loop)
137 ? loop_outer (loop)->num : -1));
139 if (loop->latch)
141 bool read_profile_p;
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",
145 (uint64_t) nit);
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);
152 free (bbs);
153 fprintf (file, "\n");
155 if (loop_dump_aux)
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. */
162 void
163 flow_loops_dump (FILE *file, void (*loop_dump_aux) (const class loop *, FILE *, int), int verbose)
165 if (!current_loops || ! file)
166 return;
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);
175 if (verbose)
176 flow_loops_cfg_dump (file);
179 /* Free data allocated for LOOP. */
181 void
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
191 loop structure. */
192 for (exit = loop->exits->next; exit != loop->exits; exit = next)
194 next = exit->next;
195 exit->next = exit;
196 exit->prev = exit;
199 ggc_free (loop->exits);
200 ggc_free (loop);
203 /* Free all the memory allocated for LOOPS. */
205 void
206 flow_loops_free (struct loops *loops)
208 if (loops->larray)
210 unsigned i;
211 loop_p loop;
213 /* Free the loop descriptors. */
214 FOR_EACH_VEC_SAFE_ELT (loops->larray, i, loop)
216 if (!loop)
217 continue;
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;
233 int num_nodes = 1;
234 edge latch;
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))
243 continue;
245 num_nodes++;
246 stack.safe_push (latch->src);
247 latch->src->loop_father = loop;
249 while (!stack.is_empty ())
251 basic_block node;
252 edge e;
253 edge_iterator ei;
255 node = stack.pop ();
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;
264 num_nodes++;
265 stack.safe_push (ancestor);
270 stack.release ();
272 return num_nodes;
275 /* Records the vector of superloops of the loop LOOP, whose immediate
276 superloop is FATHER. */
278 static void
279 establish_preds (class loop *loop, class loop *father)
281 loop_p ploop;
282 unsigned depth = loop_depth (father) + 1;
283 unsigned i;
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. */
302 void
303 flow_loop_tree_node_add (class loop *father, class loop *loop,
304 class loop *after)
306 if (after)
308 loop->next = after->next;
309 after->next = loop;
311 else
313 loop->next = father->inner;
314 father->inner = loop;
317 establish_preds (loop, father);
320 /* Remove LOOP from the loop hierarchy tree. */
322 void
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;
332 else
334 for (prev = father->inner; prev->next != loop; prev = prev->next)
335 continue;
336 prev->next = loop->next;
339 loop->superloops = NULL;
342 /* Allocates and returns new loop structure. */
344 class loop *
345 alloc_loop (void)
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;
356 return loop;
359 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
360 (including the root of the loop tree). */
362 void
363 init_loops_structure (struct function *fn,
364 struct loops *loops, unsigned num_loops)
366 class loop *root;
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. */
385 bool
386 bb_loop_header_p (basic_block header)
388 edge_iterator ei;
389 edge e;
391 /* If we have an abnormal predecessor, do not consider the
392 loop (not worth the problems). */
393 if (bb_has_abnormal_pred (header))
394 return false;
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))
406 return true;
409 return false;
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. */
420 struct loops *
421 flow_loops_find (struct loops *loops)
423 bool from_scratch = (loops == NULL);
424 int *rc_order;
425 int b;
426 unsigned i;
428 /* Ensure that the dominators are computed. */
429 calculate_dominance_info (CDI_DOMINATORS);
431 if (!loops)
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)
443 return loops;
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))
461 class loop *loop;
463 /* The current active loop tree has valid loop-fathers for
464 header blocks. */
465 if (!from_scratch
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
471 below. */
472 flow_loop_tree_node_remove (loop);
474 else
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;
483 if (!from_scratch
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. */
490 loop->latch = NULL;
491 larray.safe_push (loop);
494 /* Make blocks part of the loop root node at start. */
495 header->loop_father = loops->tree_root;
498 free (rc_order);
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;
506 edge_iterator ei;
507 edge e;
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
513 single one. */
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. */
523 loop->latch = NULL;
524 break;
526 loop->latch = latch;
531 return loops;
534 /* qsort helper for sort_sibling_loops. */
536 static int *sort_sibling_loops_cmp_rpo;
537 static int
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. */
548 void
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;
557 free (rc_order);
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;
569 while (sibling);
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;
577 *siblingp = NULL;
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
595 not find one.
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). */
602 static edge
603 find_subloop_latch_edge_by_profile (vec<edge> latches)
605 unsigned i;
606 edge e, me = NULL;
607 profile_count mcount = profile_count::zero (), tcount = profile_count::zero ();
609 FOR_EACH_VEC_ELT (latches, i, e)
611 if (e->count ()> mcount)
613 me = e;
614 mcount = e->count();
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)
621 return NULL;
623 if (dump_file)
624 fprintf (dump_file,
625 "Found latch edge %d -> %d using profile information.\n",
626 me->src->index, me->dest->index);
627 return me;
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
632 do not find any.
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
640 another edge. */
642 static edge
643 find_subloop_latch_edge_by_ivs (class loop *loop ATTRIBUTE_UNUSED, vec<edge> latches)
645 edge e, latch = latches[0];
646 unsigned i;
647 gphi *phi;
648 gphi_iterator psi;
649 tree lop;
650 basic_block bb;
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))
655 latch = e;
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))
660 return NULL;
662 /* Check for a phi node that would deny that this is a latch edge of
663 a subloop. */
664 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
666 phi = psi.phi ();
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)
672 continue;
673 bb = gimple_bb (SSA_NAME_DEF_STMT (lop));
674 if (!bb || !flow_bb_inside_loop_p (loop, bb))
675 continue;
677 FOR_EACH_VEC_ELT (latches, i, e)
678 if (e != latch
679 && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop)
680 return NULL;
683 if (dump_file)
684 fprintf (dump_file,
685 "Found latch edge %d -> %d using iv structure.\n",
686 latch->src->index, latch->dest->index);
687 return latch;
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
692 returns NULL. */
694 static edge
695 find_subloop_latch_edge (class loop *loop)
697 vec<edge> latches = get_loop_latch_edges (loop);
698 edge latch = NULL;
700 if (latches.length () > 1)
702 latch = find_subloop_latch_edge_by_profile (latches);
704 if (!latch
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);
712 latches.release ();
713 return latch;
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;
720 static bool
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. */
728 static void
729 form_subloop (class loop *loop, edge latch)
731 edge_iterator ei;
732 edge e, new_entry;
733 class loop *new_loop;
735 mfb_reis_set = new hash_set<edge>;
736 FOR_EACH_EDGE (e, ei, loop->header->preds)
738 if (e != latch)
739 mfb_reis_set->add (e);
741 new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
742 NULL);
743 delete mfb_reis_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. */
758 static void
759 merge_latch_edges (class loop *loop)
761 vec<edge> latches = get_loop_latch_edges (loop);
762 edge latch, e;
763 unsigned i;
765 gcc_assert (latches.length () > 0);
767 if (latches.length () == 1)
768 loop->latch = latches[0]->src;
769 else
771 if (dump_file)
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,
778 NULL);
779 delete mfb_reis_set;
781 loop->header = latch->dest;
782 loop->latch = latch->src;
785 latches.release ();
788 /* LOOP may have several latch edges. Transform it into (possibly several)
789 loops with single latch edge. */
791 static void
792 disambiguate_multiple_latches (class loop *loop)
794 edge e;
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. */
807 if (dump_file)
808 fprintf (dump_file, "Disambiguating loop %d with multiple latches\n",
809 loop->num);
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
814 such entry edge. */
815 e = find_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), loop->header);
816 if (e)
817 split_edge (e);
819 while (1)
821 e = find_subloop_latch_edge (loop);
822 if (!e)
823 break;
825 form_subloop (loop, e);
828 merge_latch_edges (loop);
831 /* Split loops with multiple latch edges. */
833 void
834 disambiguate_loops_with_multiple_latches (void)
836 for (auto loop : loops_list (cfun, 0))
838 if (!loop->latch)
839 disambiguate_multiple_latches (loop);
843 /* Return nonzero if basic block BB belongs to LOOP. */
844 bool
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))
851 return 0;
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. */
858 static bool
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
871 returned. */
873 unsigned
874 get_loop_body_with_size (const class loop *loop, basic_block *body,
875 unsigned max_size)
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. */
885 basic_block *
886 get_loop_body (const class loop *loop)
888 basic_block *body, bb;
889 unsigned tv = 0;
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)
903 body[tv++] = bb;
905 else
906 tv = get_loop_body_with_size (loop, body, loop->num_nodes);
908 gcc_assert (tv == loop->num_nodes);
909 return body;
912 /* Fills dominance descendants inside LOOP of the basic block BB into
913 array TOVISIT from index *TV. */
915 static void
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);
923 son;
924 son = next_dom_son (CDI_DOMINATORS, son))
926 if (!flow_bb_inside_loop_p (loop, son))
927 continue;
929 if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
931 postpone = son;
932 continue;
934 fill_sons_in_loop (loop, son, tovisit, tv);
937 if (postpone)
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. */
945 basic_block *
946 get_loop_body_in_dom_order (const class loop *loop)
948 basic_block *tovisit;
949 int tv;
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));
957 tv = 0;
958 fill_sons_in_loop (loop, loop->header, tovisit, &tv);
960 gcc_assert (tv == (int) loop->num_nodes);
962 return tovisit;
965 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
967 basic_block *
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);
975 return bbs;
978 /* Same as above, but use gcc_sort_r instead of qsort. */
980 basic_block *
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);
988 return bbs;
991 /* Get body of a LOOP in breadth first sort order. */
993 basic_block *
994 get_loop_body_in_bfs_order (const class loop *loop)
996 basic_block *blocks;
997 basic_block bb;
998 unsigned int i = 1;
999 unsigned int vc = 0;
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)
1010 edge e;
1011 edge_iterator ei;
1012 gcc_assert (i > vc);
1013 bb = blocks[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;
1026 return blocks;
1029 /* Hash function for struct loop_exit. */
1031 hashval_t
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. */
1039 bool
1040 loop_exit_hasher::equal (loop_exit *exit, edge e)
1042 return exit->e == e;
1045 /* Frees the list of loop exit descriptions EX. */
1047 void
1048 loop_exit_hasher::remove (loop_exit *exit)
1050 loop_exit *next;
1051 for (; exit; exit = next)
1053 next = exit->next_e;
1055 exit->next->prev = exit->prev;
1056 exit->prev->next = exit->next;
1058 ggc_free (exit);
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. */
1076 void
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))
1083 return;
1085 if (!removed
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;
1092 aloop != cloop;
1093 aloop = loop_outer (aloop))
1095 exit = ggc_alloc<loop_exit> ();
1096 exit->e = e;
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;
1104 exits = exit;
1108 if (!exits && new_edge)
1109 return;
1111 loop_exit **slot
1112 = current_loops->exits->find_slot_with_hash (e, htab_hash_pointer (e),
1113 exits ? INSERT : NO_INSERT);
1114 if (!slot)
1115 return;
1117 if (exits)
1119 if (*slot)
1120 loop_exit_hasher::remove (*slot);
1121 *slot = exits;
1123 else
1124 current_loops->exits->clear_slot (slot);
1127 /* For each loop, record list of exit edges, and start maintaining these
1128 lists. */
1130 void
1131 record_loop_exits (void)
1133 basic_block bb;
1134 edge_iterator ei;
1135 edge e;
1137 if (!current_loops)
1138 return;
1140 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1141 return;
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;
1164 unsigned n = 0;
1165 edge e = exit->e;
1167 for (; exit != NULL; exit = exit->next_e)
1168 n++;
1170 fprintf (file, "Edge %d->%d exits %u loops\n",
1171 e->src->index, e->dest->index, n);
1173 return 1;
1176 /* Dumps the recorded exits of loops to FILE. */
1178 extern void dump_recorded_exits (FILE *);
1179 void
1180 dump_recorded_exits (FILE *file)
1182 if (!current_loops->exits)
1183 return;
1184 current_loops->exits->traverse<FILE *, dump_recorded_exit> (file);
1187 /* Releases lists of loop exits. */
1189 void
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. */
1200 auto_vec<edge>
1201 get_loop_exit_edges (const class loop *loop, basic_block *body)
1203 auto_vec<edge> edges;
1204 edge e;
1205 unsigned i;
1206 edge_iterator ei;
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);
1218 else
1220 bool body_from_caller = true;
1221 if (!body)
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)
1233 free (body);
1236 return edges;
1239 /* Counts the number of conditional branches inside LOOP. */
1241 unsigned
1242 num_loop_branches (const class loop *loop)
1244 unsigned i, n;
1245 basic_block * body;
1247 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1249 body = get_loop_body (loop);
1250 n = 0;
1251 for (i = 0; i < loop->num_nodes; i++)
1252 if (EDGE_COUNT (body[i]->succs) >= 2)
1253 n++;
1254 free (body);
1256 return n;
1259 /* Adds basic block BB to LOOP. */
1260 void
1261 add_bb_to_loop (basic_block bb, class loop *loop)
1263 unsigned i;
1264 loop_p ploop;
1265 edge_iterator ei;
1266 edge e;
1268 gcc_assert (bb->loop_father == NULL);
1269 bb->loop_father = loop;
1270 loop->num_nodes++;
1271 FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
1272 ploop->num_nodes++;
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. */
1285 void
1286 remove_bb_from_loops (basic_block bb)
1288 unsigned i;
1289 class loop *loop = bb->loop_father;
1290 loop_p ploop;
1291 edge_iterator ei;
1292 edge e;
1294 gcc_assert (loop != NULL);
1295 loop->num_nodes--;
1296 FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
1297 ploop->num_nodes--;
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. */
1311 class loop *
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);
1332 return loop_s;
1335 /* Removes LOOP from structures and frees its data. */
1337 void
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. */
1352 static void
1353 cancel_loop (class loop *loop)
1355 basic_block *bbs;
1356 unsigned i;
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;
1366 free (bbs);
1367 delete_loop (loop);
1370 /* Cancels LOOP and all its subloops. */
1371 void
1372 cancel_loop_tree (class loop *loop)
1374 while (loop->inner)
1375 cancel_loop_tree (loop->inner);
1376 cancel_loop (loop);
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. */
1383 #if __GNUC__ >= 10
1384 # pragma GCC diagnostic push
1385 # pragma GCC diagnostic ignored "-Wformat-diag"
1386 #endif
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
1396 DEBUG_FUNCTION void
1397 verify_loop_structure (void)
1399 unsigned *sizes, i, j;
1400 basic_block bb, *bbs;
1401 class loop *loop;
1402 int err = 0;
1403 edge e;
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");
1411 err = 1;
1414 /* We need up-to-date dominators, compute or verify them. */
1415 if (!dom_available)
1416 calculate_dominance_info (CDI_DOMINATORS);
1417 else
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");
1427 err = 1;
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);
1437 err = 1;
1439 else if (bb->loop_father->header != bb)
1441 error ("loop with header %d not in loop tree", bb->index);
1442 err = 1;
1445 else if (bb->loop_father->header == bb)
1447 error ("non-loop with header %d not marked for removal", bb->index);
1448 err = 1;
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))
1457 unsigned n;
1459 if (loop->header == NULL)
1461 error ("removed loop %d in loop tree", loop->num);
1462 err = 1;
1463 continue;
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);
1471 err = 1;
1474 for (j = 0; j < n; j++)
1476 bb = bbs[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);
1482 err = 1;
1485 /* Ignore this block if it is in an inner loop. */
1486 if (bitmap_bit_p (visited, bb->index))
1487 continue;
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);
1494 err = 1;
1498 free (bbs);
1500 /* Check headers and latches. */
1501 for (auto loop : loops_list (cfun, 0))
1503 i = loop->num;
1504 if (loop->header == NULL)
1505 continue;
1506 if (!bb_loop_header_p (loop->header))
1508 error ("loop %d%'s header is not a loop header", i);
1509 err = 1;
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);
1515 err = 1;
1517 if (loop->latch)
1519 if (!find_edge (loop->latch, loop->header))
1521 error ("loop %d%'s latch does not have an edge to its header", i);
1522 err = 1;
1524 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, loop->header))
1526 error ("loop %d%'s latch is not dominated by its header", i);
1527 err = 1;
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);
1535 err = 1;
1537 if (single_succ (loop->latch) != loop->header)
1539 error ("loop %d%'s latch does not have header as successor", i);
1540 err = 1;
1542 if (loop->latch->loop_father != loop)
1544 error ("loop %d%'s latch does not belong directly to it", i);
1545 err = 1;
1548 if (loop->header->loop_father != loop)
1550 error ("loop %d%'s header does not belong directly to it", i);
1551 err = 1;
1553 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1555 edge_iterator ei;
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"
1561 " region", i);
1562 err = 1;
1567 /* Check irreducible loops. */
1568 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1570 auto_edge_flag saved_edge_irr (cfun);
1571 auto_bb_flag saved_bb_irr (cfun);
1572 /* Save old info. */
1573 FOR_EACH_BB_FN (bb, cfun)
1575 edge_iterator ei;
1576 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1577 bb->flags |= saved_bb_irr;
1578 FOR_EACH_EDGE (e, ei, bb->succs)
1579 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1580 e->flags |= saved_edge_irr;
1583 /* Recount it. */
1584 mark_irreducible_loops ();
1586 /* Compare. */
1587 FOR_EACH_BB_FN (bb, cfun)
1589 edge_iterator ei;
1591 if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1592 && !(bb->flags & saved_bb_irr))
1594 error ("basic block %d should be marked irreducible", bb->index);
1595 err = 1;
1597 else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1598 && (bb->flags & saved_bb_irr))
1600 error ("basic block %d should not be marked irreducible", bb->index);
1601 err = 1;
1603 bb->flags &= ~saved_bb_irr;
1604 FOR_EACH_EDGE (e, ei, bb->succs)
1606 if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1607 && !(e->flags & saved_edge_irr))
1609 error ("edge from %d to %d should be marked irreducible",
1610 e->src->index, e->dest->index);
1611 err = 1;
1613 else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1614 && (e->flags & saved_edge_irr))
1616 error ("edge from %d to %d should not be marked irreducible",
1617 e->src->index, e->dest->index);
1618 err = 1;
1620 e->flags &= ~saved_edge_irr;
1625 /* Check the recorded loop exits. */
1626 for (auto loop : loops_list (cfun, 0))
1628 if (!loop->exits || loop->exits->e != NULL)
1630 error ("corrupted head of the exits list of loop %d",
1631 loop->num);
1632 err = 1;
1634 else
1636 /* Check that the list forms a cycle, and all elements except
1637 for the head are nonnull. */
1638 for (mexit = loop->exits, exit = mexit->next, i = 0;
1639 exit->e && exit != mexit;
1640 exit = exit->next)
1642 if (i++ & 1)
1643 mexit = mexit->next;
1646 if (exit != loop->exits)
1648 error ("corrupted exits list of loop %d", loop->num);
1649 err = 1;
1653 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1655 if (loop->exits->next != loop->exits)
1657 error ("nonempty exits list of loop %d, but exits are not recorded",
1658 loop->num);
1659 err = 1;
1664 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1666 unsigned n_exits = 0, eloops;
1668 sizes = XCNEWVEC (unsigned, num);
1669 memset (sizes, 0, sizeof (unsigned) * num);
1670 FOR_EACH_BB_FN (bb, cfun)
1672 edge_iterator ei;
1673 if (bb->loop_father == current_loops->tree_root)
1674 continue;
1675 FOR_EACH_EDGE (e, ei, bb->succs)
1677 if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
1678 continue;
1680 n_exits++;
1681 exit = get_exit_descriptions (e);
1682 if (!exit)
1684 error ("exit %d->%d not recorded",
1685 e->src->index, e->dest->index);
1686 err = 1;
1688 eloops = 0;
1689 for (; exit; exit = exit->next_e)
1690 eloops++;
1692 for (loop = bb->loop_father;
1693 loop != e->dest->loop_father
1694 /* When a loop exit is also an entry edge which
1695 can happen when avoiding CFG manipulations
1696 then the last loop exited is the outer loop
1697 of the loop entered. */
1698 && loop != loop_outer (e->dest->loop_father);
1699 loop = loop_outer (loop))
1701 eloops--;
1702 sizes[loop->num]++;
1705 if (eloops != 0)
1707 error ("wrong list of exited loops for edge %d->%d",
1708 e->src->index, e->dest->index);
1709 err = 1;
1714 if (n_exits != current_loops->exits->elements ())
1716 error ("too many loop exits recorded");
1717 err = 1;
1720 for (auto loop : loops_list (cfun, 0))
1722 eloops = 0;
1723 for (exit = loop->exits->next; exit->e; exit = exit->next)
1724 eloops++;
1725 if (eloops != sizes[loop->num])
1727 error ("%d exits recorded for loop %d (having %d exits)",
1728 eloops, loop->num, sizes[loop->num]);
1729 err = 1;
1733 free (sizes);
1736 gcc_assert (!err);
1738 if (!dom_available)
1739 free_dominance_info (CDI_DOMINATORS);
1742 #if __GNUC__ >= 10
1743 # pragma GCC diagnostic pop
1744 #endif
1746 /* Returns latch edge of LOOP. */
1747 edge
1748 loop_latch_edge (const class loop *loop)
1750 return find_edge (loop->latch, loop->header);
1753 /* Returns preheader edge of LOOP. */
1754 edge
1755 loop_preheader_edge (const class loop *loop)
1757 edge e;
1758 edge_iterator ei;
1760 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
1761 && ! loops_state_satisfies_p (LOOPS_MAY_HAVE_MULTIPLE_LATCHES));
1763 FOR_EACH_EDGE (e, ei, loop->header->preds)
1764 if (e->src != loop->latch)
1765 break;
1767 if (! e)
1769 gcc_assert (! loop_outer (loop));
1770 return single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1773 return e;
1776 /* Returns true if E is an exit of LOOP. */
1778 bool
1779 loop_exit_edge_p (const class loop *loop, const_edge e)
1781 return (flow_bb_inside_loop_p (loop, e->src)
1782 && !flow_bb_inside_loop_p (loop, e->dest));
1785 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1786 or more than one exit. If loops do not have the exits recorded, NULL
1787 is returned always. */
1789 edge
1790 single_exit (const class loop *loop)
1792 struct loop_exit *exit = loop->exits->next;
1794 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1795 return NULL;
1797 if (exit->e && exit->next == loop->exits)
1798 return exit->e;
1799 else
1800 return NULL;
1803 /* Returns true when BB has an incoming edge exiting LOOP. */
1805 bool
1806 loop_exits_to_bb_p (class loop *loop, basic_block bb)
1808 edge e;
1809 edge_iterator ei;
1811 FOR_EACH_EDGE (e, ei, bb->preds)
1812 if (loop_exit_edge_p (loop, e))
1813 return true;
1815 return false;
1818 /* Returns true when BB has an outgoing edge exiting LOOP. */
1820 bool
1821 loop_exits_from_bb_p (class loop *loop, basic_block bb)
1823 edge e;
1824 edge_iterator ei;
1826 FOR_EACH_EDGE (e, ei, bb->succs)
1827 if (loop_exit_edge_p (loop, e))
1828 return true;
1830 return false;
1833 /* Return location corresponding to the loop control condition if possible. */
1835 dump_user_location_t
1836 get_loop_location (class loop *loop)
1838 rtx_insn *insn = NULL;
1839 class niter_desc *desc = NULL;
1840 edge exit;
1842 /* For a for or while loop, we would like to return the location
1843 of the for or while statement, if possible. To do this, look
1844 for the branch guarding the loop back-edge. */
1846 /* If this is a simple loop with an in_edge, then the loop control
1847 branch is typically at the end of its source. */
1848 desc = get_simple_loop_desc (loop);
1849 if (desc->in_edge)
1851 FOR_BB_INSNS_REVERSE (desc->in_edge->src, insn)
1853 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1854 return insn;
1857 /* If loop has a single exit, then the loop control branch
1858 must be at the end of its source. */
1859 if ((exit = single_exit (loop)))
1861 FOR_BB_INSNS_REVERSE (exit->src, insn)
1863 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1864 return insn;
1867 /* Next check the latch, to see if it is non-empty. */
1868 FOR_BB_INSNS_REVERSE (loop->latch, insn)
1870 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1871 return insn;
1873 /* Finally, if none of the above identifies the loop control branch,
1874 return the first location in the loop header. */
1875 FOR_BB_INSNS (loop->header, insn)
1877 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1878 return insn;
1880 /* If all else fails, simply return the current function location. */
1881 return dump_user_location_t::from_function_decl (current_function_decl);
1884 /* Records that every statement in LOOP is executed I_BOUND times.
1885 REALISTIC is true if I_BOUND is expected to be close to the real number
1886 of iterations. UPPER is true if we are sure the loop iterates at most
1887 I_BOUND times. */
1889 void
1890 record_niter_bound (class loop *loop, const widest_int &i_bound,
1891 bool realistic, bool upper)
1893 /* Update the bounds only when there is no previous estimation, or when the
1894 current estimation is smaller. */
1895 if (upper
1896 && (!loop->any_upper_bound
1897 || wi::ltu_p (i_bound, loop->nb_iterations_upper_bound)))
1899 loop->any_upper_bound = true;
1900 loop->nb_iterations_upper_bound = i_bound;
1901 if (!loop->any_likely_upper_bound)
1903 loop->any_likely_upper_bound = true;
1904 loop->nb_iterations_likely_upper_bound = i_bound;
1907 if (realistic
1908 && (!loop->any_estimate
1909 || wi::ltu_p (i_bound, loop->nb_iterations_estimate)))
1911 loop->any_estimate = true;
1912 loop->nb_iterations_estimate = i_bound;
1914 if (!realistic
1915 && (!loop->any_likely_upper_bound
1916 || wi::ltu_p (i_bound, loop->nb_iterations_likely_upper_bound)))
1918 loop->any_likely_upper_bound = true;
1919 loop->nb_iterations_likely_upper_bound = i_bound;
1922 /* If an upper bound is smaller than the realistic estimate of the
1923 number of iterations, use the upper bound instead. */
1924 if (loop->any_upper_bound
1925 && loop->any_estimate
1926 && wi::ltu_p (loop->nb_iterations_upper_bound,
1927 loop->nb_iterations_estimate))
1928 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
1929 if (loop->any_upper_bound
1930 && loop->any_likely_upper_bound
1931 && wi::ltu_p (loop->nb_iterations_upper_bound,
1932 loop->nb_iterations_likely_upper_bound))
1933 loop->nb_iterations_likely_upper_bound = loop->nb_iterations_upper_bound;
1936 /* Similar to get_estimated_loop_iterations, but returns the estimate only
1937 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1938 on the number of iterations of LOOP could not be derived, returns -1. */
1940 HOST_WIDE_INT
1941 get_estimated_loop_iterations_int (class loop *loop)
1943 widest_int nit;
1944 HOST_WIDE_INT hwi_nit;
1946 if (!get_estimated_loop_iterations (loop, &nit))
1947 return -1;
1949 if (!wi::fits_shwi_p (nit))
1950 return -1;
1951 hwi_nit = nit.to_shwi ();
1953 return hwi_nit < 0 ? -1 : hwi_nit;
1956 /* Returns an upper bound on the number of executions of statements
1957 in the LOOP. For statements before the loop exit, this exceeds
1958 the number of execution of the latch by one. */
1960 HOST_WIDE_INT
1961 max_stmt_executions_int (class loop *loop)
1963 HOST_WIDE_INT nit = get_max_loop_iterations_int (loop);
1964 HOST_WIDE_INT snit;
1966 if (nit == -1)
1967 return -1;
1969 snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
1971 /* If the computation overflows, return -1. */
1972 return snit < 0 ? -1 : snit;
1975 /* Returns an likely upper bound on the number of executions of statements
1976 in the LOOP. For statements before the loop exit, this exceeds
1977 the number of execution of the latch by one. */
1979 HOST_WIDE_INT
1980 likely_max_stmt_executions_int (class loop *loop)
1982 HOST_WIDE_INT nit = get_likely_max_loop_iterations_int (loop);
1983 HOST_WIDE_INT snit;
1985 if (nit == -1)
1986 return -1;
1988 snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
1990 /* If the computation overflows, return -1. */
1991 return snit < 0 ? -1 : snit;
1994 /* Sets NIT to the estimated number of executions of the latch of the
1995 LOOP. If we have no reliable estimate, the function returns false, otherwise
1996 returns true. */
1998 bool
1999 get_estimated_loop_iterations (class loop *loop, widest_int *nit)
2001 /* Even if the bound is not recorded, possibly we can derrive one from
2002 profile. */
2003 if (!loop->any_estimate)
2005 if (loop->header->count.reliable_p ())
2007 *nit = gcov_type_to_wide_int
2008 (expected_loop_iterations_unbounded (loop) + 1);
2009 return true;
2011 return false;
2014 *nit = loop->nb_iterations_estimate;
2015 return true;
2018 /* Sets NIT to an upper bound for the maximum number of executions of the
2019 latch of the LOOP. If we have no reliable estimate, the function returns
2020 false, otherwise returns true. */
2022 bool
2023 get_max_loop_iterations (const class loop *loop, widest_int *nit)
2025 if (!loop->any_upper_bound)
2026 return false;
2028 *nit = loop->nb_iterations_upper_bound;
2029 return true;
2032 /* Similar to get_max_loop_iterations, but returns the estimate only
2033 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
2034 on the number of iterations of LOOP could not be derived, returns -1. */
2036 HOST_WIDE_INT
2037 get_max_loop_iterations_int (const class loop *loop)
2039 widest_int nit;
2040 HOST_WIDE_INT hwi_nit;
2042 if (!get_max_loop_iterations (loop, &nit))
2043 return -1;
2045 if (!wi::fits_shwi_p (nit))
2046 return -1;
2047 hwi_nit = nit.to_shwi ();
2049 return hwi_nit < 0 ? -1 : hwi_nit;
2052 /* Sets NIT to an upper bound for the maximum number of executions of the
2053 latch of the LOOP. If we have no reliable estimate, the function returns
2054 false, otherwise returns true. */
2056 bool
2057 get_likely_max_loop_iterations (class loop *loop, widest_int *nit)
2059 if (!loop->any_likely_upper_bound)
2060 return false;
2062 *nit = loop->nb_iterations_likely_upper_bound;
2063 return true;
2066 /* Similar to get_max_loop_iterations, but returns the estimate only
2067 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
2068 on the number of iterations of LOOP could not be derived, returns -1. */
2070 HOST_WIDE_INT
2071 get_likely_max_loop_iterations_int (class loop *loop)
2073 widest_int nit;
2074 HOST_WIDE_INT hwi_nit;
2076 if (!get_likely_max_loop_iterations (loop, &nit))
2077 return -1;
2079 if (!wi::fits_shwi_p (nit))
2080 return -1;
2081 hwi_nit = nit.to_shwi ();
2083 return hwi_nit < 0 ? -1 : hwi_nit;
2086 /* Returns the loop depth of the loop BB belongs to. */
2089 bb_loop_depth (const_basic_block bb)
2091 return bb->loop_father ? loop_depth (bb->loop_father) : 0;
2094 /* Marks LOOP for removal and sets LOOPS_NEED_FIXUP. */
2096 void
2097 mark_loop_for_removal (loop_p loop)
2099 if (loop->header == NULL)
2100 return;
2101 loop->former_header = loop->header;
2102 loop->header = NULL;
2103 loop->latch = NULL;
2104 loops_state_set (LOOPS_NEED_FIXUP);
2107 /* Starting from loop tree ROOT, walk loop tree as the visiting
2108 order specified by FLAGS. The supported visiting orders
2109 are:
2110 - LI_ONLY_INNERMOST
2111 - LI_FROM_INNERMOST
2112 - Preorder (if neither of above is specified) */
2114 void
2115 loops_list::walk_loop_tree (class loop *root, unsigned flags)
2117 bool only_innermost_p = flags & LI_ONLY_INNERMOST;
2118 bool from_innermost_p = flags & LI_FROM_INNERMOST;
2119 bool preorder_p = !(only_innermost_p || from_innermost_p);
2121 /* Early handle root without any inner loops, make later
2122 processing simpler, that is all loops processed in the
2123 following while loop are impossible to be root. */
2124 if (!root->inner)
2126 if (flags & LI_INCLUDE_ROOT)
2127 this->to_visit.quick_push (root->num);
2128 return;
2130 else if (preorder_p && flags & LI_INCLUDE_ROOT)
2131 this->to_visit.quick_push (root->num);
2133 class loop *aloop;
2134 for (aloop = root->inner;
2135 aloop->inner != NULL;
2136 aloop = aloop->inner)
2138 if (preorder_p)
2139 this->to_visit.quick_push (aloop->num);
2140 continue;
2143 while (1)
2145 gcc_assert (aloop != root);
2146 if (from_innermost_p || aloop->inner == NULL)
2147 this->to_visit.quick_push (aloop->num);
2149 if (aloop->next)
2151 for (aloop = aloop->next;
2152 aloop->inner != NULL;
2153 aloop = aloop->inner)
2155 if (preorder_p)
2156 this->to_visit.quick_push (aloop->num);
2157 continue;
2160 else if (loop_outer (aloop) == root)
2161 break;
2162 else
2163 aloop = loop_outer (aloop);
2166 /* When visiting from innermost, we need to consider root here
2167 since the previous while loop doesn't handle it. */
2168 if (from_innermost_p && flags & LI_INCLUDE_ROOT)
2169 this->to_visit.quick_push (root->num);