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   FOR_EACH_EDGE (e, ei, pred->succs)
 482     if (e->dest == succ)
 483       return e;
 484
 485   return NULL;
 486 }
 487
 488 /* This routine will determine what, if any, edge there is between
 489    a specified predecessor and successor.  */
 490
 491 int
 492 find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
 493 {
 494   int x;
 495
 496   for (x = 0; x < NUM_EDGES (edge_list); x++)
 497     if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
 498         && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
 499       return x;
 500
 501   return (EDGE_INDEX_NO_EDGE);
 502 }
 503
 504 /* Dump the list of basic blocks in the bitmap NODES.  */
 505
 506 void
 507 flow_nodes_print (const char *str, const sbitmap nodes, FILE *file)
 508 {
 509   int node;
 510
 511   if (! nodes)
 512     return;
 513
 514   fprintf (file, "%s { ", str);
 515   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
 516   fputs ("}\n", file);
 517 }
 518
 519 /* Dump the list of edges in the array EDGE_LIST.  */
 520
 521 void
 522 flow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file)
 523 {
 524   int i;
 525
 526   if (! edge_list)
 527     return;
 528
 529   fprintf (file, "%s { ", str);
 530   for (i = 0; i < num_edges; i++)
 531     fprintf (file, "%d->%d ", edge_list[i]->src->index,
 532              edge_list[i]->dest->index);
 533
 534   fputs ("}\n", file);
 535 }
 536
 537 \f
 538 /* This routine will remove any fake predecessor edges for a basic block.
 539    When the edge is removed, it is also removed from whatever successor
 540    list it is in.  */
 541
 542 static void
 543 remove_fake_predecessors (basic_block bb)
 544 {
 545   edge e;
 546   edge_iterator ei;
 547
 548   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
 549     {
 550       if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
 551         remove_edge (e);
 552       else
 553         ei_next (&ei);
 554     }
 555 }
 556
 557 /* This routine will remove all fake edges from the flow graph.  If
 558    we remove all fake successors, it will automatically remove all
 559    fake predecessors.  */
 560
 561 void
 562 remove_fake_edges (void)
 563 {
 564   basic_block bb;
 565
 566   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 567     remove_fake_predecessors (bb);
 568 }
 569
 570 /* This routine will remove all fake edges to the EXIT_BLOCK.  */
 571
 572 void
 573 remove_fake_exit_edges (void)
 574 {
 575   remove_fake_predecessors (EXIT_BLOCK_PTR);
 576 }
 577
 578
 579 /* This function will add a fake edge between any block which has no
 580    successors, and the exit block. Some data flow equations require these
 581    edges to exist.  */
 582
 583 void
 584 add_noreturn_fake_exit_edges (void)
 585 {
 586   basic_block bb;
 587
 588   FOR_EACH_BB (bb)
 589     if (EDGE_COUNT (bb->succs) == 0)
 590       make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 591 }
 592
 593 /* This function adds a fake edge between any infinite loops to the
 594    exit block.  Some optimizations require a path from each node to
 595    the exit node.
 596
 597    See also Morgan, Figure 3.10, pp. 82-83.
 598
 599    The current implementation is ugly, not attempting to minimize the
 600    number of inserted fake edges.  To reduce the number of fake edges
 601    to insert, add fake edges from _innermost_ loops containing only
 602    nodes not reachable from the exit block.  */
 603
 604 void
 605 connect_infinite_loops_to_exit (void)
 606 {
 607   basic_block unvisited_block;
 608   struct depth_first_search_dsS dfs_ds;
 609
 610   /* Perform depth-first search in the reverse graph to find nodes
 611      reachable from the exit block.  */
 612   flow_dfs_compute_reverse_init (&dfs_ds);
 613   flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
 614
 615   /* Repeatedly add fake edges, updating the unreachable nodes.  */
 616   while (1)
 617     {
 618       unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds);
 619       if (!unvisited_block)
 620         break;
 621
 622       make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
 623       flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
 624     }
 625
 626   flow_dfs_compute_reverse_finish (&dfs_ds);
 627   return;
 628 }
 629 \f
 630 /* Compute reverse top sort order.  */
 631
 632 void
 633 flow_reverse_top_sort_order_compute (int *rts_order)
 634 {
 635   edge_iterator *stack;
 636   int sp;
 637   int postnum = 0;
 638   sbitmap visited;
 639
 640   /* Allocate stack for back-tracking up CFG.  */
 641   stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
 642   sp = 0;
 643
 644   /* Allocate bitmap to track nodes that have been visited.  */
 645   visited = sbitmap_alloc (last_basic_block);
 646
 647   /* None of the nodes in the CFG have been visited yet.  */
 648   sbitmap_zero (visited);
 649
 650   /* Push the first edge on to the stack.  */
 651   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 652
 653   while (sp)
 654     {
 655       edge_iterator ei;
 656       basic_block src;
 657       basic_block dest;
 658
 659       /* Look at the edge on the top of the stack.  */
 660       ei = stack[sp - 1];
 661       src = ei_edge (ei)->src;
 662       dest = ei_edge (ei)->dest;
 663
 664       /* Check if the edge destination has been visited yet.  */
 665       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 666         {
 667           /* Mark that we have visited the destination.  */
 668           SET_BIT (visited, dest->index);
 669
 670           if (EDGE_COUNT (dest->succs) > 0)
 671             /* Since the DEST node has been visited for the first
 672                time, check its successors.  */
 673             stack[sp++] = ei_start (dest->succs);
 674           else
 675             rts_order[postnum++] = dest->index;
 676         }
 677       else
 678         {
 679           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
 680            rts_order[postnum++] = src->index;
 681
 682           if (!ei_one_before_end_p (ei))
 683             ei_next (&stack[sp - 1]);
 684           else
 685             sp--;
 686         }
 687     }
 688
 689   free (stack);
 690   sbitmap_free (visited);
 691 }
 692
 693 /* Compute the depth first search order and store in the array
 694   DFS_ORDER if nonzero, marking the nodes visited in VISITED.  If
 695   RC_ORDER is nonzero, return the reverse completion number for each
 696   node.  Returns the number of nodes visited.  A depth first search
 697   tries to get as far away from the starting point as quickly as
 698   possible.  */
 699
 700 int
 701 flow_depth_first_order_compute (int *dfs_order, int *rc_order)
 702 {
 703   edge_iterator *stack;
 704   int sp;
 705   int dfsnum = 0;
 706   int rcnum = n_basic_blocks - 1;
 707   sbitmap visited;
 708
 709   /* Allocate stack for back-tracking up CFG.  */
 710   stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
 711   sp = 0;
 712
 713   /* Allocate bitmap to track nodes that have been visited.  */
 714   visited = sbitmap_alloc (last_basic_block);
 715
 716   /* None of the nodes in the CFG have been visited yet.  */
 717   sbitmap_zero (visited);
 718
 719   /* Push the first edge on to the stack.  */
 720   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 721
 722   while (sp)
 723     {
 724       edge_iterator ei;
 725       basic_block src;
 726       basic_block dest;
 727
 728       /* Look at the edge on the top of the stack.  */
 729       ei = stack[sp - 1];
 730       src = ei_edge (ei)->src;
 731       dest = ei_edge (ei)->dest;
 732
 733       /* Check if the edge destination has been visited yet.  */
 734       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 735         {
 736           /* Mark that we have visited the destination.  */
 737           SET_BIT (visited, dest->index);
 738
 739           if (dfs_order)
 740             dfs_order[dfsnum] = dest->index;
 741
 742           dfsnum++;
 743
 744           if (EDGE_COUNT (dest->succs) > 0)
 745             /* Since the DEST node has been visited for the first
 746                time, check its successors.  */
 747             stack[sp++] = ei_start (dest->succs);
 748           else if (rc_order)
 749             /* There are no successors for the DEST node so assign
 750                its reverse completion number.  */
 751             rc_order[rcnum--] = dest->index;
 752         }
 753       else
 754         {
 755           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR
 756               && rc_order)
 757             /* There are no more successors for the SRC node
 758                so assign its reverse completion number.  */
 759             rc_order[rcnum--] = src->index;
 760
 761           if (!ei_one_before_end_p (ei))
 762             ei_next (&stack[sp - 1]);
 763           else
 764             sp--;
 765         }
 766     }
 767
 768   free (stack);
 769   sbitmap_free (visited);
 770
 771   /* The number of nodes visited should be the number of blocks.  */
 772   gcc_assert (dfsnum == n_basic_blocks);
 773
 774   return dfsnum;
 775 }
 776
 777 /* Compute the depth first search order on the _reverse_ graph and
 778    store in the array DFS_ORDER, marking the nodes visited in VISITED.
 779    Returns the number of nodes visited.
 780
 781    The computation is split into three pieces:
 782
 783    flow_dfs_compute_reverse_init () creates the necessary data
 784    structures.
 785
 786    flow_dfs_compute_reverse_add_bb () adds a basic block to the data
 787    structures.  The block will start the search.
 788
 789    flow_dfs_compute_reverse_execute () continues (or starts) the
 790    search using the block on the top of the stack, stopping when the
 791    stack is empty.
 792
 793    flow_dfs_compute_reverse_finish () destroys the necessary data
 794    structures.
 795
 796    Thus, the user will probably call ..._init(), call ..._add_bb() to
 797    add a beginning basic block to the stack, call ..._execute(),
 798    possibly add another bb to the stack and again call ..._execute(),
 799    ..., and finally call _finish().  */
 800
 801 /* Initialize the data structures used for depth-first search on the
 802    reverse graph.  If INITIALIZE_STACK is nonzero, the exit block is
 803    added to the basic block stack.  DATA is the current depth-first
 804    search context.  If INITIALIZE_STACK is nonzero, there is an
 805    element on the stack.  */
 806
 807 static void
 808 flow_dfs_compute_reverse_init (depth_first_search_ds data)
 809 {
 810   /* Allocate stack for back-tracking up CFG.  */
 811   data->stack = xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
 812                          * sizeof (basic_block));
 813   data->sp = 0;
 814
 815   /* Allocate bitmap to track nodes that have been visited.  */
 816   data->visited_blocks = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
 817
 818   /* None of the nodes in the CFG have been visited yet.  */
 819   sbitmap_zero (data->visited_blocks);
 820
 821   return;
 822 }
 823
 824 /* Add the specified basic block to the top of the dfs data
 825    structures.  When the search continues, it will start at the
 826    block.  */
 827
 828 static void
 829 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb)
 830 {
 831   data->stack[data->sp++] = bb;
 832   SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1));
 833 }
 834
 835 /* Continue the depth-first search through the reverse graph starting with the
 836    block at the stack's top and ending when the stack is empty.  Visited nodes
 837    are marked.  Returns an unvisited basic block, or NULL if there is none
 838    available.  */
 839
 840 static basic_block
 841 flow_dfs_compute_reverse_execute (depth_first_search_ds data)
 842 {
 843   basic_block bb;
 844   edge e;
 845   edge_iterator ei;
 846
 847   while (data->sp > 0)
 848     {
 849       bb = data->stack[--data->sp];
 850
 851       /* Perform depth-first search on adjacent vertices.  */
 852       FOR_EACH_EDGE (e, ei, bb->preds)
 853         if (!TEST_BIT (data->visited_blocks,
 854                        e->src->index - (INVALID_BLOCK + 1)))
 855           flow_dfs_compute_reverse_add_bb (data, e->src);
 856     }
 857
 858   /* Determine if there are unvisited basic blocks.  */
 859   FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
 860     if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
 861       return bb;
 862
 863   return NULL;
 864 }
 865
 866 /* Destroy the data structures needed for depth-first search on the
 867    reverse graph.  */
 868
 869 static void
 870 flow_dfs_compute_reverse_finish (depth_first_search_ds data)
 871 {
 872   free (data->stack);
 873   sbitmap_free (data->visited_blocks);
 874 }
 875
 876 /* Performs dfs search from BB over vertices satisfying PREDICATE;
 877    if REVERSE, go against direction of edges.  Returns number of blocks
 878    found and their list in RSLT.  RSLT can contain at most RSLT_MAX items.  */
 879 int
 880 dfs_enumerate_from (basic_block bb, int reverse,
 881                     bool (*predicate) (basic_block, void *),
 882                     basic_block *rslt, int rslt_max, void *data)
 883 {
 884   basic_block *st, lbb;
 885   int sp = 0, tv = 0;
 886
 887   st = xcalloc (rslt_max, sizeof (basic_block));
 888   rslt[tv++] = st[sp++] = bb;
 889   bb->flags |= BB_VISITED;
 890   while (sp)
 891     {
 892       edge e;
 893       edge_iterator ei;
 894       lbb = st[--sp];
 895       if (reverse)
 896         {
 897           FOR_EACH_EDGE (e, ei, lbb->preds)
 898             if (!(e->src->flags & BB_VISITED) && predicate (e->src, data))
 899               {
 900                 gcc_assert (tv != rslt_max);
 901                 rslt[tv++] = st[sp++] = e->src;
 902                 e->src->flags |= BB_VISITED;
 903               }
 904         }
 905       else
 906         {
 907           FOR_EACH_EDGE (e, ei, lbb->succs)
 908             if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data))
 909               {
 910                 gcc_assert (tv != rslt_max);
 911                 rslt[tv++] = st[sp++] = e->dest;
 912                 e->dest->flags |= BB_VISITED;
 913               }
 914         }
 915     }
 916   free (st);
 917   for (sp = 0; sp < tv; sp++)
 918     rslt[sp]->flags &= ~BB_VISITED;
 919   return tv;
 920 }
 921
 922
 923 /* Computing the Dominance Frontier:
 924
 925    As described in Morgan, section 3.5, this may be done simply by
 926    walking the dominator tree bottom-up, computing the frontier for
 927    the children before the parent.  When considering a block B,
 928    there are two cases:
 929
 930    (1) A flow graph edge leaving B that does not lead to a child
 931    of B in the dominator tree must be a block that is either equal
 932    to B or not dominated by B.  Such blocks belong in the frontier
 933    of B.
 934
 935    (2) Consider a block X in the frontier of one of the children C
 936    of B.  If X is not equal to B and is not dominated by B, it
 937    is in the frontier of B.  */
 938
 939 static void
 940 compute_dominance_frontiers_1 (bitmap *frontiers, basic_block bb, sbitmap done)
 941 {
 942   edge e;
 943   edge_iterator ei;
 944   basic_block c;
 945
 946   SET_BIT (done, bb->index);
 947
 948   /* Do the frontier of the children first.  Not all children in the
 949      dominator tree (blocks dominated by this one) are children in the
 950      CFG, so check all blocks.  */
 951   for (c = first_dom_son (CDI_DOMINATORS, bb);
 952        c;
 953        c = next_dom_son (CDI_DOMINATORS, c))
 954     {
 955       if (! TEST_BIT (done, c->index))
 956         compute_dominance_frontiers_1 (frontiers, c, done);
 957     }
 958
 959   /* Find blocks conforming to rule (1) above.  */
 960   FOR_EACH_EDGE (e, ei, bb->succs)
 961     {
 962       if (e->dest == EXIT_BLOCK_PTR)
 963         continue;
 964       if (get_immediate_dominator (CDI_DOMINATORS, e->dest) != bb)
 965         bitmap_set_bit (frontiers[bb->index], e->dest->index);
 966     }
 967
 968   /* Find blocks conforming to rule (2).  */
 969   for (c = first_dom_son (CDI_DOMINATORS, bb);
 970        c;
 971        c = next_dom_son (CDI_DOMINATORS, c))
 972     {
 973       int x;
 974       bitmap_iterator bi;
 975
 976       EXECUTE_IF_SET_IN_BITMAP (frontiers[c->index], 0, x, bi)
 977         {
 978           if (get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (x)) != bb)
 979             bitmap_set_bit (frontiers[bb->index], x);
 980         }
 981     }
 982 }
 983
 984
 985 void
 986 compute_dominance_frontiers (bitmap *frontiers)
 987 {
 988   sbitmap done = sbitmap_alloc (last_basic_block);
 989
 990   timevar_push (TV_DOM_FRONTIERS);
 991
 992   sbitmap_zero (done);
 993
 994   compute_dominance_frontiers_1 (frontiers, EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest, done);
 995
 996   sbitmap_free (done);
 997
 998   timevar_pop (TV_DOM_FRONTIERS);
 999 }
1000