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