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