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