gcc/cfgloop.c

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