gcc/cfgloop.c

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