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