gcc/cfgloop.c

   1 /* Natural loop discovery code for GNU compiler.
   2    Copyright (C) 2000, 2001, 2003, 2004, 2005 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, USA.  */
  20
  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
  38 static void flow_loops_cfg_dump (FILE *);
  39 static void establish_preds (struct loop *);
  40 \f
  41 /* Dump loop related CFG information.  */
  42
  43 static void
  44 flow_loops_cfg_dump (FILE *file)
  45 {
  46   basic_block bb;
  47
  48   if (!file)
  49     return;
  50
  51   FOR_EACH_BB (bb)
  52     {
  53       edge succ;
  54       edge_iterator ei;
  55
  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");
  60     }
  61 }
  62
  63 /* Return nonzero if the nodes of LOOP are a subset of OUTER.  */
  64
  65 bool
  66 flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
  67 {
  68   return (loop->depth > outer->depth
  69          && loop->pred[outer->depth] == outer);
  70 }
  71
  72 /* Returns the loop such that LOOP is nested DEPTH (indexed from zero)
  73    loops within LOOP.  */
  74
  75 struct loop *
  76 superloop_at_depth (struct loop *loop, unsigned depth)
  77 {
  78   gcc_assert (depth <= (unsigned) loop->depth);
  79
  80   if (depth == (unsigned) loop->depth)
  81     return loop;
  82
  83   return loop->pred[depth];
  84 }
  85
  86 /* Returns the list of the latch edges of LOOP.  */
  87
  88 static VEC (edge, heap) *
  89 get_loop_latch_edges (const struct loop *loop)
  90 {
  91   edge_iterator ei;
  92   edge e;
  93   VEC (edge, heap) *ret = NULL;
  94
  95   FOR_EACH_EDGE (e, ei, loop->header->preds)
  96     {
  97       if (dominated_by_p (CDI_DOMINATORS, e->src, loop->header))
  98         VEC_safe_push (edge, heap, ret, e);
  99     }
 100
 101   return ret;
 102 }
 103
 104 /* Dump the loop information specified by LOOP to the stream FILE
 105    using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
 106
 107 void
 108 flow_loop_dump (const struct loop *loop, FILE *file,
 109                 void (*loop_dump_aux) (const struct loop *, FILE *, int),
 110                 int verbose)
 111 {
 112   basic_block *bbs;
 113   unsigned i;
 114   VEC (edge, heap) *latches;
 115   edge e;
 116
 117   if (! loop || ! loop->header)
 118     return;
 119
 120   fprintf (file, ";;\n;; Loop %d\n", loop->num);
 121
 122   fprintf (file, ";;  header %d, ", loop->header->index);
 123   if (loop->latch)
 124     fprintf (file, "latch %d\n", loop->latch->index);
 125   else
 126     {
 127       fprintf (file, "multiple latches:");
 128       latches = get_loop_latch_edges (loop);
 129       for (i = 0; VEC_iterate (edge, latches, i, e); i++)
 130         fprintf (file, " %d", e->src->index);
 131       VEC_free (edge, heap, latches);
 132       fprintf (file, "\n");
 133     }
 134
 135   fprintf (file, ";;  depth %d, outer %ld\n",
 136            loop->depth, (long) (loop->outer ? loop->outer->num : -1));
 137
 138   fprintf (file, ";;  nodes:");
 139   bbs = get_loop_body (loop);
 140   for (i = 0; i < loop->num_nodes; i++)
 141     fprintf (file, " %d", bbs[i]->index);
 142   free (bbs);
 143   fprintf (file, "\n");
 144
 145   if (loop_dump_aux)
 146     loop_dump_aux (loop, file, verbose);
 147 }
 148
 149 /* Dump the loop information about loops to the stream FILE,
 150    using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
 151
 152 void
 153 flow_loops_dump (FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
 154 {
 155   loop_iterator li;
 156   struct loop *loop;
 157
 158   if (!current_loops || ! file)
 159     return;
 160
 161   fprintf (file, ";; %d loops found\n", number_of_loops ());
 162
 163   FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
 164     {
 165       flow_loop_dump (loop, file, loop_dump_aux, verbose);
 166     }
 167
 168   if (verbose)
 169     flow_loops_cfg_dump (file);
 170 }
 171
 172 /* Free data allocated for LOOP.  */
 173 void
 174 flow_loop_free (struct loop *loop)
 175 {
 176   struct loop_exit *exit, *next;
 177
 178   if (loop->pred)
 179     free (loop->pred);
 180
 181   /* Break the list of the loop exit records.  They will be freed when the
 182      corresponding edge is rescanned or removed, and this avoids
 183      accessing the (already released) head of the list stored in the
 184      loop structure.  */
 185   for (exit = loop->exits.next; exit != &loop->exits; exit = next)
 186     {
 187       next = exit->next;
 188       exit->next = exit;
 189       exit->prev = exit;
 190     }
 191
 192   free (loop);
 193 }
 194
 195 /* Free all the memory allocated for LOOPS.  */
 196
 197 void
 198 flow_loops_free (struct loops *loops)
 199 {
 200   if (loops->larray)
 201     {
 202       unsigned i;
 203       loop_p loop;
 204
 205       /* Free the loop descriptors.  */
 206       for (i = 0; VEC_iterate (loop_p, loops->larray, i, loop); i++)
 207         {
 208           if (!loop)
 209             continue;
 210
 211           flow_loop_free (loop);
 212         }
 213
 214       VEC_free (loop_p, heap, loops->larray);
 215       loops->larray = NULL;
 216     }
 217 }
 218
 219 /* Find the nodes contained within the LOOP with header HEADER.
 220    Return the number of nodes within the loop.  */
 221
 222 int
 223 flow_loop_nodes_find (basic_block header, struct loop *loop)
 224 {
 225   VEC (basic_block, heap) *stack = NULL;
 226   int num_nodes = 1;
 227   edge latch;
 228   edge_iterator latch_ei;
 229
 230   header->loop_father = loop;
 231   header->loop_depth = loop->depth;
 232
 233   FOR_EACH_EDGE (latch, latch_ei, loop->header->preds)
 234     {
 235       if (latch->src->loop_father == loop
 236           || !dominated_by_p (CDI_DOMINATORS, latch->src, loop->header))
 237         continue;
 238
 239       num_nodes++;
 240       VEC_safe_push (basic_block, heap, stack, latch->src);
 241       latch->src->loop_father = loop;
 242       latch->src->loop_depth = loop->depth;
 243
 244       while (!VEC_empty (basic_block, stack))
 245         {
 246           basic_block node;
 247           edge e;
 248           edge_iterator ei;
 249
 250           node = VEC_pop (basic_block, stack);
 251
 252           FOR_EACH_EDGE (e, ei, node->preds)
 253             {
 254               basic_block ancestor = e->src;
 255
 256               if (ancestor->loop_father != loop)
 257                 {
 258                   ancestor->loop_father = loop;
 259                   ancestor->loop_depth = loop->depth;
 260                   num_nodes++;
 261                   VEC_safe_push (basic_block, heap, stack, ancestor);
 262                 }
 263             }
 264         }
 265     }
 266   VEC_free (basic_block, heap, stack);
 267
 268   return num_nodes;
 269 }
 270
 271 static void
 272 establish_preds (struct loop *loop)
 273 {
 274   struct loop *ploop, *father = loop->outer;
 275
 276   loop->depth = father->depth + 1;
 277
 278   /* Remember the current loop depth if it is the largest seen so far.  */
 279   cfun->max_loop_depth = MAX (cfun->max_loop_depth, loop->depth);
 280
 281   if (loop->pred)
 282     free (loop->pred);
 283   loop->pred = XNEWVEC (struct loop *, loop->depth);
 284   memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth);
 285   loop->pred[father->depth] = father;
 286
 287   for (ploop = loop->inner; ploop; ploop = ploop->next)
 288     establish_preds (ploop);
 289 }
 290
 291 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
 292    added loop.  If LOOP has some children, take care of that their
 293    pred field will be initialized correctly.  */
 294
 295 void
 296 flow_loop_tree_node_add (struct loop *father, struct loop *loop)
 297 {
 298   loop->next = father->inner;
 299   father->inner = loop;
 300   loop->outer = father;
 301
 302   establish_preds (loop);
 303 }
 304
 305 /* Remove LOOP from the loop hierarchy tree.  */
 306
 307 void
 308 flow_loop_tree_node_remove (struct loop *loop)
 309 {
 310   struct loop *prev, *father;
 311
 312   father = loop->outer;
 313   loop->outer = NULL;
 314
 315   /* Remove loop from the list of sons.  */
 316   if (father->inner == loop)
 317     father->inner = loop->next;
 318   else
 319     {
 320       for (prev = father->inner; prev->next != loop; prev = prev->next);
 321       prev->next = loop->next;
 322     }
 323
 324   loop->depth = -1;
 325   free (loop->pred);
 326   loop->pred = NULL;
 327 }
 328
 329 /* Allocates and returns new loop structure.  */
 330
 331 struct loop *
 332 alloc_loop (void)
 333 {
 334   struct loop *loop = XCNEW (struct loop);
 335
 336   loop->exits.next = loop->exits.prev = &loop->exits;
 337   return loop;
 338 }
 339
 340 /* Find all the natural loops in the function and save in LOOPS structure and
 341    recalculate loop_depth information in basic block structures.
 342    Return the number of natural loops found.  */
 343
 344 int
 345 flow_loops_find (struct loops *loops)
 346 {
 347   int b;
 348   int num_loops;
 349   edge e;
 350   sbitmap headers;
 351   int *dfs_order;
 352   int *rc_order;
 353   basic_block header;
 354   basic_block bb;
 355   struct loop *root;
 356
 357   memset (loops, 0, sizeof *loops);
 358
 359   /* We are going to recount the maximum loop depth,
 360      so throw away the last count.  */
 361   cfun->max_loop_depth = 0;
 362
 363   /* Taking care of this degenerate case makes the rest of
 364      this code simpler.  */
 365   if (n_basic_blocks == NUM_FIXED_BLOCKS)
 366     return 0;
 367
 368   dfs_order = NULL;
 369   rc_order = NULL;
 370
 371   /* Ensure that the dominators are computed.  */
 372   calculate_dominance_info (CDI_DOMINATORS);
 373
 374   /* Count the number of loop headers.  This should be the
 375      same as the number of natural loops.  */
 376   headers = sbitmap_alloc (last_basic_block);
 377   sbitmap_zero (headers);
 378
 379   num_loops = 0;
 380   FOR_EACH_BB (header)
 381     {
 382       edge_iterator ei;
 383
 384       header->loop_depth = 0;
 385
 386       /* If we have an abnormal predecessor, do not consider the
 387          loop (not worth the problems).  */
 388       FOR_EACH_EDGE (e, ei, header->preds)
 389         if (e->flags & EDGE_ABNORMAL)
 390           break;
 391       if (e)
 392         continue;
 393
 394       FOR_EACH_EDGE (e, ei, header->preds)
 395         {
 396           basic_block latch = e->src;
 397
 398           gcc_assert (!(e->flags & EDGE_ABNORMAL));
 399
 400           /* Look for back edges where a predecessor is dominated
 401              by this block.  A natural loop has a single entry
 402              node (header) that dominates all the nodes in the
 403              loop.  It also has single back edge to the header
 404              from a latch node.  */
 405           if (latch != ENTRY_BLOCK_PTR
 406               && dominated_by_p (CDI_DOMINATORS, latch, header))
 407             {
 408               /* Shared headers should be eliminated by now.  */
 409               SET_BIT (headers, header->index);
 410               num_loops++;
 411             }
 412         }
 413     }
 414
 415   /* Allocate loop structures.  */
 416   loops->larray = VEC_alloc (loop_p, heap, num_loops + 1);
 417
 418   /* Dummy loop containing whole function.  */
 419   root = alloc_loop ();
 420   root->num_nodes = n_basic_blocks;
 421   root->latch = EXIT_BLOCK_PTR;
 422   root->header = ENTRY_BLOCK_PTR;
 423   ENTRY_BLOCK_PTR->loop_father = root;
 424   EXIT_BLOCK_PTR->loop_father = root;
 425
 426   VEC_quick_push (loop_p, loops->larray, root);
 427   loops->tree_root = root;
 428
 429   /* Find and record information about all the natural loops
 430      in the CFG.  */
 431   FOR_EACH_BB (bb)
 432     bb->loop_father = loops->tree_root;
 433
 434   if (num_loops)
 435     {
 436       /* Compute depth first search order of the CFG so that outer
 437          natural loops will be found before inner natural loops.  */
 438       dfs_order = XNEWVEC (int, n_basic_blocks);
 439       rc_order = XNEWVEC (int, n_basic_blocks);
 440       pre_and_rev_post_order_compute (dfs_order, rc_order, false);
 441
 442       num_loops = 1;
 443
 444       for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++)
 445         {
 446           struct loop *loop;
 447           edge_iterator ei;
 448
 449           /* Search the nodes of the CFG in reverse completion order
 450              so that we can find outer loops first.  */
 451           if (!TEST_BIT (headers, rc_order[b]))
 452             continue;
 453
 454           header = BASIC_BLOCK (rc_order[b]);
 455
 456           loop = alloc_loop ();
 457           VEC_quick_push (loop_p, loops->larray, loop);
 458
 459           loop->header = header;
 460           loop->num = num_loops;
 461           num_loops++;
 462
 463           flow_loop_tree_node_add (header->loop_father, loop);
 464           loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
 465
 466           /* Look for the latch for this header block, if it has just a
 467              single one.  */
 468           FOR_EACH_EDGE (e, ei, header->preds)
 469             {
 470               basic_block latch = e->src;
 471
 472               if (flow_bb_inside_loop_p (loop, latch))
 473                 {
 474                   if (loop->latch != NULL)
 475                     {
 476                       /* More than one latch edge.  */
 477                       loop->latch = NULL;
 478                       break;
 479                     }
 480                   loop->latch = latch;
 481                 }
 482             }
 483         }
 484
 485       free (dfs_order);
 486       free (rc_order);
 487     }
 488
 489   sbitmap_free (headers);
 490
 491   loops->exits = NULL;
 492   loops->state = 0;
 493   return VEC_length (loop_p, loops->larray);
 494 }
 495
 496 /* Ratio of frequencies of edges so that one of more latch edges is
 497    considered to belong to inner loop with same header.  */
 498 #define HEAVY_EDGE_RATIO 8
 499
 500 /* Minimum number of samples for that we apply
 501    find_subloop_latch_edge_by_profile heuristics.  */
 502 #define HEAVY_EDGE_MIN_SAMPLES 10
 503
 504 /* If the profile info is available, finds an edge in LATCHES that much more
 505    frequent than the remaining edges.  Returns such an edge, or NULL if we do
 506    not find one.
 507
 508    We do not use guessed profile here, only the measured one.  The guessed
 509    profile is usually too flat and unreliable for this (and it is mostly based
 510    on the loop structure of the program, so it does not make much sense to
 511    derive the loop structure from it).  */
 512
 513 static edge
 514 find_subloop_latch_edge_by_profile (VEC (edge, heap) *latches)
 515 {
 516   unsigned i;
 517   edge e, me = NULL;
 518   gcov_type mcount = 0, tcount = 0;
 519
 520   for (i = 0; VEC_iterate (edge, latches, i, e); i++)
 521     {
 522       if (e->count > mcount)
 523         {
 524           me = e;
 525           mcount = e->count;
 526         }
 527       tcount += e->count;
 528     }
 529
 530   if (tcount < HEAVY_EDGE_MIN_SAMPLES
 531       || (tcount - mcount) * HEAVY_EDGE_RATIO > tcount)
 532     return NULL;
 533
 534   if (dump_file)
 535     fprintf (dump_file,
 536              "Found latch edge %d -> %d using profile information.\n",
 537              me->src->index, me->dest->index);
 538   return me;
 539 }
 540
 541 /* Among LATCHES, guesses a latch edge of LOOP corresponding to subloop, based
 542    on the structure of induction variables.  Returns this edge, or NULL if we
 543    do not find any.
 544
 545    We are quite conservative, and look just for an obvious simple innermost
 546    loop (which is the case where we would lose the most performance by not
 547    disambiguating the loop).  More precisely, we look for the following
 548    situation: The source of the chosen latch edge dominates sources of all
 549    the other latch edges.  Additionally, the header does not contain a phi node
 550    such that the argument from the chosen edge is equal to the argument from
 551    another edge.  */
 552
 553 static edge
 554 find_subloop_latch_edge_by_ivs (struct loop *loop, VEC (edge, heap) *latches)
 555 {
 556   edge e, latch = VEC_index (edge, latches, 0);
 557   unsigned i;
 558   tree phi, lop;
 559   basic_block bb;
 560
 561   /* Find the candidate for the latch edge.  */
 562   for (i = 1; VEC_iterate (edge, latches, i, e); i++)
 563     if (dominated_by_p (CDI_DOMINATORS, latch->src, e->src))
 564       latch = e;
 565
 566   /* Verify that it dominates all the latch edges.  */
 567   for (i = 0; VEC_iterate (edge, latches, i, e); i++)
 568     if (!dominated_by_p (CDI_DOMINATORS, e->src, latch->src))
 569       return NULL;
 570
 571   /* Check for a phi node that would deny that this is a latch edge of
 572      a subloop.  */
 573   for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
 574     {
 575       lop = PHI_ARG_DEF_FROM_EDGE (phi, latch);
 576
 577       /* Ignore the values that are not changed inside the subloop.  */
 578       if (TREE_CODE (lop) != SSA_NAME
 579           || SSA_NAME_DEF_STMT (lop) == phi)
 580         continue;
 581       bb = bb_for_stmt (SSA_NAME_DEF_STMT (lop));
 582       if (!bb || !flow_bb_inside_loop_p (loop, bb))
 583         continue;
 584
 585       for (i = 0; VEC_iterate (edge, latches, i, e); i++)
 586         if (e != latch
 587             && PHI_ARG_DEF_FROM_EDGE (phi, e) == lop)
 588           return NULL;
 589     }
 590
 591   if (dump_file)
 592     fprintf (dump_file,
 593              "Found latch edge %d -> %d using iv structure.\n",
 594              latch->src->index, latch->dest->index);
 595   return latch;
 596 }
 597
 598 /* If we can determine that one of the several latch edges of LOOP behaves
 599    as a latch edge of a separate subloop, returns this edge.  Otherwise
 600    returns NULL.  */
 601
 602 static edge
 603 find_subloop_latch_edge (struct loop *loop)
 604 {
 605   VEC (edge, heap) *latches = get_loop_latch_edges (loop);
 606   edge latch = NULL;
 607
 608   if (VEC_length (edge, latches) > 1)
 609     {
 610       latch = find_subloop_latch_edge_by_profile (latches);
 611
 612       if (!latch
 613           /* We consider ivs to guess the latch edge only in SSA.  Perhaps we
 614              should use cfghook for this, but it is hard to imagine it would
 615              be useful elsewhere.  */
 616           && current_ir_type () == IR_GIMPLE)
 617         latch = find_subloop_latch_edge_by_ivs (loop, latches);
 618     }
 619
 620   VEC_free (edge, heap, latches);
 621   return latch;
 622 }
 623
 624 /* Callback for make_forwarder_block.  Returns true if the edge E is marked
 625    in the set MFB_REIS_SET.  */
 626
 627 static struct pointer_set_t *mfb_reis_set;
 628 static bool
 629 mfb_redirect_edges_in_set (edge e)
 630 {
 631   return pointer_set_contains (mfb_reis_set, e);
 632 }
 633
 634 /* Creates a subloop of LOOP with latch edge LATCH.  */
 635
 636 static void
 637 form_subloop (struct loop *loop, edge latch)
 638 {
 639   edge_iterator ei;
 640   edge e, new_entry;
 641   struct loop *new_loop;
 642
 643   mfb_reis_set = pointer_set_create ();
 644   FOR_EACH_EDGE (e, ei, loop->header->preds)
 645     {
 646       if (e != latch)
 647         pointer_set_insert (mfb_reis_set, e);
 648     }
 649   new_entry = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
 650                                     NULL);
 651   pointer_set_destroy (mfb_reis_set);
 652
 653   loop->header = new_entry->src;
 654
 655   /* Find the blocks and subloops that belong to the new loop, and add it to
 656      the appropriate place in the loop tree.  */
 657   new_loop = alloc_loop ();
 658   new_loop->header = new_entry->dest;
 659   new_loop->latch = latch->src;
 660   add_loop (new_loop, loop);
 661 }
 662
 663 /* Make all the latch edges of LOOP to go to a single forwarder block --
 664    a new latch of LOOP.  */
 665
 666 static void
 667 merge_latch_edges (struct loop *loop)
 668 {
 669   VEC (edge, heap) *latches = get_loop_latch_edges (loop);
 670   edge latch, e;
 671   unsigned i;
 672
 673   gcc_assert (VEC_length (edge, latches) > 0);
 674
 675   if (VEC_length (edge, latches) == 1)
 676     loop->latch = VEC_index (edge, latches, 0)->src;
 677   else
 678     {
 679       if (dump_file)
 680         fprintf (dump_file, "Merged latch edges of loop %d\n", loop->num);
 681
 682       mfb_reis_set = pointer_set_create ();
 683       for (i = 0; VEC_iterate (edge, latches, i, e); i++)
 684         pointer_set_insert (mfb_reis_set, e);
 685       latch = make_forwarder_block (loop->header, mfb_redirect_edges_in_set,
 686                                     NULL);
 687       pointer_set_destroy (mfb_reis_set);
 688
 689       loop->header = latch->dest;
 690       loop->latch = latch->src;
 691     }
 692
 693   VEC_free (edge, heap, latches);
 694 }
 695
 696 /* LOOP may have several latch edges.  Transform it into (possibly several)
 697    loops with single latch edge.  */
 698
 699 static void
 700 disambiguate_multiple_latches (struct loop *loop)
 701 {
 702   edge e;
 703
 704   /* We eliminate the multiple latches by splitting the header to the forwarder
 705      block F and the rest R, and redirecting the edges.  There are two cases:
 706
 707      1) If there is a latch edge E that corresponds to a subloop (we guess
 708         that based on profile -- if it is taken much more often than the
 709         remaining edges; and on trees, using the information about induction
 710         variables of the loops), we redirect E to R, all the remaining edges to
 711         F, then rescan the loops and try again for the outer loop.
 712      2) If there is no such edge, we redirect all latch edges to F, and the
 713         entry edges to R, thus making F the single latch of the loop.  */
 714
 715   if (dump_file)
 716     fprintf (dump_file, "Disambiguating loop %d with multiple latches\n",
 717              loop->num);
 718
 719   /* During latch merging, we may need to redirect the entry edges to a new
 720      block.  This would cause problems if the entry edge was the one from the
 721      entry block.  To avoid having to handle this case specially, split
 722      such entry edge.  */
 723   e = find_edge (ENTRY_BLOCK_PTR, loop->header);
 724   if (e)
 725     split_edge (e);
 726
 727   while (1)
 728     {
 729       e = find_subloop_latch_edge (loop);
 730       if (!e)
 731         break;
 732
 733       form_subloop (loop, e);
 734     }
 735
 736   merge_latch_edges (loop);
 737 }
 738
 739 /* Split loops with multiple latch edges.  */
 740
 741 void
 742 disambiguate_loops_with_multiple_latches (void)
 743 {
 744   loop_iterator li;
 745   struct loop *loop;
 746
 747   FOR_EACH_LOOP (li, loop, 0)
 748     {
 749       if (!loop->latch)
 750         disambiguate_multiple_latches (loop);
 751     }
 752 }
 753
 754 /* Return nonzero if basic block BB belongs to LOOP.  */
 755 bool
 756 flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb)
 757 {
 758   struct loop *source_loop;
 759
 760   if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
 761     return 0;
 762
 763   source_loop = bb->loop_father;
 764   return loop == source_loop || flow_loop_nested_p (loop, source_loop);
 765 }
 766
 767 /* Enumeration predicate for get_loop_body_with_size.  */
 768 static bool
 769 glb_enum_p (basic_block bb, void *glb_loop)
 770 {
 771   struct loop *loop = glb_loop;
 772   return (bb != loop->header
 773           && dominated_by_p (CDI_DOMINATORS, bb, loop->header));
 774 }
 775
 776 /* Gets basic blocks of a LOOP.  Header is the 0-th block, rest is in dfs
 777    order against direction of edges from latch.  Specially, if
 778    header != latch, latch is the 1-st block.  LOOP cannot be the fake
 779    loop tree root, and its size must be at most MAX_SIZE.  The blocks
 780    in the LOOP body are stored to BODY, and the size of the LOOP is
 781    returned.  */
 782
 783 unsigned
 784 get_loop_body_with_size (const struct loop *loop, basic_block *body,
 785                          unsigned max_size)
 786 {
 787   return dfs_enumerate_from (loop->header, 1, glb_enum_p,
 788                              body, max_size, (void *) loop);
 789 }
 790
 791 /* Gets basic blocks of a LOOP.  Header is the 0-th block, rest is in dfs
 792    order against direction of edges from latch.  Specially, if
 793    header != latch, latch is the 1-st block.  */
 794
 795 basic_block *
 796 get_loop_body (const struct loop *loop)
 797 {
 798   basic_block *body, bb;
 799   unsigned tv = 0;
 800
 801   gcc_assert (loop->num_nodes);
 802
 803   body = XCNEWVEC (basic_block, loop->num_nodes);
 804
 805   if (loop->latch == EXIT_BLOCK_PTR)
 806     {
 807       /* There may be blocks unreachable from EXIT_BLOCK, hence we need to
 808          special-case the fake loop that contains the whole function.  */
 809       gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks);
 810       body[tv++] = loop->header;
 811       body[tv++] = EXIT_BLOCK_PTR;
 812       FOR_EACH_BB (bb)
 813         body[tv++] = bb;
 814     }
 815   else
 816     tv = get_loop_body_with_size (loop, body, loop->num_nodes);
 817
 818   gcc_assert (tv == loop->num_nodes);
 819   return body;
 820 }
 821
 822 /* Fills dominance descendants inside LOOP of the basic block BB into
 823    array TOVISIT from index *TV.  */
 824
 825 static void
 826 fill_sons_in_loop (const struct loop *loop, basic_block bb,
 827                    basic_block *tovisit, int *tv)
 828 {
 829   basic_block son, postpone = NULL;
 830
 831   tovisit[(*tv)++] = bb;
 832   for (son = first_dom_son (CDI_DOMINATORS, bb);
 833        son;
 834        son = next_dom_son (CDI_DOMINATORS, son))
 835     {
 836       if (!flow_bb_inside_loop_p (loop, son))
 837         continue;
 838
 839       if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
 840         {
 841           postpone = son;
 842           continue;
 843         }
 844       fill_sons_in_loop (loop, son, tovisit, tv);
 845     }
 846
 847   if (postpone)
 848     fill_sons_in_loop (loop, postpone, tovisit, tv);
 849 }
 850
 851 /* Gets body of a LOOP (that must be different from the outermost loop)
 852    sorted by dominance relation.  Additionally, if a basic block s dominates
 853    the latch, then only blocks dominated by s are be after it.  */
 854
 855 basic_block *
 856 get_loop_body_in_dom_order (const struct loop *loop)
 857 {
 858   basic_block *tovisit;
 859   int tv;
 860
 861   gcc_assert (loop->num_nodes);
 862
 863   tovisit = XCNEWVEC (basic_block, loop->num_nodes);
 864
 865   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
 866
 867   tv = 0;
 868   fill_sons_in_loop (loop, loop->header, tovisit, &tv);
 869
 870   gcc_assert (tv == (int) loop->num_nodes);
 871
 872   return tovisit;
 873 }
 874
 875 /* Get body of a LOOP in breadth first sort order.  */
 876
 877 basic_block *
 878 get_loop_body_in_bfs_order (const struct loop *loop)
 879 {
 880   basic_block *blocks;
 881   basic_block bb;
 882   bitmap visited;
 883   unsigned int i = 0;
 884   unsigned int vc = 1;
 885
 886   gcc_assert (loop->num_nodes);
 887   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
 888
 889   blocks = XCNEWVEC (basic_block, loop->num_nodes);
 890   visited = BITMAP_ALLOC (NULL);
 891
 892   bb = loop->header;
 893   while (i < loop->num_nodes)
 894     {
 895       edge e;
 896       edge_iterator ei;
 897
 898       if (!bitmap_bit_p (visited, bb->index))
 899         {
 900           /* This basic block is now visited */
 901           bitmap_set_bit (visited, bb->index);
 902           blocks[i++] = bb;
 903         }
 904
 905       FOR_EACH_EDGE (e, ei, bb->succs)
 906         {
 907           if (flow_bb_inside_loop_p (loop, e->dest))
 908             {
 909               if (!bitmap_bit_p (visited, e->dest->index))
 910                 {
 911                   bitmap_set_bit (visited, e->dest->index);
 912                   blocks[i++] = e->dest;
 913                 }
 914             }
 915         }
 916
 917       gcc_assert (i >= vc);
 918
 919       bb = blocks[vc++];
 920     }
 921
 922   BITMAP_FREE (visited);
 923   return blocks;
 924 }
 925
 926 /* Hash function for struct loop_exit.  */
 927
 928 static hashval_t
 929 loop_exit_hash (const void *ex)
 930 {
 931   struct loop_exit *exit = (struct loop_exit *) ex;
 932
 933   return htab_hash_pointer (exit->e);
 934 }
 935
 936 /* Equality function for struct loop_exit.  Compares with edge.  */
 937
 938 static int
 939 loop_exit_eq (const void *ex, const void *e)
 940 {
 941   struct loop_exit *exit = (struct loop_exit *) ex;
 942
 943   return exit->e == e;
 944 }
 945
 946 /* Frees the list of loop exit descriptions EX.  */
 947
 948 static void
 949 loop_exit_free (void *ex)
 950 {
 951   struct loop_exit *exit = (struct loop_exit *) ex, *next;
 952
 953   for (; exit; exit = next)
 954     {
 955       next = exit->next_e;
 956
 957       exit->next->prev = exit->prev;
 958       exit->prev->next = exit->next;
 959
 960       free (exit);
 961     }
 962 }
 963
 964 /* Returns the list of records for E as an exit of a loop.  */
 965
 966 static struct loop_exit *
 967 get_exit_descriptions (edge e)
 968 {
 969   return htab_find_with_hash (current_loops->exits, e,
 970                               htab_hash_pointer (e));
 971 }
 972
 973 /* Updates the lists of loop exits in that E appears.
 974    If REMOVED is true, E is being removed, and we
 975    just remove it from the lists of exits.
 976    If NEW_EDGE is true and E is not a loop exit, we
 977    do not try to remove it from loop exit lists.  */
 978
 979 void
 980 rescan_loop_exit (edge e, bool new_edge, bool removed)
 981 {
 982   void **slot;
 983   struct loop_exit *exits = NULL, *exit;
 984   struct loop *aloop, *cloop;
 985
 986   if ((current_loops->state & LOOPS_HAVE_RECORDED_EXITS) == 0)
 987     return;
 988
 989   if (!removed
 990       && e->src->loop_father != NULL
 991       && e->dest->loop_father != NULL
 992       && !flow_bb_inside_loop_p (e->src->loop_father, e->dest))
 993     {
 994       cloop = find_common_loop (e->src->loop_father, e->dest->loop_father);
 995       for (aloop = e->src->loop_father;
 996            aloop != cloop;
 997            aloop = aloop->outer)
 998         {
 999           exit = XNEW (struct loop_exit);
1000           exit->e = e;
1001
1002           exit->next = aloop->exits.next;
1003           exit->prev = &aloop->exits;
1004           exit->next->prev = exit;
1005           exit->prev->next = exit;
1006
1007           exit->next_e = exits;
1008           exits = exit;
1009         }
1010     }
1011
1012   if (!exits && new_edge)
1013     return;
1014
1015   slot = htab_find_slot_with_hash (current_loops->exits, e,
1016                                    htab_hash_pointer (e),
1017                                    exits ? INSERT : NO_INSERT);
1018   if (!slot)
1019     return;
1020
1021   if (exits)
1022     {
1023       if (*slot)
1024         loop_exit_free (*slot);
1025       *slot = exits;
1026     }
1027   else
1028     htab_clear_slot (current_loops->exits, slot);
1029 }
1030
1031 /* For each loop, record list of exit edges, and start maintaining these
1032    lists.  */
1033
1034 void
1035 record_loop_exits (void)
1036 {
1037   basic_block bb;
1038   edge_iterator ei;
1039   edge e;
1040
1041   if (!current_loops)
1042     return;
1043
1044   if (current_loops->state & LOOPS_HAVE_RECORDED_EXITS)
1045     return;
1046   current_loops->state |= LOOPS_HAVE_RECORDED_EXITS;
1047
1048   gcc_assert (current_loops->exits == NULL);
1049   current_loops->exits = htab_create (2 * number_of_loops (),
1050                                       loop_exit_hash,
1051                                       loop_exit_eq,
1052                                       loop_exit_free);
1053
1054   FOR_EACH_BB (bb)
1055     {
1056       FOR_EACH_EDGE (e, ei, bb->succs)
1057         {
1058           rescan_loop_exit (e, true, false);
1059         }
1060     }
1061 }
1062
1063 /* Dumps information about the exit in *SLOT to FILE.
1064    Callback for htab_traverse.  */
1065
1066 static int
1067 dump_recorded_exit (void **slot, void *file)
1068 {
1069   struct loop_exit *exit = *slot;
1070   unsigned n = 0;
1071   edge e = exit->e;
1072
1073   for (; exit != NULL; exit = exit->next_e)
1074     n++;
1075
1076   fprintf (file, "Edge %d->%d exits %u loops\n",
1077            e->src->index, e->dest->index, n);
1078
1079   return 1;
1080 }
1081
1082 /* Dumps the recorded exits of loops to FILE.  */
1083
1084 extern void dump_recorded_exits (FILE *);
1085 void
1086 dump_recorded_exits (FILE *file)
1087 {
1088   if (!current_loops->exits)
1089     return;
1090   htab_traverse (current_loops->exits, dump_recorded_exit, file);
1091 }
1092
1093 /* Releases lists of loop exits.  */
1094
1095 void
1096 release_recorded_exits (void)
1097 {
1098   gcc_assert (current_loops->state & LOOPS_HAVE_RECORDED_EXITS);
1099   htab_delete (current_loops->exits);
1100   current_loops->exits = NULL;
1101   current_loops->state &= ~LOOPS_HAVE_RECORDED_EXITS;
1102 }
1103
1104 /* Returns the list of the exit edges of a LOOP.  */
1105
1106 VEC (edge, heap) *
1107 get_loop_exit_edges (const struct loop *loop)
1108 {
1109   VEC (edge, heap) *edges = NULL;
1110   edge e;
1111   unsigned i;
1112   basic_block *body;
1113   edge_iterator ei;
1114   struct loop_exit *exit;
1115
1116   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1117
1118   /* If we maintain the lists of exits, use them.  Otherwise we must
1119      scan the body of the loop.  */
1120   if (current_loops->state & LOOPS_HAVE_RECORDED_EXITS)
1121     {
1122       for (exit = loop->exits.next; exit->e; exit = exit->next)
1123         VEC_safe_push (edge, heap, edges, exit->e);
1124     }
1125   else
1126     {
1127       body = get_loop_body (loop);
1128       for (i = 0; i < loop->num_nodes; i++)
1129         FOR_EACH_EDGE (e, ei, body[i]->succs)
1130           {
1131             if (!flow_bb_inside_loop_p (loop, e->dest))
1132               VEC_safe_push (edge, heap, edges, e);
1133           }
1134       free (body);
1135     }
1136
1137   return edges;
1138 }
1139
1140 /* Counts the number of conditional branches inside LOOP.  */
1141
1142 unsigned
1143 num_loop_branches (const struct loop *loop)
1144 {
1145   unsigned i, n;
1146   basic_block * body;
1147
1148   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1149
1150   body = get_loop_body (loop);
1151   n = 0;
1152   for (i = 0; i < loop->num_nodes; i++)
1153     if (EDGE_COUNT (body[i]->succs) >= 2)
1154       n++;
1155   free (body);
1156
1157   return n;
1158 }
1159
1160 /* Adds basic block BB to LOOP.  */
1161 void
1162 add_bb_to_loop (basic_block bb, struct loop *loop)
1163 {
1164   int i;
1165   edge_iterator ei;
1166   edge e;
1167
1168   gcc_assert (bb->loop_father == NULL);
1169   bb->loop_father = loop;
1170   bb->loop_depth = loop->depth;
1171   loop->num_nodes++;
1172   for (i = 0; i < loop->depth; i++)
1173     loop->pred[i]->num_nodes++;
1174
1175   FOR_EACH_EDGE (e, ei, bb->succs)
1176     {
1177       rescan_loop_exit (e, true, false);
1178     }
1179   FOR_EACH_EDGE (e, ei, bb->preds)
1180     {
1181       rescan_loop_exit (e, true, false);
1182     }
1183 }
1184
1185 /* Remove basic block BB from loops.  */
1186 void
1187 remove_bb_from_loops (basic_block bb)
1188 {
1189   int i;
1190   struct loop *loop = bb->loop_father;
1191   edge_iterator ei;
1192   edge e;
1193
1194   gcc_assert (loop != NULL);
1195   loop->num_nodes--;
1196   for (i = 0; i < loop->depth; i++)
1197     loop->pred[i]->num_nodes--;
1198   bb->loop_father = NULL;
1199   bb->loop_depth = 0;
1200
1201   FOR_EACH_EDGE (e, ei, bb->succs)
1202     {
1203       rescan_loop_exit (e, false, true);
1204     }
1205   FOR_EACH_EDGE (e, ei, bb->preds)
1206     {
1207       rescan_loop_exit (e, false, true);
1208     }
1209 }
1210
1211 /* Finds nearest common ancestor in loop tree for given loops.  */
1212 struct loop *
1213 find_common_loop (struct loop *loop_s, struct loop *loop_d)
1214 {
1215   if (!loop_s) return loop_d;
1216   if (!loop_d) return loop_s;
1217
1218   if (loop_s->depth < loop_d->depth)
1219     loop_d = loop_d->pred[loop_s->depth];
1220   else if (loop_s->depth > loop_d->depth)
1221     loop_s = loop_s->pred[loop_d->depth];
1222
1223   while (loop_s != loop_d)
1224     {
1225       loop_s = loop_s->outer;
1226       loop_d = loop_d->outer;
1227     }
1228   return loop_s;
1229 }
1230
1231 /* Removes LOOP from structures and frees its data.  */
1232
1233 void
1234 delete_loop (struct loop *loop)
1235 {
1236   /* Remove the loop from structure.  */
1237   flow_loop_tree_node_remove (loop);
1238
1239   /* Remove loop from loops array.  */
1240   VEC_replace (loop_p, current_loops->larray, loop->num, NULL);
1241
1242   /* Free loop data.  */
1243   flow_loop_free (loop);
1244 }
1245
1246 /* Cancels the LOOP; it must be innermost one.  */
1247
1248 static void
1249 cancel_loop (struct loop *loop)
1250 {
1251   basic_block *bbs;
1252   unsigned i;
1253
1254   gcc_assert (!loop->inner);
1255
1256   /* Move blocks up one level (they should be removed as soon as possible).  */
1257   bbs = get_loop_body (loop);
1258   for (i = 0; i < loop->num_nodes; i++)
1259     bbs[i]->loop_father = loop->outer;
1260
1261   delete_loop (loop);
1262 }
1263
1264 /* Cancels LOOP and all its subloops.  */
1265 void
1266 cancel_loop_tree (struct loop *loop)
1267 {
1268   while (loop->inner)
1269     cancel_loop_tree (loop->inner);
1270   cancel_loop (loop);
1271 }
1272
1273 /* Checks that information about loops is correct
1274      -- sizes of loops are all right
1275      -- results of get_loop_body really belong to the loop
1276      -- loop header have just single entry edge and single latch edge
1277      -- loop latches have only single successor that is header of their loop
1278      -- irreducible loops are correctly marked
1279   */
1280 void
1281 verify_loop_structure (void)
1282 {
1283   unsigned *sizes, i, j;
1284   sbitmap irreds;
1285   basic_block *bbs, bb;
1286   struct loop *loop;
1287   int err = 0;
1288   edge e;
1289   unsigned num = number_of_loops ();
1290   loop_iterator li;
1291   struct loop_exit *exit, *mexit;
1292
1293   /* Check sizes.  */
1294   sizes = XCNEWVEC (unsigned, num);
1295   sizes[0] = 2;
1296
1297   FOR_EACH_BB (bb)
1298     for (loop = bb->loop_father; loop; loop = loop->outer)
1299       sizes[loop->num]++;
1300
1301   FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
1302     {
1303       i = loop->num;
1304
1305       if (loop->num_nodes != sizes[i])
1306         {
1307           error ("size of loop %d should be %d, not %d",
1308                    i, sizes[i], loop->num_nodes);
1309           err = 1;
1310         }
1311     }
1312
1313   /* Check get_loop_body.  */
1314   FOR_EACH_LOOP (li, loop, 0)
1315     {
1316       bbs = get_loop_body (loop);
1317
1318       for (j = 0; j < loop->num_nodes; j++)
1319         if (!flow_bb_inside_loop_p (loop, bbs[j]))
1320           {
1321             error ("bb %d do not belong to loop %d",
1322                     bbs[j]->index, loop->num);
1323             err = 1;
1324           }
1325       free (bbs);
1326     }
1327
1328   /* Check headers and latches.  */
1329   FOR_EACH_LOOP (li, loop, 0)
1330     {
1331       i = loop->num;
1332
1333       if ((current_loops->state & LOOPS_HAVE_PREHEADERS)
1334           && EDGE_COUNT (loop->header->preds) != 2)
1335         {
1336           error ("loop %d's header does not have exactly 2 entries", i);
1337           err = 1;
1338         }
1339       if (current_loops->state & LOOPS_HAVE_SIMPLE_LATCHES)
1340         {
1341           if (!single_succ_p (loop->latch))
1342             {
1343               error ("loop %d's latch does not have exactly 1 successor", i);
1344               err = 1;
1345             }
1346           if (single_succ (loop->latch) != loop->header)
1347             {
1348               error ("loop %d's latch does not have header as successor", i);
1349               err = 1;
1350             }
1351           if (loop->latch->loop_father != loop)
1352             {
1353               error ("loop %d's latch does not belong directly to it", i);
1354               err = 1;
1355             }
1356         }
1357       if (loop->header->loop_father != loop)
1358         {
1359           error ("loop %d's header does not belong directly to it", i);
1360           err = 1;
1361         }
1362       if ((current_loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1363           && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
1364         {
1365           error ("loop %d's latch is marked as part of irreducible region", i);
1366           err = 1;
1367         }
1368     }
1369
1370   /* Check irreducible loops.  */
1371   if (current_loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1372     {
1373       /* Record old info.  */
1374       irreds = sbitmap_alloc (last_basic_block);
1375       FOR_EACH_BB (bb)
1376         {
1377           edge_iterator ei;
1378           if (bb->flags & BB_IRREDUCIBLE_LOOP)
1379             SET_BIT (irreds, bb->index);
1380           else
1381             RESET_BIT (irreds, bb->index);
1382           FOR_EACH_EDGE (e, ei, bb->succs)
1383             if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1384               e->flags |= EDGE_ALL_FLAGS + 1;
1385         }
1386
1387       /* Recount it.  */
1388       mark_irreducible_loops ();
1389
1390       /* Compare.  */
1391       FOR_EACH_BB (bb)
1392         {
1393           edge_iterator ei;
1394
1395           if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1396               && !TEST_BIT (irreds, bb->index))
1397             {
1398               error ("basic block %d should be marked irreducible", bb->index);
1399               err = 1;
1400             }
1401           else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1402               && TEST_BIT (irreds, bb->index))
1403             {
1404               error ("basic block %d should not be marked irreducible", bb->index);
1405               err = 1;
1406             }
1407           FOR_EACH_EDGE (e, ei, bb->succs)
1408             {
1409               if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1410                   && !(e->flags & (EDGE_ALL_FLAGS + 1)))
1411                 {
1412                   error ("edge from %d to %d should be marked irreducible",
1413                          e->src->index, e->dest->index);
1414                   err = 1;
1415                 }
1416               else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1417                        && (e->flags & (EDGE_ALL_FLAGS + 1)))
1418                 {
1419                   error ("edge from %d to %d should not be marked irreducible",
1420                          e->src->index, e->dest->index);
1421                   err = 1;
1422                 }
1423               e->flags &= ~(EDGE_ALL_FLAGS + 1);
1424             }
1425         }
1426       free (irreds);
1427     }
1428
1429   /* Check the recorded loop exits.  */
1430   FOR_EACH_LOOP (li, loop, 0)
1431     {
1432       if (loop->exits.e != NULL)
1433         {
1434           error ("corrupted head of the exits list of loop %d",
1435                  loop->num);
1436           err = 1;
1437         }
1438       else
1439         {
1440           /* Check that the list forms a cycle, and all elements except
1441              for the head are nonnull.  */
1442           for (mexit = &loop->exits, exit = mexit->next, i = 0;
1443                exit->e && exit != mexit;
1444                exit = exit->next)
1445             {
1446               if (i++ & 1)
1447                 mexit = mexit->next;
1448             }
1449
1450           if (exit != &loop->exits)
1451             {
1452               error ("corrupted exits list of loop %d", loop->num);
1453               err = 1;
1454             }
1455         }
1456
1457       if ((current_loops->state & LOOPS_HAVE_RECORDED_EXITS) == 0)
1458         {
1459           if (loop->exits.next != &loop->exits)
1460             {
1461               error ("nonempty exits list of loop %d, but exits are not recorded",
1462                      loop->num);
1463               err = 1;
1464             }
1465         }
1466     }
1467
1468   if (current_loops->state & LOOPS_HAVE_RECORDED_EXITS)
1469     {
1470       unsigned n_exits = 0, eloops;
1471
1472       memset (sizes, 0, sizeof (unsigned) * num);
1473       FOR_EACH_BB (bb)
1474         {
1475           edge_iterator ei;
1476           if (bb->loop_father == current_loops->tree_root)
1477             continue;
1478           FOR_EACH_EDGE (e, ei, bb->succs)
1479             {
1480               if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
1481                 continue;
1482
1483               n_exits++;
1484               exit = get_exit_descriptions (e);
1485               if (!exit)
1486                 {
1487                   error ("Exit %d->%d not recorded",
1488                          e->src->index, e->dest->index);
1489                   err = 1;
1490                 }
1491               eloops = 0;
1492               for (; exit; exit = exit->next_e)
1493                 eloops++;
1494
1495               for (loop = bb->loop_father;
1496                    loop != e->dest->loop_father;
1497                    loop = loop->outer)
1498                 {
1499                   eloops--;
1500                   sizes[loop->num]++;
1501                 }
1502
1503               if (eloops != 0)
1504                 {
1505                   error ("Wrong list of exited loops for edge  %d->%d",
1506                          e->src->index, e->dest->index);
1507                   err = 1;
1508                 }
1509             }
1510         }
1511
1512       if (n_exits != htab_elements (current_loops->exits))
1513         {
1514           error ("Too many loop exits recorded");
1515           err = 1;
1516         }
1517
1518       FOR_EACH_LOOP (li, loop, 0)
1519         {
1520           eloops = 0;
1521           for (exit = loop->exits.next; exit->e; exit = exit->next)
1522             eloops++;
1523           if (eloops != sizes[loop->num])
1524             {
1525               error ("%d exits recorded for loop %d (having %d exits)",
1526                      eloops, loop->num, sizes[loop->num]);
1527               err = 1;
1528             }
1529         }
1530     }
1531
1532   gcc_assert (!err);
1533
1534   free (sizes);
1535 }
1536
1537 /* Returns latch edge of LOOP.  */
1538 edge
1539 loop_latch_edge (const struct loop *loop)
1540 {
1541   return find_edge (loop->latch, loop->header);
1542 }
1543
1544 /* Returns preheader edge of LOOP.  */
1545 edge
1546 loop_preheader_edge (const struct loop *loop)
1547 {
1548   edge e;
1549   edge_iterator ei;
1550
1551   gcc_assert ((current_loops->state & LOOPS_HAVE_PREHEADERS) != 0);
1552
1553   FOR_EACH_EDGE (e, ei, loop->header->preds)
1554     if (e->src != loop->latch)
1555       break;
1556
1557   return e;
1558 }
1559
1560 /* Returns true if E is an exit of LOOP.  */
1561
1562 bool
1563 loop_exit_edge_p (const struct loop *loop, edge e)
1564 {
1565   return (flow_bb_inside_loop_p (loop, e->src)
1566           && !flow_bb_inside_loop_p (loop, e->dest));
1567 }
1568
1569 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1570    or more than one exit.  If loops do not have the exits recorded, NULL
1571    is returned always.  */
1572
1573 edge
1574 single_exit (const struct loop *loop)
1575 {
1576   struct loop_exit *exit = loop->exits.next;
1577
1578   if ((current_loops->state & LOOPS_HAVE_RECORDED_EXITS) == 0)
1579     return NULL;
1580
1581   if (exit->e && exit->next == &loop->exits)
1582     return exit->e;
1583   else
1584     return NULL;
1585 }