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 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 "hard-reg-set.h"
  29 #include "basic-block.h"
  30 #include "insn-config.h"
  31 #include "recog.h"
  32 #include "toplev.h"
  33 #include "tm_p.h"
  34 #include "timevar.h"
  35
  36 /* Store the data structures necessary for depth-first search.  */
  37 struct depth_first_search_dsS {
  38   /* stack for backtracking during the algorithm */
  39   basic_block *stack;
  40
  41   /* number of edges in the stack.  That is, positions 0, ..., sp-1
  42      have edges.  */
  43   unsigned int sp;
  44
  45   /* record of basic blocks already seen by depth-first search */
  46   sbitmap visited_blocks;
  47 };
  48 typedef struct depth_first_search_dsS *depth_first_search_ds;
  49
  50 static void flow_dfs_compute_reverse_init (depth_first_search_ds);
  51 static void flow_dfs_compute_reverse_add_bb (depth_first_search_ds,
  52                                              basic_block);
  53 static basic_block flow_dfs_compute_reverse_execute (depth_first_search_ds);
  54 static void flow_dfs_compute_reverse_finish (depth_first_search_ds);
  55 static bool flow_active_insn_p (rtx);
  56 \f
  57 /* Like active_insn_p, except keep the return value clobber around
  58    even after reload.  */
  59
  60 static bool
  61 flow_active_insn_p (rtx insn)
  62 {
  63   if (active_insn_p (insn))
  64     return true;
  65
  66   /* A clobber of the function return value exists for buggy
  67      programs that fail to return a value.  Its effect is to
  68      keep the return value from being live across the entire
  69      function.  If we allow it to be skipped, we introduce the
  70      possibility for register livetime aborts.  */
  71   if (GET_CODE (PATTERN (insn)) == CLOBBER
  72       && REG_P (XEXP (PATTERN (insn), 0))
  73       && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
  74     return true;
  75
  76   return false;
  77 }
  78
  79 /* Return true if the block has no effect and only forwards control flow to
  80    its single destination.  */
  81
  82 bool
  83 forwarder_block_p (basic_block bb)
  84 {
  85   rtx insn;
  86
  87   if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
  88       || EDGE_COUNT (bb->succs) != 1)
  89     return false;
  90
  91   for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
  92     if (INSN_P (insn) && flow_active_insn_p (insn))
  93       return false;
  94
  95   return (!INSN_P (insn)
  96           || (JUMP_P (insn) && simplejump_p (insn))
  97           || !flow_active_insn_p (insn));
  98 }
  99
 100 /* Return nonzero if we can reach target from src by falling through.  */
 101
 102 bool
 103 can_fallthru (basic_block src, basic_block target)
 104 {
 105   rtx insn = BB_END (src);
 106   rtx insn2;
 107   edge e;
 108   edge_iterator ei;
 109
 110   if (target == EXIT_BLOCK_PTR)
 111     return true;
 112   if (src->next_bb != target)
 113     return 0;
 114   FOR_EACH_EDGE (e, ei, src->succs)
 115     if (e->dest == EXIT_BLOCK_PTR
 116         && e->flags & EDGE_FALLTHRU)
 117       return 0;
 118
 119   insn2 = BB_HEAD (target);
 120   if (insn2 && !active_insn_p (insn2))
 121     insn2 = next_active_insn (insn2);
 122
 123   /* ??? Later we may add code to move jump tables offline.  */
 124   return next_active_insn (insn) == insn2;
 125 }
 126
 127 /* Return nonzero if we could reach target from src by falling through,
 128    if the target was made adjacent.  If we already have a fall-through
 129    edge to the exit block, we can't do that.  */
 130 bool
 131 could_fall_through (basic_block src, basic_block target)
 132 {
 133   edge e;
 134   edge_iterator ei;
 135
 136   if (target == EXIT_BLOCK_PTR)
 137     return true;
 138   FOR_EACH_EDGE (e, ei, src->succs)
 139     if (e->dest == EXIT_BLOCK_PTR
 140         && e->flags & EDGE_FALLTHRU)
 141       return 0;
 142   return true;
 143 }
 144 \f
 145 /* Mark the back edges in DFS traversal.
 146    Return nonzero if a loop (natural or otherwise) is present.
 147    Inspired by Depth_First_Search_PP described in:
 148
 149      Advanced Compiler Design and Implementation
 150      Steven Muchnick
 151      Morgan Kaufmann, 1997
 152
 153    and heavily borrowed from flow_depth_first_order_compute.  */
 154
 155 bool
 156 mark_dfs_back_edges (void)
 157 {
 158   edge_iterator *stack;
 159   int *pre;
 160   int *post;
 161   int sp;
 162   int prenum = 1;
 163   int postnum = 1;
 164   sbitmap visited;
 165   bool found = false;
 166
 167   /* Allocate the preorder and postorder number arrays.  */
 168   pre = xcalloc (last_basic_block, sizeof (int));
 169   post = xcalloc (last_basic_block, sizeof (int));
 170
 171   /* Allocate stack for back-tracking up CFG.  */
 172   stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
 173   sp = 0;
 174
 175   /* Allocate bitmap to track nodes that have been visited.  */
 176   visited = sbitmap_alloc (last_basic_block);
 177
 178   /* None of the nodes in the CFG have been visited yet.  */
 179   sbitmap_zero (visited);
 180
 181   /* Push the first edge on to the stack.  */
 182   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 183
 184   while (sp)
 185     {
 186       edge_iterator ei;
 187       basic_block src;
 188       basic_block dest;
 189
 190       /* Look at the edge on the top of the stack.  */
 191       ei = stack[sp - 1];
 192       src = ei_edge (ei)->src;
 193       dest = ei_edge (ei)->dest;
 194       ei_edge (ei)->flags &= ~EDGE_DFS_BACK;
 195
 196       /* Check if the edge destination has been visited yet.  */
 197       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 198         {
 199           /* Mark that we have visited the destination.  */
 200           SET_BIT (visited, dest->index);
 201
 202           pre[dest->index] = prenum++;
 203           if (EDGE_COUNT (dest->succs) > 0)
 204             {
 205               /* Since the DEST node has been visited for the first
 206                  time, check its successors.  */
 207               stack[sp++] = ei_start (dest->succs);
 208             }
 209           else
 210             post[dest->index] = postnum++;
 211         }
 212       else
 213         {
 214           if (dest != EXIT_BLOCK_PTR && src != ENTRY_BLOCK_PTR
 215               && pre[src->index] >= pre[dest->index]
 216               && post[dest->index] == 0)
 217             ei_edge (ei)->flags |= EDGE_DFS_BACK, found = true;
 218
 219           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
 220             post[src->index] = postnum++;
 221
 222           if (!ei_one_before_end_p (ei))
 223             ei_next (&stack[sp - 1]);
 224           else
 225             sp--;
 226         }
 227     }
 228
 229   free (pre);
 230   free (post);
 231   free (stack);
 232   sbitmap_free (visited);
 233
 234   return found;
 235 }
 236
 237 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru.  */
 238
 239 void
 240 set_edge_can_fallthru_flag (void)
 241 {
 242   basic_block bb;
 243
 244   FOR_EACH_BB (bb)
 245     {
 246       edge e;
 247       edge_iterator ei;
 248
 249       FOR_EACH_EDGE (e, ei, bb->succs)
 250         {
 251           e->flags &= ~EDGE_CAN_FALLTHRU;
 252
 253           /* The FALLTHRU edge is also CAN_FALLTHRU edge.  */
 254           if (e->flags & EDGE_FALLTHRU)
 255             e->flags |= EDGE_CAN_FALLTHRU;
 256         }
 257
 258       /* If the BB ends with an invertible condjump all (2) edges are
 259          CAN_FALLTHRU edges.  */
 260       if (EDGE_COUNT (bb->succs) != 2)
 261         continue;
 262       if (!any_condjump_p (BB_END (bb)))
 263         continue;
 264       if (!invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0))
 265         continue;
 266       invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0);
 267       EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU;
 268       EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU;
 269     }
 270 }
 271
 272 /* Find unreachable blocks.  An unreachable block will have 0 in
 273    the reachable bit in block->flags.  A nonzero value indicates the
 274    block is reachable.  */
 275
 276 void
 277 find_unreachable_blocks (void)
 278 {
 279   edge e;
 280   edge_iterator ei;
 281   basic_block *tos, *worklist, bb;
 282
 283   tos = worklist = xmalloc (sizeof (basic_block) * n_basic_blocks);
 284
 285   /* Clear all the reachability flags.  */
 286
 287   FOR_EACH_BB (bb)
 288     bb->flags &= ~BB_REACHABLE;
 289
 290   /* Add our starting points to the worklist.  Almost always there will
 291      be only one.  It isn't inconceivable that we might one day directly
 292      support Fortran alternate entry points.  */
 293
 294   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 295     {
 296       *tos++ = e->dest;
 297
 298       /* Mark the block reachable.  */
 299       e->dest->flags |= BB_REACHABLE;
 300     }
 301
 302   /* Iterate: find everything reachable from what we've already seen.  */
 303
 304   while (tos != worklist)
 305     {
 306       basic_block b = *--tos;
 307
 308       FOR_EACH_EDGE (e, ei, b->succs)
 309         if (!(e->dest->flags & BB_REACHABLE))
 310           {
 311             *tos++ = e->dest;
 312             e->dest->flags |= BB_REACHABLE;
 313           }
 314     }
 315
 316   free (worklist);
 317 }
 318 \f
 319 /* Functions to access an edge list with a vector representation.
 320    Enough data is kept such that given an index number, the
 321    pred and succ that edge represents can be determined, or
 322    given a pred and a succ, its index number can be returned.
 323    This allows algorithms which consume a lot of memory to
 324    represent the normally full matrix of edge (pred,succ) with a
 325    single indexed vector,  edge (EDGE_INDEX (pred, succ)), with no
 326    wasted space in the client code due to sparse flow graphs.  */
 327
 328 /* This functions initializes the edge list. Basically the entire
 329    flowgraph is processed, and all edges are assigned a number,
 330    and the data structure is filled in.  */
 331
 332 struct edge_list *
 333 create_edge_list (void)
 334 {
 335   struct edge_list *elist;
 336   edge e;
 337   int num_edges;
 338   int block_count;
 339   basic_block bb;
 340   edge_iterator ei;
 341
 342   block_count = n_basic_blocks + 2;   /* Include the entry and exit blocks.  */
 343
 344   num_edges = 0;
 345
 346   /* Determine the number of edges in the flow graph by counting successor
 347      edges on each basic block.  */
 348   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 349     {
 350       num_edges += EDGE_COUNT (bb->succs);
 351     }
 352
 353   elist = xmalloc (sizeof (struct edge_list));
 354   elist->num_blocks = block_count;
 355   elist->num_edges = num_edges;
 356   elist->index_to_edge = xmalloc (sizeof (edge) * num_edges);
 357
 358   num_edges = 0;
 359
 360   /* Follow successors of blocks, and register these edges.  */
 361   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 362     FOR_EACH_EDGE (e, ei, bb->succs)
 363       elist->index_to_edge[num_edges++] = e;
 364
 365   return elist;
 366 }
 367
 368 /* This function free's memory associated with an edge list.  */
 369
 370 void
 371 free_edge_list (struct edge_list *elist)
 372 {
 373   if (elist)
 374     {
 375       free (elist->index_to_edge);
 376       free (elist);
 377     }
 378 }
 379
 380 /* This function provides debug output showing an edge list.  */
 381
 382 void
 383 print_edge_list (FILE *f, struct edge_list *elist)
 384 {
 385   int x;
 386
 387   fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
 388            elist->num_blocks - 2, elist->num_edges);
 389
 390   for (x = 0; x < elist->num_edges; x++)
 391     {
 392       fprintf (f, " %-4d - edge(", x);
 393       if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
 394         fprintf (f, "entry,");
 395       else
 396         fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
 397
 398       if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
 399         fprintf (f, "exit)\n");
 400       else
 401         fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
 402     }
 403 }
 404
 405 /* This function provides an internal consistency check of an edge list,
 406    verifying that all edges are present, and that there are no
 407    extra edges.  */
 408
 409 void
 410 verify_edge_list (FILE *f, struct edge_list *elist)
 411 {
 412   int pred, succ, index;
 413   edge e;
 414   basic_block bb, p, s;
 415   edge_iterator ei;
 416
 417   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 418     {
 419       FOR_EACH_EDGE (e, ei, bb->succs)
 420         {
 421           pred = e->src->index;
 422           succ = e->dest->index;
 423           index = EDGE_INDEX (elist, e->src, e->dest);
 424           if (index == EDGE_INDEX_NO_EDGE)
 425             {
 426               fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
 427               continue;
 428             }
 429
 430           if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
 431             fprintf (f, "*p* Pred for index %d should be %d not %d\n",
 432                      index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
 433           if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
 434             fprintf (f, "*p* Succ for index %d should be %d not %d\n",
 435                      index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
 436         }
 437     }
 438
 439   /* We've verified that all the edges are in the list, now lets make sure
 440      there are no spurious edges in the list.  */
 441
 442   FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 443     FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 444       {
 445         int found_edge = 0;
 446
 447         FOR_EACH_EDGE (e, ei, p->succs)
 448           if (e->dest == s)
 449             {
 450               found_edge = 1;
 451               break;
 452             }
 453
 454         FOR_EACH_EDGE (e, ei, s->preds)
 455           if (e->src == p)
 456             {
 457               found_edge = 1;
 458               break;
 459             }
 460
 461         if (EDGE_INDEX (elist, p, s)
 462             == EDGE_INDEX_NO_EDGE && found_edge != 0)
 463           fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
 464                    p->index, s->index);
 465         if (EDGE_INDEX (elist, p, s)
 466             != EDGE_INDEX_NO_EDGE && found_edge == 0)
 467           fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
 468                    p->index, s->index, EDGE_INDEX (elist, p, s));
 469       }
 470 }
 471
 472 /* Given PRED and SUCC blocks, return the edge which connects the blocks.
 473    If no such edge exists, return NULL.  */
 474
 475 edge
 476 find_edge (basic_block pred, basic_block succ)
 477 {
 478   edge e;
 479   edge_iterator ei;
 480
 481   FOR_EACH_EDGE (e, ei, pred->succs)
 482     if (e->dest == succ)
 483       return e;
 484
 485   return NULL;
 486 }
 487
 488 /* This routine will determine what, if any, edge there is between
 489    a specified predecessor and successor.  */
 490
 491 int
 492 find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
 493 {
 494   int x;
 495
 496   for (x = 0; x < NUM_EDGES (edge_list); x++)
 497     if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
 498         && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
 499       return x;
 500
 501   return (EDGE_INDEX_NO_EDGE);
 502 }
 503
 504 /* Dump the list of basic blocks in the bitmap NODES.  */
 505
 506 void
 507 flow_nodes_print (const char *str, const sbitmap nodes, FILE *file)
 508 {
 509   int node;
 510
 511   if (! nodes)
 512     return;
 513
 514   fprintf (file, "%s { ", str);
 515   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
 516   fputs ("}\n", file);
 517 }
 518
 519 /* Dump the list of edges in the array EDGE_LIST.  */
 520
 521 void
 522 flow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file)
 523 {
 524   int i;
 525
 526   if (! edge_list)
 527     return;
 528
 529   fprintf (file, "%s { ", str);
 530   for (i = 0; i < num_edges; i++)
 531     fprintf (file, "%d->%d ", edge_list[i]->src->index,
 532              edge_list[i]->dest->index);
 533
 534   fputs ("}\n", file);
 535 }
 536
 537 \f
 538 /* This routine will remove any fake predecessor edges for a basic block.
 539    When the edge is removed, it is also removed from whatever successor
 540    list it is in.  */
 541
 542 static void
 543 remove_fake_predecessors (basic_block bb)
 544 {
 545   edge e;
 546   edge_iterator ei;
 547
 548   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
 549     {
 550       if ((e->flags & EDGE_FAKE) == EDGE_FAKE)
 551         remove_edge (e);
 552       else
 553         ei_next (&ei);
 554     }
 555 }
 556
 557 /* This routine will remove all fake edges from the flow graph.  If
 558    we remove all fake successors, it will automatically remove all
 559    fake predecessors.  */
 560
 561 void
 562 remove_fake_edges (void)
 563 {
 564   basic_block bb;
 565
 566   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 567     remove_fake_predecessors (bb);
 568 }
 569
 570 /* This routine will remove all fake edges to the EXIT_BLOCK.  */
 571
 572 void
 573 remove_fake_exit_edges (void)
 574 {
 575   remove_fake_predecessors (EXIT_BLOCK_PTR);
 576 }
 577
 578
 579 /* This function will add a fake edge between any block which has no
 580    successors, and the exit block. Some data flow equations require these
 581    edges to exist.  */
 582
 583 void
 584 add_noreturn_fake_exit_edges (void)
 585 {
 586   basic_block bb;
 587
 588   FOR_EACH_BB (bb)
 589     if (EDGE_COUNT (bb->succs) == 0)
 590       make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 591 }
 592
 593 /* This function adds a fake edge between any infinite loops to the
 594    exit block.  Some optimizations require a path from each node to
 595    the exit node.
 596
 597    See also Morgan, Figure 3.10, pp. 82-83.
 598
 599    The current implementation is ugly, not attempting to minimize the
 600    number of inserted fake edges.  To reduce the number of fake edges
 601    to insert, add fake edges from _innermost_ loops containing only
 602    nodes not reachable from the exit block.  */
 603
 604 void
 605 connect_infinite_loops_to_exit (void)
 606 {
 607   basic_block unvisited_block;
 608   struct depth_first_search_dsS dfs_ds;
 609
 610   /* Perform depth-first search in the reverse graph to find nodes
 611      reachable from the exit block.  */
 612   flow_dfs_compute_reverse_init (&dfs_ds);
 613   flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
 614
 615   /* Repeatedly add fake edges, updating the unreachable nodes.  */
 616   while (1)
 617     {
 618       unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds);
 619       if (!unvisited_block)
 620         break;
 621
 622       make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
 623       flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
 624     }
 625
 626   flow_dfs_compute_reverse_finish (&dfs_ds);
 627   return;
 628 }
 629 \f
 630 /* Compute reverse top sort order.  */
 631
 632 void
 633 flow_reverse_top_sort_order_compute (int *rts_order)
 634 {
 635   edge_iterator *stack;
 636   int sp;
 637   int postnum = 0;
 638   sbitmap visited;
 639
 640   /* Allocate stack for back-tracking up CFG.  */
 641   stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
 642   sp = 0;
 643
 644   /* Allocate bitmap to track nodes that have been visited.  */
 645   visited = sbitmap_alloc (last_basic_block);
 646
 647   /* None of the nodes in the CFG have been visited yet.  */
 648   sbitmap_zero (visited);
 649
 650   /* Push the first edge on to the stack.  */
 651   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 652
 653   while (sp)
 654     {
 655       edge_iterator ei;
 656       basic_block src;
 657       basic_block dest;
 658
 659       /* Look at the edge on the top of the stack.  */
 660       ei = stack[sp - 1];
 661       src = ei_edge (ei)->src;
 662       dest = ei_edge (ei)->dest;
 663
 664       /* Check if the edge destination has been visited yet.  */
 665       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 666         {
 667           /* Mark that we have visited the destination.  */
 668           SET_BIT (visited, dest->index);
 669
 670           if (EDGE_COUNT (dest->succs) > 0)
 671             /* Since the DEST node has been visited for the first
 672                time, check its successors.  */
 673             stack[sp++] = ei_start (dest->succs);
 674           else
 675             rts_order[postnum++] = dest->index;
 676         }
 677       else
 678         {
 679           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR)
 680            rts_order[postnum++] = src->index;
 681
 682           if (!ei_one_before_end_p (ei))
 683             ei_next (&stack[sp - 1]);
 684           else
 685             sp--;
 686         }
 687     }
 688
 689   free (stack);
 690   sbitmap_free (visited);
 691 }
 692
 693 /* Compute the depth first search order and store in the array
 694   DFS_ORDER if nonzero, marking the nodes visited in VISITED.  If
 695   RC_ORDER is nonzero, return the reverse completion number for each
 696   node.  Returns the number of nodes visited.  A depth first search
 697   tries to get as far away from the starting point as quickly as
 698   possible.  */
 699
 700 int
 701 flow_depth_first_order_compute (int *dfs_order, int *rc_order)
 702 {
 703   edge_iterator *stack;
 704   int sp;
 705   int dfsnum = 0;
 706   int rcnum = n_basic_blocks - 1;
 707   sbitmap visited;
 708
 709   /* Allocate stack for back-tracking up CFG.  */
 710   stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge_iterator));
 711   sp = 0;
 712
 713   /* Allocate bitmap to track nodes that have been visited.  */
 714   visited = sbitmap_alloc (last_basic_block);
 715
 716   /* None of the nodes in the CFG have been visited yet.  */
 717   sbitmap_zero (visited);
 718
 719   /* Push the first edge on to the stack.  */
 720   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 721
 722   while (sp)
 723     {
 724       edge_iterator ei;
 725       basic_block src;
 726       basic_block dest;
 727
 728       /* Look at the edge on the top of the stack.  */
 729       ei = stack[sp - 1];
 730       src = ei_edge (ei)->src;
 731       dest = ei_edge (ei)->dest;
 732
 733       /* Check if the edge destination has been visited yet.  */
 734       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 735         {
 736           /* Mark that we have visited the destination.  */
 737           SET_BIT (visited, dest->index);
 738
 739           if (dfs_order)
 740             dfs_order[dfsnum] = dest->index;
 741
 742           dfsnum++;
 743
 744           if (EDGE_COUNT (dest->succs) > 0)
 745             /* Since the DEST node has been visited for the first
 746                time, check its successors.  */
 747             stack[sp++] = ei_start (dest->succs);
 748           else if (rc_order)
 749             /* There are no successors for the DEST node so assign
 750                its reverse completion number.  */
 751             rc_order[rcnum--] = dest->index;
 752         }
 753       else
 754         {
 755           if (ei_one_before_end_p (ei) && src != ENTRY_BLOCK_PTR
 756               && rc_order)
 757             /* There are no more successors for the SRC node
 758                so assign its reverse completion number.  */
 759             rc_order[rcnum--] = src->index;
 760
 761           if (!ei_one_before_end_p (ei))
 762             ei_next (&stack[sp - 1]);
 763           else
 764             sp--;
 765         }
 766     }
 767
 768   free (stack);
 769   sbitmap_free (visited);
 770
 771   /* The number of nodes visited should be the number of blocks.  */
 772   gcc_assert (dfsnum == n_basic_blocks);
 773
 774   return dfsnum;
 775 }
 776
 777 struct dfst_node
 778 {
 779     unsigned nnodes;
 780     struct dfst_node **node;
 781     struct dfst_node *up;
 782 };
 783
 784 /* Compute a preorder transversal ordering such that a sub-tree which
 785    is the source of a cross edge appears before the sub-tree which is
 786    the destination of the cross edge.  This allows for easy detection
 787    of all the entry blocks for a loop.
 788
 789    The ordering is compute by:
 790
 791      1) Generating a depth first spanning tree.
 792
 793      2) Walking the resulting tree from right to left.  */
 794
 795 void
 796 flow_preorder_transversal_compute (int *pot_order)
 797 {
 798   edge_iterator *stack, ei;
 799   int i;
 800   int max_successors;
 801   int sp;
 802   sbitmap visited;
 803   struct dfst_node *node;
 804   struct dfst_node *dfst;
 805   basic_block bb;
 806
 807   /* Allocate stack for back-tracking up CFG.  */
 808   stack = xmalloc ((n_basic_blocks + 1) * sizeof (edge));
 809   sp = 0;
 810
 811   /* Allocate the tree.  */
 812   dfst = xcalloc (last_basic_block, sizeof (struct dfst_node));
 813
 814   FOR_EACH_BB (bb)
 815     {
 816       max_successors = EDGE_COUNT (bb->succs);
 817       dfst[bb->index].node
 818         = (max_successors
 819            ? xcalloc (max_successors, sizeof (struct dfst_node *)) : NULL);
 820     }
 821
 822   /* Allocate bitmap to track nodes that have been visited.  */
 823   visited = sbitmap_alloc (last_basic_block);
 824
 825   /* None of the nodes in the CFG have been visited yet.  */
 826   sbitmap_zero (visited);
 827
 828   /* Push the first edge on to the stack.  */
 829   stack[sp++] = ei_start (ENTRY_BLOCK_PTR->succs);
 830
 831   while (sp)
 832     {
 833       basic_block src;
 834       basic_block dest;
 835
 836       /* Look at the edge on the top of the stack.  */
 837       ei = stack[sp - 1];
 838       src = ei_edge (ei)->src;
 839       dest = ei_edge (ei)->dest;
 840
 841       /* Check if the edge destination has been visited yet.  */
 842       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 843         {
 844           /* Mark that we have visited the destination.  */
 845           SET_BIT (visited, dest->index);
 846
 847           /* Add the destination to the preorder tree.  */
 848           if (src != ENTRY_BLOCK_PTR)
 849             {
 850               dfst[src->index].node[dfst[src->index].nnodes++]
 851                 = &dfst[dest->index];
 852               dfst[dest->index].up = &dfst[src->index];
 853             }
 854
 855           if (EDGE_COUNT (dest->succs) > 0)
 856             /* Since the DEST node has been visited for the first
 857                time, check its successors.  */
 858             stack[sp++] = ei_start (dest->succs);
 859         }
 860
 861       else if (! ei_one_before_end_p (ei))
 862         ei_next (&stack[sp - 1]);
 863       else
 864         sp--;
 865     }
 866
 867   free (stack);
 868   sbitmap_free (visited);
 869
 870   /* Record the preorder transversal order by
 871      walking the tree from right to left.  */
 872
 873   i = 0;
 874   node = &dfst[ENTRY_BLOCK_PTR->next_bb->index];
 875   pot_order[i++] = 0;
 876
 877   while (node)
 878     {
 879       if (node->nnodes)
 880         {
 881           node = node->node[--node->nnodes];
 882           pot_order[i++] = node - dfst;
 883         }
 884       else
 885         node = node->up;
 886     }
 887
 888   /* Free the tree.  */
 889
 890   for (i = 0; i < last_basic_block; i++)
 891     if (dfst[i].node)
 892       free (dfst[i].node);
 893
 894   free (dfst);
 895 }
 896
 897 /* Compute the depth first search order on the _reverse_ graph and
 898    store in the array DFS_ORDER, marking the nodes visited in VISITED.
 899    Returns the number of nodes visited.
 900
 901    The computation is split into three pieces:
 902
 903    flow_dfs_compute_reverse_init () creates the necessary data
 904    structures.
 905
 906    flow_dfs_compute_reverse_add_bb () adds a basic block to the data
 907    structures.  The block will start the search.
 908
 909    flow_dfs_compute_reverse_execute () continues (or starts) the
 910    search using the block on the top of the stack, stopping when the
 911    stack is empty.
 912
 913    flow_dfs_compute_reverse_finish () destroys the necessary data
 914    structures.
 915
 916    Thus, the user will probably call ..._init(), call ..._add_bb() to
 917    add a beginning basic block to the stack, call ..._execute(),
 918    possibly add another bb to the stack and again call ..._execute(),
 919    ..., and finally call _finish().  */
 920
 921 /* Initialize the data structures used for depth-first search on the
 922    reverse graph.  If INITIALIZE_STACK is nonzero, the exit block is
 923    added to the basic block stack.  DATA is the current depth-first
 924    search context.  If INITIALIZE_STACK is nonzero, there is an
 925    element on the stack.  */
 926
 927 static void
 928 flow_dfs_compute_reverse_init (depth_first_search_ds data)
 929 {
 930   /* Allocate stack for back-tracking up CFG.  */
 931   data->stack = xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
 932                          * sizeof (basic_block));
 933   data->sp = 0;
 934
 935   /* Allocate bitmap to track nodes that have been visited.  */
 936   data->visited_blocks = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
 937
 938   /* None of the nodes in the CFG have been visited yet.  */
 939   sbitmap_zero (data->visited_blocks);
 940
 941   return;
 942 }
 943
 944 /* Add the specified basic block to the top of the dfs data
 945    structures.  When the search continues, it will start at the
 946    block.  */
 947
 948 static void
 949 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb)
 950 {
 951   data->stack[data->sp++] = bb;
 952   SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1));
 953 }
 954
 955 /* Continue the depth-first search through the reverse graph starting with the
 956    block at the stack's top and ending when the stack is empty.  Visited nodes
 957    are marked.  Returns an unvisited basic block, or NULL if there is none
 958    available.  */
 959
 960 static basic_block
 961 flow_dfs_compute_reverse_execute (depth_first_search_ds data)
 962 {
 963   basic_block bb;
 964   edge e;
 965   edge_iterator ei;
 966
 967   while (data->sp > 0)
 968     {
 969       bb = data->stack[--data->sp];
 970
 971       /* Perform depth-first search on adjacent vertices.  */
 972       FOR_EACH_EDGE (e, ei, bb->preds)
 973         if (!TEST_BIT (data->visited_blocks,
 974                        e->src->index - (INVALID_BLOCK + 1)))
 975           flow_dfs_compute_reverse_add_bb (data, e->src);
 976     }
 977
 978   /* Determine if there are unvisited basic blocks.  */
 979   FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
 980     if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
 981       return bb;
 982
 983   return NULL;
 984 }
 985
 986 /* Destroy the data structures needed for depth-first search on the
 987    reverse graph.  */
 988
 989 static void
 990 flow_dfs_compute_reverse_finish (depth_first_search_ds data)
 991 {
 992   free (data->stack);
 993   sbitmap_free (data->visited_blocks);
 994 }
 995
 996 /* Performs dfs search from BB over vertices satisfying PREDICATE;
 997    if REVERSE, go against direction of edges.  Returns number of blocks
 998    found and their list in RSLT.  RSLT can contain at most RSLT_MAX items.  */
 999 int
