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