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