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