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