gcc/cfgloop.c

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