gcc/cfgloop.c

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