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