gcc/cfgloop.c

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