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 last_bb = last_basic_block;
 262   bool check_last_block = false;
 263
 264   if (n_basic_blocks == 0)
 265     return 0;
 266
 267   if (! blocks)
 268     check_last_block = true;
 269   else
 270     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
 271
 272   /* In the last basic block, before epilogue generation, there will be
 273      a fallthru edge to EXIT.  Special care is required if the last insn
 274      of the last basic block is a call because make_edge folds duplicate
 275      edges, which would result in the fallthru edge also being marked
 276      fake, which would result in the fallthru edge being removed by
 277      remove_fake_edges, which would result in an invalid CFG.
 278
 279      Moreover, we can't elide the outgoing fake edge, since the block
 280      profiler needs to take this into account in order to solve the minimal
 281      spanning tree in the case that the call doesn't return.
 282
 283      Handle this by adding a dummy instruction in a new last basic block.  */
 284   if (check_last_block)
 285     {
 286       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
 287       rtx insn = bb->end;
 288
 289       /* Back up past insns that must be kept in the same block as a call.  */
 290       while (insn != bb->head
 291              && keep_with_call_p (insn))
 292         insn = PREV_INSN (insn);
 293
 294       if (need_fake_edge_p (insn))
 295         {
 296           edge e;
 297
 298           for (e = bb->succ; e; e = e->succ_next)
 299             if (e->dest == EXIT_BLOCK_PTR)
 300               break;
 301
 302           insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e);
 303           commit_edge_insertions ();
 304         }
 305     }
 306
 307   /* Now add fake edges to the function exit for any non constant
 308      calls since there is no way that we can determine if they will
 309      return or not...  */
 310
 311   for (i = 0; i < last_bb; i++)
 312     {
 313       basic_block bb = BASIC_BLOCK (i);
 314       rtx insn;
 315       rtx prev_insn;
 316
 317       if (!bb)
 318         continue;
 319
 320       if (blocks && !TEST_BIT (blocks, i))
 321         continue;
 322
 323       for (insn = bb->end; ; insn = prev_insn)
 324         {
 325           prev_insn = PREV_INSN (insn);
 326           if (need_fake_edge_p (insn))
 327             {
 328               edge e;
 329               rtx split_at_insn = insn;
 330
 331               /* Don't split the block between a call and an insn that should
 332                  remain in the same block as the call.  */
 333               if (GET_CODE (insn) == CALL_INSN)
 334                 while (split_at_insn != bb->end
 335                        && keep_with_call_p (NEXT_INSN (split_at_insn)))
 336                   split_at_insn = NEXT_INSN (split_at_insn);
 337
 338               /* The handling above of the final block before the epilogue
 339                  should be enough to verify that there is no edge to the exit
 340                  block in CFG already.  Calling make_edge in such case would
 341                  cause us to mark that edge as fake and remove it later.  */
 342
 343 #ifdef ENABLE_CHECKING
 344               if (split_at_insn == bb->end)
 345                 for (e = bb->succ; e; e = e->succ_next)
 346                   if (e->dest == EXIT_BLOCK_PTR)
 347                     abort ();
 348 #endif
 349
 350               /* Note that the following may create a new basic block
 351                  and renumber the existing basic blocks.  */
 352               if (split_at_insn != bb->end)
 353                 {
 354                   e = split_block (bb, split_at_insn);
 355                   if (e)
 356                     blocks_split++;
 357                 }
 358
 359               make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 360             }
 361
 362           if (insn == bb->head)
 363             break;
 364         }
 365     }
 366
 367   if (blocks_split)
 368     verify_flow_info ();
 369
 370   return blocks_split;
 371 }
 372
 373 /* Find unreachable blocks.  An unreachable block will have 0 in
 374    the reachable bit in block->flags.  A non-zero value indicates the
 375    block is reachable.  */
 376
 377 void
 378 find_unreachable_blocks ()
 379 {
 380   edge e;
 381   basic_block *tos, *worklist, bb;
 382
 383   tos = worklist =
 384         (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
 385
 386   /* Clear all the reachability flags.  */
 387
 388   FOR_EACH_BB (bb)
 389     bb->flags &= ~BB_REACHABLE;
 390
 391   /* Add our starting points to the worklist.  Almost always there will
 392      be only one.  It isn't inconceivable that we might one day directly
 393      support Fortran alternate entry points.  */
 394
 395   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
 396     {
 397       *tos++ = e->dest;
 398
 399       /* Mark the block reachable.  */
 400       e->dest->flags |= BB_REACHABLE;
 401     }
 402
 403   /* Iterate: find everything reachable from what we've already seen.  */
 404
 405   while (tos != worklist)
 406     {
 407       basic_block b = *--tos;
 408
 409       for (e = b->succ; e; e = e->succ_next)
 410         if (!(e->dest->flags & BB_REACHABLE))
 411           {
 412             *tos++ = e->dest;
 413             e->dest->flags |= BB_REACHABLE;
 414           }
 415     }
 416
 417   free (worklist);
 418 }
 419 \f
 420 /* Functions to access an edge list with a vector representation.
 421    Enough data is kept such that given an index number, the
 422    pred and succ that edge represents can be determined, or
 423    given a pred and a succ, its index number can be returned.
 424    This allows algorithms which consume a lot of memory to
 425    represent the normally full matrix of edge (pred,succ) with a
 426    single indexed vector,  edge (EDGE_INDEX (pred, succ)), with no
 427    wasted space in the client code due to sparse flow graphs.  */
 428
 429 /* This functions initializes the edge list. Basically the entire
 430    flowgraph is processed, and all edges are assigned a number,
 431    and the data structure is filled in.  */
 432
 433 struct edge_list *
 434 create_edge_list ()
 435 {
 436   struct edge_list *elist;
 437   edge e;
 438   int num_edges;
 439   int block_count;
 440   basic_block bb;
 441
 442   block_count = n_basic_blocks + 2;   /* Include the entry and exit blocks.  */
 443
 444   num_edges = 0;
 445
 446   /* Determine the number of edges in the flow graph by counting successor
 447      edges on each basic block.  */
 448   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 449     {
 450       for (e = bb->succ; e; e = e->succ_next)
 451         num_edges++;
 452     }
 453
 454   elist = (struct edge_list *) xmalloc (sizeof (struct edge_list));
 455   elist->num_blocks = block_count;
 456   elist->num_edges = num_edges;
 457   elist->index_to_edge = (edge *) xmalloc (sizeof (edge) * num_edges);
 458
 459   num_edges = 0;
 460
 461   /* Follow successors of blocks, and register these edges.  */
 462   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 463     for (e = bb->succ; e; e = e->succ_next)
 464       elist->index_to_edge[num_edges++] = e;
 465
 466   return elist;
 467 }
 468
 469 /* This function free's memory associated with an edge list.  */
 470
 471 void
 472 free_edge_list (elist)
 473      struct edge_list *elist;
 474 {
 475   if (elist)
 476     {
 477       free (elist->index_to_edge);
 478       free (elist);
 479     }
 480 }
 481
 482 /* This function provides debug output showing an edge list.  */
 483
 484 void
 485 print_edge_list (f, elist)
 486      FILE *f;
 487      struct edge_list *elist;
 488 {
 489   int x;
 490
 491   fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
 492            elist->num_blocks - 2, elist->num_edges);
 493
 494   for (x = 0; x < elist->num_edges; x++)
 495     {
 496       fprintf (f, " %-4d - edge(", x);
 497       if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
 498         fprintf (f, "entry,");
 499       else
 500         fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
 501
 502       if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
 503         fprintf (f, "exit)\n");
 504       else
 505         fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
 506     }
 507 }
 508
 509 /* This function provides an internal consistency check of an edge list,
 510    verifying that all edges are present, and that there are no
 511    extra edges.  */
 512
 513 void
 514 verify_edge_list (f, elist)
 515      FILE *f;
 516      struct edge_list *elist;
 517 {
 518   int pred, succ, index;
 519   edge e;
 520   basic_block bb, p, s;
 521
 522   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 523     {
 524       for (e = bb->succ; e; e = e->succ_next)
 525         {
 526           pred = e->src->index;
 527           succ = e->dest->index;
 528           index = EDGE_INDEX (elist, e->src, e->dest);
 529           if (index == EDGE_INDEX_NO_EDGE)
 530             {
 531               fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
 532               continue;
 533             }
 534
 535           if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
 536             fprintf (f, "*p* Pred for index %d should be %d not %d\n",
 537                      index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
 538           if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
 539             fprintf (f, "*p* Succ for index %d should be %d not %d\n",
 540                      index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
 541         }
 542     }
 543
 544   /* We've verified that all the edges are in the list, now lets make sure
 545      there are no spurious edges in the list.  */
 546
 547   FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 548     FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 549       {
 550         int found_edge = 0;
 551
 552         for (e = p->succ; e; e = e->succ_next)
 553           if (e->dest == s)
 554             {
 555               found_edge = 1;
 556               break;
 557             }
 558
 559         for (e = s->pred; e; e = e->pred_next)
 560           if (e->src == p)
 561             {
 562               found_edge = 1;
 563               break;
 564             }
 565
 566         if (EDGE_INDEX (elist, p, s)
 567             == EDGE_INDEX_NO_EDGE && found_edge != 0)
 568           fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
 569                    p->index, s->index);
 570         if (EDGE_INDEX (elist, p, s)
 571             != EDGE_INDEX_NO_EDGE && found_edge == 0)
 572           fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
 573                    p->index, s->index, EDGE_INDEX (elist, p, s));
 574       }
 575 }
 576
 577 /* This routine will determine what, if any, edge there is between
 578    a specified predecessor and successor.  */
 579
 580 int
 581 find_edge_index (edge_list, pred, succ)
 582      struct edge_list *edge_list;
 583      basic_block pred, succ;
 584 {
 585   int x;
 586
 587   for (x = 0; x < NUM_EDGES (edge_list); x++)
 588     if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
 589         && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
 590       return x;
 591
 592   return (EDGE_INDEX_NO_EDGE);
 593 }
 594
 595 /* Dump the list of basic blocks in the bitmap NODES.  */
 596
 597 void
 598 flow_nodes_print (str, nodes, file)
 599      const char *str;
 600      const sbitmap nodes;
 601      FILE *file;
 602 {
 603   int node;
 604
 605   if (! nodes)
 606     return;
 607
 608   fprintf (file, "%s { ", str);
 609   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
 610   fputs ("}\n", file);
 611 }
 612
 613 /* Dump the list of edges in the array EDGE_LIST.  */
 614
 615 void
 616 flow_edge_list_print (str, edge_list, num_edges, file)
 617      const char *str;
 618      const edge *edge_list;
 619      int num_edges;
 620      FILE *file;
 621 {
 622   int i;
 623
 624   if (! edge_list)
 625     return;
 626
 627   fprintf (file, "%s { ", str);
 628   for (i = 0; i < num_edges; i++)
 629     fprintf (file, "%d->%d ", edge_list[i]->src->index,
 630              edge_list[i]->dest->index);
 631
 632   fputs ("}\n", file);
 633 }
 634
 635 \f
 636 /* This routine will remove any fake successor edges for a basic block.
 637    When the edge is removed, it is also removed from whatever predecessor
 638    list it is in.  */
 639
 640 static void
 641 remove_fake_successors (bb)
 642      basic_block bb;
 643 {
 644   edge e;
 645
 646   for (e = bb->succ; e;)
 647     {
 648       edge tmp = e;
 649
 650       e = e->succ_next;
 651       if ((tmp->flags & EDGE_FAKE) == EDGE_FAKE)
 652         remove_edge (tmp);
 653     }
 654 }
 655
 656 /* This routine will remove all fake edges from the flow graph.  If
 657    we remove all fake successors, it will automatically remove all
 658    fake predecessors.  */
 659
 660 void
 661 remove_fake_edges ()
 662 {
 663   basic_block bb;
 664
 665   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 666     remove_fake_successors (bb);
 667 }
 668
 669 /* This function will add a fake edge between any block which has no
 670    successors, and the exit block. Some data flow equations require these
 671    edges to exist.  */
 672
 673 void
 674 add_noreturn_fake_exit_edges ()
 675 {
 676   basic_block bb;
 677
 678   FOR_EACH_BB (bb)
 679     if (bb->succ == NULL)
 680       make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 681 }
 682
 683 /* This function adds a fake edge between any infinite loops to the
 684    exit block.  Some optimizations require a path from each node to
 685    the exit node.
 686
 687    See also Morgan, Figure 3.10, pp. 82-83.
 688
 689    The current implementation is ugly, not attempting to minimize the
 690    number of inserted fake edges.  To reduce the number of fake edges
 691    to insert, add fake edges from _innermost_ loops containing only
 692    nodes not reachable from the exit block.  */
 693
 694 void
 695 connect_infinite_loops_to_exit ()
 696 {
 697   basic_block unvisited_block;
 698   struct depth_first_search_dsS dfs_ds;
 699
 700   /* Perform depth-first search in the reverse graph to find nodes
 701      reachable from the exit block.  */
 702   flow_dfs_compute_reverse_init (&dfs_ds);
 703   flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
 704
 705   /* Repeatedly add fake edges, updating the unreachable nodes.  */
 706   while (1)
 707     {
 708       unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds);
 709       if (!unvisited_block)
 710         break;
 711
 712       make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
 713       flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
 714     }
 715
 716   flow_dfs_compute_reverse_finish (&dfs_ds);
 717   return;
 718 }
 719 \f
 720 /* Compute reverse top sort order */
 721
 722 void
 723 flow_reverse_top_sort_order_compute (rts_order)
 724      int *rts_order;
 725 {
 726   edge *stack;
 727   int sp;
 728   int postnum = 0;
 729   sbitmap visited;
 730
 731   /* Allocate stack for back-tracking up CFG.  */
 732   stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
 733   sp = 0;
 734
 735   /* Allocate bitmap to track nodes that have been visited.  */
 736   visited = sbitmap_alloc (last_basic_block);
 737
 738   /* None of the nodes in the CFG have been visited yet.  */
 739   sbitmap_zero (visited);
 740
 741   /* Push the first edge on to the stack.  */
 742   stack[sp++] = ENTRY_BLOCK_PTR->succ;
 743
 744   while (sp)
 745     {
 746       edge e;
 747       basic_block src;
 748       basic_block dest;
 749
 750       /* Look at the edge on the top of the stack.  */
 751       e = stack[sp - 1];
 752       src = e->src;
 753       dest = e->dest;
 754
 755       /* Check if the edge destination has been visited yet.  */
 756       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 757         {
 758           /* Mark that we have visited the destination.  */
 759           SET_BIT (visited, dest->index);
 760
 761           if (dest->succ)
 762             /* Since the DEST node has been visited for the first
 763                time, check its successors.  */
 764             stack[sp++] = dest->succ;
 765           else
 766             rts_order[postnum++] = dest->index;
 767         }
 768       else
 769         {
 770           if (! e->succ_next && src != ENTRY_BLOCK_PTR)
 771            rts_order[postnum++] = src->index;
 772
 773           if (e->succ_next)
 774             stack[sp - 1] = e->succ_next;
 775           else
 776             sp--;
 777         }
 778     }
 779
 780   free (stack);
 781   sbitmap_free (visited);
 782 }
 783
 784 /* Compute the depth first search order and store in the array
 785   DFS_ORDER if non-zero, marking the nodes visited in VISITED.  If
 786   RC_ORDER is non-zero, return the reverse completion number for each
 787   node.  Returns the number of nodes visited.  A depth first search
 788   tries to get as far away from the starting point as quickly as
 789   possible.  */
 790
 791 int
 792 flow_depth_first_order_compute (dfs_order, rc_order)
 793      int *dfs_order;
 794      int *rc_order;
 795 {
 796   edge *stack;
 797   int sp;
 798   int dfsnum = 0;
 799   int rcnum = n_basic_blocks - 1;
 800   sbitmap visited;
 801
 802   /* Allocate stack for back-tracking up CFG.  */
 803   stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
 804   sp = 0;
 805
 806   /* Allocate bitmap to track nodes that have been visited.  */
 807   visited = sbitmap_alloc (last_basic_block);
 808
 809   /* None of the nodes in the CFG have been visited yet.  */
 810   sbitmap_zero (visited);
 811
 812   /* Push the first edge on to the stack.  */
 813   stack[sp++] = ENTRY_BLOCK_PTR->succ;
 814
 815   while (sp)
 816     {
 817       edge e;
 818       basic_block src;
 819       basic_block dest;
 820
 821       /* Look at the edge on the top of the stack.  */
 822       e = stack[sp - 1];
 823       src = e->src;
 824       dest = e->dest;
 825
 826       /* Check if the edge destination has been visited yet.  */
 827       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 828         {
 829           /* Mark that we have visited the destination.  */
 830           SET_BIT (visited, dest->index);
 831
 832           if (dfs_order)
 833             dfs_order[dfsnum] = dest->index;
 834
 835           dfsnum++;
 836
 837           if (dest->succ)
 838             /* Since the DEST node has been visited for the first
 839                time, check its successors.  */
 840             stack[sp++] = dest->succ;
 841           else if (rc_order)
 842             /* There are no successors for the DEST node so assign
 843                its reverse completion number.  */
 844             rc_order[rcnum--] = dest->index;
 845         }
 846       else
 847         {
 848           if (! e->succ_next && src != ENTRY_BLOCK_PTR
 849               && rc_order)
 850             /* There are no more successors for the SRC node
 851                so assign its reverse completion number.  */
 852             rc_order[rcnum--] = src->index;
 853
 854           if (e->succ_next)
 855             stack[sp - 1] = e->succ_next;
 856           else
 857             sp--;
 858         }
 859     }
 860
 861   free (stack);
 862   sbitmap_free (visited);
 863
 864   /* The number of nodes visited should not be greater than
 865      n_basic_blocks.  */
 866   if (dfsnum > n_basic_blocks)
 867     abort ();
 868
 869   /* There are some nodes left in the CFG that are unreachable.  */
 870   if (dfsnum < n_basic_blocks)
 871     abort ();
 872
 873   return dfsnum;
 874 }
 875
 876 struct dfst_node
 877 {
 878     unsigned nnodes;
 879     struct dfst_node **node;
 880     struct dfst_node *up;
 881 };
 882
 883 /* Compute a preorder transversal ordering such that a sub-tree which
 884    is the source of a cross edge appears before the sub-tree which is
 885    the destination of the cross edge.  This allows for easy detection
 886    of all the entry blocks for a loop.
 887
 888    The ordering is compute by:
 889
 890      1) Generating a depth first spanning tree.
 891
 892      2) Walking the resulting tree from right to left.  */
 893
 894 void
 895 flow_preorder_transversal_compute (pot_order)
 896      int *pot_order;
 897 {
 898   edge e;
 899   edge *stack;
 900   int i;
 901   int max_successors;
 902   int sp;
 903   sbitmap visited;
 904   struct dfst_node *node;
 905   struct dfst_node *dfst;
 906   basic_block bb;
 907
 908   /* Allocate stack for back-tracking up CFG.  */
 909   stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
 910   sp = 0;
 911
 912   /* Allocate the tree.  */
 913   dfst = (struct dfst_node *) xcalloc (last_basic_block,
 914                                        sizeof (struct dfst_node));
 915
 916   FOR_EACH_BB (bb)
 917     {
 918       max_successors = 0;
 919       for (e = bb->succ; e; e = e->succ_next)
 920         max_successors++;
 921
 922       dfst[bb->index].node
 923         = (max_successors
 924            ? (struct dfst_node **) xcalloc (max_successors,
 925                                             sizeof (struct dfst_node *))
 926            : NULL);
 927     }
 928
 929   /* Allocate bitmap to track nodes that have been visited.  */
 930   visited = sbitmap_alloc (last_basic_block);
 931
 932   /* None of the nodes in the CFG have been visited yet.  */
 933   sbitmap_zero (visited);
 934
 935   /* Push the first edge on to the stack.  */
 936   stack[sp++] = ENTRY_BLOCK_PTR->succ;
 937
 938   while (sp)
 939     {
 940       basic_block src;
 941       basic_block dest;
 942
 943       /* Look at the edge on the top of the stack.  */
 944       e = stack[sp - 1];
 945       src = e->src;
 946       dest = e->dest;
 947
 948       /* Check if the edge destination has been visited yet.  */
 949       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 950         {
 951           /* Mark that we have visited the destination.  */
 952           SET_BIT (visited, dest->index);
 953
 954           /* Add the destination to the preorder tree.  */
 955           if (src != ENTRY_BLOCK_PTR)
 956             {
 957               dfst[src->index].node[dfst[src->index].nnodes++]
 958                 = &dfst[dest->index];
 959               dfst[dest->index].up = &dfst[src->index];
 960             }
 961
 962           if (dest->succ)
 963             /* Since the DEST node has been visited for the first
 964                time, check its successors.  */
 965             stack[sp++] = dest->succ;
 966         }
 967
 968       else if (e->succ_next)
 969         stack[sp - 1] = e->succ_next;
 970       else
 971         sp--;
 972     }
 973
 974   free (stack);
 975   sbitmap_free (visited);
 976
 977   /* Record the preorder transversal order by
 978      walking the tree from right to left.  */
 979
 980   i = 0;
 981   node = &dfst[ENTRY_BLOCK_PTR->next_bb->index];
 982   pot_order[i++] = 0;
 983
 984   while (node)
 985     {
 986       if (node->nnodes)
 987         {
 988           node = node->node[--node->nnodes];
 989           pot_order[i++] = node - dfst;
 990         }
 991       else
 992         node = node->up;
 993     }
 994
 995   /* Free the tree.  */
 996
 997   for (i = 0; i < last_basic_block; i++)
 998     if (dfst[i].node)
 999       free (dfst[i].node);
1000
1001   free (dfst);
1002 }
1003
1004 /* Compute the depth first search order on the _reverse_ graph and
1005    store in the array DFS_ORDER, marking the nodes visited in VISITED.
1006    Returns the number of nodes visited.
1007
1008    The computation is split into three pieces:
1009
1010    flow_dfs_compute_reverse_init () creates the necessary data
1011    structures.
1012
1013    flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1014    structures.  The block will start the search.
1015
1016    flow_dfs_compute_reverse_execute () continues (or starts) the
1017    search using the block on the top of the stack, stopping when the
1018    stack is empty.
1019
1020    flow_dfs_compute_reverse_finish () destroys the necessary data
1021    structures.
1022
1023    Thus, the user will probably call ..._init(), call ..._add_bb() to
1024    add a beginning basic block to the stack, call ..._execute(),
1025    possibly add another bb to the stack and again call ..._execute(),
1026    ..., and finally call _finish().  */
1027
1028 /* Initialize the data structures used for depth-first search on the
1029    reverse graph.  If INITIALIZE_STACK is nonzero, the exit block is
1030    added to the basic block stack.  DATA is the current depth-first
1031    search context.  If INITIALIZE_STACK is non-zero, there is an
1032    element on the stack.  */
1033
1034 static void
1035 flow_dfs_compute_reverse_init (data)
1036      depth_first_search_ds data;
1037 {
1038   /* Allocate stack for back-tracking up CFG.  */
1039   data->stack = (basic_block *) xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
1040                                          * sizeof (basic_block));
1041   data->sp = 0;
1042
1043   /* Allocate bitmap to track nodes that have been visited.  */
1044   data->visited_blocks = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
1045
1046   /* None of the nodes in the CFG have been visited yet.  */
1047   sbitmap_zero (data->visited_blocks);
1048
1049   return;
1050 }
1051
1052 /* Add the specified basic block to the top of the dfs data
1053    structures.  When the search continues, it will start at the
1054    block.  */
1055
1056 static void
1057 flow_dfs_compute_reverse_add_bb (data, bb)
1058      depth_first_search_ds data;
1059      basic_block bb;
1060 {
1061   data->stack[data->sp++] = bb;
1062   SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1));
1063 }
1064
1065 /* Continue the depth-first search through the reverse graph starting with the
1066    block at the stack's top and ending when the stack is empty.  Visited nodes
1067    are marked.  Returns an unvisited basic block, or NULL if there is none
1068    available.  */
1069
1070 static basic_block
1071 flow_dfs_compute_reverse_execute (data)
1072      depth_first_search_ds data;
1073 {
1074   basic_block bb;
1075   edge e;
1076
1077   while (data->sp > 0)
1078     {
1079       bb = data->stack[--data->sp];
1080
1081       /* Perform depth-first search on adjacent vertices.  */
1082       for (e = bb->pred; e; e = e->pred_next)
1083         if (!TEST_BIT (data->visited_blocks,
1084                        e->src->index - (INVALID_BLOCK + 1)))
1085           flow_dfs_compute_reverse_add_bb (data, e->src);
1086     }
1087
1088   /* Determine if there are unvisited basic blocks.  */
1089   FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
1090     if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
1091       return bb;
1092
1093   return NULL;
1094 }
1095
1096 /* Destroy the data structures needed for depth-first search on the
1097    reverse graph.  */
1098
1099 static void
1100 flow_dfs_compute_reverse_finish (data)
1101      depth_first_search_ds data;
1102 {
1103   free (data->stack);
1104   sbitmap_free (data->visited_blocks);
1105 }