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, 2005
   4    Free Software Foundation, Inc.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  21 02111-1307, USA.  */
  22
  23 /* This file contains low level functions to manipulate the CFG and
  24    analyze it.  All other modules should not transform the data structure
  25    directly and use abstraction instead.  The file is supposed to be
  26    ordered bottom-up and should not contain any code dependent on a
  27    particular intermediate language (RTL or trees).
  28
  29    Available functionality:
  30      - Initialization/deallocation
  31          init_flow, clear_edges
  32      - Low level basic block manipulation
  33          alloc_block, expunge_block
  34      - Edge manipulation
  35          make_edge, make_single_succ_edge, cached_make_edge, remove_edge
  36          - Low level edge redirection (without updating instruction chain)
  37              redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
  38      - Dumping and debugging
  39          dump_flow_info, debug_flow_info, dump_edge_info
  40      - Allocation of AUX fields for basic blocks
  41          alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block
  42      - clear_bb_flags
  43      - Consistency checking
  44          verify_flow_info
  45      - Dumping and debugging
  46          print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
  47  */
  48 \f
  49 #include "config.h"
  50 #include "system.h"
  51 #include "coretypes.h"
  52 #include "tm.h"
  53 #include "tree.h"
  54 #include "rtl.h"
  55 #include "hard-reg-set.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 "alloc-pool.h"
  64 #include "timevar.h"
  65 #include "ggc.h"
  66
  67 /* The obstack on which the flow graph components are allocated.  */
  68
  69 struct bitmap_obstack reg_obstack;
  70
  71 /* Number of basic blocks in the current function.  */
  72
  73 int n_basic_blocks;
  74
  75 /* First free basic block number.  */
  76
  77 int last_basic_block;
  78
  79 /* Number of edges in the current function.  */
  80
  81 int n_edges;
  82
  83 /* The basic block array.  */
  84
  85 varray_type basic_block_info;
  86
  87 /* The special entry and exit blocks.  */
  88 basic_block ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR;
  89
  90 /* Memory alloc pool for bb member rbi.  */
  91 alloc_pool rbi_pool;
  92
  93 void debug_flow_info (void);
  94 static void free_edge (edge);
  95
  96 /* Indicate the presence of the profile.  */
  97 enum profile_status profile_status;
  98 \f
  99 /* Called once at initialization time.  */
 100
 101 void
 102 init_flow (void)
 103 {
 104   n_edges = 0;
 105
 106   ENTRY_BLOCK_PTR = ggc_alloc_cleared (sizeof (*ENTRY_BLOCK_PTR));
 107   ENTRY_BLOCK_PTR->index = ENTRY_BLOCK;
 108   EXIT_BLOCK_PTR = ggc_alloc_cleared (sizeof (*EXIT_BLOCK_PTR));
 109   EXIT_BLOCK_PTR->index = EXIT_BLOCK;
 110   ENTRY_BLOCK_PTR->next_bb = EXIT_BLOCK_PTR;
 111   EXIT_BLOCK_PTR->prev_bb = ENTRY_BLOCK_PTR;
 112 }
 113 \f
 114 /* Helper function for remove_edge and clear_edges.  Frees edge structure
 115    without actually unlinking it from the pred/succ lists.  */
 116
 117 static void
 118 free_edge (edge e ATTRIBUTE_UNUSED)
 119 {
 120   n_edges--;
 121   ggc_free (e);
 122 }
 123
 124 /* Free the memory associated with the edge structures.  */
 125
 126 void
 127 clear_edges (void)
 128 {
 129   basic_block bb;
 130   edge e;
 131   edge_iterator ei;
 132
 133   FOR_EACH_BB (bb)
 134     {
 135       FOR_EACH_EDGE (e, ei, bb->succs)
 136         free_edge (e);
 137       VEC_truncate (edge, bb->succs, 0);
 138       VEC_truncate (edge, bb->preds, 0);
 139     }
 140
 141   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 142     free_edge (e);
 143   VEC_truncate (edge, EXIT_BLOCK_PTR->preds, 0);
 144   VEC_truncate (edge, ENTRY_BLOCK_PTR->succs, 0);
 145
 146   gcc_assert (!n_edges);
 147 }
 148 \f
 149 /* Allocate memory for basic_block.  */
 150
 151 basic_block
 152 alloc_block (void)
 153 {
 154   basic_block bb;
 155   bb = ggc_alloc_cleared (sizeof (*bb));
 156   return bb;
 157 }
 158
 159 /* Create memory pool for rbi_pool.  */
 160
 161 void
 162 alloc_rbi_pool (void)
 163 {
 164   rbi_pool = create_alloc_pool ("rbi pool",
 165                                 sizeof (struct reorder_block_def),
 166                                 n_basic_blocks + 2);
 167 }
 168
 169 /* Free rbi_pool.  */
 170
 171 void
 172 free_rbi_pool (void)
 173 {
 174   free_alloc_pool (rbi_pool);
 175 }
 176
 177 /* Initialize rbi (the structure containing data used by basic block
 178    duplication and reordering) for the given basic block.  */
 179
 180 void
 181 initialize_bb_rbi (basic_block bb)
 182 {
 183   gcc_assert (!bb->rbi);
 184   bb->rbi = pool_alloc (rbi_pool);
 185   memset (bb->rbi, 0, sizeof (struct reorder_block_def));
 186 }
 187
 188 /* Link block B to chain after AFTER.  */
 189 void
 190 link_block (basic_block b, basic_block after)
 191 {
 192   b->next_bb = after->next_bb;
 193   b->prev_bb = after;
 194   after->next_bb = b;
 195   b->next_bb->prev_bb = b;
 196 }
 197
 198 /* Unlink block B from chain.  */
 199 void
 200 unlink_block (basic_block b)
 201 {
 202   b->next_bb->prev_bb = b->prev_bb;
 203   b->prev_bb->next_bb = b->next_bb;
 204   b->prev_bb = NULL;
 205   b->next_bb = NULL;
 206 }
 207
 208 /* Sequentially order blocks and compact the arrays.  */
 209 void
 210 compact_blocks (void)
 211 {
 212   int i;
 213   basic_block bb;
 214
 215   i = 0;
 216   FOR_EACH_BB (bb)
 217     {
 218       BASIC_BLOCK (i) = bb;
 219       bb->index = i;
 220       i++;
 221     }
 222
 223   gcc_assert (i == n_basic_blocks);
 224
 225   for (; i < last_basic_block; i++)
 226     BASIC_BLOCK (i) = NULL;
 227
 228   last_basic_block = n_basic_blocks;
 229 }
 230
 231 /* Remove block B from the basic block array.  */
 232
 233 void
 234 expunge_block (basic_block b)
 235 {
 236   unlink_block (b);
 237   BASIC_BLOCK (b->index) = NULL;
 238   n_basic_blocks--;
 239   /* We should be able to ggc_free here, but we are not.
 240      The dead SSA_NAMES are left pointing to dead statements that are pointing
 241      to dead basic blocks making garbage collector to die.
 242      We should be able to release all dead SSA_NAMES and at the same time we should
 243      clear out BB pointer of dead statements consistently.  */
 244 }
 245 \f
 246 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
 247    created edge.  Use this only if you are sure that this edge can't
 248    possibly already exist.  */
 249
 250 edge
 251 unchecked_make_edge (basic_block src, basic_block dst, int flags)
 252 {
 253   edge e;
 254   e = ggc_alloc_cleared (sizeof (*e));
 255   n_edges++;
 256
 257   VEC_safe_push (edge, src->succs, e);
 258   VEC_safe_push (edge, dst->preds, e);
 259
 260   e->src = src;
 261   e->dest = dst;
 262   e->flags = flags;
 263   e->dest_idx = EDGE_COUNT (dst->preds) - 1;
 264
 265   execute_on_growing_pred (e);
 266
 267   return e;
 268 }
 269
 270 /* Create an edge connecting SRC and DST with FLAGS optionally using
 271    edge cache CACHE.  Return the new edge, NULL if already exist.  */
 272
 273 edge
 274 cached_make_edge (sbitmap *edge_cache, basic_block src, basic_block dst, int flags)
 275 {
 276   int use_edge_cache;
 277   edge e;
 278
 279   /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that
 280      many edges to them, or we didn't allocate memory for it.  */
 281   use_edge_cache = (edge_cache
 282                     && src != ENTRY_BLOCK_PTR && dst != EXIT_BLOCK_PTR);
 283
 284   /* Make sure we don't add duplicate edges.  */
 285   switch (use_edge_cache)
 286     {
 287     default:
 288       /* Quick test for non-existence of the edge.  */
 289       if (! TEST_BIT (edge_cache[src->index], dst->index))
 290         break;
 291
 292       /* The edge exists; early exit if no work to do.  */
 293       if (flags == 0)
 294         return NULL;
 295
 296       /* Fall through.  */
 297     case 0:
 298       e = find_edge (src, dst);
 299       if (e)
 300         {
 301           e->flags |= flags;
 302           return NULL;
 303         }
 304       break;
 305     }
 306
 307   e = unchecked_make_edge (src, dst, flags);
 308
 309   if (use_edge_cache)
 310     SET_BIT (edge_cache[src->index], dst->index);
 311
 312   return e;
 313 }
 314
 315 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
 316    created edge or NULL if already exist.  */
 317
 318 edge
 319 make_edge (basic_block src, basic_block dest, int flags)
 320 {
 321   return cached_make_edge (NULL, src, dest, flags);
 322 }
 323
 324 /* Create an edge connecting SRC to DEST and set probability by knowing
 325    that it is the single edge leaving SRC.  */
 326
 327 edge
 328 make_single_succ_edge (basic_block src, basic_block dest, int flags)
 329 {
 330   edge e = make_edge (src, dest, flags);
 331
 332   e->probability = REG_BR_PROB_BASE;
 333   e->count = src->count;
 334   return e;
 335 }
 336
 337 /* This function will remove an edge from the flow graph.  */
 338
 339 void
 340 remove_edge (edge e)
 341 {
 342   edge tmp;
 343   basic_block src, dest;
 344   unsigned int dest_idx;
 345   bool found = false;
 346   edge_iterator ei;
 347
 348   execute_on_shrinking_pred (e);
 349
 350   src = e->src;
 351   dest = e->dest;
 352   dest_idx = e->dest_idx;
 353
 354   for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); )
 355     {
 356       if (tmp == e)
 357         {
 358           VEC_unordered_remove (edge, src->succs, ei.index);
 359           found = true;
 360           break;
 361         }
 362       else
 363         ei_next (&ei);
 364     }
 365
 366   gcc_assert (found);
 367
 368   VEC_unordered_remove (edge, dest->preds, dest_idx);
 369
 370   /* If we removed an edge in the middle of the edge vector, we need
 371      to update dest_idx of the edge that moved into the "hole".  */
 372   if (dest_idx < EDGE_COUNT (dest->preds))
 373     EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
 374
 375   free_edge (e);
 376 }
 377
 378 /* Redirect an edge's successor from one block to another.  */
 379
 380 void
 381 redirect_edge_succ (edge e, basic_block new_succ)
 382 {
 383   basic_block dest = e->dest;
 384   unsigned int dest_idx = e->dest_idx;
 385
 386   execute_on_shrinking_pred (e);
 387
 388   VEC_unordered_remove (edge, dest->preds, dest_idx);
 389
 390   /* If we removed an edge in the middle of the edge vector, we need
 391      to update dest_idx of the edge that moved into the "hole".  */
 392   if (dest_idx < EDGE_COUNT (dest->preds))
 393     EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
 394
 395   /* Reconnect the edge to the new successor block.  */
 396   VEC_safe_push (edge, new_succ->preds, e);
 397   e->dest = new_succ;
 398   e->dest_idx = EDGE_COUNT (new_succ->preds) - 1;
 399   execute_on_growing_pred (e);
 400 }
 401
 402 /* Like previous but avoid possible duplicate edge.  */
 403
 404 edge
 405 redirect_edge_succ_nodup (edge e, basic_block new_succ)
 406 {
 407   edge s;
 408
 409   s = find_edge (e->src, new_succ);
 410   if (s && s != e)
 411     {
 412       s->flags |= e->flags;
 413       s->probability += e->probability;
 414       if (s->probability > REG_BR_PROB_BASE)
 415         s->probability = REG_BR_PROB_BASE;
 416       s->count += e->count;
 417       remove_edge (e);
 418       e = s;
 419     }
 420   else
 421     redirect_edge_succ (e, new_succ);
 422
 423   return e;
 424 }
 425
 426 /* Redirect an edge's predecessor from one block to another.  */
 427
 428 void
 429 redirect_edge_pred (edge e, basic_block new_pred)
 430 {
 431   edge tmp;
 432   edge_iterator ei;
 433   bool found = false;
 434
 435   /* Disconnect the edge from the old predecessor block.  */
 436   for (ei = ei_start (e->src->succs); (tmp = ei_safe_edge (ei)); )
 437     {
 438       if (tmp == e)
 439         {
 440           VEC_unordered_remove (edge, e->src->succs, ei.index);
 441           found = true;
 442           break;
 443         }
 444       else
 445         ei_next (&ei);
 446     }
 447
 448   gcc_assert (found);
 449
 450   /* Reconnect the edge to the new predecessor block.  */
 451   VEC_safe_push (edge, new_pred->succs, e);
 452   e->src = new_pred;
 453 }
 454
 455 /* Clear all basic block flags, with the exception of partitioning.  */
 456 void
 457 clear_bb_flags (void)
 458 {
 459   basic_block bb;
 460
 461   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 462     bb->flags = BB_PARTITION (bb);
 463 }
 464 \f
 465 /* Check the consistency of profile information.  We can't do that
 466    in verify_flow_info, as the counts may get invalid for incompletely
 467    solved graphs, later eliminating of conditionals or roundoff errors.
 468    It is still practical to have them reported for debugging of simple
 469    testcases.  */
 470 void
 471 check_bb_profile (basic_block bb, FILE * file)
 472 {
 473   edge e;
 474   int sum = 0;
 475   gcov_type lsum;
 476   edge_iterator ei;
 477
 478   if (profile_status == PROFILE_ABSENT)
 479     return;
 480
 481   if (bb != EXIT_BLOCK_PTR)
 482     {
 483       FOR_EACH_EDGE (e, ei, bb->succs)
 484         sum += e->probability;
 485       if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
 486         fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
 487                  sum * 100.0 / REG_BR_PROB_BASE);
 488       lsum = 0;
 489       FOR_EACH_EDGE (e, ei, bb->succs)
 490         lsum += e->count;
 491       if (EDGE_COUNT (bb->succs)
 492           && (lsum - bb->count > 100 || lsum - bb->count < -100))
 493         fprintf (file, "Invalid sum of outgoing counts %i, should be %i\n",
 494                  (int) lsum, (int) bb->count);
 495     }
 496   if (bb != ENTRY_BLOCK_PTR)
 497     {
 498       sum = 0;
 499       FOR_EACH_EDGE (e, ei, bb->preds)
 500         sum += EDGE_FREQUENCY (e);
 501       if (abs (sum - bb->frequency) > 100)
 502         fprintf (file,
 503                  "Invalid sum of incoming frequencies %i, should be %i\n",
 504                  sum, bb->frequency);
 505       lsum = 0;
 506       FOR_EACH_EDGE (e, ei, bb->preds)
 507         lsum += e->count;
 508       if (lsum - bb->count > 100 || lsum - bb->count < -100)
 509         fprintf (file, "Invalid sum of incoming counts %i, should be %i\n",
 510                  (int) lsum, (int) bb->count);
 511     }
 512 }
 513 \f
 514 void
 515 dump_flow_info (FILE *file)
 516 {
 517   int i;
 518   basic_block bb;
 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 }