1000 dfs_enumerate_from (basic_block bb, int reverse,
1001                     bool (*predicate) (basic_block, void *),
1002                     basic_block *rslt, int rslt_max, void *data)
1003 {
1004   basic_block *st, lbb;
1005   int sp = 0, tv = 0;
1006
1007   st = xcalloc (rslt_max, sizeof (basic_block));
1008   rslt[tv++] = st[sp++] = bb;
1009   bb->flags |= BB_VISITED;
1010   while (sp)
1011     {
1012       edge e;
1013       edge_iterator ei;
1014       lbb = st[--sp];
1015       if (reverse)
1016         {
1017           FOR_EACH_EDGE (e, ei, lbb->preds)
1018             if (!(e->src->flags & BB_VISITED) && predicate (e->src, data))
1019               {
1020                 gcc_assert (tv != rslt_max);
1021                 rslt[tv++] = st[sp++] = e->src;
1022                 e->src->flags |= BB_VISITED;
1023               }
1024         }
1025       else
1026         {
1027           FOR_EACH_EDGE (e, ei, lbb->succs)
1028             if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data))
1029               {
1030                 gcc_assert (tv != rslt_max);
1031                 rslt[tv++] = st[sp++] = e->dest;
1032                 e->dest->flags |= BB_VISITED;
1033               }
1034         }
1035     }
1036   free (st);
1037   for (sp = 0; sp < tv; sp++)
1038     rslt[sp]->flags &= ~BB_VISITED;
1039   return tv;
1040 }
1041
1042
1043 /* Computing the Dominance Frontier:
1044
1045    As described in Morgan, section 3.5, this may be done simply by
1046    walking the dominator tree bottom-up, computing the frontier for
1047    the children before the parent.  When considering a block B,
1048    there are two cases:
1049
1050    (1) A flow graph edge leaving B that does not lead to a child
1051    of B in the dominator tree must be a block that is either equal
1052    to B or not dominated by B.  Such blocks belong in the frontier
1053    of B.
1054
1055    (2) Consider a block X in the frontier of one of the children C
1056    of B.  If X is not equal to B and is not dominated by B, it
1057    is in the frontier of B.  */
1058
1059 static void
1060 compute_dominance_frontiers_1 (bitmap *frontiers, basic_block bb, sbitmap done)
1061 {
1062   edge e;
1063   edge_iterator ei;
1064   basic_block c;
1065
1066   SET_BIT (done, bb->index);
1067
1068   /* Do the frontier of the children first.  Not all children in the
1069      dominator tree (blocks dominated by this one) are children in the
1070      CFG, so check all blocks.  */
1071   for (c = first_dom_son (CDI_DOMINATORS, bb);
1072        c;
1073        c = next_dom_son (CDI_DOMINATORS, c))
1074     {
1075       if (! TEST_BIT (done, c->index))
1076         compute_dominance_frontiers_1 (frontiers, c, done);
1077     }
1078
1079   /* Find blocks conforming to rule (1) above.  */
1080   FOR_EACH_EDGE (e, ei, bb->succs)
1081     {
1082       if (e->dest == EXIT_BLOCK_PTR)
1083         continue;
1084       if (get_immediate_dominator (CDI_DOMINATORS, e->dest) != bb)
1085         bitmap_set_bit (frontiers[bb->index], e->dest->index);
1086     }
1087
1088   /* Find blocks conforming to rule (2).  */
1089   for (c = first_dom_son (CDI_DOMINATORS, bb);
1090        c;
1091        c = next_dom_son (CDI_DOMINATORS, c))
1092     {
1093       int x;
1094       bitmap_iterator bi;
1095
1096       EXECUTE_IF_SET_IN_BITMAP (frontiers[c->index], 0, x, bi)
1097         {
1098           if (get_immediate_dominator (CDI_DOMINATORS, BASIC_BLOCK (x)) != bb)
1099             bitmap_set_bit (frontiers[bb->index], x);
1100         }
1101     }
1102 }
1103
1104
1105 void
1106 compute_dominance_frontiers (bitmap *frontiers)
1107 {
1108   sbitmap done = sbitmap_alloc (last_basic_block);
1109
1110   timevar_push (TV_DOM_FRONTIERS);
1111
1112   sbitmap_zero (done);
1113
1114   compute_dominance_frontiers_1 (frontiers, EDGE_SUCC (ENTRY_BLOCK_PTR, 0)->dest, done);
1115
1116   sbitmap_free (done);
1117
1118   timevar_pop (TV_DOM_FRONTIERS);
1119 }
1120