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