Daily bump.
[official-gcc.git] / gcc / cfgloop.c
blobf565708ae9ed55dddb3512f342e99e6385bac2a9
1 /* Natural loop discovery code for GNU compiler.
2 Copyright (C) 2000, 2001, 2003, 2004, 2005, 2006, 2007
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
10 version.
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
15 for more details.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "hard-reg-set.h"
27 #include "obstack.h"
28 #include "function.h"
29 #include "basic-block.h"
30 #include "toplev.h"
31 #include "cfgloop.h"
32 #include "flags.h"
33 #include "tree.h"
34 #include "tree-flow.h"
35 #include "pointer-set.h"
36 #include "output.h"
37 #include "ggc.h"
39 static void flow_loops_cfg_dump (FILE *);
41 /* Dump loop related CFG information. */
43 static void
44 flow_loops_cfg_dump (FILE *file)
46 basic_block bb;
48 if (!file)
49 return;
51 FOR_EACH_BB (bb)
53 edge succ;
54 edge_iterator ei;
56 fprintf (file, ";; %d succs { ", bb->index);
57 FOR_EACH_EDGE (succ, ei, bb->succs)
58 fprintf (file, "%d ", succ->dest->index);
59 fprintf (file, "}\n");
63 /* Return nonzero if the nodes of LOOP are a subset of OUTER. */
65 bool
66 flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
68 unsigned odepth = loop_depth (outer);
70 return (loop_depth (loop) > odepth
71 && VEC_index (loop_p, loop->superloops, odepth) == outer);
74 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
75 loops within LOOP. */
77 struct loop *
78 superloop_at_depth (struct loop *loop, unsigned depth)
80 unsigned ldepth = loop_depth (loop);
82 gcc_assert (depth <= ldepth);
84 if (depth == ldepth)
85 return loop;
87 return VEC_index (loop_p, loop->superloops, depth);
90 /* Returns the list of the latch edges of LOOP. */
92 static VEC (edge, heap) *
93 get_loop_latch_edges (const struct loop *loop)
95 edge_iterator ei;
96 edge e;
97 VEC (edge, heap) *ret = NULL;
99 FOR_EACH_EDGE (e, ei, loop->header->preds)
101 if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header))
102 VEC_safe_push (edge, heap, ret, e);
105 return ret;
108 /* Dump the loop information specified by LOOP to the stream FILE
109 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
111 void
112 flow_loop_dump (const struct loop *loop, FILE *file,
113 void (*loop_dump_aux) (const struct loop *, FILE *, int),
114 int verbose)
116 basic_block *bbs;
117 unsigned i;
118 VEC (edge, heap) *latches;
119 edge e;
121 if (! loop || ! loop->header)
122 return;
124 fprintf (file, ";;\n;; Loop %d\n", loop->num);
126 fprintf (file, ";; header %d, ", loop->header->index);
127 if (loop->latch)
128 fprintf (file, "latch %d\n", loop->latch->index);
129 else
131 fprintf (file, "multiple latches:");
132 latches = get_loop_latch_edges (loop);
133 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
134 fprintf (file, " %d", e->src->index);
135 VEC_free (edge, heap, latches);
136 fprintf (file, "\n");
139 fprintf (file, ";; depth %d, outer %ld\n",
140 loop_depth (loop), (long) (loop_outer (loop)
141 ? loop_outer (loop)->num : -1));
143 fprintf (file, ";; nodes:");
144 bbs = get_loop_body (loop);
145 for (i = 0; i < loop->num_nodes; i++)
146 fprintf (file, " %d", bbs[i]->index);
147 free (bbs);
148 fprintf (file, "\n");
150 if (loop_dump_aux)
151 loop_dump_aux (loop, file, verbose);
154 /* Dump the loop information about loops to the stream FILE,
155 using auxiliary dump callback function LOOP_DUMP_AUX if non null. */
157 void
158 flow_loops_dump (FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
160 loop_iterator li;
161 struct loop *loop;
163 if (!current_loops || ! file)
164 return;
166 fprintf (file, ";; %d loops found\n", number_of_loops ());
168 FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
170 flow_loop_dump (loop, file, loop_dump_aux, verbose);
173 if (verbose)
174 flow_loops_cfg_dump (file);
177 /* Free data allocated for LOOP. */
179 void
180 flow_loop_free (struct loop *loop)
182 struct loop_exit *exit, *next;
184 VEC_free (loop_p, gc, loop->superloops);
186 /* Break the list of the loop exit records. They will be freed when the
187 corresponding edge is rescanned or removed, and this avoids
188 accessing the (already released) head of the list stored in the
189 loop structure. */
190 for (exit = loop->exits->next; exit != loop->exits; exit = next)
192 next = exit->next;
193 exit->next = exit;
194 exit->prev = exit;
197 ggc_free (loop->exits);
198 ggc_free (loop);
201 /* Free all the memory allocated for LOOPS. */
203 void
204 flow_loops_free (struct loops *loops)
206 if (loops->larray)
208 unsigned i;
209 loop_p loop;
211 /* Free the loop descriptors. */
212 for (i = 0; VEC_iterate (loop_p, loops->larray, i, loop); i++)
214 if (!loop)
215 continue;
217 flow_loop_free (loop);
220 VEC_free (loop_p, gc, loops->larray);
224 /* Find the nodes contained within the LOOP with header HEADER.
225 Return the number of nodes within the loop. */
228 flow_loop_nodes_find (basic_block header, struct loop *loop)
230 VEC (basic_block, heap) *stack = NULL;
231 int num_nodes = 1;
232 edge latch;
233 edge_iterator latch_ei;
234 unsigned depth = loop_depth (loop);
236 header->loop_father = loop;
237 header->loop_depth = depth;
239 FOR_EACH_EDGE (latch, latch_ei, loop->header->preds)
241 if (latch->src->loop_father == loop
242 || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header))
243 continue;
245 num_nodes++;
246 VEC_safe_push (basic_block, heap, stack, latch->src);
247 latch->src->loop_father = loop;
248 latch->src->loop_depth = depth;
250 while (!VEC_empty (basic_block, stack))
252 basic_block node;
253 edge e;
254 edge_iterator ei;
256 node = VEC_pop (basic_block, stack);
258 FOR_EACH_EDGE (e, ei, node->preds)
260 basic_block ancestor = e->src;
262 if (ancestor->loop_father != loop)
264 ancestor->loop_father = loop;
265 ancestor->loop_depth = depth;
266 num_nodes++;
267 VEC_safe_push (basic_block, heap, stack, ancestor);
272 VEC_free (basic_block, heap, stack);
274 return num_nodes;
277 /* Records the vector of superloops of the loop LOOP, whose immediate
278 superloop is FATHER. */
280 static void
281 establish_preds (struct loop *loop, struct loop *father)
283 loop_p ploop;
284 unsigned depth = loop_depth (father) + 1;
285 unsigned i;
287 VEC_truncate (loop_p, loop->superloops, 0);
288 VEC_reserve (loop_p, gc, loop->superloops, depth);
289 for (i = 0; VEC_iterate (loop_p, father->superloops, i, ploop); i++)
290 VEC_quick_push (loop_p, loop->superloops, ploop);
291 VEC_quick_push (loop_p, loop->superloops, father);
293 for (ploop = loop->inner; ploop; ploop = ploop->next)
294 establish_preds (ploop, loop);
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. */
301 void
302 flow_loop_tree_node_add (struct loop *father, struct loop *loop)
304 loop->next = father->inner;
305 father->inner = loop;
307 establish_preds (loop, father);
310 /* Remove LOOP from the loop hierarchy tree. */
312 void
313 flow_loop_tree_node_remove (struct loop *loop)
315 struct loop *prev, *father;
317 father = loop_outer (loop);
319 /* Remove loop from the list of sons. */
320 if (father->inner == loop)
321 father->inner = loop->next;
322 else
324 for (prev = father->inner; prev->next != loop; prev = prev->next)
325 continue;
326 prev->next = loop->next;
329 VEC_truncate (loop_p, loop->superloops, 0);
332 /* Allocates and returns new loop structure. */
334 struct loop *
335 alloc_loop (void)
337 struct loop *loop = GGC_CNEW (struct loop);
339 loop->exits = GGC_CNEW (struct loop_exit);
340 loop->exits->next = loop->exits->prev = loop->exits;
342 return loop;
345 /* Initializes loops structure LOOPS, reserving place for NUM_LOOPS loops
346 (including the root of the loop tree). */
348 static void
349 init_loops_structure (struct loops *loops, unsigned num_loops)
351 struct loop *root;
353 memset (loops, 0, sizeof *loops);
354 loops->larray = VEC_alloc (loop_p, gc, num_loops);
356 /* Dummy loop containing whole function. */
357 root = alloc_loop ();
358 root->num_nodes = n_basic_blocks;
359 root->latch = EXIT_BLOCK_PTR;
360 root->header = ENTRY_BLOCK_PTR;
361 ENTRY_BLOCK_PTR->loop_father = root;
362 EXIT_BLOCK_PTR->loop_father = root;
364 VEC_quick_push (loop_p, loops->larray, root);
365 loops->tree_root = root;
368 /* Find all the natural loops in the function and save in LOOPS structure and
369 recalculate loop_depth information in basic block structures.
370 Return the number of natural loops found. */
373 flow_loops_find (struct loops *loops)
375 int b;
376 int num_loops;
377 edge e;
378 sbitmap headers;
379 int *dfs_order;
380 int *rc_order;
381 basic_block header;
382 basic_block bb;
384 /* Ensure that the dominators are computed. */
385 calculate_dominance_info (CDI_DOMINATORS);
387 /* Taking care of this degenerate case makes the rest of
388 this code simpler. */
389 if (n_basic_blocks == NUM_FIXED_BLOCKS)
391 init_loops_structure (loops, 1);
392 return 1;
395 dfs_order = NULL;
396 rc_order = NULL;
398 /* Count the number of loop headers. This should be the
399 same as the number of natural loops. */
400 headers = sbitmap_alloc (last_basic_block);
401 sbitmap_zero (headers);
403 num_loops = 0;
404 FOR_EACH_BB (header)
406 edge_iterator ei;
408 header->loop_depth = 0;
410 /* If we have an abnormal predecessor, do not consider the
411 loop (not worth the problems). */
412 FOR_EACH_EDGE (e, ei, header->preds)
413 if (e->flags & EDGE_ABNORMAL)
414 break;
415 if (e)
416 continue;
418 FOR_EACH_EDGE (e, ei, header->preds)
420 basic_block latch = e->src;
422 gcc_assert (!(e->flags & EDGE_ABNORMAL));
424 /* Look for back edges where a predecessor is dominated
425 by this block. A natural loop has a single entry
426 node (header) that dominates all the nodes in the
427 loop. It also has single back edge to the header
428 from a latch node. */
429 if (latch != ENTRY_BLOCK_PTR
430 && dominated_by_p (CDI_DOMINATORS, latch, header))
432 /* Shared headers should be eliminated by now. */
433 SET_BIT (headers, header->index);
434 num_loops++;
439 /* Allocate loop structures. */
440 init_loops_structure (loops, num_loops + 1);
442 /* Find and record information about all the natural loops
443 in the CFG. */
444 FOR_EACH_BB (bb)
445 bb->loop_father = loops->tree_root;
447 if (num_loops)
449 /* Compute depth first search order of the CFG so that outer
450 natural loops will be found before inner natural loops. */
451 dfs_order = XNEWVEC (int, n_basic_blocks);
452 rc_order = XNEWVEC (int, n_basic_blocks);
453 pre_and_rev_post_order_compute (dfs_order, rc_order, false);
455 num_loops = 1;
457 for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++)
459 struct loop *loop;
460 edge_iterator ei;
462 /* Search the nodes of the CFG in reverse completion order
463 so that we can find outer loops first. */
464 if (!TEST_BIT (headers, rc_order[b]))
465 continue;
467 header = BASIC_BLOCK (rc_order[b]);
469 loop = alloc_loop ();
470 VEC_quick_push (loop_p, loops->larray, loop);
472 loop->header = header;
473 loop->num = num_loops;
474 num_loops++;
476 flow_loop_tree_node_add (header->loop_father, loop);
477 loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
479 /* Look for the latch for this header block, if it has just a
480 single one. */
481 FOR_EACH_EDGE (e, ei, header->preds)
483 basic_block latch = e->src;
485 if (flow_bb_inside_loop_p (loop, latch))
487 if (loop->latch != NULL)
489 /* More than one latch edge. */
490 loop->latch = NULL;
491 break;
493 loop->latch = latch;
498 free (dfs_order);
499 free (rc_order);
502 sbitmap_free (headers);
504 loops->exits = NULL;
505 return VEC_length (loop_p, loops->larray);
508 /* Ratio of frequencies of edges so that one of more latch edges is
509 considered to belong to inner loop with same header. */
510 #define HEAVY_EDGE_RATIO 8
512 /* Minimum number of samples for that we apply
513 find_subloop_latch_edge_by_profile heuristics. */
514 #define HEAVY_EDGE_MIN_SAMPLES 10
516 /* If the profile info is available, finds an edge in LATCHES that much more
517 frequent than the remaining edges. Returns such an edge, or NULL if we do
518 not find one.
520 We do not use guessed profile here, only the measured one. The guessed
521 profile is usually too flat and unreliable for this (and it is mostly based
522 on the loop structure of the program, so it does not make much sense to
523 derive the loop structure from it). */
525 static edge
526 find_subloop_latch_edge_by_profile (VEC (edge, heap) *latches)
528 unsigned i;
529 edge e, me = NULL;
530 gcov_type mcount = 0, tcount = 0;
532 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
534 if (e->count > mcount)
536 me = e;
537 mcount = e->count;
539 tcount += e->count;
542 if (tcount < HEAVY_EDGE_MIN_SAMPLES
543 || (tcount - mcount) * HEAVY_EDGE_RATIO > tcount)
544 return NULL;
546 if (dump_file)
547 fprintf (dump_file,
548 "Found latch edge %d -> %d using profile information.\n",
549 me->src->index, me->dest->index);
550 return me;
553 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
554 on the structure of induction variables. Returns this edge, or NULL if we
555 do not find any.
557 We are quite conservative, and look just for an obvious simple innermost
558 loop (which is the case where we would lose the most performance by not
559 disambiguating the loop). More precisely, we look for the following
560 situation: The source of the chosen latch edge dominates sources of all
561 the other latch edges. Additionally, the header does not contain a phi node
562 such that the argument from the chosen edge is equal to the argument from
563 another edge. */
565 static edge
566 find_subloop_latch_edge_by_ivs (struct loop *loop, VEC (edge, heap) *latches)
568 edge e, latch = VEC_index (edge, latches, 0);
569 unsigned i;
570 tree phi, lop;
571 basic_block bb;
573 /* Find the candidate for the latch edge. */
574 for (i = 1; VEC_iterate (edge, latches, i, e); i++)
575 if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src))
576 latch = e;
578 /* Verify that it dominates all the latch edges. */
579 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
580 if (!dominated_by_p (CDI_DOMINATORS, e->src, latch->src))
581 return NULL;
583 /* Check for a phi node that would deny that this is a latch edge of
584 a subloop. */
585 for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
587 lop = PHI_ARG_DEF_FROM_EDGE (phi, latch);
589 /* Ignore the values that are not changed inside the subloop. */
590 if (TREE_CODE (lop) != SSA_NAME
591 || SSA_NAME_DEF_STMT (lop) == phi)
592 continue;
593 bb = bb_for_stmt (SSA_NAME_DEF_STMT (lop));
594 if (!bb || !flow_bb_inside_loop_p (loop, bb))
595 continue;
597 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
598 if (e != latch
599 && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop)
600 return NULL;
603 if (dump_file)
604 fprintf (dump_file,
605 "Found latch edge %d -> %d using iv structure.\n",
606 latch->src->index, latch->dest->index);
607 return latch;
610 /* If we can determine that one of the several latch edges of LOOP behaves
611 as a latch edge of a separate subloop, returns this edge. Otherwise
612 returns NULL. */
614 static edge
615 find_subloop_latch_edge (struct loop *loop)
617 VEC (edge, heap) *latches = get_loop_latch_edges (loop);
618 edge latch = NULL;
620 if (VEC_length (edge, latches) > 1)
622 latch = find_subloop_latch_edge_by_profile (latches);
624 if (!latch
625 /* We consider ivs to guess the latch edge only in SSA. Perhaps we
626 should use cfghook for this, but it is hard to imagine it would
627 be useful elsewhere. */
628 && current_ir_type () == IR_GIMPLE)
629 latch = find_subloop_latch_edge_by_ivs (loop, latches);
632 VEC_free (edge, heap, latches);
633 return latch;
636 /* Callback for make_forwarder_block. Returns true if the edge E is marked
637 in the set MFB_REIS_SET. */
639 static struct pointer_set_t *mfb_reis_set;
640 static bool
641 mfb_redirect_edges_in_set (edge e)
643 return pointer_set_contains (mfb_reis_set, e);
646 /* Creates a subloop of LOOP with latch edge LATCH. */
648 static void
649 form_subloop (struct loop *loop, edge latch)
651 edge_iterator ei;
652 edge e, new_entry;
653 struct loop *new_loop;
655 mfb_reis_set = pointer_set_create ();
656 FOR_EACH_EDGE (e, ei, loop->header->preds)
658 if (e != latch)
659 pointer_set_insert (mfb_reis_set, e);
661 new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
662 NULL);
663 pointer_set_destroy (mfb_reis_set);
665 loop->header = new_entry->src;
667 /* Find the blocks and subloops that belong to the new loop, and add it to
668 the appropriate place in the loop tree. */
669 new_loop = alloc_loop ();
670 new_loop->header = new_entry->dest;
671 new_loop->latch = latch->src;
672 add_loop (new_loop, loop);
675 /* Make all the latch edges of LOOP to go to a single forwarder block --
676 a new latch of LOOP. */
678 static void
679 merge_latch_edges (struct loop *loop)
681 VEC (edge, heap) *latches = get_loop_latch_edges (loop);
682 edge latch, e;
683 unsigned i;
685 gcc_assert (VEC_length (edge, latches) > 0);
687 if (VEC_length (edge, latches) == 1)
688 loop->latch = VEC_index (edge, latches, 0)->src;
689 else
691 if (dump_file)
692 fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num);
694 mfb_reis_set = pointer_set_create ();
695 for (i = 0; VEC_iterate (edge, latches, i, e); i++)
696 pointer_set_insert (mfb_reis_set, e);
697 latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
698 NULL);
699 pointer_set_destroy (mfb_reis_set);
701 loop->header = latch->dest;
702 loop->latch = latch->src;
705 VEC_free (edge, heap, latches);
708 /* LOOP may have several latch edges. Transform it into (possibly several)
709 loops with single latch edge. */
711 static void
712 disambiguate_multiple_latches (struct loop *loop)
714 edge e;
716 /* We eliminate the multiple latches by splitting the header to the forwarder
717 block F and the rest R, and redirecting the edges. There are two cases:
719 1) If there is a latch edge E that corresponds to a subloop (we guess
720 that based on profile -- if it is taken much more often than the
721 remaining edges; and on trees, using the information about induction
722 variables of the loops), we redirect E to R, all the remaining edges to
723 F, then rescan the loops and try again for the outer loop.
724 2) If there is no such edge, we redirect all latch edges to F, and the
725 entry edges to R, thus making F the single latch of the loop. */
727 if (dump_file)
728 fprintf (dump_file, "Disambiguating loop %d with multiple latches\n",
729 loop->num);
731 /* During latch merging, we may need to redirect the entry edges to a new
732 block. This would cause problems if the entry edge was the one from the
733 entry block. To avoid having to handle this case specially, split
734 such entry edge. */
735 e = find_edge (ENTRY_BLOCK_PTR, loop->header);
736 if (e)
737 split_edge (e);
739 while (1)
741 e = find_subloop_latch_edge (loop);
742 if (!e)
743 break;
745 form_subloop (loop, e);
748 merge_latch_edges (loop);
751 /* Split loops with multiple latch edges. */
753 void
754 disambiguate_loops_with_multiple_latches (void)
756 loop_iterator li;
757 struct loop *loop;
759 FOR_EACH_LOOP (li, loop, 0)
761 if (!loop->latch)
762 disambiguate_multiple_latches (loop);
766 /* Return nonzero if basic block BB belongs to LOOP. */
767 bool
768 flow_bb_inside_loop_p (const struct loop *loop, const_basic_block bb)
770 struct loop *source_loop;
772 if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
773 return 0;
775 source_loop = bb->loop_father;
776 return loop == source_loop || flow_loop_nested_p (loop, source_loop);
779 /* Enumeration predicate for get_loop_body_with_size. */
780 static bool
781 glb_enum_p (const_basic_block bb, const void *glb_loop)
783 const struct loop *const loop = (const struct loop *) glb_loop;
784 return (bb != loop->header
785 && dominated_by_p (CDI_DOMINATORS, bb, loop->header));
788 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
789 order against direction of edges from latch. Specially, if
790 header != latch, latch is the 1-st block. LOOP cannot be the fake
791 loop tree root, and its size must be at most MAX_SIZE. The blocks
792 in the LOOP body are stored to BODY, and the size of the LOOP is
793 returned. */
795 unsigned
796 get_loop_body_with_size (const struct loop *loop, basic_block *body,
797 unsigned max_size)
799 return dfs_enumerate_from (loop->header, 1, glb_enum_p,
800 body, max_size, loop);
803 /* Gets basic blocks of a LOOP. Header is the 0-th block, rest is in dfs
804 order against direction of edges from latch. Specially, if
805 header != latch, latch is the 1-st block. */
807 basic_block *
808 get_loop_body (const struct loop *loop)
810 basic_block *body, bb;
811 unsigned tv = 0;
813 gcc_assert (loop->num_nodes);
815 body = XCNEWVEC (basic_block, loop->num_nodes);
817 if (loop->latch == EXIT_BLOCK_PTR)
819 /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
820 special-case the fake loop that contains the whole function. */
821 gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks);
822 body[tv++] = loop->header;
823 body[tv++] = EXIT_BLOCK_PTR;
824 FOR_EACH_BB (bb)
825 body[tv++] = bb;
827 else
828 tv = get_loop_body_with_size (loop, body, loop->num_nodes);
830 gcc_assert (tv == loop->num_nodes);
831 return body;
834 /* Fills dominance descendants inside LOOP of the basic block BB into
835 array TOVISIT from index *TV. */
837 static void
838 fill_sons_in_loop (const struct loop *loop, basic_block bb,
839 basic_block *tovisit, int *tv)
841 basic_block son, postpone = NULL;
843 tovisit[(*tv)++] = bb;
844 for (son = first_dom_son (CDI_DOMINATORS, bb);
845 son;
846 son = next_dom_son (CDI_DOMINATORS, son))
848 if (!flow_bb_inside_loop_p (loop, son))
849 continue;
851 if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
853 postpone = son;
854 continue;
856 fill_sons_in_loop (loop, son, tovisit, tv);
859 if (postpone)
860 fill_sons_in_loop (loop, postpone, tovisit, tv);
863 /* Gets body of a LOOP (that must be different from the outermost loop)
864 sorted by dominance relation. Additionally, if a basic block s dominates
865 the latch, then only blocks dominated by s are be after it. */
867 basic_block *
868 get_loop_body_in_dom_order (const struct loop *loop)
870 basic_block *tovisit;
871 int tv;
873 gcc_assert (loop->num_nodes);
875 tovisit = XCNEWVEC (basic_block, loop->num_nodes);
877 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
879 tv = 0;
880 fill_sons_in_loop (loop, loop->header, tovisit, &tv);
882 gcc_assert (tv == (int) loop->num_nodes);
884 return tovisit;
887 /* Get body of a LOOP in breadth first sort order. */
889 basic_block *
890 get_loop_body_in_bfs_order (const struct loop *loop)
892 basic_block *blocks;
893 basic_block bb;
894 bitmap visited;
895 unsigned int i = 0;
896 unsigned int vc = 1;
898 gcc_assert (loop->num_nodes);
899 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
901 blocks = XCNEWVEC (basic_block, loop->num_nodes);
902 visited = BITMAP_ALLOC (NULL);
904 bb = loop->header;
905 while (i < loop->num_nodes)
907 edge e;
908 edge_iterator ei;
910 if (!bitmap_bit_p (visited, bb->index))
912 /* This basic block is now visited */
913 bitmap_set_bit (visited, bb->index);
914 blocks[i++] = bb;
917 FOR_EACH_EDGE (e, ei, bb->succs)
919 if (flow_bb_inside_loop_p (loop, e->dest))
921 if (!bitmap_bit_p (visited, e->dest->index))
923 bitmap_set_bit (visited, e->dest->index);
924 blocks[i++] = e->dest;
929 gcc_assert (i >= vc);
931 bb = blocks[vc++];
934 BITMAP_FREE (visited);
935 return blocks;
938 /* Hash function for struct loop_exit. */
940 static hashval_t
941 loop_exit_hash (const void *ex)
943 const struct loop_exit *const exit = (const struct loop_exit *) ex;
945 return htab_hash_pointer (exit->e);
948 /* Equality function for struct loop_exit. Compares with edge. */
950 static int
951 loop_exit_eq (const void *ex, const void *e)
953 const struct loop_exit *const exit = (const struct loop_exit *) ex;
955 return exit->e == e;
958 /* Frees the list of loop exit descriptions EX. */
960 static void
961 loop_exit_free (void *ex)
963 struct loop_exit *exit = (struct loop_exit *) ex, *next;
965 for (; exit; exit = next)
967 next = exit->next_e;
969 exit->next->prev = exit->prev;
970 exit->prev->next = exit->next;
972 ggc_free (exit);
976 /* Returns the list of records for E as an exit of a loop. */
978 static struct loop_exit *
979 get_exit_descriptions (edge e)
981 return (struct loop_exit *) htab_find_with_hash (current_loops->exits, e,
982 htab_hash_pointer (e));
985 /* Updates the lists of loop exits in that E appears.
986 If REMOVED is true, E is being removed, and we
987 just remove it from the lists of exits.
988 If NEW_EDGE is true and E is not a loop exit, we
989 do not try to remove it from loop exit lists. */
991 void
992 rescan_loop_exit (edge e, bool new_edge, bool removed)
994 void **slot;
995 struct loop_exit *exits = NULL, *exit;
996 struct loop *aloop, *cloop;
998 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
999 return;
1001 if (!removed
1002 && e->src->loop_father != NULL
1003 && e->dest->loop_father != NULL
1004 && !flow_bb_inside_loop_p (e->src->loop_father, e->dest))
1006 cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
1007 for (aloop = e->src->loop_father;
1008 aloop != cloop;
1009 aloop = loop_outer (aloop))
1011 exit = GGC_NEW (struct loop_exit);
1012 exit->e = e;
1014 exit->next = aloop->exits->next;
1015 exit->prev = aloop->exits;
1016 exit->next->prev = exit;
1017 exit->prev->next = exit;
1019 exit->next_e = exits;
1020 exits = exit;
1024 if (!exits && new_edge)
1025 return;
1027 slot = htab_find_slot_with_hash (current_loops->exits, e,
1028 htab_hash_pointer (e),
1029 exits ? INSERT : NO_INSERT);
1030 if (!slot)
1031 return;
1033 if (exits)
1035 if (*slot)
1036 loop_exit_free (*slot);
1037 *slot = exits;
1039 else
1040 htab_clear_slot (current_loops->exits, slot);
1043 /* For each loop, record list of exit edges, and start maintaining these
1044 lists. */
1046 void
1047 record_loop_exits (void)
1049 basic_block bb;
1050 edge_iterator ei;
1051 edge e;
1053 if (!current_loops)
1054 return;
1056 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1057 return;
1058 loops_state_set (LOOPS_HAVE_RECORDED_EXITS);
1060 gcc_assert (current_loops->exits == NULL);
1061 current_loops->exits = htab_create_alloc (2 * number_of_loops (),
1062 loop_exit_hash,
1063 loop_exit_eq,
1064 loop_exit_free,
1065 ggc_calloc, ggc_free);
1067 FOR_EACH_BB (bb)
1069 FOR_EACH_EDGE (e, ei, bb->succs)
1071 rescan_loop_exit (e, true, false);
1076 /* Dumps information about the exit in *SLOT to FILE.
1077 Callback for htab_traverse. */
1079 static int
1080 dump_recorded_exit (void **slot, void *file)
1082 struct loop_exit *exit = (struct loop_exit *) *slot;
1083 unsigned n = 0;
1084 edge e = exit->e;
1086 for (; exit != NULL; exit = exit->next_e)
1087 n++;
1089 fprintf ((FILE*) file, "Edge %d->%d exits %u loops\n",
1090 e->src->index, e->dest->index, n);
1092 return 1;
1095 /* Dumps the recorded exits of loops to FILE. */
1097 extern void dump_recorded_exits (FILE *);
1098 void
1099 dump_recorded_exits (FILE *file)
1101 if (!current_loops->exits)
1102 return;
1103 htab_traverse (current_loops->exits, dump_recorded_exit, file);
1106 /* Releases lists of loop exits. */
1108 void
1109 release_recorded_exits (void)
1111 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS));
1112 htab_delete (current_loops->exits);
1113 current_loops->exits = NULL;
1114 loops_state_clear (LOOPS_HAVE_RECORDED_EXITS);
1117 /* Returns the list of the exit edges of a LOOP. */
1119 VEC (edge, heap) *
1120 get_loop_exit_edges (const struct loop *loop)
1122 VEC (edge, heap) *edges = NULL;
1123 edge e;
1124 unsigned i;
1125 basic_block *body;
1126 edge_iterator ei;
1127 struct loop_exit *exit;
1129 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1131 /* If we maintain the lists of exits, use them. Otherwise we must
1132 scan the body of the loop. */
1133 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1135 for (exit = loop->exits->next; exit->e; exit = exit->next)
1136 VEC_safe_push (edge, heap, edges, exit->e);
1138 else
1140 body = get_loop_body (loop);
1141 for (i = 0; i < loop->num_nodes; i++)
1142 FOR_EACH_EDGE (e, ei, body[i]->succs)
1144 if (!flow_bb_inside_loop_p (loop, e->dest))
1145 VEC_safe_push (edge, heap, edges, e);
1147 free (body);
1150 return edges;
1153 /* Counts the number of conditional branches inside LOOP. */
1155 unsigned
1156 num_loop_branches (const struct loop *loop)
1158 unsigned i, n;
1159 basic_block * body;
1161 gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1163 body = get_loop_body (loop);
1164 n = 0;
1165 for (i = 0; i < loop->num_nodes; i++)
1166 if (EDGE_COUNT (body[i]->succs) >= 2)
1167 n++;
1168 free (body);
1170 return n;
1173 /* Adds basic block BB to LOOP. */
1174 void
1175 add_bb_to_loop (basic_block bb, struct loop *loop)
1177 unsigned i;
1178 loop_p ploop;
1179 edge_iterator ei;
1180 edge e;
1182 gcc_assert (bb->loop_father == NULL);
1183 bb->loop_father = loop;
1184 bb->loop_depth = loop_depth (loop);
1185 loop->num_nodes++;
1186 for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++)
1187 ploop->num_nodes++;
1189 FOR_EACH_EDGE (e, ei, bb->succs)
1191 rescan_loop_exit (e, true, false);
1193 FOR_EACH_EDGE (e, ei, bb->preds)
1195 rescan_loop_exit (e, true, false);
1199 /* Remove basic block BB from loops. */
1200 void
1201 remove_bb_from_loops (basic_block bb)
1203 int i;
1204 struct loop *loop = bb->loop_father;
1205 loop_p ploop;
1206 edge_iterator ei;
1207 edge e;
1209 gcc_assert (loop != NULL);
1210 loop->num_nodes--;
1211 for (i = 0; VEC_iterate (loop_p, loop->superloops, i, ploop); i++)
1212 ploop->num_nodes--;
1213 bb->loop_father = NULL;
1214 bb->loop_depth = 0;
1216 FOR_EACH_EDGE (e, ei, bb->succs)
1218 rescan_loop_exit (e, false, true);
1220 FOR_EACH_EDGE (e, ei, bb->preds)
1222 rescan_loop_exit (e, false, true);
1226 /* Finds nearest common ancestor in loop tree for given loops. */
1227 struct loop *
1228 find_common_loop (struct loop *loop_s, struct loop *loop_d)
1230 unsigned sdepth, ddepth;
1232 if (!loop_s) return loop_d;
1233 if (!loop_d) return loop_s;
1235 sdepth = loop_depth (loop_s);
1236 ddepth = loop_depth (loop_d);
1238 if (sdepth < ddepth)
1239 loop_d = VEC_index (loop_p, loop_d->superloops, sdepth);
1240 else if (sdepth > ddepth)
1241 loop_s = VEC_index (loop_p, loop_s->superloops, ddepth);
1243 while (loop_s != loop_d)
1245 loop_s = loop_outer (loop_s);
1246 loop_d = loop_outer (loop_d);
1248 return loop_s;
1251 /* Removes LOOP from structures and frees its data. */
1253 void
1254 delete_loop (struct loop *loop)
1256 /* Remove the loop from structure. */
1257 flow_loop_tree_node_remove (loop);
1259 /* Remove loop from loops array. */
1260 VEC_replace (loop_p, current_loops->larray, loop->num, NULL);
1262 /* Free loop data. */
1263 flow_loop_free (loop);
1266 /* Cancels the LOOP; it must be innermost one. */
1268 static void
1269 cancel_loop (struct loop *loop)
1271 basic_block *bbs;
1272 unsigned i;
1273 struct loop *outer = loop_outer (loop);
1275 gcc_assert (!loop->inner);
1277 /* Move blocks up one level (they should be removed as soon as possible). */
1278 bbs = get_loop_body (loop);
1279 for (i = 0; i < loop->num_nodes; i++)
1280 bbs[i]->loop_father = outer;
1282 delete_loop (loop);
1285 /* Cancels LOOP and all its subloops. */
1286 void
1287 cancel_loop_tree (struct loop *loop)
1289 while (loop->inner)
1290 cancel_loop_tree (loop->inner);
1291 cancel_loop (loop);
1294 /* Checks that information about loops is correct
1295 -- sizes of loops are all right
1296 -- results of get_loop_body really belong to the loop
1297 -- loop header have just single entry edge and single latch edge
1298 -- loop latches have only single successor that is header of their loop
1299 -- irreducible loops are correctly marked
1301 void
1302 verify_loop_structure (void)
1304 unsigned *sizes, i, j;
1305 sbitmap irreds;
1306 basic_block *bbs, bb;
1307 struct loop *loop;
1308 int err = 0;
1309 edge e;
1310 unsigned num = number_of_loops ();
1311 loop_iterator li;
1312 struct loop_exit *exit, *mexit;
1314 /* Check sizes. */
1315 sizes = XCNEWVEC (unsigned, num);
1316 sizes[0] = 2;
1318 FOR_EACH_BB (bb)
1319 for (loop = bb->loop_father; loop; loop = loop_outer (loop))
1320 sizes[loop->num]++;
1322 FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
1324 i = loop->num;
1326 if (loop->num_nodes != sizes[i])
1328 error ("size of loop %d should be %d, not %d",
1329 i, sizes[i], loop->num_nodes);
1330 err = 1;
1334 /* Check get_loop_body. */
1335 FOR_EACH_LOOP (li, loop, 0)
1337 bbs = get_loop_body (loop);
1339 for (j = 0; j < loop->num_nodes; j++)
1340 if (!flow_bb_inside_loop_p (loop, bbs[j]))
1342 error ("bb %d do not belong to loop %d",
1343 bbs[j]->index, loop->num);
1344 err = 1;
1346 free (bbs);
1349 /* Check headers and latches. */
1350 FOR_EACH_LOOP (li, loop, 0)
1352 i = loop->num;
1354 if (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS)
1355 && EDGE_COUNT (loop->header->preds) != 2)
1357 error ("loop %d's header does not have exactly 2 entries", i);
1358 err = 1;
1360 if (loops_state_satisfies_p (LOOPS_HAVE_SIMPLE_LATCHES))
1362 if (!single_succ_p (loop->latch))
1364 error ("loop %d's latch does not have exactly 1 successor", i);
1365 err = 1;
1367 if (single_succ (loop->latch) != loop->header)
1369 error ("loop %d's latch does not have header as successor", i);
1370 err = 1;
1372 if (loop->latch->loop_father != loop)
1374 error ("loop %d's latch does not belong directly to it", i);
1375 err = 1;
1378 if (loop->header->loop_father != loop)
1380 error ("loop %d's header does not belong directly to it", i);
1381 err = 1;
1383 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1384 && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
1386 error ("loop %d's latch is marked as part of irreducible region", i);
1387 err = 1;
1391 /* Check irreducible loops. */
1392 if (loops_state_satisfies_p (LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1394 /* Record old info. */
1395 irreds = sbitmap_alloc (last_basic_block);
1396 FOR_EACH_BB (bb)
1398 edge_iterator ei;
1399 if (bb->flags & BB_IRREDUCIBLE_LOOP)
1400 SET_BIT (irreds, bb->index);
1401 else
1402 RESET_BIT (irreds, bb->index);
1403 FOR_EACH_EDGE (e, ei, bb->succs)
1404 if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1405 e->flags |= EDGE_ALL_FLAGS + 1;
1408 /* Recount it. */
1409 mark_irreducible_loops ();
1411 /* Compare. */
1412 FOR_EACH_BB (bb)
1414 edge_iterator ei;
1416 if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1417 && !TEST_BIT (irreds, bb->index))
1419 error ("basic block %d should be marked irreducible", bb->index);
1420 err = 1;
1422 else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1423 && TEST_BIT (irreds, bb->index))
1425 error ("basic block %d should not be marked irreducible", bb->index);
1426 err = 1;
1428 FOR_EACH_EDGE (e, ei, bb->succs)
1430 if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1431 && !(e->flags & (EDGE_ALL_FLAGS + 1)))
1433 error ("edge from %d to %d should be marked irreducible",
1434 e->src->index, e->dest->index);
1435 err = 1;
1437 else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1438 && (e->flags & (EDGE_ALL_FLAGS + 1)))
1440 error ("edge from %d to %d should not be marked irreducible",
1441 e->src->index, e->dest->index);
1442 err = 1;
1444 e->flags &= ~(EDGE_ALL_FLAGS + 1);
1447 free (irreds);
1450 /* Check the recorded loop exits. */
1451 FOR_EACH_LOOP (li, loop, 0)
1453 if (!loop->exits || loop->exits->e != NULL)
1455 error ("corrupted head of the exits list of loop %d",
1456 loop->num);
1457 err = 1;
1459 else
1461 /* Check that the list forms a cycle, and all elements except
1462 for the head are nonnull. */
1463 for (mexit = loop->exits, exit = mexit->next, i = 0;
1464 exit->e && exit != mexit;
1465 exit = exit->next)
1467 if (i++ & 1)
1468 mexit = mexit->next;
1471 if (exit != loop->exits)
1473 error ("corrupted exits list of loop %d", loop->num);
1474 err = 1;
1478 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1480 if (loop->exits->next != loop->exits)
1482 error ("nonempty exits list of loop %d, but exits are not recorded",
1483 loop->num);
1484 err = 1;
1489 if (loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1491 unsigned n_exits = 0, eloops;
1493 memset (sizes, 0, sizeof (unsigned) * num);
1494 FOR_EACH_BB (bb)
1496 edge_iterator ei;
1497 if (bb->loop_father == current_loops->tree_root)
1498 continue;
1499 FOR_EACH_EDGE (e, ei, bb->succs)
1501 if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
1502 continue;
1504 n_exits++;
1505 exit = get_exit_descriptions (e);
1506 if (!exit)
1508 error ("Exit %d->%d not recorded",
1509 e->src->index, e->dest->index);
1510 err = 1;
1512 eloops = 0;
1513 for (; exit; exit = exit->next_e)
1514 eloops++;
1516 for (loop = bb->loop_father;
1517 loop != e->dest->loop_father;
1518 loop = loop_outer (loop))
1520 eloops--;
1521 sizes[loop->num]++;
1524 if (eloops != 0)
1526 error ("Wrong list of exited loops for edge %d->%d",
1527 e->src->index, e->dest->index);
1528 err = 1;
1533 if (n_exits != htab_elements (current_loops->exits))
1535 error ("Too many loop exits recorded");
1536 err = 1;
1539 FOR_EACH_LOOP (li, loop, 0)
1541 eloops = 0;
1542 for (exit = loop->exits->next; exit->e; exit = exit->next)
1543 eloops++;
1544 if (eloops != sizes[loop->num])
1546 error ("%d exits recorded for loop %d (having %d exits)",
1547 eloops, loop->num, sizes[loop->num]);
1548 err = 1;
1553 gcc_assert (!err);
1555 free (sizes);
1558 /* Returns latch edge of LOOP. */
1559 edge
1560 loop_latch_edge (const struct loop *loop)
1562 return find_edge (loop->latch, loop->header);
1565 /* Returns preheader edge of LOOP. */
1566 edge
1567 loop_preheader_edge (const struct loop *loop)
1569 edge e;
1570 edge_iterator ei;
1572 gcc_assert (loops_state_satisfies_p (LOOPS_HAVE_PREHEADERS));
1574 FOR_EACH_EDGE (e, ei, loop->header->preds)
1575 if (e->src != loop->latch)
1576 break;
1578 return e;
1581 /* Returns true if E is an exit of LOOP. */
1583 bool
1584 loop_exit_edge_p (const struct loop *loop, const_edge e)
1586 return (flow_bb_inside_loop_p (loop, e->src)
1587 && !flow_bb_inside_loop_p (loop, e->dest));
1590 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1591 or more than one exit. If loops do not have the exits recorded, NULL
1592 is returned always. */
1594 edge
1595 single_exit (const struct loop *loop)
1597 struct loop_exit *exit = loop->exits->next;
1599 if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
1600 return NULL;
1602 if (exit->e && exit->next == loop->exits)
1603 return exit->e;
1604 else
1605 return NULL;