typeck.c (cp_truthvalue_conversion): Add tsubst_flags_t parameter and use it in calls...
[official-gcc.git] / gcc / cfgloop.c
blob4ad1f658708f83dbd8789666c26d4bd056837bc6
1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000-2019 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 class loop *loop;
167 if (!current_loops || ! file)
168 return;
170 fprintf (file, ";; %d loops found\n", number_of_loops (cfun));
172 FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT)
174 flow_loop_dump (loop, file, loop_dump_aux, verbose);
177 if (verbose)
178 flow_loops_cfg_dump (file);
181 /* Free data allocated for LOOP. */
183 void
184 flow_loop_free (class loop *loop)
186 struct loop_exit *exit, *next;
188 vec_free (loop->superloops);
190 /* Break the list of the loop exit records. They will be freed when the
191 corresponding edge is rescanned or removed, and this avoids
192 accessing the (already released) head of the list stored in the
193 loop structure. */
194 for (exit = loop->exits->next; exit != loop->exits; exit = next)
196 next = exit->next;
197 exit->next = exit;
198 exit->prev = exit;
201 ggc_free (loop->exits);
202 ggc_free (loop);
205 /* Free all the memory allocated for LOOPS. */
207 void
208 flow_loops_free (struct loops *loops)
210 if (loops->larray)
212 unsigned i;
213 loop_p loop;
215 /* Free the loop descriptors. */
216 FOR_EACH_VEC_SAFE_ELT (loops->larray, i, loop)
218 if (!loop)
219 continue;
221 flow_loop_free (loop);
224 vec_free (loops->larray);
228 /* Find the nodes contained within the LOOP with header HEADER.
229 Return the number of nodes within the loop. */
232 flow_loop_nodes_find (basic_block header, class loop *loop)
234 vec<basic_block> stack = vNULL;
235 int num_nodes = 1;
236 edge latch;
237 edge_iterator latch_ei;
239 header->loop_father = loop;
241 FOR_EACH_EDGE (latch, latch_ei, loop->header->preds)
243 if (latch->src->loop_father == loop
244 || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header))
245 continue;
247 num_nodes++;
248 stack.safe_push (latch->src);
249 latch->src->loop_father = loop;
251 while (!stack.is_empty ())
253 basic_block node;
254 edge e;
255 edge_iterator ei;
257 node = stack.pop ();
259 FOR_EACH_EDGE (e, ei, node->preds)
261 basic_block ancestor = e->src;
263 if (ancestor->loop_father != loop)
265 ancestor->loop_father = loop;
266 num_nodes++;
267 stack.safe_push (ancestor);
272 stack.release ();
274 return num_nodes;
277 /* Records the vector of superloops of the loop LOOP, whose immediate
278 superloop is FATHER. */
280 static void
281 establish_preds (class loop *loop, class loop *father)
283 loop_p ploop;
284 unsigned depth = loop_depth (father) + 1;
285 unsigned i;
287 loop->superloops = 0;
288 vec_alloc (loop->superloops, depth);
289 FOR_EACH_VEC_SAFE_ELT (father->superloops, i, ploop)
290 loop->superloops->quick_push (ploop);
291 loop->superloops->quick_push (father);
293 for (ploop = loop->inner; ploop; ploop = ploop->next)
294 establish_preds (ploop, loop);
297 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
298 added loop. If LOOP has some children, take care of that their
299 pred field will be initialized correctly. If AFTER is non-null
300 then it's expected it's a pointer into FATHERs inner sibling
301 list and LOOP is added behind AFTER, otherwise it's added in front
302 of FATHERs siblings. */
304 void
305 flow_loop_tree_node_add (class loop *father, class loop *loop,
306 class loop *after)
308 if (after)
310 loop->next = after->next;
311 after->next = loop;
313 else
315 loop->next = father->inner;
316 father->inner = loop;
319 establish_preds (loop, father);
322 /* Remove LOOP from the loop hierarchy tree. */
324 void
325 flow_loop_tree_node_remove (class loop *loop)
327 class loop *prev, *father;
329 father = loop_outer (loop);
331 /* Remove loop from the list of sons. */
332 if (father->inner == loop)
333 father->inner = loop->next;
334 else
336 for (prev = father->inner; prev->next != loop; prev = prev->next)
337 continue;
338 prev->next = loop->next;
341 loop->superloops = NULL;
344 /* Allocates and returns new loop structure. */
346 class loop *
347 alloc_loop (void)
349 class loop *loop = ggc_cleared_alloc<class loop> ();
351 loop->exits = ggc_cleared_alloc<loop_exit> ();
352 loop->exits->next = loop->exits->prev = loop->exits;
353 loop->can_be_parallel = false;
354 loop->constraints = 0;
355 loop->nb_iterations_upper_bound = 0;
356 loop->nb_iterations_likely_upper_bound = 0;
357 loop->nb_iterations_estimate = 0;
358 return loop;
361 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
362 (including the root of the loop tree). */
364 void
365 init_loops_structure (struct function *fn,
366 struct loops *loops, unsigned num_loops)
368 class loop *root;
370 memset (loops, 0, sizeof *loops);
371 vec_alloc (loops->larray, num_loops);
373 /* Dummy loop containing whole function. */
374 root = alloc_loop ();
375 root->num_nodes = n_basic_blocks_for_fn (fn);
376 root->latch = EXIT_BLOCK_PTR_FOR_FN (fn);
377 root->header = ENTRY_BLOCK_PTR_FOR_FN (fn);
378 ENTRY_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
379 EXIT_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
381 loops->larray->quick_push (root);
382 loops->tree_root = root;
385 /* Returns whether HEADER is a loop header. */
387 bool
388 bb_loop_header_p (basic_block header)
390 edge_iterator ei;
391 edge e;
393 /* If we have an abnormal predecessor, do not consider the
394 loop (not worth the problems). */
395 if (bb_has_abnormal_pred (header))
396 return false;
398 /* Look for back edges where a predecessor is dominated
399 by this block. A natural loop has a single entry
400 node (header) that dominates all the nodes in the
401 loop. It also has single back edge to the header
402 from a latch node. */
403 FOR_EACH_EDGE (e, ei, header->preds)
405 basic_block latch = e->src;
406 if (latch != ENTRY_BLOCK_PTR_FOR_FN (cfun)
407 && dominated_by_p (CDI_DOMINATORS, latch, header))
408 return true;
411 return false;
414 /* Find all the natural loops in the function and save in LOOPS structure and
415 recalculate loop_father information in basic block structures.
416 If LOOPS is non-NULL then the loop structures for already recorded loops
417 will be re-used and their number will not change. We assume that no
418 stale loops exist in LOOPS.
419 When LOOPS is NULL it is allocated and re-built from scratch.
420 Return the built LOOPS structure. */
422 struct loops *
423 flow_loops_find (struct loops *loops)
425 bool from_scratch = (loops == NULL);
426 int *rc_order;
427 int b;
428 unsigned i;
430 /* Ensure that the dominators are computed. */
431 calculate_dominance_info (CDI_DOMINATORS);
433 if (!loops)
435 loops = ggc_cleared_alloc<struct loops> ();
436 init_loops_structure (cfun, loops, 1);
439 /* Ensure that loop exits were released. */
440 gcc_assert (loops->exits == NULL);
442 /* Taking care of this degenerate case makes the rest of
443 this code simpler. */
444 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
445 return loops;
447 /* The root loop node contains all basic-blocks. */
448 loops->tree_root->num_nodes = n_basic_blocks_for_fn (cfun);
450 /* Compute depth first search order of the CFG so that outer
451 natural loops will be found before inner natural loops. */
452 rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
453 pre_and_rev_post_order_compute (NULL, rc_order, false);
455 /* Gather all loop headers in reverse completion order and allocate
456 loop structures for loops that are not already present. */
457 auto_vec<loop_p> larray (loops->larray->length ());
458 for (b = 0; b < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; b++)
460 basic_block header = BASIC_BLOCK_FOR_FN (cfun, rc_order[b]);
461 if (bb_loop_header_p (header))
463 class loop *loop;
465 /* The current active loop tree has valid loop-fathers for
466 header blocks. */
467 if (!from_scratch
468 && header->loop_father->header == header)
470 loop = header->loop_father;
471 /* If we found an existing loop remove it from the
472 loop tree. It is going to be inserted again
473 below. */
474 flow_loop_tree_node_remove (loop);
476 else
478 /* Otherwise allocate a new loop structure for the loop. */
479 loop = alloc_loop ();
480 /* ??? We could re-use unused loop slots here. */
481 loop->num = loops->larray->length ();
482 vec_safe_push (loops->larray, loop);
483 loop->header = header;
485 if (!from_scratch
486 && dump_file && (dump_flags & TDF_DETAILS))
487 fprintf (dump_file, "flow_loops_find: discovered new "
488 "loop %d with header %d\n",
489 loop->num, header->index);
491 /* Reset latch, we recompute it below. */
492 loop->latch = NULL;
493 larray.safe_push (loop);
496 /* Make blocks part of the loop root node at start. */
497 header->loop_father = loops->tree_root;
500 free (rc_order);
502 /* Now iterate over the loops found, insert them into the loop tree
503 and assign basic-block ownership. */
504 for (i = 0; i < larray.length (); ++i)
506 class loop *loop = larray[i];
507 basic_block header = loop->header;
508 edge_iterator ei;
509 edge e;
511 flow_loop_tree_node_add (header->loop_father, loop);
512 loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
514 /* Look for the latch for this header block, if it has just a
515 single one. */
516 FOR_EACH_EDGE (e, ei, header->preds)
518 basic_block latch = e->src;
520 if (flow_bb_inside_loop_p (loop, latch))
522 if (loop->latch != NULL)
524 /* More than one latch edge. */
525 loop->latch = NULL;
526 break;
528 loop->latch = latch;
533 return loops;
536 /* qsort helper for sort_sibling_loops. */
538 static int *sort_sibling_loops_cmp_rpo;
539 static int
540 sort_sibling_loops_cmp (const void *la_, const void *lb_)
542 const class loop *la = *(const class loop * const *)la_;
543 const class loop *lb = *(const class loop * const *)lb_;
544 return (sort_sibling_loops_cmp_rpo[la->header->index]
545 - sort_sibling_loops_cmp_rpo[lb->header->index]);
548 /* Sort sibling loops in RPO order. */
550 void
551 sort_sibling_loops (function *fn)
553 /* Match flow_loops_find in the order we sort sibling loops. */
554 sort_sibling_loops_cmp_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
555 int *rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
556 pre_and_rev_post_order_compute_fn (fn, NULL, rc_order, false);
557 for (int i = 0; i < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; ++i)
558 sort_sibling_loops_cmp_rpo[rc_order[i]] = i;
559 free (rc_order);
561 auto_vec<loop_p, 3> siblings;
562 loop_p loop;
563 FOR_EACH_LOOP_FN (fn, loop, LI_INCLUDE_ROOT)
564 if (loop->inner && loop->inner->next)
566 loop_p sibling = loop->inner;
569 siblings.safe_push (sibling);
570 sibling = sibling->next;
572 while (sibling);
573 siblings.qsort (sort_sibling_loops_cmp);
574 loop_p *siblingp = &loop->inner;
575 for (unsigned i = 0; i < siblings.length (); ++i)
577 *siblingp = siblings[i];
578 siblingp = &(*siblingp)->next;
580 *siblingp = NULL;
581 siblings.truncate (0);
584 free (sort_sibling_loops_cmp_rpo);
585 sort_sibling_loops_cmp_rpo = NULL;
588 /* Ratio of frequencies of edges so that one of more latch edges is
589 considered to belong to inner loop with same header. */
590 #define HEAVY_EDGE_RATIO 8
592 /* Minimum number of samples for that we apply
593 find_subloop_latch_edge_by_profile heuristics. */
594 #define HEAVY_EDGE_MIN_SAMPLES 10
596 /* If the profile info is available, finds an edge in LATCHES that much more
597 frequent than the remaining edges. Returns such an edge, or NULL if we do
598 not find one.
600 We do not use guessed profile here, only the measured one. The guessed
601 profile is usually too flat and unreliable for this (and it is mostly based
602 on the loop structure of the program, so it does not make much sense to
603 derive the loop structure from it). */
605 static edge
606 find_subloop_latch_edge_by_profile (vec<edge> latches)
608 unsigned i;
609 edge e, me = NULL;
610 profile_count mcount = profile_count::zero (), tcount = profile_count::zero ();
612 FOR_EACH_VEC_ELT (latches, i, e)
614 if (e->count ()> mcount)
616 me = e;
617 mcount = e->count();
619 tcount += e->count();
622 if (!tcount.initialized_p () || !(tcount.ipa () > HEAVY_EDGE_MIN_SAMPLES)
623 || (tcount - mcount).apply_scale (HEAVY_EDGE_RATIO, 1) > tcount)
624 return NULL;
626 if (dump_file)
627 fprintf (dump_file,
628 "Found latch edge %d -> %d using profile information.\n",
629 me->src->index, me->dest->index);
630 return me;
633 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
634 on the structure of induction variables. Returns this edge, or NULL if we
635 do not find any.
637 We are quite conservative, and look just for an obvious simple innermost
638 loop (which is the case where we would lose the most performance by not
639 disambiguating the loop). More precisely, we look for the following
640 situation: The source of the chosen latch edge dominates sources of all
641 the other latch edges. Additionally, the header does not contain a phi node
642 such that the argument from the chosen edge is equal to the argument from
643 another edge. */
645 static edge
646 find_subloop_latch_edge_by_ivs (class loop *loop ATTRIBUTE_UNUSED, vec<edge> latches)
648 edge e, latch = latches[0];
649 unsigned i;
650 gphi *phi;
651 gphi_iterator psi;
652 tree lop;
653 basic_block bb;
655 /* Find the candidate for the latch edge. */
656 for (i = 1; latches.iterate (i, &e); i++)
657 if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src))
658 latch = e;
660 /* Verify that it dominates all the latch edges. */
661 FOR_EACH_VEC_ELT (latches, i, e)
662 if (!dominated_by_p (CDI_DOMINATORS, e->src, latch->src))
663 return NULL;
665 /* Check for a phi node that would deny that this is a latch edge of
666 a subloop. */
667 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
669 phi = psi.phi ();
670 lop = PHI_ARG_DEF_FROM_EDGE (phi, latch);
672 /* Ignore the values that are not changed inside the subloop. */
673 if (TREE_CODE (lop) != SSA_NAME
674 || SSA_NAME_DEF_STMT (lop) == phi)
675 continue;
676 bb = gimple_bb (SSA_NAME_DEF_STMT (lop));
677 if (!bb || !flow_bb_inside_loop_p (loop, bb))
678 continue;
680 FOR_EACH_VEC_ELT (latches, i, e)
681 if (e != latch
682 && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop)
683 return NULL;
686 if (dump_file)
687 fprintf (dump_file,
688 "Found latch edge %d -> %d using iv structure.\n",
689 latch->src->index, latch->dest->index);
690 return latch;
693 /* If we can determine that one of the several latch edges of LOOP behaves
694 as a latch edge of a separate subloop, returns this edge. Otherwise
695 returns NULL. */
697 static edge
698 find_subloop_latch_edge (class loop *loop)
700 vec<edge> latches = get_loop_latch_edges (loop);
701 edge latch = NULL;
703 if (latches.length () > 1)
705 latch = find_subloop_latch_edge_by_profile (latches);
707 if (!latch
708 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
709 should use cfghook for this, but it is hard to imagine it would
710 be useful elsewhere. */
711 && current_ir_type () == IR_GIMPLE)
712 latch = find_subloop_latch_edge_by_ivs (loop, latches);
715 latches.release ();
716 return latch;
719 /* Callback for make_forwarder_block. Returns true if the edge E is marked
720 in the set MFB_REIS_SET. */
722 static hash_set<edge> *mfb_reis_set;
723 static bool
724 mfb_redirect_edges_in_set (edge e)
726 return mfb_reis_set->contains (e);
729 /* Creates a subloop of LOOP with latch edge LATCH. */
731 static void
732 form_subloop (class loop *loop, edge latch)
734 edge_iterator ei;
735 edge e, new_entry;
736 class loop *new_loop;
738 mfb_reis_set = new hash_set<edge>;
739 FOR_EACH_EDGE (e, ei, loop->header->preds)
741 if (e != latch)
742 mfb_reis_set->add (e);
744 new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
745 NULL);
746 delete mfb_reis_set;
748 loop->header = new_entry->src;
750 /* Find the blocks and subloops that belong to the new loop, and add it to
751 the appropriate place in the loop tree. */
752 new_loop = alloc_loop ();
753 new_loop->header = new_entry->dest;
754 new_loop->latch = latch->src;
755 add_loop (new_loop, loop);
758 /* Make all the latch edges of LOOP to go to a single forwarder block --
759 a new latch of LOOP. */
761 static void
762 merge_latch_edges (class loop *loop)
764 vec<edge> latches = get_loop_latch_edges (loop);
765 edge latch, e;
766 unsigned i;
768 gcc_assert (latches.length () > 0);
770 if (latches.length () == 1)
771 loop->latch = latches[0]->src;
772 else
774 if (dump_file)
775 fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num);
777 mfb_reis_set = new hash_set<edge>;
778 FOR_EACH_VEC_ELT (latches, i, e)
779 mfb_reis_set->add (e);
780 latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
781 NULL);
782 delete mfb_reis_set;
784 loop->header = latch->dest;
785 loop->latch = latch->src;
788 latches.release ();
791 /* LOOP may have several latch edges. Transform it into (possibly several)
792 loops with single latch edge. */
794 static void
795 disambiguate_multiple_latches (class loop *loop)
797 edge e;
799 /* We eliminate the multiple latches by splitting the header to the forwarder
800 block F and the rest R, and redirecting the edges. There are two cases:
802 1) If there is a latch edge E that corresponds to a subloop (we guess
803 that based on profile -- if it is taken much more often than the
804 remaining edges; and on trees, using the information about induction
805 variables of the loops), we redirect E to R, all the remaining edges to
806 F, then rescan the loops and try again for the outer loop.
807 2) If there is no such edge, we redirect all latch edges to F, and the
808 entry edges to R, thus making F the single latch of the loop. */
810 if (dump_file)
811 fprintf (dump_file, "Disambiguating loop %d with multiple latches\n",
812 loop->num);
814 /* During latch merging, we may need to redirect the entry edges to a new
815 block. This would cause problems if the entry edge was the one from the
816 entry block. To avoid having to handle this case specially, split
817 such entry edge. */
818 e = find_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), loop->header);
819 if (e)
820 split_edge (e);
822 while (1)
824 e = find_subloop_latch_edge (loop);
825 if (!e)
826 break;
828 form_subloop (loop, e);
831 merge_latch_edges (loop);
834 /* Split loops with multiple latch edges. */
836 void
837 disambiguate_loops_with_multiple_latches (void)
839 class loop *loop;
841 FOR_EACH_LOOP (loop, 0)
843 if (!loop->latch)
844 disambiguate_multiple_latches (loop);
848 /* Return nonzero if basic block BB belongs to LOOP. */
849 bool
850 flow_bb_inside_loop_p (const class loop *loop, const_basic_block bb)
852 class loop *source_loop;
854 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
855 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
856 return 0;
858 source_loop = bb->loop_father;
859 return loop == source_loop || flow_loop_nested_p (loop, source_loop);
862 /* Enumeration predicate for get_loop_body_with_size. */
863 static bool
864 glb_enum_p (const_basic_block bb, const void *glb_loop)
866 const class loop *const loop = (const class loop *) glb_loop;
867 return (bb != loop->header
868 && dominated_by_p (CDI_DOMINATORS, bb, loop->header));
871 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
872 order against direction of edges from latch. Specially, if
873 header != latch, latch is the 1-st block. LOOP cannot be the fake
874 loop tree root, and its size must be at most MAX_SIZE. The blocks
875 in the LOOP body are stored to BODY, and the size of the LOOP is
876 returned. */
878 unsigned
879 get_loop_body_with_size (const class loop *loop, basic_block *body,
880 unsigned max_size)
882 return dfs_enumerate_from (loop->header, 1, glb_enum_p,
883 body, max_size, loop);
886 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
887 order against direction of edges from latch. Specially, if
888 header != latch, latch is the 1-st block. */
890 basic_block *
891 get_loop_body (const class loop *loop)
893 basic_block *body, bb;
894 unsigned tv = 0;
896 gcc_assert (loop->num_nodes);
898 body = XNEWVEC (basic_block, loop->num_nodes);
900 if (loop->latch == EXIT_BLOCK_PTR_FOR_FN (cfun))
902 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
903 special-case the fake loop that contains the whole function. */
904 gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks_for_fn (cfun));
905 body[tv++] = loop->header;
906 body[tv++] = EXIT_BLOCK_PTR_FOR_FN (cfun);
907 FOR_EACH_BB_FN (bb, cfun)
908 body[tv++] = bb;
910 else
911 tv = get_loop_body_with_size (loop, body, loop->num_nodes);
913 gcc_assert (tv == loop->num_nodes);
914 return body;
917 /* Fills dominance descendants inside LOOP of the basic block BB into
918 array TOVISIT from index *TV. */
920 static void
921 fill_sons_in_loop (const class loop *loop, basic_block bb,
922 basic_block *tovisit, int *tv)
924 basic_block son, postpone = NULL;
926 tovisit[(*tv)++] = bb;
927 for (son = first_dom_son (CDI_DOMINATORS, bb);
928 son;
929 son = next_dom_son (CDI_DOMINATORS, son))
931 if (!flow_bb_inside_loop_p (loop, son))
932 continue;
934 if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
936 postpone = son;
937 continue;
939 fill_sons_in_loop (loop, son, tovisit, tv);
942 if (postpone)
943 fill_sons_in_loop (loop, postpone, tovisit, tv);
946 /* Gets body of a LOOP (that must be different from the outermost loop)
947 sorted by dominance relation. Additionally, if a basic block s dominates
948 the latch, then only blocks dominated by s are be after it. */
950 basic_block *
951 get_loop_body_in_dom_order (const class loop *loop)
953 basic_block *tovisit;
954 int tv;
956 gcc_assert (loop->num_nodes);
958 tovisit = XNEWVEC (basic_block, loop->num_nodes);
960 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
962 tv = 0;
963 fill_sons_in_loop (loop, loop->header, tovisit, &tv);
965 gcc_assert (tv == (int) loop->num_nodes);
967 return tovisit;
970 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
972 basic_block *
973 get_loop_body_in_custom_order (const class loop *loop,
974 int (*bb_comparator) (const void *, const void *))
976 basic_block *bbs = get_loop_body (loop);
978 qsort (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator);
980 return bbs;
983 /* Get body of a LOOP in breadth first sort order. */
985 basic_block *
986 get_loop_body_in_bfs_order (const class loop *loop)
988 basic_block *blocks;
989 basic_block bb;
990 unsigned int i = 1;
991 unsigned int vc = 0;
993 gcc_assert (loop->num_nodes);
994 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
996 blocks = XNEWVEC (basic_block, loop->num_nodes);
997 auto_bitmap visited;
998 blocks[0] = loop->header;
999 bitmap_set_bit (visited, loop->header->index);
1000 while (i < loop->num_nodes)
1002 edge e;
1003 edge_iterator ei;
1004 gcc_assert (i > vc);
1005 bb = blocks[vc++];
1007 FOR_EACH_EDGE (e, ei, bb->succs)
1009 if (flow_bb_inside_loop_p (loop, e->dest))
1011 /* This bb is now visited. */
1012 if (bitmap_set_bit (visited, e->dest->index))
1013 blocks[i++] = e->dest;
1018 return blocks;
1021 /* Hash function for struct loop_exit. */
1023 hashval_t
1024 loop_exit_hasher::hash (loop_exit *exit)
1026 return htab_hash_pointer (exit->e);
1029 /* Equality function for struct loop_exit. Compares with edge. */
1031 bool
1032 loop_exit_hasher::equal (loop_exit *exit, edge e)
1034 return exit->e == e;
1037 /* Frees the list of loop exit descriptions EX. */
1039 void
1040 loop_exit_hasher::remove (loop_exit *exit)
1042 loop_exit *next;
1043 for (; exit; exit = next)
1045 next = exit->next_e;
1047 exit->next->prev = exit->prev;
1048 exit->prev->next = exit->next;
1050 ggc_free (exit);
1054 /* Returns the list of records for E as an exit of a loop. */
1056 static struct loop_exit *
1057 get_exit_descriptions (edge e)
1059 return current_loops->exits->find_with_hash (e, htab_hash_pointer (e));
1062 /* Updates the lists of loop exits in that E appears.
1063 If REMOVED is true, E is being removed, and we
1064 just remove it from the lists of exits.
1065 If NEW_EDGE is true and E is not a loop exit, we
1066 do not try to remove it from loop exit lists. */
1068 void
1069 rescan_loop_exit (edge e, bool new_edge, bool removed)
1071 struct loop_exit *exits = NULL, *exit;
1072 class loop *aloop, *cloop;
1074 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1075 return;
1077 if (!removed
1078 && e->src->loop_father != NULL
1079 && e->dest->loop_father != NULL
1080 && !flow_bb_inside_loop_p (e->src->loop_father, e->dest))
1082 cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
1083 for (aloop = e->src->loop_father;
1084 aloop != cloop;
1085 aloop = loop_outer (aloop))
1087 exit = ggc_alloc<loop_exit> ();
1088 exit->e = e;
1090 exit->next = aloop->exits->next;
1091 exit->prev = aloop->exits;
1092 exit->next->prev = exit;
1093 exit->prev->next = exit;
1095 exit->next_e = exits;
1096 exits = exit;
1100 if (!exits && new_edge)
1101 return;
1103 loop_exit **slot
1104 = current_loops->exits->find_slot_with_hash (e, htab_hash_pointer (e),
1105 exits ? INSERT : NO_INSERT);
1106 if (!slot)
1107 return;
1109 if (exits)
1111 if (*slot)
1112 loop_exit_hasher::remove (*slot);
1113 *slot = exits;
1115 else
1116 current_loops->exits->clear_slot (slot);
1119 /* For each loop, record list of exit edges, and start maintaining these
1120 lists. */
1122 void
1123 record_loop_exits (void)
1125 basic_block bb;
1126 edge_iterator ei;
1127 edge e;
1129 if (!current_loops)
1130 return;
1132 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1133 return;
1134 loops_state_set (LOOPS_HAVE_RECORDED_EXITS);
1136 gcc_assert (current_loops->exits == NULL);
1137 current_loops->exits
1138 = hash_table<loop_exit_hasher>::create_ggc (2 * number_of_loops (cfun));
1140 FOR_EACH_BB_FN (bb, cfun)
1142 FOR_EACH_EDGE (e, ei, bb->succs)
1144 rescan_loop_exit (e, true, false);
1149 /* Dumps information about the exit in *SLOT to FILE.
1150 Callback for htab_traverse. */
1153 dump_recorded_exit (loop_exit **slot, FILE *file)
1155 struct loop_exit *exit = *slot;
1156 unsigned n = 0;
1157 edge e = exit->e;
1159 for (; exit != NULL; exit = exit->next_e)
1160 n++;
1162 fprintf (file, "Edge %d->%d exits %u loops\n",
1163 e->src->index, e->dest->index, n);
1165 return 1;
1168 /* Dumps the recorded exits of loops to FILE. */
1170 extern void dump_recorded_exits (FILE *);
1171 void
1172 dump_recorded_exits (FILE *file)
1174 if (!current_loops->exits)
1175 return;
1176 current_loops->exits->traverse<FILE *, dump_recorded_exit> (file);
1179 /* Releases lists of loop exits. */
1181 void
1182 release_recorded_exits (function *fn)
1184 gcc_assert (loops_state_satisfies_p (fn, LOOPS_HAVE_RECORDED_EXITS));
1185 loops_for_fn (fn)->exits->empty ();
1186 loops_for_fn (fn)->exits = NULL;
1187 loops_state_clear (fn, LOOPS_HAVE_RECORDED_EXITS);
1190 /* Returns the list of the exit edges of a LOOP. */
1192 vec<edge>
1193 get_loop_exit_edges (const class loop *loop)
1195 vec<edge> edges = vNULL;
1196 edge e;
1197 unsigned i;
1198 basic_block *body;
1199 edge_iterator ei;
1200 struct loop_exit *exit;
1202 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1204 /* If we maintain the lists of exits, use them. Otherwise we must
1205 scan the body of the loop. */
1206 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1208 for (exit = loop->exits->next; exit->e; exit = exit->next)
1209 edges.safe_push (exit->e);
1211 else
1213 body = get_loop_body (loop);
1214 for (i = 0; i < loop->num_nodes; i++)
1215 FOR_EACH_EDGE (e, ei, body[i]->succs)
1217 if (!flow_bb_inside_loop_p (loop, e->dest))
1218 edges.safe_push (e);
1220 free (body);
1223 return edges;
1226 /* Counts the number of conditional branches inside LOOP. */
1228 unsigned
1229 num_loop_branches (const class loop *loop)
1231 unsigned i, n;
1232 basic_block * body;
1234 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1236 body = get_loop_body (loop);
1237 n = 0;
1238 for (i = 0; i < loop->num_nodes; i++)
1239 if (EDGE_COUNT (body[i]->succs) >= 2)
1240 n++;
1241 free (body);
1243 return n;
1246 /* Adds basic block BB to LOOP. */
1247 void
1248 add_bb_to_loop (basic_block bb, class loop *loop)
1250 unsigned i;
1251 loop_p ploop;
1252 edge_iterator ei;
1253 edge e;
1255 gcc_assert (bb->loop_father == NULL);
1256 bb->loop_father = loop;
1257 loop->num_nodes++;
1258 FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
1259 ploop->num_nodes++;
1261 FOR_EACH_EDGE (e, ei, bb->succs)
1263 rescan_loop_exit (e, true, false);
1265 FOR_EACH_EDGE (e, ei, bb->preds)
1267 rescan_loop_exit (e, true, false);
1271 /* Remove basic block BB from loops. */
1272 void
1273 remove_bb_from_loops (basic_block bb)
1275 unsigned i;
1276 class loop *loop = bb->loop_father;
1277 loop_p ploop;
1278 edge_iterator ei;
1279 edge e;
1281 gcc_assert (loop != NULL);
1282 loop->num_nodes--;
1283 FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
1284 ploop->num_nodes--;
1285 bb->loop_father = NULL;
1287 FOR_EACH_EDGE (e, ei, bb->succs)
1289 rescan_loop_exit (e, false, true);
1291 FOR_EACH_EDGE (e, ei, bb->preds)
1293 rescan_loop_exit (e, false, true);
1297 /* Finds nearest common ancestor in loop tree for given loops. */
1298 class loop *
1299 find_common_loop (class loop *loop_s, class loop *loop_d)
1301 unsigned sdepth, ddepth;
1303 if (!loop_s) return loop_d;
1304 if (!loop_d) return loop_s;
1306 sdepth = loop_depth (loop_s);
1307 ddepth = loop_depth (loop_d);
1309 if (sdepth < ddepth)
1310 loop_d = (*loop_d->superloops)[sdepth];
1311 else if (sdepth > ddepth)
1312 loop_s = (*loop_s->superloops)[ddepth];
1314 while (loop_s != loop_d)
1316 loop_s = loop_outer (loop_s);
1317 loop_d = loop_outer (loop_d);
1319 return loop_s;
1322 /* Removes LOOP from structures and frees its data. */
1324 void
1325 delete_loop (class loop *loop)
1327 /* Remove the loop from structure. */
1328 flow_loop_tree_node_remove (loop);
1330 /* Remove loop from loops array. */
1331 (*current_loops->larray)[loop->num] = NULL;
1333 /* Free loop data. */
1334 flow_loop_free (loop);
1337 /* Cancels the LOOP; it must be innermost one. */
1339 static void
1340 cancel_loop (class loop *loop)
1342 basic_block *bbs;
1343 unsigned i;
1344 class loop *outer = loop_outer (loop);
1346 gcc_assert (!loop->inner);
1348 /* Move blocks up one level (they should be removed as soon as possible). */
1349 bbs = get_loop_body (loop);
1350 for (i = 0; i < loop->num_nodes; i++)
1351 bbs[i]->loop_father = outer;
1353 free (bbs);
1354 delete_loop (loop);
1357 /* Cancels LOOP and all its subloops. */
1358 void
1359 cancel_loop_tree (class loop *loop)
1361 while (loop->inner)
1362 cancel_loop_tree (loop->inner);
1363 cancel_loop (loop);
1366 /* Disable warnings about missing quoting in GCC diagnostics for
1367 the verification errors. Their format strings don't follow GCC
1368 diagnostic conventions and the calls are ultimately followed by
1369 a deliberate ICE triggered by a failed assertion. */
1370 #if __GNUC__ >= 10
1371 # pragma GCC diagnostic push
1372 # pragma GCC diagnostic ignored "-Wformat-diag"
1373 #endif
1375 /* Checks that information about loops is correct
1376 -- sizes of loops are all right
1377 -- results of get_loop_body really belong to the loop
1378 -- loop header have just single entry edge and single latch edge
1379 -- loop latches have only single successor that is header of their loop
1380 -- irreducible loops are correctly marked
1381 -- the cached loop depth and loop father of each bb is correct
1383 DEBUG_FUNCTION void
1384 verify_loop_structure (void)
1386 unsigned *sizes, i, j;
1387 basic_block bb, *bbs;
1388 class loop *loop;
1389 int err = 0;
1390 edge e;
1391 unsigned num = number_of_loops (cfun);
1392 struct loop_exit *exit, *mexit;
1393 bool dom_available = dom_info_available_p (CDI_DOMINATORS);
1395 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP))
1397 error ("loop verification on loop tree that needs fixup");
1398 err = 1;
1401 /* We need up-to-date dominators, compute or verify them. */
1402 if (!dom_available)
1403 calculate_dominance_info (CDI_DOMINATORS);
1404 else
1405 verify_dominators (CDI_DOMINATORS);
1407 /* Check the loop tree root. */
1408 if (current_loops->tree_root->header != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1409 || current_loops->tree_root->latch != EXIT_BLOCK_PTR_FOR_FN (cfun)
1410 || (current_loops->tree_root->num_nodes
1411 != (unsigned) n_basic_blocks_for_fn (cfun)))
1413 error ("corrupt loop tree root");
1414 err = 1;
1417 /* Check the headers. */
1418 FOR_EACH_BB_FN (bb, cfun)
1419 if (bb_loop_header_p (bb))
1421 if (bb->loop_father->header == NULL)
1423 error ("loop with header %d marked for removal", bb->index);
1424 err = 1;
1426 else if (bb->loop_father->header != bb)
1428 error ("loop with header %d not in loop tree", bb->index);
1429 err = 1;
1432 else if (bb->loop_father->header == bb)
1434 error ("non-loop with header %d not marked for removal", bb->index);
1435 err = 1;
1438 /* Check the recorded loop father and sizes of loops. */
1439 auto_sbitmap visited (last_basic_block_for_fn (cfun));
1440 bitmap_clear (visited);
1441 bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
1442 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1444 unsigned n;
1446 if (loop->header == NULL)
1448 error ("removed loop %d in loop tree", loop->num);
1449 err = 1;
1450 continue;
1453 n = get_loop_body_with_size (loop, bbs, n_basic_blocks_for_fn (cfun));
1454 if (loop->num_nodes != n)
1456 error ("size of loop %d should be %d, not %d",
1457 loop->num, n, loop->num_nodes);
1458 err = 1;
1461 for (j = 0; j < n; j++)
1463 bb = bbs[j];
1465 if (!flow_bb_inside_loop_p (loop, bb))
1467 error ("bb %d does not belong to loop %d",
1468 bb->index, loop->num);
1469 err = 1;
1472 /* Ignore this block if it is in an inner loop. */
1473 if (bitmap_bit_p (visited, bb->index))
1474 continue;
1475 bitmap_set_bit (visited, bb->index);
1477 if (bb->loop_father != loop)
1479 error ("bb %d has father loop %d, should be loop %d",
1480 bb->index, bb->loop_father->num, loop->num);
1481 err = 1;
1485 free (bbs);
1487 /* Check headers and latches. */
1488 FOR_EACH_LOOP (loop, 0)
1490 i = loop->num;
1491 if (loop->header == NULL)
1492 continue;
1493 if (!bb_loop_header_p (loop->header))
1495 error ("loop %d%'s header is not a loop header", i);
1496 err = 1;
1498 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
1499 && EDGE_COUNT (loop->header->preds) != 2)
1501 error ("loop %d%'s header does not have exactly 2 entries", i);
1502 err = 1;
1504 if (loop->latch)
1506 if (!find_edge (loop->latch, loop->header))
1508 error ("loop %d%'s latch does not have an edge to its header", i);
1509 err = 1;
1511 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, loop->header))
1513 error ("loop %d%'s latch is not dominated by its header", i);
1514 err = 1;
1517 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
1519 if (!single_succ_p (loop->latch))
1521 error ("loop %d%'s latch does not have exactly 1 successor", i);
1522 err = 1;
1524 if (single_succ (loop->latch) != loop->header)
1526 error ("loop %d%'s latch does not have header as successor", i);
1527 err = 1;
1529 if (loop->latch->loop_father != loop)
1531 error ("loop %d%'s latch does not belong directly to it", i);
1532 err = 1;
1535 if (loop->header->loop_father != loop)
1537 error ("loop %d%'s header does not belong directly to it", i);
1538 err = 1;
1540 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1541 && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
1543 error ("loop %d%'s latch is marked as part of irreducible region", i);
1544 err = 1;
1548 /* Check irreducible loops. */
1549 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1551 auto_edge_flag saved_irr_mask (cfun);
1552 /* Record old info. */
1553 auto_sbitmap irreds (last_basic_block_for_fn (cfun));
1554 FOR_EACH_BB_FN (bb, cfun)
1556 edge_iterator ei;
1557 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1558 bitmap_set_bit (irreds, bb->index);
1559 else
1560 bitmap_clear_bit (irreds, bb->index);
1561 FOR_EACH_EDGE (e, ei, bb->succs)
1562 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1563 e->flags |= saved_irr_mask;
1566 /* Recount it. */
1567 mark_irreducible_loops ();
1569 /* Compare. */
1570 FOR_EACH_BB_FN (bb, cfun)
1572 edge_iterator ei;
1574 if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1575 && !bitmap_bit_p (irreds, bb->index))
1577 error ("basic block %d should be marked irreducible", bb->index);
1578 err = 1;
1580 else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1581 && bitmap_bit_p (irreds, bb->index))
1583 error ("basic block %d should not be marked irreducible", bb->index);
1584 err = 1;
1586 FOR_EACH_EDGE (e, ei, bb->succs)
1588 if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1589 && !(e->flags & saved_irr_mask))
1591 error ("edge from %d to %d should be marked irreducible",
1592 e->src->index, e->dest->index);
1593 err = 1;
1595 else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1596 && (e->flags & saved_irr_mask))
1598 error ("edge from %d to %d should not be marked irreducible",
1599 e->src->index, e->dest->index);
1600 err = 1;
1602 e->flags &= ~saved_irr_mask;
1607 /* Check the recorded loop exits. */
1608 FOR_EACH_LOOP (loop, 0)
1610 if (!loop->exits || loop->exits->e != NULL)
1612 error ("corrupted head of the exits list of loop %d",
1613 loop->num);
1614 err = 1;
1616 else
1618 /* Check that the list forms a cycle, and all elements except
1619 for the head are nonnull. */
1620 for (mexit = loop->exits, exit = mexit->next, i = 0;
1621 exit->e && exit != mexit;
1622 exit = exit->next)
1624 if (i++ & 1)
1625 mexit = mexit->next;
1628 if (exit != loop->exits)
1630 error ("corrupted exits list of loop %d", loop->num);
1631 err = 1;
1635 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1637 if (loop->exits->next != loop->exits)
1639 error ("nonempty exits list of loop %d, but exits are not recorded",
1640 loop->num);
1641 err = 1;
1646 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1648 unsigned n_exits = 0, eloops;
1650 sizes = XCNEWVEC (unsigned, num);
1651 memset (sizes, 0, sizeof (unsigned) * num);
1652 FOR_EACH_BB_FN (bb, cfun)
1654 edge_iterator ei;
1655 if (bb->loop_father == current_loops->tree_root)
1656 continue;
1657 FOR_EACH_EDGE (e, ei, bb->succs)
1659 if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
1660 continue;
1662 n_exits++;
1663 exit = get_exit_descriptions (e);
1664 if (!exit)
1666 error ("exit %d->%d not recorded",
1667 e->src->index, e->dest->index);
1668 err = 1;
1670 eloops = 0;
1671 for (; exit; exit = exit->next_e)
1672 eloops++;
1674 for (loop = bb->loop_father;
1675 loop != e->dest->loop_father
1676 /* When a loop exit is also an entry edge which
1677 can happen when avoiding CFG manipulations
1678 then the last loop exited is the outer loop
1679 of the loop entered. */
1680 && loop != loop_outer (e->dest->loop_father);
1681 loop = loop_outer (loop))
1683 eloops--;
1684 sizes[loop->num]++;
1687 if (eloops != 0)
1689 error ("wrong list of exited loops for edge %d->%d",
1690 e->src->index, e->dest->index);
1691 err = 1;
1696 if (n_exits != current_loops->exits->elements ())
1698 error ("too many loop exits recorded");
1699 err = 1;
1702 FOR_EACH_LOOP (loop, 0)
1704 eloops = 0;
1705 for (exit = loop->exits->next; exit->e; exit = exit->next)
1706 eloops++;
1707 if (eloops != sizes[loop->num])
1709 error ("%d exits recorded for loop %d (having %d exits)",
1710 eloops, loop->num, sizes[loop->num]);
1711 err = 1;
1715 free (sizes);
1718 gcc_assert (!err);
1720 if (!dom_available)
1721 free_dominance_info (CDI_DOMINATORS);
1724 #if __GNUC__ >= 10
1725 # pragma GCC diagnostic pop
1726 #endif
1728 /* Returns latch edge of LOOP. */
1729 edge
1730 loop_latch_edge (const class loop *loop)
1732 return find_edge (loop->latch, loop->header);
1735 /* Returns preheader edge of LOOP. */
1736 edge
1737 loop_preheader_edge (const class loop *loop)
1739 edge e;
1740 edge_iterator ei;
1742 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
1743 && ! loops_state_satisfies_p (LOOPS_MAY_HAVE_MULTIPLE_LATCHES));
1745 FOR_EACH_EDGE (e, ei, loop->header->preds)
1746 if (e->src != loop->latch)
1747 break;
1749 if (! e)
1751 gcc_assert (! loop_outer (loop));
1752 return single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1755 return e;
1758 /* Returns true if E is an exit of LOOP. */
1760 bool
1761 loop_exit_edge_p (const class loop *loop, const_edge e)
1763 return (flow_bb_inside_loop_p (loop, e->src)
1764 && !flow_bb_inside_loop_p (loop, e->dest));
1767 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1768 or more than one exit. If loops do not have the exits recorded, NULL
1769 is returned always. */
1771 edge
1772 single_exit (const class loop *loop)
1774 struct loop_exit *exit = loop->exits->next;
1776 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1777 return NULL;
1779 if (exit->e && exit->next == loop->exits)
1780 return exit->e;
1781 else
1782 return NULL;
1785 /* Returns true when BB has an incoming edge exiting LOOP. */
1787 bool
1788 loop_exits_to_bb_p (class loop *loop, basic_block bb)
1790 edge e;
1791 edge_iterator ei;
1793 FOR_EACH_EDGE (e, ei, bb->preds)
1794 if (loop_exit_edge_p (loop, e))
1795 return true;
1797 return false;
1800 /* Returns true when BB has an outgoing edge exiting LOOP. */
1802 bool
1803 loop_exits_from_bb_p (class loop *loop, basic_block bb)
1805 edge e;
1806 edge_iterator ei;
1808 FOR_EACH_EDGE (e, ei, bb->succs)
1809 if (loop_exit_edge_p (loop, e))
1810 return true;
1812 return false;
1815 /* Return location corresponding to the loop control condition if possible. */
1817 dump_user_location_t
1818 get_loop_location (class loop *loop)
1820 rtx_insn *insn = NULL;
1821 class niter_desc *desc = NULL;
1822 edge exit;
1824 /* For a for or while loop, we would like to return the location
1825 of the for or while statement, if possible. To do this, look
1826 for the branch guarding the loop back-edge. */
1828 /* If this is a simple loop with an in_edge, then the loop control
1829 branch is typically at the end of its source. */
1830 desc = get_simple_loop_desc (loop);
1831 if (desc->in_edge)
1833 FOR_BB_INSNS_REVERSE (desc->in_edge->src, insn)
1835 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1836 return insn;
1839 /* If loop has a single exit, then the loop control branch
1840 must be at the end of its source. */
1841 if ((exit = single_exit (loop)))
1843 FOR_BB_INSNS_REVERSE (exit->src, insn)
1845 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1846 return insn;
1849 /* Next check the latch, to see if it is non-empty. */
1850 FOR_BB_INSNS_REVERSE (loop->latch, insn)
1852 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1853 return insn;
1855 /* Finally, if none of the above identifies the loop control branch,
1856 return the first location in the loop header. */
1857 FOR_BB_INSNS (loop->header, insn)
1859 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1860 return insn;
1862 /* If all else fails, simply return the current function location. */
1863 return dump_user_location_t::from_function_decl (current_function_decl);
1866 /* Records that every statement in LOOP is executed I_BOUND times.
1867 REALISTIC is true if I_BOUND is expected to be close to the real number
1868 of iterations. UPPER is true if we are sure the loop iterates at most
1869 I_BOUND times. */
1871 void
1872 record_niter_bound (class loop *loop, const widest_int &i_bound,
1873 bool realistic, bool upper)
1875 /* Update the bounds only when there is no previous estimation, or when the
1876 current estimation is smaller. */
1877 if (upper
1878 && (!loop->any_upper_bound
1879 || wi::ltu_p (i_bound, loop->nb_iterations_upper_bound)))
1881 loop->any_upper_bound = true;
1882 loop->nb_iterations_upper_bound = i_bound;
1883 if (!loop->any_likely_upper_bound)
1885 loop->any_likely_upper_bound = true;
1886 loop->nb_iterations_likely_upper_bound = i_bound;
1889 if (realistic
1890 && (!loop->any_estimate
1891 || wi::ltu_p (i_bound, loop->nb_iterations_estimate)))
1893 loop->any_estimate = true;
1894 loop->nb_iterations_estimate = i_bound;
1896 if (!realistic
1897 && (!loop->any_likely_upper_bound
1898 || wi::ltu_p (i_bound, loop->nb_iterations_likely_upper_bound)))
1900 loop->any_likely_upper_bound = true;
1901 loop->nb_iterations_likely_upper_bound = i_bound;
1904 /* If an upper bound is smaller than the realistic estimate of the
1905 number of iterations, use the upper bound instead. */
1906 if (loop->any_upper_bound
1907 && loop->any_estimate
1908 && wi::ltu_p (loop->nb_iterations_upper_bound,
1909 loop->nb_iterations_estimate))
1910 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
1911 if (loop->any_upper_bound
1912 && loop->any_likely_upper_bound
1913 && wi::ltu_p (loop->nb_iterations_upper_bound,
1914 loop->nb_iterations_likely_upper_bound))
1915 loop->nb_iterations_likely_upper_bound = loop->nb_iterations_upper_bound;
1918 /* Similar to get_estimated_loop_iterations, but returns the estimate only
1919 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1920 on the number of iterations of LOOP could not be derived, returns -1. */
1922 HOST_WIDE_INT
1923 get_estimated_loop_iterations_int (class loop *loop)
1925 widest_int nit;
1926 HOST_WIDE_INT hwi_nit;
1928 if (!get_estimated_loop_iterations (loop, &nit))
1929 return -1;
1931 if (!wi::fits_shwi_p (nit))
1932 return -1;
1933 hwi_nit = nit.to_shwi ();
1935 return hwi_nit < 0 ? -1 : hwi_nit;
1938 /* Returns an upper bound on the number of executions of statements
1939 in the LOOP. For statements before the loop exit, this exceeds
1940 the number of execution of the latch by one. */
1942 HOST_WIDE_INT
1943 max_stmt_executions_int (class loop *loop)
1945 HOST_WIDE_INT nit = get_max_loop_iterations_int (loop);
1946 HOST_WIDE_INT snit;
1948 if (nit == -1)
1949 return -1;
1951 snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
1953 /* If the computation overflows, return -1. */
1954 return snit < 0 ? -1 : snit;
1957 /* Returns an likely upper bound on the number of executions of statements
1958 in the LOOP. For statements before the loop exit, this exceeds
1959 the number of execution of the latch by one. */
1961 HOST_WIDE_INT
1962 likely_max_stmt_executions_int (class loop *loop)
1964 HOST_WIDE_INT nit = get_likely_max_loop_iterations_int (loop);
1965 HOST_WIDE_INT snit;
1967 if (nit == -1)
1968 return -1;
1970 snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
1972 /* If the computation overflows, return -1. */
1973 return snit < 0 ? -1 : snit;
1976 /* Sets NIT to the estimated number of executions of the latch of the
1977 LOOP. If we have no reliable estimate, the function returns false, otherwise
1978 returns true. */
1980 bool
1981 get_estimated_loop_iterations (class loop *loop, widest_int *nit)
1983 /* Even if the bound is not recorded, possibly we can derrive one from
1984 profile. */
1985 if (!loop->any_estimate)
1987 if (loop->header->count.reliable_p ())
1989 *nit = gcov_type_to_wide_int
1990 (expected_loop_iterations_unbounded (loop) + 1);
1991 return true;
1993 return false;
1996 *nit = loop->nb_iterations_estimate;
1997 return true;
2000 /* Sets NIT to an upper bound for the maximum number of executions of the
2001 latch of the LOOP. If we have no reliable estimate, the function returns
2002 false, otherwise returns true. */
2004 bool
2005 get_max_loop_iterations (const class loop *loop, widest_int *nit)
2007 if (!loop->any_upper_bound)
2008 return false;
2010 *nit = loop->nb_iterations_upper_bound;
2011 return true;
2014 /* Similar to get_max_loop_iterations, but returns the estimate only
2015 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
2016 on the number of iterations of LOOP could not be derived, returns -1. */
2018 HOST_WIDE_INT
2019 get_max_loop_iterations_int (const class loop *loop)
2021 widest_int nit;
2022 HOST_WIDE_INT hwi_nit;
2024 if (!get_max_loop_iterations (loop, &nit))
2025 return -1;
2027 if (!wi::fits_shwi_p (nit))
2028 return -1;
2029 hwi_nit = nit.to_shwi ();
2031 return hwi_nit < 0 ? -1 : hwi_nit;
2034 /* Sets NIT to an upper bound for the maximum number of executions of the
2035 latch of the LOOP. If we have no reliable estimate, the function returns
2036 false, otherwise returns true. */
2038 bool
2039 get_likely_max_loop_iterations (class loop *loop, widest_int *nit)
2041 if (!loop->any_likely_upper_bound)
2042 return false;
2044 *nit = loop->nb_iterations_likely_upper_bound;
2045 return true;
2048 /* Similar to get_max_loop_iterations, but returns the estimate only
2049 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
2050 on the number of iterations of LOOP could not be derived, returns -1. */
2052 HOST_WIDE_INT
2053 get_likely_max_loop_iterations_int (class loop *loop)
2055 widest_int nit;
2056 HOST_WIDE_INT hwi_nit;
2058 if (!get_likely_max_loop_iterations (loop, &nit))
2059 return -1;
2061 if (!wi::fits_shwi_p (nit))
2062 return -1;
2063 hwi_nit = nit.to_shwi ();
2065 return hwi_nit < 0 ? -1 : hwi_nit;
2068 /* Returns the loop depth of the loop BB belongs to. */
2071 bb_loop_depth (const_basic_block bb)
2073 return bb->loop_father ? loop_depth (bb->loop_father) : 0;
2076 /* Marks LOOP for removal and sets LOOPS_NEED_FIXUP. */
2078 void
2079 mark_loop_for_removal (loop_p loop)
2081 if (loop->header == NULL)
2082 return;
2083 loop->former_header = loop->header;
2084 loop->header = NULL;
2085 loop->latch = NULL;
2086 loops_state_set (LOOPS_NEED_FIXUP);