gcc/cfgloop.c

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