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 5970 : flow_loops_cfg_dump (FILE *file)
44 : {
45 5970 : basic_block bb;
46 :
47 5970 : if (!file)
48 : return;
49 :
50 27315 : FOR_EACH_BB_FN (bb, cfun)
51 : {
52 21345 : edge succ;
53 21345 : edge_iterator ei;
54 :
55 21345 : fprintf (file, ";; %d succs { ", bb->index);
56 49488 : FOR_EACH_EDGE (succ, ei, bb->succs)
57 28143 : fprintf (file, "%d ", succ->dest->index);
58 21345 : fprintf (file, "}\n");
59 : }
60 : }
61 :
62 : /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
63 :
64 : bool
65 771458337 : flow_loop_nested_p (const class loop *outer, const class loop *loop)
66 : {
67 771458337 : unsigned odepth = loop_depth (outer);
68 :
69 771458337 : return (loop_depth (loop) > odepth
70 505109158 : && (*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 22158043 : superloop_at_depth (class loop *loop, unsigned depth)
78 : {
79 22158043 : unsigned ldepth = loop_depth (loop);
80 :
81 22158043 : gcc_assert (depth <= ldepth);
82 :
83 22158043 : if (depth == ldepth)
84 : return loop;
85 :
86 5800984 : return (*loop->superloops)[depth];
87 : }
88 :
89 : /* Returns the list of the latch edges of LOOP. */
90 :
91 : static vec<edge>
92 47420 : get_loop_latch_edges (const class loop *loop)
93 : {
94 47420 : edge_iterator ei;
95 47420 : edge e;
96 47420 : vec<edge> ret = vNULL;
97 :
98 200859 : FOR_EACH_EDGE (e, ei, loop->header->preds)
99 : {
100 153439 : if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header))
101 104341 : ret.safe_push (e);
102 : }
103 :
104 47420 : 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 7593 : flow_loop_dump (const class loop *loop, FILE *file,
112 : void (*loop_dump_aux) (const class loop *, FILE *, int),
113 : int verbose)
114 : {
115 7593 : basic_block *bbs;
116 7593 : unsigned i;
117 7593 : vec<edge> latches;
118 7593 : edge e;
119 :
120 7593 : if (! loop || ! loop->header)
121 0 : return;
122 :
123 7593 : fprintf (file, ";;\n;; Loop %d\n", loop->num);
124 :
125 7593 : fprintf (file, ";; header %d, ", loop->header->index);
126 7593 : if (loop->latch)
127 7589 : 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 15186 : fprintf (file, ";; depth %d, outer %ld",
139 7593 : loop_depth (loop), (long) (loop_outer (loop)
140 1595 : ? loop_outer (loop)->num : -1));
141 7593 : print_loop_info (file, loop, ";; ");
142 :
143 7593 : fprintf (file, "\n;; nodes:");
144 7593 : bbs = get_loop_body (loop);
145 53903 : for (i = 0; i < loop->num_nodes; i++)
146 38717 : fprintf (file, " %d", bbs[i]->index);
147 7593 : free (bbs);
148 7593 : fprintf (file, "\n");
149 :
150 7593 : 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 49719623 : flow_loops_dump (FILE *file, void (*loop_dump_aux) (const class loop *, FILE *, int), int verbose)
159 : {
160 49719623 : if (!current_loops || ! file)
161 : return;
162 :
163 11996 : fprintf (file, ";; %d loops found\n", number_of_loops (cfun));
164 :
165 25520 : for (auto loop : loops_list (cfun, LI_INCLUDE_ROOT))
166 : {
167 7526 : flow_loop_dump (loop, file, loop_dump_aux, verbose);
168 5998 : }
169 :
170 5998 : if (verbose)
171 5970 : flow_loops_cfg_dump (file);
172 : }
173 :
174 : /* Free data allocated for LOOP. */
175 :
176 : void
177 17330980 : flow_loop_free (class loop *loop)
178 : {
179 17330980 : struct loop_exit *exit, *next;
180 :
181 17330980 : 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 17344324 : for (exit = loop->exits->next; exit != loop->exits; exit = next)
188 : {
189 13344 : next = exit->next;
190 13344 : exit->next = exit;
191 13344 : exit->prev = exit;
192 : }
193 :
194 17330980 : ggc_free (loop->exits);
195 17330980 : ggc_free (loop);
196 17330980 : }
197 :
198 : /* Free all the memory allocated for LOOPS. */
199 :
200 : void
201 10865884 : flow_loops_free (struct loops *loops)
202 : {
203 10865884 : if (loops->larray)
204 : {
205 : unsigned i;
206 : loop_p loop;
207 :
208 : /* Free the loop descriptors. */
209 28287738 : FOR_EACH_VEC_SAFE_ELT (loops->larray, i, loop)
210 : {
211 17421854 : if (!loop)
212 508414 : continue;
213 :
214 16913440 : flow_loop_free (loop);
215 : }
216 :
217 21731768 : vec_free (loops->larray);
218 : }
219 10865884 : }
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 22175938 : flow_loop_nodes_find (basic_block header, class loop *loop)
226 : {
227 22175938 : vec<basic_block> stack = vNULL;
228 22175938 : int num_nodes = 1;
229 22175938 : edge latch;
230 22175938 : edge_iterator latch_ei;
231 :
232 22175938 : header->loop_father = loop;
233 :
234 67295911 : FOR_EACH_EDGE (latch, latch_ei, loop->header->preds)
235 : {
236 73611193 : if (latch->src->loop_father == loop
237 45119973 : || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header))
238 28491220 : continue;
239 :
240 16628753 : num_nodes++;
241 16628753 : stack.safe_push (latch->src);
242 16628753 : latch->src->loop_father = loop;
243 :
244 168941686 : while (!stack.is_empty ())
245 : {
246 107192960 : basic_block node;
247 107192960 : edge e;
248 107192960 : edge_iterator ei;
249 :
250 107192960 : node = stack.pop ();
251 :
252 255156555 : FOR_EACH_EDGE (e, ei, node->preds)
253 : {
254 147963595 : basic_block ancestor = e->src;
255 :
256 147963595 : if (ancestor->loop_father != loop)
257 : {
258 90564207 : ancestor->loop_father = loop;
259 90564207 : num_nodes++;
260 90564207 : stack.safe_push (ancestor);
261 : }
262 : }
263 : }
264 : }
265 22175938 : stack.release ();
266 :
267 22175938 : 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 23131721 : establish_preds (class loop *loop, class loop *father)
275 : {
276 23131721 : loop_p ploop;
277 23131721 : unsigned depth = loop_depth (father) + 1;
278 23131721 : unsigned i;
279 :
280 23131721 : loop->superloops = 0;
281 23131721 : vec_alloc (loop->superloops, depth);
282 55571824 : FOR_EACH_VEC_SAFE_ELT (father->superloops, i, ploop)
283 9308382 : loop->superloops->quick_push (ploop);
284 23131721 : loop->superloops->quick_push (father);
285 :
286 23213027 : for (ploop = loop->inner; ploop; ploop = ploop->next)
287 81306 : establish_preds (ploop, loop);
288 23131721 : }
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 23050415 : flow_loop_tree_node_add (class loop *father, class loop *loop,
299 : class loop *after)
300 : {
301 23050415 : if (after)
302 : {
303 4832 : loop->next = after->next;
304 4832 : after->next = loop;
305 : }
306 : else
307 : {
308 23045583 : loop->next = father->inner;
309 23045583 : father->inner = loop;
310 : }
311 :
312 23050415 : establish_preds (loop, father);
313 23050415 : }
314 :
315 : /* Remove LOOP from the loop hierarchy tree. */
316 :
317 : void
318 16988392 : flow_loop_tree_node_remove (class loop *loop)
319 : {
320 16988392 : class loop *prev, *father;
321 :
322 16988392 : father = loop_outer (loop);
323 :
324 : /* Remove loop from the list of sons. */
325 16988392 : if (father->inner == loop)
326 7902803 : father->inner = loop->next;
327 : else
328 : {
329 232850820 : for (prev = father->inner; prev->next != loop; prev = prev->next)
330 223765231 : continue;
331 9085589 : prev->next = loop->next;
332 : }
333 :
334 16988392 : loop->superloops = NULL;
335 16988392 : }
336 :
337 : /* Allocates and returns new loop structure. */
338 :
339 : class loop *
340 17451000 : alloc_loop (void)
341 : {
342 17451000 : class loop *loop = ggc_cleared_alloc<class loop> ();
343 :
344 17451000 : loop->exits = ggc_cleared_alloc<loop_exit> ();
345 17451000 : loop->exits->next = loop->exits->prev = loop->exits;
346 17451000 : loop->can_be_parallel = false;
347 17451000 : loop->constraints = 0;
348 17451000 : loop->nb_iterations_upper_bound = 0;
349 17451000 : loop->nb_iterations_likely_upper_bound = 0;
350 17451000 : loop->nb_iterations_estimate = 0;
351 17451000 : 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 10971437 : init_loops_structure (struct function *fn,
359 : struct loops *loops, unsigned num_loops)
360 : {
361 10971437 : class loop *root;
362 :
363 10971437 : memset (loops, 0, sizeof *loops);
364 10971437 : vec_alloc (loops->larray, num_loops);
365 :
366 : /* Dummy loop containing whole function. */
367 10971437 : root = alloc_loop ();
368 10971437 : root->num_nodes = n_basic_blocks_for_fn (fn);
369 10971437 : root->latch = EXIT_BLOCK_PTR_FOR_FN (fn);
370 10971437 : root->header = ENTRY_BLOCK_PTR_FOR_FN (fn);
371 10971437 : ENTRY_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
372 10971437 : EXIT_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
373 :
374 10971437 : loops->larray->quick_push (root);
375 10971437 : loops->tree_root = root;
376 10971437 : }
377 :
378 : /* Returns whether HEADER is a loop header. */
379 :
380 : bool
381 3901583116 : bb_loop_header_p (basic_block header)
382 : {
383 3901583116 : edge_iterator ei;
384 3901583116 : edge e;
385 :
386 : /* If we have an abnormal predecessor, do not consider the
387 : loop (not worth the problems). */
388 3901583116 : 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 8857058712 : FOR_EACH_EDGE (e, ei, header->preds)
397 : {
398 5398265274 : basic_block latch = e->src;
399 5398265274 : if (latch != ENTRY_BLOCK_PTR_FOR_FN (cfun)
400 5398265274 : && 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 21721194 : flow_loops_find (struct loops *loops)
417 : {
418 21721194 : bool from_scratch = (loops == NULL);
419 21721194 : int *rc_order;
420 21721194 : int b;
421 21721194 : unsigned i;
422 :
423 : /* Ensure that the dominators are computed. */
424 21721194 : calculate_dominance_info (CDI_DOMINATORS);
425 :
426 21721194 : if (!loops)
427 : {
428 10824151 : loops = ggc_cleared_alloc<struct loops> ();
429 10824151 : init_loops_structure (cfun, loops, 1);
430 : }
431 :
432 : /* Ensure that loop exits were released. */
433 21721194 : gcc_assert (loops->exits == NULL);
434 :
435 : /* Taking care of this degenerate case makes the rest of
436 : this code simpler. */
437 21721194 : if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
438 : return loops;
439 :
440 : /* The root loop node contains all basic-blocks. */
441 21485533 : 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 21485533 : rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
446 21485533 : 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 21485533 : auto_vec<loop_p> larray (loops->larray->length ());
451 361826945 : for (b = 0; b < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; b++)
452 : {
453 340341412 : basic_block header = BASIC_BLOCK_FOR_FN (cfun, rc_order[b]);
454 340341412 : if (bb_loop_header_p (header))
455 : {
456 22175938 : class loop *loop;
457 :
458 : /* The current active loop tree has valid loop-fathers for
459 : header blocks. */
460 22175938 : if (!from_scratch
461 16553752 : && header->loop_father->header == header)
462 : {
463 16490830 : 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 16490830 : flow_loop_tree_node_remove (loop);
468 : }
469 : else
470 : {
471 : /* Otherwise allocate a new loop structure for the loop. */
472 5685108 : loop = alloc_loop ();
473 : /* ??? We could re-use unused loop slots here. */
474 5685108 : loop->num = loops->larray->length ();
475 5685108 : vec_safe_push (loops->larray, loop);
476 5685108 : loop->header = header;
477 :
478 5685108 : if (!from_scratch
479 5685108 : && 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 22175938 : loop->latch = NULL;
486 22175938 : larray.safe_push (loop);
487 : }
488 :
489 : /* Make blocks part of the loop root node at start. */
490 340341412 : header->loop_father = loops->tree_root;
491 : }
492 :
493 21485533 : free (rc_order);
494 :
495 : /* Now iterate over the loops found, insert them into the loop tree
496 : and assign basic-block ownership. */
497 43661471 : for (i = 0; i < larray.length (); ++i)
498 : {
499 22175938 : class loop *loop = larray[i];
500 22175938 : basic_block header = loop->header;
501 22175938 : edge_iterator ei;
502 22175938 : edge e;
503 :
504 22175938 : flow_loop_tree_node_add (header->loop_father, loop);
505 22175938 : 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 66906556 : FOR_EACH_EDGE (e, ei, header->preds)
510 : {
511 44958933 : basic_block latch = e->src;
512 :
513 44958933 : if (flow_bb_inside_loop_p (loop, latch))
514 : {
515 22404253 : if (loop->latch != NULL)
516 : {
517 : /* More than one latch edge. */
518 228315 : loop->latch = NULL;
519 228315 : break;
520 : }
521 22175938 : loop->latch = latch;
522 : }
523 : }
524 : }
525 :
526 21485533 : return loops;
527 21485533 : }
528 :
529 : /* qsort helper for sort_sibling_loops. */
530 :
531 : static int *sort_sibling_loops_cmp_rpo;
532 : static int
533 2635 : sort_sibling_loops_cmp (const void *la_, const void *lb_)
534 : {
535 2635 : const class loop *la = *(const class loop * const *)la_;
536 2635 : const class loop *lb = *(const class loop * const *)lb_;
537 2635 : return (sort_sibling_loops_cmp_rpo[la->header->index]
538 2635 : - sort_sibling_loops_cmp_rpo[lb->header->index]);
539 : }
540 :
541 : /* Sort sibling loops in RPO order. */
542 :
543 : void
544 556 : sort_sibling_loops (function *fn)
545 : {
546 : /* Match flow_loops_find in the order we sort sibling loops. */
547 556 : sort_sibling_loops_cmp_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
548 556 : int *rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
549 556 : pre_and_rev_post_order_compute_fn (fn, NULL, rc_order, false);
550 7570 : for (int i = 0; i < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; ++i)
551 7014 : sort_sibling_loops_cmp_rpo[rc_order[i]] = i;
552 556 : free (rc_order);
553 :
554 556 : auto_vec<loop_p, 3> siblings;
555 3597 : for (auto loop : loops_list (fn, LI_INCLUDE_ROOT))
556 1929 : if (loop->inner && loop->inner->next)
557 : {
558 224 : loop_p sibling = loop->inner;
559 598 : do
560 : {
561 598 : siblings.safe_push (sibling);
562 598 : sibling = sibling->next;
563 : }
564 598 : while (sibling);
565 224 : siblings.qsort (sort_sibling_loops_cmp);
566 224 : loop_p *siblingp = &loop->inner;
567 822 : for (unsigned i = 0; i < siblings.length (); ++i)
568 : {
569 598 : *siblingp = siblings[i];
570 598 : siblingp = &(*siblingp)->next;
571 : }
572 224 : *siblingp = NULL;
573 224 : siblings.truncate (0);
574 556 : }
575 :
576 556 : free (sort_sibling_loops_cmp_rpo);
577 556 : sort_sibling_loops_cmp_rpo = NULL;
578 556 : }
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 19752 : find_subloop_latch_edge_by_profile (vec<edge> latches)
599 : {
600 19752 : unsigned i;
601 19752 : edge e, me = NULL;
602 19752 : profile_count mcount = profile_count::zero (), tcount = profile_count::zero ();
603 :
604 69862 : FOR_EACH_VEC_ELT (latches, i, e)
605 : {
606 50110 : if (e->count ()> mcount)
607 : {
608 7975 : me = e;
609 7975 : mcount = e->count();
610 : }
611 50110 : tcount += e->count();
612 : }
613 :
614 19752 : if (!tcount.initialized_p () || !(tcount.ipa () > HEAVY_EDGE_MIN_SAMPLES)
615 19772 : || (tcount - mcount) * HEAVY_EDGE_RATIO > tcount)
616 19738 : 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 19042 : find_subloop_latch_edge_by_ivs (class loop *loop ATTRIBUTE_UNUSED, vec<edge> latches)
639 : {
640 19042 : edge e, latch = latches[0];
641 19042 : unsigned i;
642 19042 : gphi *phi;
643 19042 : gphi_iterator psi;
644 19042 : tree lop;
645 19042 : basic_block bb;
646 :
647 : /* Find the candidate for the latch edge. */
648 48681 : for (i = 1; latches.iterate (i, &e); i++)
649 29639 : if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src))
650 5730 : latch = e;
651 :
652 : /* Verify that it dominates all the latch edges. */
653 49794 : FOR_EACH_VEC_ELT (latches, i, e)
654 41430 : 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 20547 : for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
660 : {
661 17151 : phi = psi.phi ();
662 17151 : lop = PHI_ARG_DEF_FROM_EDGE (phi, latch);
663 :
664 : /* Ignore the values that are not changed inside the subloop. */
665 20739 : if (TREE_CODE (lop) != SSA_NAME
666 17151 : || SSA_NAME_DEF_STMT (lop) == phi)
667 3588 : continue;
668 13563 : bb = gimple_bb (SSA_NAME_DEF_STMT (lop));
669 13563 : if (!bb || !flow_bb_inside_loop_p (loop, bb))
670 17 : continue;
671 :
672 36664 : FOR_EACH_VEC_ELT (latches, i, e)
673 24481 : if (e != latch
674 24481 : && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop)
675 : return NULL;
676 : }
677 :
678 3396 : 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 25413 : find_subloop_latch_edge (class loop *loop)
691 : {
692 25413 : vec<edge> latches = get_loop_latch_edges (loop);
693 25413 : edge latch = NULL;
694 :
695 25413 : if (latches.length () > 1)
696 : {
697 19752 : latch = find_subloop_latch_edge_by_profile (latches);
698 :
699 19752 : 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 19752 : && current_ir_type () == IR_GIMPLE)
704 19042 : latch = find_subloop_latch_edge_by_ivs (loop, latches);
705 : }
706 :
707 25413 : latches.release ();
708 25413 : 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 70691 : mfb_redirect_edges_in_set (edge e, void *data)
716 : {
717 70691 : hash_set<edge> *set = (hash_set<edge> *)data;
718 70691 : return set->contains (e);
719 : }
720 :
721 : /* Creates a subloop of LOOP with latch edge LATCH. */
722 :
723 : static void
724 3410 : form_subloop (class loop *loop, edge latch)
725 : {
726 3410 : edge_iterator ei;
727 3410 : edge e, new_entry;
728 3410 : class loop *new_loop;
729 :
730 3410 : hash_set<edge> *reis_set = new hash_set<edge>;
731 14049 : FOR_EACH_EDGE (e, ei, loop->header->preds)
732 : {
733 10639 : if (e != latch)
734 7229 : reis_set->add (e);
735 : }
736 3410 : new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set, reis_set);
737 3410 : delete reis_set;
738 :
739 3410 : 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 3410 : new_loop = alloc_loop ();
744 3410 : new_loop->header = new_entry->dest;
745 3410 : new_loop->latch = latch->src;
746 3410 : add_loop (new_loop, loop);
747 3410 : }
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 22003 : merge_latch_edges (class loop *loop)
754 : {
755 22003 : vec<edge> latches = get_loop_latch_edges (loop);
756 22003 : edge latch, e;
757 22003 : unsigned i;
758 :
759 22003 : gcc_assert (latches.length () > 0);
760 :
761 22003 : if (latches.length () == 1)
762 5661 : loop->latch = latches[0]->src;
763 : else
764 : {
765 16342 : if (dump_file)
766 8 : fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num);
767 :
768 16342 : hash_set<edge> *reis_set = new hash_set<edge>;
769 75585 : FOR_EACH_VEC_ELT (latches, i, e)
770 42901 : reis_set->add (e);
771 16342 : latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set, reis_set);
772 16342 : delete reis_set;
773 :
774 16342 : loop->header = latch->dest;
775 16342 : loop->latch = latch->src;
776 : }
777 :
778 22003 : latches.release ();
779 22003 : }
780 :
781 : /* LOOP may have several latch edges. Transform it into (possibly several)
782 : loops with single latch edge. */
783 :
784 : static void
785 22003 : disambiguate_multiple_latches (class loop *loop)
786 : {
787 22003 : 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 22003 : 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 22003 : e = find_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), loop->header);
809 22003 : if (e)
810 897 : split_edge (e);
811 :
812 28823 : while (1)
813 : {
814 25413 : e = find_subloop_latch_edge (loop);
815 25413 : if (!e)
816 : break;
817 :
818 3410 : form_subloop (loop, e);
819 : }
820 :
821 22003 : merge_latch_edges (loop);
822 22003 : }
823 :
824 : /* Split loops with multiple latch edges. */
825 :
826 : void
827 28479912 : disambiguate_loops_with_multiple_latches (void)
828 : {
829 103053977 : for (auto loop : loops_list (cfun, 0))
830 : {
831 17614241 : if (!loop->latch)
832 22003 : disambiguate_multiple_latches (loop);
833 28479912 : }
834 28479912 : }
835 :
836 : /* Return nonzero if basic block BB belongs to LOOP. */
837 : bool
838 3237821728 : flow_bb_inside_loop_p (const class loop *loop, const_basic_block bb)
839 : {
840 3237821728 : class loop *source_loop;
841 :
842 3237821728 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
843 3237808998 : || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
844 : return 0;
845 :
846 3219758128 : source_loop = bb->loop_father;
847 3219758128 : 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 1225546445 : glb_enum_p (const_basic_block bb, const void *glb_loop)
853 : {
854 1225546445 : const class loop *const loop = (const class loop *) glb_loop;
855 1225546445 : return (bb != loop->header
856 1225546445 : && 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 219274676 : get_loop_body_with_size (const class loop *loop, basic_block *body,
868 : unsigned max_size)
869 : {
870 219274676 : return dfs_enumerate_from (loop->header, 1, glb_enum_p,
871 219274676 : 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 21892249 : get_loop_body (const class loop *loop)
880 : {
881 21892249 : basic_block *body, bb;
882 21892249 : unsigned tv = 0;
883 :
884 21892249 : gcc_assert (loop->num_nodes);
885 :
886 21892249 : body = XNEWVEC (basic_block, loop->num_nodes);
887 :
888 21892249 : 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 6246 : gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks_for_fn (cfun));
893 6246 : body[tv++] = loop->header;
894 6246 : body[tv++] = EXIT_BLOCK_PTR_FOR_FN (cfun);
895 28451 : FOR_EACH_BB_FN (bb, cfun)
896 22205 : body[tv++] = bb;
897 : }
898 : else
899 21886003 : tv = get_loop_body_with_size (loop, body, loop->num_nodes);
900 :
901 21892249 : gcc_assert (tv == loop->num_nodes);
902 21892249 : 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 5711004 : fill_sons_in_loop (const class loop *loop, basic_block bb,
910 : basic_block *tovisit, int *tv)
911 : {
912 9439361 : basic_block son, postpone = NULL;
913 :
914 9439361 : tovisit[(*tv)++] = bb;
915 9439361 : for (son = first_dom_son (CDI_DOMINATORS, bb);
916 19112871 : son;
917 9673510 : son = next_dom_son (CDI_DOMINATORS, son))
918 : {
919 9673510 : if (!flow_bb_inside_loop_p (loop, son))
920 2214879 : continue;
921 :
922 7458631 : if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
923 : {
924 3728357 : postpone = son;
925 3728357 : continue;
926 : }
927 3730274 : fill_sons_in_loop (loop, son, tovisit, tv);
928 : }
929 :
930 9439361 : if (postpone)
931 : fill_sons_in_loop (loop, postpone, tovisit, tv);
932 5711004 : }
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 1980730 : get_loop_body_in_dom_order (const class loop *loop)
940 : {
941 1980730 : basic_block *tovisit;
942 1980730 : int tv;
943 :
944 1980730 : gcc_assert (loop->num_nodes);
945 :
946 1980730 : tovisit = XNEWVEC (basic_block, loop->num_nodes);
947 :
948 1980730 : gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
949 :
950 1980730 : tv = 0;
951 1980730 : fill_sons_in_loop (loop, loop->header, tovisit, &tv);
952 :
953 1980730 : gcc_assert (tv == (int) loop->num_nodes);
954 :
955 1980730 : 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 146658 : get_loop_body_in_custom_order (const class loop *loop, void *data,
975 : int (*bb_comparator) (const void *, const void *, void *))
976 : {
977 146658 : basic_block *bbs = get_loop_body (loop);
978 :
979 146658 : gcc_sort_r (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator, data);
980 :
981 146658 : return bbs;
982 : }
983 :
984 : /* Get body of a LOOP in breadth first sort order. */
985 :
986 : basic_block *
987 399982 : get_loop_body_in_bfs_order (const class loop *loop)
988 : {
989 399982 : basic_block *blocks;
990 399982 : basic_block bb;
991 399982 : unsigned int i = 1;
992 399982 : unsigned int vc = 0;
993 :
994 399982 : gcc_assert (loop->num_nodes);
995 399982 : gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
996 :
997 399982 : blocks = XNEWVEC (basic_block, loop->num_nodes);
998 399982 : auto_bitmap visited;
999 399982 : blocks[0] = loop->header;
1000 399982 : bitmap_set_bit (visited, loop->header->index);
1001 2104919 : while (i < loop->num_nodes)
1002 : {
1003 1304955 : edge e;
1004 1304955 : edge_iterator ei;
1005 1304955 : gcc_assert (i > vc);
1006 1304955 : bb = blocks[vc++];
1007 :
1008 3577722 : FOR_EACH_EDGE (e, ei, bb->succs)
1009 : {
1010 2272767 : if (flow_bb_inside_loop_p (loop, e->dest))
1011 : {
1012 : /* This bb is now visited. */
1013 1562376 : if (bitmap_set_bit (visited, e->dest->index))
1014 1356303 : blocks[i++] = e->dest;
1015 : }
1016 : }
1017 : }
1018 :
1019 399982 : return blocks;
1020 399982 : }
1021 :
1022 : /* Hash function for struct loop_exit. */
1023 :
1024 : hashval_t
1025 251891504 : loop_exit_hasher::hash (loop_exit *exit)
1026 : {
1027 251891504 : return htab_hash_pointer (exit->e);
1028 : }
1029 :
1030 : /* Equality function for struct loop_exit. Compares with edge. */
1031 :
1032 : bool
1033 298844117 : loop_exit_hasher::equal (loop_exit *exit, edge e)
1034 : {
1035 298844117 : return exit->e == e;
1036 : }
1037 :
1038 : /* Frees the list of loop exit descriptions EX. */
1039 :
1040 : void
1041 19312452 : loop_exit_hasher::remove (loop_exit *exit)
1042 : {
1043 19312452 : loop_exit *next;
1044 40097852 : for (; exit; exit = next)
1045 : {
1046 20785400 : next = exit->next_e;
1047 :
1048 20785400 : exit->next->prev = exit->prev;
1049 20785400 : exit->prev->next = exit->next;
1050 :
1051 20785400 : ggc_free (exit);
1052 : }
1053 19312452 : }
1054 :
1055 : /* Returns the list of records for E as an exit of a loop. */
1056 :
1057 : static struct loop_exit *
1058 40951114 : get_exit_descriptions (edge e)
1059 : {
1060 40951114 : 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 552240905 : rescan_loop_exit (edge e, bool new_edge, bool removed)
1071 : {
1072 552240905 : struct loop_exit *exits = NULL, *exit;
1073 552240905 : class loop *aloop, *cloop;
1074 :
1075 552240905 : if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1076 : return;
1077 :
1078 253730489 : if (!removed
1079 238136379 : && e->src->loop_father != NULL
1080 238136379 : && e->dest->loop_father != NULL
1081 489831832 : && !flow_bb_inside_loop_p (e->src->loop_father, e->dest))
1082 : {
1083 37357577 : cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
1084 37357577 : for (aloop = e->src->loop_father;
1085 58142977 : aloop != cloop;
1086 20785400 : aloop = loop_outer (aloop))
1087 : {
1088 20785400 : exit = ggc_alloc<loop_exit> ();
1089 20785400 : exit->e = e;
1090 :
1091 20785400 : exit->next = aloop->exits->next;
1092 20785400 : exit->prev = aloop->exits;
1093 20785400 : exit->next->prev = exit;
1094 20785400 : exit->prev->next = exit;
1095 :
1096 20785400 : exit->next_e = exits;
1097 20785400 : exits = exit;
1098 : }
1099 : }
1100 :
1101 253730489 : if (!exits && new_edge)
1102 : return;
1103 :
1104 38522085 : loop_exit **slot
1105 57731718 : = current_loops->exits->find_slot_with_hash (e, htab_hash_pointer (e),
1106 : exits ? INSERT : NO_INSERT);
1107 38522085 : if (!slot)
1108 : return;
1109 :
1110 20635341 : if (exits)
1111 : {
1112 19312452 : if (*slot)
1113 402682 : loop_exit_hasher::remove (*slot);
1114 19312452 : *slot = exits;
1115 : }
1116 : else
1117 1322889 : 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 17291788 : record_loop_exits (void)
1125 : {
1126 17291788 : basic_block bb;
1127 17291788 : edge_iterator ei;
1128 17291788 : edge e;
1129 :
1130 17291788 : if (!current_loops)
1131 0 : return;
1132 :
1133 17291788 : if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1134 : return;
1135 17291788 : loops_state_set (LOOPS_HAVE_RECORDED_EXITS);
1136 :
1137 17291788 : gcc_assert (current_loops->exits == NULL);
1138 17291788 : current_loops->exits
1139 34583576 : = hash_table<loop_exit_hasher>::create_ggc (2 * number_of_loops (cfun));
1140 :
1141 173447711 : FOR_EACH_BB_FN (bb, cfun)
1142 : {
1143 375074415 : FOR_EACH_EDGE (e, ei, bb->succs)
1144 : {
1145 218918492 : 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 17291788 : release_recorded_exits (function *fn)
1184 : {
1185 17291788 : gcc_assert (loops_state_satisfies_p (fn, LOOPS_HAVE_RECORDED_EXITS));
1186 17291788 : loops_for_fn (fn)->exits->empty ();
1187 17291788 : loops_for_fn (fn)->exits = NULL;
1188 17291788 : loops_state_clear (fn, LOOPS_HAVE_RECORDED_EXITS);
1189 17291788 : }
1190 :
1191 : /* Returns the list of the exit edges of a LOOP. */
1192 :
1193 : auto_vec<edge>
1194 36655714 : get_loop_exit_edges (const class loop *loop, basic_block *body)
1195 : {
1196 36655714 : auto_vec<edge> edges;
1197 36655714 : edge e;
1198 36655714 : unsigned i;
1199 36655714 : edge_iterator ei;
1200 36655714 : struct loop_exit *exit;
1201 :
1202 36655714 : 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 36655714 : if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1207 : {
1208 111942559 : for (exit = loop->exits->next; exit->e; exit = exit->next)
1209 75951067 : edges.safe_push (exit->e);
1210 : }
1211 : else
1212 : {
1213 664222 : bool body_from_caller = true;
1214 664222 : if (!body)
1215 : {
1216 654996 : body = get_loop_body (loop);
1217 654996 : body_from_caller = false;
1218 : }
1219 4792290 : for (i = 0; i < loop->num_nodes; i++)
1220 10763669 : FOR_EACH_EDGE (e, ei, body[i]->succs)
1221 : {
1222 6635601 : if (!flow_bb_inside_loop_p (loop, e->dest))
1223 1605756 : edges.safe_push (e);
1224 : }
1225 664222 : if (!body_from_caller)
1226 654996 : free (body);
1227 : }
1228 :
1229 36655714 : 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 636 : for (i = 0; i < loop->num_nodes; i++)
1245 570 : 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 45190644 : add_bb_to_loop (basic_block bb, class loop *loop)
1255 : {
1256 45190644 : unsigned i;
1257 45190644 : loop_p ploop;
1258 45190644 : edge_iterator ei;
1259 45190644 : edge e;
1260 :
1261 45190644 : gcc_assert (bb->loop_father == NULL);
1262 45190644 : bb->loop_father = loop;
1263 45190644 : loop->num_nodes++;
1264 65487956 : FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
1265 20297312 : ploop->num_nodes++;
1266 :
1267 94547453 : FOR_EACH_EDGE (e, ei, bb->succs)
1268 : {
1269 49356809 : rescan_loop_exit (e, true, false);
1270 : }
1271 75847136 : FOR_EACH_EDGE (e, ei, bb->preds)
1272 : {
1273 30656492 : rescan_loop_exit (e, true, false);
1274 : }
1275 45190644 : }
1276 :
1277 : /* Remove basic block BB from loops. */
1278 : void
1279 56691628 : remove_bb_from_loops (basic_block bb)
1280 : {
1281 56691628 : unsigned i;
1282 56691628 : class loop *loop = bb->loop_father;
1283 56691628 : loop_p ploop;
1284 56691628 : edge_iterator ei;
1285 56691628 : edge e;
1286 :
1287 56691628 : gcc_assert (loop != NULL);
1288 56691628 : loop->num_nodes--;
1289 78233778 : FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
1290 21542150 : ploop->num_nodes--;
1291 56691628 : bb->loop_father = NULL;
1292 :
1293 85254435 : FOR_EACH_EDGE (e, ei, bb->succs)
1294 : {
1295 28562807 : rescan_loop_exit (e, false, true);
1296 : }
1297 77142020 : FOR_EACH_EDGE (e, ei, bb->preds)
1298 : {
1299 20450392 : rescan_loop_exit (e, false, true);
1300 : }
1301 56691628 : }
1302 :
1303 : /* Finds nearest common ancestor in loop tree for given loops. */
1304 : class loop *
1305 206091120 : find_common_loop (class loop *loop_s, class loop *loop_d)
1306 : {
1307 206091120 : unsigned sdepth, ddepth;
1308 :
1309 206091120 : if (!loop_s) return loop_d;
1310 206090575 : if (!loop_d) return loop_s;
1311 :
1312 206090575 : sdepth = loop_depth (loop_s);
1313 206090575 : ddepth = loop_depth (loop_d);
1314 :
1315 83638724 : if (sdepth < ddepth)
1316 6415793 : loop_d = (*loop_d->superloops)[sdepth];
1317 199674782 : else if (sdepth > ddepth)
1318 100692237 : loop_s = (*loop_s->superloops)[ddepth];
1319 :
1320 207009719 : while (loop_s != loop_d)
1321 : {
1322 919144 : loop_s = loop_outer (loop_s);
1323 919144 : 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 148649 : delete_loop (class loop *loop)
1332 : {
1333 : /* Remove the loop from structure. */
1334 148649 : flow_loop_tree_node_remove (loop);
1335 :
1336 : /* Remove loop from loops array. */
1337 148649 : (*current_loops->larray)[loop->num] = NULL;
1338 :
1339 : /* Free loop data. */
1340 148649 : flow_loop_free (loop);
1341 148649 : }
1342 :
1343 : /* Cancels the LOOP; it must be innermost one. */
1344 :
1345 : static void
1346 10666 : cancel_loop (class loop *loop)
1347 : {
1348 10666 : basic_block *bbs;
1349 10666 : unsigned i;
1350 10666 : class loop *outer = loop_outer (loop);
1351 :
1352 10666 : gcc_assert (!loop->inner);
1353 :
1354 : /* Move blocks up one level (they should be removed as soon as possible). */
1355 10666 : bbs = get_loop_body (loop);
1356 44175 : for (i = 0; i < loop->num_nodes; i++)
1357 22843 : bbs[i]->loop_father = outer;
1358 :
1359 10666 : free (bbs);
1360 10666 : delete_loop (loop);
1361 10666 : }
1362 :
1363 : /* Cancels LOOP and all its subloops. */
1364 : void
1365 10666 : cancel_loop_tree (class loop *loop)
1366 : {
1367 11154 : while (loop->inner)
1368 488 : cancel_loop_tree (loop->inner);
1369 10666 : cancel_loop (loop);
1370 10666 : }
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 370708589 : verify_loop_structure (void)
1391 : {
1392 370708589 : unsigned *sizes, i, j;
1393 370708589 : basic_block bb, *bbs;
1394 370708589 : int err = 0;
1395 370708589 : edge e;
1396 370708589 : unsigned num = number_of_loops (cfun);
1397 370708589 : struct loop_exit *exit, *mexit;
1398 370708589 : bool dom_available = dom_info_available_p (CDI_DOMINATORS);
1399 :
1400 370708589 : 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 370708589 : if (!dom_available)
1408 100058953 : calculate_dominance_info (CDI_DOMINATORS);
1409 : else
1410 270649636 : verify_dominators (CDI_DOMINATORS);
1411 :
1412 : /* Check the loop tree root. */
1413 370708589 : if (current_loops->tree_root->header != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1414 370708589 : || current_loops->tree_root->latch != EXIT_BLOCK_PTR_FOR_FN (cfun)
1415 370708589 : || (current_loops->tree_root->num_nodes
1416 370708589 : != (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 3684350974 : FOR_EACH_BB_FN (bb, cfun)
1424 3313642385 : if (bb_loop_header_p (bb))
1425 : {
1426 196740127 : 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 196740127 : 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 3116902258 : 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 370708589 : auto_sbitmap visited (last_basic_block_for_fn (cfun));
1445 370708589 : bitmap_clear (visited);
1446 370708589 : bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
1447 1308865894 : for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1448 : {
1449 196740127 : unsigned n;
1450 :
1451 196740127 : 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 196740127 : n = get_loop_body_with_size (loop, bbs, n_basic_blocks_for_fn (cfun));
1459 196740127 : 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 1304787324 : for (j = 0; j < n; j++)
1467 : {
1468 1108047197 : bb = bbs[j];
1469 :
1470 1108047197 : 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 1108047197 : if (bitmap_bit_p (visited, bb->index))
1479 260564980 : continue;
1480 847482217 : bitmap_set_bit (visited, bb->index);
1481 :
1482 847482217 : 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 370708589 : }
1490 370708589 : free (bbs);
1491 :
1492 : /* Check headers and latches. */
1493 1308865894 : for (auto loop : loops_list (cfun, 0))
1494 : {
1495 196740127 : i = loop->num;
1496 196740127 : if (loop->header == NULL)
1497 0 : continue;
1498 196740127 : 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 196740127 : if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
1504 196740127 : && 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 196740127 : if (loop->latch)
1510 : {
1511 195851761 : 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 195851761 : 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 196740127 : if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
1523 : {
1524 30283162 : 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 30283162 : 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 30283162 : 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 196740127 : 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 196740127 : if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1546 : {
1547 27004840 : edge_iterator ei;
1548 81014784 : FOR_EACH_EDGE (e, ei, loop->header->preds)
1549 54009944 : if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header)
1550 54009944 : && 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 196740127 : tree ref;
1560 196740127 : if (loop->nb_iterations
1561 196740127 : && (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 370708589 : }
1569 :
1570 : /* Check irreducible loops. */
1571 370708589 : if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1572 : {
1573 33496000 : auto_edge_flag saved_edge_irr (cfun);
1574 33496000 : auto_bb_flag saved_bb_irr (cfun);
1575 : /* Save old info. */
1576 430869792 : FOR_EACH_BB_FN (bb, cfun)
1577 : {
1578 397373792 : edge_iterator ei;
1579 397373792 : if (bb->flags & BB_IRREDUCIBLE_LOOP)
1580 541817 : bb->flags |= saved_bb_irr;
1581 955025163 : FOR_EACH_EDGE (e, ei, bb->succs)
1582 557651371 : if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1583 782540 : e->flags |= saved_edge_irr;
1584 : }
1585 :
1586 : /* Recount it. */
1587 33496000 : mark_irreducible_loops ();
1588 :
1589 : /* Compare. */
1590 430869792 : FOR_EACH_BB_FN (bb, cfun)
1591 : {
1592 397373792 : edge_iterator ei;
1593 :
1594 397373792 : if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1595 397373792 : && !(bb->flags & saved_bb_irr))
1596 : {
1597 0 : error ("basic block %d should be marked irreducible", bb->index);
1598 0 : err = 1;
1599 : }
1600 397373792 : else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1601 397373792 : && (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 397373792 : bb->flags &= ~saved_bb_irr;
1607 955025163 : FOR_EACH_EDGE (e, ei, bb->succs)
1608 : {
1609 557651371 : if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1610 557651371 : && !(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 557651371 : else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1617 557651371 : && (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 557651371 : e->flags &= ~saved_edge_irr;
1624 : }
1625 : }
1626 33496000 : }
1627 :
1628 : /* Check the recorded loop exits. */
1629 1308865894 : for (auto loop : loops_list (cfun, 0))
1630 : {
1631 196740127 : 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 196740127 : for (mexit = loop->exits, exit = mexit->next, i = 0;
1642 240760354 : exit->e && exit != mexit;
1643 44020227 : exit = exit->next)
1644 : {
1645 44020227 : if (i++ & 1)
1646 13109326 : mexit = mexit->next;
1647 : }
1648 :
1649 196740127 : if (exit != loop->exits)
1650 : {
1651 0 : error ("corrupted exits list of loop %d", loop->num);
1652 0 : err = 1;
1653 : }
1654 : }
1655 :
1656 196740127 : if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1657 : {
1658 172637307 : 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 370708589 : }
1666 :
1667 370708589 : if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1668 : {
1669 25513655 : unsigned n_exits = 0, eloops;
1670 :
1671 25513655 : sizes = XCNEWVEC (unsigned, num);
1672 25513655 : memset (sizes, 0, sizeof (unsigned) * num);
1673 361705756 : FOR_EACH_BB_FN (bb, cfun)
1674 : {
1675 336192101 : edge_iterator ei;
1676 336192101 : if (bb->loop_father == current_loops->tree_root)
1677 223589168 : continue;
1678 287856264 : FOR_EACH_EDGE (e, ei, bb->succs)
1679 : {
1680 175253331 : if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
1681 134302217 : continue;
1682 :
1683 40951114 : n_exits++;
1684 40951114 : exit = get_exit_descriptions (e);
1685 40951114 : 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 40951114 : eloops = 0;
1692 84971341 : for (; exit; exit = exit->next_e)
1693 44020227 : eloops++;
1694 :
1695 40951114 : for (class loop *loop = bb->loop_father;
1696 84971341 : 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 84971341 : && loop != loop_outer (e->dest->loop_father);
1702 44020227 : loop = loop_outer (loop))
1703 : {
1704 44020227 : eloops--;
1705 44020227 : sizes[loop->num]++;
1706 : }
1707 :
1708 40951114 : 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 25513655 : if (n_exits != current_loops->exits->elements ())
1718 : {
1719 0 : error ("too many loop exits recorded");
1720 0 : err = 1;
1721 : }
1722 :
1723 100643785 : for (auto loop : loops_list (cfun, 0))
1724 : {
1725 24102820 : eloops = 0;
1726 68123047 : for (exit = loop->exits->next; exit->e; exit = exit->next)
1727 44020227 : eloops++;
1728 24102820 : 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 25513655 : }
1735 :
1736 25513655 : free (sizes);
1737 : }
1738 :
1739 370708589 : gcc_assert (!err);
1740 :
1741 370708589 : if (!dom_available)
1742 100058953 : free_dominance_info (CDI_DOMINATORS);
1743 370708589 : }
1744 :
1745 : #if __GNUC__ >= 10
1746 : # pragma GCC diagnostic pop
1747 : #endif
1748 :
1749 : /* Returns latch edge of LOOP. */
1750 : edge
1751 12849950 : loop_latch_edge (const class loop *loop)
1752 : {
1753 12849950 : return find_edge (loop->latch, loop->header);
1754 : }
1755 :
1756 : /* Returns preheader edge of LOOP. */
1757 : edge
1758 429796929 : loop_preheader_edge (const class loop *loop)
1759 : {
1760 429796929 : edge e;
1761 429796929 : edge_iterator ei;
1762 :
1763 429796929 : gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
1764 : && ! loops_state_satisfies_p (LOOPS_MAY_HAVE_MULTIPLE_LATCHES));
1765 :
1766 655838574 : FOR_EACH_EDGE (e, ei, loop->header->preds)
1767 654992107 : if (e->src != loop->latch)
1768 : break;
1769 :
1770 429796929 : if (! e)
1771 : {
1772 846467 : gcc_assert (! loop_outer (loop));
1773 846467 : 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 35933339 : loop_exit_edge_p (const class loop *loop, const_edge e)
1783 : {
1784 35933339 : return (flow_bb_inside_loop_p (loop, e->src)
1785 35933339 : && !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 35251357 : single_exit (const class loop *loop)
1794 : {
1795 35251357 : struct loop_exit *exit = loop->exits->next;
1796 :
1797 35251357 : if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1798 : return NULL;
1799 :
1800 35222330 : if (exit->e && exit->next == loop->exits)
1801 : return exit->e;
1802 : else
1803 10553083 : 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 1471417 : loop_exits_from_bb_p (class loop *loop, basic_block bb)
1827 : {
1828 1471417 : edge e;
1829 1471417 : edge_iterator ei;
1830 :
1831 3098834 : FOR_EACH_EDGE (e, ei, bb->succs)
1832 2582898 : 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 586247 : get_loop_location (class loop *loop)
1842 : {
1843 586247 : rtx_insn *insn = NULL;
1844 586247 : class niter_desc *desc = NULL;
1845 586247 : 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 586247 : desc = get_simple_loop_desc (loop);
1854 586247 : if (desc->in_edge)
1855 : {
1856 589025 : FOR_BB_INSNS_REVERSE (desc->in_edge->src, insn)
1857 : {
1858 584010 : if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1859 406027 : 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 180220 : if ((exit = single_exit (loop)))
1865 : {
1866 206350 : FOR_BB_INSNS_REVERSE (exit->src, insn)
1867 : {
1868 197505 : if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1869 100112 : return insn;
1870 : }
1871 : }
1872 : /* Next check the latch, to see if it is non-empty. */
1873 189655 : FOR_BB_INSNS_REVERSE (loop->latch, insn)
1874 : {
1875 131612 : if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1876 22065 : 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 277656 : FOR_BB_INSNS (loop->header, insn)
1881 : {
1882 266509 : if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1883 46896 : return insn;
1884 : }
1885 : /* If all else fails, simply return the current function location. */
1886 11147 : 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 17349902 : record_niter_bound (class loop *loop, const widest_int &i_bound,
1896 : bool realistic, bool upper)
1897 : {
1898 17349902 : if (wi::min_precision (i_bound, SIGNED) > bound_wide_int ().get_precision ())
1899 0 : return;
1900 :
1901 17349902 : 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 17349902 : if (upper
1906 17349902 : && (!loop->any_upper_bound
1907 15888052 : || wi::ltu_p (bound, loop->nb_iterations_upper_bound)))
1908 : {
1909 875278 : loop->any_upper_bound = true;
1910 875278 : loop->nb_iterations_upper_bound = bound;
1911 875278 : if (!loop->any_likely_upper_bound)
1912 : {
1913 506816 : loop->any_likely_upper_bound = true;
1914 506816 : loop->nb_iterations_likely_upper_bound = bound;
1915 : }
1916 : }
1917 17349902 : if (realistic
1918 17349902 : && (!loop->any_estimate
1919 2825992 : || wi::ltu_p (bound, loop->nb_iterations_estimate)))
1920 : {
1921 240644 : loop->any_estimate = true;
1922 240644 : loop->nb_iterations_estimate = bound;
1923 : }
1924 17349902 : if (!realistic
1925 17349902 : && (!loop->any_likely_upper_bound
1926 14288333 : || wi::ltu_p (bound, loop->nb_iterations_likely_upper_bound)))
1927 : {
1928 240370 : loop->any_likely_upper_bound = true;
1929 240370 : 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 17349902 : if (loop->any_upper_bound
1935 17345687 : && loop->any_estimate
1936 26463351 : && wi::ltu_p (loop->nb_iterations_upper_bound,
1937 9113449 : loop->nb_iterations_estimate))
1938 6398 : loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
1939 17349902 : if (loop->any_upper_bound
1940 17345687 : && loop->any_likely_upper_bound
1941 34695589 : && wi::ltu_p (loop->nb_iterations_upper_bound,
1942 17345687 : loop->nb_iterations_likely_upper_bound))
1943 37645 : 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 307867 : max_stmt_executions_int (class loop *loop)
1972 : {
1973 307867 : HOST_WIDE_INT nit = get_max_loop_iterations_int (loop);
1974 307867 : HOST_WIDE_INT snit;
1975 :
1976 307867 : if (nit == -1)
1977 : return -1;
1978 :
1979 281910 : snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
1980 :
1981 : /* If the computation overflows, return -1. */
1982 281910 : 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 4947446 : likely_max_stmt_executions_int (class loop *loop)
1991 : {
1992 4947446 : HOST_WIDE_INT nit = get_likely_max_loop_iterations_int (loop);
1993 4947446 : HOST_WIDE_INT snit;
1994 :
1995 4947446 : if (nit == -1)
1996 : return -1;
1997 :
1998 4206110 : snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
1999 :
2000 : /* If the computation overflows, return -1. */
2001 4206110 : 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 9253115 : get_estimated_loop_iterations (class loop *loop, widest_int *nit)
2010 : {
2011 : /* Even if the bound is not recorded, possibly we can derrive one from
2012 : profile. */
2013 9253115 : if (!loop->any_estimate)
2014 : {
2015 5300371 : sreal snit;
2016 5300371 : bool reliable;
2017 5300371 : if (expected_loop_iterations_by_profile (loop, &snit, &reliable)
2018 5300371 : && reliable)
2019 : {
2020 3 : *nit = snit.to_nearest_int ();
2021 3 : return true;
2022 : }
2023 : return false;
2024 : }
2025 :
2026 3952744 : *nit = widest_int::from (loop->nb_iterations_estimate, SIGNED);
2027 3952744 : 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 22952655 : get_max_loop_iterations (const class loop *loop, widest_int *nit)
2036 : {
2037 22952655 : if (!loop->any_upper_bound)
2038 : return false;
2039 :
2040 20517661 : *nit = widest_int::from (loop->nb_iterations_upper_bound, SIGNED);
2041 20517661 : 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 1748447 : get_max_loop_iterations_int (const class loop *loop)
2050 : {
2051 1748447 : widest_int nit;
2052 1748447 : HOST_WIDE_INT hwi_nit;
2053 :
2054 1748447 : if (!get_max_loop_iterations (loop, &nit))
2055 : return -1;
2056 :
2057 1370140 : if (!wi::fits_shwi_p (nit))
2058 : return -1;
2059 1309153 : hwi_nit = nit.to_shwi ();
2060 :
2061 1309153 : return hwi_nit < 0 ? -1 : hwi_nit;
2062 1748447 : }
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 5392076 : get_likely_max_loop_iterations (class loop *loop, widest_int *nit)
2070 : {
2071 5392076 : if (!loop->any_likely_upper_bound)
2072 : return false;
2073 :
2074 4802935 : *nit = widest_int::from (loop->nb_iterations_likely_upper_bound, SIGNED);
2075 4802935 : 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 5010039 : get_likely_max_loop_iterations_int (class loop *loop)
2084 : {
2085 5010039 : widest_int nit;
2086 5010039 : HOST_WIDE_INT hwi_nit;
2087 :
2088 5010039 : if (!get_likely_max_loop_iterations (loop, &nit))
2089 : return -1;
2090 :
2091 4552278 : if (!wi::fits_shwi_p (nit))
2092 : return -1;
2093 4268146 : hwi_nit = nit.to_shwi ();
2094 :
2095 4268146 : return hwi_nit < 0 ? -1 : hwi_nit;
2096 5010039 : }
2097 :
2098 : /* Returns the loop depth of the loop BB belongs to. */
2099 :
2100 : int
2101 54765863 : bb_loop_depth (const_basic_block bb)
2102 : {
2103 66970286 : 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 268391 : mark_loop_for_removal (loop_p loop)
2110 : {
2111 268391 : if (loop->header == NULL)
2112 : return;
2113 268391 : loop->former_header = loop->header;
2114 268391 : loop->header = NULL;
2115 268391 : loop->latch = NULL;
2116 268391 : 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 1362774328 : loops_list::walk_loop_tree (class loop *root, unsigned flags)
2128 : {
2129 1362774328 : bool only_innermost_p = flags & LI_ONLY_INNERMOST;
2130 1362774328 : bool from_innermost_p = flags & LI_FROM_INNERMOST;
2131 1362774328 : 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 1362774328 : if (!root->inner)
2137 : {
2138 1100560889 : if (flags & LI_INCLUDE_ROOT)
2139 11935 : this->to_visit.quick_push (root->num);
2140 1100560889 : return;
2141 : }
2142 262213439 : else if (preorder_p && flags & LI_INCLUDE_ROOT)
2143 51198 : this->to_visit.quick_push (root->num);
2144 :
2145 : class loop *aloop;
2146 68585004 : for (aloop = root->inner;
2147 330798443 : aloop->inner != NULL;
2148 68585004 : aloop = aloop->inner)
2149 : {
2150 68585004 : if (preorder_p)
2151 49777615 : this->to_visit.quick_push (aloop->num);
2152 68585004 : continue;
2153 : }
2154 :
2155 913452801 : while (1)
2156 : {
2157 913452801 : gcc_assert (aloop != root);
2158 913452801 : if (from_innermost_p || aloop->inner == NULL)
2159 785027744 : this->to_visit.quick_push (aloop->num);
2160 :
2161 913452801 : if (aloop->next)
2162 : {
2163 99041664 : for (aloop = aloop->next;
2164 582654358 : aloop->inner != NULL;
2165 99041664 : aloop = aloop->inner)
2166 : {
2167 99041664 : if (preorder_p)
2168 78647442 : this->to_visit.quick_push (aloop->num);
2169 99041664 : continue;
2170 : }
2171 : }
2172 429840107 : 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 262213439 : if (from_innermost_p && flags & LI_INCLUDE_ROOT)
2181 0 : this->to_visit.quick_push (root->num);
2182 68585004 : }
2183 :
|
