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