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