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