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 "vec.h"
  35 #include "vecprim.h"
  36 #include "timevar.h"
  37
  38 /* Store the data structures necessary for depth-first search.  */
  39 struct depth_first_search_dsS {
  40   /* stack for backtracking during the algorithm */
  41   basic_block *stack;
  42
  43   /* number of edges in the stack.  That is, positions 0, ..., sp-1
  44      have edges.  */
  45   unsigned int sp;
  46
  47   /* record of basic blocks already seen by depth-first search */
  48   sbitmap visited_blocks;
  49 };
  50 typedef struct depth_first_search_dsS *depth_first_search_ds;
  51
  52 static void flow_dfs_compute_reverse_init (depth_first_search_ds);
  53 static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds,
  54                                              basic_block);
  55 static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds,
  56                                                      basic_block);
  57 static void flow_dfs_compute_reverse_finish (depth_first_search_ds);
  58 static bool flow_active_insn_p (const_rtx);
  59 \f
  60 /* Like active_insn_p, except keep the return value clobber around
  61    even after reload.  */
  62
  63 static bool
  64 flow_active_insn_p (const_rtx insn)
  65 {
  66   if (active_insn_p (insn))
  67     return true;
  68
  69   /* A clobber of the function return value exists for buggy
  70      programs that fail to return a value.  Its effect is to
  71      keep the return value from being live across the entire
  72      function.  If we allow it to be skipped, we introduce the
  73      possibility for register lifetime confusion.  */
  74   if (GET_CODE (PATTERN (insn)) == CLOBBER
  75       && REG_P (XEXP (PATTERN (insn), 0))
  76       && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
  77     return true;
  78
  79   return false;
  80 }
  81
  82 /* Return true if the block has no effect and only forwards control flow to
  83    its single destination.  */
  84
  85 bool
  86 forwarder_block_p (const_basic_block bb)
  87 {
  88   rtx insn;
  89
  90   if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
  91       || !single_succ_p (bb))
  92     return false;
  93
  94   for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
  95     if (INSN_P (insn) && flow_active_insn_p (insn))
  96       return false;
  97
  98   return (!INSN_P (insn)
  99           || (JUMP_P (insn) && simplejump_p (insn))
 100           || !flow_active_insn_p (insn));
 101 }
 102
 103 /* Return nonzero if we can reach target from src by falling through.  */
 104
 105 bool
 106 can_fallthru (basic_block src, basic_block target)
 107 {
 108   rtx insn = BB_END (src);
 109   rtx insn2;
 110   edge e;
 111   edge_iterator ei;
 112
 113   if (target == EXIT_BLOCK_PTR)
 114     return true;
 115   if (src->next_bb != target)
 116     return 0;
 117   FOR_EACH_EDGE (e, ei, src->succs)
 118     if (e->dest == EXIT_BLOCK_PTR
 119         && e->flags & EDGE_FALLTHRU)
 120       return 0;
 121
 122   insn2 = BB_HEAD (target);
 123   if (insn2 && !active_insn_p (insn2))
 124     insn2 = next_active_insn (insn2);
 125
 126   /* ??? Later we may add code to move jump tables offline.  */
 127   return next_active_insn (insn) == insn2;
 128 }
 129
 130 /* Return nonzero if we could reach target from src by falling through,
 131    if the target was made adjacent.  If we already have a fall-through
 132    edge to the exit block, we can't do that.  */
 133 bool
 134 could_fall_through (basic_block src, basic_block target)
 135 {
 136   edge e;
 137   edge_iterator ei;
 138
 139   if (target == EXIT_BLOCK_PTR)
 140     return true;
 141   FOR_EACH_EDGE (e, ei, src->succs)
 142     if (e->dest == EXIT_BLOCK_PTR
 143         && e->flags & EDGE_FALLTHRU)
 144       return 0;
 145   return true;
 146 }
 147 \f
 148 /* Mark the back edges in DFS traversal.
 149    Return nonzero if a loop (natural or otherwise) is present.
 150    Inspired by Depth_First_Search_PP described in:
 151
 152      Advanced Compiler Design and Implementation
 153      Steven Muchnick
 154      Morgan Kaufmann, 1997
 155
 156    and heavily borrowed from pre_and_rev_post_order_compute.  */
 157
 158 bool
 159 mark_dfs_back_edges (void)
 160 {
 161   edge_iterator *stack;
 162   int *pre;
 163   int *post;
 164   int sp;
 165   int prenum = 1;
 166   int postnum = 1;
 167   sbitmap visited;
 168   bool found = false;
 169
 170   /* Allocate the preorder and postorder number arrays.  */
 171   pre = XCNEWVEC (int, last_basic_block);
 172   post = XCNEWVEC (int, last_basic_block);
 173
 174   /* Allocate stack for back-tracking up CFG.  */
 175   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
 176   sp = 0;
 177
 178   /* Allocate bitmap to track nodes that have been visited.  */
 179   visited = sbitmap_alloc (last_basic_block);
 180
 181   /* None of the nodes in the CFG have been visited yet.  */
 182   sbitmap_zero (visited);
 183
 184   /* Push the first edge on to the stack.  */
 185   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 186
 187   while (sp)
 188     {
 189       edge_iterator ei;
 190       basic_block src;
 191       basic_block dest;
 192
 193       /* Look at the edge on the top of the stack.  */
 194       ei = stack[sp - 1];
 195       src = ei_edge (ei)->src;
 196       dest = ei_edge (ei)->dest;
 197       ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
 198
 199       /* Check if the edge destination has been visited yet.  */
 200       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 201         {
 202           /* Mark that we have visited the destination.  */
 203           SET_BIT (visited, dest->index);
 204
 205           pre[dest->index] = prenum++;
 206           if (EDGE_COUNT (dest->succs) > 0)
 207             {
 208               /* Since the DEST node has been visited for the first
 209                  time, check its successors.  */
 210               stack[sp++] = ei_start (dest->succs);
 211             }
 212           else
 213             post[dest->index] = postnum++;
 214         }
 215       else
 216         {
 217           if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
 218               && pre[src->index] >= pre[dest->index]
 219               && post[dest->index] == 0)
 220             ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true;
 221
 222           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
 223             post[src->index] = postnum++;
 224
 225           if (!ei_one_before_end_p (ei))
 226             ei_next (&stack[sp - 1]);
 227           else
 228             sp--;
 229         }
 230     }
 231
 232   free (pre);
 233   free (post);
 234   free (stack);
 235   sbitmap_free (visited);
 236
 237   return found;
 238 }
 239
 240 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru.  */
 241
 242 void
 243 set_edge_can_fallthru_flag (void)
 244 {
 245   basic_block bb;
 246
 247   FOR_EACH_BB (bb)
 248     {
 249       edge e;
 250       edge_iterator ei;
 251
 252       FOR_EACH_EDGE (e, ei, bb->succs)
 253         {
 254           e->flags &= ~EDGE_CAN_FALLTHRU;
 255
 256           /* The FALLTHRU edge is also CAN_FALLTHRU edge.  */
 257           if (e->flags & EDGE_FALLTHRU)
 258             e->flags |= EDGE_CAN_FALLTHRU;
 259         }
 260
 261       /* If the BB ends with an invertible condjump all (2) edges are
 262          CAN_FALLTHRU edges.  */
 263       if (EDGE_COUNT (bb->succs) != 2)
 264         continue;
 265       if (!any_condjump_p (BB_END (bb)))
 266         continue;
 267       if (!invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0))
 268         continue;
 269       invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0);
 270       EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU;
 271       EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU;
 272     }
 273 }
 274
 275 /* Find unreachable blocks.  An unreachable block will have 0 in
 276    the reachable bit in block->flags.  A nonzero value indicates the
 277    block is reachable.  */
 278
 279 void
 280 find_unreachable_blocks (void)
 281 {
 282   edge e;
 283   edge_iterator ei;
 284   basic_block *tos, *worklist, bb;
 285
 286   tos = worklist = XNEWVEC (basic_block, n_basic_blocks);
 287
 288   /* Clear all the reachability flags.  */
 289
 290   FOR_EACH_BB (bb)
 291     bb->flags &= ~BB_REACHABLE;
 292
 293   /* Add our starting points to the worklist.  Almost always there will
 294      be only one.  It isn't inconceivable that we might one day directly
 295      support Fortran alternate entry points.  */
 296
 297   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 298     {
 299       *tos++ = e->dest;
 300
 301       /* Mark the block reachable.  */
 302       e->dest->flags |= BB_REACHABLE;
 303     }
 304
 305   /* Iterate: find everything reachable from what we've already seen.  */
 306
 307   while (tos != worklist)
 308     {
 309       basic_block b = *--tos;
 310
 311       FOR_EACH_EDGE (e, ei, b->succs)
 312         {
 313           basic_block dest = e->dest;
 314
 315           if (!(dest->flags & BB_REACHABLE))
 316             {
 317               *tos++ = dest;
 318               dest->flags |= BB_REACHABLE;
 319             }
 320         }
 321     }
 322
 323   free (worklist);
 324 }
 325 \f
 326 /* Functions to access an edge list with a vector representation.
 327    Enough data is kept such that given an index number, the
 328    pred and succ that edge represents can be determined, or
 329    given a pred and a succ, its index number can be returned.
 330    This allows algorithms which consume a lot of memory to
 331    represent the normally full matrix of edge (pred,succ) with a
 332    single indexed vector,  edge (EDGE_INDEX (pred, succ)), with no
 333    wasted space in the client code due to sparse flow graphs.  */
 334
 335 /* This functions initializes the edge list. Basically the entire
 336    flowgraph is processed, and all edges are assigned a number,
 337    and the data structure is filled in.  */
 338
 339 struct edge_list *
 340 create_edge_list (void)
 341 {
 342   struct edge_list *elist;
 343   edge e;
 344   int num_edges;
 345   int block_count;
 346   basic_block bb;
 347   edge_iterator ei;
 348
 349   block_count = n_basic_blocks; /* Include the entry and exit blocks.  */
 350
 351   num_edges = 0;
 352
 353   /* Determine the number of edges in the flow graph by counting successor
 354      edges on each basic block.  */
 355   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 356     {
 357       num_edges += EDGE_COUNT (bb->succs);
 358     }
 359
 360   elist = XNEW (struct edge_list);
 361   elist->num_blocks = block_count;
 362   elist->num_edges = num_edges;
 363   elist->index_to_edge = XNEWVEC (edge, num_edges);
 364
 365   num_edges = 0;
 366
 367   /* Follow successors of blocks, and register these edges.  */
 368   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 369     FOR_EACH_EDGE (e, ei, bb->succs)
 370       elist->index_to_edge[num_edges++] = e;
 371
 372   return elist;
 373 }
 374
 375 /* This function free's memory associated with an edge list.  */
 376
 377 void
 378 free_edge_list (struct edge_list *elist)
 379 {
 380   if (elist)
 381     {
 382       free (elist->index_to_edge);
 383       free (elist);
 384     }
 385 }
 386
 387 /* This function provides debug output showing an edge list.  */
 388
 389 void
 390 print_edge_list (FILE *f, struct edge_list *elist)
 391 {
 392   int x;
 393
 394   fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
 395            elist->num_blocks, elist->num_edges);
 396
 397   for (x = 0; x < elist->num_edges; x++)
 398     {
 399       fprintf (f, " %-4d - edge(", x);
 400       if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
 401         fprintf (f, "entry,");
 402       else
 403         fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
 404
 405       if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
 406         fprintf (f, "exit)\n");
 407       else
 408         fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
 409     }
 410 }
 411
 412 /* This function provides an internal consistency check of an edge list,
 413    verifying that all edges are present, and that there are no
 414    extra edges.  */
 415
 416 void
 417 verify_edge_list (FILE *f, struct edge_list *elist)
 418 {
 419   int pred, succ, index;
 420   edge e;
 421   basic_block bb, p, s;
 422   edge_iterator ei;
 423
 424   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 425     {
 426       FOR_EACH_EDGE (e, ei, bb->succs)
 427         {
 428           pred = e->src->index;
 429           succ = e->dest->index;
 430           index = EDGE_INDEX (elist, e->src, e->dest);
 431           if (index == EDGE_INDEX_NO_EDGE)
 432             {
 433               fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
 434               continue;
 435             }
 436
 437           if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
 438             fprintf (f, "*p* Pred for index %d should be %d not %d\n",
 439                      index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
 440           if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
 441             fprintf (f, "*p* Succ for index %d should be %d not %d\n",
 442                      index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
 443         }
 444     }
 445
 446   /* We've verified that all the edges are in the list, now lets make sure
 447      there are no spurious edges in the list.  */
 448
 449   FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 450     FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 451       {
 452         int found_edge = 0;
 453
 454         FOR_EACH_EDGE (e, ei, p->succs)
 455           if (e->dest == s)
 456             {
 457               found_edge = 1;
 458               break;
 459             }
 460
 461         FOR_EACH_EDGE (e, ei, s->preds)
 462           if (e->src == p)
 463             {
 464               found_edge = 1;
 465               break;
 466             }
 467
 468         if (EDGE_INDEX (elist, p, s)
 469             == EDGE_INDEX_NO_EDGE && found_edge != 0)
 470           fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
 471                    p->index, s->index);
 472         if (EDGE_INDEX (elist, p, s)
 473             != EDGE_INDEX_NO_EDGE && found_edge == 0)
 474           fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
 475                    p->index, s->index, EDGE_INDEX (elist, p, s));
 476       }
 477 }
 478
 479 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
 480    If no such edge exists, return NULL.  */
 481
 482 edge
 483 find_edge (basic_block pred, basic_block succ)
 484 {
 485   edge e;
 486   edge_iterator ei;
 487
 488   if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
 489     {
 490       FOR_EACH_EDGE (e, ei, pred->succs)
 491         if (e->dest == succ)
 492           return e;
 493     }
 494   else
 495     {
 496       FOR_EACH_EDGE (e, ei, succ->preds)
 497         if (e->src == pred)
 498           return e;
 499     }
 500
 501   return NULL;
 502 }
 503
 504 /* This routine will determine what, if any, edge there is between
 505    a specified predecessor and successor.  */
 506
 507 int
 508 find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
 509 {
 510   int x;
 511
 512   for (x = 0; x < NUM_EDGES (edge_list); x++)
 513     if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
 514         && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
 515       return x;
 516
 517   return (EDGE_INDEX_NO_EDGE);
 518 }
 519
 520 /* Dump the list of basic blocks in the bitmap NODES.  */
 521
 522 void
 523 flow_nodes_print (const char *str, const_sbitmap nodes, FILE *file)
 524 {
 525   unsigned int node = 0;
 526   sbitmap_iterator sbi;
 527
 528   if (! nodes)
 529     return;
 530
 531   fprintf (file, "%s { ", str);
 532   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, sbi)
 533     fprintf (file, "%d ", node);
 534   fputs ("}\n", file);
 535 }
 536
 537 /* Dump the list of edges in the array EDGE_LIST.  */
 538
 539 void
 540 flow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file)
 541 {
 542   int i;
 543
 544   if (! edge_list)
 545     return;
 546
 547   fprintf (file, "%s { ", str);
 548   for (i = 0; i < num_edges; i++)
 549     fprintf (file, "%d->%d ", edge_list[i]->src->index,
 550              edge_list[i]->dest->index);
 551
 552   fputs ("}\n", file);
 553 }
 554
 555 \f
 556 /* This routine will remove any fake predecessor edges for a basic block.
 557    When the edge is removed, it is also removed from whatever successor
 558    list it is in.  */
 559
 560 static void
 561 remove_fake_predecessors (basic_block bb)
 562 {
 563   edge e;
 564   edge_iterator ei;
 565
 566   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
 567     {
 568       if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
 569         remove_edge (e);
 570       else
 571         ei_next (&ei);
 572     }
 573 }
 574
 575 /* This routine will remove all fake edges from the flow graph.  If
 576    we remove all fake successors, it will automatically remove all
 577    fake predecessors.  */
 578
 579 void
 580 remove_fake_edges (void)
 581 {
 582   basic_block bb;
 583
 584   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 585     remove_fake_predecessors (bb);
 586 }
 587
 588 /* This routine will remove all fake edges to the EXIT_BLOCK.  */
 589
 590 void
 591 remove_fake_exit_edges (void)
 592 {
 593   remove_fake_predecessors (EXIT_BLOCK_PTR);
 594 }
 595
 596
 597 /* This function will add a fake edge between any block which has no
 598    successors, and the exit block. Some data flow equations require these
 599    edges to exist.  */
 600
 601 void
 602 add_noreturn_fake_exit_edges (void)
 603 {
 604   basic_block bb;
 605
 606   FOR_EACH_BB (bb)
 607     if (EDGE_COUNT (bb->succs) == 0)
 608       make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 609 }
 610
 611 /* This function adds a fake edge between any infinite loops to the
 612    exit block.  Some optimizations require a path from each node to
 613    the exit node.
 614
 615    See also Morgan, Figure 3.10, pp. 82-83.
 616
 617    The current implementation is ugly, not attempting to minimize the
 618    number of inserted fake edges.  To reduce the number of fake edges
 619    to insert, add fake edges from _innermost_ loops containing only
 620    nodes not reachable from the exit block.  */
 621
 622 void
 623 connect_infinite_loops_to_exit (void)
 624 {
 625   basic_block unvisited_block = EXIT_BLOCK_PTR;
 626   struct depth_first_search_dsS dfs_ds;
 627
 628   /* Perform depth-first search in the reverse graph to find nodes
 629      reachable from the exit block.  */
 630   flow_dfs_compute_reverse_init (&dfs_ds);
 631   flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
 632
 633   /* Repeatedly add fake edges, updating the unreachable nodes.  */
 634   while (1)
 635     {
 636       unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds,
 637                                                           unvisited_block);
 638       if (!unvisited_block)
 639         break;
 640
 641       make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
 642       flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
 643     }
 644
 645   flow_dfs_compute_reverse_finish (&dfs_ds);
 646   return;
 647 }
 648 \f
 649 /* Compute reverse top sort order.  This is computing a post order
 650    numbering of the graph.  If INCLUDE_ENTRY_EXIT is true, then then
 651    ENTRY_BLOCK and EXIT_BLOCK are included.  If DELETE_UNREACHABLE is
 652    true, unreachable blocks are deleted.  */
 653
 654 int
 655 post_order_compute (int *post_order, bool include_entry_exit,
 656                     bool delete_unreachable)
 657 {
 658   edge_iterator *stack;
 659   int sp;
 660   int post_order_num = 0;
 661   sbitmap visited;
 662   int count;
 663
 664   if (include_entry_exit)
 665     post_order[post_order_num++] = EXIT_BLOCK;
 666
 667   /* Allocate stack for back-tracking up CFG.  */
 668   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
 669   sp = 0;
 670
 671   /* Allocate bitmap to track nodes that have been visited.  */
 672   visited = sbitmap_alloc (last_basic_block);
 673
 674   /* None of the nodes in the CFG have been visited yet.  */
 675   sbitmap_zero (visited);
 676
 677   /* Push the first edge on to the stack.  */
 678   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 679
 680   while (sp)
 681     {
 682       edge_iterator ei;
 683       basic_block src;
 684       basic_block dest;
 685
 686       /* Look at the edge on the top of the stack.  */
 687       ei = stack[sp - 1];
 688       src = ei_edge (ei)->src;
 689       dest = ei_edge (ei)->dest;
 690
 691       /* Check if the edge destination has been visited yet.  */
 692       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 693         {
 694           /* Mark that we have visited the destination.  */
 695           SET_BIT (visited, dest->index);
 696
 697           if (EDGE_COUNT (dest->succs) > 0)
 698             /* Since the DEST node has been visited for the first
 699                time, check its successors.  */
 700             stack[sp++] = ei_start (dest->succs);
 701           else
 702             post_order[post_order_num++] = dest->index;
 703         }
 704       else
 705         {
 706           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
 707             post_order[post_order_num++] = src->index;
 708
 709           if (!ei_one_before_end_p (ei))
 710             ei_next (&stack[sp - 1]);
 711           else
 712             sp--;
 713         }
 714     }
 715
 716   if (include_entry_exit)
 717     {
 718       post_order[post_order_num++] = ENTRY_BLOCK;
 719       count = post_order_num;
 720     }
 721   else
 722     count = post_order_num + 2;
 723
 724   /* Delete the unreachable blocks if some were found and we are
 725      supposed to do it.  */
 726   if (delete_unreachable && (count != n_basic_blocks))
 727     {
 728       basic_block b;
 729       basic_block next_bb;
 730       for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
 731         {
 732           next_bb = b->next_bb;
 733
 734           if (!(TEST_BIT (visited, b->index)))
 735             delete_basic_block (b);
 736         }
 737
 738       tidy_fallthru_edges ();
 739     }
 740
 741   free (stack);
 742   sbitmap_free (visited);
 743   return post_order_num;
 744 }
 745
 746
 747 /* Helper routine for inverted_post_order_compute.
 748    BB has to belong to a region of CFG
 749    unreachable by inverted traversal from the exit.
 750    i.e. there's no control flow path from ENTRY to EXIT
 751    that contains this BB.
 752    This can happen in two cases - if there's an infinite loop
 753    or if there's a block that has no successor
 754    (call to a function with no return).
 755    Some RTL passes deal with this condition by
 756    calling connect_infinite_loops_to_exit () and/or
 757    add_noreturn_fake_exit_edges ().
 758    However, those methods involve modifying the CFG itself
 759    which may not be desirable.
 760    Hence, we deal with the infinite loop/no return cases
 761    by identifying a unique basic block that can reach all blocks
 762    in such a region by inverted traversal.
 763    This function returns a basic block that guarantees
 764    that all blocks in the region are reachable
 765    by starting an inverted traversal from the returned block.  */
 766
 767 static basic_block
 768 dfs_find_deadend (basic_block bb)
 769 {
 770   sbitmap visited = sbitmap_alloc (last_basic_block);
 771   sbitmap_zero (visited);
 772
 773   for (;;)
 774     {
 775       SET_BIT (visited, bb->index);
 776       if (EDGE_COUNT (bb->succs) == 0
 777           || TEST_BIT (visited, EDGE_SUCC (bb, 0)->dest->index))
 778         {
 779           sbitmap_free (visited);
 780           return bb;
 781         }
 782
 783       bb = EDGE_SUCC (bb, 0)->dest;
 784     }
 785
 786   gcc_unreachable ();
 787 }
 788
 789
 790 /* Compute the reverse top sort order of the inverted CFG
 791    i.e. starting from the exit block and following the edges backward
 792    (from successors to predecessors).
 793    This ordering can be used for forward dataflow problems among others.
 794
 795    This function assumes that all blocks in the CFG are reachable
 796    from the ENTRY (but not necessarily from EXIT).
 797
 798    If there's an infinite loop,
 799    a simple inverted traversal starting from the blocks
 800    with no successors can't visit all blocks.
 801    To solve this problem, we first do inverted traversal
 802    starting from the blocks with no successor.
 803    And if there's any block left that's not visited by the regular
 804    inverted traversal from EXIT,
 805    those blocks are in such problematic region.
 806    Among those, we find one block that has
 807    any visited predecessor (which is an entry into such a region),
 808    and start looking for a "dead end" from that block
 809    and do another inverted traversal from that block.  */
 810
 811 int
 812 inverted_post_order_compute (int *post_order)
 813 {
 814   basic_block bb;
 815   edge_iterator *stack;
 816   int sp;
 817   int post_order_num = 0;
 818   sbitmap visited;
 819
 820   /* Allocate stack for back-tracking up CFG.  */
 821   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
 822   sp = 0;
 823
 824   /* Allocate bitmap to track nodes that have been visited.  */
 825   visited = sbitmap_alloc (last_basic_block);
 826
 827   /* None of the nodes in the CFG have been visited yet.  */
 828   sbitmap_zero (visited);
 829
 830   /* Put all blocks that have no successor into the initial work list.  */
 831   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 832     if (EDGE_COUNT (bb->succs) == 0)
 833       {
 834         /* Push the initial edge on to the stack.  */
 835         if (EDGE_COUNT (bb->preds) > 0)
 836           {
 837             stack[sp++] = ei_start (bb->preds);
 838             SET_BIT (visited, bb->index);
 839           }
 840       }
 841
 842   do
 843     {
 844       bool has_unvisited_bb = false;
 845
 846       /* The inverted traversal loop. */
 847       while (sp)
 848         {
 849           edge_iterator ei;
 850           basic_block pred;
 851
 852           /* Look at the edge on the top of the stack.  */
 853           ei = stack[sp - 1];
 854           bb = ei_edge (ei)->dest;
 855           pred = ei_edge (ei)->src;
 856
 857           /* Check if the predecessor has been visited yet.  */
 858           if (! TEST_BIT (visited, pred->index))
 859             {
 860               /* Mark that we have visited the destination.  */
 861               SET_BIT (visited, pred->index);
 862
 863               if (EDGE_COUNT (pred->preds) > 0)
 864                 /* Since the predecessor node has been visited for the first
 865                    time, check its predecessors.  */
 866                 stack[sp++] = ei_start (pred->preds);
 867               else
 868                 post_order[post_order_num++] = pred->index;
 869             }
 870           else
 871             {
 872               if (bb != EXIT_BLOCK_PTR && ei_one_before_end_p (ei))
 873                 post_order[post_order_num++] = bb->index;
 874
 875               if (!ei_one_before_end_p (ei))
 876                 ei_next (&stack[sp - 1]);
 877               else
 878                 sp--;
 879             }
 880         }
 881
 882       /* Detect any infinite loop and activate the kludge.
 883          Note that this doesn't check EXIT_BLOCK itself
 884          since EXIT_BLOCK is always added after the outer do-while loop.  */
 885       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 886         if (!TEST_BIT (visited, bb->index))
 887           {
 888             has_unvisited_bb = true;
 889
 890             if (EDGE_COUNT (bb->preds) > 0)
 891               {
 892                 edge_iterator ei;
 893                 edge e;
 894                 basic_block visited_pred = NULL;
 895
 896                 /* Find an already visited predecessor.  */
 897                 FOR_EACH_EDGE (e, ei, bb->preds)
 898                   {
 899                     if (TEST_BIT (visited, e->src->index))
 900                       visited_pred = e->src;
 901                   }
 902
 903                 if (visited_pred)
 904                   {
 905                     basic_block be = dfs_find_deadend (bb);
 906                     gcc_assert (be != NULL);
 907                     SET_BIT (visited, be->index);
 908                     stack[sp++] = ei_start (be->preds);
 909                     break;
 910                   }
 911               }
 912           }
 913
 914       if (has_unvisited_bb && sp == 0)
 915         {
 916           /* No blocks are reachable from EXIT at all.
 917              Find a dead-end from the ENTRY, and restart the iteration. */
 918           basic_block be = dfs_find_deadend (ENTRY_BLOCK_PTR);
 919           gcc_assert (be != NULL);
 920           SET_BIT (visited, be->index);
 921           stack[sp++] = ei_start (be->preds);
 922         }
 923
 924       /* The only case the below while fires is
 925          when there's an infinite loop.  */
 926     }
 927   while (sp);
 928
 929   /* EXIT_BLOCK is always included.  */
 930   post_order[post_order_num++] = EXIT_BLOCK;
 931
 932   free (stack);
 933   sbitmap_free (visited);
 934   return post_order_num;
 935 }
 936
 937 /* Compute the depth first search order and store in the array
 938   PRE_ORDER if nonzero, marking the nodes visited in VISITED.  If
 939   REV_POST_ORDER is nonzero, return the reverse completion number for each
 940   node.  Returns the number of nodes visited.  A depth first search
 941   tries to get as far away from the starting point as quickly as
 942   possible.
 943
 944   pre_order is a really a preorder numbering of the graph.
 945   rev_post_order is really a reverse postorder numbering of the graph.
 946  */
 947
 948 int
 949 pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order,
 950                                 bool include_entry_exit)
 951 {
 952   edge_iterator *stack;
 953   int sp;
 954   int pre_order_num = 0;
 955   int rev_post_order_num = n_basic_blocks - 1;
 956   sbitmap visited;
 957
 958   /* Allocate stack for back-tracking up CFG.  */
 959   stack = XNEWVEC (edge_iterator, n_basic_blocks + 1);
 960   sp = 0;
 961
 962   if (include_entry_exit)
 963     {
 964       if (pre_order)
 965         pre_order[pre_order_num] = ENTRY_BLOCK;
 966       pre_order_num++;
 967       if (rev_post_order)
 968         rev_post_order[rev_post_order_num--] = ENTRY_BLOCK;
 969     }
 970   else
 971     rev_post_order_num -= NUM_FIXED_BLOCKS;
 972
 973   /* Allocate bitmap to track nodes that have been visited.  */
 974   visited = sbitmap_alloc (last_basic_block);
 975
 976   /* None of the nodes in the CFG have been visited yet.  */
 977   sbitmap_zero (visited);
 978
 979   /* Push the first edge on to the stack.  */
 980   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 981
 982   while (sp)
 983     {
 984       edge_iterator ei;
 985       basic_block src;
 986       basic_block dest;
 987
 988       /* Look at the edge on the top of the stack.  */
 989       ei = stack[sp - 1];
 990       src = ei_edge (ei)->src;
 991       dest = ei_edge (ei)->dest;
 992
 993       /* Check if the edge destination has been visited yet.  */
 994       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 995         {
 996           /* Mark that we have visited the destination.  */
 997           SET_BIT (visited, dest->index);
 998
 999           if (pre_order)
1000             pre_order[pre_order_num] = dest->index;
1001
1002           pre_order_num++;
1003
1004           if (EDGE_COUNT (dest->succs) > 0)
1005             /* Since the DEST node has been visited for the first
1006                time, check its successors.  */
1007             stack[sp++] = ei_start (dest->succs);
1008           else if (rev_post_order)
1009             /* There are no successors for the DEST node so assign
1010                its reverse completion number.  */
1011             rev_post_order[rev_post_order_num--] = dest->index;
1012         }
1013       else
1014         {
1015           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR
1016               && rev_post_order)
1017             /* There are no more successors for the SRC node
1018                so assign its reverse completion number.  */
1019             rev_post_order[rev_post_order_num--] = src->index;
1020
1021           if (!ei_one_before_end_p (ei))
1022             ei_next (&stack[sp - 1]);
1023           else
1024             sp--;
1025         }
1026     }
1027
1028   free (stack);
1029   sbitmap_free (visited);
1030
1031   if (include_entry_exit)
1032     {
1033       if (pre_order)
1034         pre_order[pre_order_num] = EXIT_BLOCK;
1035       pre_order_num++;
1036       if (rev_post_order)
1037         rev_post_order[rev_post_order_num--] = EXIT_BLOCK;
1038       /* The number of nodes visited should be the number of blocks.  */
1039       gcc_assert (pre_order_num == n_basic_blocks);
1040     }
1041   else
1042     /* The number of nodes visited should be the number of blocks minus
1043        the entry and exit blocks which are not visited here.  */
1044     gcc_assert (pre_order_num == n_basic_blocks - NUM_FIXED_BLOCKS);
1045
1046   return pre_order_num;
1047 }
1048
1049 /* Compute the depth first search order on the _reverse_ graph and
1050    store in the array DFS_ORDER, marking the nodes visited in VISITED.
1051    Returns the number of nodes visited.
1052
1053    The computation is split into three pieces:
1054
1055    flow_dfs_compute_reverse_init () creates the necessary data
1056    structures.
1057
1058    flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1059    structures.  The block will start the search.
1060
1061    flow_dfs_compute_reverse_execute () continues (or starts) the
1062    search using the block on the top of the stack, stopping when the
1063    stack is empty.
1064
1065    flow_dfs_compute_reverse_finish () destroys the necessary data
1066    structures.
1067
1068    Thus, the user will probably call ..._init(), call ..._add_bb() to
1069    add a beginning basic block to the stack, call ..._execute(),
1070    possibly add another bb to the stack and again call ..._execute(),
1071    ..., and finally call _finish().  */
1072
1073 /* Initialize the data structures used for depth-first search on the
1074    reverse graph.  If INITIALIZE_STACK is nonzero, the exit block is
1075    added to the basic block stack.  DATA is the current depth-first
1076    search context.  If INITIALIZE_STACK is nonzero, there is an
1077    element on the stack.  */
1078
1079 static void
1080 flow_dfs_compute_reverse_init (depth_first_search_ds data)
1081 {
1082   /* Allocate stack for back-tracking up CFG.  */
1083   data->stack = XNEWVEC (basic_block, n_basic_blocks);
1084   data->sp = 0;
1085
1086   /* Allocate bitmap to track nodes that have been visited.  */
1087   data->visited_blocks = sbitmap_alloc (last_basic_block);
1088
1089   /* None of the nodes in the CFG have been visited yet.  */
1090   sbitmap_zero (data->visited_blocks);
1091
1092   return;
1093 }
1094
1095 /* Add the specified basic block to the top of the dfs data
1096    structures.  When the search continues, it will start at the
1097    block.  */
1098
1099 static void
1100 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb)
1101 {
1102   data->stack[data->sp++] = bb;
1103   SET_BIT (data->visited_blocks, bb->index);
1104 }
1105
1106 /* Continue the depth-first search through the reverse graph starting with the
1107    block at the stack's top and ending when the stack is empty.  Visited nodes
1108    are marked.  Returns an unvisited basic block, or NULL if there is none
1109    available.  */
1110
1111 static basic_block
1112 flow_dfs_compute_reverse_execute (depth_first_search_ds data,
1113                                   basic_block last_unvisited)
1114 {
1115   basic_block bb;
1116   edge e;
1117   edge_iterator ei;
1118
1119   while (data->sp > 0)
1120     {
1121       bb = data->stack[--data->sp];
1122
1123       /* Perform depth-first search on adjacent vertices.  */
1124       FOR_EACH_EDGE (e, ei, bb->preds)
1125         if (!TEST_BIT (data->visited_blocks, e->src->index))
1126           flow_dfs_compute_reverse_add_bb (data, e->src);
1127     }
1128
1129   /* Determine if there are unvisited basic blocks.  */
1130   FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
1131     if (!TEST_BIT (data->visited_blocks, bb->index))
1132       return bb;
1133
1134   return NULL;
1135 }
1136
1137 /* Destroy the data structures needed for depth-first search on the
1138    reverse graph.  */
1139
1140 static void
1141 flow_dfs_compute_reverse_finish (depth_first_search_ds data)
1142 {
1143   free (data->stack);
1144   sbitmap_free (data->visited_blocks);
1145 }
1146
1147 /* Performs dfs search from BB over vertices satisfying PREDICATE;
1148    if REVERSE, go against direction of edges.  Returns number of blocks
1149    found and their list in RSLT.  RSLT can contain at most RSLT_MAX items.  */
1150 int
1151 dfs_enumerate_from (basic_block bb, int reverse,
1152                     bool (*predicate) (const_basic_block, const void *),
1153                     basic_block *rslt, int rslt_max, const void *data)
1154 {
1155   basic_block *st, lbb;
1156   int sp = 0, tv = 0;
1157   unsigned size;
1158
1159   /* A bitmap to keep track of visited blocks.  Allocating it each time
1160      this function is called is not possible, since dfs_enumerate_from
1161      is often used on small (almost) disjoint parts of cfg (bodies of
1162      loops), and allocating a large sbitmap would lead to quadratic
1163      behavior.  */
1164   static sbitmap visited;
1165   static unsigned v_size;
1166
1167 #define MARK_VISITED(BB) (SET_BIT (visited, (BB)->index))
1168 #define UNMARK_VISITED(BB) (RESET_BIT (visited, (BB)->index))
1169 #define VISITED_P(BB) (TEST_BIT (visited, (BB)->index))
1170
1171   /* Resize the VISITED sbitmap if necessary.  */
1172   size = last_basic_block;
1173   if (size < 10)
1174     size = 10;
1175
1176   if (!visited)
1177     {
1178
1179       visited = sbitmap_alloc (size);
1180       sbitmap_zero (visited);
1181       v_size = size;
1182     }
1183   else if (v_size < size)
1184     {
1185       /* Ensure that we increase the size of the sbitmap exponentially.  */
1186       if (2 * v_size > size)
1187         size = 2 * v_size;
1188
1189       visited = sbitmap_resize (visited, size, 0);
1190       v_size = size;
1191     }
1192
1193   st = XCNEWVEC (basic_block, rslt_max);
1194   rslt[tv++] = st[sp++] = bb;
1195   MARK_VISITED (bb);
1196   while (sp)
1197     {
1198       edge e;
1199       edge_iterator ei;
1200       lbb = st[--sp];
1201       if (reverse)
1202         {
1203           FOR_EACH_EDGE (e, ei, lbb->preds)
1204             if (!VISITED_P (e->src) && predicate (e->src, data))
1205               {
1206                 gcc_assert (tv != rslt_max);
1207                 rslt[tv++] = st[sp++] = e->src;
1208                 MARK_VISITED (e->src);
1209               }
1210         }
1211       else
1212         {
1213           FOR_EACH_EDGE (e, ei, lbb->succs)
1214             if (!VISITED_P (e->dest) && predicate (e->dest, data))
1215               {
1216                 gcc_assert (tv != rslt_max);
1217                 rslt[tv++] = st[sp++] = e->dest;
1218                 MARK_VISITED (e->dest);
1219               }
1220         }
1221     }
1222   free (st);
1223   for (sp = 0; sp < tv; sp++)
1224     UNMARK_VISITED (rslt[sp]);
1225   return tv;
1226 #undef MARK_VISITED
1227 #undef UNMARK_VISITED
1228 #undef VISITED_P
1229 }
1230
1231
1232 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
1233
1234    This algorithm can be found in Timothy Harvey's PhD thesis, at
1235    http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
1236    dominance algorithms.
1237
1238    First, we identify each join point, j (any node with more than one
1239    incoming edge is a join point).
1240
1241    We then examine each predecessor, p, of j and walk up the dominator tree
1242    starting at p.
1243
1244    We stop the walk when we reach j's immediate dominator - j is in the
1245    dominance frontier of each of  the nodes in the walk, except for j's
1246    immediate dominator. Intuitively, all of the rest of j's dominators are
1247    shared by j's predecessors as well.
1248    Since they dominate j, they will not have j in their dominance frontiers.
1249
1250    The number of nodes touched by this algorithm is equal to the size
1251    of the dominance frontiers, no more, no less.
1252 */
1253
1254
1255 static void
1256 compute_dominance_frontiers_1 (bitmap *frontiers)
1257 {
1258   edge p;
1259   edge_iterator ei;
1260   basic_block b;
1261   FOR_EACH_BB (b)
1262     {
1263       if (EDGE_COUNT (b->preds) >= 2)
1264         {
1265           FOR_EACH_EDGE (p, ei, b->preds)
1266             {
1267               basic_block runner = p->src;
1268               basic_block domsb;
1269               if (runner == ENTRY_BLOCK_PTR)
1270                 continue;
1271
1272               domsb = get_immediate_dominator (CDI_DOMINATORS, b);
1273               while (runner != domsb)
1274                 {
1275                   if (bitmap_bit_p (frontiers[runner->index], b->index))
1276                     break;
1277                   bitmap_set_bit (frontiers[runner->index],
1278                                   b->index);
1279                   runner = get_immediate_dominator (CDI_DOMINATORS,
1280                                                     runner);
1281                 }
1282             }
1283         }
1284     }
1285 }
1286
1287
1288 void
1289 compute_dominance_frontiers (bitmap *frontiers)
1290 {
1291   timevar_push (TV_DOM_FRONTIERS);
1292
1293   compute_dominance_frontiers_1 (frontiers);
1294
1295   timevar_pop (TV_DOM_FRONTIERS);
1296 }
1297
1298 /* Given a set of blocks with variable definitions (DEF_BLOCKS),
1299    return a bitmap with all the blocks in the iterated dominance
1300    frontier of the blocks in DEF_BLOCKS.  DFS contains dominance
1301    frontier information as returned by compute_dominance_frontiers.
1302
1303    The resulting set of blocks are the potential sites where PHI nodes
1304    are needed.  The caller is responsible for freeing the memory
1305    allocated for the return value.  */
1306
1307 bitmap
1308 compute_idf (bitmap def_blocks, bitmap *dfs)
1309 {
1310   bitmap_iterator bi;
1311   unsigned bb_index, i;
1312   VEC(int,heap) *work_stack;
1313   bitmap phi_insertion_points;
1314
1315   work_stack = VEC_alloc (int, heap, n_basic_blocks);
1316   phi_insertion_points = BITMAP_ALLOC (NULL);
1317
1318   /* Seed the work list with all the blocks in DEF_BLOCKS.  We use
1319      VEC_quick_push here for speed.  This is safe because we know that
1320      the number of definition blocks is no greater than the number of
1321      basic blocks, which is the initial capacity of WORK_STACK.  */
1322   EXECUTE_IF_SET_IN_BITMAP (def_blocks, 0, bb_index, bi)
1323     VEC_quick_push (int, work_stack, bb_index);
1324
1325   /* Pop a block off the worklist, add every block that appears in
1326      the original block's DF that we have not already processed to
1327      the worklist.  Iterate until the worklist is empty.   Blocks
1328      which are added to the worklist are potential sites for
1329      PHI nodes.  */
1330   while (VEC_length (int, work_stack) > 0)
1331     {
1332       bb_index = VEC_pop (int, work_stack);
1333
1334       /* Since the registration of NEW -> OLD name mappings is done
1335          separately from the call to update_ssa, when updating the SSA
1336          form, the basic blocks where new and/or old names are defined
1337          may have disappeared by CFG cleanup calls.  In this case,
1338          we may pull a non-existing block from the work stack.  */
1339       gcc_assert (bb_index < (unsigned) last_basic_block);
1340
1341       EXECUTE_IF_AND_COMPL_IN_BITMAP (dfs[bb_index], phi_insertion_points,
1342                                       0, i, bi)
1343         {
1344           /* Use a safe push because if there is a definition of VAR
1345              in every basic block, then WORK_STACK may eventually have
1346              more than N_BASIC_BLOCK entries.  */
1347           VEC_safe_push (int, heap, work_stack, i);
1348           bitmap_set_bit (phi_insertion_points, i);
1349         }
1350     }
1351
1352   VEC_free (int, heap, work_stack);
1353
1354   return phi_insertion_points;
1355 }
1356
1357