gcc/cfganal.c

   1 /* Control flow graph analysis code for GNU compiler.
   2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2003, 2004, 2005, 2006, 2007 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 3, 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 COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* This file contains various simple utilities to analyze the CFG.  */
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "rtl.h"
  27 #include "obstack.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 (const_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 (const_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 lifetime confusion.  */
  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 (const_basic_block bb)
  85 {
  86   rtx insn;
  87
  88   if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
  89       || !single_succ_p (bb))
  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 pre_and_rev_post_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 = XCNEWVEC (int, last_basic_block);
 170   post = XCNEWVEC (int, last_basic_block);
 171
 172   /* Allocate stack for back-tracking up CFG.  */
 173   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
 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 = XNEWVEC (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         {
 311           basic_block dest = e->dest;
 312
 313           if (!(dest->flags & BB_REACHABLE))
 314             {
 315               *tos++ = dest;
 316               dest->flags |= BB_REACHABLE;
 317             }
 318         }
 319     }
 320
 321   free (worklist);
 322 }
 323 \f
 324 /* Functions to access an edge list with a vector representation.
 325    Enough data is kept such that given an index number, the
 326    pred and succ that edge represents can be determined, or
 327    given a pred and a succ, its index number can be returned.
 328    This allows algorithms which consume a lot of memory to
 329    represent the normally full matrix of edge (pred,succ) with a
 330    single indexed vector,  edge (EDGE_INDEX (pred, succ)), with no
 331    wasted space in the client code due to sparse flow graphs.  */
 332
 333 /* This functions initializes the edge list. Basically the entire
 334    flowgraph is processed, and all edges are assigned a number,
 335    and the data structure is filled in.  */
 336
 337 struct edge_list *
 338 create_edge_list (void)
 339 {
 340   struct edge_list *elist;
 341   edge e;
 342   int num_edges;
 343   int block_count;
 344   basic_block bb;
 345   edge_iterator ei;
 346
 347   block_count = n_basic_blocks; /* Include the entry and exit blocks.  */
 348
 349   num_edges = 0;
 350
 351   /* Determine the number of edges in the flow graph by counting successor
 352      edges on each basic block.  */
 353   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 354     {
 355       num_edges += EDGE_COUNT (bb->succs);
 356     }
 357
 358   elist = XNEW (struct edge_list);
 359   elist->num_blocks = block_count;
 360   elist->num_edges = num_edges;
 361   elist->index_to_edge = XNEWVEC (edge, num_edges);
 362
 363   num_edges = 0;
 364
 365   /* Follow successors of blocks, and register these edges.  */
 366   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 367     FOR_EACH_EDGE (e, ei, bb->succs)
 368       elist->index_to_edge[num_edges++] = e;
 369
 370   return elist;
 371 }
 372
 373 /* This function free's memory associated with an edge list.  */
 374
 375 void
 376 free_edge_list (struct edge_list *elist)
 377 {
 378   if (elist)
 379     {
 380       free (elist->index_to_edge);
 381       free (elist);
 382     }
 383 }
 384
 385 /* This function provides debug output showing an edge list.  */
 386
 387 void
 388 print_edge_list (FILE *f, struct edge_list *elist)
 389 {
 390   int x;
 391
 392   fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
 393            elist->num_blocks, elist->num_edges);
 394
 395   for (x = 0; x < elist->num_edges; x++)
 396     {
 397       fprintf (f, " %-4d - edge(", x);
 398       if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
 399         fprintf (f, "entry,");
 400       else
 401         fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
 402
 403       if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
 404         fprintf (f, "exit)\n");
 405       else
 406         fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
 407     }
 408 }
 409
 410 /* This function provides an internal consistency check of an edge list,
 411    verifying that all edges are present, and that there are no
 412    extra edges.  */
 413
 414 void
 415 verify_edge_list (FILE *f, struct edge_list *elist)
 416 {
 417   int pred, succ, index;
 418   edge e;
 419   basic_block bb, p, s;
 420   edge_iterator ei;
 421
 422   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 423     {
 424       FOR_EACH_EDGE (e, ei, bb->succs)
 425         {
 426           pred = e->src->index;
 427           succ = e->dest->index;
 428           index = EDGE_INDEX (elist, e->src, e->dest);
 429           if (index == EDGE_INDEX_NO_EDGE)
 430             {
 431               fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
 432               continue;
 433             }
 434
 435           if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
 436             fprintf (f, "*p* Pred for index %d should be %d not %d\n",
 437                      index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
 438           if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
 439             fprintf (f, "*p* Succ for index %d should be %d not %d\n",
 440                      index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
 441         }
 442     }
 443
 444   /* We've verified that all the edges are in the list, now lets make sure
 445      there are no spurious edges in the list.  */
 446
 447   FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 448     FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 449       {
 450         int found_edge = 0;
 451
 452         FOR_EACH_EDGE (e, ei, p->succs)
 453           if (e->dest == s)
 454             {
 455               found_edge = 1;
 456               break;
 457             }
 458
 459         FOR_EACH_EDGE (e, ei, s->preds)
 460           if (e->src == p)
 461             {
 462               found_edge = 1;
 463               break;
 464             }
 465
 466         if (EDGE_INDEX (elist, p, s)
 467             == EDGE_INDEX_NO_EDGE && found_edge != 0)
 468           fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
 469                    p->index, s->index);
 470         if (EDGE_INDEX (elist, p, s)
 471             != EDGE_INDEX_NO_EDGE && found_edge == 0)
 472           fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
 473                    p->index, s->index, EDGE_INDEX (elist, p, s));
 474       }
 475 }
 476
 477 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
 478    If no such edge exists, return NULL.  */
 479
 480 edge
 481 find_edge (basic_block pred, basic_block succ)
 482 {
 483   edge e;
 484   edge_iterator ei;
 485
 486   if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
 487     {
 488       FOR_EACH_EDGE (e, ei, pred->succs)
 489         if (e->dest == succ)
 490           return e;
 491     }
 492   else
 493     {
 494       FOR_EACH_EDGE (e, ei, succ->preds)
 495         if (e->src == pred)
 496           return e;
 497     }
 498
 499   return NULL;
 500 }
 501
 502 /* This routine will determine what, if any, edge there is between
 503    a specified predecessor and successor.  */
 504
 505 int
 506 find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
 507 {
 508   int x;
 509
 510   for (x = 0; x < NUM_EDGES (edge_list); x++)
 511     if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
 512         && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
 513       return x;
 514
 515   return (EDGE_INDEX_NO_EDGE);
 516 }
 517
 518 /* Dump the list of basic blocks in the bitmap NODES.  */
 519
 520 void
 521 flow_nodes_print (const char *str, const_sbitmap nodes, FILE *file)
 522 {
 523   unsigned int node = 0;
 524   sbitmap_iterator sbi;
 525
 526   if (! nodes)
 527     return;
 528
 529   fprintf (file, "%s { ", str);
 530   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, sbi)
 531     fprintf (file, "%d ", node);
 532   fputs ("}\n", file);
 533 }
 534
 535 /* Dump the list of edges in the array EDGE_LIST.  */
 536
 537 void
 538 flow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file)
 539 {
 540   int i;
 541
 542   if (! edge_list)
 543     return;
 544
 545   fprintf (file, "%s { ", str);
 546   for (i = 0; i < num_edges; i++)
 547     fprintf (file, "%d->%d ", edge_list[i]->src->index,
 548              edge_list[i]->dest->index);
 549
 550   fputs ("}\n", file);
 551 }
 552
 553 \f
 554 /* This routine will remove any fake predecessor edges for a basic block.
 555    When the edge is removed, it is also removed from whatever successor
 556    list it is in.  */
 557
 558 static void
 559 remove_fake_predecessors (basic_block bb)
 560 {
 561   edge e;
 562   edge_iterator ei;
 563
 564   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
 565     {
 566       if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
 567         remove_edge (e);
 568       else
 569         ei_next (&ei);
 570     }
 571 }
 572
 573 /* This routine will remove all fake edges from the flow graph.  If
 574    we remove all fake successors, it will automatically remove all
 575    fake predecessors.  */
 576
 577 void
 578 remove_fake_edges (void)
 579 {
 580   basic_block bb;
 581
 582   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 583     remove_fake_predecessors (bb);
 584 }
 585
 586 /* This routine will remove all fake edges to the EXIT_BLOCK.  */
 587
 588 void
 589 remove_fake_exit_edges (void)
 590 {
 591   remove_fake_predecessors (EXIT_BLOCK_PTR);
 592 }
 593
 594
 595 /* This function will add a fake edge between any block which has no
 596    successors, and the exit block. Some data flow equations require these
 597    edges to exist.  */
 598
 599 void
 600 add_noreturn_fake_exit_edges (void)
 601 {
 602   basic_block bb;
 603
 604   FOR_EACH_BB (bb)
 605     if (EDGE_COUNT (bb->succs) == 0)
 606       make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 607 }
 608
 609 /* This function adds a fake edge between any infinite loops to the
 610    exit block.  Some optimizations require a path from each node to
 611    the exit node.
 612
 613    See also Morgan, Figure 3.10, pp. 82-83.
 614
 615    The current implementation is ugly, not attempting to minimize the
 616    number of inserted fake edges.  To reduce the number of fake edges
 617    to insert, add fake edges from _innermost_ loops containing only
 618    nodes not reachable from the exit block.  */
 619
 620 void
 621 connect_infinite_loops_to_exit (void)
 622 {
 623   basic_block unvisited_block = EXIT_BLOCK_PTR;
 624   struct depth_first_search_dsS dfs_ds;
 625
 626   /* Perform depth-first search in the reverse graph to find nodes
 627      reachable from the exit block.  */
 628   flow_dfs_compute_reverse_init (&dfs_ds);
 629   flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
 630
 631   /* Repeatedly add fake edges, updating the unreachable nodes.  */
 632   while (1)
 633     {
 634       unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds,
 635                                                           unvisited_block);
 636       if (!unvisited_block)
 637         break;
 638
 639       make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
 640       flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
 641     }
 642
 643   flow_dfs_compute_reverse_finish (&dfs_ds);
 644   return;
 645 }
 646 \f
 647 /* Compute reverse top sort order.  This is computing a post order
 648    numbering of the graph.  If INCLUDE_ENTRY_EXIT is true, then then
 649    ENTRY_BLOCK and EXIT_BLOCK are included.  If DELETE_UNREACHABLE is
 650    true, unreachable blocks are deleted.  */
 651
 652 int
 653 post_order_compute (int *post_order, bool include_entry_exit,
 654                     bool delete_unreachable)
 655 {
 656   edge_iterator *stack;
 657   int sp;
 658   int post_order_num = 0;
 659   sbitmap visited;
 660   int count;
 661
 662   if (include_entry_exit)
 663     post_order[post_order_num++] = EXIT_BLOCK;
 664
 665   /* Allocate stack for back-tracking up CFG.  */
 666   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
 667   sp = 0;
 668
 669   /* Allocate bitmap to track nodes that have been visited.  */
 670   visited = sbitmap_alloc (last_basic_block);
 671
 672   /* None of the nodes in the CFG have been visited yet.  */
 673   sbitmap_zero (visited);
 674
 675   /* Push the first edge on to the stack.  */
 676   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 677
 678   while (sp)
 679     {
 680       edge_iterator ei;
 681       basic_block src;
 682       basic_block dest;
 683
 684       /* Look at the edge on the top of the stack.  */
 685       ei = stack[sp - 1];
 686       src = ei_edge (ei)->src;
 687       dest = ei_edge (ei)->dest;
 688
 689       /* Check if the edge destination has been visited yet.  */
 690       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 691         {
 692           /* Mark that we have visited the destination.  */
 693           SET_BIT (visited, dest->index);
 694
 695           if (EDGE_COUNT (dest->succs) > 0)
 696             /* Since the DEST node has been visited for the first
 697                time, check its successors.  */
 698             stack[sp++] = ei_start (dest->succs);
 699           else
 700             post_order[post_order_num++] = dest->index;
 701         }
 702       else
 703         {
 704           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
 705             post_order[post_order_num++] = src->index;
 706
 707           if (!ei_one_before_end_p (ei))
 708             ei_next (&stack[sp - 1]);
 709           else
 710             sp--;
 711         }
 712     }
 713
 714   if (include_entry_exit)
 715     {
 716       post_order[post_order_num++] = ENTRY_BLOCK;
 717       count = post_order_num;
 718     }
 719   else
 720     count = post_order_num + 2;
 721
 722   /* Delete the unreachable blocks if some were found and we are
 723      supposed to do it.  */
 724   if (delete_unreachable && (count != n_basic_blocks))
 725     {
 726       basic_block b;
 727       basic_block next_bb;
 728       for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
 729         {
 730           next_bb = b->next_bb;
 731
 732           if (!(TEST_BIT (visited, b->index)))
 733             delete_basic_block (b);
 734         }
 735
 736       tidy_fallthru_edges ();
 737     }
 738
 739   free (stack);
 740   sbitmap_free (visited);
 741   return post_order_num;
 742 }
 743
 744
 745 /* Helper routine for inverted_post_order_compute.
 746    BB has to belong to a region of CFG
 747    unreachable by inverted traversal from the exit.
 748    i.e. there's no control flow path from ENTRY to EXIT
 749    that contains this BB.
 750    This can happen in two cases - if there's an infinite loop
 751    or if there's a block that has no successor
 752    (call to a function with no return).
 753    Some RTL passes deal with this condition by
 754    calling connect_infinite_loops_to_exit () and/or
 755    add_noreturn_fake_exit_edges ().
 756    However, those methods involve modifying the CFG itself
 757    which may not be desirable.
 758    Hence, we deal with the infinite loop/no return cases
 759    by identifying a unique basic block that can reach all blocks
 760    in such a region by inverted traversal.
 761    This function returns a basic block that guarantees
 762    that all blocks in the region are reachable
 763    by starting an inverted traversal from the returned block.  */
 764
 765 static basic_block
 766 dfs_find_deadend (basic_block bb)
 767 {
 768   sbitmap visited = sbitmap_alloc (last_basic_block);
 769   sbitmap_zero (visited);
 770
 771   for (;;)
 772     {
 773       SET_BIT (visited, bb->index);
 774       if (EDGE_COUNT (bb->succs) == 0
 775           || TEST_BIT (visited, EDGE_SUCC (bb, 0)->dest->index))
 776         {
 777           sbitmap_free (visited);
 778           return bb;
 779         }
 780
 781       bb = EDGE_SUCC (bb, 0)->dest;
 782     }
 783
 784   gcc_unreachable ();
 785 }
 786
 787
 788 /* Compute the reverse top sort order of the inverted CFG
 789    i.e. starting from the exit block and following the edges backward
 790    (from successors to predecessors).
 791    This ordering can be used for forward dataflow problems among others.
 792
 793    This function assumes that all blocks in the CFG are reachable
 794    from the ENTRY (but not necessarily from EXIT).
 795
 796    If there's an infinite loop,
 797    a simple inverted traversal starting from the blocks
 798    with no successors can't visit all blocks.
 799    To solve this problem, we first do inverted traversal
 800    starting from the blocks with no successor.
 801    And if there's any block left that's not visited by the regular
 802    inverted traversal from EXIT,
 803    those blocks are in such problematic region.
 804    Among those, we find one block that has
 805    any visited predecessor (which is an entry into such a region),
 806    and start looking for a "dead end" from that block
 807    and do another inverted traversal from that block.  */
 808
 809 int
 810 inverted_post_order_compute (int *post_order)
 811 {
 812   basic_block bb;
 813   edge_iterator *stack;
 814   int sp;
 815   int post_order_num = 0;
 816   sbitmap visited;
 817
 818   /* Allocate stack for back-tracking up CFG.  */
 819   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
 820   sp = 0;
 821
 822   /* Allocate bitmap to track nodes that have been visited.  */
 823   visited = sbitmap_alloc (last_basic_block);
 824
 825   /* None of the nodes in the CFG have been visited yet.  */
 826   sbitmap_zero (visited);
 827
 828   /* Put all blocks that have no successor into the initial work list.  */
 829   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 830     if (EDGE_COUNT (bb->succs) == 0)
 831       {
 832         /* Push the initial edge on to the stack.  */
 833         if (EDGE_COUNT (bb->preds) > 0)
 834           {
 835             stack[sp++] = ei_start (bb->preds);
 836             SET_BIT (visited, bb->index);
 837           }
 838       }
 839
 840   do
 841     {
 842       bool has_unvisited_bb = false;
 843
 844       /* The inverted traversal loop. */
 845       while (sp)
 846         {
 847           edge_iterator ei;
 848           basic_block pred;
 849
 850           /* Look at the edge on the top of the stack.  */
 851           ei = stack[sp - 1];
 852           bb = ei_edge (ei)->dest;
 853           pred = ei_edge (ei)->src;
 854
 855           /* Check if the predecessor has been visited yet.  */
 856           if (! TEST_BIT (visited, pred->index))
 857             {
 858               /* Mark that we have visited the destination.  */
 859               SET_BIT (visited, pred->index);
 860
 861               if (EDGE_COUNT (pred->preds) > 0)
 862                 /* Since the predecessor node has been visited for the first
 863                    time, check its predecessors.  */
 864                 stack[sp++] = ei_start (pred->preds);
 865               else
 866                 post_order[post_order_num++] = pred->index;
 867             }
 868           else
 869             {
 870               if (bb != EXIT_BLOCK_PTR && ei_one_before_end_p (ei))
 871                 post_order[post_order_num++] = bb->index;
 872
 873               if (!ei_one_before_end_p (ei))
 874                 ei_next (&stack[sp - 1]);
 875               else
 876                 sp--;
 877             }
 878         }
 879
 880       /* Detect any infinite loop and activate the kludge.
 881          Note that this doesn't check EXIT_BLOCK itself
 882          since EXIT_BLOCK is always added after the outer do-while loop.  */
 883       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 884         if (!TEST_BIT (visited, bb->index))
 885           {
 886             has_unvisited_bb = true;
 887
 888             if (EDGE_COUNT (bb->preds) > 0)
 889               {
 890                 edge_iterator ei;
 891                 edge e;
 892                 basic_block visited_pred = NULL;
 893
 894                 /* Find an already visited predecessor.  */
 895                 FOR_EACH_EDGE (e, ei, bb->preds)
 896                   {
 897                     if (TEST_BIT (visited, e->src->index))
 898                       visited_pred = e->src;
 899                   }
 900
 901                 if (visited_pred)
 902                   {
 903                     basic_block be = dfs_find_deadend (bb);
 904                     gcc_assert (be != NULL);
 905                     SET_BIT (visited, be->index);
 906                     stack[sp++] = ei_start (be->preds);
 907                     break;
 908                   }
 909               }
 910           }
 911
 912       if (has_unvisited_bb && sp == 0)
 913         {
 914           /* No blocks are reachable from EXIT at all.
 915              Find a dead-end from the ENTRY, and restart the iteration. */
 916           basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR);
 917           gcc_assert (be != NULL);
 918           SET_BIT (visited, be->index);
 919           stack[sp++] = ei_start (be->preds);
 920         }
 921
 922       /* The only case the below while fires is
 923          when there's an infinite loop.  */
 924     }
 925   while (sp);
 926
 927   /* EXIT_BLOCK is always included.  */
 928   post_order[post_order_num++] = EXIT_BLOCK;
 929
 930   free (stack);
 931   sbitmap_free (visited);
 932   return post_order_num;
 933 }
 934
 935 /* Compute the depth first search order and store in the array
 936   PRE_ORDER if nonzero, marking the nodes visited in VISITED.  If
 937   REV_POST_ORDER is nonzero, return the reverse completion number for each
 938   node.  Returns the number of nodes visited.  A depth first search
 939   tries to get as far away from the starting point as quickly as
 940   possible.
 941
 942   pre_order is a really a preorder numbering of the graph.
 943   rev_post_order is really a reverse postorder numbering of the graph.
 944  */
 945
 946 int
 947 pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
 948                                 bool include_entry_exit)
 949 {
 950   edge_iterator *stack;
 951   int sp;
 952   int pre_order_num = 0;
 953   int rev_post_order_num = n_basic_blocks - 1;
 954   sbitmap visited;
 955
 956   /* Allocate stack for back-tracking up CFG.  */
 957   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
 958   sp = 0;
 959
 960   if (include_entry_exit)
 961     {
 962       if (pre_order)
 963         pre_order[pre_order_num] = ENTRY_BLOCK;
 964       pre_order_num++;
 965       if (rev_post_order)
 966         rev_post_order[rev_post_order_num--] = ENTRY_BLOCK;
 967     }
 968   else
 969     rev_post_order_num -= NUM_FIXED_BLOCKS;
 970
 971   /* Allocate bitmap to track nodes that have been visited.  */
 972   visited = sbitmap_alloc (last_basic_block);
 973
 974   /* None of the nodes in the CFG have been visited yet.  */
 975   sbitmap_zero (visited);
 976
 977   /* Push the first edge on to the stack.  */
 978   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 979
 980   while (sp)
 981     {
 982       edge_iterator ei;
 983       basic_block src;
 984       basic_block dest;
 985
 986       /* Look at the edge on the top of the stack.  */
 987       ei = stack[sp - 1];
 988       src = ei_edge (ei)->src;
 989       dest = ei_edge (ei)->dest;
 990
 991       /* Check if the edge destination has been visited yet.  */
 992       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 993         {
 994           /* Mark that we have visited the destination.  */
 995           SET_BIT (visited, dest->index);
 996
 997           if (pre_order)
 998             pre_order[pre_order_num] = dest->index;
 999
1000           pre_order_num++;
1001
1002           if (EDGE_COUNT (dest->succs) > 0)
1003             /* Since the DEST node has been visited for the first
1004                time, check its successors.  */
1005             stack[sp++] = ei_start (dest->succs);
1006           else if (rev_post_order)
1007             /* There are no successors for the DEST node so assign
1008                its reverse completion number.  */
1009             rev_post_order[rev_post_order_num--] = dest->index;
1010         }
1011       else
1012         {
1013           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR
1014               && rev_post_order)
1015             /* There are no more successors for the SRC node
1016                so assign its reverse completion number.  */
1017             rev_post_order[rev_post_order_num--] = src->index;
1018
1019           if (!ei_one_before_end_p (ei))
1020             ei_next (&stack[sp - 1]);
1021           else
1022             sp--;
1023         }
1024     }
1025
1026   free (stack);
1027   sbitmap_free (visited);
1028
1029   if (include_entry_exit)
1030     {
1031       if (pre_order)
1032         pre_order[pre_order_num] = EXIT_BLOCK;
1033       pre_order_num++;
1034       if (rev_post_order)
1035         rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
1036       /* The number of nodes visited should be the number of blocks.  */
1037       gcc_assert (pre_order_num == n_basic_blocks);
1038     }
1039   else
1040     /* The number of nodes visited should be the number of blocks minus
1041        the entry and exit blocks which are not visited here.  */
1042     gcc_assert (pre_order_num == n_basic_blocks - NUM_FIXED_BLOCKS);
1043
1044   return pre_order_num;
1045 }
1046
1047 /* Compute the depth first search order on the _reverse_ graph and
1048    store in the array DFS_ORDER, marking the nodes visited in VISITED.
1049    Returns the number of nodes visited.
1050
1051    The computation is split into three pieces:
1052
1053    flow_dfs_compute_reverse_init () creates the necessary data
1054    structures.
1055
1056    flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1057    structures.  The block will start the search.
1058
1059    flow_dfs_compute_reverse_execute () continues (or starts) the
1060    search using the block on the top of the stack, stopping when the
1061    stack is empty.
1062
1063    flow_dfs_compute_reverse_finish () destroys the necessary data
1064    structures.
1065
1066    Thus, the user will probably call ..._init(), call ..._add_bb() to
1067    add a beginning basic block to the stack, call ..._execute(),
1068    possibly add another bb to the stack and again call ..._execute(),
1069    ..., and finally call _finish().  */
1070
1071 /* Initialize the data structures used for depth-first search on the
1072    reverse graph.  If INITIALIZE_STACK is nonzero, the exit block is
1073    added to the basic block stack.  DATA is the current depth-first
1074    search context.  If INITIALIZE_STACK is nonzero, there is an
1075    element on the stack.  */
1076
1077 static void
1078 flow_dfs_compute_reverse_init (depth_first_search_ds data)
1079 {
1080   /* Allocate stack for back-tracking up CFG.  */
1081   data->stack = XNEWVEC (basic_block, n_basic_blocks);
1082   data->sp = 0;
1083
1084   /* Allocate bitmap to track nodes that have been visited.  */
1085   data->visited_blocks = sbitmap_alloc (last_basic_block);
1086
1087   /* None of the nodes in the CFG have been visited yet.  */
1088   sbitmap_zero (data->visited_blocks);
1089
1090   return;
1091 }
1092
1093 /* Add the specified basic block to the top of the dfs data
1094    structures.  When the search continues, it will start at the
1095    block.  */
1096
1097 static void
1098 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb)
1099 {
1100   data->stack[data->sp++] = bb;
1101   SET_BIT (data->visited_blocks, bb->index);
1102 }
1103
1104 /* Continue the depth-first search through the reverse graph starting with the
1105    block at the stack's top and ending when the stack is empty.  Visited nodes
1106    are marked.  Returns an unvisited basic block, or NULL if there is none
1107    available.  */
1108
1109 static basic_block
1110 flow_dfs_compute_reverse_execute (depth_first_search_ds data,
1111                                   basic_block last_unvisited)
1112 {
1113   basic_block bb;
1114   edge e;
1115   edge_iterator ei;
1116
1117   while (data->sp > 0)
1118     {
1119       bb = data->stack[--data->sp];
1120
1121       /* Perform depth-first search on adjacent vertices.  */
1122       FOR_EACH_EDGE (e, ei, bb->preds)
1123         if (!TEST_BIT (data->visited_blocks, e->src->index))
1124           flow_dfs_compute_reverse_add_bb (data, e->src);
1125     }
1126
1127   /* Determine if there are unvisited basic blocks.  */
1128   FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
1129     if (!TEST_BIT (data->visited_blocks, bb->index))
1130       return bb;
1131
1132   return NULL;
1133 }
1134
1135 /* Destroy the data structures needed for depth-first search on the
1136    reverse graph.  */
1137
1138 static void
1139 flow_dfs_compute_reverse_finish (depth_first_search_ds data)
1140 {
1141   free (data->stack);
1142   sbitmap_free (data->visited_blocks);
1143 }
1144
1145 /* Performs dfs search from BB over vertices satisfying PREDICATE;
1146    if REVERSE, go against direction of edges.  Returns number of blocks
1147    found and their list in RSLT.  RSLT can contain at most RSLT_MAX items.  */
1148 int
1149 dfs_enumerate_from (basic_block bb, int reverse,
1150                     bool (*predicate) (const_basic_block, const void *),
1151                     basic_block *rslt, int rslt_max, const void *data)
1152 {
1153   basic_block *st, lbb;
1154   int sp = 0, tv = 0;
1155   unsigned size;
1156
1157   /* A bitmap to keep track of visited blocks.  Allocating it each time
1158      this function is called is not possible, since dfs_enumerate_from
1159      is often used on small (almost) disjoint parts of cfg (bodies of
1160      loops), and allocating a large sbitmap would lead to quadratic
1161      behavior.  */
1162   static sbitmap visited;
1163   static unsigned v_size;
1164
1165 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
1166 #define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index))
1167 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
1168
1169   /* Resize the VISITED sbitmap if necessary.  */
1170   size = last_basic_block;
1171   if (size < 10)
1172     size = 10;
1173
1174   if (!visited)
1175     {
1176
1177       visited = sbitmap_alloc (size);
1178       sbitmap_zero (visited);
1179       v_size = size;
1180     }
1181   else if (v_size < size)
1182     {
1183       /* Ensure that we increase the size of the sbitmap exponentially.  */
1184       if (2 * v_size > size)
1185         size = 2 * v_size;
1186
1187       visited = sbitmap_resize (visited, size, 0);
1188       v_size = size;
1189     }
1190
1191   st = XCNEWVEC (basic_block, rslt_max);
1192   rslt[tv++] = st[sp++] = bb;
1193   MARK_VISITED (bb);
1194   while (sp)
1195     {
1196       edge e;
1197       edge_iterator ei;
1198       lbb = st[--sp];
1199       if (reverse)
1200         {
1201           FOR_EACH_EDGE (e, ei, lbb->preds)
1202             if (!VISITED_P (e->src) && predicate (e->src, data))
1203               {
1204                 gcc_assert (tv != rslt_max);
1205                 rslt[tv++] = st[sp++] = e->src;
1206                 MARK_VISITED (e->src);
1207               }
1208         }
1209       else
1210         {
1211           FOR_EACH_EDGE (e, ei, lbb->succs)
1212             if (!VISITED_P (e->dest) && predicate (e->dest, data))
1213               {
1214                 gcc_assert (tv != rslt_max);
1215                 rslt[tv++] = st[sp++] = e->dest;
1216                 MARK_VISITED (e->dest);
1217               }
1218         }
1219     }
1220   free (st);
1221   for (sp = 0; sp < tv; sp++)
1222     UNMARK_VISITED (rslt[sp]);
1223   return tv;
1224 #undef MARK_VISITED
1225 #undef UNMARK_VISITED
1226 #undef VISITED_P
1227 }
1228
1229
1230 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
1231
1232    This algorithm can be found in Timothy Harvey's PhD thesis, at
1233    http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
1234    dominance algorithms.
1235
1236    First, we identify each join point, j (any node with more than one
1237    incoming edge is a join point).
1238
1239    We then examine each predecessor, p, of j and walk up the dominator tree
1240    starting at p.
1241
1242    We stop the walk when we reach j's immediate dominator - j is in the
1243    dominance frontier of each of  the nodes in the walk, except for j's
1244    immediate dominator. Intuitively, all of the rest of j's dominators are
1245    shared by j's predecessors as well.
1246    Since they dominate j, they will not have j in their dominance frontiers.
1247
1248    The number of nodes touched by this algorithm is equal to the size
1249    of the dominance frontiers, no more, no less.
1250 */
1251
1252
1253 static void
1254 compute_dominance_frontiers_1 (bitmap *frontiers)
1255 {
1256   edge p;
1257   edge_iterator ei;
1258   basic_block b;
1259   FOR_EACH_BB (b)
1260     {
1261       if (EDGE_COUNT (b->preds) >= 2)
1262         {
1263           FOR_EACH_EDGE (p, ei, b->preds)
1264             {
1265               basic_block runner = p->src;
1266               basic_block domsb;
1267               if (runner == ENTRY_BLOCK_PTR)
1268                 continue;
1269
1270               domsb = get_immediate_dominator (CDI_DOMINATORS, b);
1271               while (runner != domsb)
1272                 {
1273                   if (bitmap_bit_p (frontiers[runner->index], b->index))
1274                     break;
1275                   bitmap_set_bit (frontiers[runner->index],
1276                                   b->index);
1277                   runner = get_immediate_dominator (CDI_DOMINATORS,
1278                                                     runner);
1279                 }
1280             }
1281         }
1282     }
1283 }
1284
1285
1286 void
1287 compute_dominance_frontiers (bitmap *frontiers)
1288 {
1289   timevar_push (TV_DOM_FRONTIERS);
1290
1291   compute_dominance_frontiers_1 (frontiers);
1292
1293   timevar_pop (TV_DOM_FRONTIERS);
1294 }