Fix warnings occured during profiledboostrap on
[official-gcc.git] / gcc / cfgloop.c
blobce56b69192aa586a629c2e25203acc2b917ec958
1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "rtl.h"
25 #include "hashtab.h"
26 #include "hash-set.h"
27 #include "vec.h"
28 #include "symtab.h"
29 #include "inchash.h"
30 #include "machmode.h"
31 #include "hard-reg-set.h"
32 #include "input.h"
33 #include "function.h"
34 #include "predict.h"
35 #include "dominance.h"
36 #include "cfg.h"
37 #include "cfganal.h"
38 #include "basic-block.h"
39 #include "cfgloop.h"
40 #include "diagnostic-core.h"
41 #include "flags.h"
42 #include "tree.h"
43 #include "fold-const.h"
44 #include "tree-ssa-alias.h"
45 #include "internal-fn.h"
46 #include "gimple-expr.h"
47 #include "is-a.h"
48 #include "gimple.h"
49 #include "gimple-iterator.h"
50 #include "gimple-ssa.h"
51 #include "dumpfile.h"
53 static void flow_loops_cfg_dump (FILE *);
55 /* Dump loop related CFG information. */
57 static void
58 flow_loops_cfg_dump (FILE *file)
60 basic_block bb;
62 if (!file)
63 return;
65 FOR_EACH_BB_FN (bb, cfun)
67 edge succ;
68 edge_iterator ei;
70 fprintf (file, ";; %d succs { ", bb->index);
71 FOR_EACH_EDGE (succ, ei, bb->succs)
72 fprintf (file, "%d ", succ->dest->index);
73 fprintf (file, "}\n");
77 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
79 bool
80 flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
82 unsigned odepth = loop_depth (outer);
84 return (loop_depth (loop) > odepth
85 && (*loop->superloops)[odepth] == outer);
88 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
89 loops within LOOP. */
91 struct loop *
92 superloop_at_depth (struct loop *loop, unsigned depth)
94 unsigned ldepth = loop_depth (loop);
96 gcc_assert (depth <= ldepth);
98 if (depth == ldepth)
99 return loop;
101 return (*loop->superloops)[depth];
104 /* Returns the list of the latch edges of LOOP. */
106 static vec<edge>
107 get_loop_latch_edges (const struct loop *loop)
109 edge_iterator ei;
110 edge e;
111 vec<edge> ret = vNULL;
113 FOR_EACH_EDGE (e, ei, loop->header->preds)
115 if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header))
116 ret.safe_push (e);
119 return ret;
122 /* Dump the loop information specified by LOOP to the stream FILE
123 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
125 void
126 flow_loop_dump (const struct loop *loop, FILE *file,
127 void (*loop_dump_aux) (const struct loop *, FILE *, int),
128 int verbose)
130 basic_block *bbs;
131 unsigned i;
132 vec<edge> latches;
133 edge e;
135 if (! loop || ! loop->header)
136 return;
138 fprintf (file, ";;\n;; Loop %d\n", loop->num);
140 fprintf (file, ";; header %d, ", loop->header->index);
141 if (loop->latch)
142 fprintf (file, "latch %d\n", loop->latch->index);
143 else
145 fprintf (file, "multiple latches:");
146 latches = get_loop_latch_edges (loop);
147 FOR_EACH_VEC_ELT (latches, i, e)
148 fprintf (file, " %d", e->src->index);
149 latches.release ();
150 fprintf (file, "\n");
153 fprintf (file, ";; depth %d, outer %ld\n",
154 loop_depth (loop), (long) (loop_outer (loop)
155 ? loop_outer (loop)->num : -1));
157 fprintf (file, ";; nodes:");
158 bbs = get_loop_body (loop);
159 for (i = 0; i < loop->num_nodes; i++)
160 fprintf (file, " %d", bbs[i]->index);
161 free (bbs);
162 fprintf (file, "\n");
164 if (loop_dump_aux)
165 loop_dump_aux (loop, file, verbose);
168 /* Dump the loop information about loops to the stream FILE,
169 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
171 void
172 flow_loops_dump (FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
174 struct loop *loop;
176 if (!current_loops || ! file)
177 return;
179 fprintf (file, ";; %d loops found\n", number_of_loops (cfun));
181 FOR_EACH_LOOP (loop, LI_INCLUDE_ROOT)
183 flow_loop_dump (loop, file, loop_dump_aux, verbose);
186 if (verbose)
187 flow_loops_cfg_dump (file);
190 /* Free data allocated for LOOP. */
192 void
193 flow_loop_free (struct loop *loop)
195 struct loop_exit *exit, *next;
197 vec_free (loop->superloops);
199 /* Break the list of the loop exit records. They will be freed when the
200 corresponding edge is rescanned or removed, and this avoids
201 accessing the (already released) head of the list stored in the
202 loop structure. */
203 for (exit = loop->exits->next; exit != loop->exits; exit = next)
205 next = exit->next;
206 exit->next = exit;
207 exit->prev = exit;
210 ggc_free (loop->exits);
211 ggc_free (loop);
214 /* Free all the memory allocated for LOOPS. */
216 void
217 flow_loops_free (struct loops *loops)
219 if (loops->larray)
221 unsigned i;
222 loop_p loop;
224 /* Free the loop descriptors. */
225 FOR_EACH_VEC_SAFE_ELT (loops->larray, i, loop)
227 if (!loop)
228 continue;
230 flow_loop_free (loop);
233 vec_free (loops->larray);
237 /* Find the nodes contained within the LOOP with header HEADER.
238 Return the number of nodes within the loop. */
241 flow_loop_nodes_find (basic_block header, struct loop *loop)
243 vec<basic_block> stack = vNULL;
244 int num_nodes = 1;
245 edge latch;
246 edge_iterator latch_ei;
248 header->loop_father = loop;
250 FOR_EACH_EDGE (latch, latch_ei, loop->header->preds)
252 if (latch->src->loop_father == loop
253 || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header))
254 continue;
256 num_nodes++;
257 stack.safe_push (latch->src);
258 latch->src->loop_father = loop;
260 while (!stack.is_empty ())
262 basic_block node;
263 edge e;
264 edge_iterator ei;
266 node = stack.pop ();
268 FOR_EACH_EDGE (e, ei, node->preds)
270 basic_block ancestor = e->src;
272 if (ancestor->loop_father != loop)
274 ancestor->loop_father = loop;
275 num_nodes++;
276 stack.safe_push (ancestor);
281 stack.release ();
283 return num_nodes;
286 /* Records the vector of superloops of the loop LOOP, whose immediate
287 superloop is FATHER. */
289 static void
290 establish_preds (struct loop *loop, struct loop *father)
292 loop_p ploop;
293 unsigned depth = loop_depth (father) + 1;
294 unsigned i;
296 loop->superloops = 0;
297 vec_alloc (loop->superloops, depth);
298 FOR_EACH_VEC_SAFE_ELT (father->superloops, i, ploop)
299 loop->superloops->quick_push (ploop);
300 loop->superloops->quick_push (father);
302 for (ploop = loop->inner; ploop; ploop = ploop->next)
303 establish_preds (ploop, loop);
306 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
307 added loop. If LOOP has some children, take care of that their
308 pred field will be initialized correctly. */
310 void
311 flow_loop_tree_node_add (struct loop *father, struct loop *loop)
313 loop->next = father->inner;
314 father->inner = loop;
316 establish_preds (loop, father);
319 /* Remove LOOP from the loop hierarchy tree. */
321 void
322 flow_loop_tree_node_remove (struct loop *loop)
324 struct loop *prev, *father;
326 father = loop_outer (loop);
328 /* Remove loop from the list of sons. */
329 if (father->inner == loop)
330 father->inner = loop->next;
331 else
333 for (prev = father->inner; prev->next != loop; prev = prev->next)
334 continue;
335 prev->next = loop->next;
338 loop->superloops = NULL;
341 /* Allocates and returns new loop structure. */
343 struct loop *
344 alloc_loop (void)
346 struct loop *loop = ggc_cleared_alloc<struct loop> ();
348 loop->exits = ggc_cleared_alloc<loop_exit> ();
349 loop->exits->next = loop->exits->prev = loop->exits;
350 loop->can_be_parallel = false;
351 loop->nb_iterations_upper_bound = 0;
352 loop->nb_iterations_estimate = 0;
353 return loop;
356 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
357 (including the root of the loop tree). */
359 void
360 init_loops_structure (struct function *fn,
361 struct loops *loops, unsigned num_loops)
363 struct loop *root;
365 memset (loops, 0, sizeof *loops);
366 vec_alloc (loops->larray, num_loops);
368 /* Dummy loop containing whole function. */
369 root = alloc_loop ();
370 root->num_nodes = n_basic_blocks_for_fn (fn);
371 root->latch = EXIT_BLOCK_PTR_FOR_FN (fn);
372 root->header = ENTRY_BLOCK_PTR_FOR_FN (fn);
373 ENTRY_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
374 EXIT_BLOCK_PTR_FOR_FN (fn)->loop_father = root;
376 loops->larray->quick_push (root);
377 loops->tree_root = root;
380 /* Returns whether HEADER is a loop header. */
382 bool
383 bb_loop_header_p (basic_block header)
385 edge_iterator ei;
386 edge e;
388 /* If we have an abnormal predecessor, do not consider the
389 loop (not worth the problems). */
390 if (bb_has_abnormal_pred (header))
391 return false;
393 /* Look for back edges where a predecessor is dominated
394 by this block. A natural loop has a single entry
395 node (header) that dominates all the nodes in the
396 loop. It also has single back edge to the header
397 from a latch node. */
398 FOR_EACH_EDGE (e, ei, header->preds)
400 basic_block latch = e->src;
401 if (latch != ENTRY_BLOCK_PTR_FOR_FN (cfun)
402 && dominated_by_p (CDI_DOMINATORS, latch, header))
403 return true;
406 return false;
409 /* Find all the natural loops in the function and save in LOOPS structure and
410 recalculate loop_father information in basic block structures.
411 If LOOPS is non-NULL then the loop structures for already recorded loops
412 will be re-used and their number will not change. We assume that no
413 stale loops exist in LOOPS.
414 When LOOPS is NULL it is allocated and re-built from scratch.
415 Return the built LOOPS structure. */
417 struct loops *
418 flow_loops_find (struct loops *loops)
420 bool from_scratch = (loops == NULL);
421 int *rc_order;
422 int b;
423 unsigned i;
425 /* Ensure that the dominators are computed. */
426 calculate_dominance_info (CDI_DOMINATORS);
428 if (!loops)
430 loops = ggc_cleared_alloc<struct loops> ();
431 init_loops_structure (cfun, loops, 1);
434 /* Ensure that loop exits were released. */
435 gcc_assert (loops->exits == NULL);
437 /* Taking care of this degenerate case makes the rest of
438 this code simpler. */
439 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
440 return loops;
442 /* The root loop node contains all basic-blocks. */
443 loops->tree_root->num_nodes = n_basic_blocks_for_fn (cfun);
445 /* Compute depth first search order of the CFG so that outer
446 natural loops will be found before inner natural loops. */
447 rc_order = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
448 pre_and_rev_post_order_compute (NULL, rc_order, false);
450 /* Gather all loop headers in reverse completion order and allocate
451 loop structures for loops that are not already present. */
452 auto_vec<loop_p> larray (loops->larray->length ());
453 for (b = 0; b < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; b++)
455 basic_block header = BASIC_BLOCK_FOR_FN (cfun, rc_order[b]);
456 if (bb_loop_header_p (header))
458 struct loop *loop;
460 /* The current active loop tree has valid loop-fathers for
461 header blocks. */
462 if (!from_scratch
463 && header->loop_father->header == header)
465 loop = header->loop_father;
466 /* If we found an existing loop remove it from the
467 loop tree. It is going to be inserted again
468 below. */
469 flow_loop_tree_node_remove (loop);
471 else
473 /* Otherwise allocate a new loop structure for the loop. */
474 loop = alloc_loop ();
475 /* ??? We could re-use unused loop slots here. */
476 loop->num = loops->larray->length ();
477 vec_safe_push (loops->larray, loop);
478 loop->header = header;
480 if (!from_scratch
481 && dump_file && (dump_flags & TDF_DETAILS))
482 fprintf (dump_file, "flow_loops_find: discovered new "
483 "loop %d with header %d\n",
484 loop->num, header->index);
486 /* Reset latch, we recompute it below. */
487 loop->latch = NULL;
488 larray.safe_push (loop);
491 /* Make blocks part of the loop root node at start. */
492 header->loop_father = loops->tree_root;
495 free (rc_order);
497 /* Now iterate over the loops found, insert them into the loop tree
498 and assign basic-block ownership. */
499 for (i = 0; i < larray.length (); ++i)
501 struct loop *loop = larray[i];
502 basic_block header = loop->header;
503 edge_iterator ei;
504 edge e;
506 flow_loop_tree_node_add (header->loop_father, loop);
507 loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
509 /* Look for the latch for this header block, if it has just a
510 single one. */
511 FOR_EACH_EDGE (e, ei, header->preds)
513 basic_block latch = e->src;
515 if (flow_bb_inside_loop_p (loop, latch))
517 if (loop->latch != NULL)
519 /* More than one latch edge. */
520 loop->latch = NULL;
521 break;
523 loop->latch = latch;
528 return loops;
531 /* Ratio of frequencies of edges so that one of more latch edges is
532 considered to belong to inner loop with same header. */
533 #define HEAVY_EDGE_RATIO 8
535 /* Minimum number of samples for that we apply
536 find_subloop_latch_edge_by_profile heuristics. */
537 #define HEAVY_EDGE_MIN_SAMPLES 10
539 /* If the profile info is available, finds an edge in LATCHES that much more
540 frequent than the remaining edges. Returns such an edge, or NULL if we do
541 not find one.
543 We do not use guessed profile here, only the measured one. The guessed
544 profile is usually too flat and unreliable for this (and it is mostly based
545 on the loop structure of the program, so it does not make much sense to
546 derive the loop structure from it). */
548 static edge
549 find_subloop_latch_edge_by_profile (vec<edge> latches)
551 unsigned i;
552 edge e, me = NULL;
553 gcov_type mcount = 0, tcount = 0;
555 FOR_EACH_VEC_ELT (latches, i, e)
557 if (e->count > mcount)
559 me = e;
560 mcount = e->count;
562 tcount += e->count;
565 if (tcount < HEAVY_EDGE_MIN_SAMPLES
566 || (tcount - mcount) * HEAVY_EDGE_RATIO > tcount)
567 return NULL;
569 if (dump_file)
570 fprintf (dump_file,
571 "Found latch edge %d -> %d using profile information.\n",
572 me->src->index, me->dest->index);
573 return me;
576 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
577 on the structure of induction variables. Returns this edge, or NULL if we
578 do not find any.
580 We are quite conservative, and look just for an obvious simple innermost
581 loop (which is the case where we would lose the most performance by not
582 disambiguating the loop). More precisely, we look for the following
583 situation: The source of the chosen latch edge dominates sources of all
584 the other latch edges. Additionally, the header does not contain a phi node
585 such that the argument from the chosen edge is equal to the argument from
586 another edge. */
588 static edge
589 find_subloop_latch_edge_by_ivs (struct loop *loop ATTRIBUTE_UNUSED, vec<edge> latches)
591 edge e, latch = latches[0];
592 unsigned i;
593 gphi *phi;
594 gphi_iterator psi;
595 tree lop;
596 basic_block bb;
598 /* Find the candidate for the latch edge. */
599 for (i = 1; latches.iterate (i, &e); i++)
600 if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src))
601 latch = e;
603 /* Verify that it dominates all the latch edges. */
604 FOR_EACH_VEC_ELT (latches, i, e)
605 if (!dominated_by_p (CDI_DOMINATORS, e->src, latch->src))
606 return NULL;
608 /* Check for a phi node that would deny that this is a latch edge of
609 a subloop. */
610 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
612 phi = psi.phi ();
613 lop = PHI_ARG_DEF_FROM_EDGE (phi, latch);
615 /* Ignore the values that are not changed inside the subloop. */
616 if (TREE_CODE (lop) != SSA_NAME
617 || SSA_NAME_DEF_STMT (lop) == phi)
618 continue;
619 bb = gimple_bb (SSA_NAME_DEF_STMT (lop));
620 if (!bb || !flow_bb_inside_loop_p (loop, bb))
621 continue;
623 FOR_EACH_VEC_ELT (latches, i, e)
624 if (e != latch
625 && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop)
626 return NULL;
629 if (dump_file)
630 fprintf (dump_file,
631 "Found latch edge %d -> %d using iv structure.\n",
632 latch->src->index, latch->dest->index);
633 return latch;
636 /* If we can determine that one of the several latch edges of LOOP behaves
637 as a latch edge of a separate subloop, returns this edge. Otherwise
638 returns NULL. */
640 static edge
641 find_subloop_latch_edge (struct loop *loop)
643 vec<edge> latches = get_loop_latch_edges (loop);
644 edge latch = NULL;
646 if (latches.length () > 1)
648 latch = find_subloop_latch_edge_by_profile (latches);
650 if (!latch
651 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
652 should use cfghook for this, but it is hard to imagine it would
653 be useful elsewhere. */
654 && current_ir_type () == IR_GIMPLE)
655 latch = find_subloop_latch_edge_by_ivs (loop, latches);
658 latches.release ();
659 return latch;
662 /* Callback for make_forwarder_block. Returns true if the edge E is marked
663 in the set MFB_REIS_SET. */
665 static hash_set<edge> *mfb_reis_set;
666 static bool
667 mfb_redirect_edges_in_set (edge e)
669 return mfb_reis_set->contains (e);
672 /* Creates a subloop of LOOP with latch edge LATCH. */
674 static void
675 form_subloop (struct loop *loop, edge latch)
677 edge_iterator ei;
678 edge e, new_entry;
679 struct loop *new_loop;
681 mfb_reis_set = new hash_set<edge>;
682 FOR_EACH_EDGE (e, ei, loop->header->preds)
684 if (e != latch)
685 mfb_reis_set->add (e);
687 new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
688 NULL);
689 delete mfb_reis_set;
691 loop->header = new_entry->src;
693 /* Find the blocks and subloops that belong to the new loop, and add it to
694 the appropriate place in the loop tree. */
695 new_loop = alloc_loop ();
696 new_loop->header = new_entry->dest;
697 new_loop->latch = latch->src;
698 add_loop (new_loop, loop);
701 /* Make all the latch edges of LOOP to go to a single forwarder block --
702 a new latch of LOOP. */
704 static void
705 merge_latch_edges (struct loop *loop)
707 vec<edge> latches = get_loop_latch_edges (loop);
708 edge latch, e;
709 unsigned i;
711 gcc_assert (latches.length () > 0);
713 if (latches.length () == 1)
714 loop->latch = latches[0]->src;
715 else
717 if (dump_file)
718 fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num);
720 mfb_reis_set = new hash_set<edge>;
721 FOR_EACH_VEC_ELT (latches, i, e)
722 mfb_reis_set->add (e);
723 latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
724 NULL);
725 delete mfb_reis_set;
727 loop->header = latch->dest;
728 loop->latch = latch->src;
731 latches.release ();
734 /* LOOP may have several latch edges. Transform it into (possibly several)
735 loops with single latch edge. */
737 static void
738 disambiguate_multiple_latches (struct loop *loop)
740 edge e;
742 /* We eliminate the multiple latches by splitting the header to the forwarder
743 block F and the rest R, and redirecting the edges. There are two cases:
745 1) If there is a latch edge E that corresponds to a subloop (we guess
746 that based on profile -- if it is taken much more often than the
747 remaining edges; and on trees, using the information about induction
748 variables of the loops), we redirect E to R, all the remaining edges to
749 F, then rescan the loops and try again for the outer loop.
750 2) If there is no such edge, we redirect all latch edges to F, and the
751 entry edges to R, thus making F the single latch of the loop. */
753 if (dump_file)
754 fprintf (dump_file, "Disambiguating loop %d with multiple latches\n",
755 loop->num);
757 /* During latch merging, we may need to redirect the entry edges to a new
758 block. This would cause problems if the entry edge was the one from the
759 entry block. To avoid having to handle this case specially, split
760 such entry edge. */
761 e = find_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), loop->header);
762 if (e)
763 split_edge (e);
765 while (1)
767 e = find_subloop_latch_edge (loop);
768 if (!e)
769 break;
771 form_subloop (loop, e);
774 merge_latch_edges (loop);
777 /* Split loops with multiple latch edges. */
779 void
780 disambiguate_loops_with_multiple_latches (void)
782 struct loop *loop;
784 FOR_EACH_LOOP (loop, 0)
786 if (!loop->latch)
787 disambiguate_multiple_latches (loop);
791 /* Return nonzero if basic block BB belongs to LOOP. */
792 bool
793 flow_bb_inside_loop_p (const struct loop *loop, const_basic_block bb)
795 struct loop *source_loop;
797 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
798 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
799 return 0;
801 source_loop = bb->loop_father;
802 return loop == source_loop || flow_loop_nested_p (loop, source_loop);
805 /* Enumeration predicate for get_loop_body_with_size. */
806 static bool
807 glb_enum_p (const_basic_block bb, const void *glb_loop)
809 const struct loop *const loop = (const struct loop *) glb_loop;
810 return (bb != loop->header
811 && dominated_by_p (CDI_DOMINATORS, bb, loop->header));
814 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
815 order against direction of edges from latch. Specially, if
816 header != latch, latch is the 1-st block. LOOP cannot be the fake
817 loop tree root, and its size must be at most MAX_SIZE. The blocks
818 in the LOOP body are stored to BODY, and the size of the LOOP is
819 returned. */
821 unsigned
822 get_loop_body_with_size (const struct loop *loop, basic_block *body,
823 unsigned max_size)
825 return dfs_enumerate_from (loop->header, 1, glb_enum_p,
826 body, max_size, loop);
829 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
830 order against direction of edges from latch. Specially, if
831 header != latch, latch is the 1-st block. */
833 basic_block *
834 get_loop_body (const struct loop *loop)
836 basic_block *body, bb;
837 unsigned tv = 0;
839 gcc_assert (loop->num_nodes);
841 body = XNEWVEC (basic_block, loop->num_nodes);
843 if (loop->latch == EXIT_BLOCK_PTR_FOR_FN (cfun))
845 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
846 special-case the fake loop that contains the whole function. */
847 gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks_for_fn (cfun));
848 body[tv++] = loop->header;
849 body[tv++] = EXIT_BLOCK_PTR_FOR_FN (cfun);
850 FOR_EACH_BB_FN (bb, cfun)
851 body[tv++] = bb;
853 else
854 tv = get_loop_body_with_size (loop, body, loop->num_nodes);
856 gcc_assert (tv == loop->num_nodes);
857 return body;
860 /* Fills dominance descendants inside LOOP of the basic block BB into
861 array TOVISIT from index *TV. */
863 static void
864 fill_sons_in_loop (const struct loop *loop, basic_block bb,
865 basic_block *tovisit, int *tv)
867 basic_block son, postpone = NULL;
869 tovisit[(*tv)++] = bb;
870 for (son = first_dom_son (CDI_DOMINATORS, bb);
871 son;
872 son = next_dom_son (CDI_DOMINATORS, son))
874 if (!flow_bb_inside_loop_p (loop, son))
875 continue;
877 if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
879 postpone = son;
880 continue;
882 fill_sons_in_loop (loop, son, tovisit, tv);
885 if (postpone)
886 fill_sons_in_loop (loop, postpone, tovisit, tv);
889 /* Gets body of a LOOP (that must be different from the outermost loop)
890 sorted by dominance relation. Additionally, if a basic block s dominates
891 the latch, then only blocks dominated by s are be after it. */
893 basic_block *
894 get_loop_body_in_dom_order (const struct loop *loop)
896 basic_block *tovisit;
897 int tv;
899 gcc_assert (loop->num_nodes);
901 tovisit = XNEWVEC (basic_block, loop->num_nodes);
903 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
905 tv = 0;
906 fill_sons_in_loop (loop, loop->header, tovisit, &tv);
908 gcc_assert (tv == (int) loop->num_nodes);
910 return tovisit;
913 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
915 basic_block *
916 get_loop_body_in_custom_order (const struct loop *loop,
917 int (*bb_comparator) (const void *, const void *))
919 basic_block *bbs = get_loop_body (loop);
921 qsort (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator);
923 return bbs;
926 /* Get body of a LOOP in breadth first sort order. */
928 basic_block *
929 get_loop_body_in_bfs_order (const struct loop *loop)
931 basic_block *blocks;
932 basic_block bb;
933 bitmap visited;
934 unsigned int i = 0;
935 unsigned int vc = 1;
937 gcc_assert (loop->num_nodes);
938 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
940 blocks = XNEWVEC (basic_block, loop->num_nodes);
941 visited = BITMAP_ALLOC (NULL);
943 bb = loop->header;
944 while (i < loop->num_nodes)
946 edge e;
947 edge_iterator ei;
949 if (bitmap_set_bit (visited, bb->index))
950 /* This basic block is now visited */
951 blocks[i++] = bb;
953 FOR_EACH_EDGE (e, ei, bb->succs)
955 if (flow_bb_inside_loop_p (loop, e->dest))
957 if (bitmap_set_bit (visited, e->dest->index))
958 blocks[i++] = e->dest;
962 gcc_assert (i >= vc);
964 bb = blocks[vc++];
967 BITMAP_FREE (visited);
968 return blocks;
971 /* Hash function for struct loop_exit. */
973 hashval_t
974 loop_exit_hasher::hash (loop_exit *exit)
976 return htab_hash_pointer (exit->e);
979 /* Equality function for struct loop_exit. Compares with edge. */
981 bool
982 loop_exit_hasher::equal (loop_exit *exit, edge e)
984 return exit->e == e;
987 /* Frees the list of loop exit descriptions EX. */
989 void
990 loop_exit_hasher::remove (loop_exit *exit)
992 loop_exit *next;
993 for (; exit; exit = next)
995 next = exit->next_e;
997 exit->next->prev = exit->prev;
998 exit->prev->next = exit->next;
1000 ggc_free (exit);
1004 /* Returns the list of records for E as an exit of a loop. */
1006 static struct loop_exit *
1007 get_exit_descriptions (edge e)
1009 return current_loops->exits->find_with_hash (e, htab_hash_pointer (e));
1012 /* Updates the lists of loop exits in that E appears.
1013 If REMOVED is true, E is being removed, and we
1014 just remove it from the lists of exits.
1015 If NEW_EDGE is true and E is not a loop exit, we
1016 do not try to remove it from loop exit lists. */
1018 void
1019 rescan_loop_exit (edge e, bool new_edge, bool removed)
1021 struct loop_exit *exits = NULL, *exit;
1022 struct loop *aloop, *cloop;
1024 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1025 return;
1027 if (!removed
1028 && e->src->loop_father != NULL
1029 && e->dest->loop_father != NULL
1030 && !flow_bb_inside_loop_p (e->src->loop_father, e->dest))
1032 cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
1033 for (aloop = e->src->loop_father;
1034 aloop != cloop;
1035 aloop = loop_outer (aloop))
1037 exit = ggc_alloc<loop_exit> ();
1038 exit->e = e;
1040 exit->next = aloop->exits->next;
1041 exit->prev = aloop->exits;
1042 exit->next->prev = exit;
1043 exit->prev->next = exit;
1045 exit->next_e = exits;
1046 exits = exit;
1050 if (!exits && new_edge)
1051 return;
1053 loop_exit **slot
1054 = current_loops->exits->find_slot_with_hash (e, htab_hash_pointer (e),
1055 exits ? INSERT : NO_INSERT);
1056 if (!slot)
1057 return;
1059 if (exits)
1061 if (*slot)
1062 loop_exit_hasher::remove (*slot);
1063 *slot = exits;
1065 else
1066 current_loops->exits->clear_slot (slot);
1069 /* For each loop, record list of exit edges, and start maintaining these
1070 lists. */
1072 void
1073 record_loop_exits (void)
1075 basic_block bb;
1076 edge_iterator ei;
1077 edge e;
1079 if (!current_loops)
1080 return;
1082 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1083 return;
1084 loops_state_set (LOOPS_HAVE_RECORDED_EXITS);
1086 gcc_assert (current_loops->exits == NULL);
1087 current_loops->exits
1088 = hash_table<loop_exit_hasher>::create_ggc (2 * number_of_loops (cfun));
1090 FOR_EACH_BB_FN (bb, cfun)
1092 FOR_EACH_EDGE (e, ei, bb->succs)
1094 rescan_loop_exit (e, true, false);
1099 /* Dumps information about the exit in *SLOT to FILE.
1100 Callback for htab_traverse. */
1103 dump_recorded_exit (loop_exit **slot, FILE *file)
1105 struct loop_exit *exit = *slot;
1106 unsigned n = 0;
1107 edge e = exit->e;
1109 for (; exit != NULL; exit = exit->next_e)
1110 n++;
1112 fprintf (file, "Edge %d->%d exits %u loops\n",
1113 e->src->index, e->dest->index, n);
1115 return 1;
1118 /* Dumps the recorded exits of loops to FILE. */
1120 extern void dump_recorded_exits (FILE *);
1121 void
1122 dump_recorded_exits (FILE *file)
1124 if (!current_loops->exits)
1125 return;
1126 current_loops->exits->traverse<FILE *, dump_recorded_exit> (file);
1129 /* Releases lists of loop exits. */
1131 void
1132 release_recorded_exits (void)
1134 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS));
1135 current_loops->exits->empty ();
1136 current_loops->exits = NULL;
1137 loops_state_clear (LOOPS_HAVE_RECORDED_EXITS);
1140 /* Returns the list of the exit edges of a LOOP. */
1142 vec<edge>
1143 get_loop_exit_edges (const struct loop *loop)
1145 vec<edge> edges = vNULL;
1146 edge e;
1147 unsigned i;
1148 basic_block *body;
1149 edge_iterator ei;
1150 struct loop_exit *exit;
1152 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1154 /* If we maintain the lists of exits, use them. Otherwise we must
1155 scan the body of the loop. */
1156 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1158 for (exit = loop->exits->next; exit->e; exit = exit->next)
1159 edges.safe_push (exit->e);
1161 else
1163 body = get_loop_body (loop);
1164 for (i = 0; i < loop->num_nodes; i++)
1165 FOR_EACH_EDGE (e, ei, body[i]->succs)
1167 if (!flow_bb_inside_loop_p (loop, e->dest))
1168 edges.safe_push (e);
1170 free (body);
1173 return edges;
1176 /* Counts the number of conditional branches inside LOOP. */
1178 unsigned
1179 num_loop_branches (const struct loop *loop)
1181 unsigned i, n;
1182 basic_block * body;
1184 gcc_assert (loop->latch != EXIT_BLOCK_PTR_FOR_FN (cfun));
1186 body = get_loop_body (loop);
1187 n = 0;
1188 for (i = 0; i < loop->num_nodes; i++)
1189 if (EDGE_COUNT (body[i]->succs) >= 2)
1190 n++;
1191 free (body);
1193 return n;
1196 /* Adds basic block BB to LOOP. */
1197 void
1198 add_bb_to_loop (basic_block bb, struct loop *loop)
1200 unsigned i;
1201 loop_p ploop;
1202 edge_iterator ei;
1203 edge e;
1205 gcc_assert (bb->loop_father == NULL);
1206 bb->loop_father = loop;
1207 loop->num_nodes++;
1208 FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
1209 ploop->num_nodes++;
1211 FOR_EACH_EDGE (e, ei, bb->succs)
1213 rescan_loop_exit (e, true, false);
1215 FOR_EACH_EDGE (e, ei, bb->preds)
1217 rescan_loop_exit (e, true, false);
1221 /* Remove basic block BB from loops. */
1222 void
1223 remove_bb_from_loops (basic_block bb)
1225 unsigned i;
1226 struct loop *loop = bb->loop_father;
1227 loop_p ploop;
1228 edge_iterator ei;
1229 edge e;
1231 gcc_assert (loop != NULL);
1232 loop->num_nodes--;
1233 FOR_EACH_VEC_SAFE_ELT (loop->superloops, i, ploop)
1234 ploop->num_nodes--;
1235 bb->loop_father = NULL;
1237 FOR_EACH_EDGE (e, ei, bb->succs)
1239 rescan_loop_exit (e, false, true);
1241 FOR_EACH_EDGE (e, ei, bb->preds)
1243 rescan_loop_exit (e, false, true);
1247 /* Finds nearest common ancestor in loop tree for given loops. */
1248 struct loop *
1249 find_common_loop (struct loop *loop_s, struct loop *loop_d)
1251 unsigned sdepth, ddepth;
1253 if (!loop_s) return loop_d;
1254 if (!loop_d) return loop_s;
1256 sdepth = loop_depth (loop_s);
1257 ddepth = loop_depth (loop_d);
1259 if (sdepth < ddepth)
1260 loop_d = (*loop_d->superloops)[sdepth];
1261 else if (sdepth > ddepth)
1262 loop_s = (*loop_s->superloops)[ddepth];
1264 while (loop_s != loop_d)
1266 loop_s = loop_outer (loop_s);
1267 loop_d = loop_outer (loop_d);
1269 return loop_s;
1272 /* Removes LOOP from structures and frees its data. */
1274 void
1275 delete_loop (struct loop *loop)
1277 /* Remove the loop from structure. */
1278 flow_loop_tree_node_remove (loop);
1280 /* Remove loop from loops array. */
1281 (*current_loops->larray)[loop->num] = NULL;
1283 /* Free loop data. */
1284 flow_loop_free (loop);
1287 /* Cancels the LOOP; it must be innermost one. */
1289 static void
1290 cancel_loop (struct loop *loop)
1292 basic_block *bbs;
1293 unsigned i;
1294 struct loop *outer = loop_outer (loop);
1296 gcc_assert (!loop->inner);
1298 /* Move blocks up one level (they should be removed as soon as possible). */
1299 bbs = get_loop_body (loop);
1300 for (i = 0; i < loop->num_nodes; i++)
1301 bbs[i]->loop_father = outer;
1303 free (bbs);
1304 delete_loop (loop);
1307 /* Cancels LOOP and all its subloops. */
1308 void
1309 cancel_loop_tree (struct loop *loop)
1311 while (loop->inner)
1312 cancel_loop_tree (loop->inner);
1313 cancel_loop (loop);
1316 /* Checks that information about loops is correct
1317 -- sizes of loops are all right
1318 -- results of get_loop_body really belong to the loop
1319 -- loop header have just single entry edge and single latch edge
1320 -- loop latches have only single successor that is header of their loop
1321 -- irreducible loops are correctly marked
1322 -- the cached loop depth and loop father of each bb is correct
1324 DEBUG_FUNCTION void
1325 verify_loop_structure (void)
1327 unsigned *sizes, i, j;
1328 sbitmap irreds;
1329 basic_block bb, *bbs;
1330 struct loop *loop;
1331 int err = 0;
1332 edge e;
1333 unsigned num = number_of_loops (cfun);
1334 struct loop_exit *exit, *mexit;
1335 bool dom_available = dom_info_available_p (CDI_DOMINATORS);
1336 sbitmap visited;
1338 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP))
1340 error ("loop verification on loop tree that needs fixup");
1341 err = 1;
1344 /* We need up-to-date dominators, compute or verify them. */
1345 if (!dom_available)
1346 calculate_dominance_info (CDI_DOMINATORS);
1347 else
1348 verify_dominators (CDI_DOMINATORS);
1350 /* Check the headers. */
1351 FOR_EACH_BB_FN (bb, cfun)
1352 if (bb_loop_header_p (bb))
1354 if (bb->loop_father->header == NULL)
1356 error ("loop with header %d marked for removal", bb->index);
1357 err = 1;
1359 else if (bb->loop_father->header != bb)
1361 error ("loop with header %d not in loop tree", bb->index);
1362 err = 1;
1365 else if (bb->loop_father->header == bb)
1367 error ("non-loop with header %d not marked for removal", bb->index);
1368 err = 1;
1371 /* Check the recorded loop father and sizes of loops. */
1372 visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
1373 bitmap_clear (visited);
1374 bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
1375 FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
1377 unsigned n;
1379 if (loop->header == NULL)
1381 error ("removed loop %d in loop tree", loop->num);
1382 err = 1;
1383 continue;
1386 n = get_loop_body_with_size (loop, bbs, n_basic_blocks_for_fn (cfun));
1387 if (loop->num_nodes != n)
1389 error ("size of loop %d should be %d, not %d",
1390 loop->num, n, loop->num_nodes);
1391 err = 1;
1394 for (j = 0; j < n; j++)
1396 bb = bbs[j];
1398 if (!flow_bb_inside_loop_p (loop, bb))
1400 error ("bb %d does not belong to loop %d",
1401 bb->index, loop->num);
1402 err = 1;
1405 /* Ignore this block if it is in an inner loop. */
1406 if (bitmap_bit_p (visited, bb->index))
1407 continue;
1408 bitmap_set_bit (visited, bb->index);
1410 if (bb->loop_father != loop)
1412 error ("bb %d has father loop %d, should be loop %d",
1413 bb->index, bb->loop_father->num, loop->num);
1414 err = 1;
1418 free (bbs);
1419 sbitmap_free (visited);
1421 /* Check headers and latches. */
1422 FOR_EACH_LOOP (loop, 0)
1424 i = loop->num;
1425 if (loop->header == NULL)
1426 continue;
1427 if (!bb_loop_header_p (loop->header))
1429 error ("loop %d%'s header is not a loop header", i);
1430 err = 1;
1432 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
1433 && EDGE_COUNT (loop->header->preds) != 2)
1435 error ("loop %d%'s header does not have exactly 2 entries", i);
1436 err = 1;
1438 if (loop->latch)
1440 if (!find_edge (loop->latch, loop->header))
1442 error ("loop %d%'s latch does not have an edge to its header", i);
1443 err = 1;
1445 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, loop->header))
1447 error ("loop %d%'s latch is not dominated by its header", i);
1448 err = 1;
1451 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
1453 if (!single_succ_p (loop->latch))
1455 error ("loop %d%'s latch does not have exactly 1 successor", i);
1456 err = 1;
1458 if (single_succ (loop->latch) != loop->header)
1460 error ("loop %d%'s latch does not have header as successor", i);
1461 err = 1;
1463 if (loop->latch->loop_father != loop)
1465 error ("loop %d%'s latch does not belong directly to it", i);
1466 err = 1;
1469 if (loop->header->loop_father != loop)
1471 error ("loop %d%'s header does not belong directly to it", i);
1472 err = 1;
1474 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1475 && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
1477 error ("loop %d%'s latch is marked as part of irreducible region", i);
1478 err = 1;
1482 /* Check irreducible loops. */
1483 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1485 /* Record old info. */
1486 irreds = sbitmap_alloc (last_basic_block_for_fn (cfun));
1487 FOR_EACH_BB_FN (bb, cfun)
1489 edge_iterator ei;
1490 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1491 bitmap_set_bit (irreds, bb->index);
1492 else
1493 bitmap_clear_bit (irreds, bb->index);
1494 FOR_EACH_EDGE (e, ei, bb->succs)
1495 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1496 e->flags |= EDGE_ALL_FLAGS + 1;
1499 /* Recount it. */
1500 mark_irreducible_loops ();
1502 /* Compare. */
1503 FOR_EACH_BB_FN (bb, cfun)
1505 edge_iterator ei;
1507 if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1508 && !bitmap_bit_p (irreds, bb->index))
1510 error ("basic block %d should be marked irreducible", bb->index);
1511 err = 1;
1513 else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1514 && bitmap_bit_p (irreds, bb->index))
1516 error ("basic block %d should not be marked irreducible", bb->index);
1517 err = 1;
1519 FOR_EACH_EDGE (e, ei, bb->succs)
1521 if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1522 && !(e->flags & (EDGE_ALL_FLAGS + 1)))
1524 error ("edge from %d to %d should be marked irreducible",
1525 e->src->index, e->dest->index);
1526 err = 1;
1528 else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1529 && (e->flags & (EDGE_ALL_FLAGS + 1)))
1531 error ("edge from %d to %d should not be marked irreducible",
1532 e->src->index, e->dest->index);
1533 err = 1;
1535 e->flags &= ~(EDGE_ALL_FLAGS + 1);
1538 free (irreds);
1541 /* Check the recorded loop exits. */
1542 FOR_EACH_LOOP (loop, 0)
1544 if (!loop->exits || loop->exits->e != NULL)
1546 error ("corrupted head of the exits list of loop %d",
1547 loop->num);
1548 err = 1;
1550 else
1552 /* Check that the list forms a cycle, and all elements except
1553 for the head are nonnull. */
1554 for (mexit = loop->exits, exit = mexit->next, i = 0;
1555 exit->e && exit != mexit;
1556 exit = exit->next)
1558 if (i++ & 1)
1559 mexit = mexit->next;
1562 if (exit != loop->exits)
1564 error ("corrupted exits list of loop %d", loop->num);
1565 err = 1;
1569 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1571 if (loop->exits->next != loop->exits)
1573 error ("nonempty exits list of loop %d, but exits are not recorded",
1574 loop->num);
1575 err = 1;
1580 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1582 unsigned n_exits = 0, eloops;
1584 sizes = XCNEWVEC (unsigned, num);
1585 memset (sizes, 0, sizeof (unsigned) * num);
1586 FOR_EACH_BB_FN (bb, cfun)
1588 edge_iterator ei;
1589 if (bb->loop_father == current_loops->tree_root)
1590 continue;
1591 FOR_EACH_EDGE (e, ei, bb->succs)
1593 if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
1594 continue;
1596 n_exits++;
1597 exit = get_exit_descriptions (e);
1598 if (!exit)
1600 error ("exit %d->%d not recorded",
1601 e->src->index, e->dest->index);
1602 err = 1;
1604 eloops = 0;
1605 for (; exit; exit = exit->next_e)
1606 eloops++;
1608 for (loop = bb->loop_father;
1609 loop != e->dest->loop_father
1610 /* When a loop exit is also an entry edge which
1611 can happen when avoiding CFG manipulations
1612 then the last loop exited is the outer loop
1613 of the loop entered. */
1614 && loop != loop_outer (e->dest->loop_father);
1615 loop = loop_outer (loop))
1617 eloops--;
1618 sizes[loop->num]++;
1621 if (eloops != 0)
1623 error ("wrong list of exited loops for edge %d->%d",
1624 e->src->index, e->dest->index);
1625 err = 1;
1630 if (n_exits != current_loops->exits->elements ())
1632 error ("too many loop exits recorded");
1633 err = 1;
1636 FOR_EACH_LOOP (loop, 0)
1638 eloops = 0;
1639 for (exit = loop->exits->next; exit->e; exit = exit->next)
1640 eloops++;
1641 if (eloops != sizes[loop->num])
1643 error ("%d exits recorded for loop %d (having %d exits)",
1644 eloops, loop->num, sizes[loop->num]);
1645 err = 1;
1649 free (sizes);
1652 gcc_assert (!err);
1654 if (!dom_available)
1655 free_dominance_info (CDI_DOMINATORS);
1658 /* Returns latch edge of LOOP. */
1659 edge
1660 loop_latch_edge (const struct loop *loop)
1662 return find_edge (loop->latch, loop->header);
1665 /* Returns preheader edge of LOOP. */
1666 edge
1667 loop_preheader_edge (const struct loop *loop)
1669 edge e;
1670 edge_iterator ei;
1672 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS));
1674 FOR_EACH_EDGE (e, ei, loop->header->preds)
1675 if (e->src != loop->latch)
1676 break;
1678 return e;
1681 /* Returns true if E is an exit of LOOP. */
1683 bool
1684 loop_exit_edge_p (const struct loop *loop, const_edge e)
1686 return (flow_bb_inside_loop_p (loop, e->src)
1687 && !flow_bb_inside_loop_p (loop, e->dest));
1690 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1691 or more than one exit. If loops do not have the exits recorded, NULL
1692 is returned always. */
1694 edge
1695 single_exit (const struct loop *loop)
1697 struct loop_exit *exit = loop->exits->next;
1699 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1700 return NULL;
1702 if (exit->e && exit->next == loop->exits)
1703 return exit->e;
1704 else
1705 return NULL;
1708 /* Returns true when BB has an incoming edge exiting LOOP. */
1710 bool
1711 loop_exits_to_bb_p (struct loop *loop, basic_block bb)
1713 edge e;
1714 edge_iterator ei;
1716 FOR_EACH_EDGE (e, ei, bb->preds)
1717 if (loop_exit_edge_p (loop, e))
1718 return true;
1720 return false;
1723 /* Returns true when BB has an outgoing edge exiting LOOP. */
1725 bool
1726 loop_exits_from_bb_p (struct loop *loop, basic_block bb)
1728 edge e;
1729 edge_iterator ei;
1731 FOR_EACH_EDGE (e, ei, bb->succs)
1732 if (loop_exit_edge_p (loop, e))
1733 return true;
1735 return false;
1738 /* Return location corresponding to the loop control condition if possible. */
1740 location_t
1741 get_loop_location (struct loop *loop)
1743 rtx_insn *insn = NULL;
1744 struct niter_desc *desc = NULL;
1745 edge exit;
1747 /* For a for or while loop, we would like to return the location
1748 of the for or while statement, if possible. To do this, look
1749 for the branch guarding the loop back-edge. */
1751 /* If this is a simple loop with an in_edge, then the loop control
1752 branch is typically at the end of its source. */
1753 desc = get_simple_loop_desc (loop);
1754 if (desc->in_edge)
1756 FOR_BB_INSNS_REVERSE (desc->in_edge->src, insn)
1758 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1759 return INSN_LOCATION (insn);
1762 /* If loop has a single exit, then the loop control branch
1763 must be at the end of its source. */
1764 if ((exit = single_exit (loop)))
1766 FOR_BB_INSNS_REVERSE (exit->src, insn)
1768 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1769 return INSN_LOCATION (insn);
1772 /* Next check the latch, to see if it is non-empty. */
1773 FOR_BB_INSNS_REVERSE (loop->latch, insn)
1775 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1776 return INSN_LOCATION (insn);
1778 /* Finally, if none of the above identifies the loop control branch,
1779 return the first location in the loop header. */
1780 FOR_BB_INSNS (loop->header, insn)
1782 if (INSN_P (insn) && INSN_HAS_LOCATION (insn))
1783 return INSN_LOCATION (insn);
1785 /* If all else fails, simply return the current function location. */
1786 return DECL_SOURCE_LOCATION (current_function_decl);
1789 /* Records that every statement in LOOP is executed I_BOUND times.
1790 REALISTIC is true if I_BOUND is expected to be close to the real number
1791 of iterations. UPPER is true if we are sure the loop iterates at most
1792 I_BOUND times. */
1794 void
1795 record_niter_bound (struct loop *loop, const widest_int &i_bound,
1796 bool realistic, bool upper)
1798 /* Update the bounds only when there is no previous estimation, or when the
1799 current estimation is smaller. */
1800 if (upper
1801 && (!loop->any_upper_bound
1802 || wi::ltu_p (i_bound, loop->nb_iterations_upper_bound)))
1804 loop->any_upper_bound = true;
1805 loop->nb_iterations_upper_bound = i_bound;
1807 if (realistic
1808 && (!loop->any_estimate
1809 || wi::ltu_p (i_bound, loop->nb_iterations_estimate)))
1811 loop->any_estimate = true;
1812 loop->nb_iterations_estimate = i_bound;
1815 /* If an upper bound is smaller than the realistic estimate of the
1816 number of iterations, use the upper bound instead. */
1817 if (loop->any_upper_bound
1818 && loop->any_estimate
1819 && wi::ltu_p (loop->nb_iterations_upper_bound,
1820 loop->nb_iterations_estimate))
1821 loop->nb_iterations_estimate = loop->nb_iterations_upper_bound;
1824 /* Similar to get_estimated_loop_iterations, but returns the estimate only
1825 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1826 on the number of iterations of LOOP could not be derived, returns -1. */
1828 HOST_WIDE_INT
1829 get_estimated_loop_iterations_int (struct loop *loop)
1831 widest_int nit;
1832 HOST_WIDE_INT hwi_nit;
1834 if (!get_estimated_loop_iterations (loop, &nit))
1835 return -1;
1837 if (!wi::fits_shwi_p (nit))
1838 return -1;
1839 hwi_nit = nit.to_shwi ();
1841 return hwi_nit < 0 ? -1 : hwi_nit;
1844 /* Returns an upper bound on the number of executions of statements
1845 in the LOOP. For statements before the loop exit, this exceeds
1846 the number of execution of the latch by one. */
1848 HOST_WIDE_INT
1849 max_stmt_executions_int (struct loop *loop)
1851 HOST_WIDE_INT nit = get_max_loop_iterations_int (loop);
1852 HOST_WIDE_INT snit;
1854 if (nit == -1)
1855 return -1;
1857 snit = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) nit + 1);
1859 /* If the computation overflows, return -1. */
1860 return snit < 0 ? -1 : snit;
1863 /* Sets NIT to the estimated number of executions of the latch of the
1864 LOOP. If we have no reliable estimate, the function returns false, otherwise
1865 returns true. */
1867 bool
1868 get_estimated_loop_iterations (struct loop *loop, widest_int *nit)
1870 /* Even if the bound is not recorded, possibly we can derrive one from
1871 profile. */
1872 if (!loop->any_estimate)
1874 if (loop->header->count)
1876 *nit = gcov_type_to_wide_int
1877 (expected_loop_iterations_unbounded (loop) + 1);
1878 return true;
1880 return false;
1883 *nit = loop->nb_iterations_estimate;
1884 return true;
1887 /* Sets NIT to an upper bound for the maximum number of executions of the
1888 latch of the LOOP. If we have no reliable estimate, the function returns
1889 false, otherwise returns true. */
1891 bool
1892 get_max_loop_iterations (struct loop *loop, widest_int *nit)
1894 if (!loop->any_upper_bound)
1895 return false;
1897 *nit = loop->nb_iterations_upper_bound;
1898 return true;
1901 /* Similar to get_max_loop_iterations, but returns the estimate only
1902 if it fits to HOST_WIDE_INT. If this is not the case, or the estimate
1903 on the number of iterations of LOOP could not be derived, returns -1. */
1905 HOST_WIDE_INT
1906 get_max_loop_iterations_int (struct loop *loop)
1908 widest_int nit;
1909 HOST_WIDE_INT hwi_nit;
1911 if (!get_max_loop_iterations (loop, &nit))
1912 return -1;
1914 if (!wi::fits_shwi_p (nit))
1915 return -1;
1916 hwi_nit = nit.to_shwi ();
1918 return hwi_nit < 0 ? -1 : hwi_nit;
1921 /* Returns the loop depth of the loop BB belongs to. */
1924 bb_loop_depth (const_basic_block bb)
1926 return bb->loop_father ? loop_depth (bb->loop_father) : 0;
1929 /* Marks LOOP for removal and sets LOOPS_NEED_FIXUP. */
1931 void
1932 mark_loop_for_removal (loop_p loop)
1934 if (loop->header == NULL)
1935 return;
1936 loop->former_header = loop->header;
1937 loop->header = NULL;
1938 loop->latch = NULL;
1939 loops_state_set (LOOPS_NEED_FIXUP);