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_insert (edge, src->succs, 0, e);
 274   VEC_safe_insert (edge, dst->preds, 0, 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_ordered_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_ordered_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_ordered_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_insert (edge, new_succ->preds, 0, 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_ordered_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_insert (edge, new_pred->succs, 0, 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       fprintf (file, "\nRegisters live at start:");
 624       dump_regset (bb->global_live_at_start, file);
 625
 626       fprintf (file, "\nRegisters live at end:");
 627       dump_regset (bb->global_live_at_end, file);
 628
 629       putc ('\n', file);
 630
 631       if (bb->global_live_at_start)
 632         {
 633           fprintf (file, "\nRegisters live at start:");
 634           dump_regset (bb->global_live_at_start, file);
 635         }
 636
 637       if (bb->global_live_at_end)
 638         {
 639           fprintf (file, "\nRegisters live at end:");
 640           dump_regset (bb->global_live_at_end, file);
 641         }
 642
 643       putc ('\n', file);
 644       check_bb_profile (bb, file);
 645     }
 646
 647   putc ('\n', file);
 648 }
 649
 650 void
 651 debug_flow_info (void)
 652 {
 653   dump_flow_info (stderr);
 654 }
 655
 656 void
 657 dump_edge_info (FILE *file, edge e, int do_succ)
 658 {
 659   basic_block side = (do_succ ? e->dest : e->src);
 660
 661   if (side == ENTRY_BLOCK_PTR)
 662     fputs (" ENTRY", file);
 663   else if (side == EXIT_BLOCK_PTR)
 664     fputs (" EXIT", file);
 665   else
 666     fprintf (file, " %d", side->index);
 667
 668   if (e->probability)
 669     fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
 670
 671   if (e->count)
 672     {
 673       fprintf (file, " count:");
 674       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
 675     }
 676
 677   if (e->flags)
 678     {
 679       static const char * const bitnames[] = {
 680         "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
 681         "can_fallthru", "irreducible", "sibcall", "loop_exit",
 682         "true", "false", "exec"
 683       };
 684       int comma = 0;
 685       int i, flags = e->flags;
 686
 687       fputs (" (", file);
 688       for (i = 0; flags; i++)
 689         if (flags & (1 << i))
 690           {
 691             flags &= ~(1 << i);
 692
 693             if (comma)
 694               fputc (',', file);
 695             if (i < (int) ARRAY_SIZE (bitnames))
 696               fputs (bitnames[i], file);
 697             else
 698               fprintf (file, "%d", i);
 699             comma = 1;
 700           }
 701
 702       fputc (')', file);
 703     }
 704 }
 705 \f
 706 /* Simple routines to easily allocate AUX fields of basic blocks.  */
 707
 708 static struct obstack block_aux_obstack;
 709 static void *first_block_aux_obj = 0;
 710 static struct obstack edge_aux_obstack;
 711 static void *first_edge_aux_obj = 0;
 712
 713 /* Allocate a memory block of SIZE as BB->aux.  The obstack must
 714    be first initialized by alloc_aux_for_blocks.  */
 715
 716 inline void
 717 alloc_aux_for_block (basic_block bb, int size)
 718 {
 719   /* Verify that aux field is clear.  */
 720   gcc_assert (!bb->aux && first_block_aux_obj);
 721   bb->aux = obstack_alloc (&block_aux_obstack, size);
 722   memset (bb->aux, 0, size);
 723 }
 724
 725 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
 726    alloc_aux_for_block for each basic block.  */
 727
 728 void
 729 alloc_aux_for_blocks (int size)
 730 {
 731   static int initialized;
 732
 733   if (!initialized)
 734     {
 735       gcc_obstack_init (&block_aux_obstack);
 736       initialized = 1;
 737     }
 738   else
 739     /* Check whether AUX data are still allocated.  */
 740     gcc_assert (!first_block_aux_obj);
 741
 742   first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
 743   if (size)
 744     {
 745       basic_block bb;
 746
 747       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 748         alloc_aux_for_block (bb, size);
 749     }
 750 }
 751
 752 /* Clear AUX pointers of all blocks.  */
 753
 754 void
 755 clear_aux_for_blocks (void)
 756 {
 757   basic_block bb;
 758
 759   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 760     bb->aux = NULL;
 761 }
 762
 763 /* Free data allocated in block_aux_obstack and clear AUX pointers
 764    of all blocks.  */
 765
 766 void
 767 free_aux_for_blocks (void)
 768 {
 769   gcc_assert (first_block_aux_obj);
 770   obstack_free (&block_aux_obstack, first_block_aux_obj);
 771   first_block_aux_obj = NULL;
 772
 773   clear_aux_for_blocks ();
 774 }
 775
 776 /* Allocate a memory edge of SIZE as BB->aux.  The obstack must
 777    be first initialized by alloc_aux_for_edges.  */
 778
 779 inline void
 780 alloc_aux_for_edge (edge e, int size)
 781 {
 782   /* Verify that aux field is clear.  */
 783   gcc_assert (!e->aux && first_edge_aux_obj);
 784   e->aux = obstack_alloc (&edge_aux_obstack, size);
 785   memset (e->aux, 0, size);
 786 }
 787
 788 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
 789    alloc_aux_for_edge for each basic edge.  */
 790
 791 void
 792 alloc_aux_for_edges (int size)
 793 {
 794   static int initialized;
 795
 796   if (!initialized)
 797     {
 798       gcc_obstack_init (&edge_aux_obstack);
 799       initialized = 1;
 800     }
 801   else
 802     /* Check whether AUX data are still allocated.  */
 803     gcc_assert (!first_edge_aux_obj);
 804
 805   first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
 806   if (size)
 807     {
 808       basic_block bb;
 809
 810       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 811         {
 812           edge e;
 813           edge_iterator ei;
 814
 815           FOR_EACH_EDGE (e, ei, bb->succs)
 816             alloc_aux_for_edge (e, size);
 817         }
 818     }
 819 }
 820
 821 /* Clear AUX pointers of all edges.  */
 822
 823 void
 824 clear_aux_for_edges (void)
 825 {
 826   basic_block bb;
 827   edge e;
 828
 829   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 830     {
 831       edge_iterator ei;
 832       FOR_EACH_EDGE (e, ei, bb->succs)
 833         e->aux = NULL;
 834     }
 835 }
 836
 837 /* Free data allocated in edge_aux_obstack and clear AUX pointers
 838    of all edges.  */
 839
 840 void
 841 free_aux_for_edges (void)
 842 {
 843   gcc_assert (first_edge_aux_obj);
 844   obstack_free (&edge_aux_obstack, first_edge_aux_obj);
 845   first_edge_aux_obj = NULL;
 846
 847   clear_aux_for_edges ();
 848 }
 849
 850 void
 851 debug_bb (basic_block bb)
 852 {
 853   dump_bb (bb, stderr, 0);
 854 }
 855
 856 basic_block
 857 debug_bb_n (int n)
 858 {
 859   basic_block bb = BASIC_BLOCK (n);
 860   dump_bb (bb, stderr, 0);
 861   return bb;
 862 }
 863
 864 /* Dumps cfg related information about basic block BB to FILE.  */
 865
 866 static void
 867 dump_cfg_bb_info (FILE *file, basic_block bb)
 868 {
 869   unsigned i;
 870   edge_iterator ei;
 871   bool first = true;
 872   static const char * const bb_bitnames[] =
 873     {
 874       "dirty", "new", "reachable", "visited", "irreducible_loop", "superblock"
 875     };
 876   const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
 877   edge e;
 878
 879   fprintf (file, "Basic block %d", bb->index);
 880   for (i = 0; i < n_bitnames; i++)
 881     if (bb->flags & (1 << i))
 882       {
 883         if (first)
 884           fprintf (file, " (");
 885         else
 886           fprintf (file, ", ");
 887         first = false;
 888         fprintf (file, bb_bitnames[i]);
 889       }
 890   if (!first)
 891     fprintf (file, ")");
 892   fprintf (file, "\n");
 893
 894   fprintf (file, "Predecessors: ");
 895   FOR_EACH_EDGE (e, ei, bb->preds)
 896     dump_edge_info (file, e, 0);
 897
 898   fprintf (file, "\nSuccessors: ");
 899   FOR_EACH_EDGE (e, ei, bb->succs)
 900     dump_edge_info (file, e, 1);
 901   fprintf (file, "\n\n");
 902 }
 903
 904 /* Dumps a brief description of cfg to FILE.  */
 905
 906 void
 907 brief_dump_cfg (FILE *file)
 908 {
 909   basic_block bb;
 910
 911   FOR_EACH_BB (bb)
 912     {
 913       dump_cfg_bb_info (file, bb);
 914     }
 915 }
 916
 917 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
 918    leave the block by TAKEN_EDGE.  Update profile of BB such that edge E can be
 919    redirected to destination of TAKEN_EDGE.
 920
 921    This function may leave the profile inconsistent in the case TAKEN_EDGE
 922    frequency or count is believed to be lower than FREQUENCY or COUNT
 923    respectively.  */
 924 void
 925 update_bb_profile_for_threading (basic_block bb, int edge_frequency,
 926                                  gcov_type count, edge taken_edge)
 927 {
 928   edge c;
 929   int prob;
 930   edge_iterator ei;
 931
 932   bb->count -= count;
 933   if (bb->count < 0)
 934     bb->count = 0;
 935
 936   /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
 937      Watch for overflows.  */
 938   if (bb->frequency)
 939     prob = edge_frequency * REG_BR_PROB_BASE / bb->frequency;
 940   else
 941     prob = 0;
 942   if (prob > taken_edge->probability)
 943     {
 944       if (dump_file)
 945         fprintf (dump_file, "Jump threading proved probability of edge "
 946                  "%i->%i too small (it is %i, should be %i).\n",
 947                  taken_edge->src->index, taken_edge->dest->index,
 948                  taken_edge->probability, prob);
 949       prob = taken_edge->probability;
 950     }
 951
 952   /* Now rescale the probabilities.  */
 953   taken_edge->probability -= prob;
 954   prob = REG_BR_PROB_BASE - prob;
 955   bb->frequency -= edge_frequency;
 956   if (bb->frequency < 0)
 957     bb->frequency = 0;
 958   if (prob <= 0)
 959     {
 960       if (dump_file)
 961         fprintf (dump_file, "Edge frequencies of bb %i has been reset, "
 962                  "frequency of block should end up being 0, it is %i\n",
 963                  bb->index, bb->frequency);
 964       EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
 965       ei = ei_start (bb->succs);
 966       ei_next (&ei);
 967       for (; (c = ei_safe_edge (ei)); ei_next (&ei))
 968         c->probability = 0;
 969     }
 970   else
 971     FOR_EACH_EDGE (c, ei, bb->succs)
 972       c->probability = ((c->probability * REG_BR_PROB_BASE) / (double) prob);
 973
 974   if (bb != taken_edge->src)
 975     abort ();
 976   taken_edge->count -= count;
 977   if (taken_edge->count < 0)
 978     taken_edge->count = 0;
 979 }