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