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; insn != bb->end; 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 = src->end;
 107   rtx insn2 = target->head;
 108
 109   if (src->next_bb != target)
 110     return 0;
 111
 112   if (!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 = (int *) xcalloc (last_basic_block, sizeof (int));
 143   post = (int *) xcalloc (last_basic_block, sizeof (int));
 144
 145   /* Allocate stack for back-tracking up CFG.  */
 146   stack = (edge *) 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))
 236         continue;
 237       if (!invert_jump (bb->end, JUMP_LABEL (bb->end), 0))
 238         continue;
 239       invert_jump (bb->end, JUMP_LABEL (bb->end), 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;
 309
 310       /* Back up past insns that must be kept in the same block as a call.  */
 311       while (insn != bb->head
 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; ; 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
 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)
 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)
 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)
 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 =
 406         (basic_block *) xmalloc (sizeof (basic_block) * n_basic_blocks);
 407
 408   /* Clear all the reachability flags.  */
 409
 410   FOR_EACH_BB (bb)
 411     bb->flags &= ~BB_REACHABLE;
 412
 413   /* Add our starting points to the worklist.  Almost always there will
 414      be only one.  It isn't inconceivable that we might one day directly
 415      support Fortran alternate entry points.  */
 416
 417   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
 418     {
 419       *tos++ = e->dest;
 420
 421       /* Mark the block reachable.  */
 422       e->dest->flags |= BB_REACHABLE;
 423     }
 424
 425   /* Iterate: find everything reachable from what we've already seen.  */
 426
 427   while (tos != worklist)
 428     {
 429       basic_block b = *--tos;
 430
 431       for (e = b->succ; e; e = e->succ_next)
 432         if (!(e->dest->flags & BB_REACHABLE))
 433           {
 434             *tos++ = e->dest;
 435             e->dest->flags |= BB_REACHABLE;
 436           }
 437     }
 438
 439   free (worklist);
 440 }
 441 \f
 442 /* Functions to access an edge list with a vector representation.
 443    Enough data is kept such that given an index number, the
 444    pred and succ that edge represents can be determined, or
 445    given a pred and a succ, its index number can be returned.
 446    This allows algorithms which consume a lot of memory to
 447    represent the normally full matrix of edge (pred,succ) with a
 448    single indexed vector,  edge (EDGE_INDEX (pred, succ)), with no
 449    wasted space in the client code due to sparse flow graphs.  */
 450
 451 /* This functions initializes the edge list. Basically the entire
 452    flowgraph is processed, and all edges are assigned a number,
 453    and the data structure is filled in.  */
 454
 455 struct edge_list *
 456 create_edge_list (void)
 457 {
 458   struct edge_list *elist;
 459   edge e;
 460   int num_edges;
 461   int block_count;
 462   basic_block bb;
 463
 464   block_count = n_basic_blocks + 2;   /* Include the entry and exit blocks.  */
 465
 466   num_edges = 0;
 467
 468   /* Determine the number of edges in the flow graph by counting successor
 469      edges on each basic block.  */
 470   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 471     {
 472       for (e = bb->succ; e; e = e->succ_next)
 473         num_edges++;
 474     }
 475
 476   elist = (struct edge_list *) xmalloc (sizeof (struct edge_list));
 477   elist->num_blocks = block_count;
 478   elist->num_edges = num_edges;
 479   elist->index_to_edge = (edge *) xmalloc (sizeof (edge) * num_edges);
 480
 481   num_edges = 0;
 482
 483   /* Follow successors of blocks, and register these edges.  */
 484   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 485     for (e = bb->succ; e; e = e->succ_next)
 486       elist->index_to_edge[num_edges++] = e;
 487
 488   return elist;
 489 }
 490
 491 /* This function free's memory associated with an edge list.  */
 492
 493 void
 494 free_edge_list (struct edge_list *elist)
 495 {
 496   if (elist)
 497     {
 498       free (elist->index_to_edge);
 499       free (elist);
 500     }
 501 }
 502
 503 /* This function provides debug output showing an edge list.  */
 504
 505 void
 506 print_edge_list (FILE *f, struct edge_list *elist)
 507 {
 508   int x;
 509
 510   fprintf (f, "Compressed edge list, %d BBs + entry & exit, and %d edges\n",
 511            elist->num_blocks - 2, elist->num_edges);
 512
 513   for (x = 0; x < elist->num_edges; x++)
 514     {
 515       fprintf (f, " %-4d - edge(", x);
 516       if (INDEX_EDGE_PRED_BB (elist, x) == ENTRY_BLOCK_PTR)
 517         fprintf (f, "entry,");
 518       else
 519         fprintf (f, "%d,", INDEX_EDGE_PRED_BB (elist, x)->index);
 520
 521       if (INDEX_EDGE_SUCC_BB (elist, x) == EXIT_BLOCK_PTR)
 522         fprintf (f, "exit)\n");
 523       else
 524         fprintf (f, "%d)\n", INDEX_EDGE_SUCC_BB (elist, x)->index);
 525     }
 526 }
 527
 528 /* This function provides an internal consistency check of an edge list,
 529    verifying that all edges are present, and that there are no
 530    extra edges.  */
 531
 532 void
 533 verify_edge_list (FILE *f, struct edge_list *elist)
 534 {
 535   int pred, succ, index;
 536   edge e;
 537   basic_block bb, p, s;
 538
 539   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 540     {
 541       for (e = bb->succ; e; e = e->succ_next)
 542         {
 543           pred = e->src->index;
 544           succ = e->dest->index;
 545           index = EDGE_INDEX (elist, e->src, e->dest);
 546           if (index == EDGE_INDEX_NO_EDGE)
 547             {
 548               fprintf (f, "*p* No index for edge from %d to %d\n", pred, succ);
 549               continue;
 550             }
 551
 552           if (INDEX_EDGE_PRED_BB (elist, index)->index != pred)
 553             fprintf (f, "*p* Pred for index %d should be %d not %d\n",
 554                      index, pred, INDEX_EDGE_PRED_BB (elist, index)->index);
 555           if (INDEX_EDGE_SUCC_BB (elist, index)->index != succ)
 556             fprintf (f, "*p* Succ for index %d should be %d not %d\n",
 557                      index, succ, INDEX_EDGE_SUCC_BB (elist, index)->index);
 558         }
 559     }
 560
 561   /* We've verified that all the edges are in the list, now lets make sure
 562      there are no spurious edges in the list.  */
 563
 564   FOR_BB_BETWEEN (p, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 565     FOR_BB_BETWEEN (s, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 566       {
 567         int found_edge = 0;
 568
 569         for (e = p->succ; e; e = e->succ_next)
 570           if (e->dest == s)
 571             {
 572               found_edge = 1;
 573               break;
 574             }
 575
 576         for (e = s->pred; e; e = e->pred_next)
 577           if (e->src == p)
 578             {
 579               found_edge = 1;
 580               break;
 581             }
 582
 583         if (EDGE_INDEX (elist, p, s)
 584             == EDGE_INDEX_NO_EDGE && found_edge != 0)
 585           fprintf (f, "*** Edge (%d, %d) appears to not have an index\n",
 586                    p->index, s->index);
 587         if (EDGE_INDEX (elist, p, s)
 588             != EDGE_INDEX_NO_EDGE && found_edge == 0)
 589           fprintf (f, "*** Edge (%d, %d) has index %d, but there is no edge\n",
 590                    p->index, s->index, EDGE_INDEX (elist, p, s));
 591       }
 592 }
 593
 594 /* This routine will determine what, if any, edge there is between
 595    a specified predecessor and successor.  */
 596
 597 int
 598 find_edge_index (struct edge_list *edge_list, basic_block pred, basic_block succ)
 599 {
 600   int x;
 601
 602   for (x = 0; x < NUM_EDGES (edge_list); x++)
 603     if (INDEX_EDGE_PRED_BB (edge_list, x) == pred
 604         && INDEX_EDGE_SUCC_BB (edge_list, x) == succ)
 605       return x;
 606
 607   return (EDGE_INDEX_NO_EDGE);
 608 }
 609
 610 /* Dump the list of basic blocks in the bitmap NODES.  */
 611
 612 void
 613 flow_nodes_print (const char *str, const sbitmap nodes, FILE *file)
 614 {
 615   int node;
 616
 617   if (! nodes)
 618     return;
 619
 620   fprintf (file, "%s { ", str);
 621   EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, node, {fprintf (file, "%d ", node);});
 622   fputs ("}\n", file);
 623 }
 624
 625 /* Dump the list of edges in the array EDGE_LIST.  */
 626
 627 void
 628 flow_edge_list_print (const char *str, const edge *edge_list, int num_edges, FILE *file)
 629 {
 630   int i;
 631
 632   if (! edge_list)
 633     return;
 634
 635   fprintf (file, "%s { ", str);
 636   for (i = 0; i < num_edges; i++)
 637     fprintf (file, "%d->%d ", edge_list[i]->src->index,
 638              edge_list[i]->dest->index);
 639
 640   fputs ("}\n", file);
 641 }
 642
 643 \f
 644 /* This routine will remove any fake successor edges for a basic block.
 645    When the edge is removed, it is also removed from whatever predecessor
 646    list it is in.  */
 647
 648 static void
 649 remove_fake_successors (basic_block bb)
 650 {
 651   edge e;
 652
 653   for (e = bb->succ; e;)
 654     {
 655       edge tmp = e;
 656
 657       e = e->succ_next;
 658       if ((tmp->flags & EDGE_FAKE) == EDGE_FAKE)
 659         remove_edge (tmp);
 660     }
 661 }
 662
 663 /* This routine will remove all fake edges from the flow graph.  If
 664    we remove all fake successors, it will automatically remove all
 665    fake predecessors.  */
 666
 667 void
 668 remove_fake_edges (void)
 669 {
 670   basic_block bb;
 671
 672   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 673     remove_fake_successors (bb);
 674 }
 675
 676 /* This function will add a fake edge between any block which has no
 677    successors, and the exit block. Some data flow equations require these
 678    edges to exist.  */
 679
 680 void
 681 add_noreturn_fake_exit_edges (void)
 682 {
 683   basic_block bb;
 684
 685   FOR_EACH_BB (bb)
 686     if (bb->succ == NULL)
 687       make_single_succ_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
 688 }
 689
 690 /* This function adds a fake edge between any infinite loops to the
 691    exit block.  Some optimizations require a path from each node to
 692    the exit node.
 693
 694    See also Morgan, Figure 3.10, pp. 82-83.
 695
 696    The current implementation is ugly, not attempting to minimize the
 697    number of inserted fake edges.  To reduce the number of fake edges
 698    to insert, add fake edges from _innermost_ loops containing only
 699    nodes not reachable from the exit block.  */
 700
 701 void
 702 connect_infinite_loops_to_exit (void)
 703 {
 704   basic_block unvisited_block;
 705   struct depth_first_search_dsS dfs_ds;
 706
 707   /* Perform depth-first search in the reverse graph to find nodes
 708      reachable from the exit block.  */
 709   flow_dfs_compute_reverse_init (&dfs_ds);
 710   flow_dfs_compute_reverse_add_bb (&dfs_ds, EXIT_BLOCK_PTR);
 711
 712   /* Repeatedly add fake edges, updating the unreachable nodes.  */
 713   while (1)
 714     {
 715       unvisited_block = flow_dfs_compute_reverse_execute (&dfs_ds);
 716       if (!unvisited_block)
 717         break;
 718
 719       make_edge (unvisited_block, EXIT_BLOCK_PTR, EDGE_FAKE);
 720       flow_dfs_compute_reverse_add_bb (&dfs_ds, unvisited_block);
 721     }
 722
 723   flow_dfs_compute_reverse_finish (&dfs_ds);
 724   return;
 725 }
 726 \f
 727 /* Compute reverse top sort order.  */
 728
 729 void
 730 flow_reverse_top_sort_order_compute (int *rts_order)
 731 {
 732   edge *stack;
 733   int sp;
 734   int postnum = 0;
 735   sbitmap visited;
 736
 737   /* Allocate stack for back-tracking up CFG.  */
 738   stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
 739   sp = 0;
 740
 741   /* Allocate bitmap to track nodes that have been visited.  */
 742   visited = sbitmap_alloc (last_basic_block);
 743
 744   /* None of the nodes in the CFG have been visited yet.  */
 745   sbitmap_zero (visited);
 746
 747   /* Push the first edge on to the stack.  */
 748   stack[sp++] = ENTRY_BLOCK_PTR->succ;
 749
 750   while (sp)
 751     {
 752       edge e;
 753       basic_block src;
 754       basic_block dest;
 755
 756       /* Look at the edge on the top of the stack.  */
 757       e = stack[sp - 1];
 758       src = e->src;
 759       dest = e->dest;
 760
 761       /* Check if the edge destination has been visited yet.  */
 762       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 763         {
 764           /* Mark that we have visited the destination.  */
 765           SET_BIT (visited, dest->index);
 766
 767           if (dest->succ)
 768             /* Since the DEST node has been visited for the first
 769                time, check its successors.  */
 770             stack[sp++] = dest->succ;
 771           else
 772             rts_order[postnum++] = dest->index;
 773         }
 774       else
 775         {
 776           if (! e->succ_next && src != ENTRY_BLOCK_PTR)
 777            rts_order[postnum++] = src->index;
 778
 779           if (e->succ_next)
 780             stack[sp - 1] = e->succ_next;
 781           else
 782             sp--;
 783         }
 784     }
 785
 786   free (stack);
 787   sbitmap_free (visited);
 788 }
 789
 790 /* Compute the depth first search order and store in the array
 791   DFS_ORDER if nonzero, marking the nodes visited in VISITED.  If
 792   RC_ORDER is nonzero, return the reverse completion number for each
 793   node.  Returns the number of nodes visited.  A depth first search
 794   tries to get as far away from the starting point as quickly as
 795   possible.  */
 796
 797 int
 798 flow_depth_first_order_compute (int *dfs_order, int *rc_order)
 799 {
 800   edge *stack;
 801   int sp;
 802   int dfsnum = 0;
 803   int rcnum = n_basic_blocks - 1;
 804   sbitmap visited;
 805
 806   /* Allocate stack for back-tracking up CFG.  */
 807   stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
 808   sp = 0;
 809
 810   /* Allocate bitmap to track nodes that have been visited.  */
 811   visited = sbitmap_alloc (last_basic_block);
 812
 813   /* None of the nodes in the CFG have been visited yet.  */
 814   sbitmap_zero (visited);
 815
 816   /* Push the first edge on to the stack.  */
 817   stack[sp++] = ENTRY_BLOCK_PTR->succ;
 818
 819   while (sp)
 820     {
 821       edge e;
 822       basic_block src;
 823       basic_block dest;
 824
 825       /* Look at the edge on the top of the stack.  */
 826       e = stack[sp - 1];
 827       src = e->src;
 828       dest = e->dest;
 829
 830       /* Check if the edge destination has been visited yet.  */
 831       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 832         {
 833           /* Mark that we have visited the destination.  */
 834           SET_BIT (visited, dest->index);
 835
 836           if (dfs_order)
 837             dfs_order[dfsnum] = dest->index;
 838
 839           dfsnum++;
 840
 841           if (dest->succ)
 842             /* Since the DEST node has been visited for the first
 843                time, check its successors.  */
 844             stack[sp++] = dest->succ;
 845           else if (rc_order)
 846             /* There are no successors for the DEST node so assign
 847                its reverse completion number.  */
 848             rc_order[rcnum--] = dest->index;
 849         }
 850       else
 851         {
 852           if (! e->succ_next && src != ENTRY_BLOCK_PTR
 853               && rc_order)
 854             /* There are no more successors for the SRC node
 855                so assign its reverse completion number.  */
 856             rc_order[rcnum--] = src->index;
 857
 858           if (e->succ_next)
 859             stack[sp - 1] = e->succ_next;
 860           else
 861             sp--;
 862         }
 863     }
 864
 865   free (stack);
 866   sbitmap_free (visited);
 867
 868   /* The number of nodes visited should not be greater than
 869      n_basic_blocks.  */
 870   if (dfsnum > n_basic_blocks)
 871     abort ();
 872
 873   /* There are some nodes left in the CFG that are unreachable.  */
 874   if (dfsnum < n_basic_blocks)
 875     abort ();
 876
 877   return dfsnum;
 878 }
 879
 880 struct dfst_node
 881 {
 882     unsigned nnodes;
 883     struct dfst_node **node;
 884     struct dfst_node *up;
 885 };
 886
 887 /* Compute a preorder transversal ordering such that a sub-tree which
 888    is the source of a cross edge appears before the sub-tree which is
 889    the destination of the cross edge.  This allows for easy detection
 890    of all the entry blocks for a loop.
 891
 892    The ordering is compute by:
 893
 894      1) Generating a depth first spanning tree.
 895
 896      2) Walking the resulting tree from right to left.  */
 897
 898 void
 899 flow_preorder_transversal_compute (int *pot_order)
 900 {
 901   edge e;
 902   edge *stack;
 903   int i;
 904   int max_successors;
 905   int sp;
 906   sbitmap visited;
 907   struct dfst_node *node;
 908   struct dfst_node *dfst;
 909   basic_block bb;
 910
 911   /* Allocate stack for back-tracking up CFG.  */
 912   stack = (edge *) xmalloc ((n_basic_blocks + 1) * sizeof (edge));
 913   sp = 0;
 914
 915   /* Allocate the tree.  */
 916   dfst = (struct dfst_node *) xcalloc (last_basic_block,
 917                                        sizeof (struct dfst_node));
 918
 919   FOR_EACH_BB (bb)
 920     {
 921       max_successors = 0;
 922       for (e = bb->succ; e; e = e->succ_next)
 923         max_successors++;
 924
 925       dfst[bb->index].node
 926         = (max_successors
 927            ? (struct dfst_node **) xcalloc (max_successors,
 928                                             sizeof (struct dfst_node *))
 929            : NULL);
 930     }
 931
 932   /* Allocate bitmap to track nodes that have been visited.  */
 933   visited = sbitmap_alloc (last_basic_block);
 934
 935   /* None of the nodes in the CFG have been visited yet.  */
 936   sbitmap_zero (visited);
 937
 938   /* Push the first edge on to the stack.  */
 939   stack[sp++] = ENTRY_BLOCK_PTR->succ;
 940
 941   while (sp)
 942     {
 943       basic_block src;
 944       basic_block dest;
 945
 946       /* Look at the edge on the top of the stack.  */
 947       e = stack[sp - 1];
 948       src = e->src;
 949       dest = e->dest;
 950
 951       /* Check if the edge destination has been visited yet.  */
 952       if (dest != EXIT_BLOCK_PTR && ! TEST_BIT (visited, dest->index))
 953         {
 954           /* Mark that we have visited the destination.  */
 955           SET_BIT (visited, dest->index);
 956
 957           /* Add the destination to the preorder tree.  */
 958           if (src != ENTRY_BLOCK_PTR)
 959             {
 960               dfst[src->index].node[dfst[src->index].nnodes++]
 961                 = &dfst[dest->index];
 962               dfst[dest->index].up = &dfst[src->index];
 963             }
 964
 965           if (dest->succ)
 966             /* Since the DEST node has been visited for the first
 967                time, check its successors.  */
 968             stack[sp++] = dest->succ;
 969         }
 970
 971       else if (e->succ_next)
 972         stack[sp - 1] = e->succ_next;
 973       else
 974         sp--;
 975     }
 976
 977   free (stack);
 978   sbitmap_free (visited);
 979
 980   /* Record the preorder transversal order by
 981      walking the tree from right to left.  */
 982
 983   i = 0;
 984   node = &dfst[ENTRY_BLOCK_PTR->next_bb->index];
 985   pot_order[i++] = 0;
 986
 987   while (node)
 988     {
 989       if (node->nnodes)
 990         {
 991           node = node->node[--node->nnodes];
 992           pot_order[i++] = node - dfst;
 993         }
 994       else
 995         node = node->up;
 996     }
 997
 998   /* Free the tree.  */
 999
1000   for (i = 0; i < last_basic_block; i++)
1001     if (dfst[i].node)
1002       free (dfst[i].node);
1003
1004   free (dfst);
1005 }
1006
1007 /* Compute the depth first search order on the _reverse_ graph and
1008    store in the array DFS_ORDER, marking the nodes visited in VISITED.
1009    Returns the number of nodes visited.
1010
1011    The computation is split into three pieces:
1012
1013    flow_dfs_compute_reverse_init () creates the necessary data
1014    structures.
1015
1016    flow_dfs_compute_reverse_add_bb () adds a basic block to the data
1017    structures.  The block will start the search.
1018
1019    flow_dfs_compute_reverse_execute () continues (or starts) the
1020    search using the block on the top of the stack, stopping when the
1021    stack is empty.
1022
1023    flow_dfs_compute_reverse_finish () destroys the necessary data
1024    structures.
1025
1026    Thus, the user will probably call ..._init(), call ..._add_bb() to
1027    add a beginning basic block to the stack, call ..._execute(),
1028    possibly add another bb to the stack and again call ..._execute(),
1029    ..., and finally call _finish().  */
1030
1031 /* Initialize the data structures used for depth-first search on the
1032    reverse graph.  If INITIALIZE_STACK is nonzero, the exit block is
1033    added to the basic block stack.  DATA is the current depth-first
1034    search context.  If INITIALIZE_STACK is nonzero, there is an
1035    element on the stack.  */
1036
1037 static void
1038 flow_dfs_compute_reverse_init (depth_first_search_ds data)
1039 {
1040   /* Allocate stack for back-tracking up CFG.  */
1041   data->stack = (basic_block *) xmalloc ((n_basic_blocks - (INVALID_BLOCK + 1))
1042                                          * sizeof (basic_block));
1043   data->sp = 0;
1044
1045   /* Allocate bitmap to track nodes that have been visited.  */
1046   data->visited_blocks = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1));
1047
1048   /* None of the nodes in the CFG have been visited yet.  */
1049   sbitmap_zero (data->visited_blocks);
1050
1051   return;
1052 }
1053
1054 /* Add the specified basic block to the top of the dfs data
1055    structures.  When the search continues, it will start at the
1056    block.  */
1057
1058 static void
1059 flow_dfs_compute_reverse_add_bb (depth_first_search_ds data, basic_block bb)
1060 {
1061   data->stack[data->sp++] = bb;
1062   SET_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1));
1063 }
1064
1065 /* Continue the depth-first search through the reverse graph starting with the
1066    block at the stack's top and ending when the stack is empty.  Visited nodes
1067    are marked.  Returns an unvisited basic block, or NULL if there is none
1068    available.  */
1069
1070 static basic_block
1071 flow_dfs_compute_reverse_execute (depth_first_search_ds data)
1072 {
1073   basic_block bb;
1074   edge e;
1075
1076   while (data->sp > 0)
1077     {
1078       bb = data->stack[--data->sp];
1079
1080       /* Perform depth-first search on adjacent vertices.  */
1081       for (e = bb->pred; e; e = e->pred_next)
1082         if (!TEST_BIT (data->visited_blocks,
1083                        e->src->index - (INVALID_BLOCK + 1)))
1084           flow_dfs_compute_reverse_add_bb (data, e->src);
1085     }
1086
1087   /* Determine if there are unvisited basic blocks.  */
1088   FOR_BB_BETWEEN (bb, EXIT_BLOCK_PTR, NULL, prev_bb)
1089     if (!TEST_BIT (data->visited_blocks, bb->index - (INVALID_BLOCK + 1)))
1090       return bb;
1091
1092   return NULL;
1093 }
1094
1095 /* Destroy the data structures needed for depth-first search on the
1096    reverse graph.  */
1097
1098 static void
1099 flow_dfs_compute_reverse_finish (depth_first_search_ds data)
1100 {
1101   free (data->stack);
1102   sbitmap_free (data->visited_blocks);
1103 }
1104
1105 /* Performs dfs search from BB over vertices satisfying PREDICATE;
1106    if REVERSE, go against direction of edges.  Returns number of blocks
1107    found and their list in RSLT.  RSLT can contain at most RSLT_MAX items.  */
1108 int
1109 dfs_enumerate_from (basic_block bb, int reverse,
1110                     bool (*predicate) (basic_block, void *),
1111                     basic_block *rslt, int rslt_max, void *data)
1112 {
1113   basic_block *st, lbb;
1114   int sp = 0, tv = 0;
1115
1116   st = xcalloc (rslt_max, sizeof (basic_block));
1117   rslt[tv++] = st[sp++] = bb;
1118   bb->flags |= BB_VISITED;
1119   while (sp)
1120     {
1121       edge e;
1122       lbb = st[--sp];
1123       if (reverse)
1124         {
1125           for (e = lbb->pred; e; e = e->pred_next)
1126             if (!(e->src->flags & BB_VISITED) && predicate (e->src, data))
1127               {
1128                 if (tv == rslt_max)
1129                   abort ();
1130                 rslt[tv++] = st[sp++] = e->src;
1131                 e->src->flags |= BB_VISITED;
1132               }
1133         }
1134       else
1135         {
1136           for (e = lbb->succ; e; e = e->succ_next)
1137             if (!(e->dest->flags & BB_VISITED) && predicate (e->dest, data))
1138               {
1139                 if (tv == rslt_max)
1140                   abort ();
1141                 rslt[tv++] = st[sp++] = e->dest;
1142                 e->dest->flags |= BB_VISITED;
1143               }
1144         }
1145     }
1146   free (st);
1147   for (sp = 0; sp < tv; sp++)
1148     rslt[sp]->flags &= ~BB_VISITED;
1149   return tv;
1150 }