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 /* Fills dominance descendants inside LOOP of the basic block BB into
 963    array TOVISIT from index *TV.  */
 964
 965 static void
 966 fill_sons_in_loop (const struct loop *loop, basic_block bb,
 967                    basic_block *tovisit, int *tv)
 968 {
 969   basic_block son, postpone = NULL;
 970
 971   tovisit[(*tv)++] = bb;
 972   for (son = first_dom_son (CDI_DOMINATORS, bb);
 973        son;
 974        son = next_dom_son (CDI_DOMINATORS, son))
 975     {
 976       if (!flow_bb_inside_loop_p (loop, son))
 977         continue;
 978
 979       if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
 980         {
 981           postpone = son;
 982           continue;
 983         }
 984       fill_sons_in_loop (loop, son, tovisit, tv);
 985     }
 986
 987   if (postpone)
 988     fill_sons_in_loop (loop, postpone, tovisit, tv);
 989 }
 990
 991 /* Gets body of a LOOP (that must be different from the outermost loop)
 992    sorted by dominance relation.  Additionally, if a basic block s dominates
 993    the latch, then only blocks dominated by s are be after it.  */
 994
 995 basic_block *
 996 get_loop_body_in_dom_order (const struct loop *loop)
 997 {
 998   basic_block *tovisit;
 999   int tv;
1000
1001   if (!loop->num_nodes)
1002     abort ();
1003
1004   tovisit = xcalloc (loop->num_nodes, sizeof (basic_block));
1005
1006   if (loop->latch == EXIT_BLOCK_PTR)
1007     abort ();
1008
1009   tv = 0;
1010   fill_sons_in_loop (loop, loop->header, tovisit, &tv);
1011
1012   if (tv != (int) loop->num_nodes)
1013     abort ();
1014
1015   return tovisit;
1016 }
1017
1018 /* Gets exit edges of a LOOP, returning their number in N_EDGES.  */
1019 edge *
1020 get_loop_exit_edges (const struct loop *loop, unsigned int *n_edges)
1021 {
1022   edge *edges, e;
1023   unsigned i, n;
1024   basic_block * body;
1025
1026   if (loop->latch == EXIT_BLOCK_PTR)
1027     abort ();
1028
1029   body = get_loop_body (loop);
1030   n = 0;
1031   for (i = 0; i < loop->num_nodes; i++)
1032     for (e = body[i]->succ; e; e = e->succ_next)
1033       if (!flow_bb_inside_loop_p (loop, e->dest))
1034         n++;
1035   edges = xmalloc (n * sizeof (edge));
1036   *n_edges = n;
1037   n = 0;
1038   for (i = 0; i < loop->num_nodes; i++)
1039     for (e = body[i]->succ; e; e = e->succ_next)
1040       if (!flow_bb_inside_loop_p (loop, e->dest))
1041         edges[n++] = e;
1042   free (body);
1043
1044   return edges;
1045 }
1046
1047 /* Counts the number of conditional branches inside LOOP.  */
1048
1049 unsigned
1050 num_loop_branches (const struct loop *loop)
1051 {
1052   unsigned i, n;
1053   basic_block * body;
1054
1055   if (loop->latch == EXIT_BLOCK_PTR)
1056     abort ();
1057
1058   body = get_loop_body (loop);
1059   n = 0;
1060   for (i = 0; i < loop->num_nodes; i++)
1061     if (body[i]->succ && body[i]->succ->succ_next)
1062       n++;
1063   free (body);
1064
1065   return n;
1066 }
1067
1068 /* Adds basic block BB to LOOP.  */
1069 void
1070 add_bb_to_loop (basic_block bb, struct loop *loop)
1071 {
1072    int i;
1073
1074    bb->loop_father = loop;
1075    bb->loop_depth = loop->depth;
1076    loop->num_nodes++;
1077    for (i = 0; i < loop->depth; i++)
1078      loop->pred[i]->num_nodes++;
1079  }
1080
1081 /* Remove basic block BB from loops.  */
1082 void
1083 remove_bb_from_loops (basic_block bb)
1084 {
1085    int i;
1086    struct loop *loop = bb->loop_father;
1087
1088    loop->num_nodes--;
1089    for (i = 0; i < loop->depth; i++)
1090      loop->pred[i]->num_nodes--;
1091    bb->loop_father = NULL;
1092    bb->loop_depth = 0;
1093  }
1094
1095 /* Finds nearest common ancestor in loop tree for given loops.  */
1096 struct loop *
1097 find_common_loop (struct loop *loop_s, struct loop *loop_d)
1098 {
1099   if (!loop_s) return loop_d;
1100   if (!loop_d) return loop_s;
1101
1102   if (loop_s->depth < loop_d->depth)
1103     loop_d = loop_d->pred[loop_s->depth];
1104   else if (loop_s->depth > loop_d->depth)
1105     loop_s = loop_s->pred[loop_d->depth];
1106
1107   while (loop_s != loop_d)
1108     {
1109       loop_s = loop_s->outer;
1110       loop_d = loop_d->outer;
1111     }
1112   return loop_s;
1113 }
1114
1115 /* Cancels the LOOP; it must be innermost one.  */
1116 void
1117 cancel_loop (struct loops *loops, struct loop *loop)
1118 {
1119   basic_block *bbs;
1120   unsigned i;
1121
1122   if (loop->inner)
1123     abort ();
1124
1125   /* Move blocks up one level (they should be removed as soon as possible).  */
1126   bbs = get_loop_body (loop);
1127   for (i = 0; i < loop->num_nodes; i++)
1128     bbs[i]->loop_father = loop->outer;
1129
1130   /* Remove the loop from structure.  */
1131   flow_loop_tree_node_remove (loop);
1132
1133   /* Remove loop from loops array.  */
1134   loops->parray[loop->num] = NULL;
1135
1136   /* Free loop data.  */
1137   flow_loop_free (loop);
1138 }
1139
1140 /* Cancels LOOP and all its subloops.  */
1141 void
1142 cancel_loop_tree (struct loops *loops, struct loop *loop)
1143 {
1144   while (loop->inner)
1145     cancel_loop_tree (loops, loop->inner);
1146   cancel_loop (loops, loop);
1147 }
1148
1149 /* Checks that LOOPS are all right:
1150      -- sizes of loops are all right
1151      -- results of get_loop_body really belong to the loop
1152      -- loop header have just single entry edge and single latch edge
1153      -- loop latches have only single successor that is header of their loop
1154      -- irreducible loops are correctly marked
1155   */
1156 void
1157 verify_loop_structure (struct loops *loops)
1158 {
1159   unsigned *sizes, i, j;
1160   sbitmap irreds;
1161   basic_block *bbs, bb;
1162   struct loop *loop;
1163   int err = 0;
1164   edge e;
1165
1166   /* Check sizes.  */
1167   sizes = xcalloc (loops->num, sizeof (int));
1168   sizes[0] = 2;
1169
1170   FOR_EACH_BB (bb)
1171     for (loop = bb->loop_father; loop; loop = loop->outer)
1172       sizes[loop->num]++;
1173
1174   for (i = 0; i < loops->num; i++)
1175     {
1176       if (!loops->parray[i])
1177         continue;
1178
1179       if (loops->parray[i]->num_nodes != sizes[i])
1180         {
1181           error ("Size of loop %d should be %d, not %d.",
1182                    i, sizes[i], loops->parray[i]->num_nodes);
1183           err = 1;
1184         }
1185     }
1186
1187   free (sizes);
1188
1189   /* Check get_loop_body.  */
1190   for (i = 1; i < loops->num; i++)
1191     {
1192       loop = loops->parray[i];
1193       if (!loop)
1194         continue;
1195       bbs = get_loop_body (loop);
1196
1197       for (j = 0; j < loop->num_nodes; j++)
1198         if (!flow_bb_inside_loop_p (loop, bbs[j]))
1199           {
1200             error ("Bb %d do not belong to loop %d.",
1201                     bbs[j]->index, i);
1202             err = 1;
1203           }
1204       free (bbs);
1205     }
1206
1207   /* Check headers and latches.  */
1208   for (i = 1; i < loops->num; i++)
1209     {
1210       loop = loops->parray[i];
1211       if (!loop)
1212         continue;
1213
1214       if ((loops->state & LOOPS_HAVE_PREHEADERS)
1215           && (!loop->header->pred->pred_next
1216               || loop->header->pred->pred_next->pred_next))
1217         {
1218           error ("Loop %d's header does not have exactly 2 entries.", i);
1219           err = 1;
1220         }
1221       if (loops->state & LOOPS_HAVE_SIMPLE_LATCHES)
1222         {
1223           if (!loop->latch->succ
1224               || loop->latch->succ->succ_next)
1225             {
1226               error ("Loop %d's latch does not have exactly 1 successor.", i);
1227               err = 1;
1228             }
1229           if (loop->latch->succ->dest != loop->header)
1230             {
1231               error ("Loop %d's latch does not have header as successor.", i);
1232               err = 1;
1233             }
1234           if (loop->latch->loop_father != loop)
1235             {
1236               error ("Loop %d's latch does not belong directly to it.", i);
1237               err = 1;
1238             }
1239         }
1240       if (loop->header->loop_father != loop)
1241         {
1242           error ("Loop %d's header does not belong directly to it.", i);
1243           err = 1;
1244         }
1245       if ((loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1246           && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
1247         {
1248           error ("Loop %d's latch is marked as part of irreducible region.", i);
1249           err = 1;
1250         }
1251     }
1252
1253   /* Check irreducible loops.  */
1254   if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1255     {
1256       /* Record old info.  */
1257       irreds = sbitmap_alloc (last_basic_block);
1258       FOR_EACH_BB (bb)
1259         {
1260           if (bb->flags & BB_IRREDUCIBLE_LOOP)
1261             SET_BIT (irreds, bb->index);
1262           else
1263             RESET_BIT (irreds, bb->index);
1264           for (e = bb->succ; e; e = e->succ_next)
1265             if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1266               e->flags |= EDGE_ALL_FLAGS + 1;
1267         }
1268
1269       /* Recount it.  */
1270       mark_irreducible_loops (loops);
1271
1272       /* Compare.  */
1273       FOR_EACH_BB (bb)
1274         {
1275           if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1276               && !TEST_BIT (irreds, bb->index))
1277             {
1278               error ("Basic block %d should be marked irreducible.", bb->index);
1279               err = 1;
1280             }
1281           else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1282               && TEST_BIT (irreds, bb->index))
1283             {
1284               error ("Basic block %d should not be marked irreducible.", bb->index);
1285               err = 1;
1286             }
1287           for (e = bb->succ; e; e = e->succ_next)
1288             {
1289               if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1290                   && !(e->flags & (EDGE_ALL_FLAGS + 1)))
1291                 {
1292                   error ("Edge from %d to %d should be marked irreducible.",
1293                          e->src->index, e->dest->index);
1294                   err = 1;
1295                 }
1296               else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1297                        && (e->flags & (EDGE_ALL_FLAGS + 1)))
1298                 {
1299                   error ("Edge from %d to %d should not be marked irreducible.",
1300                          e->src->index, e->dest->index);
1301                   err = 1;
1302                 }
1303               e->flags &= ~(EDGE_ALL_FLAGS + 1);
1304             }
1305         }
1306       free (irreds);
1307     }
1308
1309   if (err)
1310     abort ();
1311 }
1312
1313 /* Returns latch edge of LOOP.  */
1314 edge
1315 loop_latch_edge (const struct loop *loop)
1316 {
1317   edge e;
1318
1319   for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next)
1320     continue;
1321
1322   return e;
1323 }
1324
1325 /* Returns preheader edge of LOOP.  */
1326 edge
1327 loop_preheader_edge (const struct loop *loop)
1328 {
1329   edge e;
1330
1331   for (e = loop->header->pred; e->src == loop->latch; e = e->pred_next)
1332     continue;
1333
1334   return e;
1335 }