xref: /dragonfly/contrib/gcc-8.0/gcc/cfgloop.c (revision 37de577a)
1 /* Natural loop discovery code for GNU compiler.
2    Copyright (C) 2000-2018 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 
35 static void flow_loops_cfg_dump (FILE *);
36 
37 /* Dump loop related CFG information.  */
38 
39 static void
40 flow_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 
61 bool
62 flow_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 
73 struct loop *
74 superloop_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 
88 static vec<edge>
89 get_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 
107 void
108 flow_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 
162 void
163 flow_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 
183 void
184 flow_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 
207 void
208 flow_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 
231 int
232 flow_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 
280 static void
281 establish_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 
304 void
305 flow_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 
324 void
325 flow_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 
346 struct loop *
347 alloc_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 
364 void
365 init_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 
387 bool
388 bb_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 
422 struct loops *
423 flow_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 
538 static int *sort_sibling_loops_cmp_rpo;
539 static int
540 sort_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 
550 void
551 sort_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 
605 static edge
606 find_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 
645 static edge
646 find_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 
697 static edge
698 find_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 
722 static hash_set<edge> *mfb_reis_set;
723 static bool
724 mfb_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 
731 static void
732 form_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 
761 static void
762 merge_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 
794 static void
795 disambiguate_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 
836 void
837 disambiguate_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.  */
849 bool
850 flow_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.  */
863 static bool
864 glb_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 
878 unsigned
879 get_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 
890 basic_block *
891 get_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 
920 static void
921 fill_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 
950 basic_block *
951 get_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 
972 basic_block *
973 get_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 
985 basic_block *
986 get_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 
1023 hashval_t
1024 loop_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 
1031 bool
1032 loop_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 
1039 void
1040 loop_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 
1056 static struct loop_exit *
1057 get_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 
1068 void
1069 rescan_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 
1122 void
1123 record_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 
1152 int
1153 dump_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 
1170 extern void dump_recorded_exits (FILE *);
1171 void
1172 dump_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 
1181 void
1182 release_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 
1192 vec<edge>
1193 get_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 
1228 unsigned
1229 num_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.  */
1247 void
1248 add_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.  */
1272 void
1273 remove_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.  */
1298 struct loop *
1299 find_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 
1324 void
1325 delete_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 
1339 static void
1340 cancel_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.  */
1358 void
1359 cancel_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   */
1374 DEBUG_FUNCTION void
1375 verify_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.  */
1715 edge
1716 loop_latch_edge (const struct loop *loop)
1717 {
1718   return find_edge (loop->latch, loop->header);
1719 }
1720 
1721 /* Returns preheader edge of LOOP.  */
1722 edge
1723 loop_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 
1746 bool
1747 loop_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 
1757 edge
1758 single_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 
1773 bool
1774 loop_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 
1788 bool
1789 loop_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 
1803 location_t
1804 get_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 
1857 void
1858 record_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 
1908 HOST_WIDE_INT
1909 get_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 
1928 HOST_WIDE_INT
1929 max_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 
1947 HOST_WIDE_INT
1948 likely_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 
1966 bool
1967 get_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 
1990 bool
1991 get_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 
2004 HOST_WIDE_INT
2005 get_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 
2024 bool
2025 get_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 
2038 HOST_WIDE_INT
2039 get_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 
2056 int
2057 bb_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 
2064 void
2065 mark_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