gcc/cfg.cc

   1 /* Control flow graph manipulation code for GNU compiler.
   2    Copyright (C) 1987-2022 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   if (do_details && LOCATION_LOCUS (e->goto_locus) > BUILTINS_LOCATION)
 560     fprintf (file, " %s:%d:%d", LOCATION_FILE (e->goto_locus),
 561              LOCATION_LINE (e->goto_locus), LOCATION_COLUMN (e->goto_locus));
 562 }
 563
 564 DEBUG_FUNCTION void
 565 debug (edge_def &ref)
 566 {
 567   fprintf (stderr, "<edge (%d -> %d)>\n",
 568            ref.src->index, ref.dest->index);
 569   dump_edge_info (stderr, &ref, TDF_DETAILS, false);
 570   fprintf (stderr, "\n");
 571 }
 572
 573 DEBUG_FUNCTION void
 574 debug (edge_def *ptr)
 575 {
 576   if (ptr)
 577     debug (*ptr);
 578   else
 579     fprintf (stderr, "<nil>\n");
 580 }
 581
 582 static void
 583 debug_slim (edge e)
 584 {
 585   fprintf (stderr, "<edge 0x%p (%d -> %d)>", (void *) e,
 586            e->src->index, e->dest->index);
 587 }
 588
 589 DEFINE_DEBUG_VEC (edge)
 590 DEFINE_DEBUG_HASH_SET (edge)
 591 \f
 592 /* Simple routines to easily allocate AUX fields of basic blocks.  */
 593
 594 static struct obstack block_aux_obstack;
 595 static void *first_block_aux_obj = 0;
 596 static struct obstack edge_aux_obstack;
 597 static void *first_edge_aux_obj = 0;
 598
 599 /* Allocate a memory block of SIZE as BB->aux.  The obstack must
 600    be first initialized by alloc_aux_for_blocks.  */
 601
 602 static void
 603 alloc_aux_for_block (basic_block bb, int size)
 604 {
 605   /* Verify that aux field is clear.  */
 606   gcc_assert (!bb->aux && first_block_aux_obj);
 607   bb->aux = obstack_alloc (&block_aux_obstack, size);
 608   memset (bb->aux, 0, size);
 609 }
 610
 611 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
 612    alloc_aux_for_block for each basic block.  */
 613
 614 void
 615 alloc_aux_for_blocks (int size)
 616 {
 617   static int initialized;
 618
 619   if (!initialized)
 620     {
 621       gcc_obstack_init (&block_aux_obstack);
 622       initialized = 1;
 623     }
 624   else
 625     /* Check whether AUX data are still allocated.  */
 626     gcc_assert (!first_block_aux_obj);
 627
 628   first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
 629   if (size)
 630     {
 631       basic_block bb;
 632
 633       FOR_ALL_BB_FN (bb, cfun)
 634         alloc_aux_for_block (bb, size);
 635     }
 636 }
 637
 638 /* Clear AUX pointers of all blocks.  */
 639
 640 void
 641 clear_aux_for_blocks (void)
 642 {
 643   basic_block bb;
 644
 645   FOR_ALL_BB_FN (bb, cfun)
 646     bb->aux = NULL;
 647 }
 648
 649 /* Free data allocated in block_aux_obstack and clear AUX pointers
 650    of all blocks.  */
 651
 652 void
 653 free_aux_for_blocks (void)
 654 {
 655   gcc_assert (first_block_aux_obj);
 656   obstack_free (&block_aux_obstack, first_block_aux_obj);
 657   first_block_aux_obj = NULL;
 658
 659   clear_aux_for_blocks ();
 660 }
 661
 662 /* Allocate a memory edge of SIZE as E->aux.  The obstack must
 663    be first initialized by alloc_aux_for_edges.  */
 664
 665 void
 666 alloc_aux_for_edge (edge e, int size)
 667 {
 668   /* Verify that aux field is clear.  */
 669   gcc_assert (!e->aux && first_edge_aux_obj);
 670   e->aux = obstack_alloc (&edge_aux_obstack, size);
 671   memset (e->aux, 0, size);
 672 }
 673
 674 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
 675    alloc_aux_for_edge for each basic edge.  */
 676
 677 void
 678 alloc_aux_for_edges (int size)
 679 {
 680   static int initialized;
 681
 682   if (!initialized)
 683     {
 684       gcc_obstack_init (&edge_aux_obstack);
 685       initialized = 1;
 686     }
 687   else
 688     /* Check whether AUX data are still allocated.  */
 689     gcc_assert (!first_edge_aux_obj);
 690
 691   first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
 692   if (size)
 693     {
 694       basic_block bb;
 695
 696       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
 697                       EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
 698         {
 699           edge e;
 700           edge_iterator ei;
 701
 702           FOR_EACH_EDGE (e, ei, bb->succs)
 703             alloc_aux_for_edge (e, size);
 704         }
 705     }
 706 }
 707
 708 /* Clear AUX pointers of all edges.  */
 709
 710 void
 711 clear_aux_for_edges (void)
 712 {
 713   basic_block bb;
 714   edge e;
 715
 716   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
 717                   EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
 718     {
 719       edge_iterator ei;
 720       FOR_EACH_EDGE (e, ei, bb->succs)
 721         e->aux = NULL;
 722     }
 723 }
 724
 725 /* Free data allocated in edge_aux_obstack and clear AUX pointers
 726    of all edges.  */
 727
 728 void
 729 free_aux_for_edges (void)
 730 {
 731   gcc_assert (first_edge_aux_obj);
 732   obstack_free (&edge_aux_obstack, first_edge_aux_obj);
 733   first_edge_aux_obj = NULL;
 734
 735   clear_aux_for_edges ();
 736 }
 737
 738 DEBUG_FUNCTION void
 739 debug_bb (basic_block bb)
 740 {
 741   debug_bb (bb, dump_flags);
 742 }
 743
 744 DEBUG_FUNCTION basic_block
 745 debug_bb_n (int n)
 746 {
 747   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, n);
 748   debug_bb (bb);
 749   return bb;
 750 }
 751
 752 /* Print BB with specified FLAGS.  */
 753
 754 DEBUG_FUNCTION void
 755 debug_bb (basic_block bb, dump_flags_t flags)
 756 {
 757   dump_bb (stderr, bb, 0, flags);
 758 }
 759
 760 /* Print basic block numbered N with specified FLAGS.  */
 761
 762 DEBUG_FUNCTION basic_block
 763 debug_bb_n (int n, dump_flags_t flags)
 764 {
 765   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, n);
 766   debug_bb (bb, flags);
 767   return bb;
 768 }
 769
 770 /* Dumps cfg related information about basic block BB to OUTF.
 771    If HEADER is true, dump things that appear before the instructions
 772    contained in BB.  If FOOTER is true, dump things that appear after.
 773    Flags are the TDF_* masks as documented in dumpfile.h.
 774    NB: With TDF_DETAILS, it is assumed that cfun is available, so
 775    that maybe_hot_bb_p and probably_never_executed_bb_p don't ICE.  */
 776
 777 void
 778 dump_bb_info (FILE *outf, basic_block bb, int indent, dump_flags_t flags,
 779               bool do_header, bool do_footer)
 780 {
 781   edge_iterator ei;
 782   edge e;
 783   static const char * const bb_bitnames[] =
 784     {
 785 #define DEF_BASIC_BLOCK_FLAG(NAME,IDX) #NAME ,
 786 #include "cfg-flags.def"
 787       NULL
 788 #undef DEF_BASIC_BLOCK_FLAG
 789     };
 790   const unsigned n_bitnames = ARRAY_SIZE (bb_bitnames);
 791   bool first;
 792   char *s_indent = (char *) alloca ((size_t) indent + 1);
 793   memset ((void *) s_indent, ' ', (size_t) indent);
 794   s_indent[indent] = '\0';
 795
 796   gcc_assert (bb->flags <= BB_ALL_FLAGS);
 797
 798   if (do_header)
 799     {
 800       unsigned i;
 801
 802       fputs (";; ", outf);
 803       fprintf (outf, "%sbasic block %d, loop depth %d",
 804                s_indent, bb->index, bb_loop_depth (bb));
 805       if (flags & TDF_DETAILS)
 806         {
 807           struct function *fun = DECL_STRUCT_FUNCTION (current_function_decl);
 808           if (bb->count.initialized_p ())
 809             {
 810               fputs (", count ", outf);
 811               bb->count.dump (outf);
 812             }
 813           if (maybe_hot_bb_p (fun, bb))
 814             fputs (", maybe hot", outf);
 815           if (probably_never_executed_bb_p (fun, bb))
 816             fputs (", probably never executed", outf);
 817         }
 818       fputc ('\n', outf);
 819
 820       if (flags & TDF_DETAILS)
 821         {
 822           check_bb_profile (bb, outf, indent);
 823           fputs (";; ", outf);
 824           fprintf (outf, "%s prev block ", s_indent);
 825           if (bb->prev_bb)
 826             fprintf (outf, "%d", bb->prev_bb->index);
 827           else
 828             fprintf (outf, "(nil)");
 829           fprintf (outf, ", next block ");
 830           if (bb->next_bb)
 831             fprintf (outf, "%d", bb->next_bb->index);
 832           else
 833             fprintf (outf, "(nil)");
 834
 835           fputs (", flags:", outf);
 836           first = true;
 837           for (i = 0; i < n_bitnames; i++)
 838             if (bb->flags & (1 << i))
 839               {
 840                 if (first)
 841                   fputs (" (", outf);
 842                 else
 843                   fputs (", ", outf);
 844                 first = false;
 845                 fputs (bb_bitnames[i], outf);
 846               }
 847           if (!first)
 848             fputc (')', outf);
 849           fputc ('\n', outf);
 850         }
 851
 852       fputs (";; ", outf);
 853       fprintf (outf, "%s pred:      ", s_indent);
 854       first = true;
 855       FOR_EACH_EDGE (e, ei, bb->preds)
 856         {
 857           if (! first)
 858             {
 859               fputs (";; ", outf);
 860               fprintf (outf, "%s            ", s_indent);
 861             }
 862           first = false;
 863           dump_edge_info (outf, e, flags, 0);
 864           fputc ('\n', outf);
 865         }
 866       if (first)
 867         fputc ('\n', outf);
 868     }
 869
 870   if (do_footer)
 871     {
 872       fputs (";; ", outf);
 873       fprintf (outf, "%s succ:      ", s_indent);
 874       first = true;
 875       FOR_EACH_EDGE (e, ei, bb->succs)
 876         {
 877           if (! first)
 878             {
 879               fputs (";; ", outf);
 880               fprintf (outf, "%s            ", s_indent);
 881             }
 882           first = false;
 883           dump_edge_info (outf, e, flags, 1);
 884           fputc ('\n', outf);
 885         }
 886       if (first)
 887         fputc ('\n', outf);
 888     }
 889 }
 890
 891 /* Dumps a brief description of cfg to FILE.  */
 892
 893 void
 894 brief_dump_cfg (FILE *file, dump_flags_t flags)
 895 {
 896   basic_block bb;
 897
 898   FOR_EACH_BB_FN (bb, cfun)
 899     {
 900       dump_bb_info (file, bb, 0, flags & TDF_DETAILS, true, true);
 901     }
 902 }
 903
 904 /* An edge originally destinating BB of COUNT has been proved to
 905    leave the block by TAKEN_EDGE.  Update profile of BB such that edge E can be
 906    redirected to destination of TAKEN_EDGE.
 907
 908    This function may leave the profile inconsistent in the case TAKEN_EDGE
 909    frequency or count is believed to be lower than COUNT
 910    respectively.  */
 911 void
 912 update_bb_profile_for_threading (basic_block bb,
 913                                  profile_count count, edge taken_edge)
 914 {
 915   edge c;
 916   profile_probability prob;
 917   edge_iterator ei;
 918
 919   if (bb->count < count)
 920     {
 921       if (dump_file)
 922         fprintf (dump_file, "bb %i count became negative after threading",
 923                  bb->index);
 924     }
 925   bb->count -= count;
 926
 927   /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
 928      Watch for overflows.  */
 929   if (bb->count.nonzero_p ())
 930     prob = count.probability_in (bb->count);
 931   else
 932     prob = profile_probability::never ();
 933   if (prob > taken_edge->probability)
 934     {
 935       if (dump_file)
 936         {
 937           fprintf (dump_file, "Jump threading proved probability of edge "
 938                    "%i->%i too small (it is ",
 939                    taken_edge->src->index, taken_edge->dest->index);
 940           taken_edge->probability.dump (dump_file);
 941           fprintf (dump_file, " should be ");
 942           prob.dump (dump_file);
 943           fprintf (dump_file, ")\n");
 944         }
 945       prob = taken_edge->probability.apply_scale (6, 8);
 946     }
 947
 948   /* Now rescale the probabilities.  */
 949   taken_edge->probability -= prob;
 950   prob = prob.invert ();
 951   if (prob == profile_probability::never ())
 952     {
 953       if (dump_file)
 954         fprintf (dump_file, "Edge probabilities of bb %i has been reset, "
 955                  "count of block should end up being 0, it is non-zero\n",
 956                  bb->index);
 957       EDGE_SUCC (bb, 0)->probability = profile_probability::guessed_always ();
 958       ei = ei_start (bb->succs);
 959       ei_next (&ei);
 960       for (; (c = ei_safe_edge (ei)); ei_next (&ei))
 961         c->probability = profile_probability::guessed_never ();
 962     }
 963   else if (!(prob == profile_probability::always ()))
 964     {
 965       FOR_EACH_EDGE (c, ei, bb->succs)
 966         c->probability /= prob;
 967     }
 968
 969   gcc_assert (bb == taken_edge->src);
 970 }
 971
 972 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
 973    by NUM/DEN, in profile_count arithmetic.  More accurate than previous
 974    function but considerably slower.  */
 975 void
 976 scale_bbs_frequencies_profile_count (basic_block *bbs, int nbbs,
 977                                      profile_count num, profile_count den)
 978 {
 979   int i;
 980   if (num == profile_count::zero () || den.nonzero_p ())
 981     for (i = 0; i < nbbs; i++)
 982       bbs[i]->count = bbs[i]->count.apply_scale (num, den);
 983 }
 984
 985 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
 986    by NUM/DEN, in profile_count arithmetic.  More accurate than previous
 987    function but considerably slower.  */
 988 void
 989 scale_bbs_frequencies (basic_block *bbs, int nbbs,
 990                        profile_probability p)
 991 {
 992   int i;
 993
 994   for (i = 0; i < nbbs; i++)
 995     bbs[i]->count = bbs[i]->count.apply_probability (p);
 996 }
 997
 998 /* Data structures used to maintain mapping between basic blocks and
 999    copies.  */
