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 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, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, 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 livetime aborts.  */
  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       || EDGE_COUNT (bb->succs) != 1)
  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 flow_depth_first_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 = xcalloc (last_basic_block, sizeof (int));
 171   post = xcalloc (last_basic_block, sizeof (int));
 172
 173   /* Allocate stack for back-tracking up CFG.  */
 174   stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
 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 = xmalloc (sizeof (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         if (!(e->dest->flags & BB_REACHABLE))
 312           {
 313             *tos++ = e->dest;
 314             e->dest->flags |= BB_REACHABLE;
 315           }
 316     }
 317
 318   free (worklist);
 319 }
 320 \f
 321 /* Functions to access an edge list with a vector representation.
 322    Enough data is kept such that given an index number, the
 323    pred and succ that edge represents can be determined, or
 324    given a pred and a succ, its index number can be returned.
 325    This allows algorithms which consume a lot of memory to
 326    represent the normally full matrix of edge (pred,succ) with a
 327    single indexed vector,  edge (EDGE_INDEX (pred, succ)), with no
 328    wasted space in the client code due to sparse flow graphs.  */
 329
 330 /* This functions initializes the edge list. Basically the entire
 331    flowgraph is processed, and all edges are assigned a number,
 332    and the data structure is filled in.  */
 333
 334 struct edge_list *
 335 create_edge_list (void)
 336 {
 337   struct edge_list *elist;
 338   edge e;
 339   int num_edges;
 340   int block_count;
 341   basic_block bb;
 342   edge_iterator ei;
 343
 344   block_count = n_basic_blocks + 2;   /* Include the entry and exit blocks.  */
 345
 346   num_edges = 0;
 347
 348   /* Determine the number of edges in the flow graph by counting successor
 349      edges on each basic block.  */
 350   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 351     {
 352       num_edges += EDGE_COUNT (bb->succs);
 353     }
 354
 355   elist = xmalloc (sizeof (struct edge_list));
 356   elist->num_blocks = block_count;
 357   elist->num_edges = num_edges;
 358   elist->index_to_edge = xmalloc (sizeof (edge) * num_edges);
 359
 360   num_edges = 0;
 361
 362   /* Follow successors of blocks, and register these edges.  */
 363   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 364     FOR_EACH_EDGE (e, ei, bb->succs)
 365       elist->index_to_edge[num_edges++] = e;
 366
 367   return elist;
 368 }
 369
 370 /* This function free's memory associated with an edge list.  */
 371
 372 void
 373 free_edge_list (struct edge_list *elist)
 374 {
 375   if (elist)
 376     {
 377       free (elist->index_to_edge);
 378       free (elist);
 379     }
 380 }
 381
 382 /* This function provides debug output showing an edge list.  */
 383
 384 void
 385 print_edge_list (FILE *f, struct edge_list *elist)
 386 {
 387   int x;
 388
 389   fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
 390            elist->num_blocks - 2, elist->num_edges);
 391
 392   for (x = 0; x < elist->num_edges; x++)
 393     {
 394       fprintf (f, " %-4d - edge(", x);
 395       if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
 396         fprintf (f, "entry,");
 397       else
 398         fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
 399
 400       if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
 401         fprintf (f, "exit)\n");
 402       else
 403         fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
 404     }
 405 }
 406
 407 /* This function provides an internal consistency check of an edge list,
 408    verifying that all edges are present, and that there are no
 409    extra edges.  */
 410
 411 void
 412 verify_edge_list (FILE *f, struct edge_list *elist)
 413 {
 414   int pred, succ, index;
 415   edge e;
 416   basic_block bb, p, s;
 417   edge_iterator ei;
 418
 419   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 420     {
 421       FOR_EACH_EDGE (e, ei, bb->succs)
 422         {
 423           pred = e->src->index;
 424           succ = e->dest->index;
 425           index = EDGE_INDEX (elist, e->src, e->dest);
 426           if (index == EDGE_INDEX_NO_EDGE)
 427             {
 428               fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
 429               continue;
 430             }
 431
 432           if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
 433             fprintf (f, "*p* Pred for index %d should be %d not %d\n",
 434                      index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
 435           if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
 436             fprintf (f, "*p* Succ for index %d should be %d not %d\n",
 437                      index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
 438         }
 439     }
 440
 441   /* We've verified that all the edges are in the list, now lets make sure
 442      there are no spurious edges in the list.  */
 443
 444   FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 445     FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 446       {
 447         int found_edge = 0;
 448
 449         FOR_EACH_EDGE (e, ei, p->succs)
 450           if (e->dest == s)
 451             {
 452               found_edge = 1;
 453               break;
 454             }
 455
 456         FOR_EACH_EDGE (e, ei, s->preds)
 457           if (e->src == p)
 458             {
 459               found_edge = 1;
 460               break;
 461             }
 462
 463         if (EDGE_INDEX (elist, p, s)
 464             == EDGE_INDEX_NO_EDGE && found_edge != 0)
 465           fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
 466                    p->index, s->index);
 467         if (EDGE_INDEX (elist, p, s)
 468             != EDGE_INDEX_NO_EDGE && found_edge == 0)
 469           fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
 470                    p->index, s->index, EDGE_INDEX (elist, p, s));
 471       }
 472 }
 473
 474 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
 475    If no such edge exists, return NULL.  */
 476
 477 edge
 478 find_edge (basic_block pred, basic_block succ)
 479 {
 480   edge e;
 481   edge_iterator ei;
 482
 483   if (EDGE_COUNT (pred->succs) <= EDGE_COUNT (succ->preds))
 484     {
 485       FOR_EACH_EDGE (e, ei, pred->succs)
 486         if (e->dest == succ)
 487           return e;
 488     }
 489   else
 490     {
 491       FOR_EACH_EDGE (e, ei, succ->preds)
 492         if (e->src == pred)
 493           return e;
 494     }
 495
 496   return NULL;
 497 }
 498
 499 /* This routine will determine what, if any, edge there is between
 500    a specified predecessor and successor.  */
 501
 502 int
 503 find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
 504 {
 505   int x;
 506
 507   for (x = 0; x < NUM_EDGES (edge_list); x++)
 508     if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
 509         && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
 510       return x;
 511
 512   return (EDGE_INDEX_NO_EDGE);
 513 }
 514
 515 /* Dump the list of basic blocks in the bitmap NODES.  */
 516
 517 void
 518 flow_nodes_print (const char *str, const sbitmap nodes, FILE *file)
 519 {
 520   int node;
 521
 522   if (! nodes)
 523     return;
 524
 525   fprintf (file, "%s { ", str);
 526   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
 527   fputs ("}\n", file);
 528 }
 529
 530 /* Dump the list of edges in the array EDGE_LIST.  */
 531
 532 void
 533 flow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file)
 534 {
 535   int i;
 536
 537   if (! edge_list)
 538     return;
 539
 540   fprintf (file, "%s { ", str);
 541   for (i = 0; i < num_edges; i++)
 542     fprintf (file, "%d->%d ", edge_list[i]->src->index,
 543              edge_list[i]->dest->index);
 544
 545   fputs ("}\n", file);
 546 }
 547
 548 \f
 549 /* This routine will remove any fake predecessor edges for a basic block.
 550    When the edge is removed, it is also removed from whatever successor
 551    list it is in.  */
 552
 553 static void
 554 remove_fake_predecessors (basic_block bb)
 555 {
 556   edge e;
 557   edge_iterator ei;
 558
 559   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
 560     {
 561       if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
 562         remove_edge (e);
 563       else
 564         ei_next (&ei);
 565     }
 566 }
 567
 568 /* This routine will remove all fake edges from the flow graph.  If
 569    we remove all fake successors, it will automatically remove all
 570    fake predecessors.  */
 571
 572 void
 573 remove_fake_edges (void)
 574 {
 575   basic_block bb;
 576
 577   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 578     remove_fake_predecessors (bb);
 579 }
 580
 581 /* This routine will remove all fake edges to the EXIT_BLOCK.  */
 582
 583 void
 584 remove_fake_exit_edges (void)
 585 {
 586   remove_fake_predecessors (EXIT_BLOCK_PTR);
 587 }
 588
 589
 590 /* This function will add a fake edge between any block which has no
 591    successors, and the exit block. Some data flow equations require these
 592    edges to exist.  */
 593
 594 void
 595 add_noreturn_fake_exit_edges (void)
 596 {
 597   basic_block bb;
 598
 599   FOR_EACH_BB (bb)
 600     if (EDGE_COUNT (bb->succs) == 0)
 601       make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 602 }
 603
 604 /* This function adds a fake edge between any infinite loops to the
 605    exit block.  Some optimizations require a path from each node to
 606    the exit node.
 607
 608    See also Morgan, Figure 3.10, pp. 82-83.
 609
 610    The current implementation is ugly, not attempting to minimize the
 611    number of inserted fake edges.  To reduce the number of fake edges
 612    to insert, add fake edges from _innermost_ loops containing only
 613    nodes not reachable from the exit block.  */
 614
 615 void
 616 connect_infinite_loops_to_exit (void)
 617 {
 618   basic_block unvisited_block = EXIT_BLOCK_PTR;
 619   struct depth_first_search_dsS dfs_ds;
 620
 621   /* Perform depth-first search in the reverse graph to find nodes
 622      reachable from the exit block.  */
 623   flow_dfs_compute_reverse_init (&dfs_ds);
 624   flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
 625
 626   /* Repeatedly add fake edges, updating the unreachable nodes.  */
 627   while (1)
 628     {
 629       unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds,
 630                                                           unvisited_block);
 631       if (!unvisited_block)
 632         break;
 633
 634       make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
 635       flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
 636     }
 637
 638   flow_dfs_compute_reverse_finish (&dfs_ds);
 639   return;
 640 }
 641 \f
 642 /* Compute reverse top sort order.  */
 643
 644 void
 645 flow_reverse_top_sort_order_compute (int *rts_order)
 646 {
 647   edge_iterator *stack;
 648   int sp;
 649   int postnum = 0;
 650   sbitmap visited;
 651
 652   /* Allocate stack for back-tracking up CFG.  */
 653   stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
 654   sp = 0;
 655
 656   /* Allocate bitmap to track nodes that have been visited.  */
 657   visited = sbitmap_alloc (last_basic_block);
 658
 659   /* None of the nodes in the CFG have been visited yet.  */
 660   sbitmap_zero (visited);
 661
 662   /* Push the first edge on to the stack.  */
 663   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 664
 665   while (sp)
 666     {
 667       edge_iterator ei;
 668       basic_block src;
 669       basic_block dest;
 670
 671       /* Look at the edge on the top of the stack.  */
 672       ei = stack[sp - 1];
 673       src = ei_edge (ei)->src;
 674       dest = ei_edge (ei)->dest;
 675
 676       /* Check if the edge destination has been visited yet.  */
 677       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 678         {
 679           /* Mark that we have visited the destination.  */
 680           SET_BIT (visited, dest->index);
 681
 682           if (EDGE_COUNT (dest->succs) > 0)
 683             /* Since the DEST node has been visited for the first
 684                time, check its successors.  */
 685             stack[sp++] = ei_start (dest->succs);
 686           else
 687             rts_order[postnum++] = dest->index;
 688         }
 689       else
 690         {
 691           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
 692            rts_order[postnum++] = src->index;
 693
 694           if (!ei_one_before_end_p (ei))
 695             ei_next (&stack[sp - 1]);
 696           else
 697             sp--;
 698         }
 699     }
 700
 701   free (stack);
 702   sbitmap_free (visited);
 703 }
 704
 705 /* Compute the depth first search order and store in the array
 706   DFS_ORDER if nonzero, marking the nodes visited in VISITED.  If
 707   RC_ORDER is nonzero, return the reverse completion number for each
 708   node.  Returns the number of nodes visited.  A depth first search
 709   tries to get as far away from the starting point as quickly as
 710   possible.  */
 711
 712 int
 713 flow_depth_first_order_compute (int *dfs_order, int *rc_order)
 714 {
 715   edge_iterator *stack;
 716   int sp;
 717   int dfsnum = 0;
 718   int rcnum = n_basic_blocks - 1;
 719   sbitmap visited;
 720
 721   /* Allocate stack for back-tracking up CFG.  */
 722   stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
 723   sp = 0;
 724
 725   /* Allocate bitmap to track nodes that have been visited.  */
 726   visited = sbitmap_alloc (last_basic_block);
 727
 728   /* None of the nodes in the CFG have been visited yet.  */
 729   sbitmap_zero (visited);
 730
 731   /* Push the first edge on to the stack.  */
 732   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 733
 734   while (sp)
 735     {
 736       edge_iterator ei;
 737       basic_block src;
 738       basic_block dest;
 739
 740       /* Look at the edge on the top of the stack.  */
 741       ei = stack[sp - 1];
 742       src = ei_edge (ei)->src;
 743       dest = ei_edge (ei)->dest;
 744
 745       /* Check if the edge destination has been visited yet.  */
 746       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 747         {
 748           /* Mark that we have visited the destination.  */
 749           SET_BIT (visited, dest->index);
 750
 751           if (dfs_order)
 752             dfs_order[dfsnum] = dest->index;
 753
 754           dfsnum++;
 755
 756           if (EDGE_COUNT (dest->succs) > 0)
 757             /* Since the DEST node has been visited for the first
 758                time, check its successors.  */
 759             stack[sp++] = ei_start (dest->succs);
 760           else if (rc_order)
 761             /* There are no successors for the DEST node so assign
 762                its reverse completion number.  */
 763             rc_order[rcnum--] = dest->index;
 764         }
 765       else
 766         {
 767           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR
 768               && rc_order)
 769             /* There are no more successors for the SRC node
 770                so assign its reverse completion number.  */
 771             rc_order[rcnum--] = src->index;
 772
 773           if (!ei_one_before_end_p (ei))
 774             ei_next (&stack[sp - 1]);
 775           else
 776             sp--;
 777         }
 778     }
 779
 780   free (stack);
 781   sbitmap_free (visited);
 782
 783   /* The number of nodes visited should be the number of blocks.  */
 784   gcc_assert (dfsnum == n_basic_blocks);
 785
 786   return dfsnum;
 787 }
 788
 789 /* Compute the depth first search order on the _reverse_ graph and
 790    store in the array DFS_ORDER, marking the nodes visited in VISITED.
 791    Returns the number of nodes visited.
 792
 793    The computation is split into three pieces:
 794
 795    flow_dfs_compute_reverse_init () creates the necessary data
 796    structures.
 797
 798    flow_dfs_compute_reverse_add_bb () adds a basic block to the data
 799    structures.  The block will start the search.
 800
 801    flow_dfs_compute_reverse_execute () continues (or starts) the
 802    search using the block on the top of the stack, stopping when the
 803    stack is empty.
 804
 805    flow_dfs_compute_reverse_finish () destroys the necessary data
 806    structures.
 807
 808    Thus, the user will probably call ..._init(), call ..._add_bb() to
 809    add a beginning basic block to the stack, call ..._execute(),
 810    possibly add another bb to the stack and again call ..._execute(),
 811    ..., and finally call _finish().  */
 812
 813 /* Initialize the data structures used for depth-first search on the
 814    reverse graph.  If INITIALIZE_STACK is nonzero, the exit block is
 815    added to the basic block stack.  DATA is the current depth-first
 816    search context.  If INITIALIZE_STACK is nonzero, there is an
 817    element on the stack.  */
 818
 819 static void
 820 flow_dfs_compute_reverse_init (depth_first_search_ds data)
 821 {
 822   /* Allocate stack for back-tracking up CFG.  */
 823   data->stack = xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
 824                          * sizeof (basic_block));
 825   data->sp = 0;
 826
 827   /* Allocate bitmap to track nodes that have been visited.  */
 828   data->visited_blocks = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
 829
 830   /* None of the nodes in the CFG have been visited yet.  */
 831   sbitmap_zero (data->visited_blocks);
 832
 833   return;
 834 }
 835
 836 /* Add the specified basic block to the top of the dfs data
 837    structures.  When the search continues, it will start at the
 838    block.  */
 839
 840 static void
 841 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb)
 842 {
 843   data->stack[data->sp++] = bb;
 844   SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1));
 845 }
 846
 847 /* Continue the depth-first search through the reverse graph starting with the
 848    block at the stack's top and ending when the stack is empty.  Visited nodes
 849    are marked.  Returns an unvisited basic block, or NULL if there is none
 850    available.  */
 851
 852 static basic_block
 853 flow_dfs_compute_reverse_execute (depth_first_search_ds data,
 854                                   basic_block last_unvisited)
 855 {
 856   basic_block bb;
 857   edge e;
 858   edge_iterator ei;
 859
 860   while (data->sp > 0)
 861     {
 862       bb = data->stack[--data->sp];
 863
 864       /* Perform depth-first search on adjacent vertices.  */
 865       FOR_EACH_EDGE (e, ei, bb->preds)
 866         if (!TEST_BIT (data->visited_blocks,
 867                        e->src->index - (INVALID_BLOCK + 1)))
 868           flow_dfs_compute_reverse_add_bb (data, e->src);
 869     }
 870
 871   /* Determine if there are unvisited basic blocks.  */
 872   FOR_BB_BETWEEN (bb, last_unvisited, NULL, prev_bb)
 873     if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
 874       return bb;
 875
 876   return NULL;
 877 }
 878
 879 /* Destroy the data structures needed for depth-first search on the
 880    reverse graph.  */
 881
 882 static void
 883 flow_dfs_compute_reverse_finish (depth_first_search_ds data)
 884 {
 885   free (data->stack);
 886   sbitmap_free (data->visited_blocks);
 887 }
 888
 889 /* Performs dfs search from BB over vertices satisfying PREDICATE;
 890    if REVERSE, go against direction of edges.  Returns number of blocks
 891    found and their list in RSLT.  RSLT can contain at most RSLT_MAX items.  */
 892 int
 893 dfs_enumerate_from (basic_block bb, int reverse,
 894                     bool (*predicate) (basic_block, void *),
 895                     basic_block *rslt, int rslt_max, void *data)
 896 {
 897   basic_block *st, lbb;
 898   int sp = 0, tv = 0;
 899
 900   st = xcalloc (rslt_max, sizeof (basic_block));
 901   rslt[tv++] = st[sp++] = bb;
 902   bb->flags |= BB_VISITED;
 903   while (sp)
 904     {
 905       edge e;
 906       edge_iterator ei;
 907       lbb = st[--sp];
 908       if (reverse)
 909         {
 910           FOR_EACH_EDGE (e, ei, lbb->preds)
 911             if (!(e->src->flags & BB_VISITED) && predicate (e->src, data))
 912               {
 913                 gcc_assert (tv != rslt_max);
 914                 rslt[tv++] = st[sp++] = e->src;
 915                 e->src->flags |= BB_VISITED;
 916               }
 917         }
 918       else
 919         {
 920           FOR_EACH_EDGE (e, ei, lbb->succs)
 921             if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data))
 922               {
 923                 gcc_assert (tv != rslt_max);
 924                 rslt[tv++] = st[sp++] = e->dest;
 925                 e->dest->flags |= BB_VISITED;
 926               }
 927         }
 928     }
 929   free (st);
 930   for (sp = 0; sp < tv; sp++)
 931     rslt[sp]->flags &= ~BB_VISITED;
 932   return tv;
 933 }
 934
 935
 936 /* Compute dominance frontiers, ala Harvey, Ferrante, et al.
 937
 938    This algorithm can be found in Timothy Harvey's PhD thesis, at
 939    http://www.cs.rice.edu/~harv/dissertation.pdf in the section on iterative
 940    dominance algorithms.
 941
 942    First, we identify each join point, j (any node with more than one
 943    incoming edge is a join point).
 944
 945    We then examine each predecessor, p, of j and walk up the dominator tree
 946    starting at p.
 947
 948    We stop the walk when we reach j's immediate dominator - j is in the
 949    dominance frontier of each of  the nodes in the walk, except for j's
 950    immediate dominator. Intuitively, all of the rest of j's dominators are
 951    shared by j's predecessors as well.
 952    Since they dominate j, they will not have j in their dominance frontiers.
 953
 954    The number of nodes touched by this algorithm is equal to the size
 955    of the dominance frontiers, no more, no less.
 956 */
 957
 958
 959 static void
 960 compute_dominance_frontiers_1 (bitmap *frontiers)
 961 {
 962   edge p;
 963   edge_iterator ei;
 964   basic_block b;
 965   FOR_EACH_BB (b)
 966     {
 967       if (EDGE_COUNT (b->preds) >= 2)
 968         {
 969           FOR_EACH_EDGE (p, ei, b->preds)
 970             {
 971               basic_block runner = p->src;
 972               basic_block domsb;
 973               if (runner == ENTRY_BLOCK_PTR)
 974                 continue;
 975
 976               domsb = get_immediate_dominator (CDI_DOMINATORS, b);
 977               while (runner != domsb)
 978                 {
 979                   bitmap_set_bit (frontiers[runner->index],
 980                                   b->index);
 981                   runner = get_immediate_dominator (CDI_DOMINATORS,
 982                                                     runner);
 983                 }
 984             }
 985         }
 986     }
 987 }
 988
 989
 990 void
 991 compute_dominance_frontiers (bitmap *frontiers)
 992 {
 993   timevar_push (TV_DOM_FRONTIERS);
 994
 995   compute_dominance_frontiers_1 (frontiers);
 996
 997   timevar_pop (TV_DOM_FRONTIERS);
 998 }
 999