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