1000 typedef hash_map<int_hash<int, -1, -2>, int> copy_map_t;
1001 static copy_map_t *bb_original;
1002 static copy_map_t *bb_copy;
1003
1004 /* And between loops and copies.  */
1005 static copy_map_t *loop_copy;
1006
1007 /* Initialize the data structures to maintain mapping between blocks
1008    and its copies.  */
1009 void
1010 initialize_original_copy_tables (void)
1011 {
1012   bb_original = new copy_map_t (10);
1013   bb_copy = new copy_map_t (10);
1014   loop_copy = new copy_map_t (10);
1015 }
1016
1017 /* Reset the data structures to maintain mapping between blocks and
1018    its copies.  */
1019
1020 void
1021 reset_original_copy_tables (void)
1022 {
1023   bb_original->empty ();
1024   bb_copy->empty ();
1025   loop_copy->empty ();
1026 }
1027
1028 /* Free the data structures to maintain mapping between blocks and
1029    its copies.  */
1030 void
1031 free_original_copy_tables (void)
1032 {
1033   delete bb_copy;
1034   bb_copy = NULL;
1035   delete bb_original;
1036   bb_original = NULL;
1037   delete loop_copy;
1038   loop_copy = NULL;
1039 }
1040
1041 /* Return true iff we have had a call to initialize_original_copy_tables
1042    without a corresponding call to free_original_copy_tables.  */
1043
1044 bool
1045 original_copy_tables_initialized_p (void)
1046 {
1047   return bb_copy != NULL;
1048 }
1049
1050 /* Removes the value associated with OBJ from table TAB.  */
1051
1052 static void
1053 copy_original_table_clear (copy_map_t *tab, unsigned obj)
1054 {
1055   if (!original_copy_tables_initialized_p ())
1056     return;
1057
1058   tab->remove (obj);
1059 }
1060
1061 /* Sets the value associated with OBJ in table TAB to VAL.
1062    Do nothing when data structures are not initialized.  */
1063
1064 static void
1065 copy_original_table_set (copy_map_t *tab,
1066                          unsigned obj, unsigned val)
1067 {
1068   if (!original_copy_tables_initialized_p ())
1069     return;
1070
1071   tab->put (obj, val);
1072 }
1073
1074 /* Set original for basic block.  Do nothing when data structures are not
1075    initialized so passes not needing this don't need to care.  */
1076 void
1077 set_bb_original (basic_block bb, basic_block original)
1078 {
1079   copy_original_table_set (bb_original, bb->index, original->index);
1080 }
1081
1082 /* Get the original basic block.  */
1083 basic_block
1084 get_bb_original (basic_block bb)
1085 {
1086   gcc_assert (original_copy_tables_initialized_p ());
1087
1088   int *entry = bb_original->get (bb->index);
1089   if (entry)
1090     return BASIC_BLOCK_FOR_FN (cfun, *entry);
1091   else
1092     return NULL;
1093 }
1094
1095 /* Set copy for basic block.  Do nothing when data structures are not
1096    initialized so passes not needing this don't need to care.  */
1097 void
1098 set_bb_copy (basic_block bb, basic_block copy)
1099 {
1100   copy_original_table_set (bb_copy, bb->index, copy->index);
1101 }
1102
1103 /* Get the copy of basic block.  */
1104 basic_block
1105 get_bb_copy (basic_block bb)
1106 {
1107   gcc_assert (original_copy_tables_initialized_p ());
1108
1109   int *entry = bb_copy->get (bb->index);
1110   if (entry)
1111     return BASIC_BLOCK_FOR_FN (cfun, *entry);
1112   else
1113     return NULL;
1114 }
1115
1116 /* Set copy for LOOP to COPY.  Do nothing when data structures are not
1117    initialized so passes not needing this don't need to care.  */
1118
1119 void
1120 set_loop_copy (class loop *loop, class loop *copy)
1121 {
1122   if (!copy)
1123     copy_original_table_clear (loop_copy, loop->num);
1124   else
1125     copy_original_table_set (loop_copy, loop->num, copy->num);
1126 }
1127
1128 /* Get the copy of LOOP.  */
1129
1130 class loop *
1131 get_loop_copy (class loop *loop)
1132 {
1133   gcc_assert (original_copy_tables_initialized_p ());
1134
1135   int *entry = loop_copy->get (loop->num);
1136   if (entry)
1137     return get_loop (cfun, *entry);
1138   else
1139     return NULL;
1140 }