gcc/cfgloop.c

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