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