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