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, 2006, 2007, 2008, 2009, 2010
   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 3, 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 COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  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    TODO: Document these "Available functionality" functions in the files
  48    that implement them.
  49  */
  50 \f
  51 #include "config.h"
  52 #include "system.h"
  53 #include "coretypes.h"
  54 #include "obstack.h"
  55 #include "ggc.h"
  56 #include "hashtab.h"
  57 #include "alloc-pool.h"
  58 #include "basic-block.h"
  59 #include "df.h"
  60 #include "cfgloop.h" /* FIXME: For struct loop.  */
  61 #include "dumpfile.h"
  62
  63 \f
  64 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
  65
  66 /* Called once at initialization time.  */
  67
  68 void
  69 init_flow (struct function *the_fun)
  70 {
  71   if (!the_fun->cfg)
  72     the_fun->cfg = ggc_alloc_cleared_control_flow_graph ();
  73   n_edges_for_function (the_fun) = 0;
  74   ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)
  75     = ggc_alloc_cleared_basic_block_def ();
  76   ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)->index = ENTRY_BLOCK;
  77   EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)
  78     = ggc_alloc_cleared_basic_block_def ();
  79   EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)->index = EXIT_BLOCK;
  80   ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)->next_bb
  81     = EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun);
  82   EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)->prev_bb
  83     = ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun);
  84 }
  85 \f
  86 /* Helper function for remove_edge and clear_edges.  Frees edge structure
  87    without actually removing it from the pred/succ arrays.  */
  88
  89 static void
  90 free_edge (edge e)
  91 {
  92   n_edges--;
  93   ggc_free (e);
  94 }
  95
  96 /* Free the memory associated with the edge structures.  */
  97
  98 void
  99 clear_edges (void)
 100 {
 101   basic_block bb;
 102   edge e;
 103   edge_iterator ei;
 104
 105   FOR_EACH_BB (bb)
 106     {
 107       FOR_EACH_EDGE (e, ei, bb->succs)
 108         free_edge (e);
 109       VEC_truncate (edge, bb->succs, 0);
 110       VEC_truncate (edge, bb->preds, 0);
 111     }
 112
 113   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 114     free_edge (e);
 115   VEC_truncate (edge, EXIT_BLOCK_PTR->preds, 0);
 116   VEC_truncate (edge, ENTRY_BLOCK_PTR->succs, 0);
 117
 118   gcc_assert (!n_edges);
 119 }
 120 \f
 121 /* Allocate memory for basic_block.  */
 122
 123 basic_block
 124 alloc_block (void)
 125 {
 126   basic_block bb;
 127   bb = ggc_alloc_cleared_basic_block_def ();
 128   return bb;
 129 }
 130
 131 /* Link block B to chain after AFTER.  */
 132 void
 133 link_block (basic_block b, basic_block after)
 134 {
 135   b->next_bb = after->next_bb;
 136   b->prev_bb = after;
 137   after->next_bb = b;
 138   b->next_bb->prev_bb = b;
 139 }
 140
 141 /* Unlink block B from chain.  */
 142 void
 143 unlink_block (basic_block b)
 144 {
 145   b->next_bb->prev_bb = b->prev_bb;
 146   b->prev_bb->next_bb = b->next_bb;
 147   b->prev_bb = NULL;
 148   b->next_bb = NULL;
 149 }
 150
 151 /* Sequentially order blocks and compact the arrays.  */
 152 void
 153 compact_blocks (void)
 154 {
 155   int i;
 156
 157   SET_BASIC_BLOCK (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
 158   SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
 159
 160   if (df)
 161     df_compact_blocks ();
 162   else
 163     {
 164       basic_block bb;
 165
 166       i = NUM_FIXED_BLOCKS;
 167       FOR_EACH_BB (bb)
 168         {
 169           SET_BASIC_BLOCK (i, bb);
 170           bb->index = i;
 171           i++;
 172         }
 173       gcc_assert (i == n_basic_blocks);
 174
 175       for (; i < last_basic_block; i++)
 176         SET_BASIC_BLOCK (i, NULL);
 177     }
 178   last_basic_block = n_basic_blocks;
 179 }
 180
 181 /* Remove block B from the basic block array.  */
 182
 183 void
 184 expunge_block (basic_block b)
 185 {
 186   unlink_block (b);
 187   SET_BASIC_BLOCK (b->index, NULL);
 188   n_basic_blocks--;
 189   /* We should be able to ggc_free here, but we are not.
 190      The dead SSA_NAMES are left pointing to dead statements that are pointing
 191      to dead basic blocks making garbage collector to die.
 192      We should be able to release all dead SSA_NAMES and at the same time we should
 193      clear out BB pointer of dead statements consistently.  */
 194 }
 195 \f
 196 /* Connect E to E->src.  */
 197
 198 static inline void
 199 connect_src (edge e)
 200 {
 201   VEC_safe_push (edge, gc, e->src->succs, e);
 202   df_mark_solutions_dirty ();
 203 }
 204
 205 /* Connect E to E->dest.  */
 206
 207 static inline void
 208 connect_dest (edge e)
 209 {
 210   basic_block dest = e->dest;
 211   VEC_safe_push (edge, gc, dest->preds, e);
 212   e->dest_idx = EDGE_COUNT (dest->preds) - 1;
 213   df_mark_solutions_dirty ();
 214 }
 215
 216 /* Disconnect edge E from E->src.  */
 217
 218 static inline void
 219 disconnect_src (edge e)
 220 {
 221   basic_block src = e->src;
 222   edge_iterator ei;
 223   edge tmp;
 224
 225   for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); )
 226     {
 227       if (tmp == e)
 228         {
 229           VEC_unordered_remove (edge, src->succs, ei.index);
 230           df_mark_solutions_dirty ();
 231           return;
 232         }
 233       else
 234         ei_next (&ei);
 235     }
 236
 237   gcc_unreachable ();
 238 }
 239
 240 /* Disconnect edge E from E->dest.  */
 241
 242 static inline void
 243 disconnect_dest (edge e)
 244 {
 245   basic_block dest = e->dest;
 246   unsigned int dest_idx = e->dest_idx;
 247
 248   VEC_unordered_remove (edge, dest->preds, dest_idx);
 249
 250   /* If we removed an edge in the middle of the edge vector, we need
 251      to update dest_idx of the edge that moved into the "hole".  */
 252   if (dest_idx < EDGE_COUNT (dest->preds))
 253     EDGE_PRED (dest, dest_idx)->dest_idx = dest_idx;
 254   df_mark_solutions_dirty ();
 255 }
 256
 257 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
 258    created edge.  Use this only if you are sure that this edge can't
 259    possibly already exist.  */
 260
 261 edge
 262 unchecked_make_edge (basic_block src, basic_block dst, int flags)
 263 {
 264   edge e;
 265   e = ggc_alloc_cleared_edge_def ();
 266   n_edges++;
 267
 268   e->src = src;
 269   e->dest = dst;
 270   e->flags = flags;
 271
 272   connect_src (e);
 273   connect_dest (e);
 274
 275   execute_on_growing_pred (e);
 276   return e;
 277 }
 278
 279 /* Create an edge connecting SRC and DST with FLAGS optionally using
 280    edge cache CACHE.  Return the new edge, NULL if already exist.  */
 281
 282 edge
 283 cached_make_edge (sbitmap edge_cache, basic_block src, basic_block dst, int flags)
 284 {
 285   if (edge_cache == NULL
 286       || src == ENTRY_BLOCK_PTR
 287       || dst == EXIT_BLOCK_PTR)
 288     return make_edge (src, dst, flags);
 289
 290   /* Does the requested edge already exist?  */
 291   if (! TEST_BIT (edge_cache, dst->index))
 292     {
 293       /* The edge does not exist.  Create one and update the
 294          cache.  */
 295       SET_BIT (edge_cache, dst->index);
 296       return unchecked_make_edge (src, dst, flags);
 297     }
 298
 299   /* At this point, we know that the requested edge exists.  Adjust
 300      flags if necessary.  */
 301   if (flags)
 302     {
 303       edge e = find_edge (src, dst);
 304       e->flags |= flags;
 305     }
 306
 307   return NULL;
 308 }
 309
 310 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
 311    created edge or NULL if already exist.  */
 312
 313 edge
 314 make_edge (basic_block src, basic_block dest, int flags)
 315 {
 316   edge e = find_edge (src, dest);
 317
 318   /* Make sure we don't add duplicate edges.  */
 319   if (e)
 320     {
 321       e->flags |= flags;
 322       return NULL;
 323     }
 324
 325   return unchecked_make_edge (src, dest, flags);
 326 }
 327
 328 /* Create an edge connecting SRC to DEST and set probability by knowing
 329    that it is the single edge leaving SRC.  */
 330
 331 edge
 332 make_single_succ_edge (basic_block src, basic_block dest, int flags)
 333 {
 334   edge e = make_edge (src, dest, flags);
 335
 336   e->probability = REG_BR_PROB_BASE;
 337   e->count = src->count;
 338   return e;
 339 }
 340
 341 /* This function will remove an edge from the flow graph.  */
 342
 343 void
 344 remove_edge_raw (edge e)
 345 {
 346   remove_predictions_associated_with_edge (e);
 347   execute_on_shrinking_pred (e);
 348
 349   disconnect_src (e);
 350   disconnect_dest (e);
 351
 352   free_edge (e);
 353 }
 354
 355 /* Redirect an edge's successor from one block to another.  */
 356
 357 void
 358 redirect_edge_succ (edge e, basic_block new_succ)
 359 {
 360   execute_on_shrinking_pred (e);
 361
 362   disconnect_dest (e);
 363
 364   e->dest = new_succ;
 365
 366   /* Reconnect the edge to the new successor block.  */
 367   connect_dest (e);
 368
 369   execute_on_growing_pred (e);
 370 }
 371
 372 /* Redirect an edge's predecessor from one block to another.  */
 373
 374 void
 375 redirect_edge_pred (edge e, basic_block new_pred)
 376 {
 377   disconnect_src (e);
 378
 379   e->src = new_pred;
 380
 381   /* Reconnect the edge to the new predecessor block.  */
 382   connect_src (e);
 383 }
 384
 385 /* Clear all basic block flags that do not have to be preserved.  */
 386 void
 387 clear_bb_flags (void)
 388 {
 389   basic_block bb;
 390
 391   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 392     bb->flags &= BB_FLAGS_TO_PRESERVE;
 393 }
 394 \f
 395 /* Check the consistency of profile information.  We can't do that
 396    in verify_flow_info, as the counts may get invalid for incompletely
 397    solved graphs, later eliminating of conditionals or roundoff errors.
 398    It is still practical to have them reported for debugging of simple
 399    testcases.  */
 400 static void
 401 check_bb_profile (basic_block bb, FILE * file, int indent, int flags)
 402 {
 403   edge e;
 404   int sum = 0;
 405   gcov_type lsum;
 406   edge_iterator ei;
 407   char *s_indent = (char *) alloca ((size_t) indent + 1);
 408   memset ((void *) s_indent, ' ', (size_t) indent);
 409   s_indent[indent] = '\0';
 410
 411   if (profile_status == PROFILE_ABSENT)
 412     return;
 413
 414   if (bb != EXIT_BLOCK_PTR)
 415     {
 416       FOR_EACH_EDGE (e, ei, bb->succs)
 417         sum += e->probability;
 418       if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
 419         fprintf (file, "%s%sInvalid sum of outgoing probabilities %.1f%%\n",
 420                  (flags & TDF_COMMENT) ? ";; " : "", s_indent,
 421                  sum * 100.0 / REG_BR_PROB_BASE);
 422       lsum = 0;
 423       FOR_EACH_EDGE (e, ei, bb->succs)
 424         lsum += e->count;
 425       if (EDGE_COUNT (bb->succs)
 426           && (lsum - bb->count > 100 || lsum - bb->count < -100))
 427         fprintf (file, "%s%sInvalid sum of outgoing counts %i, should be %i\n",
 428                  (flags & TDF_COMMENT) ? ";; " : "", s_indent,
 429                  (int) lsum, (int) bb->count);
 430     }
 431   if (bb != ENTRY_BLOCK_PTR)
 432     {
 433       sum = 0;
 434       FOR_EACH_EDGE (e, ei, bb->preds)
 435         sum += EDGE_FREQUENCY (e);
 436       if (abs (sum - bb->frequency) > 100)
 437         fprintf (file,
 438                  "%s%sInvalid sum of incoming frequencies %i, should be %i\n",
 439                  (flags & TDF_COMMENT) ? ";; " : "", s_indent,
 440                  sum, bb->frequency);
 441       lsum = 0;
 442       FOR_EACH_EDGE (e, ei, bb->preds)
 443         lsum += e->count;
 444       if (lsum - bb->count > 100 || lsum - bb->count < -100)
 445         fprintf (file, "%s%sInvalid sum of incoming counts %i, should be %i\n",
 446                  (flags & TDF_COMMENT) ? ";; " : "", s_indent,
 447                  (int) lsum, (int) bb->count);
 448     }
 449 }
 450 \f
 451 void
 452 dump_edge_info (FILE *file, edge e, int flags, int do_succ)
 453 {
 454   basic_block side = (do_succ ? e->dest : e->src);
 455   bool do_details = false;
 456
 457   if ((flags & TDF_DETAILS) != 0
 458       && (flags & TDF_SLIM) == 0)
 459     do_details = true;
 460
 461   /* ENTRY_BLOCK_PTR/EXIT_BLOCK_PTR depend on cfun.
 462      Compare against ENTRY_BLOCK/EXIT_BLOCK to avoid that dependency.  */
 463   if (side->index == ENTRY_BLOCK)
 464     fputs (" ENTRY", file);
 465   else if (side->index == EXIT_BLOCK)
 466     fputs (" EXIT", file);
 467   else
 468     fprintf (file, " %d", side->index);
 469
 470   if (e->probability && do_details)
 471     fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
 472
 473   if (e->count && do_details)
 474     {
 475       fputs (" count:", file);
 476       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
 477     }
 478
 479   if (e->flags && do_details)
 480     {
 481       static const char * const bitnames[] =
 482         {
 483 #define DEF_EDGE_FLAG(NAME,IDX) #NAME ,
 484 #include "cfg-flags.def"
 485           NULL
 486 #undef DEF_EDGE_FLAG
 487         };
 488       bool comma = false;
 489       int i, flags = e->flags;
 490
 491       gcc_assert (e->flags <= EDGE_ALL_FLAGS);
 492       fputs (" (", file);
 493       for (i = 0; flags; i++)
 494         if (flags & (1 << i))
 495           {
 496             flags &= ~(1 << i);
 497
 498             if (comma)
 499               fputc (',', file);
 500             fputs (bitnames[i], file);
 501             comma = true;
 502           }
 503
 504       fputc (')', file);
 505     }
 506 }
 507 \f
 508 /* Simple routines to easily allocate AUX fields of basic blocks.  */
 509
 510 static struct obstack block_aux_obstack;
 511 static void *first_block_aux_obj = 0;
 512 static struct obstack edge_aux_obstack;
 513 static void *first_edge_aux_obj = 0;
 514
 515 /* Allocate a memory block of SIZE as BB->aux.  The obstack must
 516    be first initialized by alloc_aux_for_blocks.  */
 517
 518 static void
 519 alloc_aux_for_block (basic_block bb, int size)
 520 {
 521   /* Verify that aux field is clear.  */
 522   gcc_assert (!bb->aux && first_block_aux_obj);
 523   bb->aux = obstack_alloc (&block_aux_obstack, size);
 524   memset (bb->aux, 0, size);
 525 }
 526
 527 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
 528    alloc_aux_for_block for each basic block.  */
 529
 530 void
 531 alloc_aux_for_blocks (int size)
 532 {
 533   static int initialized;
 534
 535   if (!initialized)
 536     {
 537       gcc_obstack_init (&block_aux_obstack);
 538       initialized = 1;
 539     }
 540   else
 541     /* Check whether AUX data are still allocated.  */
 542     gcc_assert (!first_block_aux_obj);
 543
 544   first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
 545   if (size)
 546     {
 547       basic_block bb;
 548
 549       FOR_ALL_BB (bb)
 550         alloc_aux_for_block (bb, size);
 551     }
 552 }
 553
 554 /* Clear AUX pointers of all blocks.  */
 555
 556 void
 557 clear_aux_for_blocks (void)
 558 {
 559   basic_block bb;
 560
 561   FOR_ALL_BB (bb)
 562     bb->aux = NULL;
 563 }
 564
 565 /* Free data allocated in block_aux_obstack and clear AUX pointers
 566    of all blocks.  */
 567
 568 void
 569 free_aux_for_blocks (void)
 570 {
 571   gcc_assert (first_block_aux_obj);
 572   obstack_free (&block_aux_obstack, first_block_aux_obj);
 573   first_block_aux_obj = NULL;
 574
 575   clear_aux_for_blocks ();
 576 }
 577
 578 /* Allocate a memory edge of SIZE as E->aux.  The obstack must
 579    be first initialized by alloc_aux_for_edges.  */
 580
 581 void
 582 alloc_aux_for_edge (edge e, int size)
 583 {
 584   /* Verify that aux field is clear.  */
 585   gcc_assert (!e->aux && first_edge_aux_obj);
 586   e->aux = obstack_alloc (&edge_aux_obstack, size);
 587   memset (e->aux, 0, size);
 588 }
 589
 590 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
 591    alloc_aux_for_edge for each basic edge.  */
 592
 593 void
 594 alloc_aux_for_edges (int size)
 595 {
 596   static int initialized;
 597
 598   if (!initialized)
 599     {
 600       gcc_obstack_init (&edge_aux_obstack);
 601       initialized = 1;
 602     }
 603   else
 604     /* Check whether AUX data are still allocated.  */
 605     gcc_assert (!first_edge_aux_obj);
 606
 607   first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
 608   if (size)
 609     {
 610       basic_block bb;
 611
 612       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 613         {
 614           edge e;
 615           edge_iterator ei;
 616
 617           FOR_EACH_EDGE (e, ei, bb->succs)
 618             alloc_aux_for_edge (e, size);
 619         }
 620     }
 621 }
 622
 623 /* Clear AUX pointers of all edges.  */
 624
 625 void
 626 clear_aux_for_edges (void)
 627 {
 628   basic_block bb;
 629   edge e;
 630
 631   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 632     {
 633       edge_iterator ei;
 634       FOR_EACH_EDGE (e, ei, bb->succs)
 635         e->aux = NULL;
 636     }
 637 }
 638
 639 /* Free data allocated in edge_aux_obstack and clear AUX pointers
 640    of all edges.  */
 641
 642 void
 643 free_aux_for_edges (void)
 644 {
 645   gcc_assert (first_edge_aux_obj);
 646   obstack_free (&edge_aux_obstack, first_edge_aux_obj);
 647   first_edge_aux_obj = NULL;
 648
 649   clear_aux_for_edges ();
 650 }
 651
 652 DEBUG_FUNCTION void
 653 debug_bb (basic_block bb)
 654 {
 655   dump_bb (stderr, bb, 0, dump_flags);
 656 }
 657
 658 DEBUG_FUNCTION basic_block
 659 debug_bb_n (int n)
 660 {
 661   basic_block bb = BASIC_BLOCK (n);
 662   debug_bb (bb);
 663   return bb;
 664 }
 665
 666 /* Dumps cfg related information about basic block BB to OUTF.
 667    If HEADER is true, dump things that appear before the instructions
 668    contained in BB.  If FOOTER is true, dump things that appear after.
 669    Flags are the TDF_* masks as documented in dumpfile.h.
 670    NB: With TDF_DETAILS, it is assumed that cfun is available, so
 671    that maybe_hot_bb_p and probably_never_executed_bb_p don't ICE.  */
 672
 673 void
 674 dump_bb_info (FILE *outf, basic_block bb, int indent, int flags,
 675               bool do_header, bool do_footer)
 676 {
 677   edge_iterator ei;
 678   edge e;
 679   static const char * const bb_bitnames[] =
 680     {
 681 #define DEF_BASIC_BLOCK_FLAG(NAME,IDX) #NAME ,
 682 #include "cfg-flags.def"
 683       NULL
 684 #undef DEF_BASIC_BLOCK_FLAG
 685     };
 686   const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
 687   bool first;
 688   char *s_indent = (char *) alloca ((size_t) indent + 1);
 689   memset ((void *) s_indent, ' ', (size_t) indent);
 690   s_indent[indent] = '\0';
 691
 692   gcc_assert (bb->flags <= BB_ALL_FLAGS);
 693
 694   if (do_header)
 695     {
 696       unsigned i;
 697
 698       if (flags & TDF_COMMENT)
 699         fputs (";; ", outf);
 700       fprintf (outf, "%sbasic block %d, loop depth %d",
 701                s_indent, bb->index, bb_loop_depth (bb));
 702       if (flags & TDF_DETAILS)
 703         {
 704           fprintf (outf, ", count " HOST_WIDEST_INT_PRINT_DEC,
 705                    (HOST_WIDEST_INT) bb->count);
 706           fprintf (outf, ", freq %i", bb->frequency);
 707           if (maybe_hot_bb_p (bb))
 708             fputs (", maybe hot", outf);
 709           if (probably_never_executed_bb_p (bb))
 710             fputs (", probably never executed", outf);
 711         }
 712       fputc ('\n', outf);
 713       if (TDF_DETAILS)
 714         check_bb_profile (bb, outf, indent, flags);
 715
 716       if (flags & TDF_DETAILS)
 717         {
 718           if (flags & TDF_COMMENT)
 719             fputs (";; ", outf);
 720           fprintf (outf, "%s prev block ", s_indent);
 721           if (bb->prev_bb)
 722             fprintf (outf, "%d", bb->prev_bb->index);
 723           else
 724             fprintf (outf, "(nil)");
 725           fprintf (outf, ", next block ");
 726           if (bb->next_bb)
 727             fprintf (outf, "%d", bb->next_bb->index);
 728           else
 729             fprintf (outf, "(nil)");
 730
 731           fputs (", flags:", outf);
 732           first = true;
 733           for (i = 0; i < n_bitnames; i++)
 734             if (bb->flags & (1 << i))
 735               {
 736                 if (first)
 737                   fputs (" (", outf);
 738                 else
 739                   fputs (", ", outf);
 740                 first = false;
 741                 fputs (bb_bitnames[i], outf);
 742               }
 743           if (!first)
 744             fputc (')', outf);
 745           fputc ('\n', outf);
 746         }
 747
 748       if (flags & TDF_COMMENT)
 749         fputs (";; ", outf);
 750       fprintf (outf, "%s pred:      ", s_indent);
 751       first = true;
 752       FOR_EACH_EDGE (e, ei, bb->preds)
 753         {
 754           if (! first)
 755             {
 756               if (flags & TDF_COMMENT)
 757                 fputs (";; ", outf);
 758               fprintf (outf, "%s            ", s_indent);
 759             }
 760           first = false;
 761           dump_edge_info (outf, e, flags, 0);
 762           fputc ('\n', outf);
 763         }
 764     }
 765
 766   if (do_footer)
 767     {
 768       if (flags & TDF_COMMENT)
 769         fputs (";; ", outf);
 770       fprintf (outf, "%s succ:      ", s_indent);
 771       first = true;
 772       FOR_EACH_EDGE (e, ei, bb->succs)
 773         {
 774           if (! first)
 775             {
 776               if (flags & TDF_COMMENT)
 777                 fputs (";; ", outf);
 778               fprintf (outf, "%s            ", s_indent);
 779             }
 780           first = false;
 781           dump_edge_info (outf, e, flags, 1);
 782           fputc ('\n', outf);
 783         }
 784     }
 785 }
 786
 787 /* Dumps a brief description of cfg to FILE.  */
 788
 789 void
 790 brief_dump_cfg (FILE *file, int flags)
 791 {
 792   basic_block bb;
 793
 794   FOR_EACH_BB (bb)
 795     {
 796       dump_bb_info (file, bb, 0,
 797                     flags & (TDF_COMMENT | TDF_DETAILS),
 798                     true, true);
 799     }
 800 }
 801
 802 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
 803    leave the block by TAKEN_EDGE.  Update profile of BB such that edge E can be
 804    redirected to destination of TAKEN_EDGE.
 805
 806    This function may leave the profile inconsistent in the case TAKEN_EDGE
 807    frequency or count is believed to be lower than FREQUENCY or COUNT
 808    respectively.  */
 809 void
 810 update_bb_profile_for_threading (basic_block bb, int edge_frequency,
 811                                  gcov_type count, edge taken_edge)
 812 {
 813   edge c;
 814   int prob;
 815   edge_iterator ei;
 816
 817   bb->count -= count;
 818   if (bb->count < 0)
 819     {
 820       if (dump_file)
 821         fprintf (dump_file, "bb %i count became negative after threading",
 822                  bb->index);
 823       bb->count = 0;
 824     }
 825
 826   /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
 827      Watch for overflows.  */
 828   if (bb->frequency)
 829     prob = edge_frequency * REG_BR_PROB_BASE / bb->frequency;
 830   else
 831     prob = 0;
 832   if (prob > taken_edge->probability)
 833     {
 834       if (dump_file)
 835         fprintf (dump_file, "Jump threading proved probability of edge "
 836                  "%i->%i too small (it is %i, should be %i).\n",
 837                  taken_edge->src->index, taken_edge->dest->index,
 838                  taken_edge->probability, prob);
 839       prob = taken_edge->probability;
 840     }
 841
 842   /* Now rescale the probabilities.  */
 843   taken_edge->probability -= prob;
 844   prob = REG_BR_PROB_BASE - prob;
 845   bb->frequency -= edge_frequency;
 846   if (bb->frequency < 0)
 847     bb->frequency = 0;
 848   if (prob <= 0)
 849     {
 850       if (dump_file)
 851         fprintf (dump_file, "Edge frequencies of bb %i has been reset, "
 852                  "frequency of block should end up being 0, it is %i\n",
 853                  bb->index, bb->frequency);
 854       EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
 855       ei = ei_start (bb->succs);
 856       ei_next (&ei);
 857       for (; (c = ei_safe_edge (ei)); ei_next (&ei))
 858         c->probability = 0;
 859     }
 860   else if (prob != REG_BR_PROB_BASE)
 861     {
 862       int scale = RDIV (65536 * REG_BR_PROB_BASE, prob);
 863
 864       FOR_EACH_EDGE (c, ei, bb->succs)
 865         {
 866           /* Protect from overflow due to additional scaling.  */
 867           if (c->probability > prob)
 868             c->probability = REG_BR_PROB_BASE;
 869           else
 870             {
 871               c->probability = RDIV (c->probability * scale, 65536);
 872               if (c->probability > REG_BR_PROB_BASE)
 873                 c->probability = REG_BR_PROB_BASE;
 874             }
 875         }
 876     }
 877
 878   gcc_assert (bb == taken_edge->src);
 879   taken_edge->count -= count;
 880   if (taken_edge->count < 0)
 881     {
 882       if (dump_file)
 883         fprintf (dump_file, "edge %i->%i count became negative after threading",
 884                  taken_edge->src->index, taken_edge->dest->index);
 885       taken_edge->count = 0;
 886     }
 887 }
 888
 889 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
 890    by NUM/DEN, in int arithmetic.  May lose some accuracy.  */
 891 void
 892 scale_bbs_frequencies_int (basic_block *bbs, int nbbs, int num, int den)
 893 {
 894   int i;
 895   edge e;
 896   if (num < 0)
 897     num = 0;
 898
 899   /* Scale NUM and DEN to avoid overflows.  Frequencies are in order of
 900      10^4, if we make DEN <= 10^3, we can afford to upscale by 100
 901      and still safely fit in int during calculations.  */
 902   if (den > 1000)
 903     {
 904       if (num > 1000000)
 905         return;
 906
 907       num = RDIV (1000 * num, den);
 908       den = 1000;
 909     }
 910   if (num > 100 * den)
 911     return;
 912
 913   for (i = 0; i < nbbs; i++)
 914     {
 915       edge_iterator ei;
 916       bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
 917       /* Make sure the frequencies do not grow over BB_FREQ_MAX.  */
 918       if (bbs[i]->frequency > BB_FREQ_MAX)
 919         bbs[i]->frequency = BB_FREQ_MAX;
 920       bbs[i]->count = RDIV (bbs[i]->count * num, den);
 921       FOR_EACH_EDGE (e, ei, bbs[i]->succs)
 922         e->count = RDIV (e->count * num, den);
 923     }
 924 }
 925
 926 /* numbers smaller than this value are safe to multiply without getting
 927    64bit overflow.  */
 928 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
 929
 930 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
 931    by NUM/DEN, in gcov_type arithmetic.  More accurate than previous
 932    function but considerably slower.  */
 933 void
 934 scale_bbs_frequencies_gcov_type (basic_block *bbs, int nbbs, gcov_type num,
 935                                  gcov_type den)
 936 {
 937   int i;
 938   edge e;
 939   gcov_type fraction = RDIV (num * 65536, den);
 940
 941   gcc_assert (fraction >= 0);
 942
 943   if (num < MAX_SAFE_MULTIPLIER)
 944     for (i = 0; i < nbbs; i++)
 945       {
 946         edge_iterator ei;
 947         bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
 948         if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
 949           bbs[i]->count = RDIV (bbs[i]->count * num, den);
 950         else
 951           bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
 952         FOR_EACH_EDGE (e, ei, bbs[i]->succs)
 953           if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
 954             e->count = RDIV (e->count * num, den);
 955           else
 956             e->count = RDIV (e->count * fraction, 65536);
 957       }
 958    else
 959     for (i = 0; i < nbbs; i++)
 960       {
 961         edge_iterator ei;
 962         if (sizeof (gcov_type) > sizeof (int))
 963           bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
 964         else
 965           bbs[i]->frequency = RDIV (bbs[i]->frequency * fraction, 65536);
 966         bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
 967         FOR_EACH_EDGE (e, ei, bbs[i]->succs)
 968           e->count = RDIV (e->count * fraction, 65536);
 969       }
 970 }
 971
 972 /* Data structures used to maintain mapping between basic blocks and
 973    copies.  */
 974 static htab_t bb_original;
 975 static htab_t bb_copy;
 976
 977 /* And between loops and copies.  */
 978 static htab_t loop_copy;
 979 static alloc_pool original_copy_bb_pool;
 980
 981 struct htab_bb_copy_original_entry
 982 {
 983   /* Block we are attaching info to.  */
 984   int index1;
 985   /* Index of original or copy (depending on the hashtable) */
 986   int index2;
 987 };
 988
 989 static hashval_t
 990 bb_copy_original_hash (const void *p)
 991 {
 992   const struct htab_bb_copy_original_entry *data
 993     = ((const struct htab_bb_copy_original_entry *)p);
 994
 995   return data->index1;
 996 }
 997 static int
 998 bb_copy_original_eq (const void *p, const void *q)
 999 {
1000   const struct htab_bb_copy_original_entry *data
1001     = ((const struct htab_bb_copy_original_entry *)p);
1002   const struct htab_bb_copy_original_entry *data2
1003     = ((const struct htab_bb_copy_original_entry *)q);
1004
1005   return data->index1 == data2->index1;
1006 }
1007
1008 /* Initialize the data structures to maintain mapping between blocks
1009    and its copies.  */
1010 void
1011 initialize_original_copy_tables (void)
1012 {
1013   gcc_assert (!original_copy_bb_pool);
1014   original_copy_bb_pool
1015     = create_alloc_pool ("original_copy",
1016                          sizeof (struct htab_bb_copy_original_entry), 10);
1017   bb_original = htab_create (10, bb_copy_original_hash,
1018                              bb_copy_original_eq, NULL);
1019   bb_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1020   loop_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1021 }
1022
1023 /* Free the data structures to maintain mapping between blocks and
1024    its copies.  */
1025 void
1026 free_original_copy_tables (void)
1027 {
1028   gcc_assert (original_copy_bb_pool);
1029   htab_delete (bb_copy);
1030   htab_delete (bb_original);
1031   htab_delete (loop_copy);
1032   free_alloc_pool (original_copy_bb_pool);
1033   bb_copy = NULL;
1034   bb_original = NULL;
1035   loop_copy = NULL;
1036   original_copy_bb_pool = NULL;
1037 }
1038
1039 /* Removes the value associated with OBJ from table TAB.  */
1040
1041 static void
1042 copy_original_table_clear (htab_t tab, unsigned obj)
1043 {
1044   void **slot;
1045   struct htab_bb_copy_original_entry key, *elt;
1046
1047   if (!original_copy_bb_pool)
1048     return;
1049
1050   key.index1 = obj;
1051   slot = htab_find_slot (tab, &key, NO_INSERT);
1052   if (!slot)
1053     return;
1054
1055   elt = (struct htab_bb_copy_original_entry *) *slot;
1056   htab_clear_slot (tab, slot);
1057   pool_free (original_copy_bb_pool, elt);
1058 }
1059
1060 /* Sets the value associated with OBJ in table TAB to VAL.
1061    Do nothing when data structures are not initialized.  */
1062
1063 static void
1064 copy_original_table_set (htab_t tab, unsigned obj, unsigned val)
1065 {
1066   struct htab_bb_copy_original_entry **slot;
1067   struct htab_bb_copy_original_entry key;
1068
1069   if (!original_copy_bb_pool)
1070     return;
1071
1072   key.index1 = obj;
1073   slot = (struct htab_bb_copy_original_entry **)
1074                 htab_find_slot (tab, &key, INSERT);
1075   if (!*slot)
1076     {
1077       *slot = (struct htab_bb_copy_original_entry *)
1078                 pool_alloc (original_copy_bb_pool);
1079       (*slot)->index1 = obj;
1080     }
1081   (*slot)->index2 = val;
1082 }
1083
1084 /* Set original for basic block.  Do nothing when data structures are not
1085    initialized so passes not needing this don't need to care.  */
1086 void
1087 set_bb_original (basic_block bb, basic_block original)
1088 {
1089   copy_original_table_set (bb_original, bb->index, original->index);
1090 }
1091
1092 /* Get the original basic block.  */
1093 basic_block
1094 get_bb_original (basic_block bb)
1095 {
1096   struct htab_bb_copy_original_entry *entry;
1097   struct htab_bb_copy_original_entry key;
1098
1099   gcc_assert (original_copy_bb_pool);
1100
1101   key.index1 = bb->index;
1102   entry = (struct htab_bb_copy_original_entry *) htab_find (bb_original, &key);
1103   if (entry)
1104     return BASIC_BLOCK (entry->index2);
1105   else
1106     return NULL;
1107 }
1108
1109 /* Set copy for basic block.  Do nothing when data structures are not
1110    initialized so passes not needing this don't need to care.  */
1111 void
1112 set_bb_copy (basic_block bb, basic_block copy)
1113 {
1114   copy_original_table_set (bb_copy, bb->index, copy->index);
1115 }
1116
1117 /* Get the copy of basic block.  */
1118 basic_block
1119 get_bb_copy (basic_block bb)
1120 {
1121   struct htab_bb_copy_original_entry *entry;
1122   struct htab_bb_copy_original_entry key;
1123
1124   gcc_assert (original_copy_bb_pool);
1125
1126   key.index1 = bb->index;
1127   entry = (struct htab_bb_copy_original_entry *) htab_find (bb_copy, &key);
1128   if (entry)
1129     return BASIC_BLOCK (entry->index2);
1130   else
1131     return NULL;
1132 }
1133
1134 /* Set copy for LOOP to COPY.  Do nothing when data structures are not
1135    initialized so passes not needing this don't need to care.  */
1136
1137 void
1138 set_loop_copy (struct loop *loop, struct loop *copy)
1139 {
1140   if (!copy)
1141     copy_original_table_clear (loop_copy, loop->num);
1142   else
1143     copy_original_table_set (loop_copy, loop->num, copy->num);
1144 }
1145
1146 /* Get the copy of LOOP.  */
1147
1148 struct loop *
1149 get_loop_copy (struct loop *loop)
1150 {
1151   struct htab_bb_copy_original_entry *entry;
1152   struct htab_bb_copy_original_entry key;
1153
1154   gcc_assert (original_copy_bb_pool);
1155
1156   key.index1 = loop->num;
1157   entry = (struct htab_bb_copy_original_entry *) htab_find (loop_copy, &key);
1158   if (entry)
1159     return get_loop (entry->index2);
1160   else
1161     return NULL;
1162 }