gcc/cfg.c

   1 /* Control flow graph manipulation code for GNU compiler.
   2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /* This file contains low level functions to manipulate the CFG and
  23    analyze it.  All other modules should not transform the data structure
  24    directly and use abstraction instead.  The file is supposed to be
  25    ordered bottom-up and should not contain any code dependent on a
  26    particular intermediate language (RTL or trees).
  27
  28    Available functionality:
  29      - Initialization/deallocation
  30          init_flow, clear_edges
  31      - Low level basic block manipulation
  32          alloc_block, expunge_block
  33      - Edge manipulation
  34          make_edge, make_single_succ_edge, cached_make_edge, remove_edge
  35          - Low level edge redirection (without updating instruction chain)
  36              redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
  37      - Dumping and debugging
  38          dump_flow_info, debug_flow_info, dump_edge_info
  39      - Allocation of AUX fields for basic blocks
  40          alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block
  41      - clear_bb_flags
  42      - Consistency checking
  43          verify_flow_info
  44      - Dumping and debugging
  45          print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
  46  */
  47 \f
  48 #include "config.h"
  49 #include "system.h"
  50 #include "coretypes.h"
  51 #include "tm.h"
  52 #include "tree.h"
  53 #include "rtl.h"
  54 #include "hard-reg-set.h"
  55 #include "basic-block.h"
  56 #include "regs.h"
  57 #include "flags.h"
  58 #include "output.h"
  59 #include "function.h"
  60 #include "except.h"
  61 #include "toplev.h"
  62 #include "tm_p.h"
  63 #include "obstack.h"
  64 #include "alloc-pool.h"
  65 #include "timevar.h"
  66 #include "ggc.h"
  67
  68 /* The obstack on which the flow graph components are allocated.  */
  69
  70 struct obstack flow_obstack;
  71 static char *flow_firstobj;
  72
  73 /* Number of basic blocks in the current function.  */
  74
  75 int n_basic_blocks;
  76
  77 /* First free basic block number.  */
  78
  79 int last_basic_block;
  80
  81 /* Number of edges in the current function.  */
  82
  83 int n_edges;
  84
  85 /* The basic block array.  */
  86
  87 varray_type basic_block_info;
  88
  89 /* The special entry and exit blocks.  */
  90 basic_block ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR;
  91
  92 /* Memory alloc pool for bb member rbi.  */
  93 alloc_pool rbi_pool;
  94
  95 void debug_flow_info (void);
  96 static void free_edge (edge);
  97
  98 /* Indicate the presence of the profile.  */
  99 enum profile_status profile_status;
 100 \f
 101 /* Called once at initialization time.  */
 102
 103 void
 104 init_flow (void)
 105 {
 106   static int initialized;
 107
 108   n_edges = 0;
 109
 110   if (!initialized)
 111     {
 112       gcc_obstack_init (&flow_obstack);
 113       flow_firstobj = obstack_alloc (&flow_obstack, 0);
 114       initialized = 1;
 115     }
 116   else
 117     {
 118       obstack_free (&flow_obstack, flow_firstobj);
 119       flow_firstobj = obstack_alloc (&flow_obstack, 0);
 120     }
 121
 122   ENTRY_BLOCK_PTR = ggc_alloc_cleared (sizeof (*ENTRY_BLOCK_PTR));
 123   ENTRY_BLOCK_PTR->index = ENTRY_BLOCK;
 124   EXIT_BLOCK_PTR = ggc_alloc_cleared (sizeof (*EXIT_BLOCK_PTR));
 125   EXIT_BLOCK_PTR->index = EXIT_BLOCK;
 126   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
 127   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
 128 }
 129 \f
 130 /* Helper function for remove_edge and clear_edges.  Frees edge structure
 131    without actually unlinking it from the pred/succ lists.  */
 132
 133 static void
 134 free_edge (edge e ATTRIBUTE_UNUSED)
 135 {
 136   n_edges--;
 137   ggc_free (e);
 138 }
 139
 140 /* Free the memory associated with the edge structures.  */
 141
 142 void
 143 clear_edges (void)
 144 {
 145   basic_block bb;
 146   edge e;
 147   edge_iterator ei;
 148
 149   FOR_EACH_BB (bb)
 150     {
 151       FOR_EACH_EDGE (e, ei, bb->succs)
 152         free_edge (e);
 153       VEC_truncate (edge, bb->succs, 0);
 154       VEC_truncate (edge, bb->preds, 0);
 155     }
 156
 157   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 158     free_edge (e);
 159   VEC_truncate (edge, EXIT_BLOCK_PTR->preds, 0);
 160   VEC_truncate (edge, ENTRY_BLOCK_PTR->succs, 0);
 161
 162   gcc_assert (!n_edges);
 163 }
 164 \f
 165 /* Allocate memory for basic_block.  */
 166
 167 basic_block
 168 alloc_block (void)
 169 {
 170   basic_block bb;
 171   bb = ggc_alloc_cleared (sizeof (*bb));
 172   return bb;
 173 }
 174
 175 /* Create memory pool for rbi_pool.  */
 176
 177 void
 178 alloc_rbi_pool (void)
 179 {
 180   rbi_pool = create_alloc_pool ("rbi pool",
 181                                 sizeof (struct reorder_block_def),
 182                                 n_basic_blocks + 2);
 183 }
 184
 185 /* Free rbi_pool.  */
 186
 187 void
 188 free_rbi_pool (void)
 189 {
 190   free_alloc_pool (rbi_pool);
 191 }
 192
 193 /* Initialize rbi (the structure containing data used by basic block
 194    duplication and reordering) for the given basic block.  */
 195
 196 void
 197 initialize_bb_rbi (basic_block bb)
 198 {
 199   gcc_assert (!bb->rbi);
 200   bb->rbi = pool_alloc (rbi_pool);
 201   memset (bb->rbi, 0, sizeof (struct reorder_block_def));
 202 }
 203
 204 /* Link block B to chain after AFTER.  */
 205 void
 206 link_block (basic_block b, basic_block after)
 207 {
 208   b->next_bb = after->next_bb;
 209   b->prev_bb = after;
 210   after->next_bb = b;
 211   b->next_bb->prev_bb = b;
 212 }
 213
 214 /* Unlink block B from chain.  */
 215 void
 216 unlink_block (basic_block b)
 217 {
 218   b->next_bb->prev_bb = b->prev_bb;
 219   b->prev_bb->next_bb = b->next_bb;
 220   b->prev_bb = NULL;
 221   b->next_bb = NULL;
 222 }
 223
 224 /* Sequentially order blocks and compact the arrays.  */
 225 void
 226 compact_blocks (void)
 227 {
 228   int i;
 229   basic_block bb;
 230
 231   i = 0;
 232   FOR_EACH_BB (bb)
 233     {
 234       BASIC_BLOCK (i) = bb;
 235       bb->index = i;
 236       i++;
 237     }
 238
 239   gcc_assert (i == n_basic_blocks);
 240
 241   for (; i < last_basic_block; i++)
 242     BASIC_BLOCK (i) = NULL;
 243
 244   last_basic_block = n_basic_blocks;
 245 }
 246
 247 /* Remove block B from the basic block array.  */
 248
 249 void
 250 expunge_block (basic_block b)
 251 {
 252   unlink_block (b);
 253   BASIC_BLOCK (b->index) = NULL;
 254   n_basic_blocks--;
 255   /* We should be able to ggc_free here, but we are not.
 256      The dead SSA_NAMES are left pointing to dead statements that are pointing
 257      to dead basic blocks making garbage collector to die.
 258      We should be able to release all dead SSA_NAMES and at the same time we should
 259      clear out BB pointer of dead statements consistently.  */
 260 }
 261 \f
 262 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
 263    created edge.  Use this only if you are sure that this edge can't
 264    possibly already exist.  */
 265
 266 edge
 267 unchecked_make_edge (basic_block src, basic_block dst, int flags)
 268 {
 269   edge e;
 270   e = ggc_alloc_cleared (sizeof (*e));
 271   n_edges++;
 272
 273   VEC_safe_push (edge, src->succs, e);
 274   VEC_safe_push (edge, dst->preds, e);
 275
 276   e->src = src;
 277   e->dest = dst;
 278   e->flags = flags;
 279
 280   return e;
 281 }
 282
 283 /* Create an edge connecting SRC and DST with FLAGS optionally using
 284    edge cache CACHE.  Return the new edge, NULL if already exist.  */
 285
 286 edge
 287 cached_make_edge (sbitmap *edge_cache, basic_block src, basic_block dst, int flags)
 288 {
 289   int use_edge_cache;
 290   edge e;
 291   edge_iterator ei;
 292
 293   /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that
 294      many edges to them, or we didn't allocate memory for it.  */
 295   use_edge_cache = (edge_cache
 296                     && src != ENTRY_BLOCK_PTR && dst != EXIT_BLOCK_PTR);
 297
 298   /* Make sure we don't add duplicate edges.  */
 299   switch (use_edge_cache)
 300     {
 301     default:
 302       /* Quick test for non-existence of the edge.  */
 303       if (! TEST_BIT (edge_cache[src->index], dst->index))
 304         break;
 305
 306       /* The edge exists; early exit if no work to do.  */
 307       if (flags == 0)
 308         return NULL;
 309
 310       /* Fall through.  */
 311     case 0:
 312       FOR_EACH_EDGE (e, ei, src->succs)
 313         {
 314           if (e->dest == dst)
 315             {
 316               e->flags |= flags;
 317               return NULL;
 318             }
 319         }
 320       break;
 321     }
 322
 323   e = unchecked_make_edge (src, dst, flags);
 324
 325   if (use_edge_cache)
 326     SET_BIT (edge_cache[src->index], dst->index);
 327
 328   return e;
 329 }
 330
 331 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
 332    created edge or NULL if already exist.  */
 333
 334 edge
 335 make_edge (basic_block src, basic_block dest, int flags)
 336 {
 337   return cached_make_edge (NULL, src, dest, flags);
 338 }
 339
 340 /* Create an edge connecting SRC to DEST and set probability by knowing
 341    that it is the single edge leaving SRC.  */
 342
 343 edge
 344 make_single_succ_edge (basic_block src, basic_block dest, int flags)
 345 {
 346   edge e = make_edge (src, dest, flags);
 347
 348   e->probability = REG_BR_PROB_BASE;
 349   e->count = src->count;
 350   return e;
 351 }
 352
 353 /* This function will remove an edge from the flow graph.  */
 354
 355 void
 356 remove_edge (edge e)
 357 {
 358   edge tmp;
 359   basic_block src, dest;
 360   bool found = false;
 361   unsigned ix;
 362
 363   src = e->src;
 364   dest = e->dest;
 365
 366   for (ix = 0; VEC_iterate (edge, src->succs, ix, tmp); )
 367     {
 368       if (tmp == e)
 369         {
 370           VEC_unordered_remove (edge, src->succs, ix);
 371           found = true;
 372           break;
 373         }
 374       else
 375         ix++;
 376     }
 377
 378   gcc_assert (found);
 379
 380   if (!found)
 381     abort ();
 382
 383   found = false;
 384   for (ix = 0; VEC_iterate (edge, dest->preds, ix, tmp); )
 385     {
 386       if (tmp == e)
 387         {
 388           VEC_unordered_remove (edge, dest->preds, ix);
 389           found = true;
 390           break;
 391         }
 392       else
 393         ix++;
 394     }
 395
 396   gcc_assert (found);
 397
 398   free_edge (e);
 399 }
 400
 401 /* Redirect an edge's successor from one block to another.  */
 402
 403 void
 404 redirect_edge_succ (edge e, basic_block new_succ)
 405 {
 406   edge tmp;
 407   unsigned ix;
 408   bool found = false;
 409
 410   /* Disconnect the edge from the old successor block.  */
 411   for (ix = 0; VEC_iterate (edge, e->dest->preds, ix, tmp); )
 412     {
 413       if (tmp == e)
 414         {
 415           VEC_unordered_remove (edge, e->dest->preds, ix);
 416           found = true;
 417           break;
 418         }
 419       else
 420         ix++;
 421     }
 422
 423   if (!found)
 424     abort ();
 425
 426   /* Reconnect the edge to the new successor block.  */
 427   VEC_safe_push (edge, new_succ->preds, e);
 428   e->dest = new_succ;
 429 }
 430
 431 /* Like previous but avoid possible duplicate edge.  */
 432
 433 edge
 434 redirect_edge_succ_nodup (edge e, basic_block new_succ)
 435 {
 436   edge s;
 437   edge_iterator ei;
 438
 439   /* Check whether the edge is already present.  */
 440   FOR_EACH_EDGE (s, ei, e->src->succs)
 441     {
 442       if (s->dest == new_succ && s != e)
 443         break;
 444     }
 445
 446   if (s)
 447     {
 448       s->flags |= e->flags;
 449       s->probability += e->probability;
 450       if (s->probability > REG_BR_PROB_BASE)
 451         s->probability = REG_BR_PROB_BASE;
 452       s->count += e->count;
 453       remove_edge (e);
 454       e = s;
 455     }
 456   else
 457     redirect_edge_succ (e, new_succ);
 458
 459   return e;
 460 }
 461
 462 /* Redirect an edge's predecessor from one block to another.  */
 463
 464 void
 465 redirect_edge_pred (edge e, basic_block new_pred)
 466 {
 467   edge tmp;
 468   bool found = false;
 469   unsigned ix;
 470
 471   /* Disconnect the edge from the old predecessor block.  */
 472   for (ix = 0; VEC_iterate (edge, e->src->succs, ix, tmp); )
 473     {
 474       if (tmp == e)
 475         {
 476           VEC_unordered_remove (edge, e->src->succs, ix);
 477           found = true;
 478           break;
 479         }
 480       else
 481         ix++;
 482     }
 483
 484   if (!found)
 485     abort ();
 486
 487   /* Reconnect the edge to the new predecessor block.  */
 488   VEC_safe_push (edge, new_pred->succs, e);
 489   e->src = new_pred;
 490 }
 491
 492 /* Clear all basic block flags, with the exception of partitioning.  */
 493 void
 494 clear_bb_flags (void)
 495 {
 496   basic_block bb;
 497
 498   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 499     bb->flags = BB_PARTITION (bb);
 500 }
 501 \f
 502 /* Check the consistency of profile information.  We can't do that
 503    in verify_flow_info, as the counts may get invalid for incompletely
 504    solved graphs, later eliminating of conditionals or roundoff errors.
 505    It is still practical to have them reported for debugging of simple
 506    testcases.  */
 507 void
 508 check_bb_profile (basic_block bb, FILE * file)
 509 {
 510   edge e;
 511   int sum = 0;
 512   gcov_type lsum;
 513   edge_iterator ei;
 514
 515   if (profile_status == PROFILE_ABSENT)
 516     return;
 517
 518   if (bb != EXIT_BLOCK_PTR)
 519     {
 520       FOR_EACH_EDGE (e, ei, bb->succs)
 521         sum += e->probability;
 522       if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
 523         fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
 524                  sum * 100.0 / REG_BR_PROB_BASE);
 525       lsum = 0;
 526       FOR_EACH_EDGE (e, ei, bb->succs)
 527         lsum += e->count;
 528       if (EDGE_COUNT (bb->succs)
 529           && (lsum - bb->count > 100 || lsum - bb->count < -100))
 530         fprintf (file, "Invalid sum of outgoing counts %i, should be %i\n",
 531                  (int) lsum, (int) bb->count);
 532     }
 533   if (bb != ENTRY_BLOCK_PTR)
 534     {
 535       sum = 0;
 536       FOR_EACH_EDGE (e, ei, bb->preds)
 537         sum += EDGE_FREQUENCY (e);
 538       if (abs (sum - bb->frequency) > 100)
 539         fprintf (file,
 540                  "Invalid sum of incoming frequencies %i, should be %i\n",
 541                  sum, bb->frequency);
 542       lsum = 0;
 543       FOR_EACH_EDGE (e, ei, bb->preds)
 544         lsum += e->count;
 545       if (lsum - bb->count > 100 || lsum - bb->count < -100)
 546         fprintf (file, "Invalid sum of incoming counts %i, should be %i\n",
 547                  (int) lsum, (int) bb->count);
 548     }
 549 }
 550 \f
 551 void
 552 dump_flow_info (FILE *file)
 553 {
 554   int i;
 555   basic_block bb;
 556   static const char * const reg_class_names[] = REG_CLASS_NAMES;
 557
 558   if (reg_n_info)
 559     {
 560       int max_regno = max_reg_num ();
 561       fprintf (file, "%d registers.\n", max_regno);
 562       for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
 563         if (REG_N_REFS (i))
 564           {
 565             enum reg_class class, altclass;
 566
 567             fprintf (file, "\nRegister %d used %d times across %d insns",
 568                      i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
 569             if (REG_BASIC_BLOCK (i) >= 0)
 570               fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
 571             if (REG_N_SETS (i))
 572               fprintf (file, "; set %d time%s", REG_N_SETS (i),
 573                        (REG_N_SETS (i) == 1) ? "" : "s");
 574             if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
 575               fprintf (file, "; user var");
 576             if (REG_N_DEATHS (i) != 1)
 577               fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
 578             if (REG_N_CALLS_CROSSED (i) == 1)
 579               fprintf (file, "; crosses 1 call");
 580             else if (REG_N_CALLS_CROSSED (i))
 581               fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
 582             if (regno_reg_rtx[i] != NULL
 583                 && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
 584               fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
 585
 586             class = reg_preferred_class (i);
 587             altclass = reg_alternate_class (i);
 588             if (class != GENERAL_REGS || altclass != ALL_REGS)
 589               {
 590                 if (altclass == ALL_REGS || class == ALL_REGS)
 591                   fprintf (file, "; pref %s", reg_class_names[(int) class]);
 592                 else if (altclass == NO_REGS)
 593                   fprintf (file, "; %s or none", reg_class_names[(int) class]);
 594                 else
 595                   fprintf (file, "; pref %s, else %s",
 596                            reg_class_names[(int) class],
 597                            reg_class_names[(int) altclass]);
 598               }
 599
 600             if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
 601               fprintf (file, "; pointer");
 602             fprintf (file, ".\n");
 603           }
 604     }
 605
 606   fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
 607   FOR_EACH_BB (bb)
 608     {
 609       edge e;
 610       edge_iterator ei;
 611
 612       fprintf (file, "\nBasic block %d ", bb->index);
 613       fprintf (file, "prev %d, next %d, ",
 614                bb->prev_bb->index, bb->next_bb->index);
 615       fprintf (file, "loop_depth %d, count ", bb->loop_depth);
 616       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
 617       fprintf (file, ", freq %i", bb->frequency);
 618       if (maybe_hot_bb_p (bb))
 619         fprintf (file, ", maybe hot");
 620       if (probably_never_executed_bb_p (bb))
 621         fprintf (file, ", probably never executed");
 622       fprintf (file, ".\n");
 623
 624       fprintf (file, "Predecessors: ");
 625       FOR_EACH_EDGE (e, ei, bb->preds)
 626         dump_edge_info (file, e, 0);
 627
 628       fprintf (file, "\nSuccessors: ");
 629       FOR_EACH_EDGE (e, ei, bb->succs)
 630         dump_edge_info (file, e, 1);
 631
 632       fprintf (file, "\nRegisters live at start:");
 633       dump_regset (bb->global_live_at_start, file);
 634
 635       fprintf (file, "\nRegisters live at end:");
 636       dump_regset (bb->global_live_at_end, file);
 637
 638       putc ('\n', file);
 639
 640       if (bb->global_live_at_start)
 641         {
 642           fprintf (file, "\nRegisters live at start:");
 643           dump_regset (bb->global_live_at_start, file);
 644         }
 645
 646       if (bb->global_live_at_end)
 647         {
 648           fprintf (file, "\nRegisters live at end:");
 649           dump_regset (bb->global_live_at_end, file);
 650         }
 651
 652       putc ('\n', file);
 653       check_bb_profile (bb, file);
 654     }
 655
 656   putc ('\n', file);
 657 }
 658
 659 void
 660 debug_flow_info (void)
 661 {
 662   dump_flow_info (stderr);
 663 }
 664
 665 void
 666 dump_edge_info (FILE *file, edge e, int do_succ)
 667 {
 668   basic_block side = (do_succ ? e->dest : e->src);
 669
 670   if (side == ENTRY_BLOCK_PTR)
 671     fputs (" ENTRY", file);
 672   else if (side == EXIT_BLOCK_PTR)
 673     fputs (" EXIT", file);
 674   else
 675     fprintf (file, " %d", side->index);
 676
 677   if (e->probability)
 678     fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
 679
 680   if (e->count)
 681     {
 682       fprintf (file, " count:");
 683       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
 684     }
 685
 686   if (e->flags)
 687     {
 688       static const char * const bitnames[] = {
 689         "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
 690         "can_fallthru", "irreducible", "sibcall", "loop_exit",
 691         "true", "false", "exec"
 692       };
 693       int comma = 0;
 694       int i, flags = e->flags;
 695
 696       fputs (" (", file);
 697       for (i = 0; flags; i++)
 698         if (flags & (1 << i))
 699           {
 700             flags &= ~(1 << i);
 701
 702             if (comma)
 703               fputc (',', file);
 704             if (i < (int) ARRAY_SIZE (bitnames))
 705               fputs (bitnames[i], file);
 706             else
 707               fprintf (file, "%d", i);
 708             comma = 1;
 709           }
 710
 711       fputc (')', file);
 712     }
 713 }
 714 \f
 715 /* Simple routines to easily allocate AUX fields of basic blocks.  */
 716
 717 static struct obstack block_aux_obstack;
 718 static void *first_block_aux_obj = 0;
 719 static struct obstack edge_aux_obstack;
 720 static void *first_edge_aux_obj = 0;
 721
 722 /* Allocate a memory block of SIZE as BB->aux.  The obstack must
 723    be first initialized by alloc_aux_for_blocks.  */
 724
 725 inline void
 726 alloc_aux_for_block (basic_block bb, int size)
 727 {
 728   /* Verify that aux field is clear.  */
 729   gcc_assert (!bb->aux && first_block_aux_obj);
 730   bb->aux = obstack_alloc (&block_aux_obstack, size);
 731   memset (bb->aux, 0, size);
 732 }
 733
 734 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
 735    alloc_aux_for_block for each basic block.  */
 736
 737 void
 738 alloc_aux_for_blocks (int size)
 739 {
 740   static int initialized;
 741
 742   if (!initialized)
 743     {
 744       gcc_obstack_init (&block_aux_obstack);
 745       initialized = 1;
 746     }
 747   else
 748     /* Check whether AUX data are still allocated.  */
 749     gcc_assert (!first_block_aux_obj);
 750
 751   first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
 752   if (size)
 753     {
 754       basic_block bb;
 755
 756       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 757         alloc_aux_for_block (bb, size);
 758     }
 759 }
 760
 761 /* Clear AUX pointers of all blocks.  */
 762
 763 void
 764 clear_aux_for_blocks (void)
 765 {
 766   basic_block bb;
 767
 768   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 769     bb->aux = NULL;
 770 }
 771
 772 /* Free data allocated in block_aux_obstack and clear AUX pointers
 773    of all blocks.  */
 774
 775 void
 776 free_aux_for_blocks (void)
 777 {
 778   gcc_assert (first_block_aux_obj);
 779   obstack_free (&block_aux_obstack, first_block_aux_obj);
 780   first_block_aux_obj = NULL;
 781
 782   clear_aux_for_blocks ();
 783 }
 784
 785 /* Allocate a memory edge of SIZE as BB->aux.  The obstack must
 786    be first initialized by alloc_aux_for_edges.  */
 787
 788 inline void
 789 alloc_aux_for_edge (edge e, int size)
 790 {
 791   /* Verify that aux field is clear.  */
 792   gcc_assert (!e->aux && first_edge_aux_obj);
 793   e->aux = obstack_alloc (&edge_aux_obstack, size);
 794   memset (e->aux, 0, size);
 795 }
 796
 797 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
 798    alloc_aux_for_edge for each basic edge.  */
 799
 800 void
 801 alloc_aux_for_edges (int size)
 802 {
 803   static int initialized;
 804
 805   if (!initialized)
 806     {
 807       gcc_obstack_init (&edge_aux_obstack);
 808       initialized = 1;
 809     }
 810   else
 811     /* Check whether AUX data are still allocated.  */
 812     gcc_assert (!first_edge_aux_obj);
 813
 814   first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
 815   if (size)
 816     {
 817       basic_block bb;
 818
 819       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 820         {
 821           edge e;
 822           edge_iterator ei;
 823
 824           FOR_EACH_EDGE (e, ei, bb->succs)
 825             alloc_aux_for_edge (e, size);
 826         }
 827     }
 828 }
 829
 830 /* Clear AUX pointers of all edges.  */
 831
 832 void
 833 clear_aux_for_edges (void)
 834 {
 835   basic_block bb;
 836   edge e;
 837
 838   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 839     {
 840       edge_iterator ei;
 841       FOR_EACH_EDGE (e, ei, bb->succs)
 842         e->aux = NULL;
 843     }
 844 }
 845
 846 /* Free data allocated in edge_aux_obstack and clear AUX pointers
 847    of all edges.  */
 848
 849 void
 850 free_aux_for_edges (void)
 851 {
 852   gcc_assert (first_edge_aux_obj);
 853   obstack_free (&edge_aux_obstack, first_edge_aux_obj);
 854   first_edge_aux_obj = NULL;
 855
 856   clear_aux_for_edges ();
 857 }
 858
 859 void
 860 debug_bb (basic_block bb)
 861 {
 862   dump_bb (bb, stderr, 0);
 863 }
 864
 865 basic_block
 866 debug_bb_n (int n)
 867 {
 868   basic_block bb = BASIC_BLOCK (n);
 869   dump_bb (bb, stderr, 0);
 870   return bb;
 871 }
 872
 873 /* Dumps cfg related information about basic block BB to FILE.  */
 874
 875 static void
 876 dump_cfg_bb_info (FILE *file, basic_block bb)
 877 {
 878   unsigned i;
 879   edge_iterator ei;
 880   bool first = true;
 881   static const char * const bb_bitnames[] =
 882     {
 883       "dirty", "new", "reachable", "visited", "irreducible_loop", "superblock"
 884     };
 885   const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
 886   edge e;
 887
 888   fprintf (file, "Basic block %d", bb->index);
 889   for (i = 0; i < n_bitnames; i++)
 890     if (bb->flags & (1 << i))
 891       {
 892         if (first)
 893           fprintf (file, " (");
 894         else
 895           fprintf (file, ", ");
 896         first = false;
 897         fprintf (file, bb_bitnames[i]);
 898       }
 899   if (!first)
 900     fprintf (file, ")");
 901   fprintf (file, "\n");
 902
 903   fprintf (file, "Predecessors: ");
 904   FOR_EACH_EDGE (e, ei, bb->preds)
 905     dump_edge_info (file, e, 0);
 906
 907   fprintf (file, "\nSuccessors: ");
 908   FOR_EACH_EDGE (e, ei, bb->succs)
 909     dump_edge_info (file, e, 1);
 910   fprintf (file, "\n\n");
 911 }
 912
 913 /* Dumps a brief description of cfg to FILE.  */
 914
 915 void
 916 brief_dump_cfg (FILE *file)
 917 {
 918   basic_block bb;
 919
 920   FOR_EACH_BB (bb)
 921     {
 922       dump_cfg_bb_info (file, bb);
 923     }
 924 }