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   return e;
 281 }
 282
 283 /* Create an edge connecting SRC and DST with FLAGS optionally using
 284    edge cache CACHE.  Return the new edge, NULL if already exist.  */
 285
 286 edge
 287 cached_make_edge (sbitmap *edge_cache, basic_block src, basic_block dst, int flags)
 288 {
 289   int use_edge_cache;
 290   edge e;
 291   edge_iterator ei;
 292
 293   /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that
 294      many edges to them, or we didn't allocate memory for it.  */
 295   use_edge_cache = (edge_cache
 296                     && src != ENTRY_BLOCK_PTR && dst != EXIT_BLOCK_PTR);
 297
 298   /* Make sure we don't add duplicate edges.  */
 299   switch (use_edge_cache)
 300     {
 301     default:
 302       /* Quick test for non-existence of the edge.  */
 303       if (! TEST_BIT (edge_cache[src->index], dst->index))
 304         break;
 305
 306       /* The edge exists; early exit if no work to do.  */
 307       if (flags == 0)
 308         return NULL;
 309
 310       /* Fall through.  */
 311     case 0:
 312       FOR_EACH_EDGE (e, ei, src->succs)
 313         if (e->dest == dst)
 314           {
 315             e->flags |= flags;
 316             return NULL;
 317           }
 318       break;
 319     }
 320
 321   e = unchecked_make_edge (src, dst, flags);
 322
 323   if (use_edge_cache)
 324     SET_BIT (edge_cache[src->index], dst->index);
 325
 326   return e;
 327 }
 328
 329 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
 330    created edge or NULL if already exist.  */
 331
 332 edge
 333 make_edge (basic_block src, basic_block dest, int flags)
 334 {
 335   return cached_make_edge (NULL, src, dest, flags);
 336 }
 337
 338 /* Create an edge connecting SRC to DEST and set probability by knowing
 339    that it is the single edge leaving SRC.  */
 340
 341 edge
 342 make_single_succ_edge (basic_block src, basic_block dest, int flags)
 343 {
 344   edge e = make_edge (src, dest, flags);
 345
 346   e->probability = REG_BR_PROB_BASE;
 347   e->count = src->count;
 348   return e;
 349 }
 350
 351 /* This function will remove an edge from the flow graph.  */
 352
 353 void
 354 remove_edge (edge e)
 355 {
 356   edge tmp;
 357   basic_block src, dest;
 358   unsigned int dest_idx;
 359   bool found = false;
 360   edge_iterator ei;
 361
 362   src = e->src;
 363   dest = e->dest;
 364   dest_idx = e->dest_idx;
 365
 366   for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); )
 367     {
 368       if (tmp == e)
 369         {
 370           VEC_unordered_remove (edge, src->succs, ei.index);
 371           found = true;
 372           break;
 373         }
 374       else
 375         ei_next (&ei);
 376     }
 377
 378   gcc_assert (found);
 379
 380   VEC_unordered_remove (edge, dest->preds, dest_idx);
 381
 382   /* If we removed an edge in the middle of the edge vector, we need
 383      to update dest_idx of the edge that moved into the "hole".  */
 384   if (dest_idx < EDGE_COUNT (dest->preds))
 385     EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
 386
 387   free_edge (e);
 388 }
 389
 390 /* Redirect an edge's successor from one block to another.  */
 391
 392 void
 393 redirect_edge_succ (edge e, basic_block new_succ)
 394 {
 395   basic_block dest = e->dest;
 396   unsigned int dest_idx = e->dest_idx;
 397
 398   VEC_unordered_remove (edge, dest->preds, dest_idx);
 399
 400   /* If we removed an edge in the middle of the edge vector, we need
 401      to update dest_idx of the edge that moved into the "hole".  */
 402   if (dest_idx < EDGE_COUNT (dest->preds))
 403     EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
 404
 405   /* Reconnect the edge to the new successor block.  */
 406   VEC_safe_push (edge, new_succ->preds, e);
 407   e->dest = new_succ;
 408   e->dest_idx = EDGE_COUNT (new_succ->preds) - 1;
 409 }
 410
 411 /* Like previous but avoid possible duplicate edge.  */
 412
 413 edge
 414 redirect_edge_succ_nodup (edge e, basic_block new_succ)
 415 {
 416   edge s;
 417
 418   s = find_edge (e->src, new_succ);
 419   if (s && s != e)
 420     {
 421       s->flags |= e->flags;
 422       s->probability += e->probability;
 423       if (s->probability > REG_BR_PROB_BASE)
 424         s->probability = REG_BR_PROB_BASE;
 425       s->count += e->count;
 426       remove_edge (e);
 427       e = s;
 428     }
 429   else
 430     redirect_edge_succ (e, new_succ);
 431
 432   return e;
 433 }
 434
 435 /* Redirect an edge's predecessor from one block to another.  */
 436
 437 void
 438 redirect_edge_pred (edge e, basic_block new_pred)
 439 {
 440   edge tmp;
 441   edge_iterator ei;
 442   bool found = false;
 443
 444   /* Disconnect the edge from the old predecessor block.  */
 445   for (ei = ei_start (e->src->succs); (tmp = ei_safe_edge (ei)); )
 446     {
 447       if (tmp == e)
 448         {
 449           VEC_unordered_remove (edge, e->src->succs, ei.index);
 450           found = true;
 451           break;
 452         }
 453       else
 454         ei_next (&ei);
 455     }
 456
 457   gcc_assert (found);
 458
 459   /* Reconnect the edge to the new predecessor block.  */
 460   VEC_safe_push (edge, new_pred->succs, e);
 461   e->src = new_pred;
 462 }
 463
 464 /* Clear all basic block flags, with the exception of partitioning.  */
 465 void
 466 clear_bb_flags (void)
 467 {
 468   basic_block bb;
 469
 470   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 471     bb->flags = BB_PARTITION (bb);
 472 }
 473 \f
 474 /* Check the consistency of profile information.  We can't do that
 475    in verify_flow_info, as the counts may get invalid for incompletely
 476    solved graphs, later eliminating of conditionals or roundoff errors.
 477    It is still practical to have them reported for debugging of simple
 478    testcases.  */
 479 void
 480 check_bb_profile (basic_block bb, FILE * file)
 481 {
 482   edge e;
 483   int sum = 0;
 484   gcov_type lsum;
 485   edge_iterator ei;
 486
 487   if (profile_status == PROFILE_ABSENT)
 488     return;
 489
 490   if (bb != EXIT_BLOCK_PTR)
 491     {
 492       FOR_EACH_EDGE (e, ei, bb->succs)
 493         sum += e->probability;
 494       if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
 495         fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
 496                  sum * 100.0 / REG_BR_PROB_BASE);
 497       lsum = 0;
 498       FOR_EACH_EDGE (e, ei, bb->succs)
 499         lsum += e->count;
 500       if (EDGE_COUNT (bb->succs)
 501           && (lsum - bb->count > 100 || lsum - bb->count < -100))
 502         fprintf (file, "Invalid sum of outgoing counts %i, should be %i\n",
 503                  (int) lsum, (int) bb->count);
 504     }
 505   if (bb != ENTRY_BLOCK_PTR)
 506     {
 507       sum = 0;
 508       FOR_EACH_EDGE (e, ei, bb->preds)
 509         sum += EDGE_FREQUENCY (e);
 510       if (abs (sum - bb->frequency) > 100)
 511         fprintf (file,
 512                  "Invalid sum of incoming frequencies %i, should be %i\n",
 513                  sum, bb->frequency);
 514       lsum = 0;
 515       FOR_EACH_EDGE (e, ei, bb->preds)
 516         lsum += e->count;
 517       if (lsum - bb->count > 100 || lsum - bb->count < -100)
 518         fprintf (file, "Invalid sum of incoming counts %i, should be %i\n",
 519                  (int) lsum, (int) bb->count);
 520     }
 521 }
 522 \f
 523 void
 524 dump_flow_info (FILE *file)
 525 {
 526   int i;
 527   basic_block bb;
 528   static const char * const reg_class_names[] = REG_CLASS_NAMES;
 529
 530   if (reg_n_info)
 531     {
 532       int max_regno = max_reg_num ();
 533       fprintf (file, "%d registers.\n", max_regno);
 534       for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
 535         if (REG_N_REFS (i))
 536           {
 537             enum reg_class class, altclass;
 538
 539             fprintf (file, "\nRegister %d used %d times across %d insns",
 540                      i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
 541             if (REG_BASIC_BLOCK (i) >= 0)
 542               fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
 543             if (REG_N_SETS (i))
 544               fprintf (file, "; set %d time%s", REG_N_SETS (i),
 545                        (REG_N_SETS (i) == 1) ? "" : "s");
 546             if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
 547               fprintf (file, "; user var");
 548             if (REG_N_DEATHS (i) != 1)
 549               fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
 550             if (REG_N_CALLS_CROSSED (i) == 1)
 551               fprintf (file, "; crosses 1 call");
 552             else if (REG_N_CALLS_CROSSED (i))
 553               fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
 554             if (regno_reg_rtx[i] != NULL
 555                 && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
 556               fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
 557
 558             class = reg_preferred_class (i);
 559             altclass = reg_alternate_class (i);
 560             if (class != GENERAL_REGS || altclass != ALL_REGS)
 561               {
 562                 if (altclass == ALL_REGS || class == ALL_REGS)
 563                   fprintf (file, "; pref %s", reg_class_names[(int) class]);
 564                 else if (altclass == NO_REGS)
 565                   fprintf (file, "; %s or none", reg_class_names[(int) class]);
 566                 else
 567                   fprintf (file, "; pref %s, else %s",
 568                            reg_class_names[(int) class],
 569                            reg_class_names[(int) altclass]);
 570               }
 571
 572             if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
 573               fprintf (file, "; pointer");
 574             fprintf (file, ".\n");
 575           }
 576     }
 577
 578   fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
 579   FOR_EACH_BB (bb)
 580     {
 581       edge e;
 582       edge_iterator ei;
 583
 584       fprintf (file, "\nBasic block %d ", bb->index);
 585       fprintf (file, "prev %d, next %d, ",
 586                bb->prev_bb->index, bb->next_bb->index);
 587       fprintf (file, "loop_depth %d, count ", bb->loop_depth);
 588       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
 589       fprintf (file, ", freq %i", bb->frequency);
 590       if (maybe_hot_bb_p (bb))
 591         fprintf (file, ", maybe hot");
 592       if (probably_never_executed_bb_p (bb))
 593         fprintf (file, ", probably never executed");
 594       fprintf (file, ".\n");
 595
 596       fprintf (file, "Predecessors: ");
 597       FOR_EACH_EDGE (e, ei, bb->preds)
 598         dump_edge_info (file, e, 0);
 599
 600       fprintf (file, "\nSuccessors: ");
 601       FOR_EACH_EDGE (e, ei, bb->succs)
 602         dump_edge_info (file, e, 1);
 603
 604       if (bb->global_live_at_start)
 605         {
 606           fprintf (file, "\nRegisters live at start:");
 607           dump_regset (bb->global_live_at_start, file);
 608         }
 609
 610       if (bb->global_live_at_end)
 611         {
 612           fprintf (file, "\nRegisters live at end:");
 613           dump_regset (bb->global_live_at_end, file);
 614         }
 615
 616       putc ('\n', file);
 617       check_bb_profile (bb, file);
 618     }
 619
 620   putc ('\n', file);
 621 }
 622
 623 void
 624 debug_flow_info (void)
 625 {
 626   dump_flow_info (stderr);
 627 }
 628
 629 void
 630 dump_edge_info (FILE *file, edge e, int do_succ)
 631 {
 632   basic_block side = (do_succ ? e->dest : e->src);
 633
 634   if (side == ENTRY_BLOCK_PTR)
 635     fputs (" ENTRY", file);
 636   else if (side == EXIT_BLOCK_PTR)
 637     fputs (" EXIT", file);
 638   else
 639     fprintf (file, " %d", side->index);
 640
 641   if (e->probability)
 642     fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
 643
 644   if (e->count)
 645     {
 646       fprintf (file, " count:");
 647       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
 648     }
 649
 650   if (e->flags)
 651     {
 652       static const char * const bitnames[] = {
 653         "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
 654         "can_fallthru", "irreducible", "sibcall", "loop_exit",
 655         "true", "false", "exec"
 656       };
 657       int comma = 0;
 658       int i, flags = e->flags;
 659
 660       fputs (" (", file);
 661       for (i = 0; flags; i++)
 662         if (flags & (1 << i))
 663           {
 664             flags &= ~(1 << i);
 665
 666             if (comma)
 667               fputc (',', file);
 668             if (i < (int) ARRAY_SIZE (bitnames))
 669               fputs (bitnames[i], file);
 670             else
 671               fprintf (file, "%d", i);
 672             comma = 1;
 673           }
 674
 675       fputc (')', file);
 676     }
 677 }
 678 \f
 679 /* Simple routines to easily allocate AUX fields of basic blocks.  */
 680
 681 static struct obstack block_aux_obstack;
 682 static void *first_block_aux_obj = 0;
 683 static struct obstack edge_aux_obstack;
 684 static void *first_edge_aux_obj = 0;
 685
 686 /* Allocate a memory block of SIZE as BB->aux.  The obstack must
 687    be first initialized by alloc_aux_for_blocks.  */
 688
 689 inline void
 690 alloc_aux_for_block (basic_block bb, int size)
 691 {
 692   /* Verify that aux field is clear.  */
 693   gcc_assert (!bb->aux && first_block_aux_obj);
 694   bb->aux = obstack_alloc (&block_aux_obstack, size);
 695   memset (bb->aux, 0, size);
 696 }
 697
 698 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
 699    alloc_aux_for_block for each basic block.  */
 700
 701 void
 702 alloc_aux_for_blocks (int size)
 703 {
 704   static int initialized;
 705
 706   if (!initialized)
 707     {
 708       gcc_obstack_init (&block_aux_obstack);
 709       initialized = 1;
 710     }
 711   else
 712     /* Check whether AUX data are still allocated.  */
 713     gcc_assert (!first_block_aux_obj);
 714
 715   first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
 716   if (size)
 717     {
 718       basic_block bb;
 719
 720       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 721         alloc_aux_for_block (bb, size);
 722     }
 723 }
 724
 725 /* Clear AUX pointers of all blocks.  */
 726
 727 void
 728 clear_aux_for_blocks (void)
 729 {
 730   basic_block bb;
 731
 732   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 733     bb->aux = NULL;
 734 }
 735
 736 /* Free data allocated in block_aux_obstack and clear AUX pointers
 737    of all blocks.  */
 738
 739 void
 740 free_aux_for_blocks (void)
 741 {
 742   gcc_assert (first_block_aux_obj);
 743   obstack_free (&block_aux_obstack, first_block_aux_obj);
 744   first_block_aux_obj = NULL;
 745
 746   clear_aux_for_blocks ();
 747 }
 748
 749 /* Allocate a memory edge of SIZE as BB->aux.  The obstack must
 750    be first initialized by alloc_aux_for_edges.  */
 751
 752 inline void
 753 alloc_aux_for_edge (edge e, int size)
 754 {
 755   /* Verify that aux field is clear.  */
 756   gcc_assert (!e->aux && first_edge_aux_obj);
 757   e->aux = obstack_alloc (&edge_aux_obstack, size);
 758   memset (e->aux, 0, size);
 759 }
 760
 761 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
 762    alloc_aux_for_edge for each basic edge.  */
 763
 764 void
 765 alloc_aux_for_edges (int size)
 766 {
 767   static int initialized;
 768
 769   if (!initialized)
 770     {
 771       gcc_obstack_init (&edge_aux_obstack);
 772       initialized = 1;
 773     }
 774   else
 775     /* Check whether AUX data are still allocated.  */
 776     gcc_assert (!first_edge_aux_obj);
 777
 778   first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
 779   if (size)
 780     {
 781       basic_block bb;
 782
 783       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 784         {
 785           edge e;
 786           edge_iterator ei;
 787
 788           FOR_EACH_EDGE (e, ei, bb->succs)
 789             alloc_aux_for_edge (e, size);
 790         }
 791     }
 792 }
 793
 794 /* Clear AUX pointers of all edges.  */
 795
 796 void
 797 clear_aux_for_edges (void)
 798 {
 799   basic_block bb;
 800   edge e;
 801
 802   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 803     {
 804       edge_iterator ei;
 805       FOR_EACH_EDGE (e, ei, bb->succs)
 806         e->aux = NULL;
 807     }
 808 }
 809
 810 /* Free data allocated in edge_aux_obstack and clear AUX pointers
 811    of all edges.  */
 812
 813 void
 814 free_aux_for_edges (void)
 815 {
 816   gcc_assert (first_edge_aux_obj);
 817   obstack_free (&edge_aux_obstack, first_edge_aux_obj);
 818   first_edge_aux_obj = NULL;
 819
 820   clear_aux_for_edges ();
 821 }
 822
 823 void
 824 debug_bb (basic_block bb)
 825 {
 826   dump_bb (bb, stderr, 0);
 827 }
 828
 829 basic_block
 830 debug_bb_n (int n)
 831 {
 832   basic_block bb = BASIC_BLOCK (n);
 833   dump_bb (bb, stderr, 0);
 834   return bb;
 835 }
 836
 837 /* Dumps cfg related information about basic block BB to FILE.  */
 838
 839 static void
 840 dump_cfg_bb_info (FILE *file, basic_block bb)
 841 {
 842   unsigned i;
 843   edge_iterator ei;
 844   bool first = true;
 845   static const char * const bb_bitnames[] =
 846     {
 847       "dirty", "new", "reachable", "visited", "irreducible_loop", "superblock"
 848     };
 849   const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
 850   edge e;
 851
 852   fprintf (file, "Basic block %d", bb->index);
 853   for (i = 0; i < n_bitnames; i++)
 854     if (bb->flags & (1 << i))
 855       {
 856         if (first)
 857           fprintf (file, " (");
 858         else
 859           fprintf (file, ", ");
 860         first = false;
 861         fprintf (file, bb_bitnames[i]);
 862       }
 863   if (!first)
 864     fprintf (file, ")");
 865   fprintf (file, "\n");
 866
 867   fprintf (file, "Predecessors: ");
 868   FOR_EACH_EDGE (e, ei, bb->preds)
 869     dump_edge_info (file, e, 0);
 870
 871   fprintf (file, "\nSuccessors: ");
 872   FOR_EACH_EDGE (e, ei, bb->succs)
 873     dump_edge_info (file, e, 1);
 874   fprintf (file, "\n\n");
 875 }
 876
 877 /* Dumps a brief description of cfg to FILE.  */
 878
 879 void
 880 brief_dump_cfg (FILE *file)
 881 {
 882   basic_block bb;
 883
 884   FOR_EACH_BB (bb)
 885     {
 886       dump_cfg_bb_info (file, bb);
 887     }
 888 }
 889
 890 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
 891    leave the block by TAKEN_EDGE.  Update profile of BB such that edge E can be
 892    redirected to destination of TAKEN_EDGE.
 893
 894    This function may leave the profile inconsistent in the case TAKEN_EDGE
 895    frequency or count is believed to be lower than FREQUENCY or COUNT
 896    respectively.  */
 897 void
 898 update_bb_profile_for_threading (basic_block bb, int edge_frequency,
 899                                  gcov_type count, edge taken_edge)
 900 {
 901   edge c;
 902   int prob;
 903   edge_iterator ei;
 904
 905   bb->count -= count;
 906   if (bb->count < 0)
 907     bb->count = 0;
 908
 909   /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
 910      Watch for overflows.  */
 911   if (bb->frequency)
 912     prob = edge_frequency * REG_BR_PROB_BASE / bb->frequency;
 913   else
 914     prob = 0;
 915   if (prob > taken_edge->probability)
 916     {
 917       if (dump_file)
 918         fprintf (dump_file, "Jump threading proved probability of edge "
 919                  "%i->%i too small (it is %i, should be %i).\n",
 920                  taken_edge->src->index, taken_edge->dest->index,
 921                  taken_edge->probability, prob);
 922       prob = taken_edge->probability;
 923     }
 924
 925   /* Now rescale the probabilities.  */
 926   taken_edge->probability -= prob;
 927   prob = REG_BR_PROB_BASE - prob;
 928   bb->frequency -= edge_frequency;
 929   if (bb->frequency < 0)
 930     bb->frequency = 0;
 931   if (prob <= 0)
 932     {
 933       if (dump_file)
 934         fprintf (dump_file, "Edge frequencies of bb %i has been reset, "
 935                  "frequency of block should end up being 0, it is %i\n",
 936                  bb->index, bb->frequency);
 937       EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
 938       ei = ei_start (bb->succs);
 939       ei_next (&ei);
 940       for (; (c = ei_safe_edge (ei)); ei_next (&ei))
 941         c->probability = 0;
 942     }
 943   else if (prob != REG_BR_PROB_BASE)
 944     {
 945       int scale = REG_BR_PROB_BASE / prob;
 946
 947       FOR_EACH_EDGE (c, ei, bb->succs)
 948         c->probability *= scale;
 949     }
 950
 951   if (bb != taken_edge->src)
 952     abort ();
 953   taken_edge->count -= count;
 954   if (taken_edge->count < 0)
 955     taken_edge->count = 0;
 956 }