gcc/cfgloop.c

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