1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000, 2001, 2003, 2004, 2005, 2006, 2007, 2008
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
26 #include "hard-reg-set.h"
29 #include "basic-block.h"
34 #include "tree-flow.h"
35 #include "pointer-set.h"
39 #include <machine/cpufunc.h>
42 static void flow_loops_cfg_dump (FILE *);
44 /* Dump loop related CFG information. */
47 flow_loops_cfg_dump (FILE *file)
59 fprintf (file, ";; %d succs { ", bb->index);
60 FOR_EACH_EDGE (succ, ei, bb->succs)
61 fprintf (file, "%d ", succ->dest->index);
62 fprintf (file, "}\n");
66 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
69 flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
71 unsigned odepth = loop_depth (outer);
73 return (loop_depth (loop) > odepth
74 && VEC_index (loop_p, loop->superloops, odepth) == outer);
77 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
81 superloop_at_depth (struct loop *loop, unsigned depth)
83 unsigned ldepth = loop_depth (loop);
85 gcc_assert (depth <= ldepth);
90 return VEC_index (loop_p, loop->superloops, depth);
93 /* Returns the list of the latch edges of LOOP. */
95 static VEC (edge, heap) *
96 get_loop_latch_edges (const struct loop *loop)
100 VEC (edge, heap) *ret = NULL;
102 FOR_EACH_EDGE (e, ei, loop->header->preds)
104 if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header))
105 VEC_safe_push (edge, heap, ret, e);
111 /* Dump the loop information specified by LOOP to the stream FILE
112 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
115 flow_loop_dump (const struct loop *loop, FILE *file,
116 void (*loop_dump_aux) (const struct loop *, FILE *, int),
121 VEC (edge, heap) *latches;
124 if (! loop || ! loop->header)
127 fprintf (file, ";;\n;; Loop %d\n", loop->num);
129 fprintf (file, ";; header %d, ", loop->header->index);
131 fprintf (file, "latch %d\n", loop->latch->index);
134 fprintf (file, "multiple latches:");
135 latches = get_loop_latch_edges (loop);
136 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
137 fprintf (file, " %d", e->src->index);
138 VEC_free (edge, heap, latches);
139 fprintf (file, "\n");
142 fprintf (file, ";; depth %d, outer %ld\n",
143 loop_depth (loop), (long) (loop_outer (loop)
144 ? loop_outer (loop)->num : -1));
146 fprintf (file, ";; nodes:");
147 bbs = get_loop_body (loop);
148 for (i = 0; i < loop->num_nodes; i++)
149 fprintf (file, " %d", bbs[i]->index);
151 fprintf (file, "\n");
154 loop_dump_aux (loop, file, verbose);
157 /* Dump the loop information about loops to the stream FILE,
158 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
161 flow_loops_dump (FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
166 if (!current_loops || ! file)
169 fprintf (file, ";; %d loops found\n", number_of_loops ());
171 FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
173 flow_loop_dump (loop, file, loop_dump_aux, verbose);
177 flow_loops_cfg_dump (file);
180 /* Free data allocated for LOOP. */
183 flow_loop_free (struct loop *loop)
185 struct loop_exit *exit, *next;
187 VEC_free (loop_p, gc, loop->superloops);
189 /* Break the list of the loop exit records. They will be freed when the
190 corresponding edge is rescanned or removed, and this avoids
191 accessing the (already released) head of the list stored in the
193 for (exit = loop->exits->next; exit != loop->exits; exit = next)
200 ggc_free (loop->exits);
204 /* Free all the memory allocated for LOOPS. */
207 flow_loops_free (struct loops *loops)
214 /* Free the loop descriptors. */
215 for (i = 0; VEC_iterate (loop_p, loops->larray, i, loop); i++)
220 flow_loop_free (loop);
223 VEC_free (loop_p, gc, loops->larray);
227 /* Find the nodes contained within the LOOP with header HEADER.
228 Return the number of nodes within the loop. */
231 flow_loop_nodes_find (basic_block header, struct loop *loop)
233 VEC (basic_block, heap) *stack = NULL;
236 edge_iterator latch_ei;
237 unsigned depth = loop_depth (loop);
239 header->loop_father = loop;
240 header->loop_depth = depth;
242 FOR_EACH_EDGE (latch, latch_ei, loop->header->preds)
244 if (latch->src->loop_father == loop
245 || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header))
249 VEC_safe_push (basic_block, heap, stack, latch->src);
250 latch->src->loop_father = loop;
251 latch->src->loop_depth = depth;
253 while (!VEC_empty (basic_block, stack))
259 node = VEC_pop (basic_block, stack);
261 FOR_EACH_EDGE (e, ei, node->preds)
263 basic_block ancestor = e->src;
265 if (ancestor->loop_father != loop)
267 ancestor->loop_father = loop;
268 ancestor->loop_depth = depth;
270 VEC_safe_push (basic_block, heap, stack, ancestor);
275 VEC_free (basic_block, heap, stack);
280 /* Records the vector of superloops of the loop LOOP, whose immediate
281 superloop is FATHER. */
284 establish_preds (struct loop *loop, struct loop *father)
287 unsigned depth = loop_depth (father) + 1;
290 VEC_truncate (loop_p, loop->superloops, 0);
291 VEC_reserve (loop_p, gc, loop->superloops, depth);
292 for (i = 0; VEC_iterate (loop_p, father->superloops, i, ploop); i++)
293 VEC_quick_push (loop_p, loop->superloops, ploop);
294 VEC_quick_push (loop_p, loop->superloops, father);
296 for (ploop = loop->inner; ploop; ploop = ploop->next)
297 establish_preds (ploop, loop);
300 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
301 added loop. If LOOP has some children, take care of that their
302 pred field will be initialized correctly. */
305 flow_loop_tree_node_add (struct loop *father, struct loop *loop)
307 loop->next = father->inner;
308 father->inner = loop;
310 establish_preds (loop, father);
313 /* Remove LOOP from the loop hierarchy tree. */
316 flow_loop_tree_node_remove (struct loop *loop)
318 struct loop *prev, *father;
320 father = loop_outer (loop);
322 /* Remove loop from the list of sons. */
323 if (father->inner == loop)
324 father->inner = loop->next;
327 for (prev = father->inner; prev->next != loop; prev = prev->next)
329 prev->next = loop->next;
332 VEC_truncate (loop_p, loop->superloops, 0);
335 /* Allocates and returns new loop structure. */
340 struct loop *loop = GGC_CNEW (struct loop);
342 loop->exits = GGC_CNEW (struct loop_exit);
343 loop->exits->next = loop->exits->prev = loop->exits;
348 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
349 (including the root of the loop tree). */
352 init_loops_structure (struct loops *loops, unsigned num_loops)
356 memset (loops, 0, sizeof *loops);
357 loops->larray = VEC_alloc (loop_p, gc, num_loops);
359 /* Dummy loop containing whole function. */
360 root = alloc_loop ();
361 root->num_nodes = n_basic_blocks;
362 root->latch = EXIT_BLOCK_PTR;
363 root->header = ENTRY_BLOCK_PTR;
364 ENTRY_BLOCK_PTR->loop_father = root;
365 EXIT_BLOCK_PTR->loop_father = root;
367 VEC_quick_push (loop_p, loops->larray, root);
368 loops->tree_root = root;
371 /* Find all the natural loops in the function and save in LOOPS structure and
372 recalculate loop_depth information in basic block structures.
373 Return the number of natural loops found. */
376 flow_loops_find (struct loops *loops)
387 /* Ensure that the dominators are computed. */
388 calculate_dominance_info (CDI_DOMINATORS);
390 /* Taking care of this degenerate case makes the rest of
391 this code simpler. */
392 if (n_basic_blocks == NUM_FIXED_BLOCKS)
394 init_loops_structure (loops, 1);
401 /* Count the number of loop headers. This should be the
402 same as the number of natural loops. */
403 headers = sbitmap_alloc (last_basic_block);
404 sbitmap_zero (headers);
411 header->loop_depth = 0;
413 /* If we have an abnormal predecessor, do not consider the
414 loop (not worth the problems). */
415 FOR_EACH_EDGE (e, ei, header->preds)
416 if (e->flags & EDGE_ABNORMAL)
421 FOR_EACH_EDGE (e, ei, header->preds)
423 basic_block latch = e->src;
425 gcc_assert (!(e->flags & EDGE_ABNORMAL));
427 /* Look for back edges where a predecessor is dominated
428 by this block. A natural loop has a single entry
429 node (header) that dominates all the nodes in the
430 loop. It also has single back edge to the header
431 from a latch node. */
432 if (latch != ENTRY_BLOCK_PTR
433 && dominated_by_p (CDI_DOMINATORS, latch, header))
435 /* Shared headers should be eliminated by now. */
436 SET_BIT (headers, header->index);
442 /* Allocate loop structures. */
443 init_loops_structure (loops, num_loops + 1);
445 /* Find and record information about all the natural loops
448 bb->loop_father = loops->tree_root;
452 /* Compute depth first search order of the CFG so that outer
453 natural loops will be found before inner natural loops. */
454 dfs_order = XNEWVEC (int, n_basic_blocks);
455 rc_order = XNEWVEC (int, n_basic_blocks);
456 pre_and_rev_post_order_compute (dfs_order, rc_order, false);
460 for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++)
465 /* Search the nodes of the CFG in reverse completion order
466 so that we can find outer loops first. */
467 if (!TEST_BIT (headers, rc_order[b]))
470 header = BASIC_BLOCK (rc_order[b]);
472 loop = alloc_loop ();
473 VEC_quick_push (loop_p, loops->larray, loop);
475 loop->header = header;
476 loop->num = num_loops;
479 flow_loop_tree_node_add (header->loop_father, loop);
480 loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
482 /* Look for the latch for this header block, if it has just a
484 FOR_EACH_EDGE (e, ei, header->preds)
486 basic_block latch = e->src;
488 if (flow_bb_inside_loop_p (loop, latch))
490 if (loop->latch != NULL)
492 /* More than one latch edge. */
505 sbitmap_free (headers);
508 return VEC_length (loop_p, loops->larray);
511 /* Ratio of frequencies of edges so that one of more latch edges is
512 considered to belong to inner loop with same header. */
513 #define HEAVY_EDGE_RATIO 8
515 /* Minimum number of samples for that we apply
516 find_subloop_latch_edge_by_profile heuristics. */
517 #define HEAVY_EDGE_MIN_SAMPLES 10
519 /* If the profile info is available, finds an edge in LATCHES that much more
520 frequent than the remaining edges. Returns such an edge, or NULL if we do
523 We do not use guessed profile here, only the measured one. The guessed
524 profile is usually too flat and unreliable for this (and it is mostly based
525 on the loop structure of the program, so it does not make much sense to
526 derive the loop structure from it). */
529 find_subloop_latch_edge_by_profile (VEC (edge, heap) *latches)
533 gcov_type mcount = 0, tcount = 0;
535 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
537 if (e->count > mcount)
545 if (tcount < HEAVY_EDGE_MIN_SAMPLES
546 || (tcount - mcount) * HEAVY_EDGE_RATIO > tcount)
551 "Found latch edge %d -> %d using profile information.\n",
552 me->src->index, me->dest->index);
556 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
557 on the structure of induction variables. Returns this edge, or NULL if we
560 We are quite conservative, and look just for an obvious simple innermost
561 loop (which is the case where we would lose the most performance by not
562 disambiguating the loop). More precisely, we look for the following
563 situation: The source of the chosen latch edge dominates sources of all
564 the other latch edges. Additionally, the header does not contain a phi node
565 such that the argument from the chosen edge is equal to the argument from
569 find_subloop_latch_edge_by_ivs (struct loop *loop ATTRIBUTE_UNUSED, VEC (edge, heap) *latches)
571 edge e, latch = VEC_index (edge, latches, 0);
574 gimple_stmt_iterator psi;
578 /* Find the candidate for the latch edge. */
579 for (i = 1; VEC_iterate (edge, latches, i, e); i++)
580 if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src))
583 /* Verify that it dominates all the latch edges. */
584 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
585 if (!dominated_by_p (CDI_DOMINATORS, e->src, latch->src))
588 /* Check for a phi node that would deny that this is a latch edge of
590 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
592 phi = gsi_stmt (psi);
593 lop = PHI_ARG_DEF_FROM_EDGE (phi, latch);
595 /* Ignore the values that are not changed inside the subloop. */
596 if (TREE_CODE (lop) != SSA_NAME
597 || SSA_NAME_DEF_STMT (lop) == phi)
599 bb = gimple_bb (SSA_NAME_DEF_STMT (lop));
600 if (!bb || !flow_bb_inside_loop_p (loop, bb))
603 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
605 && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop)
611 "Found latch edge %d -> %d using iv structure.\n",
612 latch->src->index, latch->dest->index);
616 /* If we can determine that one of the several latch edges of LOOP behaves
617 as a latch edge of a separate subloop, returns this edge. Otherwise
621 find_subloop_latch_edge (struct loop *loop)
623 VEC (edge, heap) *latches = get_loop_latch_edges (loop);
626 if (VEC_length (edge, latches) > 1)
628 latch = find_subloop_latch_edge_by_profile (latches);
631 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
632 should use cfghook for this, but it is hard to imagine it would
633 be useful elsewhere. */
634 && current_ir_type () == IR_GIMPLE)
635 latch = find_subloop_latch_edge_by_ivs (loop, latches);
638 VEC_free (edge, heap, latches);
642 /* Callback for make_forwarder_block. Returns true if the edge E is marked
643 in the set MFB_REIS_SET. */
645 static struct pointer_set_t *mfb_reis_set;
647 mfb_redirect_edges_in_set (edge e)
649 return pointer_set_contains (mfb_reis_set, e);
652 /* Creates a subloop of LOOP with latch edge LATCH. */
655 form_subloop (struct loop *loop, edge latch)
659 struct loop *new_loop;
661 mfb_reis_set = pointer_set_create ();
662 FOR_EACH_EDGE (e, ei, loop->header->preds)
665 pointer_set_insert (mfb_reis_set, e);
667 new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
669 pointer_set_destroy (mfb_reis_set);
671 loop->header = new_entry->src;
673 /* Find the blocks and subloops that belong to the new loop, and add it to
674 the appropriate place in the loop tree. */
675 new_loop = alloc_loop ();
676 new_loop->header = new_entry->dest;
677 new_loop->latch = latch->src;
678 add_loop (new_loop, loop);
681 /* Make all the latch edges of LOOP to go to a single forwarder block --
682 a new latch of LOOP. */
685 merge_latch_edges (struct loop *loop)
687 VEC (edge, heap) *latches = get_loop_latch_edges (loop);
691 gcc_assert (VEC_length (edge, latches) > 0);
693 if (VEC_length (edge, latches) == 1)
694 loop->latch = VEC_index (edge, latches, 0)->src;
698 fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num);
700 mfb_reis_set = pointer_set_create ();
701 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
702 pointer_set_insert (mfb_reis_set, e);
703 latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
705 pointer_set_destroy (mfb_reis_set);
707 loop->header = latch->dest;
708 loop->latch = latch->src;
711 VEC_free (edge, heap, latches);
714 /* LOOP may have several latch edges. Transform it into (possibly several)
715 loops with single latch edge. */
718 disambiguate_multiple_latches (struct loop *loop)
722 /* We eliminate the multiple latches by splitting the header to the forwarder
723 block F and the rest R, and redirecting the edges. There are two cases:
725 1) If there is a latch edge E that corresponds to a subloop (we guess
726 that based on profile -- if it is taken much more often than the
727 remaining edges; and on trees, using the information about induction
728 variables of the loops), we redirect E to R, all the remaining edges to
729 F, then rescan the loops and try again for the outer loop.
730 2) If there is no such edge, we redirect all latch edges to F, and the
731 entry edges to R, thus making F the single latch of the loop. */
734 fprintf (dump_file, "Disambiguating loop %d with multiple latches\n",
737 /* During latch merging, we may need to redirect the entry edges to a new
738 block. This would cause problems if the entry edge was the one from the
739 entry block. To avoid having to handle this case specially, split
741 e = find_edge (ENTRY_BLOCK_PTR, loop->header);
747 e = find_subloop_latch_edge (loop);
751 form_subloop (loop, e);
754 merge_latch_edges (loop);
757 /* Split loops with multiple latch edges. */
760 disambiguate_loops_with_multiple_latches (void)
765 FOR_EACH_LOOP (li, loop, 0)
768 disambiguate_multiple_latches (loop);
772 /* Return nonzero if basic block BB belongs to LOOP. */
774 flow_bb_inside_loop_p (const struct loop *loop, const_basic_block bb)
776 struct loop *source_loop;
778 if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
781 source_loop = bb->loop_father;
782 return loop == source_loop || flow_loop_nested_p (loop, source_loop);
785 /* Enumeration predicate for get_loop_body_with_size. */
787 glb_enum_p (const_basic_block bb, const void *glb_loop)
789 const struct loop *const loop = (const struct loop *) glb_loop;
790 return (bb != loop->header
791 && dominated_by_p (CDI_DOMINATORS, bb, loop->header));
794 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
795 order against direction of edges from latch. Specially, if
796 header != latch, latch is the 1-st block. LOOP cannot be the fake
797 loop tree root, and its size must be at most MAX_SIZE. The blocks
798 in the LOOP body are stored to BODY, and the size of the LOOP is
802 get_loop_body_with_size (const struct loop *loop, basic_block *body,
805 return dfs_enumerate_from (loop->header, 1, glb_enum_p,
806 body, max_size, loop);
809 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
810 order against direction of edges from latch. Specially, if
811 header != latch, latch is the 1-st block. */
814 get_loop_body (const struct loop *loop)
816 basic_block *body, bb;
819 gcc_assert (loop->num_nodes);
821 body = XCNEWVEC (basic_block, loop->num_nodes);
823 if (loop->latch == EXIT_BLOCK_PTR)
825 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
826 special-case the fake loop that contains the whole function. */
827 gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks);
828 body[tv++] = loop->header;
829 body[tv++] = EXIT_BLOCK_PTR;
834 tv = get_loop_body_with_size (loop, body, loop->num_nodes);
836 gcc_assert (tv == loop->num_nodes);
840 /* Fills dominance descendants inside LOOP of the basic block BB into
841 array TOVISIT from index *TV. */
844 fill_sons_in_loop (const struct loop *loop, basic_block bb,
845 basic_block *tovisit, int *tv)
847 basic_block son, postpone = NULL;
849 tovisit[(*tv)++] = bb;
850 for (son = first_dom_son (CDI_DOMINATORS, bb);
852 son = next_dom_son (CDI_DOMINATORS, son))
854 if (!flow_bb_inside_loop_p (loop, son))
857 if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
862 fill_sons_in_loop (loop, son, tovisit, tv);
866 fill_sons_in_loop (loop, postpone, tovisit, tv);
867 #ifdef __AMDCPUBUG_DFLY01_AVAILABLE__
868 cpu_amdcpubug_dfly01();
872 /* Gets body of a LOOP (that must be different from the outermost loop)
873 sorted by dominance relation. Additionally, if a basic block s dominates
874 the latch, then only blocks dominated by s are be after it. */
877 get_loop_body_in_dom_order (const struct loop *loop)
879 basic_block *tovisit;
882 gcc_assert (loop->num_nodes);
884 tovisit = XCNEWVEC (basic_block, loop->num_nodes);
886 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
889 fill_sons_in_loop (loop, loop->header, tovisit, &tv);
891 gcc_assert (tv == (int) loop->num_nodes);
896 /* Gets body of a LOOP sorted via provided BB_COMPARATOR. */
899 get_loop_body_in_custom_order (const struct loop *loop,
900 int (*bb_comparator) (const void *, const void *))
902 basic_block *bbs = get_loop_body (loop);
904 qsort (bbs, loop->num_nodes, sizeof (basic_block), bb_comparator);
909 /* Get body of a LOOP in breadth first sort order. */
912 get_loop_body_in_bfs_order (const struct loop *loop)
920 gcc_assert (loop->num_nodes);
921 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
923 blocks = XCNEWVEC (basic_block, loop->num_nodes);
924 visited = BITMAP_ALLOC (NULL);
927 while (i < loop->num_nodes)
932 if (!bitmap_bit_p (visited, bb->index))
934 /* This basic block is now visited */
935 bitmap_set_bit (visited, bb->index);
939 FOR_EACH_EDGE (e, ei, bb->succs)
941 if (flow_bb_inside_loop_p (loop, e->dest))
943 if (!bitmap_bit_p (visited, e->dest->index))
945 bitmap_set_bit (visited, e->dest->index);
946 blocks[i++] = e->dest;
951 gcc_assert (i >= vc);
956 BITMAP_FREE (visited);
960 /* Hash function for struct loop_exit. */
963 loop_exit_hash (const void *ex)
965 const struct loop_exit *const exit = (const struct loop_exit *) ex;
967 return htab_hash_pointer (exit->e);
970 /* Equality function for struct loop_exit. Compares with edge. */
973 loop_exit_eq (const void *ex, const void *e)
975 const struct loop_exit *const exit = (const struct loop_exit *) ex;
980 /* Frees the list of loop exit descriptions EX. */
983 loop_exit_free (void *ex)
985 struct loop_exit *exit = (struct loop_exit *) ex, *next;
987 for (; exit; exit = next)
991 exit->next->prev = exit->prev;
992 exit->prev->next = exit->next;
998 /* Returns the list of records for E as an exit of a loop. */
1000 static struct loop_exit *
1001 get_exit_descriptions (edge e)
1003 return (struct loop_exit *) htab_find_with_hash (current_loops->exits, e,
1004 htab_hash_pointer (e));
1007 /* Updates the lists of loop exits in that E appears.
1008 If REMOVED is true, E is being removed, and we
1009 just remove it from the lists of exits.
1010 If NEW_EDGE is true and E is not a loop exit, we
1011 do not try to remove it from loop exit lists. */
1014 rescan_loop_exit (edge e, bool new_edge, bool removed)
1017 struct loop_exit *exits = NULL, *exit;
1018 struct loop *aloop, *cloop;
1020 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1024 && e->src->loop_father != NULL
1025 && e->dest->loop_father != NULL
1026 && !flow_bb_inside_loop_p (e->src->loop_father, e->dest))
1028 cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
1029 for (aloop = e->src->loop_father;
1031 aloop = loop_outer (aloop))
1033 exit = GGC_NEW (struct loop_exit);
1036 exit->next = aloop->exits->next;
1037 exit->prev = aloop->exits;
1038 exit->next->prev = exit;
1039 exit->prev->next = exit;
1041 exit->next_e = exits;
1046 if (!exits && new_edge)
1049 slot = htab_find_slot_with_hash (current_loops->exits, e,
1050 htab_hash_pointer (e),
1051 exits ? INSERT : NO_INSERT);
1058 loop_exit_free (*slot);
1062 htab_clear_slot (current_loops->exits, slot);
1065 /* For each loop, record list of exit edges, and start maintaining these
1069 record_loop_exits (void)
1078 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1080 loops_state_set (LOOPS_HAVE_RECORDED_EXITS);
1082 gcc_assert (current_loops->exits == NULL);
1083 current_loops->exits = htab_create_alloc (2 * number_of_loops (),
1087 ggc_calloc, ggc_free);
1091 FOR_EACH_EDGE (e, ei, bb->succs)
1093 rescan_loop_exit (e, true, false);
1098 /* Dumps information about the exit in *SLOT to FILE.
1099 Callback for htab_traverse. */
1102 dump_recorded_exit (void **slot, void *file)
1104 struct loop_exit *exit = (struct loop_exit *) *slot;
1108 for (; exit != NULL; exit = exit->next_e)
1111 fprintf ((FILE*) file, "Edge %d->%d exits %u loops\n",
1112 e->src->index, e->dest->index, n);
1117 /* Dumps the recorded exits of loops to FILE. */
1119 extern void dump_recorded_exits (FILE *);
1121 dump_recorded_exits (FILE *file)
1123 if (!current_loops->exits)
1125 htab_traverse (current_loops->exits, dump_recorded_exit, file);
1128 /* Releases lists of loop exits. */
1131 release_recorded_exits (void)
1133 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS));
1134 htab_delete (current_loops->exits);
1135 current_loops->exits = NULL;
1136 loops_state_clear (LOOPS_HAVE_RECORDED_EXITS);
1139 /* Returns the list of the exit edges of a LOOP. */
1142 get_loop_exit_edges (const struct loop *loop)
1144 VEC (edge, heap) *edges = NULL;
1149 struct loop_exit *exit;
1151 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1153 /* If we maintain the lists of exits, use them. Otherwise we must
1154 scan the body of the loop. */
1155 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1157 for (exit = loop->exits->next; exit->e; exit = exit->next)
1158 VEC_safe_push (edge, heap, edges, exit->e);
1162 body = get_loop_body (loop);
1163 for (i = 0; i < loop->num_nodes; i++)
1164 FOR_EACH_EDGE (e, ei, body[i]->succs)
1166 if (!flow_bb_inside_loop_p (loop, e->dest))
1167 VEC_safe_push (edge, heap, edges, e);
1175 /* Counts the number of conditional branches inside LOOP. */
1178 num_loop_branches (const struct loop *loop)
1183 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1185 body = get_loop_body (loop);
1187 for (i = 0; i < loop->num_nodes; i++)
1188 if (EDGE_COUNT (body[i]->succs) >= 2)
1195 /* Adds basic block BB to LOOP. */
1197 add_bb_to_loop (basic_block bb, struct loop *loop)
1204 gcc_assert (bb->loop_father == NULL);
1205 bb->loop_father = loop;
1206 bb->loop_depth = loop_depth (loop);
1208 for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++)
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. */
1223 remove_bb_from_loops (basic_block bb)
1226 struct loop *loop = bb->loop_father;
1231 gcc_assert (loop != NULL);
1233 for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++)
1235 bb->loop_father = NULL;
1238 FOR_EACH_EDGE (e, ei, bb->succs)
1240 rescan_loop_exit (e, false, true);
1242 FOR_EACH_EDGE (e, ei, bb->preds)
1244 rescan_loop_exit (e, false, true);
1248 /* Finds nearest common ancestor in loop tree for given loops. */
1250 find_common_loop (struct loop *loop_s, struct loop *loop_d)
1252 unsigned sdepth, ddepth;
1254 if (!loop_s) return loop_d;
1255 if (!loop_d) return loop_s;
1257 sdepth = loop_depth (loop_s);
1258 ddepth = loop_depth (loop_d);
1260 if (sdepth < ddepth)
1261 loop_d = VEC_index (loop_p, loop_d->superloops, sdepth);
1262 else if (sdepth > ddepth)
1263 loop_s = VEC_index (loop_p, loop_s->superloops, ddepth);
1265 while (loop_s != loop_d)
1267 loop_s = loop_outer (loop_s);
1268 loop_d = loop_outer (loop_d);
1273 /* Removes LOOP from structures and frees its data. */
1276 delete_loop (struct loop *loop)
1278 /* Remove the loop from structure. */
1279 flow_loop_tree_node_remove (loop);
1281 /* Remove loop from loops array. */
1282 VEC_replace (loop_p, current_loops->larray, loop->num, NULL);
1284 /* Free loop data. */
1285 flow_loop_free (loop);
1288 /* Cancels the LOOP; it must be innermost one. */
1291 cancel_loop (struct loop *loop)
1295 struct loop *outer = loop_outer (loop);
1297 gcc_assert (!loop->inner);
1299 /* Move blocks up one level (they should be removed as soon as possible). */
1300 bbs = get_loop_body (loop);
1301 for (i = 0; i < loop->num_nodes; i++)
1302 bbs[i]->loop_father = outer;
1307 /* Cancels LOOP and all its subloops. */
1309 cancel_loop_tree (struct loop *loop)
1312 cancel_loop_tree (loop->inner);
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
1324 verify_loop_structure (void)
1326 unsigned *sizes, i, j;
1328 basic_block *bbs, bb;
1332 unsigned num = number_of_loops ();
1334 struct loop_exit *exit, *mexit;
1337 sizes = XCNEWVEC (unsigned, num);
1341 for (loop = bb->loop_father; loop; loop = loop_outer (loop))
1344 FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
1348 if (loop->num_nodes != sizes[i])
1350 error ("size of loop %d should be %d, not %d",
1351 i, sizes[i], loop->num_nodes);
1356 /* Check get_loop_body. */
1357 FOR_EACH_LOOP (li, loop, 0)
1359 bbs = get_loop_body (loop);
1361 for (j = 0; j < loop->num_nodes; j++)
1362 if (!flow_bb_inside_loop_p (loop, bbs[j]))
1364 error ("bb %d do not belong to loop %d",
1365 bbs[j]->index, loop->num);
1371 /* Check headers and latches. */
1372 FOR_EACH_LOOP (li, loop, 0)
1376 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
1377 && EDGE_COUNT (loop->header->preds) != 2)
1379 error ("loop %d's header does not have exactly 2 entries", i);
1382 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
1384 if (!single_succ_p (loop->latch))
1386 error ("loop %d's latch does not have exactly 1 successor", i);
1389 if (single_succ (loop->latch) != loop->header)
1391 error ("loop %d's latch does not have header as successor", i);
1394 if (loop->latch->loop_father != loop)
1396 error ("loop %d's latch does not belong directly to it", i);
1400 if (loop->header->loop_father != loop)
1402 error ("loop %d's header does not belong directly to it", i);
1405 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1406 && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
1408 error ("loop %d's latch is marked as part of irreducible region", i);
1413 /* Check irreducible loops. */
1414 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1416 /* Record old info. */
1417 irreds = sbitmap_alloc (last_basic_block);
1421 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1422 SET_BIT (irreds, bb->index);
1424 RESET_BIT (irreds, bb->index);
1425 FOR_EACH_EDGE (e, ei, bb->succs)
1426 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1427 e->flags |= EDGE_ALL_FLAGS + 1;
1431 mark_irreducible_loops ();
1438 if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1439 && !TEST_BIT (irreds, bb->index))
1441 error ("basic block %d should be marked irreducible", bb->index);
1444 else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1445 && TEST_BIT (irreds, bb->index))
1447 error ("basic block %d should not be marked irreducible", bb->index);
1450 FOR_EACH_EDGE (e, ei, bb->succs)
1452 if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1453 && !(e->flags & (EDGE_ALL_FLAGS + 1)))
1455 error ("edge from %d to %d should be marked irreducible",
1456 e->src->index, e->dest->index);
1459 else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1460 && (e->flags & (EDGE_ALL_FLAGS + 1)))
1462 error ("edge from %d to %d should not be marked irreducible",
1463 e->src->index, e->dest->index);
1466 e->flags &= ~(EDGE_ALL_FLAGS + 1);
1472 /* Check the recorded loop exits. */
1473 FOR_EACH_LOOP (li, loop, 0)
1475 if (!loop->exits || loop->exits->e != NULL)
1477 error ("corrupted head of the exits list of loop %d",
1483 /* Check that the list forms a cycle, and all elements except
1484 for the head are nonnull. */
1485 for (mexit = loop->exits, exit = mexit->next, i = 0;
1486 exit->e && exit != mexit;
1490 mexit = mexit->next;
1493 if (exit != loop->exits)
1495 error ("corrupted exits list of loop %d", loop->num);
1500 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1502 if (loop->exits->next != loop->exits)
1504 error ("nonempty exits list of loop %d, but exits are not recorded",
1511 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1513 unsigned n_exits = 0, eloops;
1515 memset (sizes, 0, sizeof (unsigned) * num);
1519 if (bb->loop_father == current_loops->tree_root)
1521 FOR_EACH_EDGE (e, ei, bb->succs)
1523 if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
1527 exit = get_exit_descriptions (e);
1530 error ("Exit %d->%d not recorded",
1531 e->src->index, e->dest->index);
1535 for (; exit; exit = exit->next_e)
1538 for (loop = bb->loop_father;
1539 loop != e->dest->loop_father;
1540 loop = loop_outer (loop))
1548 error ("Wrong list of exited loops for edge %d->%d",
1549 e->src->index, e->dest->index);
1555 if (n_exits != htab_elements (current_loops->exits))
1557 error ("Too many loop exits recorded");
1561 FOR_EACH_LOOP (li, loop, 0)
1564 for (exit = loop->exits->next; exit->e; exit = exit->next)
1566 if (eloops != sizes[loop->num])
1568 error ("%d exits recorded for loop %d (having %d exits)",
1569 eloops, loop->num, sizes[loop->num]);
1580 /* Returns latch edge of LOOP. */
1582 loop_latch_edge (const struct loop *loop)
1584 return find_edge (loop->latch, loop->header);
1587 /* Returns preheader edge of LOOP. */
1589 loop_preheader_edge (const struct loop *loop)
1594 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS));
1596 FOR_EACH_EDGE (e, ei, loop->header->preds)
1597 if (e->src != loop->latch)
1603 /* Returns true if E is an exit of LOOP. */
1606 loop_exit_edge_p (const struct loop *loop, const_edge e)
1608 return (flow_bb_inside_loop_p (loop, e->src)
1609 && !flow_bb_inside_loop_p (loop, e->dest));
1612 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1613 or more than one exit. If loops do not have the exits recorded, NULL
1614 is returned always. */
1617 single_exit (const struct loop *loop)
1619 struct loop_exit *exit = loop->exits->next;
1621 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1624 if (exit->e && exit->next == loop->exits)
1630 /* Returns true when BB has an edge exiting LOOP. */
1633 is_loop_exit (struct loop *loop, basic_block bb)
1638 FOR_EACH_EDGE (e, ei, bb->preds)
1639 if (loop_exit_edge_p (loop, e))