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