gcc/cfgloop.c

   1 /* Natural loop discovery code for GNU compiler.
   2    Copyright (C) 2000, 2001, 2003, 2004 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 "coretypes.h"
  24 #include "tm.h"
  25 #include "rtl.h"
  26 #include "hard-reg-set.h"
  27 #include "basic-block.h"
  28 #include "toplev.h"
  29 #include "cfgloop.h"
  30 #include "flags.h"
  31
  32 /* Ratio of frequencies of edges so that one of more latch edges is
  33    considered to belong to inner loop with same header.  */
  34 #define HEAVY_EDGE_RATIO 8
  35
  36 #define HEADER_BLOCK(B) (* (int *) (B)->aux)
  37 #define LATCH_EDGE(E) (*(int *) (E)->aux)
  38
  39 static void flow_loops_cfg_dump (const struct loops *, FILE *);
  40 static void flow_loop_entry_edges_find (struct loop *);
  41 static void flow_loop_exit_edges_find (struct loop *);
  42 static int flow_loop_nodes_find (basic_block, struct loop *);
  43 static void flow_loop_pre_header_scan (struct loop *);
  44 static basic_block flow_loop_pre_header_find (basic_block);
  45 static int flow_loop_level_compute (struct loop *);
  46 static int flow_loops_level_compute (struct loops *);
  47 static void establish_preds (struct loop *);
  48 static void canonicalize_loop_headers (void);
  49 static bool glb_enum_p (basic_block, void *);
  50 \f
  51 /* Dump loop related CFG information.  */
  52
  53 static void
  54 flow_loops_cfg_dump (const struct loops *loops, FILE *file)
  55 {
  56   int i;
  57   basic_block bb;
  58
  59   if (! loops->num || ! file)
  60     return;
  61
  62   FOR_EACH_BB (bb)
  63     {
  64       edge succ;
  65
  66       fprintf (file, ";; %d succs { ", bb->index);
  67       for (succ = bb->succ; succ; succ = succ->succ_next)
  68         fprintf (file, "%d ", succ->dest->index);
  69       fprintf (file, "}\n");
  70     }
  71
  72   /* Dump the DFS node order.  */
  73   if (loops->cfg.dfs_order)
  74     {
  75       fputs (";; DFS order: ", file);
  76       for (i = 0; i < n_basic_blocks; i++)
  77         fprintf (file, "%d ", loops->cfg.dfs_order[i]);
  78
  79       fputs ("\n", file);
  80     }
  81
  82   /* Dump the reverse completion node order.  */
  83   if (loops->cfg.rc_order)
  84     {
  85       fputs (";; RC order: ", file);
  86       for (i = 0; i < n_basic_blocks; i++)
  87         fprintf (file, "%d ", loops->cfg.rc_order[i]);
  88
  89       fputs ("\n", file);
  90     }
  91 }
  92
  93 /* Return nonzero if the nodes of LOOP are a subset of OUTER.  */
  94
  95 bool
  96 flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
  97 {
  98   return loop->depth > outer->depth
  99          && loop->pred[outer->depth] == outer;
 100 }
 101
 102 /* Dump the loop information specified by LOOP to the stream FILE
 103    using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
 104
 105 void
 106 flow_loop_dump (const struct loop *loop, FILE *file,
 107                 void (*loop_dump_aux) (const struct loop *, FILE *, int),
 108                 int verbose)
 109 {
 110   basic_block *bbs;
 111   unsigned i;
 112
 113   if (! loop || ! loop->header)
 114     return;
 115
 116   fprintf (file, ";;\n;; Loop %d:%s\n", loop->num,
 117              loop->invalid ? " invalid" : "");
 118
 119   fprintf (file, ";;  header %d, latch %d, pre-header %d\n",
 120            loop->header->index, loop->latch->index,
 121            loop->pre_header ? loop->pre_header->index : -1);
 122   fprintf (file, ";;  depth %d, level %d, outer %ld\n",
 123            loop->depth, loop->level,
 124            (long) (loop->outer ? loop->outer->num : -1));
 125
 126   if (loop->pre_header_edges)
 127     flow_edge_list_print (";;  pre-header edges", loop->pre_header_edges,
 128                           loop->num_pre_header_edges, file);
 129
 130   flow_edge_list_print (";;  entry edges", loop->entry_edges,
 131                         loop->num_entries, file);
 132   fprintf (file, ";;  nodes:");
 133   bbs = get_loop_body (loop);
 134   for (i = 0; i < loop->num_nodes; i++)
 135     fprintf (file, " %d", bbs[i]->index);
 136   free (bbs);
 137   fprintf (file, "\n");
 138   flow_edge_list_print (";;  exit edges", loop->exit_edges,
 139                         loop->num_exits, file);
 140
 141   if (loop_dump_aux)
 142     loop_dump_aux (loop, file, verbose);
 143 }
 144
 145 /* Dump the loop information specified by LOOPS to the stream FILE,
 146    using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
 147
 148 void
 149 flow_loops_dump (const struct loops *loops, FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
 150 {
 151   int i;
 152   int num_loops;
 153
 154   num_loops = loops->num;
 155   if (! num_loops || ! file)
 156     return;
 157
 158   fprintf (file, ";; %d loops found, %d levels\n",
 159            num_loops, loops->levels);
 160
 161   for (i = 0; i < num_loops; i++)
 162     {
 163       struct loop *loop = loops->parray[i];
 164
 165       if (!loop)
 166         continue;
 167
 168       flow_loop_dump (loop, file, loop_dump_aux, verbose);
 169     }
 170
 171   if (verbose)
 172     flow_loops_cfg_dump (loops, file);
 173 }
 174
 175 /* Free data allocated for LOOP.  */
 176 void
 177 flow_loop_free (struct loop *loop)
 178 {
 179   if (loop->pre_header_edges)
 180     free (loop->pre_header_edges);
 181   if (loop->entry_edges)
 182     free (loop->entry_edges);
 183   if (loop->exit_edges)
 184     free (loop->exit_edges);
 185   if (loop->pred)
 186     free (loop->pred);
 187   free (loop);
 188 }
 189
 190 /* Free all the memory allocated for LOOPS.  */
 191
 192 void
 193 flow_loops_free (struct loops *loops)
 194 {
 195   if (loops->parray)
 196     {
 197       unsigned i;
 198
 199       if (! loops->num)
 200         abort ();
 201
 202       /* Free the loop descriptors.  */
 203       for (i = 0; i < loops->num; i++)
 204         {
 205           struct loop *loop = loops->parray[i];
 206
 207           if (!loop)
 208             continue;
 209
 210           flow_loop_free (loop);
 211         }
 212
 213       free (loops->parray);
 214       loops->parray = NULL;
 215
 216       if (loops->cfg.dfs_order)
 217         free (loops->cfg.dfs_order);
 218       if (loops->cfg.rc_order)
 219         free (loops->cfg.rc_order);
 220
 221     }
 222 }
 223
 224 /* Find the entry edges into the LOOP.  */
 225
 226 static void
 227 flow_loop_entry_edges_find (struct loop *loop)
 228 {
 229   edge e;
 230   int num_entries;
 231
 232   num_entries = 0;
 233   for (e = loop->header->pred; e; e = e->pred_next)
 234     {
 235       if (flow_loop_outside_edge_p (loop, e))
 236         num_entries++;
 237     }
 238
 239   if (! num_entries)
 240     abort ();
 241
 242   loop->entry_edges = xmalloc (num_entries * sizeof (edge *));
 243
 244   num_entries = 0;
 245   for (e = loop->header->pred; e; e = e->pred_next)
 246     {
 247       if (flow_loop_outside_edge_p (loop, e))
 248         loop->entry_edges[num_entries++] = e;
 249     }
 250
 251   loop->num_entries = num_entries;
 252 }
 253
 254 /* Find the exit edges from the LOOP.  */
 255
 256 static void
 257 flow_loop_exit_edges_find (struct loop *loop)
 258 {
 259   edge e;
 260   basic_block node, *bbs;
 261   unsigned num_exits, i;
 262
 263   loop->exit_edges = NULL;
 264   loop->num_exits = 0;
 265
 266   /* Check all nodes within the loop to see if there are any
 267      successors not in the loop.  Note that a node may have multiple
 268      exiting edges.  */
 269   num_exits = 0;
 270   bbs = get_loop_body (loop);
 271   for (i = 0; i < loop->num_nodes; i++)
 272     {
 273       node = bbs[i];
 274       for (e = node->succ; e; e = e->succ_next)
 275         {
 276           basic_block dest = e->dest;
 277
 278           if (!flow_bb_inside_loop_p (loop, dest))
 279             num_exits++;
 280         }
 281     }
 282
 283   if (! num_exits)
 284     {
 285       free (bbs);
 286       return;
 287     }
 288
 289   loop->exit_edges = xmalloc (num_exits * sizeof (edge *));
 290
 291   /* Store all exiting edges into an array.  */
 292   num_exits = 0;
 293   for (i = 0; i < loop->num_nodes; i++)
 294     {
 295       node = bbs[i];
 296       for (e = node->succ; e; e = e->succ_next)
 297         {
 298           basic_block dest = e->dest;
 299
 300           if (!flow_bb_inside_loop_p (loop, dest))
 301             loop->exit_edges[num_exits++] = e;
 302       }
 303     }
 304   free (bbs);
 305   loop->num_exits = num_exits;
 306 }
 307
 308 /* Find the nodes contained within the LOOP with header HEADER.
 309    Return the number of nodes within the loop.  */
 310
 311 static int
 312 flow_loop_nodes_find (basic_block header, struct loop *loop)
 313 {
 314   basic_block *stack;
 315   int sp;
 316   int num_nodes = 1;
 317
 318   header->loop_father = loop;
 319   header->loop_depth = loop->depth;
 320
 321   if (loop->latch->loop_father != loop)
 322     {
 323       stack = xmalloc (n_basic_blocks * sizeof (basic_block));
 324       sp = 0;
 325       num_nodes++;
 326       stack[sp++] = loop->latch;
 327       loop->latch->loop_father = loop;
 328       loop->latch->loop_depth = loop->depth;
 329
 330       while (sp)
 331         {
 332           basic_block node;
 333           edge e;
 334
 335           node = stack[--sp];
 336
 337           for (e = node->pred; e; e = e->pred_next)
 338             {
 339               basic_block ancestor = e->src;
 340
 341               if (ancestor != ENTRY_BLOCK_PTR
 342                   && ancestor->loop_father != loop)
 343                 {
 344                   ancestor->loop_father = loop;
 345                   ancestor->loop_depth = loop->depth;
 346                   num_nodes++;
 347                   stack[sp++] = ancestor;
 348                 }
 349             }
 350         }
 351       free (stack);
 352     }
 353   return num_nodes;
 354 }
 355
 356 /* Find the root node of the loop pre-header extended basic block and
 357    the edges along the trace from the root node to the loop header.  */
 358
 359 static void
 360 flow_loop_pre_header_scan (struct loop *loop)
 361 {
 362   int num;
 363   basic_block ebb;
 364   edge e;
 365
 366   loop->num_pre_header_edges = 0;
 367   if (loop->num_entries != 1)
 368     return;
 369
 370   ebb = loop->entry_edges[0]->src;
 371   if (ebb == ENTRY_BLOCK_PTR)
 372     return;
 373
 374   /* Count number of edges along trace from loop header to
 375      root of pre-header extended basic block.  Usually this is
 376      only one or two edges.  */
 377   for (num = 1; ebb->pred->src != ENTRY_BLOCK_PTR && ! ebb->pred->pred_next;
 378        num++)
 379     ebb = ebb->pred->src;
 380
 381   loop->pre_header_edges = xmalloc (num * sizeof (edge));
 382   loop->num_pre_header_edges = num;
 383
 384   /* Store edges in order that they are followed.  The source of the first edge
 385      is the root node of the pre-header extended basic block and the
 386      destination of the last last edge is the loop header.  */
 387   for (e = loop->entry_edges[0]; num; e = e->src->pred)
 388     loop->pre_header_edges[--num] = e;
 389 }
 390
 391 /* Return the block for the pre-header of the loop with header
 392    HEADER.  Return NULL if there is no pre-header.  */
 393
 394 static basic_block
 395 flow_loop_pre_header_find (basic_block header)
 396 {
 397   basic_block pre_header;
 398   edge e;
 399
 400   /* If block p is a predecessor of the header and is the only block
 401      that the header does not dominate, then it is the pre-header.  */
 402   pre_header = NULL;
 403   for (e = header->pred; e; e = e->pred_next)
 404     {
 405       basic_block node = e->src;
 406
 407       if (node != ENTRY_BLOCK_PTR
 408           && ! dominated_by_p (CDI_DOMINATORS, node, header))
 409         {
 410           if (pre_header == NULL)
 411             pre_header = node;
 412           else
 413             {
 414               /* There are multiple edges into the header from outside
 415                  the loop so there is no pre-header block.  */
 416               pre_header = NULL;
 417               break;
 418             }
 419         }
 420     }
 421
 422   return pre_header;
 423 }
 424
 425 static void
 426 establish_preds (struct loop *loop)
 427 {
 428   struct loop *ploop, *father = loop->outer;
 429
 430   loop->depth = father->depth + 1;
 431   if (loop->pred)
 432     free (loop->pred);
 433   loop->pred = xmalloc (sizeof (struct loop *) * loop->depth);
 434   memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth);
 435   loop->pred[father->depth] = father;
 436
 437   for (ploop = loop->inner; ploop; ploop = ploop->next)
 438     establish_preds (ploop);
 439 }
 440
 441 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
 442    added loop.  If LOOP has some children, take care of that their
 443    pred field will be initialized correctly.  */
 444
 445 void
 446 flow_loop_tree_node_add (struct loop *father, struct loop *loop)
 447 {
 448   loop->next = father->inner;
 449   father->inner = loop;
 450   loop->outer = father;
 451
 452   establish_preds (loop);
 453 }
 454
 455 /* Remove LOOP from the loop hierarchy tree.  */
 456
 457 void
 458 flow_loop_tree_node_remove (struct loop *loop)
 459 {
 460   struct loop *prev, *father;
 461
 462   father = loop->outer;
 463   loop->outer = NULL;
 464
 465   /* Remove loop from the list of sons.  */
 466   if (father->inner == loop)
 467     father->inner = loop->next;
 468   else
 469     {
 470       for (prev = father->inner; prev->next != loop; prev = prev->next);
 471       prev->next = loop->next;
 472     }
 473
 474   loop->depth = -1;
 475   free (loop->pred);
 476   loop->pred = NULL;
 477 }
 478
 479 /* Helper function to compute loop nesting depth and enclosed loop level
 480    for the natural loop specified by LOOP.  Returns the loop level.  */
 481
 482 static int
 483 flow_loop_level_compute (struct loop *loop)
 484 {
 485   struct loop *inner;
 486   int level = 1;
 487
 488   if (! loop)
 489     return 0;
 490
 491   /* Traverse loop tree assigning depth and computing level as the
 492      maximum level of all the inner loops of this loop.  The loop
 493      level is equivalent to the height of the loop in the loop tree
 494      and corresponds to the number of enclosed loop levels (including
 495      itself).  */
 496   for (inner = loop->inner; inner; inner = inner->next)
 497     {
 498       int ilevel = flow_loop_level_compute (inner) + 1;
 499
 500       if (ilevel > level)
 501         level = ilevel;
 502     }
 503
 504   loop->level = level;
 505   return level;
 506 }
 507
 508 /* Compute the loop nesting depth and enclosed loop level for the loop
 509    hierarchy tree specified by LOOPS.  Return the maximum enclosed loop
 510    level.  */
 511
 512 static int
 513 flow_loops_level_compute (struct loops *loops)
 514 {
 515   return flow_loop_level_compute (loops->tree_root);
 516 }
 517
 518 /* Scan a single natural loop specified by LOOP collecting information
 519    about it specified by FLAGS.  */
 520
 521 int
 522 flow_loop_scan (struct loop *loop, int flags)
 523 {
 524   if (flags & LOOP_ENTRY_EDGES)
 525     {
 526       /* Find edges which enter the loop header.
 527          Note that the entry edges should only
 528          enter the header of a natural loop.  */
 529       flow_loop_entry_edges_find (loop);
 530     }
 531
 532   if (flags & LOOP_EXIT_EDGES)
 533     {
 534       /* Find edges which exit the loop.  */
 535       flow_loop_exit_edges_find (loop);
 536     }
 537
 538   if (flags & LOOP_PRE_HEADER)
 539     {
 540       /* Look to see if the loop has a pre-header node.  */
 541       loop->pre_header = flow_loop_pre_header_find (loop->header);
 542
 543       /* Find the blocks within the extended basic block of
 544          the loop pre-header.  */
 545       flow_loop_pre_header_scan (loop);
 546     }
 547
 548   return 1;
 549 }
 550
 551 /* A callback to update latch and header info for basic block JUMP created
 552    by redirecting an edge.  */
 553
 554 static void
 555 update_latch_info (basic_block jump)
 556 {
 557   alloc_aux_for_block (jump, sizeof (int));
 558   HEADER_BLOCK (jump) = 0;
 559   alloc_aux_for_edge (jump->pred, sizeof (int));
 560   LATCH_EDGE (jump->pred) = 0;
 561 }
 562
 563 /* A callback for make_forwarder block, to redirect all edges except for
 564    MFB_KJ_EDGE to the entry part.  E is the edge for that we should decide
 565    whether to redirect it.  */
 566
 567 static edge mfb_kj_edge;
 568 static bool
 569 mfb_keep_just (edge e)
 570 {
 571   return e != mfb_kj_edge;
 572 }
 573
 574 /* A callback for make_forwarder block, to redirect the latch edges into an
 575    entry part.  E is the edge for that we should decide whether to redirect
 576    it.  */
 577
 578 static bool
 579 mfb_keep_nonlatch (edge e)
 580 {
 581   return LATCH_EDGE (e);
 582 }
 583
 584 /* Takes care of merging natural loops with shared headers.  */
 585
 586 static void
 587 canonicalize_loop_headers (void)
 588 {
 589   basic_block header;
 590   edge e;
 591
 592   /* Compute the dominators.  */
 593   calculate_dominance_info (CDI_DOMINATORS);
 594
 595   alloc_aux_for_blocks (sizeof (int));
 596   alloc_aux_for_edges (sizeof (int));
 597
 598   /* Split blocks so that each loop has only single latch.  */
 599   FOR_EACH_BB (header)
 600     {
 601       int num_latches = 0;
 602       int have_abnormal_edge = 0;
 603
 604       for (e = header->pred; e; e = e->pred_next)
 605         {
 606           basic_block latch = e->src;
 607
 608           if (e->flags & EDGE_ABNORMAL)
 609             have_abnormal_edge = 1;
 610
 611           if (latch != ENTRY_BLOCK_PTR
 612               && dominated_by_p (CDI_DOMINATORS, latch, header))
 613             {
 614               num_latches++;
 615               LATCH_EDGE (e) = 1;
 616             }
 617         }
 618       if (have_abnormal_edge)
 619         HEADER_BLOCK (header) = 0;
 620       else
 621         HEADER_BLOCK (header) = num_latches;
 622     }
 623
 624   free_dominance_info (CDI_DOMINATORS);
 625
 626   if (HEADER_BLOCK (ENTRY_BLOCK_PTR->succ->dest))
 627     {
 628       basic_block bb;
 629
 630       /* We could not redirect edges freely here. On the other hand,
 631          we can simply split the edge from entry block.  */
 632       bb = split_edge (ENTRY_BLOCK_PTR->succ);
 633
 634       alloc_aux_for_edge (bb->succ, sizeof (int));
 635       LATCH_EDGE (bb->succ) = 0;
 636       alloc_aux_for_block (bb, sizeof (int));
 637       HEADER_BLOCK (bb) = 0;
 638     }
 639
 640   FOR_EACH_BB (header)
 641     {
 642       int max_freq, is_heavy;
 643       edge heavy, tmp_edge;
 644
 645       if (HEADER_BLOCK (header) <= 1)
 646         continue;
 647
 648       /* Find a heavy edge.  */
 649       is_heavy = 1;
 650       heavy = NULL;
 651       max_freq = 0;
 652       for (e = header->pred; e; e = e->pred_next)
 653         if (LATCH_EDGE (e) &&
 654             EDGE_FREQUENCY (e) > max_freq)
 655           max_freq = EDGE_FREQUENCY (e);
 656       for (e = header->pred; e; e = e->pred_next)
 657         if (LATCH_EDGE (e) &&
 658             EDGE_FREQUENCY (e) >= max_freq / HEAVY_EDGE_RATIO)
 659           {
 660             if (heavy)
 661               {
 662                 is_heavy = 0;
 663                 break;
 664               }
 665             else
 666               heavy = e;
 667           }
 668
 669       if (is_heavy)
 670         {
 671           /* Split out the heavy edge, and create inner loop for it.  */
 672           mfb_kj_edge = heavy;
 673           tmp_edge = make_forwarder_block (header, mfb_keep_just,
 674                                            update_latch_info);
 675           alloc_aux_for_block (tmp_edge->dest, sizeof (int));
 676           HEADER_BLOCK (tmp_edge->dest) = 1;
 677           alloc_aux_for_edge (tmp_edge, sizeof (int));
 678           LATCH_EDGE (tmp_edge) = 0;
 679           HEADER_BLOCK (header)--;
 680         }
 681
 682       if (HEADER_BLOCK (header) > 1)
 683         {
 684           /* Create a new latch block.  */
 685           tmp_edge = make_forwarder_block (header, mfb_keep_nonlatch,
 686                                            update_latch_info);
 687           alloc_aux_for_block (tmp_edge->dest, sizeof (int));
 688           HEADER_BLOCK (tmp_edge->src) = 0;
 689           HEADER_BLOCK (tmp_edge->dest) = 1;
 690           alloc_aux_for_edge (tmp_edge, sizeof (int));
 691           LATCH_EDGE (tmp_edge) = 1;
 692         }
 693     }
 694
 695   free_aux_for_blocks ();
 696   free_aux_for_edges ();
 697 }
 698
 699 /* Find all the natural loops in the function and save in LOOPS structure and
 700    recalculate loop_depth information in basic block structures.  FLAGS
 701    controls which loop information is collected.  Return the number of natural
 702    loops found.  */
 703
 704 int
 705 flow_loops_find (struct loops *loops, int flags)
 706 {
 707   int i;
 708   int b;
 709   int num_loops;
 710   edge e;
 711   sbitmap headers;
 712   int *dfs_order;
 713   int *rc_order;
 714   basic_block header;
 715   basic_block bb;
 716
 717   /* This function cannot be repeatedly called with different
 718      flags to build up the loop information.  The loop tree
 719      must always be built if this function is called.  */
 720   if (! (flags & LOOP_TREE))
 721     abort ();
 722
 723   memset (loops, 0, sizeof *loops);
 724
 725   /* Taking care of this degenerate case makes the rest of
 726      this code simpler.  */
 727   if (n_basic_blocks == 0)
 728     return 0;
 729
 730   dfs_order = NULL;
 731   rc_order = NULL;
 732
 733   /* Join loops with shared headers.  */
 734   canonicalize_loop_headers ();
 735
 736   /* Compute the dominators.  */
 737   calculate_dominance_info (CDI_DOMINATORS);
 738
 739   /* Count the number of loop headers.  This should be the
 740      same as the number of natural loops.  */
 741   headers = sbitmap_alloc (last_basic_block);
 742   sbitmap_zero (headers);
 743
 744   num_loops = 0;
 745   FOR_EACH_BB (header)
 746     {
 747       int more_latches = 0;
 748
 749       header->loop_depth = 0;
 750
 751       /* If we have an abnormal predecessor, do not consider the
 752          loop (not worth the problems).  */
 753       for (e = header->pred; e; e = e->pred_next)
 754         if (e->flags & EDGE_ABNORMAL)
 755           break;
 756       if (e)
 757         continue;
 758
 759       for (e = header->pred; e; e = e->pred_next)
 760         {
 761           basic_block latch = e->src;
 762
 763           if (e->flags & EDGE_ABNORMAL)
 764             abort ();
 765
 766           /* Look for back edges where a predecessor is dominated
 767              by this block.  A natural loop has a single entry
 768              node (header) that dominates all the nodes in the
 769              loop.  It also has single back edge to the header
 770              from a latch node.  */
 771           if (latch != ENTRY_BLOCK_PTR
 772               && dominated_by_p (CDI_DOMINATORS, latch, header))
 773             {
 774               /* Shared headers should be eliminated by now.  */
 775               if (more_latches)
 776                 abort ();
 777               more_latches = 1;
 778               SET_BIT (headers, header->index);
 779               num_loops++;
 780             }
 781         }
 782     }
 783
 784   /* Allocate loop structures.  */
 785   loops->parray = xcalloc (num_loops + 1, sizeof (struct loop *));
 786
 787   /* Dummy loop containing whole function.  */
 788   loops->parray[0] = xcalloc (1, sizeof (struct loop));
 789   loops->parray[0]->next = NULL;
 790   loops->parray[0]->inner = NULL;
 791   loops->parray[0]->outer = NULL;
 792   loops->parray[0]->depth = 0;
 793   loops->parray[0]->pred = NULL;
 794   loops->parray[0]->num_nodes = n_basic_blocks + 2;
 795   loops->parray[0]->latch = EXIT_BLOCK_PTR;
 796   loops->parray[0]->header = ENTRY_BLOCK_PTR;
 797   ENTRY_BLOCK_PTR->loop_father = loops->parray[0];
 798   EXIT_BLOCK_PTR->loop_father = loops->parray[0];
 799
 800   loops->tree_root = loops->parray[0];
 801
 802   /* Find and record information about all the natural loops
 803      in the CFG.  */
 804   loops->num = 1;
 805   FOR_EACH_BB (bb)
 806     bb->loop_father = loops->tree_root;
 807
 808   if (num_loops)
 809     {
 810       /* Compute depth first search order of the CFG so that outer
 811          natural loops will be found before inner natural loops.  */
 812       dfs_order = xmalloc (n_basic_blocks * sizeof (int));
 813       rc_order = xmalloc (n_basic_blocks * sizeof (int));
 814       flow_depth_first_order_compute (dfs_order, rc_order);
 815
 816       /* Save CFG derived information to avoid recomputing it.  */
 817       loops->cfg.dfs_order = dfs_order;
 818       loops->cfg.rc_order = rc_order;
 819
 820       num_loops = 1;
 821
 822       for (b = 0; b < n_basic_blocks; b++)
 823         {
 824           struct loop *loop;
 825
 826           /* Search the nodes of the CFG in reverse completion order
 827              so that we can find outer loops first.  */
 828           if (!TEST_BIT (headers, rc_order[b]))
 829             continue;
 830
 831           header = BASIC_BLOCK (rc_order[b]);
 832
 833           loop = loops->parray[num_loops] = xcalloc (1, sizeof (struct loop));
 834
 835           loop->header = header;
 836           loop->num = num_loops;
 837           num_loops++;
 838
 839           /* Look for the latch for this header block.  */
 840           for (e = header->pred; e; e = e->pred_next)
 841             {
 842               basic_block latch = e->src;
 843
 844               if (latch != ENTRY_BLOCK_PTR
 845                   && dominated_by_p (CDI_DOMINATORS, latch, header))
 846                 {
 847                   loop->latch = latch;
 848                   break;
 849                 }
 850             }
 851
 852           flow_loop_tree_node_add (header->loop_father, loop);
 853           loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
 854         }
 855
 856       /* Assign the loop nesting depth and enclosed loop level for each
 857          loop.  */
 858       loops->levels = flow_loops_level_compute (loops);
 859
 860       /* Scan the loops.  */
 861       for (i = 1; i < num_loops; i++)
 862         flow_loop_scan (loops->parray[i], flags);
 863
 864       loops->num = num_loops;
 865     }
 866   else
 867     {
 868       free_dominance_info (CDI_DOMINATORS);
 869     }
 870
 871   sbitmap_free (headers);
 872
 873   loops->state = 0;
 874 #ifdef ENABLE_CHECKING
 875   verify_flow_info ();
 876   verify_loop_structure (loops);
 877 #endif
 878
 879   return loops->num;
 880 }
 881
 882 /* Update the information regarding the loops in the CFG
 883    specified by LOOPS.  */
 884
 885 int
 886 flow_loops_update (struct loops *loops, int flags)
 887 {
 888   /* One day we may want to update the current loop data.  For now
 889      throw away the old stuff and rebuild what we need.  */
 890   if (loops->parray)
 891     flow_loops_free (loops);
 892
 893   return flow_loops_find (loops, flags);
 894 }
 895
 896 /* Return nonzero if basic block BB belongs to LOOP.  */
 897 bool
 898 flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb)
 899 {
 900   struct loop *source_loop;
 901
 902   if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
 903     return 0;
 904
 905   source_loop = bb->loop_father;
 906   return loop == source_loop || flow_loop_nested_p (loop, source_loop);
 907 }
 908
 909 /* Return nonzero if edge E enters header of LOOP from outside of LOOP.  */
 910
 911 bool
 912 flow_loop_outside_edge_p (const struct loop *loop, edge e)
 913 {
 914   if (e->dest != loop->header)
 915     abort ();
 916   return !flow_bb_inside_loop_p (loop, e->src);
 917 }
 918
 919 /* Enumeration predicate for get_loop_body.  */
 920 static bool
 921 glb_enum_p (basic_block bb, void *glb_header)
 922 {
 923   return bb != (basic_block) glb_header;
 924 }
 925
 926 /* Gets basic blocks of a LOOP.  Header is the 0-th block, rest is in dfs
 927    order against direction of edges from latch.  Specially, if
 928    header != latch, latch is the 1-st block.  */
 929 basic_block *
 930 get_loop_body (const struct loop *loop)
 931 {
 932   basic_block *tovisit, bb;
 933   unsigned tv = 0;
 934
 935   if (!loop->num_nodes)
 936     abort ();
 937
 938   tovisit = xcalloc (loop->num_nodes, sizeof (basic_block));
 939   tovisit[tv++] = loop->header;
 940
 941   if (loop->latch == EXIT_BLOCK_PTR)
 942     {
 943       /* There may be blocks unreachable from EXIT_BLOCK.  */
 944       if (loop->num_nodes != (unsigned) n_basic_blocks + 2)
 945         abort ();
 946       FOR_EACH_BB (bb)
 947         tovisit[tv++] = bb;
 948       tovisit[tv++] = EXIT_BLOCK_PTR;
 949     }
 950   else if (loop->latch != loop->header)
 951     {
 952       tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p,
 953                                tovisit + 1, loop->num_nodes - 1,
 954                                loop->header) + 1;
 955     }
 956
 957   if (tv != loop->num_nodes)
 958     abort ();
 959   return tovisit;
 960 }
 961
 962 /* Gets exit edges of a LOOP, returning their number in N_EDGES.  */
 963 edge *
 964 get_loop_exit_edges (const struct loop *loop, unsigned int *n_edges)
 965 {
 966   edge *edges, e;
 967   unsigned i, n;
 968   basic_block * body;
 969
 970   if (loop->latch == EXIT_BLOCK_PTR)
 971     abort ();
 972
 973   body = get_loop_body (loop);
 974   n = 0;
 975   for (i = 0; i < loop->num_nodes; i++)
 976     for (e = body[i]->succ; e; e = e->succ_next)
 977       if (!flow_bb_inside_loop_p (loop, e->dest))
 978         n++;
 979   edges = xmalloc (n * sizeof (edge));
 980   *n_edges = n;
 981   n = 0;
 982   for (i = 0; i < loop->num_nodes; i++)
 983     for (e = body[i]->succ; e; e = e->succ_next)
 984       if (!flow_bb_inside_loop_p (loop, e->dest))
 985         edges[n++] = e;
 986   free (body);
 987
 988   return edges;
 989 }
 990
 991 /* Adds basic block BB to LOOP.  */
 992 void
 993 add_bb_to_loop (basic_block bb, struct loop *loop)
 994 {
 995    int i;
 996
 997    bb->loop_father = loop;
 998    bb->loop_depth = loop->depth;
 999    loop->num_nodes++;
1000    for (i = 0; i < loop->depth; i++)
1001      loop->pred[i]->num_nodes++;
1002  }
1003
1004 /* Remove basic block BB from loops.  */
1005 void
1006 remove_bb_from_loops (basic_block bb)
1007 {
1008    int i;
1009    struct loop *loop = bb->loop_father;
1010
1011    loop->num_nodes--;
1012    for (i = 0; i < loop->depth; i++)
1013      loop->pred[i]->num_nodes--;
1014    bb->loop_father = NULL;
1015    bb->loop_depth = 0;
1016  }
1017
1018 /* Finds nearest common ancestor in loop tree for given loops.  */
1019 struct loop *
1020 find_common_loop (struct loop *loop_s, struct loop *loop_d)
1021 {
1022   if (!loop_s) return loop_d;
1023   if (!loop_d) return loop_s;
1024
1025   if (loop_s->depth < loop_d->depth)
1026     loop_d = loop_d->pred[loop_s->depth];
1027   else if (loop_s->depth > loop_d->depth)
1028     loop_s = loop_s->pred[loop_d->depth];
1029
1030   while (loop_s != loop_d)
1031     {
1032       loop_s = loop_s->outer;
1033       loop_d = loop_d->outer;
1034     }
1035   return loop_s;
1036 }
1037
1038 /* Cancels the LOOP; it must be innermost one.  */
1039 void
1040 cancel_loop (struct loops *loops, struct loop *loop)
1041 {
1042   basic_block *bbs;
1043   unsigned i;
1044
1045   if (loop->inner)
1046     abort ();
1047
1048   /* Move blocks up one level (they should be removed as soon as possible).  */
1049   bbs = get_loop_body (loop);
1050   for (i = 0; i < loop->num_nodes; i++)
1051     bbs[i]->loop_father = loop->outer;
1052
1053   /* Remove the loop from structure.  */
1054   flow_loop_tree_node_remove (loop);
1055
1056   /* Remove loop from loops array.  */
1057   loops->parray[loop->num] = NULL;
1058
1059   /* Free loop data.  */
1060   flow_loop_free (loop);
1061 }
1062
1063 /* Cancels LOOP and all its subloops.  */
1064 void
1065 cancel_loop_tree (struct loops *loops, struct loop *loop)
1066 {
1067   while (loop->inner)
1068     cancel_loop_tree (loops, loop->inner);
1069   cancel_loop (loops, loop);
1070 }
1071
1072 /* Checks that LOOPS are all right:
1073      -- sizes of loops are all right
1074      -- results of get_loop_body really belong to the loop
1075      -- loop header have just single entry edge and single latch edge
1076      -- loop latches have only single successor that is header of their loop
1077      -- irreducible loops are correctly marked
1078   */
1079 void
1080 verify_loop_structure (struct loops *loops)
1081 {
1082   unsigned *sizes, i, j;
1083   sbitmap irreds;
1084   basic_block *bbs, bb;
1085   struct loop *loop;
1086   int err = 0;
1087   edge e;
1088
1089   /* Check sizes.  */
1090   sizes = xcalloc (loops->num, sizeof (int));
1091   sizes[0] = 2;
1092
1093   FOR_EACH_BB (bb)
1094     for (loop = bb->loop_father; loop; loop = loop->outer)
1095       sizes[loop->num]++;
1096
1097   for (i = 0; i < loops->num; i++)
1098     {
1099       if (!loops->parray[i])
1100         continue;
1101
1102       if (loops->parray[i]->num_nodes != sizes[i])
1103         {
1104           error ("Size of loop %d should be %d, not %d.",
1105                    i, sizes[i], loops->parray[i]->num_nodes);
1106           err = 1;
1107         }
1108     }
1109
1110   free (sizes);
1111
1112   /* Check get_loop_body.  */
1113   for (i = 1; i < loops->num; i++)
1114     {
1115       loop = loops->parray[i];
1116       if (!loop)
1117         continue;
1118       bbs = get_loop_body (loop);
1119
1120       for (j = 0; j < loop->num_nodes; j++)
1121         if (!flow_bb_inside_loop_p (loop, bbs[j]))
1122           {
1123             error ("Bb %d do not belong to loop %d.",
1124                     bbs[j]->index, i);
1125             err = 1;
1126           }
1127       free (bbs);
1128     }
1129
1130   /* Check headers and latches.  */
1131   for (i = 1; i < loops->num; i++)
1132     {
1133       loop = loops->parray[i];
1134       if (!loop)
1135         continue;
1136
1137       if ((loops->state & LOOPS_HAVE_PREHEADERS)
1138           && (!loop->header->pred->pred_next
1139               || loop->header->pred->pred_next->pred_next))
1140         {
1141           error ("Loop %d's header does not have exactly 2 entries.", i);
1142           err = 1;
1143         }
1144       if (loops->state & LOOPS_HAVE_SIMPLE_LATCHES)
1145         {
1146           if (!loop->latch->succ
1147               || loop->latch->succ->succ_next)
1148             {
1149               error ("Loop %d's latch does not have exactly 1 successor.", i);
1150               err = 1;
1151             }
1152           if (loop->latch->succ->dest != loop->header)
1153             {
1154               error ("Loop %d's latch does not have header as successor.", i);
1155               err = 1;
1156             }
1157           if (loop->latch->loop_father != loop)
1158             {
1159               error ("Loop %d's latch does not belong directly to it.", i);
1160               err = 1;
1161             }
1162         }
1163       if (loop->header->loop_father != loop)
1164         {
1165           error ("Loop %d's header does not belong directly to it.", i);
1166           err = 1;
1167         }
1168       if ((loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1169           && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
1170         {
1171           error ("Loop %d's latch is marked as part of irreducible region.", i);
1172           err = 1;
1173         }
1174     }
1175
1176   /* Check irreducible loops.  */
1177   if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1178     {
1179       /* Record old info.  */
1180       irreds = sbitmap_alloc (last_basic_block);
1181       FOR_EACH_BB (bb)
1182         {
1183           if (bb->flags & BB_IRREDUCIBLE_LOOP)
1184             SET_BIT (irreds, bb->index);
1185           else
1186             RESET_BIT (irreds, bb->index);
1187           for (e = bb->succ; e; e = e->succ_next)
1188             if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1189               e->flags |= EDGE_ALL_FLAGS + 1;
1190         }
1191
1192       /* Recount it.  */
1193       mark_irreducible_loops (loops);
1194
1195       /* Compare.  */
1196       FOR_EACH_BB (bb)
1197         {
1198           if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1199               && !TEST_BIT (irreds, bb->index))
1200             {
1201               error ("Basic block %d should be marked irreducible.", bb->index);
1202               err = 1;
1203             }
1204           else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1205               && TEST_BIT (irreds, bb->index))
1206             {
1207               error ("Basic block %d should not be marked irreducible.", bb->index);
1208               err = 1;
1209             }
1210           for (e = bb->succ; e; e = e->succ_next)
1211             {
1212               if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1213                   && !(e->flags & (EDGE_ALL_FLAGS + 1)))
1214                 {
1215                   error ("Edge from %d to %d should be marked irreducible.",
1216                          e->src->index, e->dest->index);
1217                   err = 1;
1218                 }
1219               else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1220                        && (e->flags & (EDGE_ALL_FLAGS + 1)))
1221                 {
1222                   error ("Edge from %d to %d should not be marked irreducible.",
1223                          e->src->index, e->dest->index);
1224                   err = 1;
1225                 }
1226               e->flags &= ~(EDGE_ALL_FLAGS + 1);
1227             }
1228         }
1229       free (irreds);
1230     }
1231
1232   if (err)
1233     abort ();
1234 }
1235
1236 /* Returns latch edge of LOOP.  */
1237 edge
1238 loop_latch_edge (const struct loop *loop)
1239 {
1240   edge e;
1241
1242   for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next)
1243     continue;
1244
1245   return e;
1246 }
1247
1248 /* Returns preheader edge of LOOP.  */
1249 edge
1250 loop_preheader_edge (const struct loop *loop)
1251 {
1252   edge e;
1253
1254   for (e = loop->header->pred; e->src == loop->latch; e = e->pred_next)
1255     continue;
1256
1257   return e;
1258 }