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