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