Line data Source code
1 : /* Natural loop discovery code for GNU compiler.
2 : Copyright (C) 2000-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
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.
10 :
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.
15 :
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/>. */
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 :
38 : static void flow_loops_cfg_dump (FILE *);
39 :
40 : /* Dump loop related CFG information. */
41 :
42 : static void
43 6776 : flow_loops_cfg_dump (FILE *file)
44 : {
45 6776 : basic_block bb;
46 :
47 6776 : if (!file)
48 : return;
49 :
50 29433 : FOR_EACH_BB_FN (bb, cfun)
51 : {
52 22657 : edge succ;
53 22657 : edge_iterator ei;
54 :
55 22657 : fprintf (file, ";; %d succs { ", bb->index);
56 52300 : FOR_EACH_EDGE (succ, ei, bb->succs)
57 29643 : fprintf (file, "%d ", succ->dest->index);
58 22657 : fprintf (file, "}\n");
59 : }
60 : }
61 :
62 : /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
63 :
64 : bool
65 775859863 : flow_loop_nested_p (const class loop *outer, const class loop *loop)
66 : {
67 775859863 : unsigned odepth = loop_depth (outer);
68 :
69 775859863 : return (loop_depth (loop) > odepth
70 506817024 : && (*loop->superloops)[odepth] == outer);
71 : }
72 :
73 : /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
74 : loops within LOOP. */
75 :
76 : class loop *
77 22208773 : superloop_at_depth (class loop *loop, unsigned depth)
78 : {
79 22208773 : unsigned ldepth = loop_depth (loop);
80 :
81 22208773 : gcc_assert (depth <= ldepth);
82 :
83 22208773 : if (depth == ldepth)
84 : return loop;
85 :
86 5814158 : return (*loop->superloops)[depth];
87 : }
88 :
89 : /* Returns the list of the latch edges of LOOP. */
90 :
91 : static vec<edge>
92 47919 : get_loop_latch_edges (const class loop *loop)
93 : {
94 47919 : edge_iterator ei;
95 47919 : edge e;
96 47919 : vec<edge> ret = vNULL;
97 :
98 203057 : FOR_EACH_EDGE (e, ei, loop->header->preds)
99 : {
100 155138 : if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header))
101 105543 : ret.safe_push (e);
102 : }
103 :
104 47919 : 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 :
110 : void
111 8496 : flow_loop_dump (const class loop *loop, FILE *file,
112 : void (*loop_dump_aux) (const class loop *, FILE *, int),
113 : int verbose)
114 : {
115 8496 : basic_block *bbs;
116 8496 : unsigned i;
117 8496 : vec<edge> latches;
118 8496 : edge e;
119 :
120 8496 : if (! loop || ! loop->header)
121 0 : return;
122 :
123 8496 : fprintf (file, ";;\n;; Loop %d\n", loop->num);
124 :
125 8496 : fprintf (file, ";; header %d, ", loop->header->index);
126 8496 : if (loop->latch)
127 8492 : fprintf (file, "latch %d\n", loop->latch->index);
128 : else
129 : {
130 4 : fprintf (file, "multiple latches:");
131 4 : latches = get_loop_latch_edges (loop);
132 16 : FOR_EACH_VEC_ELT (latches, i, e)
133 8 : fprintf (file, " %d", e->src->index);
134 4 : latches.release ();
135 4 : fprintf (file, "\n");
136 : }
137 :
138 16992 : fprintf (file, ";; depth %d, outer %ld",
139 8496 : loop_depth (loop), (long) (loop_outer (loop)
140 1692 : ? loop_outer (loop)->num : -1));
141 8496 : print_loop_info (file, loop, ";; ");
142 :
143 8496 : fprintf (file, "\n;; nodes:");
144 8496 : bbs = get_loop_body (loop);
145 59396 : for (i = 0; i < loop->num_nodes; i++)
146 42404 : fprintf (file, " %d", bbs[i]->index);
147 8496 : free (bbs);
148 8496 : fprintf (file, "\n");
149 :
150 8496 : if (loop_dump_aux)
151 0 : 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 :
157 : void
158 49704255 : flow_loops_dump (FILE *file, void (*loop_dump_aux) (const class loop *, FILE *, int), int verbose)
159 : {
160 49704255 : if (!current_loops || ! file)
161 : return;
162 :
163 13608 : fprintf (file, ";; %d loops found\n", number_of_loops (cfun));
164 :
165 28841 : for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT))
166 : {
167 8429 : flow_loop_dump (loop, file, loop_dump_aux, verbose);
168 6804 : }
169 :
170 6804 : if (verbose)
171 6776 : flow_loops_cfg_dump (file);
172 : }
173 :
174 : /* Free data allocated for LOOP. */
175 :
176 : void
177 17334519 : flow_loop_free (class loop *loop)
178 : {
179 17334519 : struct loop_exit *exit, *next;
180 :
181 17334519 : vec_free (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 17347804 : for (exit = loop->exits->next; exit != loop->exits; exit = next)
188 : {
189 13285 : next = exit->next;
190 13285 : exit->next = exit;
191 13285 : exit->prev = exit;
192 : }
193 :
194 17334519 : ggc_free (loop->exits);
195 17334519 : ggc_free (loop);
196 17334519 : }
197 :
198 : /* Free all the memory allocated for LOOPS. */
199 :
200 : void
201 10890161 : flow_loops_free (struct loops *loops)
202 : {
203 10890161 : if (loops->larray)
204 : {
205 : unsigned i;
206 : loop_p loop;
207 :
208 : /* Free the loop descriptors. */
209 28315956 : FOR_EACH_VEC_SAFE_ELT (loops->larray, i, loop)
210 : {
211 17425795 : if (!loop)
212 510127 : continue;
213 :
214 16915668 : flow_loop_free (loop);
215 : }
216 :
217 21780322 : vec_free (loops->larray);
218 : }
219 10890161 : }
220 :
221 : /* Find the nodes contained within the LOOP with header HEADER.
222 : Return the number of nodes within the loop. */
223 :
224 : int
225 22011875 : flow_loop_nodes_find (basic_block header, class loop *loop)
226 : {
227 22011875 : vec<basic_block> stack = vNULL;
228 22011875 : int num_nodes = 1;
229 22011875 : edge latch;
230 22011875 : edge_iterator latch_ei;
231 :
232 22011875 : header->loop_father = loop;
233 :
234 66812749 : FOR_EACH_EDGE (latch, latch_ei, loop->header->preds)
235 : {
236 73069273 : if (latch->src->loop_father == loop
237 44800874 : || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header))
238 28268399 : continue;
239 :
240 16532475 : num_nodes++;
241 16532475 : stack.safe_push (latch->src);
242 16532475 : latch->src->loop_father = loop;
243 :
244 168166718 : while (!stack.is_empty ())
245 : {
246 106833369 : basic_block node;
247 106833369 : edge e;
248 106833369 : edge_iterator ei;
249 :
250 106833369 : node = stack.pop ();
251 :
252 254501979 : FOR_EACH_EDGE (e, ei, node->preds)
253 : {
254 147668610 : basic_block ancestor = e->src;
255 :
256 147668610 : if (ancestor->loop_father != loop)
257 : {
258 90300894 : ancestor->loop_father = loop;
259 90300894 : num_nodes++;
260 90300894 : stack.safe_push (ancestor);
261 : }
262 : }
263 : }
264 : }
265 22011875 : stack.release ();
266 :
267 22011875 : return num_nodes;
268 : }
269 :
270 : /* Records the vector of superloops of the loop LOOP, whose immediate
271 : superloop is FATHER. */
272 :
273 : static void
274 22964950 : establish_preds (class loop *loop, class loop *father)
275 : {
276 22964950 : loop_p ploop;
277 22964950 : unsigned depth = loop_depth (father) + 1;
278 22964950 : unsigned i;
279 :
280 22964950 : loop->superloops = 0;
281 22964950 : vec_alloc (loop->superloops, depth);
282 55207250 : FOR_EACH_VEC_SAFE_ELT (father->superloops, i, ploop)
283 9277350 : loop->superloops->quick_push (ploop);
284 22964950 : loop->superloops->quick_push (father);
285 :
286 23046227 : for (ploop = loop->inner; ploop; ploop = ploop->next)
287 81277 : establish_preds (ploop, loop);
288 22964950 : }
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 :
297 : void
298 22883673 : flow_loop_tree_node_add (class loop *father, class loop *loop,
299 : class loop *after)
300 : {
301 22883673 : if (after)
302 : {
303 4831 : loop->next = after->next;
304 4831 : after->next = loop;
305 : }
306 : else
307 : {
308 22878842 : loop->next = father->inner;
309 22878842 : father->inner = loop;
310 : }
311 :
312 22883673 : establish_preds (loop, father);
313 22883673 : }
314 :
315 : /* Remove LOOP from the loop hierarchy tree. */
316 :
317 : void
318 16843593 : flow_loop_tree_node_remove (class loop *loop)
319 : {
320 16843593 : class loop *prev, *father;
321 :
322 16843593 : father = loop_outer (loop);
323 :
324 : /* Remove loop from the list of sons. */
325 16843593 : if (father->inner == loop)
326 7861655 : father->inner = loop->next;
327 : else
328 : {
329 229240352 : for (prev = father->inner; prev->next != loop; prev = prev->next)
330 220258414 : continue;
331 8981938 : prev->next = loop->next;
332 : }
333 :
334 16843593 : loop->superloops = NULL;
335 16843593 : }
336 :
337 : /* Allocates and returns new loop structure. */
338 :
339 : class loop *
340 17457984 : alloc_loop (void)
341 : {
342 17457984 : class loop *loop = ggc_cleared_alloc<class loop> ();
343 :
344 17457984 : loop->exits = ggc_cleared_alloc<loop_exit> ();
345 17457984 : loop->exits->next = loop->exits->prev = loop->exits;
346 17457984 : loop->can_be_parallel = false;
347 17457984 : loop->constraints = 0;
348 17457984 : loop->nb_iterations_upper_bound = 0;
349 17457984 : loop->nb_iterations_likely_upper_bound = 0;
350 17457984 : loop->nb_iterations_estimate = 0;
351 17457984 : return loop;
352 : }
353 :
354 : /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
355 : (including the root of the loop tree). */
356 :
357 : void
358 10999053 : init_loops_structure (struct function *fn,
359 : struct loops *loops, unsigned num_loops)
360 : {
361 10999053 : class loop *root;
362 :
363 10999053 : memset (loops, 0, sizeof *loops);
364 10999053 : vec_alloc (loops->larray, num_loops);
365 :
366 : /* Dummy loop containing whole function. */
367 10999053 : root = alloc_loop ();
368 10999053 : root->num_nodes = n_basic_blocks_for_fn (fn);
369 10999053 : root->latch = EXIT_BLOCK_PTR_FOR_FN (fn);
370 10999053 : root->header = ENTRY_BLOCK_PTR_FOR_FN (fn);
371 10999053 : ENTRY_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
372 10999053 : EXIT_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
373 :
374 10999053 : loops->larray->quick_push (root);
375 10999053 : loops->tree_root = root;
376 10999053 : }
377 :
378 : /* Returns whether HEADER is a loop header. */
379 :
380 : bool
381 3892597454 : bb_loop_header_p (basic_block header)
382 : {
383 3892597454 : edge_iterator ei;
384 3892597454 : edge e;
385 :
386 : /* If we have an abnormal predecessor, do not consider the
387 : loop (not worth the problems). */
388 3892597454 : if (bb_has_abnormal_pred (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 8833830651 : FOR_EACH_EDGE (e, ei, header->preds)
397 : {
398 5383224863 : basic_block latch = e->src;
399 5383224863 : if (latch != ENTRY_BLOCK_PTR_FOR_FN (cfun)
400 5383224863 : && 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 :
415 : struct loops *
416 21744396 : flow_loops_find (struct loops *loops)
417 : {
418 21744396 : bool from_scratch = (loops == NULL);
419 21744396 : int *rc_order;
420 21744396 : int b;
421 21744396 : unsigned i;
422 :
423 : /* Ensure that the dominators are computed. */
424 21744396 : calculate_dominance_info (CDI_DOMINATORS);
425 :
426 21744396 : if (!loops)
427 : {
428 10849992 : loops = ggc_cleared_alloc<struct loops> ();
429 10849992 : init_loops_structure (cfun, loops, 1);
430 : }
431 :
432 : /* Ensure that loop exits were released. */
433 21744396 : gcc_assert (loops->exits == NULL);
434 :
435 : /* Taking care of this degenerate case makes the rest of
436 : this code simpler. */
437 21744396 : if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
438 : return loops;
439 :
440 : /* The root loop node contains all basic-blocks. */
441 21505463 : 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 21505463 : rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
446 21505463 : 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 21505463 : auto_vec<loop_p> larray (loops->larray->length ());
451 359194796 : for (b = 0; b < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; b++)
452 : {
453 337689333 : basic_block header = BASIC_BLOCK_FOR_FN (cfun, rc_order[b]);
454 337689333 : if (bb_loop_header_p (header))
455 : {
456 22011875 : class loop *loop;
457 :
458 : /* The current active loop tree has valid loop-fathers for
459 : header blocks. */
460 22011875 : if (!from_scratch
461 16404660 : && header->loop_father->header == header)
462 : {
463 16344361 : 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 16344361 : flow_loop_tree_node_remove (loop);
468 : }
469 : else
470 : {
471 : /* Otherwise allocate a new loop structure for the loop. */
472 5667514 : loop = alloc_loop ();
473 : /* ??? We could re-use unused loop slots here. */
474 5667514 : loop->num = loops->larray->length ();
475 5667514 : vec_safe_push (loops->larray, loop);
476 5667514 : loop->header = header;
477 :
478 5667514 : if (!from_scratch
479 5667514 : && dump_file && (dump_flags & TDF_DETAILS))
480 3 : fprintf (dump_file, "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 22011875 : loop->latch = NULL;
486 22011875 : larray.safe_push (loop);
487 : }
488 :
489 : /* Make blocks part of the loop root node at start. */
490 337689333 : header->loop_father = loops->tree_root;
491 : }
492 :
493 21505463 : free (rc_order);
494 :
495 : /* Now iterate over the loops found, insert them into the loop tree
496 : and assign basic-block ownership. */
497 43517338 : for (i = 0; i < larray.length (); ++i)
498 : {
499 22011875 : class loop *loop = larray[i];
500 22011875 : basic_block header = loop->header;
501 22011875 : edge_iterator ei;
502 22011875 : edge e;
503 :
504 22011875 : flow_loop_tree_node_add (header->loop_father, loop);
505 22011875 : loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
506 :
507 : /* Look for the latch for this header block, if it has just a
508 : single one. */
509 66415295 : FOR_EACH_EDGE (e, ei, header->preds)
510 : {
511 44634351 : basic_block latch = e->src;
512 :
513 44634351 : if (flow_bb_inside_loop_p (loop, latch))
514 : {
515 22242806 : if (loop->latch != NULL)
516 : {
517 : /* More than one latch edge. */
518 230931 : loop->latch = NULL;
519 230931 : break;
520 : }
521 22011875 : loop->latch = latch;
522 : }
523 : }
524 : }
525 :
526 21505463 : return loops;
527 21505463 : }
528 :
529 : /* qsort helper for sort_sibling_loops. */
530 :
531 : static int *sort_sibling_loops_cmp_rpo;
532 : static int
533 2626 : sort_sibling_loops_cmp (const void *la_, const void *lb_)
534 : {
535 2626 : const class loop *la = *(const class loop * const *)la_;
536 2626 : const class loop *lb = *(const class loop * const *)lb_;
537 2626 : return (sort_sibling_loops_cmp_rpo[la->header->index]
538 2626 : - sort_sibling_loops_cmp_rpo[lb->header->index]);
539 : }
540 :
541 : /* Sort sibling loops in RPO order. */
542 :
543 : void
544 557 : sort_sibling_loops (function *fn)
545 : {
546 : /* Match flow_loops_find in the order we sort sibling loops. */
547 557 : sort_sibling_loops_cmp_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
548 557 : int *rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
549 557 : pre_and_rev_post_order_compute_fn (fn, NULL, rc_order, false);
550 7583 : for (int i = 0; i < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; ++i)
551 7026 : sort_sibling_loops_cmp_rpo[rc_order[i]] = i;
552 557 : free (rc_order);
553 :
554 557 : auto_vec<loop_p, 3> siblings;
555 3601 : for (auto loop : loops_list (fn, LI_INCLUDE_ROOT))
556 1930 : if (loop->inner && loop->inner->next)
557 : {
558 224 : loop_p sibling = loop->inner;
559 597 : do
560 : {
561 597 : siblings.safe_push (sibling);
562 597 : sibling = sibling->next;
563 : }
564 597 : while (sibling);
565 224 : siblings.qsort (sort_sibling_loops_cmp);
566 224 : loop_p *siblingp = &loop->inner;
567 821 : for (unsigned i = 0; i < siblings.length (); ++i)
568 : {
569 597 : *siblingp = siblings[i];
570 597 : siblingp = &(*siblingp)->next;
571 : }
572 224 : *siblingp = NULL;
573 224 : siblings.truncate (0);
574 557 : }
575 :
576 557 : free (sort_sibling_loops_cmp_rpo);
577 557 : sort_sibling_loops_cmp_rpo = NULL;
578 557 : }
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 :
597 : static edge
598 19964 : find_subloop_latch_edge_by_profile (vec<edge> latches)
599 : {
600 19964 : unsigned i;
601 19964 : edge e, me = NULL;
602 19964 : profile_count mcount = profile_count::zero (), tcount = profile_count::zero ();
603 :
604 70636 : FOR_EACH_VEC_ELT (latches, i, e)
605 : {
606 50672 : if (e->count ()> mcount)
607 : {
608 8108 : me = e;
609 8108 : mcount = e->count();
610 : }
611 50672 : tcount += e->count();
612 : }
613 :
614 19964 : if (!tcount.initialized_p () || !(tcount.ipa () > HEAVY_EDGE_MIN_SAMPLES)
615 19984 : || (tcount - mcount) * HEAVY_EDGE_RATIO > tcount)
616 19950 : return NULL;
617 :
618 14 : if (dump_file)
619 0 : fprintf (dump_file,
620 : "Found latch edge %d -> %d using profile information.\n",
621 0 : 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 :
637 : static edge
638 19271 : find_subloop_latch_edge_by_ivs (class loop *loop ATTRIBUTE_UNUSED, vec<edge> latches)
639 : {
640 19271 : edge e, latch = latches[0];
641 19271 : unsigned i;
642 19271 : gphi *phi;
643 19271 : gphi_iterator psi;
644 19271 : tree lop;
645 19271 : basic_block bb;
646 :
647 : /* Find the candidate for the latch edge. */
648 49279 : for (i = 1; latches.iterate (i, &e); i++)
649 30008 : if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src))
650 5771 : latch = e;
651 :
652 : /* Verify that it dominates all the latch edges. */
653 50321 : FOR_EACH_VEC_ELT (latches, i, e)
654 41900 : 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 20614 : for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
660 : {
661 17221 : phi = psi.phi ();
662 17221 : lop = PHI_ARG_DEF_FROM_EDGE (phi, latch);
663 :
664 : /* Ignore the values that are not changed inside the subloop. */
665 20809 : if (TREE_CODE (lop) != SSA_NAME
666 17221 : || SSA_NAME_DEF_STMT (lop) == phi)
667 3588 : continue;
668 13633 : bb = gimple_bb (SSA_NAME_DEF_STMT (lop));
669 13633 : if (!bb || !flow_bb_inside_loop_p (loop, bb))
670 14 : continue;
671 :
672 36791 : FOR_EACH_VEC_ELT (latches, i, e)
673 24598 : if (e != latch
674 24598 : && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop)
675 : return NULL;
676 : }
677 :
678 3393 : if (dump_file)
679 1 : fprintf (dump_file,
680 : "Found latch edge %d -> %d using iv structure.\n",
681 1 : 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 :
689 : static edge
690 25661 : find_subloop_latch_edge (class loop *loop)
691 : {
692 25661 : vec<edge> latches = get_loop_latch_edges (loop);
693 25661 : edge latch = NULL;
694 :
695 25661 : if (latches.length () > 1)
696 : {
697 19964 : latch = find_subloop_latch_edge_by_profile (latches);
698 :
699 19964 : 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 19964 : && current_ir_type () == IR_GIMPLE)
704 19271 : latch = find_subloop_latch_edge_by_ivs (loop, latches);
705 : }
706 :
707 25661 : latches.release ();
708 25661 : return latch;
709 : }
710 :
711 : /* Callback for make_forwarder_block. Returns true if the edge E is marked
712 : in the set SET(DATA). */
713 :
714 : static bool
715 71464 : mfb_redirect_edges_in_set (edge e, void *data)
716 : {
717 71464 : hash_set<edge> *set = (hash_set<edge> *)data;
718 71464 : return set->contains (e);
719 : }
720 :
721 : /* Creates a subloop of LOOP with latch edge LATCH. */
722 :
723 : static void
724 3407 : form_subloop (class loop *loop, edge latch)
725 : {
726 3407 : edge_iterator ei;
727 3407 : edge e, new_entry;
728 3407 : class loop *new_loop;
729 :
730 3407 : hash_set<edge> *reis_set = new hash_set<edge>;
731 14037 : FOR_EACH_EDGE (e, ei, loop->header->preds)
732 : {
733 10630 : if (e != latch)
734 7223 : reis_set->add (e);
735 : }
736 3407 : new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set, reis_set);
737 3407 : delete reis_set;
738 :
739 3407 : loop->header = new_entry->src;
740 :
741 : /* Find the blocks and subloops that belong to the new loop, and add it to
742 : the appropriate place in the loop tree. */
743 3407 : new_loop = alloc_loop ();
744 3407 : new_loop->header = new_entry->dest;
745 3407 : new_loop->latch = latch->src;
746 3407 : add_loop (new_loop, loop);
747 3407 : }
748 :
749 : /* Make all the latch edges of LOOP to go to a single forwarder block --
750 : a new latch of LOOP. */
751 :
752 : static void
753 22254 : merge_latch_edges (class loop *loop)
754 : {
755 22254 : vec<edge> latches = get_loop_latch_edges (loop);
756 22254 : edge latch, e;
757 22254 : unsigned i;
758 :
759 22254 : gcc_assert (latches.length () > 0);
760 :
761 22254 : if (latches.length () == 1)
762 5697 : loop->latch = latches[0]->src;
763 : else
764 : {
765 16557 : if (dump_file)
766 8 : fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num);
767 :
768 16557 : hash_set<edge> *reis_set = new hash_set<edge>;
769 76583 : FOR_EACH_VEC_ELT (latches, i, e)
770 43469 : reis_set->add (e);
771 16557 : latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set, reis_set);
772 16557 : delete reis_set;
773 :
774 16557 : loop->header = latch->dest;
775 16557 : loop->latch = latch->src;
776 : }
777 :
778 22254 : latches.release ();
779 22254 : }
780 :
781 : /* LOOP may have several latch edges. Transform it into (possibly several)
782 : loops with single latch edge. */
783 :
784 : static void
785 22254 : disambiguate_multiple_latches (class loop *loop)
786 : {
787 22254 : edge e;
788 :
789 : /* We eliminate the multiple latches by splitting the header to the forwarder
790 : block F and the rest R, and redirecting the edges. There are two cases:
791 :
792 : 1) If there is a latch edge E that corresponds to a subloop (we guess
793 : that based on profile -- if it is taken much more often than the
794 : remaining edges; and on trees, using the information about induction
795 : variables of the loops), we redirect E to R, all the remaining edges to
796 : F, then rescan the loops and try again for the outer loop.
797 : 2) If there is no such edge, we redirect all latch edges to F, and the
798 : entry edges to R, thus making F the single latch of the loop. */
799 :
800 22254 : if (dump_file)
801 9 : fprintf (dump_file, "Disambiguating loop %d with multiple latches\n",
802 : loop->num);
803 :
804 : /* During latch merging, we may need to redirect the entry edges to a new
805 : block. This would cause problems if the entry edge was the one from the
806 : entry block. To avoid having to handle this case specially, split
807 : such entry edge. */
808 22254 : e = find_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), loop->header);
809 22254 : if (e)
810 936 : split_edge (e);
811 :
812 29068 : while (1)
813 : {
814 25661 : e = find_subloop_latch_edge (loop);
815 25661 : if (!e)
816 : break;
817 :
818 3407 : form_subloop (loop, e);
819 : }
820 :
821 22254 : merge_latch_edges (loop);
822 22254 : }
823 :
824 : /* Split loops with multiple latch edges. */
825 :
826 : void
827 28451265 : disambiguate_loops_with_multiple_latches (void)
828 : {
829 102966169 : for (auto loop : loops_list (cfun, 0))
830 : {
831 17612374 : if (!loop->latch)
832 22254 : disambiguate_multiple_latches (loop);
833 28451265 : }
834 28451265 : }
835 :
836 : /* Return nonzero if basic block BB belongs to LOOP. */
837 : bool
838 3238569687 : flow_bb_inside_loop_p (const class loop *loop, const_basic_block bb)
839 : {
840 3238569687 : class loop *source_loop;
841 :
842 3238569687 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
843 3238556755 : || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
844 : return 0;
845 :
846 3220515671 : source_loop = bb->loop_father;
847 3220515671 : return loop == source_loop || flow_loop_nested_p (loop, source_loop);
848 : }
849 :
850 : /* Enumeration predicate for get_loop_body_with_size. */
851 : static bool
852 1227422580 : glb_enum_p (const_basic_block bb, const void *glb_loop)
853 : {
854 1227422580 : const class loop *const loop = (const class loop *) glb_loop;
855 1227422580 : return (bb != loop->header
856 1227422580 : && dominated_by_p (CDI_DOMINATORS, bb, loop->header));
857 : }
858 :
859 : /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
860 : order against direction of edges from latch. Specially, if
861 : header != latch, latch is the 1-st block. LOOP cannot be the fake
862 : loop tree root, and its size must be at most MAX_SIZE. The blocks
863 : in the LOOP body are stored to BODY, and the size of the LOOP is
864 : returned. */
865 :
866 : unsigned
867 219480690 : get_loop_body_with_size (const class loop *loop, basic_block *body,
868 : unsigned max_size)
869 : {
870 219480690 : return dfs_enumerate_from (loop->header, 1, glb_enum_p,
871 219480690 : body, max_size, loop);
872 : }
873 :
874 : /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
875 : order against direction of edges from latch. Specially, if
876 : header != latch, latch is the 1-st block. */
877 :
878 : basic_block *
879 22258884 : get_loop_body (const class loop *loop)
880 : {
881 22258884 : basic_block *body, bb;
882 22258884 : unsigned tv = 0;
883 :
884 22258884 : gcc_assert (loop->num_nodes);
885 :
886 22258884 : body = XNEWVEC (basic_block, loop->num_nodes);
887 :
888 22258884 : if (loop->latch == EXIT_BLOCK_PTR_FOR_FN (cfun))
889 : {
890 : /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
891 : special-case the fake loop that contains the whole function. */
892 7052 : gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks_for_fn (cfun));
893 7052 : body[tv++] = loop->header;
894 7052 : body[tv++] = EXIT_BLOCK_PTR_FOR_FN (cfun);
895 30569 : FOR_EACH_BB_FN (bb, cfun)
896 23517 : body[tv++] = bb;
897 : }
898 : else
899 22251832 : tv = get_loop_body_with_size (loop, body, loop->num_nodes);
900 :
901 22258884 : gcc_assert (tv == loop->num_nodes);
902 22258884 : return body;
903 : }
904 :
905 : /* Fills dominance descendants inside LOOP of the basic block BB into
906 : array TOVISIT from index *TV. */
907 :
908 : static void
909 5695572 : fill_sons_in_loop (const class loop *loop, basic_block bb,
910 : basic_block *tovisit, int *tv)
911 : {
912 9421074 : basic_block son, postpone = NULL;
913 :
914 9421074 : tovisit[(*tv)++] = bb;
915 9421074 : for (son = first_dom_son (CDI_DOMINATORS, bb);
916 19076519 : son;
917 9655445 : son = next_dom_son (CDI_DOMINATORS, son))
918 : {
919 9655445 : if (!flow_bb_inside_loop_p (loop, son))
920 2215209 : continue;
921 :
922 7440236 : if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
923 : {
924 3725502 : postpone = son;
925 3725502 : continue;
926 : }
927 3714734 : fill_sons_in_loop (loop, son, tovisit, tv);
928 : }
929 :
930 9421074 : if (postpone)
931 : fill_sons_in_loop (loop, postpone, tovisit, tv);
932 5695572 : }
933 :
934 : /* Gets body of a LOOP (that must be different from the outermost loop)
935 : sorted by dominance relation. Additionally, if a basic block s dominates
936 : the latch, then only blocks dominated by s are be after it. */
937 :
938 : basic_block *
939 1980838 : get_loop_body_in_dom_order (const class loop *loop)
940 : {
941 1980838 : basic_block *tovisit;
942 1980838 : int tv;
943 :
944 1980838 : gcc_assert (loop->num_nodes);
945 :
946 1980838 : tovisit = XNEWVEC (basic_block, loop->num_nodes);
947 :
948 1980838 : gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
949 :
950 1980838 : tv = 0;
951 1980838 : fill_sons_in_loop (loop, loop->header, tovisit, &tv);
952 :
953 1980838 : gcc_assert (tv == (int) loop->num_nodes);
954 :
955 1980838 : return tovisit;
956 : }
957 :
958 : /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
959 :
960 : basic_block *
961 55 : get_loop_body_in_custom_order (const class loop *loop,
962 : int (*bb_comparator) (const void *, const void *))
963 : {
964 55 : basic_block *bbs = get_loop_body (loop);
965 :
966 55 : qsort (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator);
967 :
968 55 : return bbs;
969 : }
970 :
971 : /* Same as above, but use gcc_sort_r instead of qsort. */
972 :
973 : basic_block *
974 147235 : get_loop_body_in_custom_order (const class loop *loop, void *data,
975 : int (*bb_comparator) (const void *, const void *, void *))
976 : {
977 147235 : basic_block *bbs = get_loop_body (loop);
978 :
979 147235 : gcc_sort_r (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator, data);
980 :
981 147235 : return bbs;
982 : }
983 :
984 : /* Get body of a LOOP in breadth first sort order. */
985 :
986 : basic_block *
987 399596 : get_loop_body_in_bfs_order (const class loop *loop)
988 : {
989 399596 : basic_block *blocks;
990 399596 : basic_block bb;
991 399596 : unsigned int i = 1;
992 399596 : unsigned int vc = 0;
993 :
994 399596 : gcc_assert (loop->num_nodes);
995 399596 : gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
996 :
997 399596 : blocks = XNEWVEC (basic_block, loop->num_nodes);
998 399596 : auto_bitmap visited;
999 399596 : blocks[0] = loop->header;
1000 399596 : bitmap_set_bit (visited, loop->header->index);
1001 2090113 : while (i < loop->num_nodes)
1002 : {
1003 1290921 : edge e;
1004 1290921 : edge_iterator ei;
1005 1290921 : gcc_assert (i > vc);
1006 1290921 : bb = blocks[vc++];
1007 :
1008 3541843 : FOR_EACH_EDGE (e, ei, bb->succs)
1009 : {
1010 2250922 : if (flow_bb_inside_loop_p (loop, e->dest))
1011 : {
1012 : /* This bb is now visited. */
1013 1543479 : if (bitmap_set_bit (visited, e->dest->index))
1014 1341842 : blocks[i++] = e->dest;
1015 : }
1016 : }
1017 : }
1018 :
1019 399596 : return blocks;
1020 399596 : }
1021 :
1022 : /* Hash function for struct loop_exit. */
1023 :
1024 : hashval_t
1025 251946762 : loop_exit_hasher::hash (loop_exit *exit)
1026 : {
1027 251946762 : return htab_hash_pointer (exit->e);
1028 : }
1029 :
1030 : /* Equality function for struct loop_exit. Compares with edge. */
1031 :
1032 : bool
1033 298753596 : loop_exit_hasher::equal (loop_exit *exit, edge e)
1034 : {
1035 298753596 : return exit->e == e;
1036 : }
1037 :
1038 : /* Frees the list of loop exit descriptions EX. */
1039 :
1040 : void
1041 19266152 : loop_exit_hasher::remove (loop_exit *exit)
1042 : {
1043 19266152 : loop_exit *next;
1044 40006025 : for (; exit; exit = next)
1045 : {
1046 20739873 : next = exit->next_e;
1047 :
1048 20739873 : exit->next->prev = exit->prev;
1049 20739873 : exit->prev->next = exit->next;
1050 :
1051 20739873 : ggc_free (exit);
1052 : }
1053 19266152 : }
1054 :
1055 : /* Returns the list of records for E as an exit of a loop. */
1056 :
1057 : static struct loop_exit *
1058 40847446 : get_exit_descriptions (edge e)
1059 : {
1060 40847446 : return current_loops->exits->find_with_hash (e, htab_hash_pointer (e));
1061 : }
1062 :
1063 : /* Updates the lists of loop exits in that E appears.
1064 : If REMOVED is true, E is being removed, and we
1065 : just remove it from the lists of exits.
1066 : If NEW_EDGE is true and E is not a loop exit, we
1067 : do not try to remove it from loop exit lists. */
1068 :
1069 : void
1070 549635149 : rescan_loop_exit (edge e, bool new_edge, bool removed)
1071 : {
1072 549635149 : struct loop_exit *exits = NULL, *exit;
1073 549635149 : class loop *aloop, *cloop;
1074 :
1075 549635149 : if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1076 : return;
1077 :
1078 253190005 : if (!removed
1079 237519753 : && e->src->loop_father != NULL
1080 237519753 : && e->dest->loop_father != NULL
1081 488675539 : && !flow_bb_inside_loop_p (e->src->loop_father, e->dest))
1082 : {
1083 37301720 : cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
1084 37301720 : for (aloop = e->src->loop_father;
1085 58041593 : aloop != cloop;
1086 20739873 : aloop = loop_outer (aloop))
1087 : {
1088 20739873 : exit = ggc_alloc<loop_exit> ();
1089 20739873 : exit->e = e;
1090 :
1091 20739873 : exit->next = aloop->exits->next;
1092 20739873 : exit->prev = aloop->exits;
1093 20739873 : exit->next->prev = exit;
1094 20739873 : exit->prev->next = exit;
1095 :
1096 20739873 : exit->next_e = exits;
1097 20739873 : exits = exit;
1098 : }
1099 : }
1100 :
1101 253190005 : if (!exits && new_edge)
1102 : return;
1103 :
1104 38535260 : loop_exit **slot
1105 57804368 : = current_loops->exits->find_slot_with_hash (e, htab_hash_pointer (e),
1106 : exits ? INSERT : NO_INSERT);
1107 38535260 : if (!slot)
1108 : return;
1109 :
1110 20592298 : if (exits)
1111 : {
1112 19266152 : if (*slot)
1113 398736 : loop_exit_hasher::remove (*slot);
1114 19266152 : *slot = exits;
1115 : }
1116 : else
1117 1326146 : current_loops->exits->clear_slot (slot);
1118 : }
1119 :
1120 : /* For each loop, record list of exit edges, and start maintaining these
1121 : lists. */
1122 :
1123 : void
1124 17270954 : record_loop_exits (void)
1125 : {
1126 17270954 : basic_block bb;
1127 17270954 : edge_iterator ei;
1128 17270954 : edge e;
1129 :
1130 17270954 : if (!current_loops)
1131 0 : return;
1132 :
1133 17270954 : if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1134 : return;
1135 17270954 : loops_state_set (LOOPS_HAVE_RECORDED_EXITS);
1136 :
1137 17270954 : gcc_assert (current_loops->exits == NULL);
1138 17270954 : current_loops->exits
1139 34541908 : = hash_table<loop_exit_hasher>::create_ggc (2 * number_of_loops (cfun));
1140 :
1141 173010570 : FOR_EACH_BB_FN (bb, cfun)
1142 : {
1143 374003639 : FOR_EACH_EDGE (e, ei, bb->succs)
1144 : {
1145 218264023 : rescan_loop_exit (e, true, false);
1146 : }
1147 : }
1148 : }
1149 :
1150 : /* Dumps information about the exit in *SLOT to FILE.
1151 : Callback for htab_traverse. */
1152 :
1153 : int
1154 0 : dump_recorded_exit (loop_exit **slot, FILE *file)
1155 : {
1156 0 : struct loop_exit *exit = *slot;
1157 0 : unsigned n = 0;
1158 0 : edge e = exit->e;
1159 :
1160 0 : for (; exit != NULL; exit = exit->next_e)
1161 0 : n++;
1162 :
1163 0 : fprintf (file, "Edge %d->%d exits %u loops\n",
1164 0 : e->src->index, e->dest->index, n);
1165 :
1166 0 : return 1;
1167 : }
1168 :
1169 : /* Dumps the recorded exits of loops to FILE. */
1170 :
1171 : extern void dump_recorded_exits (FILE *);
1172 : void
1173 0 : dump_recorded_exits (FILE *file)
1174 : {
1175 0 : if (!current_loops->exits)
1176 : return;
1177 0 : current_loops->exits->traverse<FILE *, dump_recorded_exit> (file);
1178 : }
1179 :
1180 : /* Releases lists of loop exits. */
1181 :
1182 : void
1183 17270954 : release_recorded_exits (function *fn)
1184 : {
1185 17270954 : gcc_assert (loops_state_satisfies_p (fn, LOOPS_HAVE_RECORDED_EXITS));
1186 17270954 : loops_for_fn (fn)->exits->empty ();
1187 17270954 : loops_for_fn (fn)->exits = NULL;
1188 17270954 : loops_state_clear (fn, LOOPS_HAVE_RECORDED_EXITS);
1189 17270954 : }
1190 :
1191 : /* Returns the list of the exit edges of a LOOP. */
1192 :
1193 : auto_vec<edge>
1194 36818484 : get_loop_exit_edges (const class loop *loop, basic_block *body)
1195 : {
1196 36818484 : auto_vec<edge> edges;
1197 36818484 : edge e;
1198 36818484 : unsigned i;
1199 36818484 : edge_iterator ei;
1200 36818484 : struct loop_exit *exit;
1201 :
1202 36818484 : gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1203 :
1204 : /* If we maintain the lists of exits, use them. Otherwise we must
1205 : scan the body of the loop. */
1206 36818484 : if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1207 : {
1208 112374581 : for (exit = loop->exits->next; exit->e; exit = exit->next)
1209 76222991 : edges.safe_push (exit->e);
1210 : }
1211 : else
1212 : {
1213 666894 : bool body_from_caller = true;
1214 666894 : if (!body)
1215 : {
1216 657959 : body = get_loop_body (loop);
1217 657959 : body_from_caller = false;
1218 : }
1219 4809471 : for (i = 0; i < loop->num_nodes; i++)
1220 10802045 : FOR_EACH_EDGE (e, ei, body[i]->succs)
1221 : {
1222 6659468 : if (!flow_bb_inside_loop_p (loop, e->dest))
1223 1612564 : edges.safe_push (e);
1224 : }
1225 666894 : if (!body_from_caller)
1226 657959 : free (body);
1227 : }
1228 :
1229 36818484 : return edges;
1230 : }
1231 :
1232 : /* Counts the number of conditional branches inside LOOP. */
1233 :
1234 : unsigned
1235 134 : num_loop_branches (const class loop *loop)
1236 : {
1237 134 : unsigned i, n;
1238 134 : basic_block * body;
1239 :
1240 134 : gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1241 :
1242 134 : body = get_loop_body (loop);
1243 134 : n = 0;
1244 635 : for (i = 0; i < loop->num_nodes; i++)
1245 569 : if (EDGE_COUNT (body[i]->succs) >= 2)
1246 202 : n++;
1247 134 : free (body);
1248 :
1249 134 : return n;
1250 : }
1251 :
1252 : /* Adds basic block BB to LOOP. */
1253 : void
1254 44847480 : add_bb_to_loop (basic_block bb, class loop *loop)
1255 : {
1256 44847480 : unsigned i;
1257 44847480 : loop_p ploop;
1258 44847480 : edge_iterator ei;
1259 44847480 : edge e;
1260 :
1261 44847480 : gcc_assert (bb->loop_father == NULL);
1262 44847480 : bb->loop_father = loop;
1263 44847480 : loop->num_nodes++;
1264 65014076 : FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
1265 20166596 : ploop->num_nodes++;
1266 :
1267 93794494 : FOR_EACH_EDGE (e, ei, bb->succs)
1268 : {
1269 48947014 : rescan_loop_exit (e, true, false);
1270 : }
1271 75247458 : FOR_EACH_EDGE (e, ei, bb->preds)
1272 : {
1273 30399978 : rescan_loop_exit (e, true, false);
1274 : }
1275 44847480 : }
1276 :
1277 : /* Remove basic block BB from loops. */
1278 : void
1279 56288287 : remove_bb_from_loops (basic_block bb)
1280 : {
1281 56288287 : unsigned i;
1282 56288287 : class loop *loop = bb->loop_father;
1283 56288287 : loop_p ploop;
1284 56288287 : edge_iterator ei;
1285 56288287 : edge e;
1286 :
1287 56288287 : gcc_assert (loop != NULL);
1288 56288287 : loop->num_nodes--;
1289 77723745 : FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
1290 21435458 : ploop->num_nodes--;
1291 56288287 : bb->loop_father = NULL;
1292 :
1293 84965995 : FOR_EACH_EDGE (e, ei, bb->succs)
1294 : {
1295 28677708 : rescan_loop_exit (e, false, true);
1296 : }
1297 76828781 : FOR_EACH_EDGE (e, ei, bb->preds)
1298 : {
1299 20540494 : rescan_loop_exit (e, false, true);
1300 : }
1301 56288287 : }
1302 :
1303 : /* Finds nearest common ancestor in loop tree for given loops. */
1304 : class loop *
1305 205787325 : find_common_loop (class loop *loop_s, class loop *loop_d)
1306 : {
1307 205787325 : unsigned sdepth, ddepth;
1308 :
1309 205787325 : if (!loop_s) return loop_d;
1310 205786782 : if (!loop_d) return loop_s;
1311 :
1312 205786782 : sdepth = loop_depth (loop_s);
1313 205786782 : ddepth = loop_depth (loop_d);
1314 :
1315 83669011 : if (sdepth < ddepth)
1316 6341325 : loop_d = (*loop_d->superloops)[sdepth];
1317 199445457 : else if (sdepth > ddepth)
1318 100399006 : loop_s = (*loop_s->superloops)[ddepth];
1319 :
1320 206717496 : while (loop_s != loop_d)
1321 : {
1322 930714 : loop_s = loop_outer (loop_s);
1323 930714 : loop_d = loop_outer (loop_d);
1324 : }
1325 : return loop_s;
1326 : }
1327 :
1328 : /* Removes LOOP from structures and frees its data. */
1329 :
1330 : void
1331 149954 : delete_loop (class loop *loop)
1332 : {
1333 : /* Remove the loop from structure. */
1334 149954 : flow_loop_tree_node_remove (loop);
1335 :
1336 : /* Remove loop from loops array. */
1337 149954 : (*current_loops->larray)[loop->num] = NULL;
1338 :
1339 : /* Free loop data. */
1340 149954 : flow_loop_free (loop);
1341 149954 : }
1342 :
1343 : /* Cancels the LOOP; it must be innermost one. */
1344 :
1345 : static void
1346 10604 : cancel_loop (class loop *loop)
1347 : {
1348 10604 : basic_block *bbs;
1349 10604 : unsigned i;
1350 10604 : class loop *outer = loop_outer (loop);
1351 :
1352 10604 : gcc_assert (!loop->inner);
1353 :
1354 : /* Move blocks up one level (they should be removed as soon as possible). */
1355 10604 : bbs = get_loop_body (loop);
1356 43927 : for (i = 0; i < loop->num_nodes; i++)
1357 22719 : bbs[i]->loop_father = outer;
1358 :
1359 10604 : free (bbs);
1360 10604 : delete_loop (loop);
1361 10604 : }
1362 :
1363 : /* Cancels LOOP and all its subloops. */
1364 : void
1365 10604 : cancel_loop_tree (class loop *loop)
1366 : {
1367 11092 : while (loop->inner)
1368 488 : cancel_loop_tree (loop->inner);
1369 10604 : cancel_loop (loop);
1370 10604 : }
1371 :
1372 : /* Disable warnings about missing quoting in GCC diagnostics for
1373 : the verification errors. Their format strings don't follow GCC
1374 : diagnostic conventions and the calls are ultimately followed by
1375 : a deliberate ICE triggered by a failed assertion. */
1376 : #if __GNUC__ >= 10
1377 : # pragma GCC diagnostic push
1378 : # pragma GCC diagnostic ignored "-Wformat-diag"
1379 : #endif
1380 :
1381 : /* Checks that information about loops is correct
1382 : -- sizes of loops are all right
1383 : -- results of get_loop_body really belong to the loop
1384 : -- loop header have just single entry edge and single latch edge
1385 : -- loop latches have only single successor that is header of their loop
1386 : -- irreducible loops are correctly marked
1387 : -- the cached loop depth and loop father of each bb is correct
1388 : */
1389 : DEBUG_FUNCTION void
1390 370942583 : verify_loop_structure (void)
1391 : {
1392 370942583 : unsigned *sizes, i, j;
1393 370942583 : basic_block bb, *bbs;
1394 370942583 : int err = 0;
1395 370942583 : edge e;
1396 370942583 : unsigned num = number_of_loops (cfun);
1397 370942583 : struct loop_exit *exit, *mexit;
1398 370942583 : bool dom_available = dom_info_available_p (CDI_DOMINATORS);
1399 :
1400 370942583 : if (loops_state_satisfies_p (LOOPS_NEED_FIXUP))
1401 : {
1402 0 : error ("loop verification on loop tree that needs fixup");
1403 0 : err = 1;
1404 : }
1405 :
1406 : /* We need up-to-date dominators, compute or verify them. */
1407 370942583 : if (!dom_available)
1408 100469992 : calculate_dominance_info (CDI_DOMINATORS);
1409 : else
1410 270472591 : verify_dominators (CDI_DOMINATORS);
1411 :
1412 : /* Check the loop tree root. */
1413 370942583 : if (current_loops->tree_root->header != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1414 370942583 : || current_loops->tree_root->latch != EXIT_BLOCK_PTR_FOR_FN (cfun)
1415 370942583 : || (current_loops->tree_root->num_nodes
1416 370942583 : != (unsigned) n_basic_blocks_for_fn (cfun)))
1417 : {
1418 0 : error ("corrupt loop tree root");
1419 0 : err = 1;
1420 : }
1421 :
1422 : /* Check the headers. */
1423 3678524893 : FOR_EACH_BB_FN (bb, cfun)
1424 3307582310 : if (bb_loop_header_p (bb))
1425 : {
1426 196578308 : if (bb->loop_father->header == NULL)
1427 : {
1428 0 : error ("loop with header %d marked for removal", bb->index);
1429 0 : err = 1;
1430 : }
1431 196578308 : else if (bb->loop_father->header != bb)
1432 : {
1433 0 : error ("loop with header %d not in loop tree", bb->index);
1434 0 : err = 1;
1435 : }
1436 : }
1437 3111004002 : else if (bb->loop_father->header == bb)
1438 : {
1439 0 : error ("non-loop with header %d not marked for removal", bb->index);
1440 0 : err = 1;
1441 : }
1442 :
1443 : /* Check the recorded loop father and sizes of loops. */
1444 370942583 : auto_sbitmap visited (last_basic_block_for_fn (cfun));
1445 370942583 : bitmap_clear (visited);
1446 370942583 : bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
1447 1309406057 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1448 : {
1449 196578308 : unsigned n;
1450 :
1451 196578308 : if (loop->header == NULL)
1452 : {
1453 0 : error ("removed loop %d in loop tree", loop->num);
1454 0 : err = 1;
1455 0 : continue;
1456 : }
1457 :
1458 196578308 : n = get_loop_body_with_size (loop, bbs, n_basic_blocks_for_fn (cfun));
1459 196578308 : if (loop->num_nodes != n)
1460 : {
1461 0 : error ("size of loop %d should be %d, not %d",
1462 : loop->num, n, loop->num_nodes);
1463 0 : err = 1;
1464 : }
1465 :
1466 1304882908 : for (j = 0; j < n; j++)
1467 : {
1468 1108304600 : bb = bbs[j];
1469 :
1470 1108304600 : if (!flow_bb_inside_loop_p (loop, bb))
1471 : {
1472 0 : error ("bb %d does not belong to loop %d",
1473 : bb->index, loop->num);
1474 0 : err = 1;
1475 : }
1476 :
1477 : /* Ignore this block if it is in an inner loop. */
1478 1108304600 : if (bitmap_bit_p (visited, bb->index))
1479 260601113 : continue;
1480 847703487 : bitmap_set_bit (visited, bb->index);
1481 :
1482 847703487 : if (bb->loop_father != loop)
1483 : {
1484 0 : error ("bb %d has father loop %d, should be loop %d",
1485 : bb->index, bb->loop_father->num, loop->num);
1486 0 : err = 1;
1487 : }
1488 : }
1489 370942583 : }
1490 370942583 : free (bbs);
1491 :
1492 : /* Check headers and latches. */
1493 1309406057 : for (auto loop : loops_list (cfun, 0))
1494 : {
1495 196578308 : i = loop->num;
1496 196578308 : if (loop->header == NULL)
1497 0 : continue;
1498 196578308 : if (!bb_loop_header_p (loop->header))
1499 : {
1500 0 : error ("loop %d%'s header is not a loop header", i);
1501 0 : err = 1;
1502 : }
1503 196578308 : if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
1504 196578308 : && EDGE_COUNT (loop->header->preds) != 2)
1505 : {
1506 0 : error ("loop %d%'s header does not have exactly 2 entries", i);
1507 0 : err = 1;
1508 : }
1509 196578308 : if (loop->latch)
1510 : {
1511 195677850 : if (!find_edge (loop->latch, loop->header))
1512 : {
1513 0 : error ("loop %d%'s latch does not have an edge to its header", i);
1514 0 : err = 1;
1515 : }
1516 195677850 : if (!dominated_by_p (CDI_DOMINATORS, loop->latch, loop->header))
1517 : {
1518 0 : error ("loop %d%'s latch is not dominated by its header", i);
1519 0 : err = 1;
1520 : }
1521 : }
1522 196578308 : if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
1523 : {
1524 30283717 : if (!single_succ_p (loop->latch))
1525 : {
1526 0 : error ("loop %d%'s latch does not have exactly 1 successor", i);
1527 0 : err = 1;
1528 : }
1529 30283717 : if (single_succ (loop->latch) != loop->header)
1530 : {
1531 0 : error ("loop %d%'s latch does not have header as successor", i);
1532 0 : err = 1;
1533 : }
1534 30283717 : if (loop->latch->loop_father != loop)
1535 : {
1536 0 : error ("loop %d%'s latch does not belong directly to it", i);
1537 0 : err = 1;
1538 : }
1539 : }
1540 196578308 : if (loop->header->loop_father != loop)
1541 : {
1542 0 : error ("loop %d%'s header does not belong directly to it", i);
1543 0 : err = 1;
1544 : }
1545 196578308 : if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1546 : {
1547 26998888 : edge_iterator ei;
1548 80996923 : FOR_EACH_EDGE (e, ei, loop->header->preds)
1549 53998035 : if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header)
1550 53998035 : && e->flags & EDGE_IRREDUCIBLE_LOOP)
1551 : {
1552 0 : error ("loop %d%'s latch is marked as part of irreducible"
1553 : " region", i);
1554 0 : err = 1;
1555 : }
1556 : }
1557 :
1558 : /* Check cached number of iterations for released SSA names. */
1559 196578308 : tree ref;
1560 196578308 : if (loop->nb_iterations
1561 196578308 : && (ref = walk_tree (&loop->nb_iterations,
1562 : find_released_ssa_name, NULL, NULL)))
1563 : {
1564 0 : error ("loop %d%'s number of iterations %qE references the"
1565 : " released SSA name %qE", i, loop->nb_iterations, ref);
1566 0 : err = 1;
1567 : }
1568 370942583 : }
1569 :
1570 : /* Check irreducible loops. */
1571 370942583 : if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1572 : {
1573 33485058 : auto_edge_flag saved_edge_irr (cfun);
1574 33485058 : auto_bb_flag saved_bb_irr (cfun);
1575 : /* Save old info. */
1576 429308905 : FOR_EACH_BB_FN (bb, cfun)
1577 : {
1578 395823847 : edge_iterator ei;
1579 395823847 : if (bb->flags & BB_IRREDUCIBLE_LOOP)
1580 546175 : bb->flags |= saved_bb_irr;
1581 951000150 : FOR_EACH_EDGE (e, ei, bb->succs)
1582 555176303 : if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1583 787196 : e->flags |= saved_edge_irr;
1584 : }
1585 :
1586 : /* Recount it. */
1587 33485058 : mark_irreducible_loops ();
1588 :
1589 : /* Compare. */
1590 429308905 : FOR_EACH_BB_FN (bb, cfun)
1591 : {
1592 395823847 : edge_iterator ei;
1593 :
1594 395823847 : if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1595 395823847 : && !(bb->flags & saved_bb_irr))
1596 : {
1597 0 : error ("basic block %d should be marked irreducible", bb->index);
1598 0 : err = 1;
1599 : }
1600 395823847 : else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1601 395823847 : && (bb->flags & saved_bb_irr))
1602 : {
1603 0 : error ("basic block %d should not be marked irreducible", bb->index);
1604 0 : err = 1;
1605 : }
1606 395823847 : bb->flags &= ~saved_bb_irr;
1607 951000150 : FOR_EACH_EDGE (e, ei, bb->succs)
1608 : {
1609 555176303 : if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1610 555176303 : && !(e->flags & saved_edge_irr))
1611 : {
1612 0 : error ("edge from %d to %d should be marked irreducible",
1613 0 : e->src->index, e->dest->index);
1614 0 : err = 1;
1615 : }
1616 555176303 : else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1617 555176303 : && (e->flags & saved_edge_irr))
1618 : {
1619 0 : error ("edge from %d to %d should not be marked irreducible",
1620 0 : e->src->index, e->dest->index);
1621 0 : err = 1;
1622 : }
1623 555176303 : e->flags &= ~saved_edge_irr;
1624 : }
1625 : }
1626 33485058 : }
1627 :
1628 : /* Check the recorded loop exits. */
1629 1309406057 : for (auto loop : loops_list (cfun, 0))
1630 : {
1631 196578308 : if (!loop->exits || loop->exits->e != NULL)
1632 : {
1633 0 : error ("corrupted head of the exits list of loop %d",
1634 : loop->num);
1635 0 : err = 1;
1636 : }
1637 : else
1638 : {
1639 : /* Check that the list forms a cycle, and all elements except
1640 : for the head are nonnull. */
1641 196578308 : for (mexit = loop->exits, exit = mexit->next, i = 0;
1642 240499720 : exit->e && exit != mexit;
1643 43921412 : exit = exit->next)
1644 : {
1645 43921412 : if (i++ & 1)
1646 13061550 : mexit = mexit->next;
1647 : }
1648 :
1649 196578308 : if (exit != loop->exits)
1650 : {
1651 0 : error ("corrupted exits list of loop %d", loop->num);
1652 0 : err = 1;
1653 : }
1654 : }
1655 :
1656 196578308 : if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1657 : {
1658 172483282 : if (loop->exits->next != loop->exits)
1659 : {
1660 0 : error ("nonempty exits list of loop %d, but exits are not recorded",
1661 : loop->num);
1662 0 : err = 1;
1663 : }
1664 : }
1665 370942583 : }
1666 :
1667 370942583 : if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1668 : {
1669 25516363 : unsigned n_exits = 0, eloops;
1670 :
1671 25516363 : sizes = XCNEWVEC (unsigned, num);
1672 25516363 : memset (sizes, 0, sizeof (unsigned) * num);
1673 360577994 : FOR_EACH_BB_FN (bb, cfun)
1674 : {
1675 335061631 : edge_iterator ei;
1676 335061631 : if (bb->loop_father == current_loops->tree_root)
1677 222584339 : continue;
1678 287607119 : FOR_EACH_EDGE (e, ei, bb->succs)
1679 : {
1680 175129827 : if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
1681 134282381 : continue;
1682 :
1683 40847446 : n_exits++;
1684 40847446 : exit = get_exit_descriptions (e);
1685 40847446 : if (!exit)
1686 : {
1687 0 : error ("exit %d->%d not recorded",
1688 0 : e->src->index, e->dest->index);
1689 0 : err = 1;
1690 : }
1691 40847446 : eloops = 0;
1692 84768858 : for (; exit; exit = exit->next_e)
1693 43921412 : eloops++;
1694 :
1695 40847446 : for (class loop *loop = bb->loop_father;
1696 84768858 : loop != e->dest->loop_father
1697 : /* When a loop exit is also an entry edge which
1698 : can happen when avoiding CFG manipulations
1699 : then the last loop exited is the outer loop
1700 : of the loop entered. */
1701 84768858 : && loop != loop_outer (e->dest->loop_father);
1702 43921412 : loop = loop_outer (loop))
1703 : {
1704 43921412 : eloops--;
1705 43921412 : sizes[loop->num]++;
1706 : }
1707 :
1708 40847446 : if (eloops != 0)
1709 : {
1710 0 : error ("wrong list of exited loops for edge %d->%d",
1711 0 : e->src->index, e->dest->index);
1712 0 : err = 1;
1713 : }
1714 : }
1715 : }
1716 :
1717 25516363 : if (n_exits != current_loops->exits->elements ())
1718 : {
1719 0 : error ("too many loop exits recorded");
1720 0 : err = 1;
1721 : }
1722 :
1723 100644115 : for (auto loop : loops_list (cfun, 0))
1724 : {
1725 24095026 : eloops = 0;
1726 68016438 : for (exit = loop->exits->next; exit->e; exit = exit->next)
1727 43921412 : eloops++;
1728 24095026 : if (eloops != sizes[loop->num])
1729 : {
1730 0 : error ("%d exits recorded for loop %d (having %d exits)",
1731 : eloops, loop->num, sizes[loop->num]);
1732 0 : err = 1;
1733 : }
1734 25516363 : }
1735 :
1736 25516363 : free (sizes);
1737 : }
1738 :
1739 370942583 : gcc_assert (!err);
1740 :
1741 370942583 : if (!dom_available)
1742 100469992 : free_dominance_info (CDI_DOMINATORS);
1743 370942583 : }
1744 :
1745 : #if __GNUC__ >= 10
1746 : # pragma GCC diagnostic pop
1747 : #endif
1748 :
1749 : /* Returns latch edge of LOOP. */
1750 : edge
1751 12760410 : loop_latch_edge (const class loop *loop)
1752 : {
1753 12760410 : return find_edge (loop->latch, loop->header);
1754 : }
1755 :
1756 : /* Returns preheader edge of LOOP. */
1757 : edge
1758 434782252 : loop_preheader_edge (const class loop *loop)
1759 : {
1760 434782252 : edge e;
1761 434782252 : edge_iterator ei;
1762 :
1763 434782252 : gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
1764 : && ! loops_state_satisfies_p (LOOPS_MAY_HAVE_MULTIPLE_LATCHES));
1765 :
1766 664811455 : FOR_EACH_EDGE (e, ei, loop->header->preds)
1767 663962075 : if (e->src != loop->latch)
1768 : break;
1769 :
1770 434782252 : if (! e)
1771 : {
1772 849380 : gcc_assert (! loop_outer (loop));
1773 849380 : return single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun));
1774 : }
1775 :
1776 : return e;
1777 : }
1778 :
1779 : /* Returns true if E is an exit of LOOP. */
1780 :
1781 : bool
1782 35799268 : loop_exit_edge_p (const class loop *loop, const_edge e)
1783 : {
1784 35799268 : return (flow_bb_inside_loop_p (loop, e->src)
1785 35799268 : && !flow_bb_inside_loop_p (loop, e->dest));
1786 : }
1787 :
1788 : /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1789 : or more than one exit. If loops do not have the exits recorded, NULL
1790 : is returned always. */
1791 :
1792 : edge
1793 35512845 : single_exit (const class loop *loop)
1794 : {
1795 35512845 : struct loop_exit *exit = loop->exits->next;
1796 :
1797 35512845 : if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1798 : return NULL;
1799 :
1800 35484125 : if (exit->e && exit->next == loop->exits)
1801 : return exit->e;
1802 : else
1803 10547524 : return NULL;
1804 : }
1805 :
1806 : /* Returns incoming edge when BB has an incoming edge exiting LOOP, else return
1807 : NULL. */
1808 :
1809 : edge
1810 0 : loop_exits_to_bb_p (class loop *loop, basic_block bb)
1811 : {
1812 0 : edge e;
1813 0 : edge_iterator ei;
1814 :
1815 0 : FOR_EACH_EDGE (e, ei, bb->preds)
1816 0 : if (loop_exit_edge_p (loop, e))
1817 : return e;
1818 :
1819 : return NULL;
1820 : }
1821 :
1822 : /* Returns outgoing edge when BB has an outgoing edge exiting LOOP, else return
1823 : NULL. */
1824 :
1825 : edge
1826 1475349 : loop_exits_from_bb_p (class loop *loop, basic_block bb)
1827 : {
1828 1475349 : edge e;
1829 1475349 : edge_iterator ei;
1830 :
1831 3108929 : FOR_EACH_EDGE (e, ei, bb->succs)
1832 2589167 : if (loop_exit_edge_p (loop, e))
1833 : return e;
1834 :
1835 : return NULL;
1836 : }
1837 :
1838 : /* Return location corresponding to the loop control condition if possible. */
1839 :
1840 : dump_user_location_t
1841 583346 : get_loop_location (class loop *loop)
1842 : {
1843 583346 : rtx_insn *insn = NULL;
1844 583346 : class niter_desc *desc = NULL;
1845 583346 : 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 583346 : desc = get_simple_loop_desc (loop);
1854 583346 : if (desc->in_edge)
1855 : {
1856 587394 : FOR_BB_INSNS_REVERSE (desc->in_edge->src, insn)
1857 : {
1858 582470 : if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1859 403391 : 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 179955 : if ((exit = single_exit (loop)))
1865 : {
1866 207218 : FOR_BB_INSNS_REVERSE (exit->src, insn)
1867 : {
1868 198341 : if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1869 100215 : return insn;
1870 : }
1871 : }
1872 : /* Next check the latch, to see if it is non-empty. */
1873 188512 : FOR_BB_INSNS_REVERSE (loop->latch, insn)
1874 : {
1875 130872 : if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1876 22100 : 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 276849 : FOR_BB_INSNS (loop->header, insn)
1881 : {
1882 265591 : if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1883 46382 : return insn;
1884 : }
1885 : /* If all else fails, simply return the current function location. */
1886 11258 : return dump_user_location_t::from_function_decl (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 :
1894 : void
1895 17404064 : record_niter_bound (class loop *loop, const widest_int &i_bound,
1896 : bool realistic, bool upper)
1897 : {
1898 17404064 : if (wi::min_precision (i_bound, SIGNED) > bound_wide_int ().get_precision ())
1899 0 : return;
1900 :
1901 17404064 : bound_wide_int bound = bound_wide_int::from (i_bound, SIGNED);
1902 :
1903 : /* Update the bounds only when there is no previous estimation, or when the
1904 : current estimation is smaller. */
1905 17404064 : if (upper
1906 17404064 : && (!loop->any_upper_bound
1907 15937548 : || wi::ltu_p (bound, loop->nb_iterations_upper_bound)))
1908 : {
1909 854479 : loop->any_upper_bound = true;
1910 854479 : loop->nb_iterations_upper_bound = bound;
1911 854479 : if (!loop->any_likely_upper_bound)
1912 : {
1913 506821 : loop->any_likely_upper_bound = true;
1914 506821 : loop->nb_iterations_likely_upper_bound = bound;
1915 : }
1916 : }
1917 17404064 : if (realistic
1918 17404064 : && (!loop->any_estimate
1919 2829026 : || wi::ltu_p (bound, loop->nb_iterations_estimate)))
1920 : {
1921 241777 : loop->any_estimate = true;
1922 241777 : loop->nb_iterations_estimate = bound;
1923 : }
1924 17404064 : if (!realistic
1925 17404064 : && (!loop->any_likely_upper_bound
1926 14338267 : || wi::ltu_p (bound, loop->nb_iterations_likely_upper_bound)))
1927 : {
1928 219425 : loop->any_likely_upper_bound = true;
1929 219425 : 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 17404064 : if (loop->any_upper_bound
1935 17399845 : && loop->any_estimate
1936 26527987 : && wi::ltu_p (loop->nb_iterations_upper_bound,
1937 9123923 : loop->nb_iterations_estimate))
1938 6173 : loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
1939 17404064 : if (loop->any_upper_bound
1940 17399845 : && loop->any_likely_upper_bound
1941 34803909 : && wi::ltu_p (loop->nb_iterations_upper_bound,
1942 17399845 : loop->nb_iterations_likely_upper_bound))
1943 37681 : 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 :
1950 : HOST_WIDE_INT
1951 231 : get_estimated_loop_iterations_int (class loop *loop)
1952 : {
1953 231 : widest_int nit;
1954 231 : HOST_WIDE_INT hwi_nit;
1955 :
1956 231 : if (!get_estimated_loop_iterations (loop, &nit))
1957 : return -1;
1958 :
1959 46 : if (!wi::fits_shwi_p (nit))
1960 : return -1;
1961 46 : hwi_nit = nit.to_shwi ();
1962 :
1963 46 : return hwi_nit < 0 ? -1 : hwi_nit;
1964 231 : }
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 :
1970 : HOST_WIDE_INT
1971 308734 : max_stmt_executions_int (class loop *loop)
1972 : {
1973 308734 : HOST_WIDE_INT nit = get_max_loop_iterations_int (loop);
1974 308734 : HOST_WIDE_INT snit;
1975 :
1976 308734 : if (nit == -1)
1977 : return -1;
1978 :
1979 282499 : snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
1980 :
1981 : /* If the computation overflows, return -1. */
1982 282499 : 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 :
1989 : HOST_WIDE_INT
1990 5553094 : likely_max_stmt_executions_int (class loop *loop)
1991 : {
1992 5553094 : HOST_WIDE_INT nit = get_likely_max_loop_iterations_int (loop);
1993 5553094 : HOST_WIDE_INT snit;
1994 :
1995 5553094 : if (nit == -1)
1996 : return -1;
1997 :
1998 4657688 : snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
1999 :
2000 : /* If the computation overflows, return -1. */
2001 4657688 : 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 :
2008 : bool
2009 9936619 : get_estimated_loop_iterations (class loop *loop, widest_int *nit)
2010 : {
2011 : /* Even if the bound is not recorded, possibly we can derive one from
2012 : profile. */
2013 9936619 : if (!loop->any_estimate)
2014 : {
2015 5907576 : sreal snit;
2016 5907576 : bool reliable;
2017 5907576 : if (expected_loop_iterations_by_profile (loop, &snit, &reliable)
2018 5907576 : && reliable)
2019 : {
2020 3 : *nit = snit.to_nearest_int ();
2021 3 : return true;
2022 : }
2023 : return false;
2024 : }
2025 :
2026 4029043 : *nit = widest_int::from (loop->nb_iterations_estimate, SIGNED);
2027 4029043 : 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 :
2034 : bool
2035 23109620 : get_max_loop_iterations (const class loop *loop, widest_int *nit)
2036 : {
2037 23109620 : if (!loop->any_upper_bound)
2038 : return false;
2039 :
2040 20655034 : *nit = widest_int::from (loop->nb_iterations_upper_bound, SIGNED);
2041 20655034 : 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 :
2048 : HOST_WIDE_INT
2049 1751139 : get_max_loop_iterations_int (const class loop *loop)
2050 : {
2051 1751139 : widest_int nit;
2052 1751139 : HOST_WIDE_INT hwi_nit;
2053 :
2054 1751139 : if (!get_max_loop_iterations (loop, &nit))
2055 : return -1;
2056 :
2057 1374256 : if (!wi::fits_shwi_p (nit))
2058 : return -1;
2059 1313632 : hwi_nit = nit.to_shwi ();
2060 :
2061 1313632 : return hwi_nit < 0 ? -1 : hwi_nit;
2062 1751139 : }
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 :
2068 : bool
2069 5999869 : get_likely_max_loop_iterations (class loop *loop, widest_int *nit)
2070 : {
2071 5999869 : if (!loop->any_likely_upper_bound)
2072 : return false;
2073 :
2074 5319858 : *nit = widest_int::from (loop->nb_iterations_likely_upper_bound, SIGNED);
2075 5319858 : 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 :
2082 : HOST_WIDE_INT
2083 5616078 : get_likely_max_loop_iterations_int (class loop *loop)
2084 : {
2085 5616078 : widest_int nit;
2086 5616078 : HOST_WIDE_INT hwi_nit;
2087 :
2088 5616078 : if (!get_likely_max_loop_iterations (loop, &nit))
2089 : return -1;
2090 :
2091 5066882 : if (!wi::fits_shwi_p (nit))
2092 : return -1;
2093 4720123 : hwi_nit = nit.to_shwi ();
2094 :
2095 4720123 : return hwi_nit < 0 ? -1 : hwi_nit;
2096 5616078 : }
2097 :
2098 : /* Returns the loop depth of the loop BB belongs to. */
2099 :
2100 : int
2101 55397234 : bb_loop_depth (const_basic_block bb)
2102 : {
2103 67764686 : return bb->loop_father ? loop_depth (bb->loop_father) : 0;
2104 : }
2105 :
2106 : /* Marks LOOP for removal and sets LOOPS_NEED_FIXUP. */
2107 :
2108 : void
2109 268330 : mark_loop_for_removal (loop_p loop)
2110 : {
2111 268330 : if (loop->header == NULL)
2112 : return;
2113 268330 : loop->former_header = loop->header;
2114 268330 : loop->header = NULL;
2115 268330 : loop->latch = NULL;
2116 268330 : loops_state_set (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 :
2126 : void
2127 1363733730 : loops_list::walk_loop_tree (class loop *root, unsigned flags)
2128 : {
2129 1363733730 : bool only_innermost_p = flags & LI_ONLY_INNERMOST;
2130 1363733730 : bool from_innermost_p = flags & LI_FROM_INNERMOST;
2131 1363733730 : 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 1363733730 : if (!root->inner)
2137 : {
2138 1100683580 : if (flags & LI_INCLUDE_ROOT)
2139 12811 : this->to_visit.quick_push (root->num);
2140 1100683580 : return;
2141 : }
2142 263050150 : else if (preorder_p && flags & LI_INCLUDE_ROOT)
2143 52087 : this->to_visit.quick_push (root->num);
2144 :
2145 : class loop *aloop;
2146 68891327 : for (aloop = root->inner;
2147 331941477 : aloop->inner != NULL;
2148 68891327 : aloop = aloop->inner)
2149 : {
2150 68891327 : if (preorder_p)
2151 50059764 : this->to_visit.quick_push (aloop->num);
2152 68891327 : continue;
2153 : }
2154 :
2155 920339642 : while (1)
2156 : {
2157 920339642 : gcc_assert (aloop != root);
2158 920339642 : if (from_innermost_p || aloop->inner == NULL)
2159 790394489 : this->to_visit.quick_push (aloop->num);
2160 :
2161 920339642 : if (aloop->next)
2162 : {
2163 100230145 : for (aloop = aloop->next;
2164 588398165 : aloop->inner != NULL;
2165 100230145 : aloop = aloop->inner)
2166 : {
2167 100230145 : if (preorder_p)
2168 79885389 : this->to_visit.quick_push (aloop->num);
2169 100230145 : continue;
2170 : }
2171 : }
2172 432171622 : else if (loop_outer (aloop) == root)
2173 : break;
2174 : else
2175 : aloop = loop_outer (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 263050150 : if (from_innermost_p && flags & LI_INCLUDE_ROOT)
2181 0 : this->to_visit.quick_push (root->num);
2182 68891327 : }
2183 :
|
