gcc/cfgloop.c

   1 /* Natural loop discovery code for GNU compiler.
   2    Copyright (C) 2000, 2001 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, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "rtl.h"
  24 #include "hard-reg-set.h"
  25 #include "basic-block.h"
  26
  27 static void flow_loops_cfg_dump         PARAMS ((const struct loops *,
  28                                                  FILE *));
  29 static int flow_loop_nested_p           PARAMS ((struct loop *,
  30                                                  struct loop *));
  31 static int flow_loop_entry_edges_find   PARAMS ((basic_block, const sbitmap,
  32                                                  edge **));
  33 static int flow_loop_exit_edges_find    PARAMS ((const sbitmap, edge **));
  34 static int flow_loop_nodes_find PARAMS ((basic_block, basic_block, sbitmap));
  35 static void flow_loop_pre_header_scan PARAMS ((struct loop *));
  36 static basic_block flow_loop_pre_header_find PARAMS ((basic_block,
  37                                                       const sbitmap *));
  38 static void flow_loop_tree_node_add     PARAMS ((struct loop *, struct loop *));
  39 static void flow_loops_tree_build       PARAMS ((struct loops *));
  40 static int flow_loop_level_compute      PARAMS ((struct loop *, int));
  41 static int flow_loops_level_compute     PARAMS ((struct loops *));
  42 \f
  43 /* Dump loop related CFG information.  */
  44
  45 static void
  46 flow_loops_cfg_dump (loops, file)
  47      const struct loops *loops;
  48      FILE *file;
  49 {
  50   int i;
  51
  52   if (! loops->num || ! file || ! loops->cfg.dom)
  53     return;
  54
  55   for (i = 0; i < n_basic_blocks; i++)
  56     {
  57       edge succ;
  58
  59       fprintf (file, ";; %d succs { ", i);
  60       for (succ = BASIC_BLOCK (i)->succ; succ; succ = succ->succ_next)
  61         fprintf (file, "%d ", succ->dest->index);
  62       flow_nodes_print ("} dom", loops->cfg.dom[i], file);
  63     }
  64
  65   /* Dump the DFS node order.  */
  66   if (loops->cfg.dfs_order)
  67     {
  68       fputs (";; DFS order: ", file);
  69       for (i = 0; i < n_basic_blocks; i++)
  70         fprintf (file, "%d ", loops->cfg.dfs_order[i]);
  71       fputs ("\n", file);
  72     }
  73   /* Dump the reverse completion node order.  */
  74   if (loops->cfg.rc_order)
  75     {
  76       fputs (";; RC order: ", file);
  77       for (i = 0; i < n_basic_blocks; i++)
  78         fprintf (file, "%d ", loops->cfg.rc_order[i]);
  79       fputs ("\n", file);
  80     }
  81 }
  82
  83 /* Return non-zero if the nodes of LOOP are a subset of OUTER.  */
  84
  85 static int
  86 flow_loop_nested_p (outer, loop)
  87      struct loop *outer;
  88      struct loop *loop;
  89 {
  90   return sbitmap_a_subset_b_p (loop->nodes, outer->nodes);
  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 (loop, file, loop_dump_aux, verbose)
  98      const struct loop *loop;
  99      FILE *file;
 100      void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
 101      int verbose;
 102 {
 103   if (! loop || ! loop->header)
 104     return;
 105
 106   if (loop->first->head && loop->last->end)
 107     fprintf (file, ";;\n;; Loop %d (%d to %d):%s%s\n",
 108             loop->num, INSN_UID (loop->first->head),
 109             INSN_UID (loop->last->end),
 110             loop->shared ? " shared" : "",
 111             loop->invalid ? " invalid" : "");
 112   else
 113     fprintf (file, ";;\n;; Loop %d:%s%s\n", loop->num,
 114              loop->shared ? " shared" : "",
 115              loop->invalid ? " invalid" : "");
 116
 117   fprintf (file, ";;  header %d, latch %d, pre-header %d, first %d, last %d\n",
 118            loop->header->index, loop->latch->index,
 119            loop->pre_header ? loop->pre_header->index : -1,
 120            loop->first->index, loop->last->index);
 121   fprintf (file, ";;  depth %d, level %d, outer %ld\n",
 122            loop->depth, loop->level,
 123            (long) (loop->outer ? loop->outer->num : -1));
 124
 125   if (loop->pre_header_edges)
 126     flow_edge_list_print (";;  pre-header edges", loop->pre_header_edges,
 127                           loop->num_pre_header_edges, file);
 128   flow_edge_list_print (";;  entry edges", loop->entry_edges,
 129                         loop->num_entries, file);
 130   fprintf (file, ";;  %d", loop->num_nodes);
 131   flow_nodes_print (" nodes", loop->nodes, file);
 132   flow_edge_list_print (";;  exit edges", loop->exit_edges,
 133                         loop->num_exits, file);
 134   if (loop->exits_doms)
 135     flow_nodes_print (";;  exit doms", loop->exits_doms, file);
 136   if (loop_dump_aux)
 137     loop_dump_aux (loop, file, verbose);
 138 }
 139
 140 /* Dump the loop information specified by LOOPS to the stream FILE,
 141    using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
 142
 143 void
 144 flow_loops_dump (loops, file, loop_dump_aux, verbose)
 145      const struct loops *loops;
 146      FILE *file;
 147      void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
 148      int verbose;
 149 {
 150   int i;
 151   int num_loops;
 152
 153   num_loops = loops->num;
 154   if (! num_loops || ! file)
 155     return;
 156
 157   fprintf (file, ";; %d loops found, %d levels\n",
 158            num_loops, loops->levels);
 159
 160   for (i = 0; i < num_loops; i++)
 161     {
 162       struct loop *loop = &loops->array[i];
 163
 164       flow_loop_dump (loop, file, loop_dump_aux, verbose);
 165
 166       if (loop->shared)
 167         {
 168           int j;
 169
 170           for (j = 0; j < i; j++)
 171             {
 172               struct loop *oloop = &loops->array[j];
 173
 174               if (loop->header == oloop->header)
 175                 {
 176                   int disjoint;
 177                   int smaller;
 178
 179                   smaller = loop->num_nodes < oloop->num_nodes;
 180
 181                   /* If the union of LOOP and OLOOP is different than
 182                      the larger of LOOP and OLOOP then LOOP and OLOOP
 183                      must be disjoint.  */
 184                   disjoint = ! flow_loop_nested_p (smaller ? loop : oloop,
 185                                                    smaller ? oloop : loop);
 186                   fprintf (file,
 187                            ";; loop header %d shared by loops %d, %d %s\n",
 188                            loop->header->index, i, j,
 189                            disjoint ? "disjoint" : "nested");
 190                 }
 191             }
 192         }
 193     }
 194
 195   if (verbose)
 196     flow_loops_cfg_dump (loops, file);
 197 }
 198
 199 /* Free all the memory allocated for LOOPS.  */
 200
 201 void
 202 flow_loops_free (loops)
 203      struct loops *loops;
 204 {
 205   if (loops->array)
 206     {
 207       int i;
 208
 209       if (! loops->num)
 210         abort ();
 211
 212       /* Free the loop descriptors.  */
 213       for (i = 0; i < loops->num; i++)
 214         {
 215           struct loop *loop = &loops->array[i];
 216
 217           if (loop->pre_header_edges)
 218             free (loop->pre_header_edges);
 219           if (loop->nodes)
 220             sbitmap_free (loop->nodes);
 221           if (loop->entry_edges)
 222             free (loop->entry_edges);
 223           if (loop->exit_edges)
 224             free (loop->exit_edges);
 225           if (loop->exits_doms)
 226             sbitmap_free (loop->exits_doms);
 227         }
 228       free (loops->array);
 229       loops->array = NULL;
 230
 231       if (loops->cfg.dom)
 232         sbitmap_vector_free (loops->cfg.dom);
 233       if (loops->cfg.dfs_order)
 234         free (loops->cfg.dfs_order);
 235
 236       if (loops->shared_headers)
 237         sbitmap_free (loops->shared_headers);
 238     }
 239 }
 240
 241 /* Find the entry edges into the loop with header HEADER and nodes
 242    NODES and store in ENTRY_EDGES array.  Return the number of entry
 243    edges from the loop.  */
 244
 245 static int
 246 flow_loop_entry_edges_find (header, nodes, entry_edges)
 247      basic_block header;
 248      const sbitmap nodes;
 249      edge **entry_edges;
 250 {
 251   edge e;
 252   int num_entries;
 253
 254   *entry_edges = NULL;
 255
 256   num_entries = 0;
 257   for (e = header->pred; e; e = e->pred_next)
 258     {
 259       basic_block src = e->src;
 260
 261       if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index))
 262         num_entries++;
 263     }
 264
 265   if (! num_entries)
 266     abort ();
 267
 268   *entry_edges = (edge *) xmalloc (num_entries * sizeof (edge *));
 269
 270   num_entries = 0;
 271   for (e = header->pred; e; e = e->pred_next)
 272     {
 273       basic_block src = e->src;
 274
 275       if (src == ENTRY_BLOCK_PTR || ! TEST_BIT (nodes, src->index))
 276         (*entry_edges)[num_entries++] = e;
 277     }
 278
 279   return num_entries;
 280 }
 281
 282 /* Find the exit edges from the loop using the bitmap of loop nodes
 283    NODES and store in EXIT_EDGES array.  Return the number of
 284    exit edges from the loop.  */
 285
 286 static int
 287 flow_loop_exit_edges_find (nodes, exit_edges)
 288      const sbitmap nodes;
 289      edge **exit_edges;
 290 {
 291   edge e;
 292   int node;
 293   int num_exits;
 294
 295   *exit_edges = NULL;
 296
 297   /* Check all nodes within the loop to see if there are any
 298      successors not in the loop.  Note that a node may have multiple
 299      exiting edges ?????  A node can have one jumping edge and one fallthru
 300      edge so only one of these can exit the loop.  */
 301   num_exits = 0;
 302   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
 303     for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
 304       {
 305         basic_block dest = e->dest;
 306
 307         if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
 308             num_exits++;
 309       }
 310   });
 311
 312   if (! num_exits)
 313     return 0;
 314
 315   *exit_edges = (edge *) xmalloc (num_exits * sizeof (edge *));
 316
 317   /* Store all exiting edges into an array.  */
 318   num_exits = 0;
 319   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {
 320     for (e = BASIC_BLOCK (node)->succ; e; e = e->succ_next)
 321       {
 322         basic_block dest = e->dest;
 323
 324         if (dest == EXIT_BLOCK_PTR || ! TEST_BIT (nodes, dest->index))
 325           (*exit_edges)[num_exits++] = e;
 326       }
 327   });
 328
 329   return num_exits;
 330 }
 331
 332 /* Find the nodes contained within the loop with header HEADER and
 333    latch LATCH and store in NODES.  Return the number of nodes within
 334    the loop.  */
 335
 336 static int
 337 flow_loop_nodes_find (header, latch, nodes)
 338      basic_block header;
 339      basic_block latch;
 340      sbitmap nodes;
 341 {
 342   basic_block *stack;
 343   int sp;
 344   int num_nodes = 0;
 345
 346   stack = (basic_block *) xmalloc (n_basic_blocks * sizeof (basic_block));
 347   sp = 0;
 348
 349   /* Start with only the loop header in the set of loop nodes.  */
 350   sbitmap_zero (nodes);
 351   SET_BIT (nodes, header->index);
 352   num_nodes++;
 353   header->loop_depth++;
 354
 355   /* Push the loop latch on to the stack.  */
 356   if (! TEST_BIT (nodes, latch->index))
 357     {
 358       SET_BIT (nodes, latch->index);
 359       latch->loop_depth++;
 360       num_nodes++;
 361       stack[sp++] = latch;
 362     }
 363
 364   while (sp)
 365     {
 366       basic_block node;
 367       edge e;
 368
 369       node = stack[--sp];
 370       for (e = node->pred; e; e = e->pred_next)
 371         {
 372           basic_block ancestor = e->src;
 373
 374           /* If each ancestor not marked as part of loop, add to set of
 375              loop nodes and push on to stack.  */
 376           if (ancestor != ENTRY_BLOCK_PTR
 377               && ! TEST_BIT (nodes, ancestor->index))
 378             {
 379               SET_BIT (nodes, ancestor->index);
 380               ancestor->loop_depth++;
 381               num_nodes++;
 382               stack[sp++] = ancestor;
 383             }
 384         }
 385     }
 386   free (stack);
 387   return num_nodes;
 388 }
 389
 390 /* Find the root node of the loop pre-header extended basic block and
 391    the edges along the trace from the root node to the loop header.  */
 392
 393 static void
 394 flow_loop_pre_header_scan (loop)
 395      struct loop *loop;
 396 {
 397   int num = 0;
 398   basic_block ebb;
 399
 400   loop->num_pre_header_edges = 0;
 401
 402   if (loop->num_entries != 1)
 403      return;
 404
 405   ebb = loop->entry_edges[0]->src;
 406
 407   if (ebb != ENTRY_BLOCK_PTR)
 408     {
 409       edge e;
 410
 411       /* Count number of edges along trace from loop header to
 412          root of pre-header extended basic block.  Usually this is
 413          only one or two edges.  */
 414       num++;
 415       while (ebb->pred->src != ENTRY_BLOCK_PTR && ! ebb->pred->pred_next)
 416         {
 417           ebb = ebb->pred->src;
 418           num++;
 419         }
 420
 421       loop->pre_header_edges = (edge *) xmalloc (num * sizeof (edge *));
 422       loop->num_pre_header_edges = num;
 423
 424       /* Store edges in order that they are followed.   The source
 425          of the first edge is the root node of the pre-header extended
 426          basic block and the destination of the last last edge is
 427          the loop header.  */
 428       for (e = loop->entry_edges[0]; num; e = e->src->pred)
 429         {
 430           loop->pre_header_edges[--num] = e;
 431         }
 432     }
 433 }
 434
 435 /* Return the block for the pre-header of the loop with header
 436    HEADER where DOM specifies the dominator information.  Return NULL if
 437    there is no pre-header.  */
 438
 439 static basic_block
 440 flow_loop_pre_header_find (header, dom)
 441      basic_block header;
 442      const sbitmap *dom;
 443 {
 444   basic_block pre_header;
 445   edge e;
 446
 447   /* If block p is a predecessor of the header and is the only block
 448      that the header does not dominate, then it is the pre-header.  */
 449   pre_header = NULL;
 450   for (e = header->pred; e; e = e->pred_next)
 451     {
 452       basic_block node = e->src;
 453
 454       if (node != ENTRY_BLOCK_PTR
 455           && ! TEST_BIT (dom[node->index], header->index))
 456         {
 457           if (pre_header == NULL)
 458             pre_header = node;
 459           else
 460             {
 461               /* There are multiple edges into the header from outside
 462                  the loop so there is no pre-header block.  */
 463               pre_header = NULL;
 464               break;
 465             }
 466         }
 467     }
 468   return pre_header;
 469 }
 470
 471 /* Add LOOP to the loop hierarchy tree where PREVLOOP was the loop
 472    previously added.  The insertion algorithm assumes that the loops
 473    are added in the order found by a depth first search of the CFG.  */
 474
 475 static void
 476 flow_loop_tree_node_add (prevloop, loop)
 477      struct loop *prevloop;
 478      struct loop *loop;
 479 {
 480
 481   if (flow_loop_nested_p (prevloop, loop))
 482     {
 483       prevloop->inner = loop;
 484       loop->outer = prevloop;
 485       return;
 486     }
 487
 488   while (prevloop->outer)
 489     {
 490       if (flow_loop_nested_p (prevloop->outer, loop))
 491         {
 492           prevloop->next = loop;
 493           loop->outer = prevloop->outer;
 494           return;
 495         }
 496       prevloop = prevloop->outer;
 497     }
 498
 499   prevloop->next = loop;
 500   loop->outer = NULL;
 501 }
 502
 503 /* Build the loop hierarchy tree for LOOPS.  */
 504
 505 static void
 506 flow_loops_tree_build (loops)
 507      struct loops *loops;
 508 {
 509   int i;
 510   int num_loops;
 511
 512   num_loops = loops->num;
 513   if (! num_loops)
 514     return;
 515
 516   /* Root the loop hierarchy tree with the first loop found.
 517      Since we used a depth first search this should be the
 518      outermost loop.  */
 519   loops->tree_root = &loops->array[0];
 520   loops->tree_root->outer = loops->tree_root->inner = loops->tree_root->next = NULL;
 521
 522   /* Add the remaining loops to the tree.  */
 523   for (i = 1; i < num_loops; i++)
 524     flow_loop_tree_node_add (&loops->array[i - 1], &loops->array[i]);
 525 }
 526
 527 /* Helper function to compute loop nesting depth and enclosed loop level
 528    for the natural loop specified by LOOP at the loop depth DEPTH.
 529    Returns the loop level.  */
 530
 531 static int
 532 flow_loop_level_compute (loop, depth)
 533      struct loop *loop;
 534      int depth;
 535 {
 536   struct loop *inner;
 537   int level = 1;
 538
 539   if (! loop)
 540     return 0;
 541
 542   /* Traverse loop tree assigning depth and computing level as the
 543      maximum level of all the inner loops of this loop.  The loop
 544      level is equivalent to the height of the loop in the loop tree
 545      and corresponds to the number of enclosed loop levels (including
 546      itself).  */
 547   for (inner = loop->inner; inner; inner = inner->next)
 548     {
 549       int ilevel;
 550
 551       ilevel = flow_loop_level_compute (inner, depth + 1) + 1;
 552
 553       if (ilevel > level)
 554         level = ilevel;
 555     }
 556   loop->level = level;
 557   loop->depth = depth;
 558   return level;
 559 }
 560
 561 /* Compute the loop nesting depth and enclosed loop level for the loop
 562    hierarchy tree specified by LOOPS.  Return the maximum enclosed loop
 563    level.  */
 564
 565 static int
 566 flow_loops_level_compute (loops)
 567      struct loops *loops;
 568 {
 569   struct loop *loop;
 570   int level;
 571   int levels = 0;
 572
 573   /* Traverse all the outer level loops.  */
 574   for (loop = loops->tree_root; loop; loop = loop->next)
 575     {
 576       level = flow_loop_level_compute (loop, 1);
 577       if (level > levels)
 578         levels = level;
 579     }
 580   return levels;
 581 }
 582
 583 /* Scan a single natural loop specified by LOOP collecting information
 584    about it specified by FLAGS.  */
 585
 586 int
 587 flow_loop_scan (loops, loop, flags)
 588      struct loops *loops;
 589      struct loop *loop;
 590      int flags;
 591 {
 592   /* Determine prerequisites.  */
 593   if ((flags & LOOP_EXITS_DOMS) && ! loop->exit_edges)
 594     flags |= LOOP_EXIT_EDGES;
 595
 596   if (flags & LOOP_ENTRY_EDGES)
 597     {
 598       /* Find edges which enter the loop header.
 599          Note that the entry edges should only
 600          enter the header of a natural loop.  */
 601       loop->num_entries
 602         = flow_loop_entry_edges_find (loop->header,
 603                                       loop->nodes,
 604                                       &loop->entry_edges);
 605     }
 606
 607   if (flags & LOOP_EXIT_EDGES)
 608     {
 609       /* Find edges which exit the loop.  */
 610       loop->num_exits
 611         = flow_loop_exit_edges_find (loop->nodes,
 612                                      &loop->exit_edges);
 613     }
 614
 615   if (flags & LOOP_EXITS_DOMS)
 616     {
 617       int j;
 618
 619       /* Determine which loop nodes dominate all the exits
 620          of the loop.  */
 621       loop->exits_doms = sbitmap_alloc (n_basic_blocks);
 622       sbitmap_copy (loop->exits_doms, loop->nodes);
 623       for (j = 0; j < loop->num_exits; j++)
 624         sbitmap_a_and_b (loop->exits_doms, loop->exits_doms,
 625                          loops->cfg.dom[loop->exit_edges[j]->src->index]);
 626
 627       /* The header of a natural loop must dominate
 628          all exits.  */
 629       if (! TEST_BIT (loop->exits_doms, loop->header->index))
 630         abort ();
 631     }
 632
 633   if (flags & LOOP_PRE_HEADER)
 634     {
 635       /* Look to see if the loop has a pre-header node.  */
 636       loop->pre_header
 637         = flow_loop_pre_header_find (loop->header, loops->cfg.dom);
 638
 639       /* Find the blocks within the extended basic block of
 640          the loop pre-header.  */
 641       flow_loop_pre_header_scan (loop);
 642     }
 643   return 1;
 644 }
 645
 646 /* Find all the natural loops in the function and save in LOOPS structure
 647    and recalculate loop_depth information in basic block structures.
 648    FLAGS controls which loop information is collected.
 649    Return the number of natural loops found.  */
 650
 651 int
 652 flow_loops_find (loops, flags)
 653      struct loops *loops;
 654      int flags;
 655 {
 656   int i;
 657   int b;
 658   int num_loops;
 659   edge e;
 660   sbitmap headers;
 661   sbitmap *dom;
 662   int *dfs_order;
 663   int *rc_order;
 664
 665   /* This function cannot be repeatedly called with different
 666      flags to build up the loop information.  The loop tree
 667      must always be built if this function is called.  */
 668   if (! (flags & LOOP_TREE))
 669     abort ();
 670
 671   memset (loops, 0, sizeof (*loops));
 672
 673   /* Taking care of this degenerate case makes the rest of
 674      this code simpler.  */
 675   if (n_basic_blocks == 0)
 676     return 0;
 677
 678   dfs_order = NULL;
 679   rc_order = NULL;
 680
 681   /* Compute the dominators.  */
 682   dom = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
 683   calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
 684
 685   /* Count the number of loop edges (back edges).  This should be the
 686      same as the number of natural loops.  */
 687
 688   num_loops = 0;
 689   for (b = 0; b < n_basic_blocks; b++)
 690     {
 691       basic_block header;
 692
 693       header = BASIC_BLOCK (b);
 694       header->loop_depth = 0;
 695
 696       for (e = header->pred; e; e = e->pred_next)
 697         {
 698           basic_block latch = e->src;
 699
 700           /* Look for back edges where a predecessor is dominated
 701              by this block.  A natural loop has a single entry
 702              node (header) that dominates all the nodes in the
 703              loop.  It also has single back edge to the header
 704              from a latch node.  Note that multiple natural loops
 705              may share the same header.  */
 706           if (b != header->index)
 707             abort ();
 708
 709           if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index], b))
 710             num_loops++;
 711         }
 712     }
 713
 714   if (num_loops)
 715     {
 716       /* Compute depth first search order of the CFG so that outer
 717          natural loops will be found before inner natural loops.  */
 718       dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
 719       rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
 720       flow_depth_first_order_compute (dfs_order, rc_order);
 721
 722       /* Save CFG derived information to avoid recomputing it.  */
 723       loops->cfg.dom = dom;
 724       loops->cfg.dfs_order = dfs_order;
 725       loops->cfg.rc_order = rc_order;
 726
 727       /* Allocate loop structures.  */
 728       loops->array
 729         = (struct loop *) xcalloc (num_loops, sizeof (struct loop));
 730
 731       headers = sbitmap_alloc (n_basic_blocks);
 732       sbitmap_zero (headers);
 733
 734       loops->shared_headers = sbitmap_alloc (n_basic_blocks);
 735       sbitmap_zero (loops->shared_headers);
 736
 737       /* Find and record information about all the natural loops
 738          in the CFG.  */
 739       num_loops = 0;
 740       for (b = 0; b < n_basic_blocks; b++)
 741         {
 742           basic_block header;
 743
 744           /* Search the nodes of the CFG in reverse completion order
 745              so that we can find outer loops first.  */
 746           header = BASIC_BLOCK (rc_order[b]);
 747
 748           /* Look for all the possible latch blocks for this header.  */
 749           for (e = header->pred; e; e = e->pred_next)
 750             {
 751               basic_block latch = e->src;
 752
 753               /* Look for back edges where a predecessor is dominated
 754                  by this block.  A natural loop has a single entry
 755                  node (header) that dominates all the nodes in the
 756                  loop.  It also has single back edge to the header
 757                  from a latch node.  Note that multiple natural loops
 758                  may share the same header.  */
 759               if (latch != ENTRY_BLOCK_PTR
 760                   && TEST_BIT (dom[latch->index], header->index))
 761                 {
 762                   struct loop *loop;
 763
 764                   loop = loops->array + num_loops;
 765
 766                   loop->header = header;
 767                   loop->latch = latch;
 768                   loop->num = num_loops;
 769
 770                   num_loops++;
 771                 }
 772             }
 773         }
 774
 775       for (i = 0; i < num_loops; i++)
 776         {
 777           struct loop *loop = &loops->array[i];
 778
 779           /* Keep track of blocks that are loop headers so
 780              that we can tell which loops should be merged.  */
 781           if (TEST_BIT (headers, loop->header->index))
 782             SET_BIT (loops->shared_headers, loop->header->index);
 783           SET_BIT (headers, loop->header->index);
 784
 785           /* Find nodes contained within the loop.  */
 786           loop->nodes = sbitmap_alloc (n_basic_blocks);
 787           loop->num_nodes
 788             = flow_loop_nodes_find (loop->header, loop->latch, loop->nodes);
 789
 790           /* Compute first and last blocks within the loop.
 791              These are often the same as the loop header and
 792              loop latch respectively, but this is not always
 793              the case.  */
 794           loop->first
 795             = BASIC_BLOCK (sbitmap_first_set_bit (loop->nodes));
 796           loop->last
 797             = BASIC_BLOCK (sbitmap_last_set_bit (loop->nodes));
 798
 799           flow_loop_scan (loops, loop, flags);
 800         }
 801
 802       /* Natural loops with shared headers may either be disjoint or
 803          nested.  Disjoint loops with shared headers cannot be inner
 804          loops and should be merged.  For now just mark loops that share
 805          headers.  */
 806       for (i = 0; i < num_loops; i++)
 807         if (TEST_BIT (loops->shared_headers, loops->array[i].header->index))
 808           loops->array[i].shared = 1;
 809
 810       sbitmap_free (headers);
 811     }
 812   else
 813     {
 814       sbitmap_vector_free (dom);
 815     }
 816
 817   loops->num = num_loops;
 818
 819   /* Build the loop hierarchy tree.  */
 820   flow_loops_tree_build (loops);
 821
 822   /* Assign the loop nesting depth and enclosed loop level for each
 823      loop.  */
 824   loops->levels = flow_loops_level_compute (loops);
 825
 826   return num_loops;
 827 }
 828
 829 /* Update the information regarding the loops in the CFG
 830    specified by LOOPS.  */
 831 int
 832 flow_loops_update (loops, flags)
 833      struct loops *loops;
 834      int flags;
 835 {
 836   /* One day we may want to update the current loop data.  For now
 837      throw away the old stuff and rebuild what we need.  */
 838   if (loops->array)
 839     flow_loops_free (loops);
 840
 841   return flow_loops_find (loops, flags);
 842 }
 843
 844 /* Return non-zero if edge E enters header of LOOP from outside of LOOP.  */
 845
 846 int
 847 flow_loop_outside_edge_p (loop, e)
 848      const struct loop *loop;
 849      edge e;
 850 {
 851   if (e->dest != loop->header)
 852     abort ();
 853   return (e->src == ENTRY_BLOCK_PTR) || ! TEST_BIT (loop->nodes, e->src->index);
 854 }