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