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