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
 148   FOR_EACH_BB (bb)
 149     {
 150       FOR_EACH_EDGE (e, bb->succs)
 151         free_edge (e);
 152       END_FOR_EACH_EDGE;
 153       VEC_truncate (edge, bb->succs, 0);
 154       VEC_truncate (edge, bb->preds, 0);
 155     }
 156
 157   FOR_EACH_EDGE (e, ENTRY_BLOCK_PTR->succs)
 158     free_edge (e);
 159   END_FOR_EACH_EDGE;
 160   VEC_truncate (edge, EXIT_BLOCK_PTR->preds, 0);
 161   VEC_truncate (edge, ENTRY_BLOCK_PTR->succs, 0);
 162
 163   gcc_assert (!n_edges);
 164 }
 165 \f
 166 /* Allocate memory for basic_block.  */
 167
 168 basic_block
 169 alloc_block (void)
 170 {
 171   basic_block bb;
 172   bb = ggc_alloc_cleared (sizeof (*bb));
 173   return bb;
 174 }
 175
 176 /* Create memory pool for rbi_pool.  */
 177
 178 void
 179 alloc_rbi_pool (void)
 180 {
 181   rbi_pool = create_alloc_pool ("rbi pool",
 182                                 sizeof (struct reorder_block_def),
 183                                 n_basic_blocks + 2);
 184 }
 185
 186 /* Free rbi_pool.  */
 187
 188 void
 189 free_rbi_pool (void)
 190 {
 191   free_alloc_pool (rbi_pool);
 192 }
 193
 194 /* Initialize rbi (the structure containing data used by basic block
 195    duplication and reordering) for the given basic block.  */
 196
 197 void
 198 initialize_bb_rbi (basic_block bb)
 199 {
 200   gcc_assert (!bb->rbi);
 201   bb->rbi = pool_alloc (rbi_pool);
 202   memset (bb->rbi, 0, sizeof (struct reorder_block_def));
 203 }
 204
 205 /* Link block B to chain after AFTER.  */
 206 void
 207 link_block (basic_block b, basic_block after)
 208 {
 209   b->next_bb = after->next_bb;
 210   b->prev_bb = after;
 211   after->next_bb = b;
 212   b->next_bb->prev_bb = b;
 213 }
 214
 215 /* Unlink block B from chain.  */
 216 void
 217 unlink_block (basic_block b)
 218 {
 219   b->next_bb->prev_bb = b->prev_bb;
 220   b->prev_bb->next_bb = b->next_bb;
 221   b->prev_bb = NULL;
 222   b->next_bb = NULL;
 223 }
 224
 225 /* Sequentially order blocks and compact the arrays.  */
 226 void
 227 compact_blocks (void)
 228 {
 229   int i;
 230   basic_block bb;
 231
 232   i = 0;
 233   FOR_EACH_BB (bb)
 234     {
 235       BASIC_BLOCK (i) = bb;
 236       bb->index = i;
 237       i++;
 238     }
 239
 240   gcc_assert (i == n_basic_blocks);
 241
 242   for (; i < last_basic_block; i++)
 243     BASIC_BLOCK (i) = NULL;
 244
 245   last_basic_block = n_basic_blocks;
 246 }
 247
 248 /* Remove block B from the basic block array.  */
 249
 250 void
 251 expunge_block (basic_block b)
 252 {
 253   unlink_block (b);
 254   BASIC_BLOCK (b->index) = NULL;
 255   n_basic_blocks--;
 256   ggc_free (b);
 257 }
 258 \f
 259 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
 260    created edge.  Use this only if you are sure that this edge can't
 261    possibly already exist.  */
 262
 263 edge
 264 unchecked_make_edge (basic_block src, basic_block dst, int flags)
 265 {
 266   edge e;
 267   e = ggc_alloc_cleared (sizeof (*e));
 268   n_edges++;
 269
 270   VEC_safe_push (edge, src->succs, e);
 271   VEC_safe_push (edge, dst->preds, e);
 272
 273   e->src = src;
 274   e->dest = dst;
 275   e->flags = flags;
 276
 277   return e;
 278 }
 279
 280 /* Create an edge connecting SRC and DST with FLAGS optionally using
 281    edge cache CACHE.  Return the new edge, NULL if already exist.  */
 282
 283 edge
 284 cached_make_edge (sbitmap *edge_cache, basic_block src, basic_block dst, int flags)
 285 {
 286   int use_edge_cache;
 287   edge e;
 288
 289   /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that
 290      many edges to them, or we didn't allocate memory for it.  */
 291   use_edge_cache = (edge_cache
 292                     && src != ENTRY_BLOCK_PTR && dst != EXIT_BLOCK_PTR);
 293
 294   /* Make sure we don't add duplicate edges.  */
 295   switch (use_edge_cache)
 296     {
 297     default:
 298       /* Quick test for non-existence of the edge.  */
 299       if (! TEST_BIT (edge_cache[src->index], dst->index))
 300         break;
 301
 302       /* The edge exists; early exit if no work to do.  */
 303       if (flags == 0)
 304         return NULL;
 305
 306       /* Fall through.  */
 307     case 0:
 308       FOR_EACH_EDGE (e, src->succs)
 309         {
 310           if (e->dest == dst)
 311             {
 312               e->flags |= flags;
 313               return NULL;
 314             }
 315         }
 316       END_FOR_EACH_EDGE;
 317       break;
 318     }
 319
 320   e = unchecked_make_edge (src, dst, flags);
 321
 322   if (use_edge_cache)
 323     SET_BIT (edge_cache[src->index], dst->index);
 324
 325   return e;
 326 }
 327
 328 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
 329    created edge or NULL if already exist.  */
 330
 331 edge
 332 make_edge (basic_block src, basic_block dest, int flags)
 333 {
 334   return cached_make_edge (NULL, src, dest, flags);
 335 }
 336
 337 /* Create an edge connecting SRC to DEST and set probability by knowing
 338    that it is the single edge leaving SRC.  */
 339
 340 edge
 341 make_single_succ_edge (basic_block src, basic_block dest, int flags)
 342 {
 343   edge e = make_edge (src, dest, flags);
 344
 345   e->probability = REG_BR_PROB_BASE;
 346   e->count = src->count;
 347   return e;
 348 }
 349
 350 /* This function will remove an edge from the flow graph.  */
 351
 352 void
 353 remove_edge (edge e)
 354 {
 355   edge tmp;
 356   basic_block src, dest;
 357   bool found = false;
 358   unsigned ix;
 359
 360   src = e->src;
 361   dest = e->dest;
 362
 363   for (ix = 0; VEC_iterate (edge, src->succs, ix, tmp); )
 364     {
 365       if (tmp == e)
 366         {
 367           VEC_unordered_remove (edge, src->succs, ix);
 368           found = true;
 369           break;
 370         }
 371       else
 372         ix++;
 373     }
 374
 375   gcc_assert (found);
 376
 377   if (!found)
 378     abort ();
 379
 380   found = false;
 381   for (ix = 0; VEC_iterate (edge, dest->preds, ix, tmp); )
 382     {
 383       if (tmp == e)
 384         {
 385           VEC_unordered_remove (edge, dest->preds, ix);
 386           found = true;
 387           break;
 388         }
 389       else
 390         ix++;
 391     }
 392
 393   gcc_assert (found);
 394
 395   free_edge (e);
 396 }
 397
 398 /* Redirect an edge's successor from one block to another.  */
 399
 400 void
 401 redirect_edge_succ (edge e, basic_block new_succ)
 402 {
 403   edge tmp;
 404   unsigned ix;
 405   bool found = false;
 406
 407   /* Disconnect the edge from the old successor block.  */
 408   for (ix = 0; VEC_iterate (edge, e->dest->preds, ix, tmp); )
 409     {
 410       if (tmp == e)
 411         {
 412           VEC_unordered_remove (edge, e->dest->preds, ix);
 413           found = true;
 414           break;
 415         }
 416       else
 417         ix++;
 418     }
 419
 420   if (!found)
 421     abort ();
 422
 423   /* Reconnect the edge to the new successor block.  */
 424   VEC_safe_push (edge, new_succ->preds, e);
 425   e->dest = new_succ;
 426 }
 427
 428 /* Like previous but avoid possible duplicate edge.  */
 429
 430 edge
 431 redirect_edge_succ_nodup (edge e, basic_block new_succ)
 432 {
 433   edge s;
 434
 435   /* Check whether the edge is already present.  */
 436   FOR_EACH_EDGE (s, e->src->succs)
 437     {
 438       if (s->dest == new_succ && s != e)
 439         break;
 440     }
 441   END_FOR_EACH_EDGE;
 442
 443   if (s)
 444     {
 445       s->flags |= e->flags;
 446       s->probability += e->probability;
 447       if (s->probability > REG_BR_PROB_BASE)
 448         s->probability = REG_BR_PROB_BASE;
 449       s->count += e->count;
 450       remove_edge (e);
 451       e = s;
 452     }
 453   else
 454     redirect_edge_succ (e, new_succ);
 455
 456   return e;
 457 }
 458
 459 /* Redirect an edge's predecessor from one block to another.  */
 460
 461 void
 462 redirect_edge_pred (edge e, basic_block new_pred)
 463 {
 464   edge tmp;
 465   bool found = false;
 466   unsigned ix;
 467
 468   /* Disconnect the edge from the old predecessor block.  */
 469   for (ix = 0; VEC_iterate (edge, e->src->succs, ix, tmp); )
 470     {
 471       if (tmp == e)
 472         {
 473           VEC_unordered_remove (edge, e->src->succs, ix);
 474           found = true;
 475           break;
 476         }
 477       else
 478         ix++;
 479     }
 480
 481   if (!found)
 482     abort ();
 483
 484   /* Reconnect the edge to the new predecessor block.  */
 485   VEC_safe_push (edge, new_pred->succs, e);
 486   e->src = new_pred;
 487 }
 488
 489 /* Clear all basic block flags, with the exception of partitioning.  */
 490 void
 491 clear_bb_flags (void)
 492 {
 493   basic_block bb;
 494
 495   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 496     bb->flags = BB_PARTITION (bb);
 497 }
 498 \f
 499 /* Check the consistency of profile information.  We can't do that
 500    in verify_flow_info, as the counts may get invalid for incompletely
 501    solved graphs, later eliminating of conditionals or roundoff errors.
 502    It is still practical to have them reported for debugging of simple
 503    testcases.  */
 504 void
 505 check_bb_profile (basic_block bb, FILE * file)
 506 {
 507   edge e;
 508   int sum = 0;
 509   gcov_type lsum;
 510
 511   if (profile_status == PROFILE_ABSENT)
 512     return;
 513
 514   if (bb != EXIT_BLOCK_PTR)
 515     {
 516       FOR_EACH_EDGE (e, bb->succs)
 517         sum += e->probability;
 518       END_FOR_EACH_EDGE;
 519       if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
 520         fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
 521                  sum * 100.0 / REG_BR_PROB_BASE);
 522       lsum = 0;
 523       FOR_EACH_EDGE (e, bb->succs)
 524         lsum += e->count;
 525       END_FOR_EACH_EDGE;
 526       if (EDGE_COUNT (bb->succs)
 527           && (lsum - bb->count > 100 || lsum - bb->count < -100))
 528         fprintf (file, "Invalid sum of outgoing counts %i, should be %i\n",
 529                  (int) lsum, (int) bb->count);
 530     }
 531   if (bb != ENTRY_BLOCK_PTR)
 532     {
 533       sum = 0;
 534       FOR_EACH_EDGE (e, bb->preds)
 535         sum += EDGE_FREQUENCY (e);
 536       END_FOR_EACH_EDGE;
 537       if (abs (sum - bb->frequency) > 100)
 538         fprintf (file,
 539                  "Invalid sum of incoming frequencies %i, should be %i\n",
 540                  sum, bb->frequency);
 541       lsum = 0;
 542       FOR_EACH_EDGE (e, bb->preds)
 543         lsum += e->count;
 544       END_FOR_EACH_EDGE;
 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
 611       fprintf (file, "\nBasic block %d ", bb->index);
 612       fprintf (file, "prev %d, next %d, ",
 613                bb->prev_bb->index, bb->next_bb->index);
 614       fprintf (file, "loop_depth %d, count ", bb->loop_depth);
 615       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
 616       fprintf (file, ", freq %i", bb->frequency);
 617       if (maybe_hot_bb_p (bb))
 618         fprintf (file, ", maybe hot");
 619       if (probably_never_executed_bb_p (bb))
 620         fprintf (file, ", probably never executed");
 621       fprintf (file, ".\n");
 622
 623       fprintf (file, "Predecessors: ");
 624       FOR_EACH_EDGE (e, bb->preds)
 625         dump_edge_info (file, e, 0);
 626       END_FOR_EACH_EDGE;
 627
 628       fprintf (file, "\nSuccessors: ");
 629       FOR_EACH_EDGE (e, bb->succs)
 630         dump_edge_info (file, e, 1);
 631       END_FOR_EACH_EDGE;
 632
 633       fprintf (file, "\nRegisters live at start:");
 634       dump_regset (bb->global_live_at_start, file);
 635
 636       fprintf (file, "\nRegisters live at end:");
 637       dump_regset (bb->global_live_at_end, file);
 638
 639       putc ('\n', file);
 640
 641       if (bb->global_live_at_start)
 642         {
 643           fprintf (file, "\nRegisters live at start:");
 644           dump_regset (bb->global_live_at_start, file);
 645         }
 646
 647       if (bb->global_live_at_end)
 648         {
 649           fprintf (file, "\nRegisters live at end:");
 650           dump_regset (bb->global_live_at_end, file);
 651         }
 652
 653       putc ('\n', file);
 654       check_bb_profile (bb, file);
 655     }
 656
 657   putc ('\n', file);
 658 }
 659
 660 void
 661 debug_flow_info (void)
 662 {
 663   dump_flow_info (stderr);
 664 }
 665
 666 void
 667 dump_edge_info (FILE *file, edge e, int do_succ)
 668 {
 669   basic_block side = (do_succ ? e->dest : e->src);
 670
 671   if (side == ENTRY_BLOCK_PTR)
 672     fputs (" ENTRY", file);
 673   else if (side == EXIT_BLOCK_PTR)
 674     fputs (" EXIT", file);
 675   else
 676     fprintf (file, " %d", side->index);
 677
 678   if (e->probability)
 679     fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
 680
 681   if (e->count)
 682     {
 683       fprintf (file, " count:");
 684       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
 685     }
 686
 687   if (e->flags)
 688     {
 689       static const char * const bitnames[] = {
 690         "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
 691         "can_fallthru", "irreducible", "sibcall", "loop_exit",
 692         "true", "false", "exec"
 693       };
 694       int comma = 0;
 695       int i, flags = e->flags;
 696
 697       fputs (" (", file);
 698       for (i = 0; flags; i++)
 699         if (flags & (1 << i))
 700           {
 701             flags &= ~(1 << i);
 702
 703             if (comma)
 704               fputc (',', file);
 705             if (i < (int) ARRAY_SIZE (bitnames))
 706               fputs (bitnames[i], file);
 707             else
 708               fprintf (file, "%d", i);
 709             comma = 1;
 710           }
 711
 712       fputc (')', file);
 713     }
 714 }
 715 \f
 716 /* Simple routines to easily allocate AUX fields of basic blocks.  */
 717
 718 static struct obstack block_aux_obstack;
 719 static void *first_block_aux_obj = 0;
 720 static struct obstack edge_aux_obstack;
 721 static void *first_edge_aux_obj = 0;
 722
 723 /* Allocate a memory block of SIZE as BB->aux.  The obstack must
 724    be first initialized by alloc_aux_for_blocks.  */
 725
 726 inline void
 727 alloc_aux_for_block (basic_block bb, int size)
 728 {
 729   /* Verify that aux field is clear.  */
 730   gcc_assert (!bb->aux && first_block_aux_obj);
 731   bb->aux = obstack_alloc (&block_aux_obstack, size);
 732   memset (bb->aux, 0, size);
 733 }
 734
 735 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
 736    alloc_aux_for_block for each basic block.  */
 737
 738 void
 739 alloc_aux_for_blocks (int size)
 740 {
 741   static int initialized;
 742
 743   if (!initialized)
 744     {
 745       gcc_obstack_init (&block_aux_obstack);
 746       initialized = 1;
 747     }
 748   else
 749     /* Check whether AUX data are still allocated.  */
 750     gcc_assert (!first_block_aux_obj);
 751
 752   first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
 753   if (size)
 754     {
 755       basic_block bb;
 756
 757       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 758         alloc_aux_for_block (bb, size);
 759     }
 760 }
 761
 762 /* Clear AUX pointers of all blocks.  */
 763
 764 void
 765 clear_aux_for_blocks (void)
 766 {
 767   basic_block bb;
 768
 769   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 770     bb->aux = NULL;
 771 }
 772
 773 /* Free data allocated in block_aux_obstack and clear AUX pointers
 774    of all blocks.  */
 775
 776 void
 777 free_aux_for_blocks (void)
 778 {
 779   gcc_assert (first_block_aux_obj);
 780   obstack_free (&block_aux_obstack, first_block_aux_obj);
 781   first_block_aux_obj = NULL;
 782
 783   clear_aux_for_blocks ();
 784 }
 785
 786 /* Allocate a memory edge of SIZE as BB->aux.  The obstack must
 787    be first initialized by alloc_aux_for_edges.  */
 788
 789 inline void
 790 alloc_aux_for_edge (edge e, int size)
 791 {
 792   /* Verify that aux field is clear.  */
 793   gcc_assert (!e->aux && first_edge_aux_obj);
 794   e->aux = obstack_alloc (&edge_aux_obstack, size);
 795   memset (e->aux, 0, size);
 796 }
 797
 798 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
 799    alloc_aux_for_edge for each basic edge.  */
 800
 801 void
 802 alloc_aux_for_edges (int size)
 803 {
 804   static int initialized;
 805
 806   if (!initialized)
 807     {
 808       gcc_obstack_init (&edge_aux_obstack);
 809       initialized = 1;
 810     }
 811   else
 812     /* Check whether AUX data are still allocated.  */
 813     gcc_assert (!first_edge_aux_obj);
 814
 815   first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
 816   if (size)
 817     {
 818       basic_block bb;
 819
 820       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 821         {
 822           edge e;
 823
 824           FOR_EACH_EDGE (e, bb->succs)
 825             alloc_aux_for_edge (e, size);
 826           END_FOR_EACH_EDGE;
 827         }
 828     }
 829 }
 830
 831 /* Clear AUX pointers of all edges.  */
 832
 833 void
 834 clear_aux_for_edges (void)
 835 {
 836   basic_block bb;
 837   edge e;
 838
 839   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 840     {
 841       FOR_EACH_EDGE (e, bb->succs)
 842         e->aux = NULL;
 843       END_FOR_EACH_EDGE;
 844     }
 845 }
 846
 847 /* Free data allocated in edge_aux_obstack and clear AUX pointers
 848    of all edges.  */
 849
 850 void
 851 free_aux_for_edges (void)
 852 {
 853   gcc_assert (first_edge_aux_obj);
 854   obstack_free (&edge_aux_obstack, first_edge_aux_obj);
 855   first_edge_aux_obj = NULL;
 856
 857   clear_aux_for_edges ();
 858 }
 859
 860 void
 861 debug_bb (basic_block bb)
 862 {
 863   dump_bb (bb, stderr, 0);
 864 }
 865
 866 basic_block
 867 debug_bb_n (int n)
 868 {
 869   basic_block bb = BASIC_BLOCK (n);
 870   dump_bb (bb, stderr, 0);
 871   return bb;
 872 }
 873
 874 /* Dumps cfg related information about basic block BB to FILE.  */
 875
 876 static void
 877 dump_cfg_bb_info (FILE *file, basic_block bb)
 878 {
 879   unsigned i;
 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, bb->preds)
 905     dump_edge_info (file, e, 0);
 906   END_FOR_EACH_EDGE;
 907
 908   fprintf (file, "\nSuccessors: ");
 909   FOR_EACH_EDGE (e, bb->succs)
 910     dump_edge_info (file, e, 1);
 911   END_FOR_EACH_EDGE;
 912   fprintf (file, "\n\n");
 913 }
 914
 915 /* Dumps a brief description of cfg to FILE.  */
 916
 917 void
 918 brief_dump_cfg (FILE *file)
 919 {
 920   basic_block bb;
 921
 922   FOR_EACH_BB (bb)
 923     {
 924       dump_cfg_bb_info (file, bb);
 925     }
 926 }