gcc/cfg.c

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