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