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 "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
  30 /* Ratio of frequencies of edges so that one of more latch edges is
  31    considered to belong to inner loop with same header.  */
  32 #define HEAVY_EDGE_RATIO 8
  33
  34 static void flow_loops_cfg_dump         PARAMS ((const struct loops *,
  35                                                  FILE *));
  36 static void flow_loop_entry_edges_find  PARAMS ((struct loop *));
  37 static void flow_loop_exit_edges_find   PARAMS ((struct loop *));
  38 static int flow_loop_nodes_find         PARAMS ((basic_block, struct loop *));
  39 static void flow_loop_pre_header_scan   PARAMS ((struct loop *));
  40 static basic_block flow_loop_pre_header_find PARAMS ((basic_block,
  41                                                       dominance_info));
  42 static int flow_loop_level_compute      PARAMS ((struct loop *));
  43 static int flow_loops_level_compute     PARAMS ((struct loops *));
  44 static basic_block make_forwarder_block PARAMS ((basic_block, int, int,
  45                                                  edge, int));
  46 static void canonicalize_loop_headers   PARAMS ((void));
  47 static bool glb_enum_p PARAMS ((basic_block, void *));
  48 static void redirect_edge_with_latch_update PARAMS ((edge, basic_block));
  49 static void flow_loop_free PARAMS ((struct loop *));
  50 \f
  51 /* Dump loop related CFG information.  */
  52
  53 static void
  54 flow_loops_cfg_dump (loops, file)
  55      const struct loops *loops;
  56      FILE *file;
  57 {
  58   int i;
  59   basic_block bb;
  60
  61   if (! loops->num || ! file || ! loops->cfg.dom)
  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 (outer, loop)
  99      const struct loop *outer;
 100      const struct loop *loop;
 101 {
 102   return loop->depth > outer->depth
 103          && loop->pred[outer->depth] == outer;
 104 }
 105
 106 /* Dump the loop information specified by LOOP to the stream FILE
 107    using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
 108
 109 void
 110 flow_loop_dump (loop, file, loop_dump_aux, verbose)
 111      const struct loop *loop;
 112      FILE *file;
 113      void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
 114      int verbose;
 115 {
 116   basic_block *bbs;
 117   int i;
 118
 119   if (! loop || ! loop->header)
 120     return;
 121
 122   fprintf (file, ";;\n;; Loop %d:%s\n", loop->num,
 123              loop->invalid ? " invalid" : "");
 124
 125   fprintf (file, ";;  header %d, latch %d, pre-header %d\n",
 126            loop->header->index, loop->latch->index,
 127            loop->pre_header ? loop->pre_header->index : -1);
 128   fprintf (file, ";;  depth %d, level %d, outer %ld\n",
 129            loop->depth, loop->level,
 130            (long) (loop->outer ? loop->outer->num : -1));
 131
 132   if (loop->pre_header_edges)
 133     flow_edge_list_print (";;  pre-header edges", loop->pre_header_edges,
 134                           loop->num_pre_header_edges, file);
 135
 136   flow_edge_list_print (";;  entry edges", loop->entry_edges,
 137                         loop->num_entries, file);
 138   fprintf (file, ";;  nodes:");
 139   bbs = get_loop_body (loop);
 140   for (i = 0; i < loop->num_nodes; i++)
 141     fprintf (file, " %d", bbs[i]->index);
 142   free (bbs);
 143   fprintf (file, "\n");
 144   flow_edge_list_print (";;  exit edges", loop->exit_edges,
 145                         loop->num_exits, file);
 146
 147   if (loop_dump_aux)
 148     loop_dump_aux (loop, file, verbose);
 149 }
 150
 151 /* Dump the loop information specified by LOOPS to the stream FILE,
 152    using auxiliary dump callback function LOOP_DUMP_AUX if non null.  */
 153
 154 void
 155 flow_loops_dump (loops, file, loop_dump_aux, verbose)
 156      const struct loops *loops;
 157      FILE *file;
 158      void (*loop_dump_aux) PARAMS((const struct loop *, FILE *, int));
 159      int verbose;
 160 {
 161   int i;
 162   int num_loops;
 163
 164   num_loops = loops->num;
 165   if (! num_loops || ! file)
 166     return;
 167
 168   fprintf (file, ";; %d loops found, %d levels\n",
 169            num_loops, loops->levels);
 170
 171   for (i = 0; i < num_loops; i++)
 172     {
 173       struct loop *loop = loops->parray[i];
 174
 175       if (!loop)
 176         continue;
 177
 178       flow_loop_dump (loop, file, loop_dump_aux, verbose);
 179     }
 180
 181   if (verbose)
 182     flow_loops_cfg_dump (loops, file);
 183 }
 184
 185 /* Free data allocated for LOOP.  */
 186 static void
 187 flow_loop_free (loop)
 188      struct loop *loop;
 189 {
 190   if (loop->pre_header_edges)
 191     free (loop->pre_header_edges);
 192   if (loop->entry_edges)
 193     free (loop->entry_edges);
 194   if (loop->exit_edges)
 195     free (loop->exit_edges);
 196   if (loop->pred)
 197     free (loop->pred);
 198   free (loop);
 199 }
 200
 201 /* Free all the memory allocated for LOOPS.  */
 202
 203 void
 204 flow_loops_free (loops)
 205      struct loops *loops;
 206 {
 207   if (loops->parray)
 208     {
 209       int i;
 210
 211       if (! loops->num)
 212         abort ();
 213
 214       /* Free the loop descriptors.  */
 215       for (i = 0; i < loops->num; i++)
 216         {
 217           struct loop *loop = loops->parray[i];
 218
 219           if (!loop)
 220             continue;
 221
 222           flow_loop_free (loop);
 223         }
 224
 225       free (loops->parray);
 226       loops->parray = NULL;
 227
 228       if (loops->cfg.dom)
 229         free_dominance_info (loops->cfg.dom);
 230
 231       if (loops->cfg.dfs_order)
 232         free (loops->cfg.dfs_order);
 233       if (loops->cfg.rc_order)
 234         free (loops->cfg.rc_order);
 235
 236     }
 237 }
 238
 239 /* Find the entry edges into the LOOP.  */
 240
 241 static void
 242 flow_loop_entry_edges_find (loop)
 243      struct loop *loop;
 244 {
 245   edge e;
 246   int num_entries;
 247
 248   num_entries = 0;
 249   for (e = loop->header->pred; e; e = e->pred_next)
 250     {
 251       if (flow_loop_outside_edge_p (loop, e))
 252         num_entries++;
 253     }
 254
 255   if (! num_entries)
 256     abort ();
 257
 258   loop->entry_edges = (edge *) xmalloc (num_entries * sizeof (edge *));
 259
 260   num_entries = 0;
 261   for (e = loop->header->pred; e; e = e->pred_next)
 262     {
 263       if (flow_loop_outside_edge_p (loop, e))
 264         loop->entry_edges[num_entries++] = e;
 265     }
 266
 267   loop->num_entries = num_entries;
 268 }
 269
 270 /* Find the exit edges from the LOOP.  */
 271
 272 static void
 273 flow_loop_exit_edges_find (loop)
 274      struct loop *loop;
 275 {
 276   edge e;
 277   basic_block node, *bbs;
 278   int 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 = (edge *) 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 (header, loop)
 330      basic_block header;
 331      struct loop *loop;
 332 {
 333   basic_block *stack;
 334   int sp;
 335   int num_nodes = 1;
 336
 337   header->loop_father = loop;
 338   header->loop_depth = loop->depth;
 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       /* If we have an abnormal predecessor, do not consider the
 808          loop (not worth the problems).  */
 809       for (e = header->pred; e; e = e->pred_next)
 810         if (e->flags & EDGE_ABNORMAL)
 811           break;
 812       if (e)
 813         continue;
 814
 815       for (e = header->pred; e; e = e->pred_next)
 816         {
 817           basic_block latch = e->src;
 818
 819           if (e->flags & EDGE_ABNORMAL)
 820             abort ();
 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 && dominated_by_p (dom, latch, header))
 828             {
 829               /* Shared headers should be eliminated by now.  */
 830               if (more_latches)
 831                 abort ();
 832               more_latches = 1;
 833               SET_BIT (headers, header->index);
 834               num_loops++;
 835             }
 836         }
 837     }
 838
 839   /* Allocate loop structures.  */
 840   loops->parray = (struct loop **) xcalloc (num_loops + 1, sizeof (struct loop *));
 841
 842   /* Dummy loop containing whole function.  */
 843   loops->parray[0] = xcalloc (1, sizeof (struct loop));
 844   loops->parray[0]->next = NULL;
 845   loops->parray[0]->inner = NULL;
 846   loops->parray[0]->outer = NULL;
 847   loops->parray[0]->depth = 0;
 848   loops->parray[0]->pred = NULL;
 849   loops->parray[0]->num_nodes = n_basic_blocks + 2;
 850   loops->parray[0]->latch = EXIT_BLOCK_PTR;
 851   loops->parray[0]->header = ENTRY_BLOCK_PTR;
 852   ENTRY_BLOCK_PTR->loop_father = loops->parray[0];
 853   EXIT_BLOCK_PTR->loop_father = loops->parray[0];
 854
 855   loops->tree_root = loops->parray[0];
 856
 857   /* Find and record information about all the natural loops
 858      in the CFG.  */
 859   loops->num = 1;
 860   FOR_EACH_BB (bb)
 861     bb->loop_father = loops->tree_root;
 862
 863   if (num_loops)
 864     {
 865       /* Compute depth first search order of the CFG so that outer
 866          natural loops will be found before inner natural loops.  */
 867       dfs_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
 868       rc_order = (int *) xmalloc (n_basic_blocks * sizeof (int));
 869       flow_depth_first_order_compute (dfs_order, rc_order);
 870
 871       /* Save CFG derived information to avoid recomputing it.  */
 872       loops->cfg.dom = dom;
 873       loops->cfg.dfs_order = dfs_order;
 874       loops->cfg.rc_order = rc_order;
 875
 876       num_loops = 1;
 877
 878       for (b = 0; b < n_basic_blocks; b++)
 879         {
 880           struct loop *loop;
 881
 882           /* Search the nodes of the CFG in reverse completion order
 883              so that we can find outer loops first.  */
 884           if (!TEST_BIT (headers, rc_order[b]))
 885             continue;
 886
 887           header = BASIC_BLOCK (rc_order[b]);
 888
 889           loop = loops->parray[num_loops] = xcalloc (1, sizeof (struct loop));
 890
 891           loop->header = header;
 892           loop->num = num_loops;
 893           num_loops++;
 894
 895           /* Look for the latch for this header block.  */
 896           for (e = header->pred; e; e = e->pred_next)
 897             {
 898               basic_block latch = e->src;
 899
 900               if (latch != ENTRY_BLOCK_PTR
 901                   && dominated_by_p (dom, latch, header))
 902                 {
 903                   loop->latch = latch;
 904                   break;
 905                 }
 906             }
 907
 908           flow_loop_tree_node_add (header->loop_father, loop);
 909           loop->num_nodes = flow_loop_nodes_find (loop->header, loop);
 910         }
 911
 912       sbitmap_free (headers);
 913
 914       /* Assign the loop nesting depth and enclosed loop level for each
 915          loop.  */
 916       loops->levels = flow_loops_level_compute (loops);
 917
 918       /* Scan the loops.  */
 919       for (i = 1; i < num_loops; i++)
 920         flow_loop_scan (loops, loops->parray[i], flags);
 921
 922       loops->num = num_loops;
 923     }
 924   else
 925     {
 926       loops->cfg.dom = NULL;
 927       free_dominance_info (dom);
 928     }
 929 #ifdef ENABLE_CHECKING
 930   verify_flow_info ();
 931   verify_loop_structure (loops, 0);
 932 #endif
 933
 934   return loops->num;
 935 }
 936
 937 /* Update the information regarding the loops in the CFG
 938    specified by LOOPS.  */
 939
 940 int
 941 flow_loops_update (loops, flags)
 942      struct loops *loops;
 943      int flags;
 944 {
 945   /* One day we may want to update the current loop data.  For now
 946      throw away the old stuff and rebuild what we need.  */
 947   if (loops->parray)
 948     flow_loops_free (loops);
 949
 950   return flow_loops_find (loops, flags);
 951 }
 952
 953 /* Return nonzero if basic block BB belongs to LOOP.  */
 954 bool
 955 flow_bb_inside_loop_p (loop, bb)
 956      const struct loop *loop;
 957      const basic_block bb;
 958 {
 959   struct loop *source_loop;
 960
 961   if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
 962     return 0;
 963
 964   source_loop = bb->loop_father;
 965   return loop == source_loop || flow_loop_nested_p (loop, source_loop);
 966 }
 967
 968 /* Return nonzero if edge E enters header of LOOP from outside of LOOP.  */
 969
 970 bool
 971 flow_loop_outside_edge_p (loop, e)
 972      const struct loop *loop;
 973      edge e;
 974 {
 975   if (e->dest != loop->header)
 976     abort ();
 977   return !flow_bb_inside_loop_p (loop, e->src);
 978 }
 979
 980 /* Enumeration predicate for get_loop_body.  */
 981 static bool
 982 glb_enum_p (bb, glb_header)
 983      basic_block bb;
 984      void *glb_header;
 985 {
 986   return bb != (basic_block) glb_header;
 987 }
 988
 989 /* Gets basic blocks of a loop.  */
 990 basic_block *
 991 get_loop_body (loop)
 992      const struct loop *loop;
 993 {
 994   basic_block *tovisit, bb;
 995   int tv = 0;
 996
 997   if (!loop->num_nodes)
 998     abort ();
 999
1000   tovisit = xcalloc (loop->num_nodes, sizeof (basic_block));
1001   tovisit[tv++] = loop->header;
1002
1003   if (loop->latch == EXIT_BLOCK_PTR)
1004     {
1005       /* There may be blocks unreachable from EXIT_BLOCK.  */
1006       if (loop->num_nodes != n_basic_blocks + 2)
1007         abort ();
1008       FOR_EACH_BB (bb)
1009         tovisit[tv++] = bb;
1010       tovisit[tv++] = EXIT_BLOCK_PTR;
1011     }
1012   else if (loop->latch != loop->header)
1013     {
1014       tv = dfs_enumerate_from (loop->latch, 1, glb_enum_p,
1015                                tovisit + 1, loop->num_nodes - 1,
1016                                loop->header) + 1;
1017     }
1018
1019   if (tv != loop->num_nodes)
1020     abort ();
1021   return tovisit;
1022 }
1023
1024 /* Adds basic block BB to LOOP.  */
1025 void
1026 add_bb_to_loop (bb, loop)
1027      basic_block bb;
1028      struct loop *loop;
1029  {
1030    int i;
1031
1032    bb->loop_father = loop;
1033    bb->loop_depth = loop->depth;
1034    loop->num_nodes++;
1035    for (i = 0; i < loop->depth; i++)
1036      loop->pred[i]->num_nodes++;
1037  }
1038
1039 /* Remove basic block BB from loops.  */
1040 void
1041 remove_bb_from_loops (bb)
1042      basic_block bb;
1043  {
1044    int i;
1045    struct loop *loop = bb->loop_father;
1046
1047    loop->num_nodes--;
1048    for (i = 0; i < loop->depth; i++)
1049      loop->pred[i]->num_nodes--;
1050    bb->loop_father = NULL;
1051    bb->loop_depth = 0;
1052  }
1053
1054 /* Finds nearest common ancestor in loop tree for given loops.  */
1055 struct loop *
1056 find_common_loop (loop_s, loop_d)
1057     struct loop *loop_s;
1058     struct loop *loop_d;
1059 {
1060   if (!loop_s) return loop_d;
1061   if (!loop_d) return loop_s;
1062
1063   if (loop_s->depth < loop_d->depth)
1064     loop_d = loop_d->pred[loop_s->depth];
1065   else if (loop_s->depth > loop_d->depth)
1066     loop_s = loop_s->pred[loop_d->depth];
1067
1068   while (loop_s != loop_d)
1069     {
1070       loop_s = loop_s->outer;
1071       loop_d = loop_d->outer;
1072     }
1073   return loop_s;
1074 }
1075
1076 /* Checks that LOOPS are allright:
1077      -- sizes of loops are allright
1078      -- results of get_loop_body really belong to the loop
1079      -- loop header have just single entry edge and single latch edge
1080      -- loop latches have only single successor that is header of their loop
1081   */
1082 void
1083 verify_loop_structure (loops, flags)
1084      struct loops *loops;
1085      int flags;
1086 {
1087   int *sizes, i, j;
1088   basic_block *bbs, bb;
1089   struct loop *loop;
1090   int err = 0;
1091
1092   /* Check sizes.  */
1093   sizes = xcalloc (loops->num, sizeof (int));
1094   sizes[0] = 2;
1095
1096   FOR_EACH_BB (bb)
1097     for (loop = bb->loop_father; loop; loop = loop->outer)
1098       sizes[loop->num]++;
1099
1100   for (i = 0; i < loops->num; i++)
1101     {
1102       if (!loops->parray[i])
1103         continue;
1104
1105       if (loops->parray[i]->num_nodes != sizes[i])
1106         {
1107           error ("Size of loop %d should be %d, not %d.",
1108                    i, sizes[i], loops->parray[i]->num_nodes);
1109           err = 1;
1110         }
1111     }
1112
1113   free (sizes);
1114
1115   /* Check get_loop_body.  */
1116   for (i = 1; i < loops->num; i++)
1117     {
1118       loop = loops->parray[i];
1119       if (!loop)
1120         continue;
1121       bbs = get_loop_body (loop);
1122
1123       for (j = 0; j < loop->num_nodes; j++)
1124         if (!flow_bb_inside_loop_p (loop, bbs[j]))
1125           {
1126             error ("Bb %d do not belong to loop %d.",
1127                     bbs[j]->index, i);
1128             err = 1;
1129           }
1130       free (bbs);
1131     }
1132
1133   /* Check headers and latches.  */
1134   for (i = 1; i < loops->num; i++)
1135     {
1136       loop = loops->parray[i];
1137       if (!loop)
1138         continue;
1139
1140       if ((flags & VLS_EXPECT_PREHEADERS)
1141           && (!loop->header->pred->pred_next
1142               || loop->header->pred->pred_next->pred_next))
1143         {
1144           error ("Loop %d's header does not have exactly 2 entries.", i);
1145           err = 1;
1146         }
1147       if (flags & VLS_EXPECT_SIMPLE_LATCHES)
1148         {
1149           if (!loop->latch->succ
1150               || loop->latch->succ->succ_next)
1151             {
1152               error ("Loop %d's latch does not have exactly 1 successor.", i);
1153               err = 1;
1154             }
1155           if (loop->latch->succ->dest != loop->header)
1156             {
1157               error ("Loop %d's latch does not have header as successor.", i);
1158               err = 1;
1159             }
1160           if (loop->latch->loop_father != loop)
1161             {
1162               error ("Loop %d's latch does not belong directly to it.", i);
1163               err = 1;
1164             }
1165         }
1166       if (loop->header->loop_father != loop)
1167         {
1168           error ("Loop %d's header does not belong directly to it.", i);
1169           err = 1;
1170         }
1171     }
1172
1173   if (err)
1174     abort ();
1175 }
1176
1177 /* Returns latch edge of LOOP.  */
1178 edge
1179 loop_latch_edge (loop)
1180      struct loop *loop;
1181 {
1182   edge e;
1183
1184   for (e = loop->header->pred; e->src != loop->latch; e = e->pred_next)
1185     continue;
1186
1187   return e;
1188 }
1189
1190 /* Returns preheader edge of LOOP.  */
1191 edge
1192 loop_preheader_edge (loop)
1193      struct loop *loop;
1194 {
1195   edge e;
1196
1197   for (e = loop->header->pred; e->src == loop->latch; e = e->pred_next)
1198     continue;
1199
1200   return e;
1201 }
1202