gcc/cfgloop.c

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