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