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 6770 : flow_loops_cfg_dump (FILE *file)
44 : {
45 6770 : basic_block bb;
46 :
47 6770 : if (!file)
48 : return;
49 :
50 29213 : FOR_EACH_BB_FN (bb, cfun)
51 : {
52 22443 : edge succ;
53 22443 : edge_iterator ei;
54 :
55 22443 : fprintf (file, ";; %d succs { ", bb->index);
56 51763 : FOR_EACH_EDGE (succ, ei, bb->succs)
57 29320 : fprintf (file, "%d ", succ->dest->index);
58 22443 : fprintf (file, "}\n");
59 : }
60 : }
61 :
62 : /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
63 :
64 : bool
65 780010673 : flow_loop_nested_p (const class loop *outer, const class loop *loop)
66 : {
67 780010673 : unsigned odepth = loop_depth (outer);
68 :
69 780010673 : return (loop_depth (loop) > odepth
70 508792429 : && (*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 22469981 : superloop_at_depth (class loop *loop, unsigned depth)
78 : {
79 22469981 : unsigned ldepth = loop_depth (loop);
80 :
81 22469981 : gcc_assert (depth <= ldepth);
82 :
83 22469981 : if (depth == ldepth)
84 : return loop;
85 :
86 5853180 : return (*loop->superloops)[depth];
87 : }
88 :
89 : /* Returns the list of the latch edges of LOOP. */
90 :
91 : static vec<edge>
92 49767 : get_loop_latch_edges (const class loop *loop)
93 : {
94 49767 : edge_iterator ei;
95 49767 : edge e;
96 49767 : vec<edge> ret = vNULL;
97 :
98 210352 : FOR_EACH_EDGE (e, ei, loop->header->preds)
99 : {
100 160585 : if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header))
101 109290 : ret.safe_push (e);
102 : }
103 :
104 49767 : 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 8455 : flow_loop_dump (const class loop *loop, FILE *file,
112 : void (*loop_dump_aux) (const class loop *, FILE *, int),
113 : int verbose)
114 : {
115 8455 : basic_block *bbs;
116 8455 : unsigned i;
117 8455 : vec<edge> latches;
118 8455 : edge e;
119 :
120 8455 : if (! loop || ! loop->header)
121 0 : return;
122 :
123 8455 : fprintf (file, ";;\n;; Loop %d\n", loop->num);
124 :
125 8455 : fprintf (file, ";; header %d, ", loop->header->index);
126 8455 : if (loop->latch)
127 8454 : fprintf (file, "latch %d\n", loop->latch->index);
128 : else
129 : {
130 1 : fprintf (file, "multiple latches:");
131 1 : latches = get_loop_latch_edges (loop);
132 4 : FOR_EACH_VEC_ELT (latches, i, e)
133 2 : fprintf (file, " %d", e->src->index);
134 1 : latches.release ();
135 1 : fprintf (file, "\n");
136 : }
137 :
138 16910 : fprintf (file, ";; depth %d, outer %ld",
139 8455 : loop_depth (loop), (long) (loop_outer (loop)
140 1657 : ? loop_outer (loop)->num : -1));
141 8455 : print_loop_info (file, loop, ";; ");
142 :
143 8455 : fprintf (file, "\n;; nodes:");
144 8455 : bbs = get_loop_body (loop);
145 58945 : for (i = 0; i < loop->num_nodes; i++)
146 42035 : fprintf (file, " %d", bbs[i]->index);
147 8455 : free (bbs);
148 8455 : fprintf (file, "\n");
149 :
150 8455 : 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 50987599 : flow_loops_dump (FILE *file, void (*loop_dump_aux) (const class loop *, FILE *, int), int verbose)
159 : {
160 50987599 : if (!current_loops || ! file)
161 : return;
162 :
163 13596 : fprintf (file, ";; %d loops found\n", number_of_loops (cfun));
164 :
165 28782 : for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT))
166 : {
167 8388 : flow_loop_dump (loop, file, loop_dump_aux, verbose);
168 6798 : }
169 :
170 6798 : if (verbose)
171 6770 : flow_loops_cfg_dump (file);
172 : }
173 :
174 : /* Free data allocated for LOOP. */
175 :
176 : void
177 17608057 : flow_loop_free (class loop *loop)
178 : {
179 17608057 : struct loop_exit *exit, *next;
180 :
181 17608057 : 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 17622613 : for (exit = loop->exits->next; exit != loop->exits; exit = next)
188 : {
189 14556 : next = exit->next;
190 14556 : exit->next = exit;
191 14556 : exit->prev = exit;
192 : }
193 :
194 17608057 : ggc_free (loop->exits);
195 17608057 : ggc_free (loop);
196 17608057 : }
197 :
198 : /* Free all the memory allocated for LOOPS. */
199 :
200 : void
201 11143691 : flow_loops_free (struct loops *loops)
202 : {
203 11143691 : if (loops->larray)
204 : {
205 : unsigned i;
206 : loop_p loop;
207 :
208 : /* Free the loop descriptors. */
209 28842951 : FOR_EACH_VEC_SAFE_ELT (loops->larray, i, loop)
210 : {
211 17699260 : if (!loop)
212 517665 : continue;
213 :
214 17181595 : flow_loop_free (loop);
215 : }
216 :
217 22287382 : vec_free (loops->larray);
218 : }
219 11143691 : }
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 22212157 : flow_loop_nodes_find (basic_block header, class loop *loop)
226 : {
227 22212157 : vec<basic_block> stack = vNULL;
228 22212157 : int num_nodes = 1;
229 22212157 : edge latch;
230 22212157 : edge_iterator latch_ei;
231 :
232 22212157 : header->loop_father = loop;
233 :
234 67416101 : FOR_EACH_EDGE (latch, latch_ei, loop->header->preds)
235 : {
236 73578483 : if (latch->src->loop_father == loop
237 45203944 : || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header))
238 28374539 : continue;
239 :
240 16829405 : num_nodes++;
241 16829405 : stack.safe_push (latch->src);
242 16829405 : latch->src->loop_father = loop;
243 :
244 171187911 : while (!stack.is_empty ())
245 : {
246 109154562 : basic_block node;
247 109154562 : edge e;
248 109154562 : edge_iterator ei;
249 :
250 109154562 : node = stack.pop ();
251 :
252 259870893 : FOR_EACH_EDGE (e, ei, node->preds)
253 : {
254 150716331 : basic_block ancestor = e->src;
255 :
256 150716331 : if (ancestor->loop_father != loop)
257 : {
258 92325157 : ancestor->loop_father = loop;
259 92325157 : num_nodes++;
260 92325157 : stack.safe_push (ancestor);
261 : }
262 : }
263 : }
264 : }
265 22212157 : stack.release ();
266 :
267 22212157 : 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 23177687 : establish_preds (class loop *loop, class loop *father)
275 : {
276 23177687 : loop_p ploop;
277 23177687 : unsigned depth = loop_depth (father) + 1;
278 23177687 : unsigned i;
279 :
280 23177687 : loop->superloops = 0;
281 23177687 : vec_alloc (loop->superloops, depth);
282 55637978 : FOR_EACH_VEC_SAFE_ELT (father->superloops, i, ploop)
283 9282604 : loop->superloops->quick_push (ploop);
284 23177687 : loop->superloops->quick_push (father);
285 :
286 23259414 : for (ploop = loop->inner; ploop; ploop = ploop->next)
287 81727 : establish_preds (ploop, loop);
288 23177687 : }
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 23095960 : flow_loop_tree_node_add (class loop *father, class loop *loop,
299 : class loop *after)
300 : {
301 23095960 : if (after)
302 : {
303 4827 : loop->next = after->next;
304 4827 : after->next = loop;
305 : }
306 : else
307 : {
308 23091133 : loop->next = father->inner;
309 23091133 : father->inner = loop;
310 : }
311 :
312 23095960 : establish_preds (loop, father);
313 23095960 : }
314 :
315 : /* Remove LOOP from the loop hierarchy tree. */
316 :
317 : void
318 17043420 : flow_loop_tree_node_remove (class loop *loop)
319 : {
320 17043420 : class loop *prev, *father;
321 :
322 17043420 : father = loop_outer (loop);
323 :
324 : /* Remove loop from the list of sons. */
325 17043420 : if (father->inner == loop)
326 7935669 : father->inner = loop->next;
327 : else
328 : {
329 246508720 : for (prev = father->inner; prev->next != loop; prev = prev->next)
330 237400969 : continue;
331 9107751 : prev->next = loop->next;
332 : }
333 :
334 17043420 : loop->superloops = NULL;
335 17043420 : }
336 :
337 : /* Allocates and returns new loop structure. */
338 :
339 : class loop *
340 17730487 : alloc_loop (void)
341 : {
342 17730487 : class loop *loop = ggc_cleared_alloc<class loop> ();
343 :
344 17730487 : loop->exits = ggc_cleared_alloc<loop_exit> ();
345 17730487 : loop->exits->next = loop->exits->prev = loop->exits;
346 17730487 : loop->can_be_parallel = false;
347 17730487 : loop->constraints = 0;
348 17730487 : loop->nb_iterations_upper_bound = 0;
349 17730487 : loop->nb_iterations_likely_upper_bound = 0;
350 17730487 : loop->nb_iterations_estimate = 0;
351 17730487 : 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 11251485 : init_loops_structure (struct function *fn,
359 : struct loops *loops, unsigned num_loops)
360 : {
361 11251485 : class loop *root;
362 :
363 11251485 : memset (loops, 0, sizeof *loops);
364 11251485 : vec_alloc (loops->larray, num_loops);
365 :
366 : /* Dummy loop containing whole function. */
367 11251485 : root = alloc_loop ();
368 11251485 : root->num_nodes = n_basic_blocks_for_fn (fn);
369 11251485 : root->latch = EXIT_BLOCK_PTR_FOR_FN (fn);
370 11251485 : root->header = ENTRY_BLOCK_PTR_FOR_FN (fn);
371 11251485 : ENTRY_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
372 11251485 : EXIT_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
373 :
374 11251485 : loops->larray->quick_push (root);
375 11251485 : loops->tree_root = root;
376 11251485 : }
377 :
378 : /* Returns whether HEADER is a loop header. */
379 :
380 : bool
381 4011206595 : bb_loop_header_p (basic_block header)
382 : {
383 4011206595 : edge_iterator ei;
384 4011206595 : edge e;
385 :
386 : /* If we have an abnormal predecessor, do not consider the
387 : loop (not worth the problems). */
388 4011206595 : 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 9183483772 : FOR_EACH_EDGE (e, ei, header->preds)
397 : {
398 5620261670 : basic_block latch = e->src;
399 5620261670 : if (latch != ENTRY_BLOCK_PTR_FOR_FN (cfun)
400 5620261670 : && 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 22317828 : flow_loops_find (struct loops *loops)
417 : {
418 22317828 : bool from_scratch = (loops == NULL);
419 22317828 : int *rc_order;
420 22317828 : int b;
421 22317828 : unsigned i;
422 :
423 : /* Ensure that the dominators are computed. */
424 22317828 : calculate_dominance_info (CDI_DOMINATORS);
425 :
426 22317828 : if (!loops)
427 : {
428 11103591 : loops = ggc_cleared_alloc<struct loops> ();
429 11103591 : init_loops_structure (cfun, loops, 1);
430 : }
431 :
432 : /* Ensure that loop exits were released. */
433 22317828 : gcc_assert (loops->exits == NULL);
434 :
435 : /* Taking care of this degenerate case makes the rest of
436 : this code simpler. */
437 22317828 : if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
438 : return loops;
439 :
440 : /* The root loop node contains all basic-blocks. */
441 22063385 : 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 22063385 : rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
446 22063385 : 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 22063385 : auto_vec<loop_p> larray (loops->larray->length ());
451 371385145 : for (b = 0; b < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; b++)
452 : {
453 349321760 : basic_block header = BASIC_BLOCK_FOR_FN (cfun, rc_order[b]);
454 349321760 : if (bb_loop_header_p (header))
455 : {
456 22212157 : class loop *loop;
457 :
458 : /* The current active loop tree has valid loop-fathers for
459 : header blocks. */
460 22212157 : if (!from_scratch
461 16589310 : && header->loop_father->header == header)
462 : {
463 16536534 : 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 16536534 : flow_loop_tree_node_remove (loop);
468 : }
469 : else
470 : {
471 : /* Otherwise allocate a new loop structure for the loop. */
472 5675623 : loop = alloc_loop ();
473 : /* ??? We could re-use unused loop slots here. */
474 5675623 : loop->num = loops->larray->length ();
475 5675623 : vec_safe_push (loops->larray, loop);
476 5675623 : loop->header = header;
477 :
478 5675623 : if (!from_scratch
479 5675623 : && 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 22212157 : loop->latch = NULL;
486 22212157 : larray.safe_push (loop);
487 : }
488 :
489 : /* Make blocks part of the loop root node at start. */
490 349321760 : header->loop_father = loops->tree_root;
491 : }
492 :
493 22063385 : free (rc_order);
494 :
495 : /* Now iterate over the loops found, insert them into the loop tree
496 : and assign basic-block ownership. */
497 44275542 : for (i = 0; i < larray.length (); ++i)
498 : {
499 22212157 : class loop *loop = larray[i];
500 22212157 : basic_block header = loop->header;
501 22212157 : edge_iterator ei;
502 22212157 : edge e;
503 :
504 22212157 : flow_loop_tree_node_add (header->loop_father, loop);
505 22212157 : 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 67017102 : FOR_EACH_EDGE (e, ei, header->preds)
510 : {
511 45034736 : basic_block latch = e->src;
512 :
513 45034736 : if (flow_bb_inside_loop_p (loop, latch))
514 : {
515 22441948 : if (loop->latch != NULL)
516 : {
517 : /* More than one latch edge. */
518 229791 : loop->latch = NULL;
519 229791 : break;
520 : }
521 22212157 : loop->latch = latch;
522 : }
523 : }
524 : }
525 :
526 22063385 : return loops;
527 22063385 : }
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 7581 : for (int i = 0; i < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; ++i)
551 7024 : 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 20890 : find_subloop_latch_edge_by_profile (vec<edge> latches)
599 : {
600 20890 : unsigned i;
601 20890 : edge e, me = NULL;
602 20890 : profile_count mcount = profile_count::zero (), tcount = profile_count::zero ();
603 :
604 73437 : FOR_EACH_VEC_ELT (latches, i, e)
605 : {
606 52547 : if (e->count ()> mcount)
607 : {
608 9455 : me = e;
609 9455 : mcount = e->count();
610 : }
611 52547 : tcount += e->count();
612 : }
613 :
614 20890 : if (!tcount.initialized_p () || !(tcount.ipa () > HEAVY_EDGE_MIN_SAMPLES)
615 20910 : || (tcount - mcount) * HEAVY_EDGE_RATIO > tcount)
616 20876 : 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 20199 : find_subloop_latch_edge_by_ivs (class loop *loop ATTRIBUTE_UNUSED, vec<edge> latches)
639 : {
640 20199 : edge e, latch = latches[0];
641 20199 : unsigned i;
642 20199 : gphi *phi;
643 20199 : gphi_iterator psi;
644 20199 : tree lop;
645 20199 : basic_block bb;
646 :
647 : /* Find the candidate for the latch edge. */
648 51158 : for (i = 1; latches.iterate (i, &e); i++)
649 30959 : if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src))
650 5754 : latch = e;
651 :
652 : /* Verify that it dominates all the latch edges. */
653 52173 : FOR_EACH_VEC_ELT (latches, i, e)
654 43758 : 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 20636 : for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
660 : {
661 17246 : phi = psi.phi ();
662 17246 : lop = PHI_ARG_DEF_FROM_EDGE (phi, latch);
663 :
664 : /* Ignore the values that are not changed inside the subloop. */
665 20845 : if (TREE_CODE (lop) != SSA_NAME
666 17246 : || SSA_NAME_DEF_STMT (lop) == phi)
667 3599 : continue;
668 13647 : bb = gimple_bb (SSA_NAME_DEF_STMT (lop));
669 13647 : if (!bb || !flow_bb_inside_loop_p (loop, bb))
670 16 : continue;
671 :
672 36862 : FOR_EACH_VEC_ELT (latches, i, e)
673 24641 : if (e != latch
674 24641 : && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop)
675 : return NULL;
676 : }
677 :
678 3390 : 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 26585 : find_subloop_latch_edge (class loop *loop)
691 : {
692 26585 : vec<edge> latches = get_loop_latch_edges (loop);
693 26585 : edge latch = NULL;
694 :
695 26585 : if (latches.length () > 1)
696 : {
697 20890 : latch = find_subloop_latch_edge_by_profile (latches);
698 :
699 20890 : 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 20890 : && current_ir_type () == IR_GIMPLE)
704 20199 : latch = find_subloop_latch_edge_by_ivs (loop, latches);
705 : }
706 :
707 26585 : latches.release ();
708 26585 : 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 74193 : mfb_redirect_edges_in_set (edge e, void *data)
716 : {
717 74193 : hash_set<edge> *set = (hash_set<edge> *)data;
718 74193 : return set->contains (e);
719 : }
720 :
721 : /* Creates a subloop of LOOP with latch edge LATCH. */
722 :
723 : static void
724 3404 : form_subloop (class loop *loop, edge latch)
725 : {
726 3404 : edge_iterator ei;
727 3404 : edge e, new_entry;
728 3404 : class loop *new_loop;
729 :
730 3404 : hash_set<edge> *reis_set = new hash_set<edge>;
731 14020 : FOR_EACH_EDGE (e, ei, loop->header->preds)
732 : {
733 10616 : if (e != latch)
734 7212 : reis_set->add (e);
735 : }
736 3404 : new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set, reis_set);
737 3404 : delete reis_set;
738 :
739 3404 : 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 3404 : new_loop = alloc_loop ();
744 3404 : new_loop->header = new_entry->dest;
745 3404 : new_loop->latch = latch->src;
746 3404 : add_loop (new_loop, loop);
747 3404 : }
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 23181 : merge_latch_edges (class loop *loop)
754 : {
755 23181 : vec<edge> latches = get_loop_latch_edges (loop);
756 23181 : edge latch, e;
757 23181 : unsigned i;
758 :
759 23181 : gcc_assert (latches.length () > 0);
760 :
761 23181 : if (latches.length () == 1)
762 5695 : loop->latch = latches[0]->src;
763 : else
764 : {
765 17486 : if (dump_file)
766 8 : fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num);
767 :
768 17486 : hash_set<edge> *reis_set = new hash_set<edge>;
769 80323 : FOR_EACH_VEC_ELT (latches, i, e)
770 45351 : reis_set->add (e);
771 17486 : latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set, reis_set);
772 17486 : delete reis_set;
773 :
774 17486 : loop->header = latch->dest;
775 17486 : loop->latch = latch->src;
776 : }
777 :
778 23181 : latches.release ();
779 23181 : }
780 :
781 : /* LOOP may have several latch edges. Transform it into (possibly several)
782 : loops with single latch edge. */
783 :
784 : static void
785 23181 : disambiguate_multiple_latches (class loop *loop)
786 : {
787 23181 : 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 23181 : 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 23181 : e = find_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), loop->header);
809 23181 : if (e)
810 944 : split_edge (e);
811 :
812 29989 : while (1)
813 : {
814 26585 : e = find_subloop_latch_edge (loop);
815 26585 : if (!e)
816 : break;
817 :
818 3404 : form_subloop (loop, e);
819 : }
820 :
821 23181 : merge_latch_edges (loop);
822 23181 : }
823 :
824 : /* Split loops with multiple latch edges. */
825 :
826 : void
827 29146095 : disambiguate_loops_with_multiple_latches (void)
828 : {
829 105241699 : for (auto loop : loops_list (cfun, 0))
830 : {
831 17803414 : if (!loop->latch)
832 23181 : disambiguate_multiple_latches (loop);
833 29146095 : }
834 29146095 : }
835 :
836 : /* Return nonzero if basic block BB belongs to LOOP. */
837 : bool
838 3306634537 : flow_bb_inside_loop_p (const class loop *loop, const_basic_block bb)
839 : {
840 3306634537 : class loop *source_loop;
841 :
842 3306634537 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
843 3306621571 : || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
844 : return 0;
845 :
846 3288020722 : source_loop = bb->loop_father;
847 3288020722 : 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 1249324903 : glb_enum_p (const_basic_block bb, const void *glb_loop)
853 : {
854 1249324903 : const class loop *const loop = (const class loop *) glb_loop;
855 1249324903 : return (bb != loop->header
856 1249324903 : && 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 222217724 : get_loop_body_with_size (const class loop *loop, basic_block *body,
868 : unsigned max_size)
869 : {
870 222217724 : return dfs_enumerate_from (loop->header, 1, glb_enum_p,
871 222217724 : 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 22524888 : get_loop_body (const class loop *loop)
880 : {
881 22524888 : basic_block *body, bb;
882 22524888 : unsigned tv = 0;
883 :
884 22524888 : gcc_assert (loop->num_nodes);
885 :
886 22524888 : body = XNEWVEC (basic_block, loop->num_nodes);
887 :
888 22524888 : 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 7046 : gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks_for_fn (cfun));
893 7046 : body[tv++] = loop->header;
894 7046 : body[tv++] = EXIT_BLOCK_PTR_FOR_FN (cfun);
895 30349 : FOR_EACH_BB_FN (bb, cfun)
896 23303 : body[tv++] = bb;
897 : }
898 : else
899 22517842 : tv = get_loop_body_with_size (loop, body, loop->num_nodes);
900 :
901 22524888 : gcc_assert (tv == loop->num_nodes);
902 22524888 : 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 5807921 : fill_sons_in_loop (const class loop *loop, basic_block bb,
910 : basic_block *tovisit, int *tv)
911 : {
912 9607206 : basic_block son, postpone = NULL;
913 :
914 9607206 : tovisit[(*tv)++] = bb;
915 9607206 : for (son = first_dom_son (CDI_DOMINATORS, bb);
916 19473921 : son;
917 9866715 : son = next_dom_son (CDI_DOMINATORS, son))
918 : {
919 9866715 : if (!flow_bb_inside_loop_p (loop, son))
920 2263690 : continue;
921 :
922 7603025 : if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
923 : {
924 3799285 : postpone = son;
925 3799285 : continue;
926 : }
927 3803740 : fill_sons_in_loop (loop, son, tovisit, tv);
928 : }
929 :
930 9607206 : if (postpone)
931 : fill_sons_in_loop (loop, postpone, tovisit, tv);
932 5807921 : }
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 2004181 : get_loop_body_in_dom_order (const class loop *loop)
940 : {
941 2004181 : basic_block *tovisit;
942 2004181 : int tv;
943 :
944 2004181 : gcc_assert (loop->num_nodes);
945 :
946 2004181 : tovisit = XNEWVEC (basic_block, loop->num_nodes);
947 :
948 2004181 : gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
949 :
950 2004181 : tv = 0;
951 2004181 : fill_sons_in_loop (loop, loop->header, tovisit, &tv);
952 :
953 2004181 : gcc_assert (tv == (int) loop->num_nodes);
954 :
955 2004181 : 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 149968 : get_loop_body_in_custom_order (const class loop *loop, void *data,
975 : int (*bb_comparator) (const void *, const void *, void *))
976 : {
977 149968 : basic_block *bbs = get_loop_body (loop);
978 :
979 149968 : gcc_sort_r (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator, data);
980 :
981 149968 : return bbs;
982 : }
983 :
984 : /* Get body of a LOOP in breadth first sort order. */
985 :
986 : basic_block *
987 407917 : get_loop_body_in_bfs_order (const class loop *loop)
988 : {
989 407917 : basic_block *blocks;
990 407917 : basic_block bb;
991 407917 : unsigned int i = 1;
992 407917 : unsigned int vc = 0;
993 :
994 407917 : gcc_assert (loop->num_nodes);
995 407917 : gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
996 :
997 407917 : blocks = XNEWVEC (basic_block, loop->num_nodes);
998 407917 : auto_bitmap visited;
999 407917 : blocks[0] = loop->header;
1000 407917 : bitmap_set_bit (visited, loop->header->index);
1001 2152827 : while (i < loop->num_nodes)
1002 : {
1003 1336993 : edge e;
1004 1336993 : edge_iterator ei;
1005 1336993 : gcc_assert (i > vc);
1006 1336993 : bb = blocks[vc++];
1007 :
1008 3667347 : FOR_EACH_EDGE (e, ei, bb->succs)
1009 : {
1010 2330354 : if (flow_bb_inside_loop_p (loop, e->dest))
1011 : {
1012 : /* This bb is now visited. */
1013 1599579 : if (bitmap_set_bit (visited, e->dest->index))
1014 1388489 : blocks[i++] = e->dest;
1015 : }
1016 : }
1017 : }
1018 :
1019 407917 : return blocks;
1020 407917 : }
1021 :
1022 : /* Hash function for struct loop_exit. */
1023 :
1024 : hashval_t
1025 258712610 : loop_exit_hasher::hash (loop_exit *exit)
1026 : {
1027 258712610 : return htab_hash_pointer (exit->e);
1028 : }
1029 :
1030 : /* Equality function for struct loop_exit. Compares with edge. */
1031 :
1032 : bool
1033 306720783 : loop_exit_hasher::equal (loop_exit *exit, edge e)
1034 : {
1035 306720783 : return exit->e == e;
1036 : }
1037 :
1038 : /* Frees the list of loop exit descriptions EX. */
1039 :
1040 : void
1041 19579747 : loop_exit_hasher::remove (loop_exit *exit)
1042 : {
1043 19579747 : loop_exit *next;
1044 40640683 : for (; exit; exit = next)
1045 : {
1046 21060936 : next = exit->next_e;
1047 :
1048 21060936 : exit->next->prev = exit->prev;
1049 21060936 : exit->prev->next = exit->next;
1050 :
1051 21060936 : ggc_free (exit);
1052 : }
1053 19579747 : }
1054 :
1055 : /* Returns the list of records for E as an exit of a loop. */
1056 :
1057 : static struct loop_exit *
1058 41704972 : get_exit_descriptions (edge e)
1059 : {
1060 41704972 : 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 567629124 : rescan_loop_exit (edge e, bool new_edge, bool removed)
1071 : {
1072 567629124 : struct loop_exit *exits = NULL, *exit;
1073 567629124 : class loop *aloop, *cloop;
1074 :
1075 567629124 : if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1076 : return;
1077 :
1078 260040047 : if (!removed
1079 243982463 : && e->src->loop_father != NULL
1080 243982463 : && e->dest->loop_father != NULL
1081 501968800 : && !flow_bb_inside_loop_p (e->src->loop_father, e->dest))
1082 : {
1083 38175064 : cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
1084 38175064 : for (aloop = e->src->loop_father;
1085 59236000 : aloop != cloop;
1086 21060936 : aloop = loop_outer (aloop))
1087 : {
1088 21060936 : exit = ggc_alloc<loop_exit> ();
1089 21060936 : exit->e = e;
1090 :
1091 21060936 : exit->next = aloop->exits->next;
1092 21060936 : exit->prev = aloop->exits;
1093 21060936 : exit->next->prev = exit;
1094 21060936 : exit->prev->next = exit;
1095 :
1096 21060936 : exit->next_e = exits;
1097 21060936 : exits = exit;
1098 : }
1099 : }
1100 :
1101 260040047 : if (!exits && new_edge)
1102 : return;
1103 :
1104 39329936 : loop_exit **slot
1105 59080125 : = current_loops->exits->find_slot_with_hash (e, htab_hash_pointer (e),
1106 : exits ? INSERT : NO_INSERT);
1107 39329936 : if (!slot)
1108 : return;
1109 :
1110 20924343 : if (exits)
1111 : {
1112 19579747 : if (*slot)
1113 411688 : loop_exit_hasher::remove (*slot);
1114 19579747 : *slot = exits;
1115 : }
1116 : else
1117 1344596 : 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 17797089 : record_loop_exits (void)
1125 : {
1126 17797089 : basic_block bb;
1127 17797089 : edge_iterator ei;
1128 17797089 : edge e;
1129 :
1130 17797089 : if (!current_loops)
1131 0 : return;
1132 :
1133 17797089 : if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1134 : return;
1135 17797089 : loops_state_set (LOOPS_HAVE_RECORDED_EXITS);
1136 :
1137 17797089 : gcc_assert (current_loops->exits == NULL);
1138 17797089 : current_loops->exits
1139 35594178 : = hash_table<loop_exit_hasher>::create_ggc (2 * number_of_loops (cfun));
1140 :
1141 177894960 : FOR_EACH_BB_FN (bb, cfun)
1142 : {
1143 384342374 : FOR_EACH_EDGE (e, ei, bb->succs)
1144 : {
1145 224244503 : 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 17797089 : release_recorded_exits (function *fn)
1184 : {
1185 17797089 : gcc_assert (loops_state_satisfies_p (fn, LOOPS_HAVE_RECORDED_EXITS));
1186 17797089 : loops_for_fn (fn)->exits->empty ();
1187 17797089 : loops_for_fn (fn)->exits = NULL;
1188 17797089 : loops_state_clear (fn, LOOPS_HAVE_RECORDED_EXITS);
1189 17797089 : }
1190 :
1191 : /* Returns the list of the exit edges of a LOOP. */
1192 :
1193 : auto_vec<edge>
1194 37024296 : get_loop_exit_edges (const class loop *loop, basic_block *body)
1195 : {
1196 37024296 : auto_vec<edge> edges;
1197 37024296 : edge e;
1198 37024296 : unsigned i;
1199 37024296 : edge_iterator ei;
1200 37024296 : struct loop_exit *exit;
1201 :
1202 37024296 : 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 37024296 : if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1207 : {
1208 113708988 : for (exit = loop->exits->next; exit->e; exit = exit->next)
1209 77365493 : edges.safe_push (exit->e);
1210 : }
1211 : else
1212 : {
1213 680801 : bool body_from_caller = true;
1214 680801 : if (!body)
1215 : {
1216 669762 : body = get_loop_body (loop);
1217 669762 : body_from_caller = false;
1218 : }
1219 4880841 : for (i = 0; i < loop->num_nodes; i++)
1220 10952755 : FOR_EACH_EDGE (e, ei, body[i]->succs)
1221 : {
1222 6752715 : if (!flow_bb_inside_loop_p (loop, e->dest))
1223 1639699 : edges.safe_push (e);
1224 : }
1225 680801 : if (!body_from_caller)
1226 669762 : free (body);
1227 : }
1228 :
1229 37024296 : return edges;
1230 : }
1231 :
1232 : /* Counts the number of conditional branches inside LOOP. */
1233 :
1234 : unsigned
1235 135 : num_loop_branches (const class loop *loop)
1236 : {
1237 135 : unsigned i, n;
1238 135 : basic_block * body;
1239 :
1240 135 : gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1241 :
1242 135 : body = get_loop_body (loop);
1243 135 : n = 0;
1244 644 : for (i = 0; i < loop->num_nodes; i++)
1245 579 : if (EDGE_COUNT (body[i]->succs) >= 2)
1246 205 : n++;
1247 135 : free (body);
1248 :
1249 135 : return n;
1250 : }
1251 :
1252 : /* Adds basic block BB to LOOP. */
1253 : void
1254 46200321 : add_bb_to_loop (basic_block bb, class loop *loop)
1255 : {
1256 46200321 : unsigned i;
1257 46200321 : loop_p ploop;
1258 46200321 : edge_iterator ei;
1259 46200321 : edge e;
1260 :
1261 46200321 : gcc_assert (bb->loop_father == NULL);
1262 46200321 : bb->loop_father = loop;
1263 46200321 : loop->num_nodes++;
1264 66594583 : FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
1265 20394262 : ploop->num_nodes++;
1266 :
1267 96783854 : FOR_EACH_EDGE (e, ei, bb->succs)
1268 : {
1269 50583533 : rescan_loop_exit (e, true, false);
1270 : }
1271 77294880 : FOR_EACH_EDGE (e, ei, bb->preds)
1272 : {
1273 31094559 : rescan_loop_exit (e, true, false);
1274 : }
1275 46200321 : }
1276 :
1277 : /* Remove basic block BB from loops. */
1278 : void
1279 58494835 : remove_bb_from_loops (basic_block bb)
1280 : {
1281 58494835 : unsigned i;
1282 58494835 : class loop *loop = bb->loop_father;
1283 58494835 : loop_p ploop;
1284 58494835 : edge_iterator ei;
1285 58494835 : edge e;
1286 :
1287 58494835 : gcc_assert (loop != NULL);
1288 58494835 : loop->num_nodes--;
1289 80315221 : FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
1290 21820386 : ploop->num_nodes--;
1291 58494835 : bb->loop_father = NULL;
1292 :
1293 88584201 : FOR_EACH_EDGE (e, ei, bb->succs)
1294 : {
1295 30089366 : rescan_loop_exit (e, false, true);
1296 : }
1297 80051991 : FOR_EACH_EDGE (e, ei, bb->preds)
1298 : {
1299 21557156 : rescan_loop_exit (e, false, true);
1300 : }
1301 58494835 : }
1302 :
1303 : /* Finds nearest common ancestor in loop tree for given loops. */
1304 : class loop *
1305 209358100 : find_common_loop (class loop *loop_s, class loop *loop_d)
1306 : {
1307 209358100 : unsigned sdepth, ddepth;
1308 :
1309 209358100 : if (!loop_s) return loop_d;
1310 209357557 : if (!loop_d) return loop_s;
1311 :
1312 209357557 : sdepth = loop_depth (loop_s);
1313 209357557 : ddepth = loop_depth (loop_d);
1314 :
1315 83993738 : if (sdepth < ddepth)
1316 6304805 : loop_d = (*loop_d->superloops)[sdepth];
1317 203052752 : else if (sdepth > ddepth)
1318 102475136 : loop_s = (*loop_s->superloops)[ddepth];
1319 :
1320 210304162 : while (loop_s != loop_d)
1321 : {
1322 946605 : loop_s = loop_outer (loop_s);
1323 946605 : 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 155425 : delete_loop (class loop *loop)
1332 : {
1333 : /* Remove the loop from structure. */
1334 155425 : flow_loop_tree_node_remove (loop);
1335 :
1336 : /* Remove loop from loops array. */
1337 155425 : (*current_loops->larray)[loop->num] = NULL;
1338 :
1339 : /* Free loop data. */
1340 155425 : flow_loop_free (loop);
1341 155425 : }
1342 :
1343 : /* Cancels the LOOP; it must be innermost one. */
1344 :
1345 : static void
1346 11863 : cancel_loop (class loop *loop)
1347 : {
1348 11863 : basic_block *bbs;
1349 11863 : unsigned i;
1350 11863 : class loop *outer = loop_outer (loop);
1351 :
1352 11863 : gcc_assert (!loop->inner);
1353 :
1354 : /* Move blocks up one level (they should be removed as soon as possible). */
1355 11863 : bbs = get_loop_body (loop);
1356 48960 : for (i = 0; i < loop->num_nodes; i++)
1357 25234 : bbs[i]->loop_father = outer;
1358 :
1359 11863 : free (bbs);
1360 11863 : delete_loop (loop);
1361 11863 : }
1362 :
1363 : /* Cancels LOOP and all its subloops. */
1364 : void
1365 11863 : cancel_loop_tree (class loop *loop)
1366 : {
1367 12350 : while (loop->inner)
1368 487 : cancel_loop_tree (loop->inner);
1369 11863 : cancel_loop (loop);
1370 11863 : }
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 381817169 : verify_loop_structure (void)
1391 : {
1392 381817169 : unsigned *sizes, i, j;
1393 381817169 : basic_block bb, *bbs;
1394 381817169 : int err = 0;
1395 381817169 : edge e;
1396 381817169 : unsigned num = number_of_loops (cfun);
1397 381817169 : struct loop_exit *exit, *mexit;
1398 381817169 : bool dom_available = dom_info_available_p (CDI_DOMINATORS);
1399 :
1400 381817169 : 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 381817169 : if (!dom_available)
1408 103164649 : calculate_dominance_info (CDI_DOMINATORS);
1409 : else
1410 278652520 : verify_dominators (CDI_DOMINATORS);
1411 :
1412 : /* Check the loop tree root. */
1413 381817169 : if (current_loops->tree_root->header != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1414 381817169 : || current_loops->tree_root->latch != EXIT_BLOCK_PTR_FOR_FN (cfun)
1415 381817169 : || (current_loops->tree_root->num_nodes
1416 381817169 : != (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 3791488048 : FOR_EACH_BB_FN (bb, cfun)
1424 3409670879 : if (bb_loop_header_p (bb))
1425 : {
1426 199038405 : 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 199038405 : 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 3210632474 : 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 381817169 : auto_sbitmap visited (last_basic_block_for_fn (cfun));
1445 381817169 : bitmap_clear (visited);
1446 381817169 : bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
1447 1344489912 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1448 : {
1449 199038405 : unsigned n;
1450 :
1451 199038405 : 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 199038405 : n = get_loop_body_with_size (loop, bbs, n_basic_blocks_for_fn (cfun));
1459 199038405 : 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 1327421473 : for (j = 0; j < n; j++)
1467 : {
1468 1128383068 : bb = bbs[j];
1469 :
1470 1128383068 : 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 1128383068 : if (bitmap_bit_p (visited, bb->index))
1479 262349725 : continue;
1480 866033343 : bitmap_set_bit (visited, bb->index);
1481 :
1482 866033343 : 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 381817169 : }
1490 381817169 : free (bbs);
1491 :
1492 : /* Check headers and latches. */
1493 1344489912 : for (auto loop : loops_list (cfun, 0))
1494 : {
1495 199038405 : i = loop->num;
1496 199038405 : if (loop->header == NULL)
1497 0 : continue;
1498 199038405 : 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 199038405 : if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
1504 199038405 : && 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 199038405 : if (loop->latch)
1510 : {
1511 198127823 : 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 198127823 : 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 199038405 : if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
1523 : {
1524 30625716 : 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 30625716 : 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 30625716 : 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 199038405 : 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 199038405 : if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1546 : {
1547 27297479 : edge_iterator ei;
1548 81892689 : FOR_EACH_EDGE (e, ei, loop->header->preds)
1549 54595210 : if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header)
1550 54595210 : && 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 199038405 : tree ref;
1560 199038405 : if (loop->nb_iterations
1561 199038405 : && (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 381817169 : }
1569 :
1570 : /* Check irreducible loops. */
1571 381817169 : if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1572 : {
1573 34244349 : auto_edge_flag saved_edge_irr (cfun);
1574 34244349 : auto_bb_flag saved_bb_irr (cfun);
1575 : /* Save old info. */
1576 441790584 : FOR_EACH_BB_FN (bb, cfun)
1577 : {
1578 407546235 : edge_iterator ei;
1579 407546235 : if (bb->flags & BB_IRREDUCIBLE_LOOP)
1580 540169 : bb->flags |= saved_bb_irr;
1581 979249496 : FOR_EACH_EDGE (e, ei, bb->succs)
1582 571703261 : if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1583 778845 : e->flags |= saved_edge_irr;
1584 : }
1585 :
1586 : /* Recount it. */
1587 34244349 : mark_irreducible_loops ();
1588 :
1589 : /* Compare. */
1590 441790584 : FOR_EACH_BB_FN (bb, cfun)
1591 : {
1592 407546235 : edge_iterator ei;
1593 :
1594 407546235 : if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1595 407546235 : && !(bb->flags & saved_bb_irr))
1596 : {
1597 0 : error ("basic block %d should be marked irreducible", bb->index);
1598 0 : err = 1;
1599 : }
1600 407546235 : else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1601 407546235 : && (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 407546235 : bb->flags &= ~saved_bb_irr;
1607 979249496 : FOR_EACH_EDGE (e, ei, bb->succs)
1608 : {
1609 571703261 : if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1610 571703261 : && !(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 571703261 : else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1617 571703261 : && (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 571703261 : e->flags &= ~saved_edge_irr;
1624 : }
1625 : }
1626 34244349 : }
1627 :
1628 : /* Check the recorded loop exits. */
1629 1344489912 : for (auto loop : loops_list (cfun, 0))
1630 : {
1631 199038405 : 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 199038405 : for (mexit = loop->exits, exit = mexit->next, i = 0;
1642 243843276 : exit->e && exit != mexit;
1643 44804871 : exit = exit->next)
1644 : {
1645 44804871 : if (i++ & 1)
1646 13448573 : mexit = mexit->next;
1647 : }
1648 :
1649 199038405 : if (exit != loop->exits)
1650 : {
1651 0 : error ("corrupted exits list of loop %d", loop->num);
1652 0 : err = 1;
1653 : }
1654 : }
1655 :
1656 199038405 : if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1657 : {
1658 174713469 : 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 381817169 : }
1666 :
1667 381817169 : if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1668 : {
1669 26069289 : unsigned n_exits = 0, eloops;
1670 :
1671 26069289 : sizes = XCNEWVEC (unsigned, num);
1672 26069289 : memset (sizes, 0, sizeof (unsigned) * num);
1673 370720580 : FOR_EACH_BB_FN (bb, cfun)
1674 : {
1675 344651291 : edge_iterator ei;
1676 344651291 : if (bb->loop_father == current_loops->tree_root)
1677 229997659 : continue;
1678 293310902 : FOR_EACH_EDGE (e, ei, bb->succs)
1679 : {
1680 178657270 : if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
1681 136952298 : continue;
1682 :
1683 41704972 : n_exits++;
1684 41704972 : exit = get_exit_descriptions (e);
1685 41704972 : 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 41704972 : eloops = 0;
1692 86509843 : for (; exit; exit = exit->next_e)
1693 44804871 : eloops++;
1694 :
1695 41704972 : for (class loop *loop = bb->loop_father;
1696 86509843 : 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 86509843 : && loop != loop_outer (e->dest->loop_father);
1702 44804871 : loop = loop_outer (loop))
1703 : {
1704 44804871 : eloops--;
1705 44804871 : sizes[loop->num]++;
1706 : }
1707 :
1708 41704972 : 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 26069289 : if (n_exits != current_loops->exits->elements ())
1718 : {
1719 0 : error ("too many loop exits recorded");
1720 0 : err = 1;
1721 : }
1722 :
1723 102532803 : for (auto loop : loops_list (cfun, 0))
1724 : {
1725 24324936 : eloops = 0;
1726 69129807 : for (exit = loop->exits->next; exit->e; exit = exit->next)
1727 44804871 : eloops++;
1728 24324936 : 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 26069289 : }
1735 :
1736 26069289 : free (sizes);
1737 : }
1738 :
1739 381817169 : gcc_assert (!err);
1740 :
1741 381817169 : if (!dom_available)
1742 103164649 : free_dominance_info (CDI_DOMINATORS);
1743 381817169 : }
1744 :
1745 : #if __GNUC__ >= 10
1746 : # pragma GCC diagnostic pop
1747 : #endif
1748 :
1749 : /* Returns latch edge of LOOP. */
1750 : edge
1751 12974177 : loop_latch_edge (const class loop *loop)
1752 : {
1753 12974177 : return find_edge (loop->latch, loop->header);
1754 : }
1755 :
1756 : /* Returns preheader edge of LOOP. */
1757 : edge
1758 435027456 : loop_preheader_edge (const class loop *loop)
1759 : {
1760 435027456 : edge e;
1761 435027456 : edge_iterator ei;
1762 :
1763 435027456 : gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
1764 : && ! loops_state_satisfies_p (LOOPS_MAY_HAVE_MULTIPLE_LATCHES));
1765 :
1766 666433418 : FOR_EACH_EDGE (e, ei, loop->header->preds)
1767 665572539 : if (e->src != loop->latch)
1768 : break;
1769 :
1770 435027456 : if (! e)
1771 : {
1772 860879 : gcc_assert (! loop_outer (loop));
1773 860879 : 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 37028440 : loop_exit_edge_p (const class loop *loop, const_edge e)
1783 : {
1784 37028440 : return (flow_bb_inside_loop_p (loop, e->src)
1785 37028440 : && !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 35853497 : single_exit (const class loop *loop)
1794 : {
1795 35853497 : struct loop_exit *exit = loop->exits->next;
1796 :
1797 35853497 : if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1798 : return NULL;
1799 :
1800 35819234 : if (exit->e && exit->next == loop->exits)
1801 : return exit->e;
1802 : else
1803 10735686 : 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 1750243 : loop_exits_from_bb_p (class loop *loop, basic_block bb)
1827 : {
1828 1750243 : edge e;
1829 1750243 : edge_iterator ei;
1830 :
1831 3836885 : FOR_EACH_EDGE (e, ei, bb->succs)
1832 3107746 : 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 583178 : get_loop_location (class loop *loop)
1842 : {
1843 583178 : rtx_insn *insn = NULL;
1844 583178 : class niter_desc *desc = NULL;
1845 583178 : 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 583178 : desc = get_simple_loop_desc (loop);
1854 583178 : if (desc->in_edge)
1855 : {
1856 580519 : FOR_BB_INSNS_REVERSE (desc->in_edge->src, insn)
1857 : {
1858 575603 : if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1859 400812 : 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 182366 : if ((exit = single_exit (loop)))
1865 : {
1866 209045 : FOR_BB_INSNS_REVERSE (exit->src, insn)
1867 : {
1868 200161 : if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1869 101674 : return insn;
1870 : }
1871 : }
1872 : /* Next check the latch, to see if it is non-empty. */
1873 189299 : FOR_BB_INSNS_REVERSE (loop->latch, insn)
1874 : {
1875 131570 : if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1876 22963 : 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 279393 : FOR_BB_INSNS (loop->header, insn)
1881 : {
1882 268184 : if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1883 46520 : return insn;
1884 : }
1885 : /* If all else fails, simply return the current function location. */
1886 11209 : 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 17600473 : record_niter_bound (class loop *loop, const widest_int &i_bound,
1896 : bool realistic, bool upper)
1897 : {
1898 17600473 : if (wi::min_precision (i_bound, SIGNED) > bound_wide_int ().get_precision ())
1899 0 : return;
1900 :
1901 17600473 : 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 17600473 : if (upper
1906 17600473 : && (!loop->any_upper_bound
1907 16124037 : || wi::ltu_p (bound, loop->nb_iterations_upper_bound)))
1908 : {
1909 866779 : loop->any_upper_bound = true;
1910 866779 : loop->nb_iterations_upper_bound = bound;
1911 866779 : if (!loop->any_likely_upper_bound)
1912 : {
1913 511618 : loop->any_likely_upper_bound = true;
1914 511618 : loop->nb_iterations_likely_upper_bound = bound;
1915 : }
1916 : }
1917 17600473 : if (realistic
1918 17600473 : && (!loop->any_estimate
1919 2867145 : || wi::ltu_p (bound, loop->nb_iterations_estimate)))
1920 : {
1921 246506 : loop->any_estimate = true;
1922 246506 : loop->nb_iterations_estimate = bound;
1923 : }
1924 17600473 : if (!realistic
1925 17600473 : && (!loop->any_likely_upper_bound
1926 14491753 : || wi::ltu_p (bound, loop->nb_iterations_likely_upper_bound)))
1927 : {
1928 221806 : loop->any_likely_upper_bound = true;
1929 221806 : 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 17600473 : if (loop->any_upper_bound
1935 17595612 : && loop->any_estimate
1936 26834686 : && wi::ltu_p (loop->nb_iterations_upper_bound,
1937 9234213 : loop->nb_iterations_estimate))
1938 6206 : loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
1939 17600473 : if (loop->any_upper_bound
1940 17595612 : && loop->any_likely_upper_bound
1941 35196085 : && wi::ltu_p (loop->nb_iterations_upper_bound,
1942 17595612 : loop->nb_iterations_likely_upper_bound))
1943 38585 : 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 308744 : max_stmt_executions_int (class loop *loop)
1972 : {
1973 308744 : HOST_WIDE_INT nit = get_max_loop_iterations_int (loop);
1974 308744 : HOST_WIDE_INT snit;
1975 :
1976 308744 : if (nit == -1)
1977 : return -1;
1978 :
1979 282493 : snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
1980 :
1981 : /* If the computation overflows, return -1. */
1982 282493 : 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 5029584 : likely_max_stmt_executions_int (class loop *loop)
1991 : {
1992 5029584 : HOST_WIDE_INT nit = get_likely_max_loop_iterations_int (loop);
1993 5029584 : HOST_WIDE_INT snit;
1994 :
1995 5029584 : if (nit == -1)
1996 : return -1;
1997 :
1998 4270401 : snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
1999 :
2000 : /* If the computation overflows, return -1. */
2001 4270401 : 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 9370320 : 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 9370320 : if (!loop->any_estimate)
2014 : {
2015 5386100 : sreal snit;
2016 5386100 : bool reliable;
2017 5386100 : if (expected_loop_iterations_by_profile (loop, &snit, &reliable)
2018 5386100 : && reliable)
2019 : {
2020 3 : *nit = snit.to_nearest_int ();
2021 3 : return true;
2022 : }
2023 : return false;
2024 : }
2025 :
2026 3984220 : *nit = widest_int::from (loop->nb_iterations_estimate, SIGNED);
2027 3984220 : 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 22288918 : get_max_loop_iterations (const class loop *loop, widest_int *nit)
2036 : {
2037 22288918 : if (!loop->any_upper_bound)
2038 : return false;
2039 :
2040 19864879 : *nit = widest_int::from (loop->nb_iterations_upper_bound, SIGNED);
2041 19864879 : 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 1774401 : get_max_loop_iterations_int (const class loop *loop)
2050 : {
2051 1774401 : widest_int nit;
2052 1774401 : HOST_WIDE_INT hwi_nit;
2053 :
2054 1774401 : if (!get_max_loop_iterations (loop, &nit))
2055 : return -1;
2056 :
2057 1388406 : if (!wi::fits_shwi_p (nit))
2058 : return -1;
2059 1327028 : hwi_nit = nit.to_shwi ();
2060 :
2061 1327028 : return hwi_nit < 0 ? -1 : hwi_nit;
2062 1774401 : }
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 5478616 : get_likely_max_loop_iterations (class loop *loop, widest_int *nit)
2070 : {
2071 5478616 : if (!loop->any_likely_upper_bound)
2072 : return false;
2073 :
2074 4870690 : *nit = widest_int::from (loop->nb_iterations_likely_upper_bound, SIGNED);
2075 4870690 : 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 5092745 : get_likely_max_loop_iterations_int (class loop *loop)
2084 : {
2085 5092745 : widest_int nit;
2086 5092745 : HOST_WIDE_INT hwi_nit;
2087 :
2088 5092745 : if (!get_likely_max_loop_iterations (loop, &nit))
2089 : return -1;
2090 :
2091 4618621 : if (!wi::fits_shwi_p (nit))
2092 : return -1;
2093 4333013 : hwi_nit = nit.to_shwi ();
2094 :
2095 4333013 : return hwi_nit < 0 ? -1 : hwi_nit;
2096 5092745 : }
2097 :
2098 : /* Returns the loop depth of the loop BB belongs to. */
2099 :
2100 : int
2101 56759918 : bb_loop_depth (const_basic_block bb)
2102 : {
2103 69334209 : 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 270475 : mark_loop_for_removal (loop_p loop)
2110 : {
2111 270475 : if (loop->header == NULL)
2112 : return;
2113 270475 : loop->former_header = loop->header;
2114 270475 : loop->header = NULL;
2115 270475 : loop->latch = NULL;
2116 270475 : 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 1402949264 : loops_list::walk_loop_tree (class loop *root, unsigned flags)
2128 : {
2129 1402949264 : bool only_innermost_p = flags & LI_ONLY_INNERMOST;
2130 1402949264 : bool from_innermost_p = flags & LI_FROM_INNERMOST;
2131 1402949264 : 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 1402949264 : if (!root->inner)
2137 : {
2138 1136264060 : if (flags & LI_INCLUDE_ROOT)
2139 12832 : this->to_visit.quick_push (root->num);
2140 1136264060 : return;
2141 : }
2142 266685204 : else if (preorder_p && flags & LI_INCLUDE_ROOT)
2143 52278 : this->to_visit.quick_push (root->num);
2144 :
2145 : class loop *aloop;
2146 68814233 : for (aloop = root->inner;
2147 335499437 : aloop->inner != NULL;
2148 68814233 : aloop = aloop->inner)
2149 : {
2150 68814233 : if (preorder_p)
2151 50008948 : this->to_visit.quick_push (aloop->num);
2152 68814233 : continue;
2153 : }
2154 :
2155 935226210 : while (1)
2156 : {
2157 935226210 : gcc_assert (aloop != root);
2158 935226210 : if (from_innermost_p || aloop->inner == NULL)
2159 804810135 : this->to_visit.quick_push (aloop->num);
2160 :
2161 935226210 : if (aloop->next)
2162 : {
2163 100883822 : for (aloop = aloop->next;
2164 599726773 : aloop->inner != NULL;
2165 100883822 : aloop = aloop->inner)
2166 : {
2167 100883822 : if (preorder_p)
2168 80407127 : this->to_visit.quick_push (aloop->num);
2169 100883822 : continue;
2170 : }
2171 : }
2172 436383259 : 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 266685204 : if (from_innermost_p && flags & LI_INCLUDE_ROOT)
2181 0 : this->to_visit.quick_push (root->num);
2182 68814233 : }
2183 :
|
