gcc/cfgloop.c

   1 /* Natural loop discovery code for GNU compiler.
   2    Copyright (C) 2000, 2001, 2003, 2004 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to the Free
  18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "rtl.h"
  26 #include "hard-reg-set.h"
  27 #include "basic-block.h"
  28 #include "toplev.h"
  29 #include "cfgloop.h"
  30 #include "flags.h"
  31 #include "tree.h"
  32 #include "tree-flow.h"
  33
  34 /* Ratio of frequencies of edges so that one of more latch edges is
  35    considered to belong to inner loop with same header.  */
  36 #define HEAVY_EDGE_RATIO 8
  37
  38 #define HEADER_BLOCK(B) (* (int *) (B)->aux)
  39 #define LATCH_EDGE(E) (*(int *) (E)->aux)
  40
  41 static void flow_loops_cfg_dump (const struct loops *, FILE *);
  42 static void flow_loop_entry_edges_find (struct loop *);
  43 static void flow_loop_exit_edges_find (struct loop *);
  44 static int flow_loop_nodes_find (basic_block, struct loop *);
  45 static void flow_loop_pre_header_scan (struct loop *);
  46 static basic_block flow_loop_pre_header_find (basic_block);
  47 static int flow_loop_level_compute (struct loop *);
  48 static int flow_loops_level_compute (struct loops *);
  49 static void establish_preds (struct loop *);
  50 static void canonicalize_loop_headers (void);
  51 static bool glb_enum_p (basic_block, void *);
  52 \f
  53 /* Dump loop related CFG information.  */
  54
  55 static void
  56 flow_loops_cfg_dump (const struct loops *loops, FILE *file)
  57 {
  58   int i;
  59   basic_block bb;
  60
  61   if (! loops->num || ! file)
  62     return;
  63
  64   FOR_EACH_BB (bb)
  65     {
  66       edge succ;
  67
  68       fprintf (file, ";; %d succs { ", bb->index);
  69       for (succ = bb->succ; succ; succ = succ->succ_next)
  70         fprintf (file, "%d ", succ->dest->index);
  71       fprintf (file, "}\n");
  72     }
  73
  74   /* Dump the DFS node order.  */
  75   if (loops->cfg.dfs_order)
  76     {
  77       fputs (";; DFS order: ", file);
  78       for (i = 0; i < n_basic_blocks; i++)
  79         fprintf (file, "%d ", loops->cfg.dfs_order[i]);
  80
  81       fputs ("\n", file);
  82     }
  83
  84   /* Dump the reverse completion node order.  */
  85   if (loops->cfg.rc_order)
  86     {
  87       fputs (";; RC order: ", file);
  88       for (i = 0; i < n_basic_blocks; i++)
  89         fprintf (file, "%d ", loops->cfg.rc_order[i]);
  90
  91       fputs ("\n", file);
  92     }
  93 }
  94
  95 /* Return nonzero if the nodes of LOOP are a subset of OUTER.  */
  96
  97 bool
  98 flow_loop_nested_p (const struct loop *outer, const struct loop *loop)
  99 {
 100   return loop->depth > outer->depth
 101          && loop->pred[outer->depth] == outer;
 102 }
 103
 104 /* Dump the loop information specified by LOOP to the stream FILE
 105    using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
 106
 107 void
 108 flow_loop_dump (const struct loop *loop, FILE *file,
 109                 void (*loop_dump_aux) (const struct loop *, FILE *, int),
 110                 int verbose)
 111 {
 112   basic_block *bbs;
 113   unsigned i;
 114
 115   if (! loop || ! loop->header)
 116     return;
 117
 118   fprintf (file, ";;\n;; Loop %d:%s\n", loop->num,
 119              loop->invalid ? " invalid" : "");
 120
 121   fprintf (file, ";;  header %d, latch %d, pre-header %d\n",
 122            loop->header->index, loop->latch->index,
 123            loop->pre_header ? loop->pre_header->index : -1);
 124   fprintf (file, ";;  depth %d, level %d, outer %ld\n",
 125            loop->depth, loop->level,
 126            (long) (loop->outer ? loop->outer->num : -1));
 127
 128   if (loop->pre_header_edges)
 129     flow_edge_list_print (";;  pre-header edges", loop->pre_header_edges,
 130                           loop->num_pre_header_edges, file);
 131
 132   flow_edge_list_print (";;  entry edges", loop->entry_edges,
 133                         loop->num_entries, file);
 134   fprintf (file, ";;  nodes:");
 135   bbs = get_loop_body (loop);
 136   for (i = 0; i < loop->num_nodes; i++)
 137     fprintf (file, " %d", bbs[i]->index);
 138   free (bbs);
 139   fprintf (file, "\n");
 140   flow_edge_list_print (";;  exit edges", loop->exit_edges,
 141                         loop->num_exits, file);
 142
 143   if (loop_dump_aux)
 144     loop_dump_aux (loop, file, verbose);
 145 }
 146
 147 /* Dump the loop information specified by LOOPS to the stream FILE,
 148    using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
 149
 150 void
 151 flow_loops_dump (const struct loops *loops, FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
 152 {
 153   int i;
 154   int num_loops;
 155
 156   num_loops = loops->num;
 157   if (! num_loops || ! file)
 158     return;
 159
 160   fprintf (file, ";; %d loops found, %d levels\n",
 161            num_loops, loops->levels);
 162
 163   for (i = 0; i < num_loops; i++)
 164     {
 165       struct loop *loop = loops->parray[i];
 166
 167       if (!loop)
 168         continue;
 169
 170       flow_loop_dump (loop, file, loop_dump_aux, verbose);
 171     }
 172
 173   if (verbose)
 174     flow_loops_cfg_dump (loops, file);
 175 }
 176
 177 /* Free data allocated for LOOP.  */
 178 void
 179 flow_loop_free (struct loop *loop)
 180 {
 181   if (loop->pre_header_edges)
 182     free (loop->pre_header_edges);
 183   if (loop->entry_edges)
 184     free (loop->entry_edges);
 185   if (loop->exit_edges)
 186     free (loop->exit_edges);
 187   if (loop->pred)
 188     free (loop->pred);
 189   free (loop);
 190 }
 191
 192 /* Free all the memory allocated for LOOPS.  */
 193
 194 void
 195 flow_loops_free (struct loops *loops)
 196 {
 197   if (loops->parray)
 198     {
 199       unsigned i;
 200
 201       if (! loops->num)
 202         abort ();
 203
 204       /* Free the loop descriptors.  */
 205       for (i = 0; i < loops->num; i++)
 206         {
 207           struct loop *loop = loops->parray[i];
 208
 209           if (!loop)
 210             continue;
 211
 212           flow_loop_free (loop);
 213         }
 214
 215       free (loops->parray);
 216       loops->parray = NULL;
 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.  Return NULL if there is no pre-header.  */
 395
 396 static basic_block
 397 flow_loop_pre_header_find (basic_block header)
 398 {
 399   basic_block pre_header;
 400   edge e;
 401
 402   /* If block p is a predecessor of the header and is the only block
 403      that the header does not dominate, then it is the pre-header.  */
 404   pre_header = NULL;
 405   for (e = header->pred; e; e = e->pred_next)
 406     {
 407       basic_block node = e->src;
 408
 409       if (node != ENTRY_BLOCK_PTR
 410           && ! dominated_by_p (CDI_DOMINATORS, node, header))
 411         {
 412           if (pre_header == NULL)
 413             pre_header = node;
 414           else
 415             {
 416               /* There are multiple edges into the header from outside
 417                  the loop so there is no pre-header block.  */
 418               pre_header = NULL;
 419               break;
 420             }
 421         }
 422     }
 423
 424   return pre_header;
 425 }
 426
 427 static void
 428 establish_preds (struct loop *loop)
 429 {
 430   struct loop *ploop, *father = loop->outer;
 431
 432   loop->depth = father->depth + 1;
 433   if (loop->pred)
 434     free (loop->pred);
 435   loop->pred = xmalloc (sizeof (struct loop *) * loop->depth);
 436   memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth);
 437   loop->pred[father->depth] = father;
 438
 439   for (ploop = loop->inner; ploop; ploop = ploop->next)
 440     establish_preds (ploop);
 441 }
 442
 443 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
 444    added loop.  If LOOP has some children, take care of that their
 445    pred field will be initialized correctly.  */
 446
 447 void
 448 flow_loop_tree_node_add (struct loop *father, struct loop *loop)
 449 {
 450   loop->next = father->inner;
 451   father->inner = loop;
 452   loop->outer = father;
 453
 454   establish_preds (loop);
 455 }
 456
 457 /* Remove LOOP from the loop hierarchy tree.  */
 458
 459 void
 460 flow_loop_tree_node_remove (struct loop *loop)
 461 {
 462   struct loop *prev, *father;
 463
 464   father = loop->outer;
 465   loop->outer = NULL;
 466
 467   /* Remove loop from the list of sons.  */
 468   if (father->inner == loop)
 469     father->inner = loop->next;
 470   else
 471     {
 472       for (prev = father->inner; prev->next != loop; prev = prev->next);
 473       prev->next = loop->next;
 474     }
 475
 476   loop->depth = -1;
 477   free (loop->pred);
 478   loop->pred = NULL;
 479 }
 480
 481 /* Helper function to compute loop nesting depth and enclosed loop level
 482    for the natural loop specified by LOOP.  Returns the loop level.  */
 483
 484 static int
 485 flow_loop_level_compute (struct loop *loop)
 486 {
 487   struct loop *inner;
 488   int level = 1;
 489
 490   if (! loop)
 491     return 0;
 492
 493   /* Traverse loop tree assigning depth and computing level as the
 494      maximum level of all the inner loops of this loop.  The loop
 495      level is equivalent to the height of the loop in the loop tree
 496      and corresponds to the number of enclosed loop levels (including
 497      itself).  */
 498   for (inner = loop->inner; inner; inner = inner->next)
 499     {
 500       int ilevel = flow_loop_level_compute (inner) + 1;
 501
 502       if (ilevel > level)
 503         level = ilevel;
 504     }
 505
 506   loop->level = level;
 507   return level;
 508 }
 509
 510 /* Compute the loop nesting depth and enclosed loop level for the loop
 511    hierarchy tree specified by LOOPS.  Return the maximum enclosed loop
 512    level.  */
 513
 514 static int
 515 flow_loops_level_compute (struct loops *loops)
 516 {
 517   return flow_loop_level_compute (loops->tree_root);
 518 }
 519
 520 /* Scan a single natural loop specified by LOOP collecting information
 521    about it specified by FLAGS.  */
 522
 523 int
 524 flow_loop_scan (struct loop *loop, int flags)
 525 {
 526   if (flags & LOOP_ENTRY_EDGES)
 527     {
 528       /* Find edges which enter the loop header.
 529          Note that the entry edges should only
 530          enter the header of a natural loop.  */
 531       flow_loop_entry_edges_find (loop);
 532     }
 533
 534   if (flags & LOOP_EXIT_EDGES)
 535     {
 536       /* Find edges which exit the loop.  */
 537       flow_loop_exit_edges_find (loop);
 538     }
 539
 540   if (flags & LOOP_PRE_HEADER)
 541     {
 542       /* Look to see if the loop has a pre-header node.  */
 543       loop->pre_header = flow_loop_pre_header_find (loop->header);
 544
 545       /* Find the blocks within the extended basic block of
 546          the loop pre-header.  */
 547       flow_loop_pre_header_scan (loop);
 548     }
 549
 550   return 1;
 551 }
 552
 553 /* A callback to update latch and header info for basic block JUMP created
 554    by redirecting an edge.  */
 555
 556 static void
 557 update_latch_info (basic_block jump)
 558 {
 559   alloc_aux_for_block (jump, sizeof (int));
 560   HEADER_BLOCK (jump) = 0;
 561   alloc_aux_for_edge (jump->pred, sizeof (int));
 562   LATCH_EDGE (jump->pred) = 0;
 563 }
 564
 565 /* A callback for make_forwarder block, to redirect all edges except for
 566    MFB_KJ_EDGE to the entry part.  E is the edge for that we should decide
 567    whether to redirect it.  */
 568
 569 static edge mfb_kj_edge;
 570 static bool
 571 mfb_keep_just (edge e)
 572 {
 573   return e != mfb_kj_edge;
 574 }
 575
 576 /* A callback for make_forwarder block, to redirect the latch edges into an
 577    entry part.  E is the edge for that we should decide whether to redirect
 578    it.  */
 579
 580 static bool
 581 mfb_keep_nonlatch (edge e)
 582 {
 583   return LATCH_EDGE (e);
 584 }
 585
 586 /* Takes care of merging natural loops with shared headers.  */
 587
 588 static void
 589 canonicalize_loop_headers (void)
 590 {
 591   basic_block header;
 592   edge e;
 593
 594   /* Compute the dominators.  */
 595   calculate_dominance_info (CDI_DOMINATORS);
 596
 597   alloc_aux_for_blocks (sizeof (int));
 598   alloc_aux_for_edges (sizeof (int));
 599
 600   /* Split blocks so that each loop has only single latch.  */
 601   FOR_EACH_BB (header)
 602     {
 603       int num_latches = 0;
 604       int have_abnormal_edge = 0;
 605
 606       for (e = header->pred; e; e = e->pred_next)
 607         {
 608           basic_block latch = e->src;
 609
 610           if (e->flags & EDGE_ABNORMAL)
 611             have_abnormal_edge = 1;
 612
 613           if (latch != ENTRY_BLOCK_PTR
 614               && dominated_by_p (CDI_DOMINATORS, latch, header))
 615             {
 616               num_latches++;
 617               LATCH_EDGE (e) = 1;
 618             }
 619         }
 620       if (have_abnormal_edge)
 621         HEADER_BLOCK (header) = 0;
 622       else
 623         HEADER_BLOCK (header) = num_latches;
 624     }
 625
 626   free_dominance_info (CDI_DOMINATORS);
 627
 628   if (HEADER_BLOCK (ENTRY_BLOCK_PTR->succ->dest))
 629     {
 630       basic_block bb;
 631
 632       /* We could not redirect edges freely here. On the other hand,
 633          we can simply split the edge from entry block.  */
 634       bb = split_edge (ENTRY_BLOCK_PTR->succ);
 635
 636       alloc_aux_for_edge (bb->succ, sizeof (int));
 637       LATCH_EDGE (bb->succ) = 0;
 638       alloc_aux_for_block (bb, sizeof (int));
 639       HEADER_BLOCK (bb) = 0;
 640     }
 641
 642   FOR_EACH_BB (header)
 643     {
 644       int max_freq, is_heavy;
 645       edge heavy, tmp_edge;
 646
 647       if (HEADER_BLOCK (header) <= 1)
 648         continue;
 649
 650       /* Find a heavy edge.  */
 651       is_heavy = 1;
 652       heavy = NULL;
 653       max_freq = 0;
 654       for (e = header->pred; e; e = e->pred_next)
 655         if (LATCH_EDGE (e) &&
 656             EDGE_FREQUENCY (e) > max_freq)
 657           max_freq = EDGE_FREQUENCY (e);
 658       for (e = header->pred; e; e = e->pred_next)
 659         if (LATCH_EDGE (e) &&
 660             EDGE_FREQUENCY (e) >= max_freq / HEAVY_EDGE_RATIO)
 661           {
 662             if (heavy)
 663               {
 664                 is_heavy = 0;
 665                 break;
 666               }
 667             else
 668               heavy = e;
 669           }
 670
 671       if (is_heavy)
 672         {
 673           /* Split out the heavy edge, and create inner loop for it.  */
 674           mfb_kj_edge = heavy;
 675           tmp_edge = make_forwarder_block (header, mfb_keep_just,
 676                                            update_latch_info);
 677           alloc_aux_for_block (tmp_edge->dest, sizeof (int));
 678           HEADER_BLOCK (tmp_edge->dest) = 1;
 679           alloc_aux_for_edge (tmp_edge, sizeof (int));
 680           LATCH_EDGE (tmp_edge) = 0;
 681           HEADER_BLOCK (header)--;
 682         }
 683
 684       if (HEADER_BLOCK (header) > 1)
 685         {
 686           /* Create a new latch block.  */
 687           tmp_edge = make_forwarder_block (header, mfb_keep_nonlatch,
 688                                            update_latch_info);
 689           alloc_aux_for_block (tmp_edge->dest, sizeof (int));
 690           HEADER_BLOCK (tmp_edge->src) = 0;
 691           HEADER_BLOCK (tmp_edge->dest) = 1;
 692           alloc_aux_for_edge (tmp_edge, sizeof (int));
 693           LATCH_EDGE (tmp_edge) = 1;
 694         }
 695     }
 696
 697   free_aux_for_blocks ();
 698   free_aux_for_edges ();
 699 }
 700
 701 /* Find all the natural loops in the function and save in LOOPS structure and
 702    recalculate loop_depth information in basic block structures.  FLAGS
 703    controls which loop information is collected.  Return the number of natural
 704    loops found.  */
 705
 706 int
 707 flow_loops_find (struct loops *loops, int flags)
 708 {
 709   int i;
 710   int b;
 711   int num_loops;
 712   edge e;
 713   sbitmap headers;
 714   int *dfs_order;
 715   int *rc_order;
 716   basic_block header;
 717   basic_block bb;
 718
 719   /* This function cannot be repeatedly called with different
 720      flags to build up the loop information.  The loop tree
 721      must always be built if this function is called.  */
 722   if (! (flags & LOOP_TREE))
 723     abort ();
 724
 725   memset (loops, 0, sizeof *loops);
 726
 727   /* Taking care of this degenerate case makes the rest of
 728      this code simpler.  */
 729   if (n_basic_blocks == 0)
 730     return 0;
 731
 732   dfs_order = NULL;
 733   rc_order = NULL;
 734
 735   /* Join loops with shared headers.  */
 736   canonicalize_loop_headers ();
 737
 738   /* Compute the dominators.  */
 739   calculate_dominance_info (CDI_DOMINATORS);
 740
 741   /* Count the number of loop headers.  This should be the
 742      same as the number of natural loops.  */
 743   headers = sbitmap_alloc (last_basic_block);
 744   sbitmap_zero (headers);
 745
 746   num_loops = 0;
 747   FOR_EACH_BB (header)
 748     {
 749       int more_latches = 0;
 750
 751       header->loop_depth = 0;
 752
 753       /* If we have an abnormal predecessor, do not consider the
 754          loop (not worth the problems).  */
 755       for (e = header->pred; e; e = e->pred_next)
 756         if (e->flags & EDGE_ABNORMAL)
 757           break;
 758       if (e)
 759         continue;
 760
 761       for (e = header->pred; e; e = e->pred_next)
 762         {
 763           basic_block latch = e->src;
 764
 765           if (e->flags & EDGE_ABNORMAL)
 766             abort ();
 767
 768           /* Look for back edges where a predecessor is dominated
 769              by this block.  A natural loop has a single entry
 770              node (header) that dominates all the nodes in the
 771              loop.  It also has single back edge to the header
 772              from a latch node.  */
 773           if (latch != ENTRY_BLOCK_PTR
 774               && dominated_by_p (CDI_DOMINATORS, latch, header))
 775             {
 776               /* Shared headers should be eliminated by now.  */
 777               if (more_latches)
 778                 abort ();
 779               more_latches = 1;
 780               SET_BIT (headers, header->index);
 781               num_loops++;
 782             }
 783         }
 784     }
 785
 786   /* Allocate loop structures.  */
 787   loops->parray = xcalloc (num_loops + 1, sizeof (struct loop *));
 788
 789   /* Dummy loop containing whole function.  */
 790   loops->parray[0] = xcalloc (1, sizeof (struct loop));
 791   loops->parray[0]->next = NULL;
 792   loops->parray[0]->inner = NULL;
 793   loops->parray[0]->outer = NULL;
 794   loops->parray[0]->depth = 0;
 795   loops->parray[0]->pred = NULL;
 796   loops->parray[0]->num_nodes = n_basic_blocks + 2;
 797   loops->parray[0]->latch = EXIT_BLOCK_PTR;
 798   loops->parray[0]->header = ENTRY_BLOCK_PTR;
 799   ENTRY_BLOCK_PTR->loop_father = loops->parray[0];
 800   EXIT_BLOCK_PTR->loop_father = loops->parray[0];
 801
 802   loops->tree_root = loops->parray[0];
 803
 804   /* Find and record information about all the natural loops
 805      in the CFG.  */
 806   loops->num = 1;
 807   FOR_EACH_BB (bb)
 808     bb->loop_father = loops->tree_root;
 809
 810   if (num_loops)
 811     {
 812       /* Compute depth first search order of the CFG so that outer
 813          natural loops will be found before inner natural loops.  */
 814       dfs_order = xmalloc (n_basic_blocks * sizeof (int));
 815       rc_order = xmalloc (n_basic_blocks * sizeof (int));
 816       flow_depth_first_order_compute (dfs_order, rc_order);
 817
 818       /* Save CFG derived information to avoid recomputing it.  */
 819       loops->cfg.dfs_order = dfs_order;
 820       loops->cfg.rc_order = rc_order;
 821
 822       num_loops = 1;
 823
 824       for (b = 0; b < n_basic_blocks; b++)
 825         {
 826           struct loop *loop;
 827
 828           /* Search the nodes of the CFG in reverse completion order
 829              so that we can find outer loops first.  */
 830           if (!TEST_BIT (headers, rc_order[b]))
 831             continue;
 832
 833           header = BASIC_BLOCK (rc_order[b]);
 834
 835           loop = loops->parray[num_loops] = xcalloc (1, sizeof (struct loop));
 836
 837           loop->header = header;
 838           loop->num = num_loops;
 839           num_loops++;
 840
 841           /* Look for the latch for this header block.  */
 842           for (e = header->pred; e; e = e->pred_next)
 843             {
 844               basic_block latch = e->src;
 845
 846               if (latch != ENTRY_BLOCK_PTR
 847                   && dominated_by_p (CDI_DOMINATORS, latch, header))
 848                 {
 849                   loop->latch = latch;
 850                   break;
 851                 }
 852             }
 853
 854           flow_loop_tree_node_add (header->loop_father, loop);
 855           loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
 856         }
 857
 858       /* Assign the loop nesting depth and enclosed loop level for each
 859          loop.  */
 860       loops->levels = flow_loops_level_compute (loops);
 861
 862       /* Scan the loops.  */
 863       for (i = 1; i < num_loops; i++)
 864         flow_loop_scan (loops->parray[i], flags);
 865
 866       loops->num = num_loops;
 867     }
 868   else
 869     {
 870       free_dominance_info (CDI_DOMINATORS);
 871     }
 872
 873   sbitmap_free (headers);
 874
 875   loops->state = 0;
 876 #ifdef ENABLE_CHECKING
 877   verify_flow_info ();
 878   verify_loop_structure (loops);
 879 #endif
 880
 881   return loops->num;
 882 }
 883
 884 /* Update the information regarding the loops in the CFG
 885    specified by LOOPS.  */
 886
 887 int
 888 flow_loops_update (struct loops *loops, int flags)
 889 {
 890   /* One day we may want to update the current loop data.  For now
 891      throw away the old stuff and rebuild what we need.  */
 892   if (loops->parray)
 893     flow_loops_free (loops);
 894
 895   return flow_loops_find (loops, flags);
 896 }
 897
 898 /* Return nonzero if basic block BB belongs to LOOP.  */
 899 bool
 900 flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb)
 901 {
 902   struct loop *source_loop;
 903
 904   if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
 905     return 0;
 906
 907   source_loop = bb->loop_father;
 908   return loop == source_loop || flow_loop_nested_p (loop, source_loop);
 909 }
 910
 911 /* Return nonzero if edge E enters header of LOOP from outside of LOOP.  */
 912
 913 bool
 914 flow_loop_outside_edge_p (const struct loop *loop, edge e)
 915 {
 916   if (e->dest != loop->header)
 917     abort ();
 918   return !flow_bb_inside_loop_p (loop, e->src);
 919 }
 920
 921 /* Enumeration predicate for get_loop_body.  */
 922 static bool
 923 glb_enum_p (basic_block bb, void *glb_header)
 924 {
 925   return bb != (basic_block) glb_header;
 926 }
 927
 928 /* Gets basic blocks of a LOOP.  Header is the 0-th block, rest is in dfs
 929    order against direction of edges from latch.  Specially, if
 930    header != latch, latch is the 1-st block.  */
 931 basic_block *
 932 get_loop_body (const struct loop *loop)
 933 {
 934   basic_block *tovisit, bb;
 935   unsigned tv = 0;
 936
 937   if (!loop->num_nodes)
 938     abort ();
 939
 940   tovisit = xcalloc (loop->num_nodes, sizeof (basic_block));
 941   tovisit[tv++] = loop->header;
 942
 943   if (loop->latch == EXIT_BLOCK_PTR)
 944     {
 945       /* There may be blocks unreachable from EXIT_BLOCK.  */
 946       if (loop->num_nodes != (unsigned) n_basic_blocks + 2)
 947         abort ();
 948       FOR_EACH_BB (bb)
 949         tovisit[tv++] = bb;
 950       tovisit[tv++] = EXIT_BLOCK_PTR;
 951     }
 952   else if (loop->latch != loop->header)
 953     {
 954       tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p,
 955                                tovisit + 1, loop->num_nodes - 1,
 956                                loop->header) + 1;
 957     }
 958
 959   if (tv != loop->num_nodes)
 960     abort ();
 961   return tovisit;
 962 }
 963
 964 /* Fills dominance descendants inside LOOP of the basic block BB into
 965    array TOVISIT from index *TV.  */
 966
 967 static void
 968 fill_sons_in_loop (const struct loop *loop, basic_block bb,
 969                    basic_block *tovisit, int *tv)
 970 {
 971   basic_block son, postpone = NULL;
 972
 973   tovisit[(*tv)++] = bb;
 974   for (son = first_dom_son (CDI_DOMINATORS, bb);
 975        son;
 976        son = next_dom_son (CDI_DOMINATORS, son))
 977     {
 978       if (!flow_bb_inside_loop_p (loop, son))
 979         continue;
 980
 981       if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
 982         {
 983           postpone = son;
 984           continue;
 985         }
 986       fill_sons_in_loop (loop, son, tovisit, tv);
 987     }
 988
 989   if (postpone)
 990     fill_sons_in_loop (loop, postpone, tovisit, tv);
 991 }
 992
 993 /* Gets body of a LOOP (that must be different from the outermost loop)
 994    sorted by dominance relation.  Additionally, if a basic block s dominates
 995    the latch, then only blocks dominated by s are be after it.  */
 996
 997 basic_block *
 998 get_loop_body_in_dom_order (const struct loop *loop)
 999 {
1000   basic_block *tovisit;
1001   int tv;
1002
1003   if (!loop->num_nodes)
1004     abort ();
1005
1006   tovisit = xcalloc (loop->num_nodes, sizeof (basic_block));
1007
1008   if (loop->latch == EXIT_BLOCK_PTR)
1009     abort ();
1010
1011   tv = 0;
1012   fill_sons_in_loop (loop, loop->header, tovisit, &tv);
1013
1014   if (tv != (int) loop->num_nodes)
1015     abort ();
1016
1017   return tovisit;
1018 }
1019
1020 /* Gets exit edges of a LOOP, returning their number in N_EDGES.  */
1021 edge *
1022 get_loop_exit_edges (const struct loop *loop, unsigned int *n_edges)
1023 {
1024   edge *edges, e;
1025   unsigned i, n;
1026   basic_block * body;
1027
1028   if (loop->latch == EXIT_BLOCK_PTR)
1029     abort ();
1030
1031   body = get_loop_body (loop);
1032   n = 0;
1033   for (i = 0; i < loop->num_nodes; i++)
1034     for (e = body[i]->succ; e; e = e->succ_next)
1035       if (!flow_bb_inside_loop_p (loop, e->dest))
1036         n++;
1037   edges = xmalloc (n * sizeof (edge));
1038   *n_edges = n;
1039   n = 0;
1040   for (i = 0; i < loop->num_nodes; i++)
1041     for (e = body[i]->succ; e; e = e->succ_next)
1042       if (!flow_bb_inside_loop_p (loop, e->dest))
1043         edges[n++] = e;
1044   free (body);
1045
1046   return edges;
1047 }
1048
1049 /* Counts the number of conditional branches inside LOOP.  */
1050
1051 unsigned
1052 num_loop_branches (const struct loop *loop)
1053 {
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     if (body[i]->succ && body[i]->succ->succ_next)
1064       n++;
1065   free (body);
1066
1067   return n;
1068 }
1069
1070 /* Adds basic block BB to LOOP.  */
1071 void
1072 add_bb_to_loop (basic_block bb, struct loop *loop)
1073 {
1074    int i;
1075
1076    bb->loop_father = loop;
1077    bb->loop_depth = loop->depth;
1078    loop->num_nodes++;
1079    for (i = 0; i < loop->depth; i++)
1080      loop->pred[i]->num_nodes++;
1081  }
1082
1083 /* Remove basic block BB from loops.  */
1084 void
1085 remove_bb_from_loops (basic_block bb)
1086 {
1087    int i;
1088    struct loop *loop = bb->loop_father;
1089
1090    loop->num_nodes--;
1091    for (i = 0; i < loop->depth; i++)
1092      loop->pred[i]->num_nodes--;
1093    bb->loop_father = NULL;
1094    bb->loop_depth = 0;
1095  }
1096
1097 /* Finds nearest common ancestor in loop tree for given loops.  */
1098 struct loop *
1099 find_common_loop (struct loop *loop_s, struct loop *loop_d)
1100 {
1101   if (!loop_s) return loop_d;
1102   if (!loop_d) return loop_s;
1103
1104   if (loop_s->depth < loop_d->depth)
1105     loop_d = loop_d->pred[loop_s->depth];
1106   else if (loop_s->depth > loop_d->depth)
1107     loop_s = loop_s->pred[loop_d->depth];
1108
1109   while (loop_s != loop_d)
1110     {
1111       loop_s = loop_s->outer;
1112       loop_d = loop_d->outer;
1113     }
1114   return loop_s;
1115 }
1116
1117 /* Cancels the LOOP; it must be innermost one.  */
1118 void
1119 cancel_loop (struct loops *loops, struct loop *loop)
1120 {
1121   basic_block *bbs;
1122   unsigned i;
1123
1124   if (loop->inner)
1125     abort ();
1126
1127   /* Move blocks up one level (they should be removed as soon as possible).  */
1128   bbs = get_loop_body (loop);
1129   for (i = 0; i < loop->num_nodes; i++)
1130     bbs[i]->loop_father = loop->outer;
1131
1132   /* Remove the loop from structure.  */
1133   flow_loop_tree_node_remove (loop);
1134
1135   /* Remove loop from loops array.  */
1136   loops->parray[loop->num] = NULL;
1137
1138   /* Free loop data.  */
1139   flow_loop_free (loop);
1140 }
1141
1142 /* Cancels LOOP and all its subloops.  */
1143 void
1144 cancel_loop_tree (struct loops *loops, struct loop *loop)
1145 {
1146   while (loop->inner)
1147     cancel_loop_tree (loops, loop->inner);
1148   cancel_loop (loops, loop);
1149 }
1150
1151 /* Checks that LOOPS are all right:
1152      -- sizes of loops are all right
1153      -- results of get_loop_body really belong to the loop
1154      -- loop header have just single entry edge and single latch edge
1155      -- loop latches have only single successor that is header of their loop
1156      -- irreducible loops are correctly marked
1157   */
1158 void
1159 verify_loop_structure (struct loops *loops)
1160 {
1161   unsigned *sizes, i, j;
1162   sbitmap irreds;
1163   basic_block *bbs, bb;
1164   struct loop *loop;
1165   int err = 0;
1166   edge e;
1167
1168   /* Check sizes.  */
1169   sizes = xcalloc (loops->num, sizeof (int));
1170   sizes[0] = 2;
1171
1172   FOR_EACH_BB (bb)
1173     for (loop = bb->loop_father; loop; loop = loop->outer)
1174       sizes[loop->num]++;
1175
1176   for (i = 0; i < loops->num; i++)
1177     {
1178       if (!loops->parray[i])
1179         continue;
1180
1181       if (loops->parray[i]->num_nodes != sizes[i])
1182         {
1183           error ("Size of loop %d should be %d, not %d.",
1184                    i, sizes[i], loops->parray[i]->num_nodes);
1185           err = 1;
1186         }
1187     }
1188
1189   free (sizes);
1190
1191   /* Check get_loop_body.  */
1192   for (i = 1; i < loops->num; i++)
1193     {
1194       loop = loops->parray[i];
1195       if (!loop)
1196         continue;
1197       bbs = get_loop_body (loop);
1198
1199       for (j = 0; j < loop->num_nodes; j++)
1200         if (!flow_bb_inside_loop_p (loop, bbs[j]))
1201           {
1202             error ("Bb %d do not belong to loop %d.",
1203                     bbs[j]->index, i);
1204             err = 1;
1205           }
1206       free (bbs);
1207     }
1208
1209   /* Check headers and latches.  */
1210   for (i = 1; i < loops->num; i++)
1211     {
1212       loop = loops->parray[i];
1213       if (!loop)
1214         continue;
1215
1216       if ((loops->state & LOOPS_HAVE_PREHEADERS)
1217           && (!loop->header->pred->pred_next
1218               || loop->header->pred->pred_next->pred_next))
1219         {
1220           error ("Loop %d's header does not have exactly 2 entries.", i);
1221           err = 1;
1222         }
1223       if (loops->state & LOOPS_HAVE_SIMPLE_LATCHES)
1224         {
1225           if (!loop->latch->succ
1226               || loop->latch->succ->succ_next)
1227             {
1228               error ("Loop %d's latch does not have exactly 1 successor.", i);
1229               err = 1;
1230             }
1231           if (loop->latch->succ->dest != loop->header)
1232             {
1233               error ("Loop %d's latch does not have header as successor.", i);
1234               err = 1;
1235             }
1236           if (loop->latch->loop_father != loop)
1237             {
1238               error ("Loop %d's latch does not belong directly to it.", i);
1239               err = 1;
1240             }
1241         }
1242       if (loop->header->loop_father != loop)
1243         {
1244           error ("Loop %d's header does not belong directly to it.", i);
1245           err = 1;
1246         }
1247       if ((loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1248           && (loop_latch_edge (loop)->flags & EDGE_IRREDUCIBLE_LOOP))
1249         {
1250           error ("Loop %d's latch is marked as part of irreducible region.", i);
1251           err = 1;
1252         }
1253     }
1254
1255   /* Check irreducible loops.  */
1256   if (loops->state & LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS)
1257     {
1258       /* Record old info.  */
1259       irreds = sbitmap_alloc (last_basic_block);
1260       FOR_EACH_BB (bb)
1261         {
1262           if (bb->flags & BB_IRREDUCIBLE_LOOP)
1263             SET_BIT (irreds, bb->index);
1264           else
1265             RESET_BIT (irreds, bb->index);
1266           for (e = bb->succ; e; e = e->succ_next)
1267             if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1268               e->flags |= EDGE_ALL_FLAGS + 1;
1269         }
1270
1271       /* Recount it.  */
1272       mark_irreducible_loops (loops);
1273
1274       /* Compare.  */
1275       FOR_EACH_BB (bb)
1276         {
1277           if ((bb->flags & BB_IRREDUCIBLE_LOOP)
1278               && !TEST_BIT (irreds, bb->index))
1279             {
1280               error ("Basic block %d should be marked irreducible.", bb->index);
1281               err = 1;
1282             }
1283           else if (!(bb->flags & BB_IRREDUCIBLE_LOOP)
1284               && TEST_BIT (irreds, bb->index))
1285             {
1286               error ("Basic block %d should not be marked irreducible.", bb->index);
1287               err = 1;
1288             }
1289           for (e = bb->succ; e; e = e->succ_next)
1290             {
1291               if ((e->flags & EDGE_IRREDUCIBLE_LOOP)
1292                   && !(e->flags & (EDGE_ALL_FLAGS + 1)))
1293                 {
1294                   error ("Edge from %d to %d should be marked irreducible.",
1295                          e->src->index, e->dest->index);
1296                   err = 1;
1297                 }
1298               else if (!(e->flags & EDGE_IRREDUCIBLE_LOOP)
1299                        && (e->flags & (EDGE_ALL_FLAGS + 1)))
1300                 {
1301                   error ("Edge from %d to %d should not be marked irreducible.",
1302                          e->src->index, e->dest->index);
1303                   err = 1;
1304                 }
1305               e->flags &= ~(EDGE_ALL_FLAGS + 1);
1306             }
1307         }
1308       free (irreds);
1309     }
1310
1311   if (err)
1312     abort ();
1313 }
1314
1315 /* Returns latch edge of LOOP.  */
1316 edge
1317 loop_latch_edge (const struct loop *loop)
1318 {
1319   edge e;
1320
1321   for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next)
1322     continue;
1323
1324   return e;
1325 }
1326
1327 /* Returns preheader edge of LOOP.  */
1328 edge
1329 loop_preheader_edge (const struct loop *loop)
1330 {
1331   edge e;
1332
1333   for (e = loop->header->pred; e->src == loop->latch; e = e->pred_next)
1334     continue;
1335
1336   return e;
1337 }