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