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