gcc/cfg.c

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