gcc/cfganal.c

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