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:%s\n", loop->num,
 131              loop->invalid ? " invalid" : "");
 132
 133   fprintf (file, ";;  header %d, latch %d\n",
 134            loop->header->index, loop->latch->index);
 135   fprintf (file, ";;  depth %d, level %d, outer %ld\n",
 136            loop->depth, loop->level,
 137            (long) (loop->outer ? loop->outer->num : -1));
 138
 139   fprintf (file, ";;  nodes:");
 140   bbs = get_loop_body (loop);
 141   for (i = 0; i < loop->num_nodes; i++)
 142     fprintf (file, " %d", bbs[i]->index);
 143   free (bbs);
 144   fprintf (file, "\n");
 145
 146   if (loop_dump_aux)
 147     loop_dump_aux (loop, file, verbose);
 148 }
 149
 150 /* Dump the loop information specified by LOOPS to the stream FILE,
 151    using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
 152
 153 void
 154 flow_loops_dump (const struct loops *loops, FILE *file, void (*loop_dump_aux) (const struct loop *, FILE *, int), int verbose)
 155 {
 156   int i;
 157   int num_loops;
 158
 159   num_loops = loops->num;
 160   if (! num_loops || ! file)
 161     return;
 162
 163   fprintf (file, ";; %d loops found\n", num_loops);
 164
 165   for (i = 0; i < num_loops; i++)
 166     {
 167       struct loop *loop = loops->parray[i];
 168
 169       if (!loop)
 170         continue;
 171
 172       flow_loop_dump (loop, file, loop_dump_aux, verbose);
 173     }
 174
 175   if (verbose)
 176     flow_loops_cfg_dump (loops, file);
 177 }
 178
 179 /* Free data allocated for LOOP.  */
 180 void
 181 flow_loop_free (struct loop *loop)
 182 {
 183   if (loop->pred)
 184     free (loop->pred);
 185   free (loop);
 186 }
 187
 188 /* Free all the memory allocated for LOOPS.  */
 189
 190 void
 191 flow_loops_free (struct loops *loops)
 192 {
 193   if (loops->parray)
 194     {
 195       unsigned i;
 196
 197       gcc_assert (loops->num);
 198
 199       /* Free the loop descriptors.  */
 200       for (i = 0; i < loops->num; i++)
 201         {
 202           struct loop *loop = loops->parray[i];
 203
 204           if (!loop)
 205             continue;
 206
 207           flow_loop_free (loop);
 208         }
 209
 210       free (loops->parray);
 211       loops->parray = NULL;
 212
 213       if (loops->cfg.dfs_order)
 214         free (loops->cfg.dfs_order);
 215       if (loops->cfg.rc_order)
 216         free (loops->cfg.rc_order);
 217
 218     }
 219 }
 220
 221 /* Find the nodes contained within the LOOP with header HEADER.
 222    Return the number of nodes within the loop.  */
 223
 224 int
 225 flow_loop_nodes_find (basic_block header, struct loop *loop)
 226 {
 227   basic_block *stack;
 228   int sp;
 229   int num_nodes = 1;
 230
 231   header->loop_father = loop;
 232   header->loop_depth = loop->depth;
 233
 234   if (loop->latch->loop_father != loop)
 235     {
 236       stack = XNEWVEC (basic_block, n_basic_blocks);
 237       sp = 0;
 238       num_nodes++;
 239       stack[sp++] = loop->latch;
 240       loop->latch->loop_father = loop;
 241       loop->latch->loop_depth = loop->depth;
 242
 243       while (sp)
 244         {
 245           basic_block node;
 246           edge e;
 247           edge_iterator ei;
 248
 249           node = stack[--sp];
 250
 251           FOR_EACH_EDGE (e, ei, node->preds)
 252             {
 253               basic_block ancestor = e->src;
 254
 255               if (ancestor != ENTRY_BLOCK_PTR
 256                   && ancestor->loop_father != loop)
 257                 {
 258                   ancestor->loop_father = loop;
 259                   ancestor->loop_depth = loop->depth;
 260                   num_nodes++;
 261                   stack[sp++] = ancestor;
 262                 }
 263             }
 264         }
 265       free (stack);
 266     }
 267   return num_nodes;
 268 }
 269
 270 /* For each loop in the lOOPS tree that has just a single exit
 271    record the exit edge.  */
 272
 273 void
 274 mark_single_exit_loops (struct loops *loops)
 275 {
 276   basic_block bb;
 277   edge e;
 278   struct loop *loop;
 279   unsigned i;
 280
 281   for (i = 1; i < loops->num; i++)
 282     {
 283       loop = loops->parray[i];
 284       if (loop)
 285         loop->single_exit = NULL;
 286     }
 287
 288   FOR_EACH_BB (bb)
 289     {
 290       edge_iterator ei;
 291       if (bb->loop_father == loops->tree_root)
 292         continue;
 293       FOR_EACH_EDGE (e, ei, bb->succs)
 294         {
 295           if (e->dest == EXIT_BLOCK_PTR)
 296             continue;
 297
 298           if (flow_bb_inside_loop_p (bb->loop_father, e->dest))
 299             continue;
 300
 301           for (loop = bb->loop_father;
 302                loop != e->dest->loop_father;
 303                loop = loop->outer)
 304             {
 305               /* If we have already seen an exit, mark this by the edge that
 306                  surely does not occur as any exit.  */
 307               if (loop->single_exit)
 308                 loop->single_exit = single_succ_edge (ENTRY_BLOCK_PTR);
 309               else
 310                 loop->single_exit = e;
 311             }
 312         }
 313     }
 314
 315   for (i = 1; i < loops->num; i++)
 316     {
 317       loop = loops->parray[i];
 318       if (!loop)
 319         continue;
 320
 321       if (loop->single_exit == single_succ_edge (ENTRY_BLOCK_PTR))
 322         loop->single_exit = NULL;
 323     }
 324
 325   loops->state |= LOOPS_HAVE_MARKED_SINGLE_EXITS;
 326 }
 327
 328 static void
 329 establish_preds (struct loop *loop)
 330 {
 331   struct loop *ploop, *father = loop->outer;
 332
 333   loop->depth = father->depth + 1;
 334
 335   /* Remember the current loop depth if it is the largest seen so far.  */
 336   cfun->max_loop_depth = MAX (cfun->max_loop_depth, loop->depth);
 337
 338   if (loop->pred)
 339     free (loop->pred);
 340   loop->pred = XNEWVEC (struct loop *, loop->depth);
 341   memcpy (loop->pred, father->pred, sizeof (struct loop *) * father->depth);
 342   loop->pred[father->depth] = father;
 343
 344   for (ploop = loop->inner; ploop; ploop = ploop->next)
 345     establish_preds (ploop);
 346 }
 347
 348 /* Add LOOP to the loop hierarchy tree where FATHER is father of the
 349    added loop.  If LOOP has some children, take care of that their
 350    pred field will be initialized correctly.  */
 351
 352 void
 353 flow_loop_tree_node_add (struct loop *father, struct loop *loop)
 354 {
 355   loop->next = father->inner;
 356   father->inner = loop;
 357   loop->outer = father;
 358
 359   establish_preds (loop);
 360 }
 361
 362 /* Remove LOOP from the loop hierarchy tree.  */
 363
 364 void
 365 flow_loop_tree_node_remove (struct loop *loop)
 366 {
 367   struct loop *prev, *father;
 368
 369   father = loop->outer;
 370   loop->outer = NULL;
 371
 372   /* Remove loop from the list of sons.  */
 373   if (father->inner == loop)
 374     father->inner = loop->next;
 375   else
 376     {
 377       for (prev = father->inner; prev->next != loop; prev = prev->next);
 378       prev->next = loop->next;
 379     }
 380
 381   loop->depth = -1;
 382   free (loop->pred);
 383   loop->pred = NULL;
 384 }
 385
 386 /* Helper function to compute loop nesting depth and enclosed loop level
 387    for the natural loop specified by LOOP.  Returns the loop level.  */
 388
 389 static int
 390 flow_loop_level_compute (struct loop *loop)
 391 {
 392   struct loop *inner;
 393   int level = 1;
 394
 395   if (! loop)
 396     return 0;
 397
 398   /* Traverse loop tree assigning depth and computing level as the
 399      maximum level of all the inner loops of this loop.  The loop
 400      level is equivalent to the height of the loop in the loop tree
 401      and corresponds to the number of enclosed loop levels (including
 402      itself).  */
 403   for (inner = loop->inner; inner; inner = inner->next)
 404     {
 405       int ilevel = flow_loop_level_compute (inner) + 1;
 406
 407       if (ilevel > level)
 408         level = ilevel;
 409     }
 410
 411   loop->level = level;
 412   return level;
 413 }
 414
 415 /* Compute the loop nesting depth and enclosed loop level for the loop
 416    hierarchy tree specified by LOOPS.  Return the maximum enclosed loop
 417    level.  */
 418
 419 static void
 420 flow_loops_level_compute (struct loops *loops)
 421 {
 422   flow_loop_level_compute (loops->tree_root);
 423 }
 424
 425 /* A callback to update latch and header info for basic block JUMP created
 426    by redirecting an edge.  */
 427
 428 static void
 429 update_latch_info (basic_block jump)
 430 {
 431   alloc_aux_for_block (jump, sizeof (int));
 432   HEADER_BLOCK (jump) = 0;
 433   alloc_aux_for_edge (single_pred_edge (jump), sizeof (int));
 434   LATCH_EDGE (single_pred_edge (jump)) = 0;
 435   set_immediate_dominator (CDI_DOMINATORS, jump, single_pred (jump));
 436 }
 437
 438 /* A callback for make_forwarder block, to redirect all edges except for
 439    MFB_KJ_EDGE to the entry part.  E is the edge for that we should decide
 440    whether to redirect it.  */
 441
 442 static edge mfb_kj_edge;
 443 static bool
 444 mfb_keep_just (edge e)
 445 {
 446   return e != mfb_kj_edge;
 447 }
 448
 449 /* A callback for make_forwarder block, to redirect the latch edges into an
 450    entry part.  E is the edge for that we should decide whether to redirect
 451    it.  */
 452
 453 static bool
 454 mfb_keep_nonlatch (edge e)
 455 {
 456   return LATCH_EDGE (e);
 457 }
 458
 459 /* Takes care of merging natural loops with shared headers.  */
 460
 461 static void
 462 canonicalize_loop_headers (void)
 463 {
 464   basic_block header;
 465   edge e;
 466
 467   alloc_aux_for_blocks (sizeof (int));
 468   alloc_aux_for_edges (sizeof (int));
 469
 470   /* Split blocks so that each loop has only single latch.  */
 471   FOR_EACH_BB (header)
 472     {
 473       edge_iterator ei;
 474       int num_latches = 0;
 475       int have_abnormal_edge = 0;
 476
 477       FOR_EACH_EDGE (e, ei, header->preds)
 478         {
 479           basic_block latch = e->src;
 480
 481           if (e->flags & EDGE_ABNORMAL)
 482             have_abnormal_edge = 1;
 483
 484           if (latch != ENTRY_BLOCK_PTR
 485               && dominated_by_p (CDI_DOMINATORS, latch, header))
 486             {
 487               num_latches++;
 488               LATCH_EDGE (e) = 1;
 489             }
 490         }
 491       if (have_abnormal_edge)
 492         HEADER_BLOCK (header) = 0;
 493       else
 494         HEADER_BLOCK (header) = num_latches;
 495     }
 496
 497   if (HEADER_BLOCK (single_succ (ENTRY_BLOCK_PTR)))
 498     {
 499       basic_block bb;
 500
 501       /* We could not redirect edges freely here. On the other hand,
 502          we can simply split the edge from entry block.  */
 503       bb = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
 504
 505       alloc_aux_for_edge (single_succ_edge (bb), sizeof (int));
 506       LATCH_EDGE (single_succ_edge (bb)) = 0;
 507       alloc_aux_for_block (bb, sizeof (int));
 508       HEADER_BLOCK (bb) = 0;
 509     }
 510
 511   FOR_EACH_BB (header)
 512     {
 513       int max_freq, is_heavy;
 514       edge heavy, tmp_edge;
 515       edge_iterator ei;
 516
 517       if (HEADER_BLOCK (header) <= 1)
 518         continue;
 519
 520       /* Find a heavy edge.  */
 521       is_heavy = 1;
 522       heavy = NULL;
 523       max_freq = 0;
 524       FOR_EACH_EDGE (e, ei, header->preds)
 525         if (LATCH_EDGE (e) &&
 526             EDGE_FREQUENCY (e) > max_freq)
 527           max_freq = EDGE_FREQUENCY (e);
 528       FOR_EACH_EDGE (e, ei, header->preds)
 529         if (LATCH_EDGE (e) &&
 530             EDGE_FREQUENCY (e) >= max_freq / HEAVY_EDGE_RATIO)
 531           {
 532             if (heavy)
 533               {
 534                 is_heavy = 0;
 535                 break;
 536               }
 537             else
 538               heavy = e;
 539           }
 540
 541       if (is_heavy)
 542         {
 543           /* Split out the heavy edge, and create inner loop for it.  */
 544           mfb_kj_edge = heavy;
 545           tmp_edge = make_forwarder_block (header, mfb_keep_just,
 546                                            update_latch_info);
 547           alloc_aux_for_block (tmp_edge->dest, sizeof (int));
 548           HEADER_BLOCK (tmp_edge->dest) = 1;
 549           alloc_aux_for_edge (tmp_edge, sizeof (int));
 550           LATCH_EDGE (tmp_edge) = 0;
 551           HEADER_BLOCK (header)--;
 552         }
 553
 554       if (HEADER_BLOCK (header) > 1)
 555         {
 556           /* Create a new latch block.  */
 557           tmp_edge = make_forwarder_block (header, mfb_keep_nonlatch,
 558                                            update_latch_info);
 559           alloc_aux_for_block (tmp_edge->dest, sizeof (int));
 560           HEADER_BLOCK (tmp_edge->src) = 0;
 561           HEADER_BLOCK (tmp_edge->dest) = 1;
 562           alloc_aux_for_edge (tmp_edge, sizeof (int));
 563           LATCH_EDGE (tmp_edge) = 1;
 564         }
 565     }
 566
 567   free_aux_for_blocks ();
 568   free_aux_for_edges ();
 569
 570 #ifdef ENABLE_CHECKING
 571   verify_dominators (CDI_DOMINATORS);
 572 #endif
 573 }
 574
 575 /* Initialize all the parallel_p fields of the loops structure to true.  */
 576
 577 static void
 578 initialize_loops_parallel_p (struct loops *loops)
 579 {
 580   unsigned int i;
 581
 582   for (i = 0; i < loops->num; i++)
 583     {
 584       struct loop *loop = loops->parray[i];
 585       loop->parallel_p = true;
 586     }
 587 }
 588
 589 /* Find all the natural loops in the function and save in LOOPS structure and
 590    recalculate loop_depth information in basic block structures.
 591    Return the number of natural loops found.  */
 592
 593 int
 594 flow_loops_find (struct loops *loops)
 595 {
 596   int b;
 597   int num_loops;
 598   edge e;
 599   sbitmap headers;
 600   int *dfs_order;
 601   int *rc_order;
 602   basic_block header;
 603   basic_block bb;
 604
 605   memset (loops, 0, sizeof *loops);
 606
 607   /* We are going to recount the maximum loop depth,
 608      so throw away the last count.  */
 609   cfun->max_loop_depth = 0;
 610
 611   /* Taking care of this degenerate case makes the rest of
 612      this code simpler.  */
 613   if (n_basic_blocks == NUM_FIXED_BLOCKS)
 614     return 0;
 615
 616   dfs_order = NULL;
 617   rc_order = NULL;
 618
 619   /* Ensure that the dominators are computed.  */
 620   calculate_dominance_info (CDI_DOMINATORS);
 621
 622   /* Join loops with shared headers.  */
 623   canonicalize_loop_headers ();
 624
 625   /* Count the number of loop headers.  This should be the
 626      same as the number of natural loops.  */
 627   headers = sbitmap_alloc (last_basic_block);
 628   sbitmap_zero (headers);
 629
 630   num_loops = 0;
 631   FOR_EACH_BB (header)
 632     {
 633       edge_iterator ei;
 634       int more_latches = 0;
 635
 636       header->loop_depth = 0;
 637
 638       /* If we have an abnormal predecessor, do not consider the
 639          loop (not worth the problems).  */
 640       FOR_EACH_EDGE (e, ei, header->preds)
 641         if (e->flags & EDGE_ABNORMAL)
 642           break;
 643       if (e)
 644         continue;
 645
 646       FOR_EACH_EDGE (e, ei, header->preds)
 647         {
 648           basic_block latch = e->src;
 649
 650           gcc_assert (!(e->flags & EDGE_ABNORMAL));
 651
 652           /* Look for back edges where a predecessor is dominated
 653              by this block.  A natural loop has a single entry
 654              node (header) that dominates all the nodes in the
 655              loop.  It also has single back edge to the header
 656              from a latch node.  */
 657           if (latch != ENTRY_BLOCK_PTR
 658               && dominated_by_p (CDI_DOMINATORS, latch, header))
 659             {
 660               /* Shared headers should be eliminated by now.  */
 661               gcc_assert (!more_latches);
 662               more_latches = 1;
 663               SET_BIT (headers, header->index);
 664               num_loops++;
 665             }
 666         }
 667     }
 668
 669   /* Allocate loop structures.  */
 670   loops->parray = XCNEWVEC (struct loop *, num_loops + 1);
 671
 672   /* Dummy loop containing whole function.  */
 673   loops->parray[0] = XCNEW (struct loop);
 674   loops->parray[0]->next = NULL;
 675   loops->parray[0]->inner = NULL;
 676   loops->parray[0]->outer = NULL;
 677   loops->parray[0]->depth = 0;
 678   loops->parray[0]->pred = NULL;
 679   loops->parray[0]->num_nodes = n_basic_blocks;
 680   loops->parray[0]->latch = EXIT_BLOCK_PTR;
 681   loops->parray[0]->header = ENTRY_BLOCK_PTR;
 682   ENTRY_BLOCK_PTR->loop_father = loops->parray[0];
 683   EXIT_BLOCK_PTR->loop_father = loops->parray[0];
 684
 685   loops->tree_root = loops->parray[0];
 686
 687   /* Find and record information about all the natural loops
 688      in the CFG.  */
 689   loops->num = 1;
 690   FOR_EACH_BB (bb)
 691     bb->loop_father = loops->tree_root;
 692
 693   if (num_loops)
 694     {
 695       /* Compute depth first search order of the CFG so that outer
 696          natural loops will be found before inner natural loops.  */
 697       dfs_order = XNEWVEC (int, n_basic_blocks);
 698       rc_order = XNEWVEC (int, n_basic_blocks);
 699       pre_and_rev_post_order_compute (dfs_order, rc_order, false);
 700
 701       /* Save CFG derived information to avoid recomputing it.  */
 702       loops->cfg.dfs_order = dfs_order;
 703       loops->cfg.rc_order = rc_order;
 704
 705       num_loops = 1;
 706
 707       for (b = 0; b < n_basic_blocks - NUM_FIXED_BLOCKS; b++)
 708         {
 709           struct loop *loop;
 710           edge_iterator ei;
 711
 712           /* Search the nodes of the CFG in reverse completion order
 713              so that we can find outer loops first.  */
 714           if (!TEST_BIT (headers, rc_order[b]))
 715             continue;
 716
 717           header = BASIC_BLOCK (rc_order[b]);
 718
 719           loop = loops->parray[num_loops] = XCNEW (struct loop);
 720
 721           loop->header = header;
 722           loop->num = num_loops;
 723           num_loops++;
 724
 725           /* Look for the latch for this header block.  */
 726           FOR_EACH_EDGE (e, ei, header->preds)
 727             {
 728               basic_block latch = e->src;
 729
 730               if (latch != ENTRY_BLOCK_PTR
 731                   && dominated_by_p (CDI_DOMINATORS, latch, header))
 732                 {
 733                   loop->latch = latch;
 734                   break;
 735                 }
 736             }
 737
 738           flow_loop_tree_node_add (header->loop_father, loop);
 739           loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
 740         }
 741
 742       /* Assign the loop nesting depth and enclosed loop level for each
 743          loop.  */
 744       flow_loops_level_compute (loops);
 745
 746       loops->num = num_loops;
 747       initialize_loops_parallel_p (loops);
 748     }
 749
 750   sbitmap_free (headers);
 751
 752   loops->state = 0;
 753 #ifdef ENABLE_CHECKING
 754   verify_flow_info ();
 755   verify_loop_structure (loops);
 756 #endif
 757
 758   return loops->num;
 759 }
 760
 761 /* Return nonzero if basic block BB belongs to LOOP.  */
 762 bool
 763 flow_bb_inside_loop_p (const struct loop *loop, const basic_block bb)
 764 {
 765   struct loop *source_loop;
 766
 767   if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
 768     return 0;
 769
 770   source_loop = bb->loop_father;
 771   return loop == source_loop || flow_loop_nested_p (loop, source_loop);
 772 }
 773
 774 /* Enumeration predicate for get_loop_body.  */
 775 static bool
 776 glb_enum_p (basic_block bb, void *glb_header)
 777 {
 778   return bb != (basic_block) glb_header;
 779 }
 780
 781 /* Gets basic blocks of a LOOP.  Header is the 0-th block, rest is in dfs
 782    order against direction of edges from latch.  Specially, if
 783    header != latch, latch is the 1-st block.  */
 784 basic_block *
 785 get_loop_body (const struct loop *loop)
 786 {
 787   basic_block *tovisit, bb;
 788   unsigned tv = 0;
 789
 790   gcc_assert (loop->num_nodes);
 791
 792   tovisit = XCNEWVEC (basic_block, loop->num_nodes);
 793   tovisit[tv++] = loop->header;
 794
 795   if (loop->latch == EXIT_BLOCK_PTR)
 796     {
 797       /* There may be blocks unreachable from EXIT_BLOCK.  */
 798       gcc_assert (loop->num_nodes == (unsigned) n_basic_blocks);
 799       FOR_EACH_BB (bb)
 800         tovisit[tv++] = bb;
 801       tovisit[tv++] = EXIT_BLOCK_PTR;
 802     }
 803   else if (loop->latch != loop->header)
 804     {
 805       tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p,
 806                                tovisit + 1, loop->num_nodes - 1,
 807                                loop->header) + 1;
 808     }
 809
 810   gcc_assert (tv == loop->num_nodes);
 811   return tovisit;
 812 }
 813
 814 /* Fills dominance descendants inside LOOP of the basic block BB into
 815    array TOVISIT from index *TV.  */
 816
 817 static void
 818 fill_sons_in_loop (const struct loop *loop, basic_block bb,
 819                    basic_block *tovisit, int *tv)
 820 {
 821   basic_block son, postpone = NULL;
 822
 823   tovisit[(*tv)++] = bb;
 824   for (son = first_dom_son (CDI_DOMINATORS, bb);
 825        son;
 826        son = next_dom_son (CDI_DOMINATORS, son))
 827     {
 828       if (!flow_bb_inside_loop_p (loop, son))
 829         continue;
 830
 831       if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
 832         {
 833           postpone = son;
 834           continue;
 835         }
 836       fill_sons_in_loop (loop, son, tovisit, tv);
 837     }
 838
 839   if (postpone)
 840     fill_sons_in_loop (loop, postpone, tovisit, tv);
 841 }
 842
 843 /* Gets body of a LOOP (that must be different from the outermost loop)
 844    sorted by dominance relation.  Additionally, if a basic block s dominates
 845    the latch, then only blocks dominated by s are be after it.  */
 846
 847 basic_block *
 848 get_loop_body_in_dom_order (const struct loop *loop)
 849 {
 850   basic_block *tovisit;
 851   int tv;
 852
 853   gcc_assert (loop->num_nodes);
 854
 855   tovisit = XCNEWVEC (basic_block, loop->num_nodes);
 856
 857   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
 858
 859   tv = 0;
 860   fill_sons_in_loop (loop, loop->header, tovisit, &tv);
 861
 862   gcc_assert (tv == (int) loop->num_nodes);
 863
 864   return tovisit;
 865 }
 866
 867 /* Get body of a LOOP in breadth first sort order.  */
 868
 869 basic_block *
 870 get_loop_body_in_bfs_order (const struct loop *loop)
 871 {
 872   basic_block *blocks;
 873   basic_block bb;
 874   bitmap visited;
 875   unsigned int i = 0;
 876   unsigned int vc = 1;
 877
 878   gcc_assert (loop->num_nodes);
 879   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
 880
 881   blocks = XCNEWVEC (basic_block, loop->num_nodes);
 882   visited = BITMAP_ALLOC (NULL);
 883
 884   bb = loop->header;
 885   while (i < loop->num_nodes)
 886     {
 887       edge e;
 888       edge_iterator ei;
 889
 890       if (!bitmap_bit_p (visited, bb->index))
 891         {
 892           /* This basic block is now visited */
 893           bitmap_set_bit (visited, bb->index);
 894           blocks[i++] = bb;
 895         }
 896
 897       FOR_EACH_EDGE (e, ei, bb->succs)
 898         {
 899           if (flow_bb_inside_loop_p (loop, e->dest))
 900             {
 901               if (!bitmap_bit_p (visited, e->dest->index))
 902                 {
 903                   bitmap_set_bit (visited, e->dest->index);
 904                   blocks[i++] = e->dest;
 905                 }
 906             }
 907         }
 908
 909       gcc_assert (i >= vc);
 910
 911       bb = blocks[vc++];
 912     }
 913
 914   BITMAP_FREE (visited);
 915   return blocks;
 916 }
 917
 918 /* Gets exit edges of a LOOP, returning their number in N_EDGES.  */
 919 edge *
 920 get_loop_exit_edges (const struct loop *loop, unsigned int *num_edges)
 921 {
 922   edge *edges, e;
 923   unsigned i, n;
 924   basic_block * body;
 925   edge_iterator ei;
 926
 927   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
 928
 929   body = get_loop_body (loop);
 930   n = 0;
 931   for (i = 0; i < loop->num_nodes; i++)
 932     FOR_EACH_EDGE (e, ei, body[i]->succs)
 933       if (!flow_bb_inside_loop_p (loop, e->dest))
 934         n++;
 935   edges = XNEWVEC (edge, n);
 936   *num_edges = n;
 937   n = 0;
 938   for (i = 0; i < loop->num_nodes; i++)
 939     FOR_EACH_EDGE (e, ei, body[i]->succs)
 940       if (!flow_bb_inside_loop_p (loop, e->dest))
 941         edges[n++] = e;
 942   free (body);
 943
 944   return edges;
 945 }
 946
 947 /* Counts the number of conditional branches inside LOOP.  */
 948
 949 unsigned
 950 num_loop_branches (const struct loop *loop)
 951 {
 952   unsigned i, n;
 953   basic_block * body;
 954
 955   gcc_assert (loop->latch != EXIT_BLOCK_PTR);
 956
 957   body = get_loop_body (loop);
 958   n = 0;
 959   for (i = 0; i < loop->num_nodes; i++)
 960     if (EDGE_COUNT (body[i]->succs) >= 2)
 961       n++;
 962   free (body);
 963
 964   return n;
 965 }
 966
 967 /* Adds basic block BB to LOOP.  */
 968 void
 969 add_bb_to_loop (basic_block bb, struct loop *loop)
 970 {
 971    int i;
 972
 973    bb->loop_father = loop;
 974    bb->loop_depth = loop->depth;
 975    loop->num_nodes++;
 976    for (i = 0; i < loop->depth; i++)
 977      loop->pred[i]->num_nodes++;
 978  }
 979
 980 /* Remove basic block BB from loops.  */
 981 void
 982 remove_bb_from_loops (basic_block bb)
 983 {
 984    int i;
 985    struct loop *loop = bb->loop_father;
 986
 987    loop->num_nodes--;
 988    for (i = 0; i < loop->depth; i++)
 989      loop->pred[i]->num_nodes--;
 990    bb->loop_father = NULL;
 991    bb->loop_depth = 0;
 992 }
 993
 994 /* Finds nearest common ancestor in loop tree for given loops.  */
 995 struct loop *
 996 find_common_loop (struct loop *loop_s, struct loop *loop_d)
 997 {
 998   if (!loop_s) return loop_d;
 999   if (!loop_d) return loop_s;
1000
1001   if (loop_s->depth < loop_d->depth)
1002     loop_d = loop_d->pred[loop_s->depth];
1003   else if (loop_s->depth > loop_d->depth)
1004     loop_s = loop_s->pred[loop_d->depth];
1005
1006   while (loop_s != loop_d)
1007     {
1008       loop_s = loop_s->outer;
1009       loop_d = loop_d->outer;
1010     }
1011   return loop_s;
1012 }
1013
1014 /* Cancels the LOOP; it must be innermost one.  */
1015 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 }