gcc/cfgloop.c

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