contrib/gcc-4.4/gcc/cfgloop.c

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