gcc/cfganal.c

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