gcc/cfg.c

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