gcc/cfgloop.c

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