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