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