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