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