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                                                       const sbitmap *));
  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         sbitmap_vector_free (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      const sbitmap *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           && ! TEST_BIT (dom[node->index], header->index))
 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   sbitmap *dom;
 649   basic_block header;
 650   edge e;
 651
 652   /* Compute the dominators.  */
 653   dom = sbitmap_vector_alloc (last_basic_block, last_basic_block);
 654   calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
 655
 656   alloc_aux_for_blocks (sizeof (int));
 657   alloc_aux_for_edges (sizeof (int));
 658
 659   /* Split blocks so that each loop has only single latch.  */
 660   FOR_EACH_BB (header)
 661     {
 662       int num_latches = 0;
 663       int have_abnormal_edge = 0;
 664
 665       for (e = header->pred; e; e = e->pred_next)
 666         {
 667           basic_block latch = e->src;
 668
 669           if (e->flags & EDGE_ABNORMAL)
 670             have_abnormal_edge = 1;
 671
 672           if (latch != ENTRY_BLOCK_PTR
 673               && TEST_BIT (dom[latch->index], header->index))
 674             {
 675               num_latches++;
 676               LATCH_EDGE (e) = 1;
 677             }
 678         }
 679       if (have_abnormal_edge)
 680         HEADER_BLOCK (header) = 0;
 681       else
 682         HEADER_BLOCK (header) = num_latches;
 683     }
 684
 685   if (HEADER_BLOCK (ENTRY_BLOCK_PTR->succ->dest))
 686     {
 687       basic_block bb;
 688
 689       /* We could not redirect edges freely here. On the other hand,
 690          we can simply split the edge from entry block.  */
 691       bb = split_edge (ENTRY_BLOCK_PTR->succ);
 692
 693       alloc_aux_for_edge (bb->succ, sizeof (int));
 694       LATCH_EDGE (bb->succ) = 0;
 695       alloc_aux_for_block (bb, sizeof (int));
 696       HEADER_BLOCK (bb) = 0;
 697     }
 698
 699   FOR_EACH_BB (header)
 700     {
 701       int num_latch;
 702       int want_join_latch;
 703       int max_freq, is_heavy;
 704       edge heavy;
 705
 706       if (!HEADER_BLOCK (header))
 707         continue;
 708
 709       num_latch = HEADER_BLOCK (header);
 710
 711       want_join_latch = (num_latch > 1);
 712
 713       if (!want_join_latch)
 714         continue;
 715
 716       /* Find a heavy edge.  */
 717       is_heavy = 1;
 718       heavy = NULL;
 719       max_freq = 0;
 720       for (e = header->pred; e; e = e->pred_next)
 721         if (LATCH_EDGE (e) &&
 722             EDGE_FREQUENCY (e) > max_freq)
 723           max_freq = EDGE_FREQUENCY (e);
 724       for (e = header->pred; e; e = e->pred_next)
 725         if (LATCH_EDGE (e) &&
 726             EDGE_FREQUENCY (e) >= max_freq / HEAVY_EDGE_RATIO)
 727           {
 728             if (heavy)
 729               {
 730                 is_heavy = 0;
 731                 break;
 732               }
 733             else
 734               heavy = e;
 735           }
 736
 737       if (is_heavy)
 738         {
 739           basic_block new_header =
 740             make_forwarder_block (header, true, true, heavy, 0);
 741           if (num_latch > 2)
 742             make_forwarder_block (new_header, true, false, NULL, 1);
 743         }
 744       else
 745         make_forwarder_block (header, true, false, NULL, 1);
 746     }
 747
 748   free_aux_for_blocks ();
 749   free_aux_for_edges ();
 750   sbitmap_vector_free (dom);
 751 }
 752
 753 /* Find all the natural loops in the function and save in LOOPS structure and
 754    recalculate loop_depth information in basic block structures.  FLAGS
 755    controls which loop information is collected.  Return the number of natural
 756    loops found.  */
 757
 758 int
 759 flow_loops_find (loops, flags)
 760      struct loops *loops;
 761      int flags;
 762 {
 763   int i;
 764   int b;
 765   int num_loops;
 766   edge e;
 767   sbitmap headers;
 768   sbitmap *dom;
 769   int *dfs_order;
 770   int *rc_order;
 771   basic_block header, 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   loops->cfg.dom = dom = sbitmap_vector_alloc (last_basic_block, last_basic_block);
 794   calculate_dominance_info (NULL, dom, CDI_DOMINATORS);
 795
 796   /* Count the number of loop headers.  This should be the
 797      same as the number of natural loops.  */
 798   headers = sbitmap_alloc (last_basic_block);
 799   sbitmap_zero (headers);
 800
 801   num_loops = 0;
 802   FOR_EACH_BB (header)
 803     {
 804       int more_latches = 0;
 805
 806       header->loop_depth = 0;
 807
 808       for (e = header->pred; e; e = e->pred_next)
 809         {
 810           basic_block latch = e->src;
 811
 812           if (e->flags & EDGE_ABNORMAL)
 813             {
 814               if (more_latches)
 815                 {
 816                   RESET_BIT (headers, header->index);
 817                   num_loops--;
 818                 }
 819               break;
 820             }
 821
 822           /* Look for back edges where a predecessor is dominated
 823              by this block.  A natural loop has a single entry
 824              node (header) that dominates all the nodes in the
 825              loop.  It also has single back edge to the header
 826              from a latch node.  */
 827           if (latch != ENTRY_BLOCK_PTR && TEST_BIT (dom[latch->index],
 828                                                     header->index))
 829             {
 830               /* Shared headers should be eliminated by now.  */
 831               if (more_latches)
 832                 abort ();
 833               more_latches = 1;
 834               SET_BIT (headers, header->index);
 835               num_loops++;
 836             }
 837         }
 838     }
 839
 840   /* Allocate loop structures.  */
 841   loops->parray = (struct loop **) xcalloc (num_loops + 1, sizeof (struct loop *));
 842
 843   /* Dummy loop containing whole function.  */
 844   loops->parray[0] = xcalloc (1, sizeof (struct loop));
 845   loops->parray[0]->next = NULL;
 846   loops->parray[0]->inner = NULL;
 847   loops->parray[0]->outer = NULL;
 848   loops->parray[0]->depth = 0;
 849   loops->parray[0]->pred = NULL;
 850   loops->parray[0]->num_nodes = n_basic_blocks + 2;
 851   loops->parray[0]->latch = EXIT_BLOCK_PTR;
 852   loops->parray[0]->header = ENTRY_BLOCK_PTR;
 853   ENTRY_BLOCK_PTR->loop_father = loops->parray[0];
 854   EXIT_BLOCK_PTR->loop_father = loops->parray[0];
 855
 856   loops->tree_root = loops->parray[0];
 857
 858   /* Find and record information about all the natural loops
 859      in the CFG.  */
 860   loops->num = 1;
 861   FOR_EACH_BB (bb)
 862     bb->loop_father = loops->tree_root;
 863
 864   if (num_loops)
 865     {
 866       /* Compute depth first search order of the CFG so that outer
 867          natural loops will be found before inner natural loops.  */
 868       dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
 869       rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
 870       flow_depth_first_order_compute (dfs_order, rc_order);
 871
 872       /* Save CFG derived information to avoid recomputing it.  */
 873       loops->cfg.dom = dom;
 874       loops->cfg.dfs_order = dfs_order;
 875       loops->cfg.rc_order = rc_order;
 876
 877       num_loops = 1;
 878
 879       for (b = 0; b < n_basic_blocks; b++)
 880         {
 881           struct loop *loop;
 882
 883           /* Search the nodes of the CFG in reverse completion order
 884              so that we can find outer loops first.  */
 885           if (!TEST_BIT (headers, rc_order[b]))
 886             continue;
 887
 888           header = BASIC_BLOCK (rc_order[b]);
 889
 890           loop = loops->parray[num_loops] = xcalloc (1, sizeof (struct loop));
 891
 892           loop->header = header;
 893           loop->num = num_loops;
 894           num_loops++;
 895
 896           /* Look for the latch for this header block.  */
 897           for (e = header->pred; e; e = e->pred_next)
 898             {
 899               basic_block latch = e->src;
 900
 901               if (latch != ENTRY_BLOCK_PTR
 902                   && TEST_BIT (dom[latch->index], header->index))
 903                 {
 904                   loop->latch = latch;
 905                   break;
 906                 }
 907             }
 908
 909           flow_loop_tree_node_add (header->loop_father, loop);
 910           loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
 911         }
 912
 913       sbitmap_free (headers);
 914
 915       /* Assign the loop nesting depth and enclosed loop level for each
 916          loop.  */
 917       loops->levels = flow_loops_level_compute (loops);
 918
 919       /* Scan the loops.  */
 920       for (i = 1; i < num_loops; i++)
 921         flow_loop_scan (loops, loops->parray[i], flags);
 922
 923       loops->num = num_loops;
 924     }
 925   else
 926     {
 927       loops->cfg.dom = NULL;
 928       sbitmap_vector_free (dom);
 929     }
 930 #ifdef ENABLE_CHECKING
 931   verify_flow_info ();
 932   verify_loop_structure (loops, 0);
 933 #endif
 934
 935   return loops->num;
 936 }
 937
 938 /* Update the information regarding the loops in the CFG
 939    specified by LOOPS.  */
 940
 941 int
 942 flow_loops_update (loops, flags)
 943      struct loops *loops;
 944      int flags;
 945 {
 946   /* One day we may want to update the current loop data.  For now
 947      throw away the old stuff and rebuild what we need.  */
 948   if (loops->parray)
 949     flow_loops_free (loops);
 950
 951   return flow_loops_find (loops, flags);
 952 }
 953
 954 /* Return non-zero if basic block BB belongs to LOOP.  */
 955 bool
 956 flow_bb_inside_loop_p (loop, bb)
 957      const struct loop *loop;
 958      const basic_block bb;
 959 {
 960   struct loop *source_loop;
 961
 962   if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
 963     return 0;
 964
 965   source_loop = bb->loop_father;
 966   return loop == source_loop || flow_loop_nested_p (loop, source_loop);
 967 }
 968
 969 /* Return non-zero if edge E enters header of LOOP from outside of LOOP.  */
 970
 971 bool
 972 flow_loop_outside_edge_p (loop, e)
 973      const struct loop *loop;
 974      edge e;
 975 {
 976   if (e->dest != loop->header)
 977     abort ();
 978   return !flow_bb_inside_loop_p (loop, e->src);
 979 }
 980
 981 /* Enumeration predicate for get_loop_body.  */
 982 static bool
 983 glb_enum_p (bb, glb_header)
 984      basic_block bb;
 985      void *glb_header;
 986 {
 987   return bb != (basic_block) glb_header;
 988 }
 989
 990 /* Gets basic blocks of a loop.  */
 991 basic_block *
 992 get_loop_body (loop)
 993      const struct loop *loop;
 994 {
 995   basic_block *tovisit, bb;
 996   int tv = 0;
 997
 998   if (!loop->num_nodes)
 999     abort ();
1000
1001   tovisit = xcalloc (loop->num_nodes, sizeof (basic_block));
1002   tovisit[tv++] = loop->header;
1003
1004   if (loop->latch == EXIT_BLOCK_PTR)
1005     {
1006       /* There may be blocks unreachable from EXIT_BLOCK.  */
1007       if (loop->num_nodes != n_basic_blocks + 2)
1008         abort ();
1009       FOR_EACH_BB (bb)
1010         tovisit[tv++] = bb;
1011       tovisit[tv++] = EXIT_BLOCK_PTR;
1012     }
1013   else if (loop->latch != loop->header)
1014     {
1015       tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p,
1016                                tovisit + 1, loop->num_nodes - 1,
1017                                loop->header) + 1;
1018     }
1019
1020   if (tv != loop->num_nodes)
1021     abort ();
1022   return tovisit;
1023 }
1024
1025 /* Adds basic block BB to LOOP.  */
1026 void
1027 add_bb_to_loop (bb, loop)
1028      basic_block bb;
1029      struct loop *loop;
1030  {
1031    int i;
1032
1033    bb->loop_father = loop;
1034    bb->loop_depth = loop->depth;
1035    loop->num_nodes++;
1036    for (i = 0; i < loop->depth; i++)
1037      loop->pred[i]->num_nodes++;
1038  }
1039
1040 /* Remove basic block BB from loops.  */
1041 void
1042 remove_bb_from_loops (bb)
1043      basic_block bb;
1044  {
1045    int i;
1046    struct loop *loop = bb->loop_father;
1047
1048    loop->num_nodes--;
1049    for (i = 0; i < loop->depth; i++)
1050      loop->pred[i]->num_nodes--;
1051    bb->loop_father = NULL;
1052    bb->loop_depth = 0;
1053  }
1054
1055 /* Finds nearest common ancestor in loop tree for given loops.  */
1056 struct loop *
1057 find_common_loop (loop_s, loop_d)
1058     struct loop *loop_s;
1059     struct loop *loop_d;
1060 {
1061   if (!loop_s) return loop_d;
1062   if (!loop_d) return loop_s;
1063
1064   if (loop_s->depth < loop_d->depth)
1065     loop_d = loop_d->pred[loop_s->depth];
1066   else if (loop_s->depth > loop_d->depth)
1067     loop_s = loop_s->pred[loop_d->depth];
1068
1069   while (loop_s != loop_d)
1070     {
1071       loop_s = loop_s->outer;
1072       loop_d = loop_d->outer;
1073     }
1074   return loop_s;
1075 }
1076
1077 /* Checks that LOOPS are allright:
1078      -- sizes of loops are allright
1079      -- results of get_loop_body really belong to the loop
1080      -- loop header have just single entry edge and single latch edge
1081      -- loop latches have only single successor that is header of their loop
1082   */
1083 void
1084 verify_loop_structure (loops, flags)
1085      struct loops *loops;
1086      int flags;
1087 {
1088   int *sizes, i, j;
1089   basic_block *bbs, bb;
1090   struct loop *loop;
1091   int err = 0;
1092
1093   /* Check sizes.  */
1094   sizes = xcalloc (loops->num, sizeof (int));
1095   sizes[0] = 2;
1096
1097   FOR_EACH_BB (bb)
1098     for (loop = bb->loop_father; loop; loop = loop->outer)
1099       sizes[loop->num]++;
1100
1101   for (i = 0; i < loops->num; i++)
1102     {
1103       if (!loops->parray[i])
1104         continue;
1105
1106       if (loops->parray[i]->num_nodes != sizes[i])
1107         {
1108           error ("Size of loop %d should be %d, not %d.",
1109                    i, sizes[i], loops->parray[i]->num_nodes);
1110           err = 1;
1111         }
1112     }
1113
1114   free (sizes);
1115
1116   /* Check get_loop_body.  */
1117   for (i = 1; i < loops->num; i++)
1118     {
1119       loop = loops->parray[i];
1120       if (!loop)
1121         continue;
1122       bbs = get_loop_body (loop);
1123
1124       for (j = 0; j < loop->num_nodes; j++)
1125         if (!flow_bb_inside_loop_p (loop, bbs[j]))
1126           {
1127             error ("Bb %d do not belong to loop %d.",
1128                     bbs[j]->index, i);
1129             err = 1;
1130           }
1131       free (bbs);
1132     }
1133
1134   /* Check headers and latches.  */
1135   for (i = 1; i < loops->num; i++)
1136     {
1137       loop = loops->parray[i];
1138       if (!loop)
1139         continue;
1140
1141       if ((flags & VLS_EXPECT_PREHEADERS)
1142           && (!loop->header->pred->pred_next
1143               || loop->header->pred->pred_next->pred_next))
1144         {
1145           error ("Loop %d's header does not have exactly 2 entries.", i);
1146           err = 1;
1147         }
1148       if (flags & VLS_EXPECT_SIMPLE_LATCHES)
1149         {
1150           if (!loop->latch->succ
1151               || loop->latch->succ->succ_next)
1152             {
1153               error ("Loop %d's latch does not have exactly 1 successor.", i);
1154               err = 1;
1155             }
1156           if (loop->latch->succ->dest != loop->header)
1157             {
1158               error ("Loop %d's latch does not have header as successor.", i);
1159               err = 1;
1160             }
1161           if (loop->latch->loop_father != loop)
1162             {
1163               error ("Loop %d's latch does not belong directly to it.", i);
1164               err = 1;
1165             }
1166         }
1167       if (loop->header->loop_father != loop)
1168         {
1169           error ("Loop %d's header does not belong directly to it.", i);
1170           err = 1;
1171         }
1172     }
1173
1174   if (err)
1175     abort ();
1176 }
1177
1178 /* Returns latch edge of LOOP.  */
1179 edge
1180 loop_latch_edge (loop)
1181      struct loop *loop;
1182 {
1183   edge e;
1184
1185   for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next)
1186     continue;
1187
1188   return e;
1189 }
1190
1191 /* Returns preheader edge of LOOP.  */
1192 edge
1193 loop_preheader_edge (loop)
1194      struct loop *loop;
1195 {
1196   edge e;
1197
1198   for (e = loop->header->pred; e->src == loop->latch; e = e->pred_next)
1199     continue;
1200
1201   return e;
1202 }
1203