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