gcc/cfganal.c

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