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