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->state & LOOPS_HAVE_RECORDED_EXITS)
1042     return;
1043   current_loops->state |= LOOPS_HAVE_RECORDED_EXITS;
1044
1045   gcc_assert (current_loops->exits == NULL);
1046   current_loops->exits = htab_create (2 * number_of_loops (),
1047                                       loop_exit_hash,
1048                                       loop_exit_eq,
1049                                       loop_exit_free);
1050
1051   FOR_EACH_BB (bb)
1052     {
1053       FOR_EACH_EDGE (e, ei, bb->succs)
1054         {
1055           rescan_loop_exit (e, true, false);
1056         }
1057     }
1058 }
1059
1060 /* Dumps information about the exit in *SLOT to FILE.
1061    Callback for htab_traverse.  */
1062
1063 static int
1064 dump_recorded_exit (void **slot, void *file)
1065 {
1066   struct loop_exit *exit = *slot;
1067   unsigned n = 0;
1068   edge e = exit->e;
1069
1070   for (; exit != NULL; exit = exit->next_e)
1071     n++;
1072
1073   fprintf (file, "Edge %d->%d exits %u loops\n",
1074            e->src->index, e->dest->index, n);
1075
1076   return 1;
1077 }
1078
1079 /* Dumps the recorded exits of loops to FILE.  */
1080
1081 extern void dump_recorded_exits (FILE *);
1082 void
1083 dump_recorded_exits (FILE *file)
1084 {
1085   if (!current_loops->exits)
1086     return;
1087   htab_traverse (current_loops->exits, dump_recorded_exit, file);
1088 }
1089
1090 /* Releases lists of loop exits.  */
1091
1092 void
1093 release_recorded_exits (void)
1094 {
1095   gcc_assert (current_loops->state & LOOPS_HAVE_RECORDED_EXITS);
1096   htab_delete (current_loops->exits);
1097   current_loops->exits = NULL;
1098   current_loops->state &= ~LOOPS_HAVE_RECORDED_EXITS;
1099 }
1100
1101 /* Returns the list of the exit edges of a LOOP.  */
1102
1103 VEC (edge, heap) *
1104 get_loop_exit_edges (const struct loop *loop)
1105 {
1106   VEC (edge, heap) *edges = NULL;
1107   edge e;
1108   unsigned i;
1109   basic_block *body;
1110   edge_iterator ei;
1111   struct loop_exit *exit;
1112
1113   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1114
1115   /* If we maintain the lists of exits, use them.  Otherwise we must
1116      scan the body of the loop.  */
1117   if (current_loops->state & LOOPS_HAVE_RECORDED_EXITS)
1118     {
1119       for (exit = loop->exits.next; exit->e; exit = exit->next)
1120         VEC_safe_push (edge, heap, edges, exit->e);
1121     }
1122   else
1123     {
1124       body = get_loop_body (loop);
1125       for (i = 0; i < loop->num_nodes; i++)
1126         FOR_EACH_EDGE (e, ei, body[i]->succs)
1127           {
1128             if (!flow_bb_inside_loop_p (loop, e->dest))
1129               VEC_safe_push (edge, heap, edges, e);
1130           }
1131       free (body);
1132     }
1133
1134   return edges;
1135 }
1136
1137 /* Counts the number of conditional branches inside LOOP.  */
1138
1139 unsigned
1140 num_loop_branches (const struct loop *loop)
1141 {
1142   unsigned i, n;
1143   basic_block * body;
1144
1145   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
1146
1147   body = get_loop_body (loop);
1148   n = 0;
1149   for (i = 0; i < loop->num_nodes; i++)
1150     if (EDGE_COUNT (body[i]->succs) >= 2)
1151       n++;
1152   free (body);
1153
1154   return n;
1155 }
1156
1157 /* Adds basic block BB to LOOP.  */
1158 void
1159 add_bb_to_loop (basic_block bb, struct loop *loop)
1160 {
1161   int i;
1162   edge_iterator ei;
1163   edge e;
1164
1165   gcc_assert (bb->loop_father == NULL);
1166   bb->loop_father = loop;
1167   bb->loop_depth = loop->depth;
1168   loop->num_nodes++;
1169   for (i = 0; i < loop->depth; i++)
1170     loop->pred[i]->num_nodes++;
1171
1172   FOR_EACH_EDGE (e, ei, bb->succs)
1173     {
1174       rescan_loop_exit (e, true, false);
1175     }
1176   FOR_EACH_EDGE (e, ei, bb->preds)
1177     {
1178       rescan_loop_exit (e, true, false);
1179     }
1180 }
1181
1182 /* Remove basic block BB from loops.  */
1183 void
1184 remove_bb_from_loops (basic_block bb)
1185 {
1186   int i;
1187   struct loop *loop = bb->loop_father;
1188   edge_iterator ei;
1189   edge e;
1190
1191   gcc_assert (loop != NULL);
1192   loop->num_nodes--;
1193   for (i = 0; i < loop->depth; i++)
1194     loop->pred[i]->num_nodes--;
1195   bb->loop_father = NULL;
1196   bb->loop_depth = 0;
1197
1198   FOR_EACH_EDGE (e, ei, bb->succs)
1199     {
1200       rescan_loop_exit (e, false, true);
1201     }
1202   FOR_EACH_EDGE (e, ei, bb->preds)
1203     {
1204       rescan_loop_exit (e, false, true);
1205     }
1206 }
1207
1208 /* Finds nearest common ancestor in loop tree for given loops.  */
1209 struct loop *
1210 find_common_loop (struct loop *loop_s, struct loop *loop_d)
1211 {
1212   if (!loop_s) return loop_d;
1213   if (!loop_d) return loop_s;
1214
1215   if (loop_s->depth < loop_d->depth)
1216     loop_d = loop_d->pred[loop_s->depth];
1217   else if (loop_s->depth > loop_d->depth)
1218     loop_s = loop_s->pred[loop_d->depth];
1219
1220   while (loop_s != loop_d)
1221     {
1222       loop_s = loop_s->outer;
1223       loop_d = loop_d->outer;
1224     }
1225   return loop_s;
1226 }
1227
1228 /* Removes LOOP from structures and frees its data.  */
1229
1230 void
1231 delete_loop (struct loop *loop)
1232 {
1233   /* Remove the loop from structure.  */
1234   flow_loop_tree_node_remove (loop);
1235
1236   /* Remove loop from loops array.  */
1237   VEC_replace (loop_p, current_loops->larray, loop->num, NULL);
1238
1239   /* Free loop data.  */
1240   flow_loop_free (loop);
1241 }
1242
1243 /* Cancels the LOOP; it must be innermost one.  */
1244
1245 static void
1246 cancel_loop (struct loop *loop)
1247 {
1248   basic_block *bbs;
1249   unsigned i;
1250
1251   gcc_assert (!loop->inner);
1252
1253   /* Move blocks up one level (they should be removed as soon as possible).  */
1254   bbs = get_loop_body (loop);
1255   for (i = 0; i < loop->num_nodes; i++)
1256     bbs[i]->loop_father = loop->outer;
1257
1258   delete_loop (loop);
1259 }
1260
1261 /* Cancels LOOP and all its subloops.  */
1262 void
1263 cancel_loop_tree (struct loop *loop)
1264 {
1265   while (loop->inner)
1266     cancel_loop_tree (loop->inner);
1267   cancel_loop (loop);
1268 }
1269
1270 /* Checks that information about loops is correct
1271      -- sizes of loops are all right
1272      -- results of get_loop_body really belong to the loop
1273      -- loop header have just single entry edge and single latch edge
1274      -- loop latches have only single successor that is header of their loop
1275      -- irreducible loops are correctly marked
1276   */
1277 void
1278 verify_loop_structure (void)
1279 {
1280   unsigned *sizes, i, j;
1281   sbitmap irreds;
1282   basic_block *bbs, bb;
1283   struct loop *loop;
1284   int err = 0;
1285   edge e;
1286   unsigned num = number_of_loops ();
1287   loop_iterator li;
1288   struct loop_exit *exit, *mexit;
1289
1290   /* Check sizes.  */
1291   sizes = XCNEWVEC (unsigned, num);
1292   sizes[0] = 2;
1293
1294   FOR_EACH_BB (bb)
1295     for (loop = bb->loop_father; loop; loop = loop->outer)
1296       sizes[loop->num]++;
1297
1298   FOR_EACH_LOOP (li, loop, LI_INCLUDE_ROOT)
1299     {
1300       i = loop->num;
1301
1302       if (loop->num_nodes != sizes[i])
1303         {
1304           error ("size of loop %d should be %d, not %d",
1305                    i, sizes[i], loop->num_nodes);
1306           err = 1;
1307         }
1308     }
1309
1310   /* Check get_loop_body.  */
1311   FOR_EACH_LOOP (li, loop, 0)
1312     {
1313       bbs = get_loop_body (loop);
1314
1315       for (j = 0; j < loop->num_nodes; j++)
1316         if (!flow_bb_inside_loop_p (loop, bbs[j]))
1317           {
1318             error ("bb %d do not belong to loop %d",
1319                     bbs[j]->index, loop->num);
1320             err = 1;
1321           }
1322       free (bbs);
1323     }
1324
1325   /* Check headers and latches.  */
1326   FOR_EACH_LOOP (li, loop, 0)
1327     {
1328       i = loop->num;
1329
1330       if ((current_loops->state & LOOPS_HAVE_PREHEADERS)
1331           && EDGE_COUNT (loop->header->preds) != 2)
1332         {
1333           error ("loop %d's header does not have exactly 2 entries", i);
1334           err = 1;
1335         }
1336       if (current_loops->state & LOOPS_HAVE_SIMPLE_LATCHES)
1337         {
1338           if (!single_succ_p (loop->latch))
1339             {
1340               error ("loop %d's latch does not have exactly 1 successor", i);
1341               err = 1;
1342             }
1343           if (single_succ (loop->latch) != loop->header)
1344             {
1345               error ("loop %d's latch does not have header as successor", i);
1346               err = 1;
1347             }
1348           if (loop->latch->loop_father != loop)
1349             {
1350               error ("loop %d's latch does not belong directly to it", i);
1351               err = 1;
1352             }
1353         }
1354       if (loop->header->loop_father != loop)
1355         {
1356           error ("loop %d's header does not belong directly to it", i);
1357           err = 1;
1358         }
1359       if ((current_loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1360           && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
1361         {
1362           error ("loop %d's latch is marked as part of irreducible region", i);
1363           err = 1;
1364         }
1365     }
1366
1367   /* Check irreducible loops.  */
1368   if (current_loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1369     {
1370       /* Record old info.  */
1371       irreds = sbitmap_alloc (last_basic_block);
1372       FOR_EACH_BB (bb)
1373         {
1374           edge_iterator ei;
1375           if (bb->flags & BB_IRREDUCIBLE_LOOP)
1376             SET_BIT (irreds, bb->index);
1377           else
1378             RESET_BIT (irreds, bb->index);
1379           FOR_EACH_EDGE (e, ei, bb->succs)
1380             if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1381               e->flags |= EDGE_ALL_FLAGS + 1;
1382         }
1383
1384       /* Recount it.  */
1385       mark_irreducible_loops ();
1386
1387       /* Compare.  */
1388       FOR_EACH_BB (bb)
1389         {
1390           edge_iterator ei;
1391
1392           if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1393               && !TEST_BIT (irreds, bb->index))
1394             {
1395               error ("basic block %d should be marked irreducible", bb->index);
1396               err = 1;
1397             }
1398           else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1399               && TEST_BIT (irreds, bb->index))
1400             {
1401               error ("basic block %d should not be marked irreducible", bb->index);
1402               err = 1;
1403             }
1404           FOR_EACH_EDGE (e, ei, bb->succs)
1405             {
1406               if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1407                   && !(e->flags & (EDGE_ALL_FLAGS + 1)))
1408                 {
1409                   error ("edge from %d to %d should be marked irreducible",
1410                          e->src->index, e->dest->index);
1411                   err = 1;
1412                 }
1413               else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1414                        && (e->flags & (EDGE_ALL_FLAGS + 1)))
1415                 {
1416                   error ("edge from %d to %d should not be marked irreducible",
1417                          e->src->index, e->dest->index);
1418                   err = 1;
1419                 }
1420               e->flags &= ~(EDGE_ALL_FLAGS + 1);
1421             }
1422         }
1423       free (irreds);
1424     }
1425
1426   /* Check the recorded loop exits.  */
1427   FOR_EACH_LOOP (li, loop, 0)
1428     {
1429       if (loop->exits.e != NULL)
1430         {
1431           error ("corrupted head of the exits list of loop %d",
1432                  loop->num);
1433           err = 1;
1434         }
1435       else
1436         {
1437           /* Check that the list forms a cycle, and all elements except
1438              for the head are nonnull.  */
1439           for (mexit = &loop->exits, exit = mexit->next, i = 0;
1440                exit->e && exit != mexit;
1441                exit = exit->next)
1442             {
1443               if (i++ & 1)
1444                 mexit = mexit->next;
1445             }
1446
1447           if (exit != &loop->exits)
1448             {
1449               error ("corrupted exits list of loop %d", loop->num);
1450               err = 1;
1451             }
1452         }
1453
1454       if ((current_loops->state & LOOPS_HAVE_RECORDED_EXITS) == 0)
1455         {
1456           if (loop->exits.next != &loop->exits)
1457             {
1458               error ("nonempty exits list of loop %d, but exits are not recorded",
1459                      loop->num);
1460               err = 1;
1461             }
1462         }
1463     }
1464
1465   if (current_loops->state & LOOPS_HAVE_RECORDED_EXITS)
1466     {
1467       unsigned n_exits = 0, eloops;
1468
1469       memset (sizes, 0, sizeof (unsigned) * num);
1470       FOR_EACH_BB (bb)
1471         {
1472           edge_iterator ei;
1473           if (bb->loop_father == current_loops->tree_root)
1474             continue;
1475           FOR_EACH_EDGE (e, ei, bb->succs)
1476             {
1477               if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
1478                 continue;
1479
1480               n_exits++;
1481               exit = get_exit_descriptions (e);
1482               if (!exit)
1483                 {
1484                   error ("Exit %d->%d not recorded",
1485                          e->src->index, e->dest->index);
1486                   err = 1;
1487                 }
1488               eloops = 0;
1489               for (; exit; exit = exit->next_e)
1490                 eloops++;
1491
1492               for (loop = bb->loop_father;
1493                    loop != e->dest->loop_father;
1494                    loop = loop->outer)
1495                 {
1496                   eloops--;
1497                   sizes[loop->num]++;
1498                 }
1499
1500               if (eloops != 0)
1501                 {
1502                   error ("Wrong list of exited loops for edge  %d->%d",
1503                          e->src->index, e->dest->index);
1504                   err = 1;
1505                 }
1506             }
1507         }
1508
1509       if (n_exits != htab_elements (current_loops->exits))
1510         {
1511           error ("Too many loop exits recorded");
1512           err = 1;
1513         }
1514
1515       FOR_EACH_LOOP (li, loop, 0)
1516         {
1517           eloops = 0;
1518           for (exit = loop->exits.next; exit->e; exit = exit->next)
1519             eloops++;
1520           if (eloops != sizes[loop->num])
1521             {
1522               error ("%d exits recorded for loop %d (having %d exits)",
1523                      eloops, loop->num, sizes[loop->num]);
1524               err = 1;
1525             }
1526         }
1527     }
1528
1529   gcc_assert (!err);
1530
1531   free (sizes);
1532 }
1533
1534 /* Returns latch edge of LOOP.  */
1535 edge
1536 loop_latch_edge (const struct loop *loop)
1537 {
1538   return find_edge (loop->latch, loop->header);
1539 }
1540
1541 /* Returns preheader edge of LOOP.  */
1542 edge
1543 loop_preheader_edge (const struct loop *loop)
1544 {
1545   edge e;
1546   edge_iterator ei;
1547
1548   FOR_EACH_EDGE (e, ei, loop->header->preds)
1549     if (e->src != loop->latch)
1550       break;
1551
1552   return e;
1553 }
1554
1555 /* Returns true if E is an exit of LOOP.  */
1556
1557 bool
1558 loop_exit_edge_p (const struct loop *loop, edge e)
1559 {
1560   return (flow_bb_inside_loop_p (loop, e->src)
1561           && !flow_bb_inside_loop_p (loop, e->dest));
1562 }
1563
1564 /* Returns the single exit edge of LOOP, or NULL if LOOP has either no exit
1565    or more than one exit.  If loops do not have the exits recorded, NULL
1566    is returned always.  */
1567
1568 edge
1569 single_exit (const struct loop *loop)
1570 {
1571   struct loop_exit *exit = loop->exits.next;
1572
1573   if ((current_loops->state & LOOPS_HAVE_RECORDED_EXITS) == 0)
1574     return NULL;
1575
1576   if (exit->e && exit->next == &loop->exits)
1577     return exit->e;
1578   else
1579     return NULL;
1580 }