gcc/cfgloop.c

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