gcc/cfgloop.c

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