gcc/cfganal.c

   1 /* Control flow graph analysis code for GNU compiler.
   2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /* This file contains various simple utilities to analyze the CFG.  */
  23 #include "config.h"
  24 #include "system.h"
  25 #include "rtl.h"
  26 #include "hard-reg-set.h"
  27 #include "basic-block.h"
  28 #include "insn-config.h"
  29 #include "recog.h"
  30 #include "toplev.h"
  31 #include "obstack.h"
  32 #include "tm_p.h"
  33
  34 /* Store the data structures necessary for depth-first search.  */
  35 struct depth_first_search_dsS {
  36   /* stack for backtracking during the algorithm */
  37   basic_block *stack;
  38
  39   /* number of edges in the stack.  That is, positions 0, ..., sp-1
  40      have edges.  */
  41   unsigned int sp;
  42
  43   /* record of basic blocks already seen by depth-first search */
  44   sbitmap visited_blocks;
  45 };
  46 typedef struct depth_first_search_dsS *depth_first_search_ds;
  47
  48 static void flow_dfs_compute_reverse_init
  49   PARAMS ((depth_first_search_ds));
  50 static void flow_dfs_compute_reverse_add_bb
  51   PARAMS ((depth_first_search_ds, basic_block));
  52 static basic_block flow_dfs_compute_reverse_execute
  53   PARAMS ((depth_first_search_ds));
  54 static void flow_dfs_compute_reverse_finish
  55   PARAMS ((depth_first_search_ds));
  56 static void remove_fake_successors      PARAMS ((basic_block));
  57 static bool need_fake_edge_p            PARAMS ((rtx));
  58 \f
  59 /* Return true if the block has no effect and only forwards control flow to
  60    its single destination.  */
  61
  62 bool
  63 forwarder_block_p (bb)
  64      basic_block bb;
  65 {
  66   rtx insn;
  67
  68   if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
  69       || !bb->succ || bb->succ->succ_next)
  70     return false;
  71
  72   for (insn = bb->head; insn != bb->end; insn = NEXT_INSN (insn))
  73     if (INSN_P (insn) && active_insn_p (insn))
  74       return false;
  75
  76   return (!INSN_P (insn)
  77           || (GET_CODE (insn) == JUMP_INSN && simplejump_p (insn))
  78           || !active_insn_p (insn));
  79 }
  80
  81 /* Return nonzero if we can reach target from src by falling through.  */
  82
  83 bool
  84 can_fallthru (src, target)
  85      basic_block src, target;
  86 {
  87   rtx insn = src->end;
  88   rtx insn2 = target->head;
  89
  90   if (src->next_bb != target)
  91     return 0;
  92
  93   if (!active_insn_p (insn2))
  94     insn2 = next_active_insn (insn2);
  95
  96   /* ??? Later we may add code to move jump tables offline.  */
  97   return next_active_insn (insn) == insn2;
  98 }
  99 \f
 100 /* Mark the back edges in DFS traversal.
 101    Return non-zero if a loop (natural or otherwise) is present.
 102    Inspired by Depth_First_Search_PP described in:
 103
 104      Advanced Compiler Design and Implementation
 105      Steven Muchnick
 106      Morgan Kaufmann, 1997
 107
 108    and heavily borrowed from flow_depth_first_order_compute.  */
 109
 110 bool
 111 mark_dfs_back_edges ()
 112 {
 113   edge *stack;
 114   int *pre;
 115   int *post;
 116   int sp;
 117   int prenum = 1;
 118   int postnum = 1;
 119   sbitmap visited;
 120   bool found = false;
 121
 122   /* Allocate the preorder and postorder number arrays.  */
 123   pre = (int *) xcalloc (last_basic_block, sizeof (int));
 124   post = (int *) xcalloc (last_basic_block, sizeof (int));
 125
 126   /* Allocate stack for back-tracking up CFG.  */
 127   stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
 128   sp = 0;
 129
 130   /* Allocate bitmap to track nodes that have been visited.  */
 131   visited = sbitmap_alloc (last_basic_block);
 132
 133   /* None of the nodes in the CFG have been visited yet.  */
 134   sbitmap_zero (visited);
 135
 136   /* Push the first edge on to the stack.  */
 137   stack[sp++] = ENTRY_BLOCK_PTR->succ;
 138
 139   while (sp)
 140     {
 141       edge e;
 142       basic_block src;
 143       basic_block dest;
 144
 145       /* Look at the edge on the top of the stack.  */
 146       e = stack[sp - 1];
 147       src = e->src;
 148       dest = e->dest;
 149       e->flags &= ~EDGE_DFS_BACK;
 150
 151       /* Check if the edge destination has been visited yet.  */
 152       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 153         {
 154           /* Mark that we have visited the destination.  */
 155           SET_BIT (visited, dest->index);
 156
 157           pre[dest->index] = prenum++;
 158           if (dest->succ)
 159             {
 160               /* Since the DEST node has been visited for the first
 161                  time, check its successors.  */
 162               stack[sp++] = dest->succ;
 163             }
 164           else
 165             post[dest->index] = postnum++;
 166         }
 167       else
 168         {
 169           if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
 170               && pre[src->index] >= pre[dest->index]
 171               && post[dest->index] == 0)
 172             e->flags |= EDGE_DFS_BACK, found = true;
 173
 174           if (! e->succ_next && src != ENTRY_BLOCK_PTR)
 175             post[src->index] = postnum++;
 176
 177           if (e->succ_next)
 178             stack[sp - 1] = e->succ_next;
 179           else
 180             sp--;
 181         }
 182     }
 183
 184   free (pre);
 185   free (post);
 186   free (stack);
 187   sbitmap_free (visited);
 188
 189   return found;
 190 }
 191
 192 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru.  */
 193
 194 void
 195 set_edge_can_fallthru_flag ()
 196 {
 197   basic_block bb;
 198
 199   FOR_EACH_BB (bb)
 200     {
 201       edge e;
 202
 203       /* The FALLTHRU edge is also CAN_FALLTHRU edge.  */
 204       for (e = bb->succ; e; e = e->succ_next)
 205         if (e->flags & EDGE_FALLTHRU)
 206           e->flags |= EDGE_CAN_FALLTHRU;
 207
 208       /* If the BB ends with an invertable condjump all (2) edges are
 209          CAN_FALLTHRU edges.  */
 210       if (!bb->succ || !bb->succ->succ_next || bb->succ->succ_next->succ_next)
 211         continue;
 212       if (!any_condjump_p (bb->end))
 213         continue;
 214       if (!invert_jump (bb->end, JUMP_LABEL (bb->end), 0))
 215         continue;
 216       invert_jump (bb->end, JUMP_LABEL (bb->end), 0);
 217       bb->succ->flags |= EDGE_CAN_FALLTHRU;
 218       bb->succ->succ_next->flags |= EDGE_CAN_FALLTHRU;
 219     }
 220 }
 221
 222 /* Return true if we need to add fake edge to exit.
 223    Helper function for the flow_call_edges_add.  */
 224
 225 static bool
 226 need_fake_edge_p (insn)
 227      rtx insn;
 228 {
 229   if (!INSN_P (insn))
 230     return false;
 231
 232   if ((GET_CODE (insn) == CALL_INSN
 233        && !SIBLING_CALL_P (insn)
 234        && !find_reg_note (insn, REG_NORETURN, NULL)
 235        && !find_reg_note (insn, REG_ALWAYS_RETURN, NULL)
 236        && !CONST_OR_PURE_CALL_P (insn)))
 237     return true;
 238
 239   return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
 240            && MEM_VOLATILE_P (PATTERN (insn)))
 241           || (GET_CODE (PATTERN (insn)) == PARALLEL
 242               && asm_noperands (insn) != -1
 243               && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
 244           || GET_CODE (PATTERN (insn)) == ASM_INPUT);
 245 }
 246
 247 /* Add fake edges to the function exit for any non constant and non noreturn
 248    calls, volatile inline assembly in the bitmap of blocks specified by
 249    BLOCKS or to the whole CFG if BLOCKS is zero.  Return the number of blocks
 250    that were split.
 251
 252    The goal is to expose cases in which entering a basic block does not imply
 253    that all subsequent instructions must be executed.  */
 254
 255 int
 256 flow_call_edges_add (blocks)
 257      sbitmap blocks;
 258 {
 259   int i;
 260   int blocks_split = 0;
 261   int bb_num = 0;
 262   basic_block *bbs, bb;
 263   bool check_last_block = false;
 264
 265   /* Map bb indices into basic block pointers since split_block
 266      will renumber the basic blocks.  */
 267
 268   bbs = xmalloc (n_basic_blocks * sizeof (*bbs));
 269
 270   if (! blocks)
 271     {
 272       FOR_EACH_BB (bb)
 273         bbs[bb_num++] = bb;
 274
 275       check_last_block = true;
 276     }
 277   else
 278     EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i,
 279                                {
 280                                  bbs[bb_num++] = BASIC_BLOCK (i);
 281                                  if (i == n_basic_blocks - 1)
 282                                    check_last_block = true;
 283                                });
 284
 285   /* In the last basic block, before epilogue generation, there will be
 286      a fallthru edge to EXIT.  Special care is required if the last insn
 287      of the last basic block is a call because make_edge folds duplicate
 288      edges, which would result in the fallthru edge also being marked
 289      fake, which would result in the fallthru edge being removed by
 290      remove_fake_edges, which would result in an invalid CFG.
 291
 292      Moreover, we can't elide the outgoing fake edge, since the block
 293      profiler needs to take this into account in order to solve the minimal
 294      spanning tree in the case that the call doesn't return.
 295
 296      Handle this by adding a dummy instruction in a new last basic block.  */
 297   if (check_last_block)
 298     {
 299       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
 300       rtx insn = bb->end;
 301
 302       /* Back up past insns that must be kept in the same block as a call.  */
 303       while (insn != bb->head
 304              && keep_with_call_p (insn))
 305         insn = PREV_INSN (insn);
 306
 307       if (need_fake_edge_p (insn))
 308         {
 309           edge e;
 310
 311           for (e = bb->succ; e; e = e->succ_next)
 312             if (e->dest == EXIT_BLOCK_PTR)
 313               break;
 314
 315           insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e);
 316           commit_edge_insertions ();
 317         }
 318     }
 319
 320   /* Now add fake edges to the function exit for any non constant
 321      calls since there is no way that we can determine if they will
 322      return or not...  */
 323
 324   for (i = 0; i < bb_num; i++)
 325     {
 326       basic_block bb = bbs[i];
 327       rtx insn;
 328       rtx prev_insn;
 329
 330       for (insn = bb->end; ; insn = prev_insn)
 331         {
 332           prev_insn = PREV_INSN (insn);
 333           if (need_fake_edge_p (insn))
 334             {
 335               edge e;
 336               rtx split_at_insn = insn;
 337
 338               /* Don't split the block between a call and an insn that should
 339                  remain in the same block as the call.  */
 340               if (GET_CODE (insn) == CALL_INSN)
 341                 while (split_at_insn != bb->end
 342                        && keep_with_call_p (NEXT_INSN (split_at_insn)))
 343                   split_at_insn = NEXT_INSN (split_at_insn);
 344
 345               /* The handling above of the final block before the epilogue
 346                  should be enough to verify that there is no edge to the exit
 347                  block in CFG already.  Calling make_edge in such case would
 348                  cause us to mark that edge as fake and remove it later.  */
 349
 350 #ifdef ENABLE_CHECKING
 351               if (split_at_insn == bb->end)
 352                 for (e = bb->succ; e; e = e->succ_next)
 353                   if (e->dest == EXIT_BLOCK_PTR)
 354                     abort ();
 355 #endif
 356
 357               /* Note that the following may create a new basic block
 358                  and renumber the existing basic blocks.  */
 359               if (split_at_insn != bb->end)
 360                 {
 361                   e = split_block (bb, split_at_insn);
 362                   if (e)
 363                     blocks_split++;
 364                 }
 365
 366               make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 367             }
 368
 369           if (insn == bb->head)
 370             break;
 371         }
 372     }
 373
 374   if (blocks_split)
 375     verify_flow_info ();
 376
 377   free (bbs);
 378   return blocks_split;
 379 }
 380
 381 /* Find unreachable blocks.  An unreachable block will have 0 in
 382    the reachable bit in block->flags.  A non-zero value indicates the
 383    block is reachable.  */
 384
 385 void
 386 find_unreachable_blocks ()
 387 {
 388   edge e;
 389   basic_block *tos, *worklist, bb;
 390
 391   tos = worklist =
 392         (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
 393
 394   /* Clear all the reachability flags.  */
 395
 396   FOR_EACH_BB (bb)
 397     bb->flags &= ~BB_REACHABLE;
 398
 399   /* Add our starting points to the worklist.  Almost always there will
 400      be only one.  It isn't inconceivable that we might one day directly
 401      support Fortran alternate entry points.  */
 402
 403   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
 404     {
 405       *tos++ = e->dest;
 406
 407       /* Mark the block reachable.  */
 408       e->dest->flags |= BB_REACHABLE;
 409     }
 410
 411   /* Iterate: find everything reachable from what we've already seen.  */
 412
 413   while (tos != worklist)
 414     {
 415       basic_block b = *--tos;
 416
 417       for (e = b->succ; e; e = e->succ_next)
 418         if (!(e->dest->flags & BB_REACHABLE))
 419           {
 420             *tos++ = e->dest;
 421             e->dest->flags |= BB_REACHABLE;
 422           }
 423     }
 424
 425   free (worklist);
 426 }
 427 \f
 428 /* Functions to access an edge list with a vector representation.
 429    Enough data is kept such that given an index number, the
 430    pred and succ that edge represents can be determined, or
 431    given a pred and a succ, its index number can be returned.
 432    This allows algorithms which consume a lot of memory to
 433    represent the normally full matrix of edge (pred,succ) with a
 434    single indexed vector,  edge (EDGE_INDEX (pred, succ)), with no
 435    wasted space in the client code due to sparse flow graphs.  */
 436
 437 /* This functions initializes the edge list. Basically the entire
 438    flowgraph is processed, and all edges are assigned a number,
 439    and the data structure is filled in.  */
 440
 441 struct edge_list *
 442 create_edge_list ()
 443 {
 444   struct edge_list *elist;
 445   edge e;
 446   int num_edges;
 447   int block_count;
 448   basic_block bb;
 449
 450   block_count = n_basic_blocks + 2;   /* Include the entry and exit blocks.  */
 451
 452   num_edges = 0;
 453
 454   /* Determine the number of edges in the flow graph by counting successor
 455      edges on each basic block.  */
 456   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 457     {
 458       for (e = bb->succ; e; e = e->succ_next)
 459         num_edges++;
 460     }
 461
 462   elist = (struct edge_list *) xmalloc (sizeof (struct edge_list));
 463   elist->num_blocks = block_count;
 464   elist->num_edges = num_edges;
 465   elist->index_to_edge = (edge *) xmalloc (sizeof (edge) * num_edges);
 466
 467   num_edges = 0;
 468
 469   /* Follow successors of blocks, and register these edges.  */
 470   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 471     for (e = bb->succ; e; e = e->succ_next)
 472       elist->index_to_edge[num_edges++] = e;
 473
 474   return elist;
 475 }
 476
 477 /* This function free's memory associated with an edge list.  */
 478
 479 void
 480 free_edge_list (elist)
 481      struct edge_list *elist;
 482 {
 483   if (elist)
 484     {
 485       free (elist->index_to_edge);
 486       free (elist);
 487     }
 488 }
 489
 490 /* This function provides debug output showing an edge list.  */
 491
 492 void
 493 print_edge_list (f, elist)
 494      FILE *f;
 495      struct edge_list *elist;
 496 {
 497   int x;
 498
 499   fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
 500            elist->num_blocks - 2, elist->num_edges);
 501
 502   for (x = 0; x < elist->num_edges; x++)
 503     {
 504       fprintf (f, " %-4d - edge(", x);
 505       if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
 506         fprintf (f, "entry,");
 507       else
 508         fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
 509
 510       if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
 511         fprintf (f, "exit)\n");
 512       else
 513         fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
 514     }
 515 }
 516
 517 /* This function provides an internal consistency check of an edge list,
 518    verifying that all edges are present, and that there are no
 519    extra edges.  */
 520
 521 void
 522 verify_edge_list (f, elist)
 523      FILE *f;
 524      struct edge_list *elist;
 525 {
 526   int pred, succ, index;
 527   edge e;
 528   basic_block bb, p, s;
 529
 530   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 531     {
 532       for (e = bb->succ; e; e = e->succ_next)
 533         {
 534           pred = e->src->index;
 535           succ = e->dest->index;
 536           index = EDGE_INDEX (elist, e->src, e->dest);
 537           if (index == EDGE_INDEX_NO_EDGE)
 538             {
 539               fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
 540               continue;
 541             }
 542
 543           if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
 544             fprintf (f, "*p* Pred for index %d should be %d not %d\n",
 545                      index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
 546           if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
 547             fprintf (f, "*p* Succ for index %d should be %d not %d\n",
 548                      index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
 549         }
 550     }
 551
 552   /* We've verified that all the edges are in the list, now lets make sure
 553      there are no spurious edges in the list.  */
 554
 555   FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 556     FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 557       {
 558         int found_edge = 0;
 559
 560         for (e = p->succ; e; e = e->succ_next)
 561           if (e->dest == s)
 562             {
 563               found_edge = 1;
 564               break;
 565             }
 566
 567         for (e = s->pred; e; e = e->pred_next)
 568           if (e->src == p)
 569             {
 570               found_edge = 1;
 571               break;
 572             }
 573
 574         if (EDGE_INDEX (elist, p, s)
 575             == EDGE_INDEX_NO_EDGE && found_edge != 0)
 576           fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
 577                    p->index, s->index);
 578         if (EDGE_INDEX (elist, p, s)
 579             != EDGE_INDEX_NO_EDGE && found_edge == 0)
 580           fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
 581                    p->index, s->index, EDGE_INDEX (elist, p, s));
 582       }
 583 }
 584
 585 /* This routine will determine what, if any, edge there is between
 586    a specified predecessor and successor.  */
 587
 588 int
 589 find_edge_index (edge_list, pred, succ)
 590      struct edge_list *edge_list;
 591      basic_block pred, succ;
 592 {
 593   int x;
 594
 595   for (x = 0; x < NUM_EDGES (edge_list); x++)
 596     if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
 597         && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
 598       return x;
 599
 600   return (EDGE_INDEX_NO_EDGE);
 601 }
 602
 603 /* Dump the list of basic blocks in the bitmap NODES.  */
 604
 605 void
 606 flow_nodes_print (str, nodes, file)
 607      const char *str;
 608      const sbitmap nodes;
 609      FILE *file;
 610 {
 611   int node;
 612
 613   if (! nodes)
 614     return;
 615
 616   fprintf (file, "%s { ", str);
 617   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
 618   fputs ("}\n", file);
 619 }
 620
 621 /* Dump the list of edges in the array EDGE_LIST.  */
 622
 623 void
 624 flow_edge_list_print (str, edge_list, num_edges, file)
 625      const char *str;
 626      const edge *edge_list;
 627      int num_edges;
 628      FILE *file;
 629 {
 630   int i;
 631
 632   if (! edge_list)
 633     return;
 634
 635   fprintf (file, "%s { ", str);
 636   for (i = 0; i < num_edges; i++)
 637     fprintf (file, "%d->%d ", edge_list[i]->src->index,
 638              edge_list[i]->dest->index);
 639
 640   fputs ("}\n", file);
 641 }
 642
 643 \f
 644 /* This routine will remove any fake successor edges for a basic block.
 645    When the edge is removed, it is also removed from whatever predecessor
 646    list it is in.  */
 647
 648 static void
 649 remove_fake_successors (bb)
 650      basic_block bb;
 651 {
 652   edge e;
 653
 654   for (e = bb->succ; e;)
 655     {
 656       edge tmp = e;
 657
 658       e = e->succ_next;
 659       if ((tmp->flags & EDGE_FAKE) == EDGE_FAKE)
 660         remove_edge (tmp);
 661     }
 662 }
 663
 664 /* This routine will remove all fake edges from the flow graph.  If
 665    we remove all fake successors, it will automatically remove all
 666    fake predecessors.  */
 667
 668 void
 669 remove_fake_edges ()
 670 {
 671   basic_block bb;
 672
 673   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 674     remove_fake_successors (bb);
 675 }
 676
 677 /* This function will add a fake edge between any block which has no
 678    successors, and the exit block. Some data flow equations require these
 679    edges to exist.  */
 680
 681 void
 682 add_noreturn_fake_exit_edges ()
 683 {
 684   basic_block bb;
 685
 686   FOR_EACH_BB (bb)
 687     if (bb->succ == NULL)
 688       make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 689 }
 690
 691 /* This function adds a fake edge between any infinite loops to the
 692    exit block.  Some optimizations require a path from each node to
 693    the exit node.
 694
 695    See also Morgan, Figure 3.10, pp. 82-83.
 696
 697    The current implementation is ugly, not attempting to minimize the
 698    number of inserted fake edges.  To reduce the number of fake edges
 699    to insert, add fake edges from _innermost_ loops containing only
 700    nodes not reachable from the exit block.  */
 701
 702 void
 703 connect_infinite_loops_to_exit ()
 704 {
 705   basic_block unvisited_block;
 706   struct depth_first_search_dsS dfs_ds;
 707
 708   /* Perform depth-first search in the reverse graph to find nodes
 709      reachable from the exit block.  */
 710   flow_dfs_compute_reverse_init (&dfs_ds);
 711   flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
 712
 713   /* Repeatedly add fake edges, updating the unreachable nodes.  */
 714   while (1)
 715     {
 716       unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds);
 717       if (!unvisited_block)
 718         break;
 719
 720       make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
 721       flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
 722     }
 723
 724   flow_dfs_compute_reverse_finish (&dfs_ds);
 725   return;
 726 }
 727 \f
 728 /* Compute reverse top sort order */
 729
 730 void
 731 flow_reverse_top_sort_order_compute (rts_order)
 732      int *rts_order;
 733 {
 734   edge *stack;
 735   int sp;
 736   int postnum = 0;
 737   sbitmap visited;
 738
 739   /* Allocate stack for back-tracking up CFG.  */
 740   stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
 741   sp = 0;
 742
 743   /* Allocate bitmap to track nodes that have been visited.  */
 744   visited = sbitmap_alloc (last_basic_block);
 745
 746   /* None of the nodes in the CFG have been visited yet.  */
 747   sbitmap_zero (visited);
 748
 749   /* Push the first edge on to the stack.  */
 750   stack[sp++] = ENTRY_BLOCK_PTR->succ;
 751
 752   while (sp)
 753     {
 754       edge e;
 755       basic_block src;
 756       basic_block dest;
 757
 758       /* Look at the edge on the top of the stack.  */
 759       e = stack[sp - 1];
 760       src = e->src;
 761       dest = e->dest;
 762
 763       /* Check if the edge destination has been visited yet.  */
 764       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 765         {
 766           /* Mark that we have visited the destination.  */
 767           SET_BIT (visited, dest->index);
 768
 769           if (dest->succ)
 770             /* Since the DEST node has been visited for the first
 771                time, check its successors.  */
 772             stack[sp++] = dest->succ;
 773           else
 774             rts_order[postnum++] = dest->index;
 775         }
 776       else
 777         {
 778           if (! e->succ_next && src != ENTRY_BLOCK_PTR)
 779            rts_order[postnum++] = src->index;
 780
 781           if (e->succ_next)
 782             stack[sp - 1] = e->succ_next;
 783           else
 784             sp--;
 785         }
 786     }
 787
 788   free (stack);
 789   sbitmap_free (visited);
 790 }
 791
 792 /* Compute the depth first search order and store in the array
 793   DFS_ORDER if non-zero, marking the nodes visited in VISITED.  If
 794   RC_ORDER is non-zero, return the reverse completion number for each
 795   node.  Returns the number of nodes visited.  A depth first search
 796   tries to get as far away from the starting point as quickly as
 797   possible.  */
 798
 799 int
 800 flow_depth_first_order_compute (dfs_order, rc_order)
 801      int *dfs_order;
 802      int *rc_order;
 803 {
 804   edge *stack;
 805   int sp;
 806   int dfsnum = 0;
 807   int rcnum = n_basic_blocks - 1;
 808   sbitmap visited;
 809
 810   /* Allocate stack for back-tracking up CFG.  */
 811   stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
 812   sp = 0;
 813
 814   /* Allocate bitmap to track nodes that have been visited.  */
 815   visited = sbitmap_alloc (last_basic_block);
 816
 817   /* None of the nodes in the CFG have been visited yet.  */
 818   sbitmap_zero (visited);
 819
 820   /* Push the first edge on to the stack.  */
 821   stack[sp++] = ENTRY_BLOCK_PTR->succ;
 822
 823   while (sp)
 824     {
 825       edge e;
 826       basic_block src;
 827       basic_block dest;
 828
 829       /* Look at the edge on the top of the stack.  */
 830       e = stack[sp - 1];
 831       src = e->src;
 832       dest = e->dest;
 833
 834       /* Check if the edge destination has been visited yet.  */
 835       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 836         {
 837           /* Mark that we have visited the destination.  */
 838           SET_BIT (visited, dest->index);
 839
 840           if (dfs_order)
 841             dfs_order[dfsnum] = dest->index;
 842
 843           dfsnum++;
 844
 845           if (dest->succ)
 846             /* Since the DEST node has been visited for the first
 847                time, check its successors.  */
 848             stack[sp++] = dest->succ;
 849           else if (rc_order)
 850             /* There are no successors for the DEST node so assign
 851                its reverse completion number.  */
 852             rc_order[rcnum--] = dest->index;
 853         }
 854       else
 855         {
 856           if (! e->succ_next && src != ENTRY_BLOCK_PTR
 857               && rc_order)
 858             /* There are no more successors for the SRC node
 859                so assign its reverse completion number.  */
 860             rc_order[rcnum--] = src->index;
 861
 862           if (e->succ_next)
 863             stack[sp - 1] = e->succ_next;
 864           else
 865             sp--;
 866         }
 867     }
 868
 869   free (stack);
 870   sbitmap_free (visited);
 871
 872   /* The number of nodes visited should not be greater than
 873      n_basic_blocks.  */
 874   if (dfsnum > n_basic_blocks)
 875     abort ();
 876
 877   /* There are some nodes left in the CFG that are unreachable.  */
 878   if (dfsnum < n_basic_blocks)
 879     abort ();
 880
 881   return dfsnum;
 882 }
 883
 884 struct dfst_node
 885 {
 886     unsigned nnodes;
 887     struct dfst_node **node;
 888     struct dfst_node *up;
 889 };
 890
 891 /* Compute a preorder transversal ordering such that a sub-tree which
 892    is the source of a cross edge appears before the sub-tree which is
 893    the destination of the cross edge.  This allows for easy detection
 894    of all the entry blocks for a loop.
 895
 896    The ordering is compute by:
 897
 898      1) Generating a depth first spanning tree.
 899
 900      2) Walking the resulting tree from right to left.  */
 901
 902 void
 903 flow_preorder_transversal_compute (pot_order)
 904      int *pot_order;
 905 {
 906   edge e;
 907   edge *stack;
 908   int i;
 909   int max_successors;
 910   int sp;
 911   sbitmap visited;
 912   struct dfst_node *node;
 913   struct dfst_node *dfst;
 914   basic_block bb;
 915
 916   /* Allocate stack for back-tracking up CFG.  */
 917   stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
 918   sp = 0;
 919
 920   /* Allocate the tree.  */
 921   dfst = (struct dfst_node *) xcalloc (last_basic_block,
 922                                        sizeof (struct dfst_node));
 923
 924   FOR_EACH_BB (bb)
 925     {
 926       max_successors = 0;
 927       for (e = bb->succ; e; e = e->succ_next)
 928         max_successors++;
 929
 930       dfst[i].node
 931         = (max_successors
 932            ? (struct dfst_node **) xcalloc (max_successors,
 933                                             sizeof (struct dfst_node *))
 934            : NULL);
 935     }
 936
 937   /* Allocate bitmap to track nodes that have been visited.  */
 938   visited = sbitmap_alloc (last_basic_block);
 939
 940   /* None of the nodes in the CFG have been visited yet.  */
 941   sbitmap_zero (visited);
 942
 943   /* Push the first edge on to the stack.  */
 944   stack[sp++] = ENTRY_BLOCK_PTR->succ;
 945
 946   while (sp)
 947     {
 948       basic_block src;
 949       basic_block dest;
 950
 951       /* Look at the edge on the top of the stack.  */
 952       e = stack[sp - 1];
 953       src = e->src;
 954       dest = e->dest;
 955
 956       /* Check if the edge destination has been visited yet.  */
 957       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 958         {
 959           /* Mark that we have visited the destination.  */
 960           SET_BIT (visited, dest->index);
 961
 962           /* Add the destination to the preorder tree.  */
 963           if (src != ENTRY_BLOCK_PTR)
 964             {
 965               dfst[src->index].node[dfst[src->index].nnodes++]
 966                 = &dfst[dest->index];
 967               dfst[dest->index].up = &dfst[src->index];
 968             }
 969
 970           if (dest->succ)
 971             /* Since the DEST node has been visited for the first
 972                time, check its successors.  */
 973             stack[sp++] = dest->succ;
 974         }
 975
 976       else if (e->succ_next)
 977         stack[sp - 1] = e->succ_next;
 978       else
 979         sp--;
 980     }
 981
 982   free (stack);
 983   sbitmap_free (visited);
 984
 985   /* Record the preorder transversal order by
 986      walking the tree from right to left.  */
 987
 988   i = 0;
 989   node = &dfst[ENTRY_BLOCK_PTR->next_bb->index];
 990   pot_order[i++] = 0;
 991
 992   while (node)
 993     {
 994       if (node->nnodes)
 995         {
 996           node = node->node[--node->nnodes];
 997           pot_order[i++] = node - dfst;
 998         }
 999       else
1000         node = node->up;
1001     }
1002
1003   /* Free the tree.  */
1004
1005   for (i = 0; i < last_basic_block; i++)
1006     if (dfst[i].node)
1007       free (dfst[i].node);
1008
1009   free (dfst);
1010 }
1011
1012 /* Compute the depth first search order on the _reverse_ graph and
1013    store in the array DFS_ORDER, marking the nodes visited in VISITED.
1014    Returns the number of nodes visited.
1015
1016    The computation is split into three pieces:
1017
1018    flow_dfs_compute_reverse_init () creates the necessary data
1019    structures.
1020
1021    flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1022    structures.  The block will start the search.
1023
1024    flow_dfs_compute_reverse_execute () continues (or starts) the
1025    search using the block on the top of the stack, stopping when the
1026    stack is empty.
1027
1028    flow_dfs_compute_reverse_finish () destroys the necessary data
1029    structures.
1030
1031    Thus, the user will probably call ..._init(), call ..._add_bb() to
1032    add a beginning basic block to the stack, call ..._execute(),
1033    possibly add another bb to the stack and again call ..._execute(),
1034    ..., and finally call _finish().  */
1035
1036 /* Initialize the data structures used for depth-first search on the
1037    reverse graph.  If INITIALIZE_STACK is nonzero, the exit block is
1038    added to the basic block stack.  DATA is the current depth-first
1039    search context.  If INITIALIZE_STACK is non-zero, there is an
1040    element on the stack.  */
1041
1042 static void
1043 flow_dfs_compute_reverse_init (data)
1044      depth_first_search_ds data;
1045 {
1046   /* Allocate stack for back-tracking up CFG.  */
1047   data->stack = (basic_block *) xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
1048                                          * sizeof (basic_block));
1049   data->sp = 0;
1050
1051   /* Allocate bitmap to track nodes that have been visited.  */
1052   data->visited_blocks = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
1053
1054   /* None of the nodes in the CFG have been visited yet.  */
1055   sbitmap_zero (data->visited_blocks);
1056
1057   return;
1058 }
1059
1060 /* Add the specified basic block to the top of the dfs data
1061    structures.  When the search continues, it will start at the
1062    block.  */
1063
1064 static void
1065 flow_dfs_compute_reverse_add_bb (data, bb)
1066      depth_first_search_ds data;
1067      basic_block bb;
1068 {
1069   data->stack[data->sp++] = bb;
1070   SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1));
1071 }
1072
1073 /* Continue the depth-first search through the reverse graph starting with the
1074    block at the stack's top and ending when the stack is empty.  Visited nodes
1075    are marked.  Returns an unvisited basic block, or NULL if there is none
1076    available.  */
1077
1078 static basic_block
1079 flow_dfs_compute_reverse_execute (data)
1080      depth_first_search_ds data;
1081 {
1082   basic_block bb;
1083   edge e;
1084
1085   while (data->sp > 0)
1086     {
1087       bb = data->stack[--data->sp];
1088
1089       /* Perform depth-first search on adjacent vertices.  */
1090       for (e = bb->pred; e; e = e->pred_next)
1091         if (!TEST_BIT (data->visited_blocks,
1092                        e->src->index - (INVALID_BLOCK + 1)))
1093           flow_dfs_compute_reverse_add_bb (data, e->src);
1094     }
1095
1096   /* Determine if there are unvisited basic blocks.  */
1097   FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
1098     if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
1099       return bb;
1100
1101   return NULL;
1102 }
1103
1104 /* Destroy the data structures needed for depth-first search on the
1105    reverse graph.  */
1106
1107 static void
1108 flow_dfs_compute_reverse_finish (data)
1109      depth_first_search_ds data;
1110 {
1111   free (data->stack);
1112   sbitmap_free (data->visited_blocks);
1113 }