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