1/* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000-2023 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
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"
34#include "tree-ssa.h"
35#include "tree-pretty-print.h"
36#include "sreal.h"
37
38static void flow_loops_cfg_dump (FILE *);
39
40/* Dump loop related CFG information. */
41
42static void
43flow_loops_cfg_dump (FILE *file)
44{
45 basic_block bb;
46
47 if (!file)
48 return;
49
50 FOR_EACH_BB_FN (bb, cfun)
51 {
52 edge succ;
53 edge_iterator ei;
54
55 fprintf (stream: file, format: ";; %d succs { ", bb->index);
56 FOR_EACH_EDGE (succ, ei, bb->succs)
57 fprintf (stream: file, format: "%d ", succ->dest->index);
58 fprintf (stream: file, format: "}\n");
59 }
60}
61
62/* Return nonzero if the nodes of LOOP are a subset of OUTER. */
63
64bool
65flow_loop_nested_p (const class loop *outer, const class loop *loop)
66{
67 unsigned odepth = loop_depth (loop: outer);
68
69 return (loop_depth (loop) > odepth
70 && (*loop->superloops)[odepth] == outer);
71}
72
73/* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
74 loops within LOOP. */
75
76class loop *
77superloop_at_depth (class loop *loop, unsigned depth)
78{
79 unsigned ldepth = loop_depth (loop);
80
81 gcc_assert (depth <= ldepth);
82
83 if (depth == ldepth)
84 return loop;
85
86 return (*loop->superloops)[depth];
87}
88
89/* Returns the list of the latch edges of LOOP. */
90
91static vec<edge>
92get_loop_latch_edges (const class loop *loop)
93{
94 edge_iterator ei;
95 edge e;
96 vec<edge> ret = vNULL;
97
98 FOR_EACH_EDGE (e, ei, loop->header->preds)
99 {
100 if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header))
101 ret.safe_push (obj: e);
102 }
103
104 return ret;
105}
106
107/* Dump the loop information specified by LOOP to the stream FILE
108 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
109
110void
111flow_loop_dump (const class loop *loop, FILE *file,
112 void (*loop_dump_aux) (const class loop *, FILE *, int),
113 int verbose)
114{
115 basic_block *bbs;
116 unsigned i;
117 vec<edge> latches;
118 edge e;
119
120 if (! loop || ! loop->header)
121 return;
122
123 fprintf (stream: file, format: ";;\n;; Loop %d\n", loop->num);
124
125 fprintf (stream: file, format: ";; header %d, ", loop->header->index);
126 if (loop->latch)
127 fprintf (stream: file, format: "latch %d\n", loop->latch->index);
128 else
129 {
130 fprintf (stream: file, format: "multiple latches:");
131 latches = get_loop_latch_edges (loop);
132 FOR_EACH_VEC_ELT (latches, i, e)
133 fprintf (stream: file, format: " %d", e->src->index);
134 latches.release ();
135 fprintf (stream: file, format: "\n");
136 }
137
138 fprintf (stream: file, format: ";; depth %d, outer %ld",
139 loop_depth (loop), (long) (loop_outer (loop)
140 ? loop_outer (loop)->num : -1));
141 print_loop_info (file, loop, ";; ");
142
143 fprintf (stream: file, format: "\n;; nodes:");
144 bbs = get_loop_body (loop);
145 for (i = 0; i < loop->num_nodes; i++)
146 fprintf (stream: file, format: " %d", bbs[i]->index);
147 free (ptr: bbs);
148 fprintf (stream: file, format: "\n");
149
150 if (loop_dump_aux)
151 loop_dump_aux (loop, file, verbose);
152}
153
154/* Dump the loop information about loops to the stream FILE,
155 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
156
157void
158flow_loops_dump (FILE *file, void (*loop_dump_aux) (const class loop *, FILE *, int), int verbose)
159{
160 if (!current_loops || ! file)
161 return;
162
163 fprintf (stream: file, format: ";; %d loops found\n", number_of_loops (cfun));
164
165 for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT))
166 {
167 flow_loop_dump (loop, file, loop_dump_aux, verbose);
168 }
169
170 if (verbose)
171 flow_loops_cfg_dump (file);
172}
173
174/* Free data allocated for LOOP. */
175
176void
177flow_loop_free (class loop *loop)
178{
179 struct loop_exit *exit, *next;
180
181 vec_free (v&: loop->superloops);
182
183 /* Break the list of the loop exit records. They will be freed when the
184 corresponding edge is rescanned or removed, and this avoids
185 accessing the (already released) head of the list stored in the
186 loop structure. */
187 for (exit = loop->exits->next; exit != loop->exits; exit = next)
188 {
189 next = exit->next;
190 exit->next = exit;
191 exit->prev = exit;
192 }
193
194 ggc_free (loop->exits);
195 ggc_free (loop);
196}
197
198/* Free all the memory allocated for LOOPS. */
199
200void
201flow_loops_free (struct loops *loops)
202{
203 if (loops->larray)
204 {
205 unsigned i;
206 loop_p loop;
207
208 /* Free the loop descriptors. */
209 FOR_EACH_VEC_SAFE_ELT (loops->larray, i, loop)
210 {
211 if (!loop)
212 continue;
213
214 flow_loop_free (loop);
215 }
216
217 vec_free (v&: loops->larray);
218 }
219}
220
221/* Find the nodes contained within the LOOP with header HEADER.
222 Return the number of nodes within the loop. */
223
224int
225flow_loop_nodes_find (basic_block header, class loop *loop)
226{
227 vec<basic_block> stack = vNULL;
228 int num_nodes = 1;
229 edge latch;
230 edge_iterator latch_ei;
231
232 header->loop_father = loop;
233
234 FOR_EACH_EDGE (latch, latch_ei, loop->header->preds)
235 {
236 if (latch->src->loop_father == loop
237 || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header))
238 continue;
239
240 num_nodes++;
241 stack.safe_push (obj: latch->src);
242 latch->src->loop_father = loop;
243
244 while (!stack.is_empty ())
245 {
246 basic_block node;
247 edge e;
248 edge_iterator ei;
249
250 node = stack.pop ();
251
252 FOR_EACH_EDGE (e, ei, node->preds)
253 {
254 basic_block ancestor = e->src;
255
256 if (ancestor->loop_father != loop)
257 {
258 ancestor->loop_father = loop;
259 num_nodes++;
260 stack.safe_push (obj: ancestor);
261 }
262 }
263 }
264 }
265 stack.release ();
266
267 return num_nodes;
268}
269
270/* Records the vector of superloops of the loop LOOP, whose immediate
271 superloop is FATHER. */
272
273static void
274establish_preds (class loop *loop, class loop *father)
275{
276 loop_p ploop;
277 unsigned depth = loop_depth (loop: father) + 1;
278 unsigned i;
279
280 loop->superloops = 0;
281 vec_alloc (v&: loop->superloops, nelems: depth);
282 FOR_EACH_VEC_SAFE_ELT (father->superloops, i, ploop)
283 loop->superloops->quick_push (obj: ploop);
284 loop->superloops->quick_push (obj: father);
285
286 for (ploop = loop->inner; ploop; ploop = ploop->next)
287 establish_preds (loop: ploop, father: loop);
288}
289
290/* Add LOOP to the loop hierarchy tree where FATHER is father of the
291 added loop. If LOOP has some children, take care of that their
292 pred field will be initialized correctly. If AFTER is non-null
293 then it's expected it's a pointer into FATHERs inner sibling
294 list and LOOP is added behind AFTER, otherwise it's added in front
295 of FATHERs siblings. */
296
297void
298flow_loop_tree_node_add (class loop *father, class loop *loop,
299 class loop *after)
300{
301 if (after)
302 {
303 loop->next = after->next;
304 after->next = loop;
305 }
306 else
307 {
308 loop->next = father->inner;
309 father->inner = loop;
310 }
311
312 establish_preds (loop, father);
313}
314
315/* Remove LOOP from the loop hierarchy tree. */
316
317void
318flow_loop_tree_node_remove (class loop *loop)
319{
320 class loop *prev, *father;
321
322 father = loop_outer (loop);
323
324 /* Remove loop from the list of sons. */
325 if (father->inner == loop)
326 father->inner = loop->next;
327 else
328 {
329 for (prev = father->inner; prev->next != loop; prev = prev->next)
330 continue;
331 prev->next = loop->next;
332 }
333
334 loop->superloops = NULL;
335}
336
337/* Allocates and returns new loop structure. */
338
339class loop *
340alloc_loop (void)
341{
342 class loop *loop = ggc_cleared_alloc<class loop> ();
343
344 loop->exits = ggc_cleared_alloc<loop_exit> ();
345 loop->exits->next = loop->exits->prev = loop->exits;
346 loop->can_be_parallel = false;
347 loop->constraints = 0;
348 loop->nb_iterations_upper_bound = 0;
349 loop->nb_iterations_likely_upper_bound = 0;
350 loop->nb_iterations_estimate = 0;
351 return loop;
352}
353
354/* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
355 (including the root of the loop tree). */
356
357void
358init_loops_structure (struct function *fn,
359 struct loops *loops, unsigned num_loops)
360{
361 class loop *root;
362
363 memset (s: loops, c: 0, n: sizeof *loops);
364 vec_alloc (v&: loops->larray, nelems: num_loops);
365
366 /* Dummy loop containing whole function. */
367 root = alloc_loop ();
368 root->num_nodes = n_basic_blocks_for_fn (fn);
369 root->latch = EXIT_BLOCK_PTR_FOR_FN (fn);
370 root->header = ENTRY_BLOCK_PTR_FOR_FN (fn);
371 ENTRY_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
372 EXIT_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
373
374 loops->larray->quick_push (obj: root);
375 loops->tree_root = root;
376}
377
378/* Returns whether HEADER is a loop header. */
379
380bool
381bb_loop_header_p (basic_block header)
382{
383 edge_iterator ei;
384 edge e;
385
386 /* If we have an abnormal predecessor, do not consider the
387 loop (not worth the problems). */
388 if (bb_has_abnormal_pred (bb: header))
389 return false;
390
391 /* Look for back edges where a predecessor is dominated
392 by this block. A natural loop has a single entry
393 node (header) that dominates all the nodes in the
394 loop. It also has single back edge to the header
395 from a latch node. */
396 FOR_EACH_EDGE (e, ei, header->preds)
397 {
398 basic_block latch = e->src;
399 if (latch != ENTRY_BLOCK_PTR_FOR_FN (cfun)
400 && dominated_by_p (CDI_DOMINATORS, latch, header))
401 return true;
402 }
403
404 return false;
405}
406
407/* Find all the natural loops in the function and save in LOOPS structure and
408 recalculate loop_father information in basic block structures.
409 If LOOPS is non-NULL then the loop structures for already recorded loops
410 will be re-used and their number will not change. We assume that no
411 stale loops exist in LOOPS.
412 When LOOPS is NULL it is allocated and re-built from scratch.
413 Return the built LOOPS structure. */
414
415struct loops *
416flow_loops_find (struct loops *loops)
417{
418 bool from_scratch = (loops == NULL);
419 int *rc_order;
420 int b;
421 unsigned i;
422
423 /* Ensure that the dominators are computed. */
424 calculate_dominance_info (CDI_DOMINATORS);
425
426 if (!loops)
427 {
428 loops = ggc_cleared_alloc<struct loops> ();
429 init_loops_structure (cfun, loops, num_loops: 1);
430 }
431
432 /* Ensure that loop exits were released. */
433 gcc_assert (loops->exits == NULL);
434
435 /* Taking care of this degenerate case makes the rest of
436 this code simpler. */
437 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
438 return loops;
439
440 /* The root loop node contains all basic-blocks. */
441 loops->tree_root->num_nodes = n_basic_blocks_for_fn (cfun);
442
443 /* Compute depth first search order of the CFG so that outer
444 natural loops will be found before inner natural loops. */
445 rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
446 pre_and_rev_post_order_compute (NULL, rc_order, false);
447
448 /* Gather all loop headers in reverse completion order and allocate
449 loop structures for loops that are not already present. */
450 auto_vec<loop_p> larray (loops->larray->length ());
451 for (b = 0; b < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; b++)
452 {
453 basic_block header = BASIC_BLOCK_FOR_FN (cfun, rc_order[b]);
454 if (bb_loop_header_p (header))
455 {
456 class loop *loop;
457
458 /* The current active loop tree has valid loop-fathers for
459 header blocks. */
460 if (!from_scratch
461 && header->loop_father->header == header)
462 {
463 loop = header->loop_father;
464 /* If we found an existing loop remove it from the
465 loop tree. It is going to be inserted again
466 below. */
467 flow_loop_tree_node_remove (loop);
468 }
469 else
470 {
471 /* Otherwise allocate a new loop structure for the loop. */
472 loop = alloc_loop ();
473 /* ??? We could re-use unused loop slots here. */
474 loop->num = loops->larray->length ();
475 vec_safe_push (v&: loops->larray, obj: loop);
476 loop->header = header;
477
478 if (!from_scratch
479 && dump_file && (dump_flags & TDF_DETAILS))
480 fprintf (stream: dump_file, format: "flow_loops_find: discovered new "
481 "loop %d with header %d\n",
482 loop->num, header->index);
483 }
484 /* Reset latch, we recompute it below. */
485 loop->latch = NULL;
486 larray.safe_push (obj: loop);
487 }
488
489 /* Make blocks part of the loop root node at start. */
490 header->loop_father = loops->tree_root;
491 }
492
493 free (ptr: rc_order);
494
495 /* Now iterate over the loops found, insert them into the loop tree
496 and assign basic-block ownership. */
497 for (i = 0; i < larray.length (); ++i)
498 {
499 class loop *loop = larray[i];
500 basic_block header = loop->header;
501 edge_iterator ei;
502 edge e;
503
504 flow_loop_tree_node_add (father: header->loop_father, loop);
505 loop->num_nodes = flow_loop_nodes_find (header: loop->header, loop);
506
507 /* Look for the latch for this header block, if it has just a
508 single one. */
509 FOR_EACH_EDGE (e, ei, header->preds)
510 {
511 basic_block latch = e->src;
512
513 if (flow_bb_inside_loop_p (loop, latch))
514 {
515 if (loop->latch != NULL)
516 {
517 /* More than one latch edge. */
518 loop->latch = NULL;
519 break;
520 }
521 loop->latch = latch;
522 }
523 }
524 }
525
526 return loops;
527}
528
529/* qsort helper for sort_sibling_loops. */
530
531static int *sort_sibling_loops_cmp_rpo;
532static int
533sort_sibling_loops_cmp (const void *la_, const void *lb_)
534{
535 const class loop *la = *(const class loop * const *)la_;
536 const class loop *lb = *(const class loop * const *)lb_;
537 return (sort_sibling_loops_cmp_rpo[la->header->index]
538 - sort_sibling_loops_cmp_rpo[lb->header->index]);
539}
540
541/* Sort sibling loops in RPO order. */
542
543void
544sort_sibling_loops (function *fn)
545{
546 /* Match flow_loops_find in the order we sort sibling loops. */
547 sort_sibling_loops_cmp_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
548 int *rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
549 pre_and_rev_post_order_compute_fn (fn, NULL, rc_order, false);
550 for (int i = 0; i < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; ++i)
551 sort_sibling_loops_cmp_rpo[rc_order[i]] = i;
552 free (ptr: rc_order);
553
554 auto_vec<loop_p, 3> siblings;
555 for (auto loop : loops_list (fn, LI_INCLUDE_ROOT))
556 if (loop->inner && loop->inner->next)
557 {
558 loop_p sibling = loop->inner;
559 do
560 {
561 siblings.safe_push (obj: sibling);
562 sibling = sibling->next;
563 }
564 while (sibling);
565 siblings.qsort (sort_sibling_loops_cmp);
566 loop_p *siblingp = &loop->inner;
567 for (unsigned i = 0; i < siblings.length (); ++i)
568 {
569 *siblingp = siblings[i];
570 siblingp = &(*siblingp)->next;
571 }
572 *siblingp = NULL;
573 siblings.truncate (size: 0);
574 }
575
576 free (ptr: sort_sibling_loops_cmp_rpo);
577 sort_sibling_loops_cmp_rpo = NULL;
578}
579
580/* Ratio of frequencies of edges so that one of more latch edges is
581 considered to belong to inner loop with same header. */
582#define HEAVY_EDGE_RATIO 8
583
584/* Minimum number of samples for that we apply
585 find_subloop_latch_edge_by_profile heuristics. */
586#define HEAVY_EDGE_MIN_SAMPLES 10
587
588/* If the profile info is available, finds an edge in LATCHES that much more
589 frequent than the remaining edges. Returns such an edge, or NULL if we do
590 not find one.
591
592 We do not use guessed profile here, only the measured one. The guessed
593 profile is usually too flat and unreliable for this (and it is mostly based
594 on the loop structure of the program, so it does not make much sense to
595 derive the loop structure from it). */
596
597static edge
598find_subloop_latch_edge_by_profile (vec<edge> latches)
599{
600 unsigned i;
601 edge e, me = NULL;
602 profile_count mcount = profile_count::zero (), tcount = profile_count::zero ();
603
604 FOR_EACH_VEC_ELT (latches, i, e)
605 {
606 if (e->count ()> mcount)
607 {
608 me = e;
609 mcount = e->count();
610 }
611 tcount += e->count();
612 }
613
614 if (!tcount.initialized_p () || !(tcount.ipa () > HEAVY_EDGE_MIN_SAMPLES)
615 || (tcount - mcount) * HEAVY_EDGE_RATIO > tcount)
616 return NULL;
617
618 if (dump_file)
619 fprintf (stream: dump_file,
620 format: "Found latch edge %d -> %d using profile information.\n",
621 me->src->index, me->dest->index);
622 return me;
623}
624
625/* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
626 on the structure of induction variables. Returns this edge, or NULL if we
627 do not find any.
628
629 We are quite conservative, and look just for an obvious simple innermost
630 loop (which is the case where we would lose the most performance by not
631 disambiguating the loop). More precisely, we look for the following
632 situation: The source of the chosen latch edge dominates sources of all
633 the other latch edges. Additionally, the header does not contain a phi node
634 such that the argument from the chosen edge is equal to the argument from
635 another edge. */
636
637static edge
638find_subloop_latch_edge_by_ivs (class loop *loop ATTRIBUTE_UNUSED, vec<edge> latches)
639{
640 edge e, latch = latches[0];
641 unsigned i;
642 gphi *phi;
643 gphi_iterator psi;
644 tree lop;
645 basic_block bb;
646
647 /* Find the candidate for the latch edge. */
648 for (i = 1; latches.iterate (ix: i, ptr: &e); i++)
649 if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src))
650 latch = e;
651
652 /* Verify that it dominates all the latch edges. */
653 FOR_EACH_VEC_ELT (latches, i, e)
654 if (!dominated_by_p (CDI_DOMINATORS, e->src, latch->src))
655 return NULL;
656
657 /* Check for a phi node that would deny that this is a latch edge of
658 a subloop. */
659 for (psi = gsi_start_phis (loop->header); !gsi_end_p (i: psi); gsi_next (i: &psi))
660 {
661 phi = psi.phi ();
662 lop = PHI_ARG_DEF_FROM_EDGE (phi, latch);
663
664 /* Ignore the values that are not changed inside the subloop. */
665 if (TREE_CODE (lop) != SSA_NAME
666 || SSA_NAME_DEF_STMT (lop) == phi)
667 continue;
668 bb = gimple_bb (SSA_NAME_DEF_STMT (lop));
669 if (!bb || !flow_bb_inside_loop_p (loop, bb))
670 continue;
671
672 FOR_EACH_VEC_ELT (latches, i, e)
673 if (e != latch
674 && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop)
675 return NULL;
676 }
677
678 if (dump_file)
679 fprintf (stream: dump_file,
680 format: "Found latch edge %d -> %d using iv structure.\n",
681 latch->src->index, latch->dest->index);
682 return latch;
683}
684
685/* If we can determine that one of the several latch edges of LOOP behaves
686 as a latch edge of a separate subloop, returns this edge. Otherwise
687 returns NULL. */
688
689static edge
690find_subloop_latch_edge (class loop *loop)
691{
692 vec<edge> latches = get_loop_latch_edges (loop);
693 edge latch = NULL;
694
695 if (latches.length () > 1)
696 {
697 latch = find_subloop_latch_edge_by_profile (latches);
698
699 if (!latch
700 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
701 should use cfghook for this, but it is hard to imagine it would
702 be useful elsewhere. */
703 && current_ir_type () == IR_GIMPLE)
704 latch = find_subloop_latch_edge_by_ivs (loop, latches);
705 }
706
707 latches.release ();
708 return latch;
709}
710
711/* Callback for make_forwarder_block. Returns true if the edge E is marked
712 in the set MFB_REIS_SET. */
713
714static hash_set<edge> *mfb_reis_set;
715static bool
716mfb_redirect_edges_in_set (edge e)
717{
718 return mfb_reis_set->contains (k: e);
719}
720
721/* Creates a subloop of LOOP with latch edge LATCH. */
722
723static void
724form_subloop (class loop *loop, edge latch)
725{
726 edge_iterator ei;
727 edge e, new_entry;
728 class loop *new_loop;
729
730 mfb_reis_set = new hash_set<edge>;
731 FOR_EACH_EDGE (e, ei, loop->header->preds)
732 {
733 if (e != latch)
734 mfb_reis_set->add (k: e);
735 }
736 new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
737 NULL);
738 delete mfb_reis_set;
739
740 loop->header = new_entry->src;
741
742 /* Find the blocks and subloops that belong to the new loop, and add it to
743 the appropriate place in the loop tree. */
744 new_loop = alloc_loop ();
745 new_loop->header = new_entry->dest;
746 new_loop->latch = latch->src;
747 add_loop (new_loop, loop);
748}
749
750/* Make all the latch edges of LOOP to go to a single forwarder block --
751 a new latch of LOOP. */
752
753static void
754merge_latch_edges (class loop *loop)
755{
756 vec<edge> latches = get_loop_latch_edges (loop);
757 edge latch, e;
758 unsigned i;
759
760 gcc_assert (latches.length () > 0);
761
762 if (latches.length () == 1)
763 loop->latch = latches[0]->src;
764 else
765 {
766 if (dump_file)
767 fprintf (stream: dump_file, format: "Merged latch edges of loop %d\n", loop->num);
768
769 mfb_reis_set = new hash_set<edge>;
770 FOR_EACH_VEC_ELT (latches, i, e)
771 mfb_reis_set->add (k: e);
772 latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
773 NULL);
774 delete mfb_reis_set;
775
776 loop->header = latch->dest;
777 loop->latch = latch->src;
778 }
779
780 latches.release ();
781}
782
783/* LOOP may have several latch edges. Transform it into (possibly several)
784 loops with single latch edge. */
785
786static void
787disambiguate_multiple_latches (class loop *loop)
788{
789 edge e;
790
791 /* We eliminate the multiple latches by splitting the header to the forwarder
792 block F and the rest R, and redirecting the edges. There are two cases:
793
794 1) If there is a latch edge E that corresponds to a subloop (we guess
795 that based on profile -- if it is taken much more often than the
796 remaining edges; and on trees, using the information about induction
797 variables of the loops), we redirect E to R, all the remaining edges to
798 F, then rescan the loops and try again for the outer loop.
799 2) If there is no such edge, we redirect all latch edges to F, and the
800 entry edges to R, thus making F the single latch of the loop. */
801
802 if (dump_file)
803 fprintf (stream: dump_file, format: "Disambiguating loop %d with multiple latches\n",
804 loop->num);
805
806 /* During latch merging, we may need to redirect the entry edges to a new
807 block. This would cause problems if the entry edge was the one from the
808 entry block. To avoid having to handle this case specially, split
809 such entry edge. */
810 e = find_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), loop->header);
811 if (e)
812 split_edge (e);
813
814 while (1)
815 {
816 e = find_subloop_latch_edge (loop);
817 if (!e)
818 break;
819
820 form_subloop (loop, latch: e);
821 }
822
823 merge_latch_edges (loop);
824}
825
826/* Split loops with multiple latch edges. */
827
828void
829disambiguate_loops_with_multiple_latches (void)
830{
831 for (auto loop : loops_list (cfun, 0))
832 {
833 if (!loop->latch)
834 disambiguate_multiple_latches (loop);
835 }
836}
837
838/* Return nonzero if basic block BB belongs to LOOP. */
839bool
840flow_bb_inside_loop_p (const class loop *loop, const_basic_block bb)
841{
842 class loop *source_loop;
843
844 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
845 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
846 return 0;
847
848 source_loop = bb->loop_father;
849 return loop == source_loop || flow_loop_nested_p (outer: loop, loop: source_loop);
850}
851
852/* Enumeration predicate for get_loop_body_with_size. */
853static bool
854glb_enum_p (const_basic_block bb, const void *glb_loop)
855{
856 const class loop *const loop = (const class loop *) glb_loop;
857 return (bb != loop->header
858 && dominated_by_p (CDI_DOMINATORS, bb, loop->header));
859}
860
861/* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
862 order against direction of edges from latch. Specially, if
863 header != latch, latch is the 1-st block. LOOP cannot be the fake
864 loop tree root, and its size must be at most MAX_SIZE. The blocks
865 in the LOOP body are stored to BODY, and the size of the LOOP is
866 returned. */
867
868unsigned
869get_loop_body_with_size (const class loop *loop, basic_block *body,
870 unsigned max_size)
871{
872 return dfs_enumerate_from (loop->header, 1, glb_enum_p,
873 body, max_size, loop);
874}
875
876/* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
877 order against direction of edges from latch. Specially, if
878 header != latch, latch is the 1-st block. */
879
880basic_block *
881get_loop_body (const class loop *loop)
882{
883 basic_block *body, bb;
884 unsigned tv = 0;
885
886 gcc_assert (loop->num_nodes);
887
888 body = XNEWVEC (basic_block, loop->num_nodes);
889
890 if (loop->latch == EXIT_BLOCK_PTR_FOR_FN (cfun))
891 {
892 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
893 special-case the fake loop that contains the whole function. */
894 gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks_for_fn (cfun));
895 body[tv++] = loop->header;
896 body[tv++] = EXIT_BLOCK_PTR_FOR_FN (cfun);
897 FOR_EACH_BB_FN (bb, cfun)
898 body[tv++] = bb;
899 }
900 else
901 tv = get_loop_body_with_size (loop, body, max_size: loop->num_nodes);
902
903 gcc_assert (tv == loop->num_nodes);
904 return body;
905}
906
907/* Fills dominance descendants inside LOOP of the basic block BB into
908 array TOVISIT from index *TV. */
909
910static void
911fill_sons_in_loop (const class loop *loop, basic_block bb,
912 basic_block *tovisit, int *tv)
913{
914 basic_block son, postpone = NULL;
915
916 tovisit[(*tv)++] = bb;
917 for (son = first_dom_son (CDI_DOMINATORS, bb);
918 son;
919 son = next_dom_son (CDI_DOMINATORS, son))
920 {
921 if (!flow_bb_inside_loop_p (loop, bb: son))
922 continue;
923
924 if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
925 {
926 postpone = son;
927 continue;
928 }
929 fill_sons_in_loop (loop, bb: son, tovisit, tv);
930 }
931
932 if (postpone)
933 fill_sons_in_loop (loop, bb: postpone, tovisit, tv);
934}
935
936/* Gets body of a LOOP (that must be different from the outermost loop)
937 sorted by dominance relation. Additionally, if a basic block s dominates
938 the latch, then only blocks dominated by s are be after it. */
939
940basic_block *
941get_loop_body_in_dom_order (const class loop *loop)
942{
943 basic_block *tovisit;
944 int tv;
945
946 gcc_assert (loop->num_nodes);
947
948 tovisit = XNEWVEC (basic_block, loop->num_nodes);
949
950 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
951
952 tv = 0;
953 fill_sons_in_loop (loop, bb: loop->header, tovisit, tv: &tv);
954
955 gcc_assert (tv == (int) loop->num_nodes);
956
957 return tovisit;
958}
959
960/* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
961
962basic_block *
963get_loop_body_in_custom_order (const class loop *loop,
964 int (*bb_comparator) (const void *, const void *))
965{
966 basic_block *bbs = get_loop_body (loop);
967
968 qsort (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator);
969
970 return bbs;
971}
972
973/* Same as above, but use gcc_sort_r instead of qsort. */
974
975basic_block *
976get_loop_body_in_custom_order (const class loop *loop, void *data,
977 int (*bb_comparator) (const void *, const void *, void *))
978{
979 basic_block *bbs = get_loop_body (loop);
980
981 gcc_sort_r (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator, data);
982
983 return bbs;
984}
985
986/* Get body of a LOOP in breadth first sort order. */
987
988basic_block *
989get_loop_body_in_bfs_order (const class loop *loop)
990{
991 basic_block *blocks;
992 basic_block bb;
993 unsigned int i = 1;
994 unsigned int vc = 0;
995
996 gcc_assert (loop->num_nodes);
997 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
998
999 blocks = XNEWVEC (basic_block, loop->num_nodes);
1000 auto_bitmap visited;
1001 blocks[0] = loop->header;
1002 bitmap_set_bit (visited, loop->header->index);
1003 while (i < loop->num_nodes)
1004 {
1005 edge e;
1006 edge_iterator ei;
1007 gcc_assert (i > vc);
1008 bb = blocks[vc++];
1009
1010 FOR_EACH_EDGE (e, ei, bb->succs)
1011 {
1012 if (flow_bb_inside_loop_p (loop, bb: e->dest))
1013 {
1014 /* This bb is now visited. */
1015 if (bitmap_set_bit (visited, e->dest->index))
1016 blocks[i++] = e->dest;
1017 }
1018 }
1019 }
1020
1021 return blocks;
1022}
1023
1024/* Hash function for struct loop_exit. */
1025
1026hashval_t
1027loop_exit_hasher::hash (loop_exit *exit)
1028{
1029 return htab_hash_pointer (exit->e);
1030}
1031
1032/* Equality function for struct loop_exit. Compares with edge. */
1033
1034bool
1035loop_exit_hasher::equal (loop_exit *exit, edge e)
1036{
1037 return exit->e == e;
1038}
1039
1040/* Frees the list of loop exit descriptions EX. */
1041
1042void
1043loop_exit_hasher::remove (loop_exit *exit)
1044{
1045 loop_exit *next;
1046 for (; exit; exit = next)
1047 {
1048 next = exit->next_e;
1049
1050 exit->next->prev = exit->prev;
1051 exit->prev->next = exit->next;
1052
1053 ggc_free (exit);
1054 }
1055}
1056
1057/* Returns the list of records for E as an exit of a loop. */
1058
1059static struct loop_exit *
1060get_exit_descriptions (edge e)
1061{
1062 return current_loops->exits->find_with_hash (comparable: e, hash: htab_hash_pointer (e));
1063}
1064
1065/* Updates the lists of loop exits in that E appears.
1066 If REMOVED is true, E is being removed, and we
1067 just remove it from the lists of exits.
1068 If NEW_EDGE is true and E is not a loop exit, we
1069 do not try to remove it from loop exit lists. */
1070
1071void
1072rescan_loop_exit (edge e, bool new_edge, bool removed)
1073{
1074 struct loop_exit *exits = NULL, *exit;
1075 class loop *aloop, *cloop;
1076
1077 if (!loops_state_satisfies_p (flags: LOOPS_HAVE_RECORDED_EXITS))
1078 return;
1079
1080 if (!removed
1081 && e->src->loop_father != NULL
1082 && e->dest->loop_father != NULL
1083 && !flow_bb_inside_loop_p (loop: e->src->loop_father, bb: e->dest))
1084 {
1085 cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
1086 for (aloop = e->src->loop_father;
1087 aloop != cloop;
1088 aloop = loop_outer (loop: aloop))
1089 {
1090 exit = ggc_alloc<loop_exit> ();
1091 exit->e = e;
1092
1093 exit->next = aloop->exits->next;
1094 exit->prev = aloop->exits;
1095 exit->next->prev = exit;
1096 exit->prev->next = exit;
1097
1098 exit->next_e = exits;
1099 exits = exit;
1100 }
1101 }
1102
1103 if (!exits && new_edge)
1104 return;
1105
1106 loop_exit **slot
1107 = current_loops->exits->find_slot_with_hash (comparable: e, hash: htab_hash_pointer (e),
1108 insert: exits ? INSERT : NO_INSERT);
1109 if (!slot)
1110 return;
1111
1112 if (exits)
1113 {
1114 if (*slot)
1115 loop_exit_hasher::remove (exit: *slot);
1116 *slot = exits;
1117 }
1118 else
1119 current_loops->exits->clear_slot (slot);
1120}
1121
1122/* For each loop, record list of exit edges, and start maintaining these
1123 lists. */
1124
1125void
1126record_loop_exits (void)
1127{
1128 basic_block bb;
1129 edge_iterator ei;
1130 edge e;
1131
1132 if (!current_loops)
1133 return;
1134
1135 if (loops_state_satisfies_p (flags: LOOPS_HAVE_RECORDED_EXITS))
1136 return;
1137 loops_state_set (flags: LOOPS_HAVE_RECORDED_EXITS);
1138
1139 gcc_assert (current_loops->exits == NULL);
1140 current_loops->exits
1141 = hash_table<loop_exit_hasher>::create_ggc (n: 2 * number_of_loops (cfun));
1142
1143 FOR_EACH_BB_FN (bb, cfun)
1144 {
1145 FOR_EACH_EDGE (e, ei, bb->succs)
1146 {
1147 rescan_loop_exit (e, new_edge: true, removed: false);
1148 }
1149 }
1150}
1151
1152/* Dumps information about the exit in *SLOT to FILE.
1153 Callback for htab_traverse. */
1154
1155int
1156dump_recorded_exit (loop_exit **slot, FILE *file)
1157{
1158 struct loop_exit *exit = *slot;
1159 unsigned n = 0;
1160 edge e = exit->e;
1161
1162 for (; exit != NULL; exit = exit->next_e)
1163 n++;
1164
1165 fprintf (stream: file, format: "Edge %d->%d exits %u loops\n",
1166 e->src->index, e->dest->index, n);
1167
1168 return 1;
1169}
1170
1171/* Dumps the recorded exits of loops to FILE. */
1172
1173extern void dump_recorded_exits (FILE *);
1174void
1175dump_recorded_exits (FILE *file)
1176{
1177 if (!current_loops->exits)
1178 return;
1179 current_loops->exits->traverse<FILE *, dump_recorded_exit> (argument: file);
1180}
1181
1182/* Releases lists of loop exits. */
1183
1184void
1185release_recorded_exits (function *fn)
1186{
1187 gcc_assert (loops_state_satisfies_p (fn, LOOPS_HAVE_RECORDED_EXITS));
1188 loops_for_fn (fn)->exits->empty ();
1189 loops_for_fn (fn)->exits = NULL;
1190 loops_state_clear (fn, flags: LOOPS_HAVE_RECORDED_EXITS);
1191}
1192
1193/* Returns the list of the exit edges of a LOOP. */
1194
1195auto_vec<edge>
1196get_loop_exit_edges (const class loop *loop, basic_block *body)
1197{
1198 auto_vec<edge> edges;
1199 edge e;
1200 unsigned i;
1201 edge_iterator ei;
1202 struct loop_exit *exit;
1203
1204 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1205
1206 /* If we maintain the lists of exits, use them. Otherwise we must
1207 scan the body of the loop. */
1208 if (loops_state_satisfies_p (flags: LOOPS_HAVE_RECORDED_EXITS))
1209 {
1210 for (exit = loop->exits->next; exit->e; exit = exit->next)
1211 edges.safe_push (obj: exit->e);
1212 }
1213 else
1214 {
1215 bool body_from_caller = true;
1216 if (!body)
1217 {
1218 body = get_loop_body (loop);
1219 body_from_caller = false;
1220 }
1221 for (i = 0; i < loop->num_nodes; i++)
1222 FOR_EACH_EDGE (e, ei, body[i]->succs)
1223 {
1224 if (!flow_bb_inside_loop_p (loop, bb: e->dest))
1225 edges.safe_push (obj: e);
1226 }
1227 if (!body_from_caller)
1228 free (ptr: body);
1229 }
1230
1231 return edges;
1232}
1233
1234/* Counts the number of conditional branches inside LOOP. */
1235
1236unsigned
1237num_loop_branches (const class loop *loop)
1238{
1239 unsigned i, n;
1240 basic_block * body;
1241
1242 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1243
1244 body = get_loop_body (loop);
1245 n = 0;
1246 for (i = 0; i < loop->num_nodes; i++)
1247 if (EDGE_COUNT (body[i]->succs) >= 2)
1248 n++;
1249 free (ptr: body);
1250
1251 return n;
1252}
1253
1254/* Adds basic block BB to LOOP. */
1255void
1256add_bb_to_loop (basic_block bb, class loop *loop)
1257{
1258 unsigned i;
1259 loop_p ploop;
1260 edge_iterator ei;
1261 edge e;
1262
1263 gcc_assert (bb->loop_father == NULL);
1264 bb->loop_father = loop;
1265 loop->num_nodes++;
1266 FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
1267 ploop->num_nodes++;
1268
1269 FOR_EACH_EDGE (e, ei, bb->succs)
1270 {
1271 rescan_loop_exit (e, new_edge: true, removed: false);
1272 }
1273 FOR_EACH_EDGE (e, ei, bb->preds)
1274 {
1275 rescan_loop_exit (e, new_edge: true, removed: false);
1276 }
1277}
1278
1279/* Remove basic block BB from loops. */
1280void
1281remove_bb_from_loops (basic_block bb)
1282{
1283 unsigned i;
1284 class loop *loop = bb->loop_father;
1285 loop_p ploop;
1286 edge_iterator ei;
1287 edge e;
1288
1289 gcc_assert (loop != NULL);
1290 loop->num_nodes--;
1291 FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
1292 ploop->num_nodes--;
1293 bb->loop_father = NULL;
1294
1295 FOR_EACH_EDGE (e, ei, bb->succs)
1296 {
1297 rescan_loop_exit (e, new_edge: false, removed: true);
1298 }
1299 FOR_EACH_EDGE (e, ei, bb->preds)
1300 {
1301 rescan_loop_exit (e, new_edge: false, removed: true);
1302 }
1303}
1304
1305/* Finds nearest common ancestor in loop tree for given loops. */
1306class loop *
1307find_common_loop (class loop *loop_s, class loop *loop_d)
1308{
1309 unsigned sdepth, ddepth;
1310
1311 if (!loop_s) return loop_d;
1312 if (!loop_d) return loop_s;
1313
1314 sdepth = loop_depth (loop: loop_s);
1315 ddepth = loop_depth (loop: loop_d);
1316
1317 if (sdepth < ddepth)
1318 loop_d = (*loop_d->superloops)[sdepth];
1319 else if (sdepth > ddepth)
1320 loop_s = (*loop_s->superloops)[ddepth];
1321
1322 while (loop_s != loop_d)
1323 {
1324 loop_s = loop_outer (loop: loop_s);
1325 loop_d = loop_outer (loop: loop_d);
1326 }
1327 return loop_s;
1328}
1329
1330/* Removes LOOP from structures and frees its data. */
1331
1332void
1333delete_loop (class loop *loop)
1334{
1335 /* Remove the loop from structure. */
1336 flow_loop_tree_node_remove (loop);
1337
1338 /* Remove loop from loops array. */
1339 (*current_loops->larray)[loop->num] = NULL;
1340
1341 /* Free loop data. */
1342 flow_loop_free (loop);
1343}
1344
1345/* Cancels the LOOP; it must be innermost one. */
1346
1347static void
1348cancel_loop (class loop *loop)
1349{
1350 basic_block *bbs;
1351 unsigned i;
1352 class loop *outer = loop_outer (loop);
1353
1354 gcc_assert (!loop->inner);
1355
1356 /* Move blocks up one level (they should be removed as soon as possible). */
1357 bbs = get_loop_body (loop);
1358 for (i = 0; i < loop->num_nodes; i++)
1359 bbs[i]->loop_father = outer;
1360
1361 free (ptr: bbs);
1362 delete_loop (loop);
1363}
1364
1365/* Cancels LOOP and all its subloops. */
1366void
1367cancel_loop_tree (class loop *loop)
1368{
1369 while (loop->inner)
1370 cancel_loop_tree (loop: loop->inner);
1371 cancel_loop (loop);
1372}
1373
1374/* Disable warnings about missing quoting in GCC diagnostics for
1375 the verification errors. Their format strings don't follow GCC
1376 diagnostic conventions and the calls are ultimately followed by
1377 a deliberate ICE triggered by a failed assertion. */
1378#if __GNUC__ >= 10
1379# pragma GCC diagnostic push
1380# pragma GCC diagnostic ignored "-Wformat-diag"
1381#endif
1382
1383/* Checks that information about loops is correct
1384 -- sizes of loops are all right
1385 -- results of get_loop_body really belong to the loop
1386 -- loop header have just single entry edge and single latch edge
1387 -- loop latches have only single successor that is header of their loop
1388 -- irreducible loops are correctly marked
1389 -- the cached loop depth and loop father of each bb is correct
1390 */
1391DEBUG_FUNCTION void
1392verify_loop_structure (void)
1393{
1394 unsigned *sizes, i, j;
1395 basic_block bb, *bbs;
1396 int err = 0;
1397 edge e;
1398 unsigned num = number_of_loops (cfun);
1399 struct loop_exit *exit, *mexit;
1400 bool dom_available = dom_info_available_p (CDI_DOMINATORS);
1401
1402 if (loops_state_satisfies_p (flags: LOOPS_NEED_FIXUP))
1403 {
1404 error ("loop verification on loop tree that needs fixup");
1405 err = 1;
1406 }
1407
1408 /* We need up-to-date dominators, compute or verify them. */
1409 if (!dom_available)
1410 calculate_dominance_info (CDI_DOMINATORS);
1411 else
1412 verify_dominators (CDI_DOMINATORS);
1413
1414 /* Check the loop tree root. */
1415 if (current_loops->tree_root->header != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1416 || current_loops->tree_root->latch != EXIT_BLOCK_PTR_FOR_FN (cfun)
1417 || (current_loops->tree_root->num_nodes
1418 != (unsigned) n_basic_blocks_for_fn (cfun)))
1419 {
1420 error ("corrupt loop tree root");
1421 err = 1;
1422 }
1423
1424 /* Check the headers. */
1425 FOR_EACH_BB_FN (bb, cfun)
1426 if (bb_loop_header_p (header: bb))
1427 {
1428 if (bb->loop_father->header == NULL)
1429 {
1430 error ("loop with header %d marked for removal", bb->index);
1431 err = 1;
1432 }
1433 else if (bb->loop_father->header != bb)
1434 {
1435 error ("loop with header %d not in loop tree", bb->index);
1436 err = 1;
1437 }
1438 }
1439 else if (bb->loop_father->header == bb)
1440 {
1441 error ("non-loop with header %d not marked for removal", bb->index);
1442 err = 1;
1443 }
1444
1445 /* Check the recorded loop father and sizes of loops. */
1446 auto_sbitmap visited (last_basic_block_for_fn (cfun));
1447 bitmap_clear (visited);
1448 bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
1449 for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1450 {
1451 unsigned n;
1452
1453 if (loop->header == NULL)
1454 {
1455 error ("removed loop %d in loop tree", loop->num);
1456 err = 1;
1457 continue;
1458 }
1459
1460 n = get_loop_body_with_size (loop, body: bbs, n_basic_blocks_for_fn (cfun));
1461 if (loop->num_nodes != n)
1462 {
1463 error ("size of loop %d should be %d, not %d",
1464 loop->num, n, loop->num_nodes);
1465 err = 1;
1466 }
1467
1468 for (j = 0; j < n; j++)
1469 {
1470 bb = bbs[j];
1471
1472 if (!flow_bb_inside_loop_p (loop, bb))
1473 {
1474 error ("bb %d does not belong to loop %d",
1475 bb->index, loop->num);
1476 err = 1;
1477 }
1478
1479 /* Ignore this block if it is in an inner loop. */
1480 if (bitmap_bit_p (map: visited, bitno: bb->index))
1481 continue;
1482 bitmap_set_bit (map: visited, bitno: bb->index);
1483
1484 if (bb->loop_father != loop)
1485 {
1486 error ("bb %d has father loop %d, should be loop %d",
1487 bb->index, bb->loop_father->num, loop->num);
1488 err = 1;
1489 }
1490 }
1491 }
1492 free (ptr: bbs);
1493
1494 /* Check headers and latches. */
1495 for (auto loop : loops_list (cfun, 0))
1496 {
1497 i = loop->num;
1498 if (loop->header == NULL)
1499 continue;
1500 if (!bb_loop_header_p (header: loop->header))
1501 {
1502 error ("loop %d%'s header is not a loop header", i);
1503 err = 1;
1504 }
1505 if (loops_state_satisfies_p (flags: LOOPS_HAVE_PREHEADERS)
1506 && EDGE_COUNT (loop->header->preds) != 2)
1507 {
1508 error ("loop %d%'s header does not have exactly 2 entries", i);
1509 err = 1;
1510 }
1511 if (loop->latch)
1512 {
1513 if (!find_edge (loop->latch, loop->header))
1514 {
1515 error ("loop %d%'s latch does not have an edge to its header", i);
1516 err = 1;
1517 }
1518 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, loop->header))
1519 {
1520 error ("loop %d%'s latch is not dominated by its header", i);
1521 err = 1;
1522 }
1523 }
1524 if (loops_state_satisfies_p (flags: LOOPS_HAVE_SIMPLE_LATCHES))
1525 {
1526 if (!single_succ_p (bb: loop->latch))
1527 {
1528 error ("loop %d%'s latch does not have exactly 1 successor", i);
1529 err = 1;
1530 }
1531 if (single_succ (bb: loop->latch) != loop->header)
1532 {
1533 error ("loop %d%'s latch does not have header as successor", i);
1534 err = 1;
1535 }
1536 if (loop->latch->loop_father != loop)
1537 {
1538 error ("loop %d%'s latch does not belong directly to it", i);
1539 err = 1;
1540 }
1541 }
1542 if (loop->header->loop_father != loop)
1543 {
1544 error ("loop %d%'s header does not belong directly to it", i);
1545 err = 1;
1546 }
1547 if (loops_state_satisfies_p (flags: LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1548 {
1549 edge_iterator ei;
1550 FOR_EACH_EDGE (e, ei, loop->header->preds)
1551 if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header)
1552 && e->flags & EDGE_IRREDUCIBLE_LOOP)
1553 {
1554 error ("loop %d%'s latch is marked as part of irreducible"
1555 " region", i);
1556 err = 1;
1557 }
1558 }
1559
1560 /* Check cached number of iterations for released SSA names. */
1561 tree ref;
1562 if (loop->nb_iterations
1563 && (ref = walk_tree (&loop->nb_iterations,
1564 find_released_ssa_name, NULL, NULL)))
1565 {
1566 error ("loop %d%'s number of iterations %qE references the"
1567 " released SSA name %qE", i, loop->nb_iterations, ref);
1568 err = 1;
1569 }
1570 }
1571
1572 /* Check irreducible loops. */
1573 if (loops_state_satisfies_p (flags: LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1574 {
1575 auto_edge_flag saved_edge_irr (cfun);
1576 auto_bb_flag saved_bb_irr (cfun);
1577 /* Save old info. */
1578 FOR_EACH_BB_FN (bb, cfun)
1579 {
1580 edge_iterator ei;
1581 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1582 bb->flags |= saved_bb_irr;
1583 FOR_EACH_EDGE (e, ei, bb->succs)
1584 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1585 e->flags |= saved_edge_irr;
1586 }
1587
1588 /* Recount it. */
1589 mark_irreducible_loops ();
1590
1591 /* Compare. */
1592 FOR_EACH_BB_FN (bb, cfun)
1593 {
1594 edge_iterator ei;
1595
1596 if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1597 && !(bb->flags & saved_bb_irr))
1598 {
1599 error ("basic block %d should be marked irreducible", bb->index);
1600 err = 1;
1601 }
1602 else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1603 && (bb->flags & saved_bb_irr))
1604 {
1605 error ("basic block %d should not be marked irreducible", bb->index);
1606 err = 1;
1607 }
1608 bb->flags &= ~saved_bb_irr;
1609 FOR_EACH_EDGE (e, ei, bb->succs)
1610 {
1611 if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1612 && !(e->flags & saved_edge_irr))
1613 {
1614 error ("edge from %d to %d should be marked irreducible",
1615 e->src->index, e->dest->index);
1616 err = 1;
1617 }
1618 else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1619 && (e->flags & saved_edge_irr))
1620 {
1621 error ("edge from %d to %d should not be marked irreducible",
1622 e->src->index, e->dest->index);
1623 err = 1;
1624 }
1625 e->flags &= ~saved_edge_irr;
1626 }
1627 }
1628 }
1629
1630 /* Check the recorded loop exits. */
1631 for (auto loop : loops_list (cfun, 0))
1632 {
1633 if (!loop->exits || loop->exits->e != NULL)
1634 {
1635 error ("corrupted head of the exits list of loop %d",
1636 loop->num);
1637 err = 1;
1638 }
1639 else
1640 {
1641 /* Check that the list forms a cycle, and all elements except
1642 for the head are nonnull. */
1643 for (mexit = loop->exits, exit = mexit->next, i = 0;
1644 exit->e && exit != mexit;
1645 exit = exit->next)
1646 {
1647 if (i++ & 1)
1648 mexit = mexit->next;
1649 }
1650
1651 if (exit != loop->exits)
1652 {
1653 error ("corrupted exits list of loop %d", loop->num);
1654 err = 1;
1655 }
1656 }
1657
1658 if (!loops_state_satisfies_p (flags: LOOPS_HAVE_RECORDED_EXITS))
1659 {
1660 if (loop->exits->next != loop->exits)
1661 {
1662 error ("nonempty exits list of loop %d, but exits are not recorded",
1663 loop->num);
1664 err = 1;
1665 }
1666 }
1667 }
1668
1669 if (loops_state_satisfies_p (flags: LOOPS_HAVE_RECORDED_EXITS))
1670 {
1671 unsigned n_exits = 0, eloops;
1672
1673 sizes = XCNEWVEC (unsigned, num);
1674 memset (s: sizes, c: 0, n: sizeof (unsigned) * num);
1675 FOR_EACH_BB_FN (bb, cfun)
1676 {
1677 edge_iterator ei;
1678 if (bb->loop_father == current_loops->tree_root)
1679 continue;
1680 FOR_EACH_EDGE (e, ei, bb->succs)
1681 {
1682 if (flow_bb_inside_loop_p (loop: bb->loop_father, bb: e->dest))
1683 continue;
1684
1685 n_exits++;
1686 exit = get_exit_descriptions (e);
1687 if (!exit)
1688 {
1689 error ("exit %d->%d not recorded",
1690 e->src->index, e->dest->index);
1691 err = 1;
1692 }
1693 eloops = 0;
1694 for (; exit; exit = exit->next_e)
1695 eloops++;
1696
1697 for (class loop *loop = bb->loop_father;
1698 loop != e->dest->loop_father
1699 /* When a loop exit is also an entry edge which
1700 can happen when avoiding CFG manipulations
1701 then the last loop exited is the outer loop
1702 of the loop entered. */
1703 && loop != loop_outer (loop: e->dest->loop_father);
1704 loop = loop_outer (loop))
1705 {
1706 eloops--;
1707 sizes[loop->num]++;
1708 }
1709
1710 if (eloops != 0)
1711 {
1712 error ("wrong list of exited loops for edge %d->%d",
1713 e->src->index, e->dest->index);
1714 err = 1;
1715 }
1716 }
1717 }
1718
1719 if (n_exits != current_loops->exits->elements ())
1720 {
1721 error ("too many loop exits recorded");
1722 err = 1;
1723 }
1724
1725 for (auto loop : loops_list (cfun, 0))
1726 {
1727 eloops = 0;
1728 for (exit = loop->exits->next; exit->e; exit = exit->next)
1729 eloops++;
1730 if (eloops != sizes[loop->num])
1731 {
1732 error ("%d exits recorded for loop %d (having %d exits)",
1733 eloops, loop->num, sizes[loop->num]);
1734 err = 1;
1735 }
1736 }
1737
1738 free (ptr: sizes);
1739 }
1740
1741 gcc_assert (!err);
1742
1743 if (!dom_available)
1744 free_dominance_info (CDI_DOMINATORS);
1745}
1746
1747#if __GNUC__ >= 10
1748# pragma GCC diagnostic pop
1749#endif
1750
1751/* Returns latch edge of LOOP. */
1752edge
1753loop_latch_edge (const class loop *loop)
1754{
1755 return find_edge (loop->latch, loop->header);
1756}
1757
1758/* Returns preheader edge of LOOP. */
1759edge
1760loop_preheader_edge (const class loop *loop)
1761{
1762 edge e;
1763 edge_iterator ei;
1764
1765 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
1766 && ! loops_state_satisfies_p (LOOPS_MAY_HAVE_MULTIPLE_LATCHES));
1767
1768 FOR_EACH_EDGE (e, ei, loop->header->preds)
1769 if (e->src != loop->latch)
1770 break;
1771
1772 if (! e)
1773 {
1774 gcc_assert (! loop_outer (loop));
1775 return single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1776 }
1777
1778 return e;
1779}
1780
1781/* Returns true if E is an exit of LOOP. */
1782
1783bool
1784loop_exit_edge_p (const class loop *loop, const_edge e)
1785{
1786 return (flow_bb_inside_loop_p (loop, bb: e->src)
1787 && !flow_bb_inside_loop_p (loop, bb: e->dest));
1788}
1789
1790/* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1791 or more than one exit. If loops do not have the exits recorded, NULL
1792 is returned always. */
1793
1794edge
1795single_exit (const class loop *loop)
1796{
1797 struct loop_exit *exit = loop->exits->next;
1798
1799 if (!loops_state_satisfies_p (flags: LOOPS_HAVE_RECORDED_EXITS))
1800 return NULL;
1801
1802 if (exit->e && exit->next == loop->exits)
1803 return exit->e;
1804 else
1805 return NULL;
1806}
1807
1808/* Returns true when BB has an incoming edge exiting LOOP. */
1809
1810bool
1811loop_exits_to_bb_p (class loop *loop, basic_block bb)
1812{
1813 edge e;
1814 edge_iterator ei;
1815
1816 FOR_EACH_EDGE (e, ei, bb->preds)
1817 if (loop_exit_edge_p (loop, e))
1818 return true;
1819
1820 return false;
1821}
1822
1823/* Returns true when BB has an outgoing edge exiting LOOP. */
1824
1825bool
1826loop_exits_from_bb_p (class loop *loop, basic_block bb)
1827{
1828 edge e;
1829 edge_iterator ei;
1830
1831 FOR_EACH_EDGE (e, ei, bb->succs)
1832 if (loop_exit_edge_p (loop, e))
1833 return true;
1834
1835 return false;
1836}
1837
1838/* Return location corresponding to the loop control condition if possible. */
1839
1840dump_user_location_t
1841get_loop_location (class loop *loop)
1842{
1843 rtx_insn *insn = NULL;
1844 class niter_desc *desc = NULL;
1845 edge exit;
1846
1847 /* For a for or while loop, we would like to return the location
1848 of the for or while statement, if possible. To do this, look
1849 for the branch guarding the loop back-edge. */
1850
1851 /* If this is a simple loop with an in_edge, then the loop control
1852 branch is typically at the end of its source. */
1853 desc = get_simple_loop_desc (loop);
1854 if (desc->in_edge)
1855 {
1856 FOR_BB_INSNS_REVERSE (desc->in_edge->src, insn)
1857 {
1858 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1859 return insn;
1860 }
1861 }
1862 /* If loop has a single exit, then the loop control branch
1863 must be at the end of its source. */
1864 if ((exit = single_exit (loop)))
1865 {
1866 FOR_BB_INSNS_REVERSE (exit->src, insn)
1867 {
1868 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1869 return insn;
1870 }
1871 }
1872 /* Next check the latch, to see if it is non-empty. */
1873 FOR_BB_INSNS_REVERSE (loop->latch, insn)
1874 {
1875 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1876 return insn;
1877 }
1878 /* Finally, if none of the above identifies the loop control branch,
1879 return the first location in the loop header. */
1880 FOR_BB_INSNS (loop->header, insn)
1881 {
1882 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1883 return insn;
1884 }
1885 /* If all else fails, simply return the current function location. */
1886 return dump_user_location_t::from_function_decl (fndecl: current_function_decl);
1887}
1888
1889/* Records that every statement in LOOP is executed I_BOUND times.
1890 REALISTIC is true if I_BOUND is expected to be close to the real number
1891 of iterations. UPPER is true if we are sure the loop iterates at most
1892 I_BOUND times. */
1893
1894void
1895record_niter_bound (class loop *loop, const widest_int &i_bound,
1896 bool realistic, bool upper)
1897{
1898 if (wi::min_precision (x: i_bound, sgn: SIGNED) > bound_wide_int ().get_precision ())
1899 return;
1900
1901 bound_wide_int bound = bound_wide_int::from (x: i_bound, sgn: SIGNED);
1902
1903 /* Update the bounds only when there is no previous estimation, or when the
1904 current estimation is smaller. */
1905 if (upper
1906 && (!loop->any_upper_bound
1907 || wi::ltu_p (x: bound, y: loop->nb_iterations_upper_bound)))
1908 {
1909 loop->any_upper_bound = true;
1910 loop->nb_iterations_upper_bound = bound;
1911 if (!loop->any_likely_upper_bound)
1912 {
1913 loop->any_likely_upper_bound = true;
1914 loop->nb_iterations_likely_upper_bound = bound;
1915 }
1916 }
1917 if (realistic
1918 && (!loop->any_estimate
1919 || wi::ltu_p (x: bound, y: loop->nb_iterations_estimate)))
1920 {
1921 loop->any_estimate = true;
1922 loop->nb_iterations_estimate = bound;
1923 }
1924 if (!realistic
1925 && (!loop->any_likely_upper_bound
1926 || wi::ltu_p (x: bound, y: loop->nb_iterations_likely_upper_bound)))
1927 {
1928 loop->any_likely_upper_bound = true;
1929 loop->nb_iterations_likely_upper_bound = bound;
1930 }
1931
1932 /* If an upper bound is smaller than the realistic estimate of the
1933 number of iterations, use the upper bound instead. */
1934 if (loop->any_upper_bound
1935 && loop->any_estimate
1936 && wi::ltu_p (x: loop->nb_iterations_upper_bound,
1937 y: loop->nb_iterations_estimate))
1938 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
1939 if (loop->any_upper_bound
1940 && loop->any_likely_upper_bound
1941 && wi::ltu_p (x: loop->nb_iterations_upper_bound,
1942 y: loop->nb_iterations_likely_upper_bound))
1943 loop->nb_iterations_likely_upper_bound = loop->nb_iterations_upper_bound;
1944}
1945
1946/* Similar to get_estimated_loop_iterations, but returns the estimate only
1947 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1948 on the number of iterations of LOOP could not be derived, returns -1. */
1949
1950HOST_WIDE_INT
1951get_estimated_loop_iterations_int (class loop *loop)
1952{
1953 widest_int nit;
1954 HOST_WIDE_INT hwi_nit;
1955
1956 if (!get_estimated_loop_iterations (loop, nit: &nit))
1957 return -1;
1958
1959 if (!wi::fits_shwi_p (x: nit))
1960 return -1;
1961 hwi_nit = nit.to_shwi ();
1962
1963 return hwi_nit < 0 ? -1 : hwi_nit;
1964}
1965
1966/* Returns an upper bound on the number of executions of statements
1967 in the LOOP. For statements before the loop exit, this exceeds
1968 the number of execution of the latch by one. */
1969
1970HOST_WIDE_INT
1971max_stmt_executions_int (class loop *loop)
1972{
1973 HOST_WIDE_INT nit = get_max_loop_iterations_int (loop);
1974 HOST_WIDE_INT snit;
1975
1976 if (nit == -1)
1977 return -1;
1978
1979 snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
1980
1981 /* If the computation overflows, return -1. */
1982 return snit < 0 ? -1 : snit;
1983}
1984
1985/* Returns an likely upper bound on the number of executions of statements
1986 in the LOOP. For statements before the loop exit, this exceeds
1987 the number of execution of the latch by one. */
1988
1989HOST_WIDE_INT
1990likely_max_stmt_executions_int (class loop *loop)
1991{
1992 HOST_WIDE_INT nit = get_likely_max_loop_iterations_int (loop);
1993 HOST_WIDE_INT snit;
1994
1995 if (nit == -1)
1996 return -1;
1997
1998 snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
1999
2000 /* If the computation overflows, return -1. */
2001 return snit < 0 ? -1 : snit;
2002}
2003
2004/* Sets NIT to the estimated number of executions of the latch of the
2005 LOOP. If we have no reliable estimate, the function returns false, otherwise
2006 returns true. */
2007
2008bool
2009get_estimated_loop_iterations (class loop *loop, widest_int *nit)
2010{
2011 /* Even if the bound is not recorded, possibly we can derrive one from
2012 profile. */
2013 if (!loop->any_estimate)
2014 {
2015 sreal snit;
2016 bool reliable;
2017 if (expected_loop_iterations_by_profile (loop, ret: &snit, reliable: &reliable)
2018 && reliable)
2019 {
2020 *nit = snit.to_nearest_int ();
2021 return true;
2022 }
2023 return false;
2024 }
2025
2026 *nit = widest_int::from (x: loop->nb_iterations_estimate, sgn: SIGNED);
2027 return true;
2028}
2029
2030/* Sets NIT to an upper bound for the maximum number of executions of the
2031 latch of the LOOP. If we have no reliable estimate, the function returns
2032 false, otherwise returns true. */
2033
2034bool
2035get_max_loop_iterations (const class loop *loop, widest_int *nit)
2036{
2037 if (!loop->any_upper_bound)
2038 return false;
2039
2040 *nit = widest_int::from (x: loop->nb_iterations_upper_bound, sgn: SIGNED);
2041 return true;
2042}
2043
2044/* Similar to get_max_loop_iterations, but returns the estimate only
2045 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
2046 on the number of iterations of LOOP could not be derived, returns -1. */
2047
2048HOST_WIDE_INT
2049get_max_loop_iterations_int (const class loop *loop)
2050{
2051 widest_int nit;
2052 HOST_WIDE_INT hwi_nit;
2053
2054 if (!get_max_loop_iterations (loop, nit: &nit))
2055 return -1;
2056
2057 if (!wi::fits_shwi_p (x: nit))
2058 return -1;
2059 hwi_nit = nit.to_shwi ();
2060
2061 return hwi_nit < 0 ? -1 : hwi_nit;
2062}
2063
2064/* Sets NIT to an upper bound for the maximum number of executions of the
2065 latch of the LOOP. If we have no reliable estimate, the function returns
2066 false, otherwise returns true. */
2067
2068bool
2069get_likely_max_loop_iterations (class loop *loop, widest_int *nit)
2070{
2071 if (!loop->any_likely_upper_bound)
2072 return false;
2073
2074 *nit = widest_int::from (x: loop->nb_iterations_likely_upper_bound, sgn: SIGNED);
2075 return true;
2076}
2077
2078/* Similar to get_max_loop_iterations, but returns the estimate only
2079 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
2080 on the number of iterations of LOOP could not be derived, returns -1. */
2081
2082HOST_WIDE_INT
2083get_likely_max_loop_iterations_int (class loop *loop)
2084{
2085 widest_int nit;
2086 HOST_WIDE_INT hwi_nit;
2087
2088 if (!get_likely_max_loop_iterations (loop, nit: &nit))
2089 return -1;
2090
2091 if (!wi::fits_shwi_p (x: nit))
2092 return -1;
2093 hwi_nit = nit.to_shwi ();
2094
2095 return hwi_nit < 0 ? -1 : hwi_nit;
2096}
2097
2098/* Returns the loop depth of the loop BB belongs to. */
2099
2100int
2101bb_loop_depth (const_basic_block bb)
2102{
2103 return bb->loop_father ? loop_depth (loop: bb->loop_father) : 0;
2104}
2105
2106/* Marks LOOP for removal and sets LOOPS_NEED_FIXUP. */
2107
2108void
2109mark_loop_for_removal (loop_p loop)
2110{
2111 if (loop->header == NULL)
2112 return;
2113 loop->former_header = loop->header;
2114 loop->header = NULL;
2115 loop->latch = NULL;
2116 loops_state_set (flags: LOOPS_NEED_FIXUP);
2117}
2118
2119/* Starting from loop tree ROOT, walk loop tree as the visiting
2120 order specified by FLAGS. The supported visiting orders
2121 are:
2122 - LI_ONLY_INNERMOST
2123 - LI_FROM_INNERMOST
2124 - Preorder (if neither of above is specified) */
2125
2126void
2127loops_list::walk_loop_tree (class loop *root, unsigned flags)
2128{
2129 bool only_innermost_p = flags & LI_ONLY_INNERMOST;
2130 bool from_innermost_p = flags & LI_FROM_INNERMOST;
2131 bool preorder_p = !(only_innermost_p || from_innermost_p);
2132
2133 /* Early handle root without any inner loops, make later
2134 processing simpler, that is all loops processed in the
2135 following while loop are impossible to be root. */
2136 if (!root->inner)
2137 {
2138 if (flags & LI_INCLUDE_ROOT)
2139 this->to_visit.quick_push (obj: root->num);
2140 return;
2141 }
2142 else if (preorder_p && flags & LI_INCLUDE_ROOT)
2143 this->to_visit.quick_push (obj: root->num);
2144
2145 class loop *aloop;
2146 for (aloop = root->inner;
2147 aloop->inner != NULL;
2148 aloop = aloop->inner)
2149 {
2150 if (preorder_p)
2151 this->to_visit.quick_push (obj: aloop->num);
2152 continue;
2153 }
2154
2155 while (1)
2156 {
2157 gcc_assert (aloop != root);
2158 if (from_innermost_p || aloop->inner == NULL)
2159 this->to_visit.quick_push (obj: aloop->num);
2160
2161 if (aloop->next)
2162 {
2163 for (aloop = aloop->next;
2164 aloop->inner != NULL;
2165 aloop = aloop->inner)
2166 {
2167 if (preorder_p)
2168 this->to_visit.quick_push (obj: aloop->num);
2169 continue;
2170 }
2171 }
2172 else if (loop_outer (loop: aloop) == root)
2173 break;
2174 else
2175 aloop = loop_outer (loop: aloop);
2176 }
2177
2178 /* When visiting from innermost, we need to consider root here
2179 since the previous while loop doesn't handle it. */
2180 if (from_innermost_p && flags & LI_INCLUDE_ROOT)
2181 this->to_visit.quick_push (obj: root->num);
2182}
2183
2184

source code of gcc/cfgloop.cc