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