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 \f
  48 #include "config.h"
  49 #include "system.h"
  50 #include "coretypes.h"
  51 #include "tm.h"
  52 #include "tree.h"
  53 #include "rtl.h"
  54 #include "hard-reg-set.h"
  55 #include "regs.h"
  56 #include "flags.h"
  57 #include "output.h"
  58 #include "function.h"
  59 #include "except.h"
  60 #include "diagnostic-core.h"
  61 #include "tm_p.h"
  62 #include "obstack.h"
  63 #include "timevar.h"
  64 #include "tree-pass.h"
  65 #include "ggc.h"
  66 #include "hashtab.h"
  67 #include "alloc-pool.h"
  68 #include "df.h"
  69 #include "cfgloop.h"
  70 #include "tree-flow.h"
  71
  72 /* The obstack on which the flow graph components are allocated.  */
  73
  74 struct bitmap_obstack reg_obstack;
  75
  76 void debug_flow_info (void);
  77 static void free_edge (edge);
  78 \f
  79 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
  80
  81 /* Called once at initialization time.  */
  82
  83 void
  84 init_flow (struct function *the_fun)
  85 {
  86   if (!the_fun->cfg)
  87     the_fun->cfg = ggc_alloc_cleared_control_flow_graph ();
  88   n_edges_for_function (the_fun) = 0;
  89   ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)
  90     = ggc_alloc_cleared_basic_block_def ();
  91   ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)->index = ENTRY_BLOCK;
  92   EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)
  93     = ggc_alloc_cleared_basic_block_def ();
  94   EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)->index = EXIT_BLOCK;
  95   ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)->next_bb
  96     = EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun);
  97   EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)->prev_bb
  98     = ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun);
  99 }
 100 \f
 101 /* Helper function for remove_edge and clear_edges.  Frees edge structure
 102    without actually unlinking it from the pred/succ lists.  */
 103
 104 static void
 105 free_edge (edge e ATTRIBUTE_UNUSED)
 106 {
 107   n_edges--;
 108   ggc_free (e);
 109 }
 110
 111 /* Free the memory associated with the edge structures.  */
 112
 113 void
 114 clear_edges (void)
 115 {
 116   basic_block bb;
 117   edge e;
 118   edge_iterator ei;
 119
 120   FOR_EACH_BB (bb)
 121     {
 122       FOR_EACH_EDGE (e, ei, bb->succs)
 123         free_edge (e);
 124       VEC_truncate (edge, bb->succs, 0);
 125       VEC_truncate (edge, bb->preds, 0);
 126     }
 127
 128   FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
 129     free_edge (e);
 130   VEC_truncate (edge, EXIT_BLOCK_PTR->preds, 0);
 131   VEC_truncate (edge, ENTRY_BLOCK_PTR->succs, 0);
 132
 133   gcc_assert (!n_edges);
 134 }
 135 \f
 136 /* Allocate memory for basic_block.  */
 137
 138 basic_block
 139 alloc_block (void)
 140 {
 141   basic_block bb;
 142   bb = ggc_alloc_cleared_basic_block_def ();
 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 (ENTRY_BLOCK, ENTRY_BLOCK_PTR);
 173   SET_BASIC_BLOCK (EXIT_BLOCK, EXIT_BLOCK_PTR);
 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 (bb)
 183         {
 184           SET_BASIC_BLOCK (i, bb);
 185           bb->index = i;
 186           i++;
 187         }
 188       gcc_assert (i == n_basic_blocks);
 189
 190       for (; i < last_basic_block; i++)
 191         SET_BASIC_BLOCK (i, NULL);
 192     }
 193   last_basic_block = n_basic_blocks;
 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 (b->index, NULL);
 203   n_basic_blocks--;
 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 should
 208      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 (edge, gc, 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 (edge, gc, 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           VEC_unordered_remove (edge, src->succs, ei.index);
 245           return;
 246         }
 247       else
 248         ei_next (&ei);
 249     }
 250
 251   df_mark_solutions_dirty ();
 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   VEC_unordered_remove (edge, dest->preds, 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_alloc_cleared_edge_def ();
 281   n_edges++;
 282
 283   e->src = src;
 284   e->dest = dst;
 285   e->flags = flags;
 286
 287   connect_src (e);
 288   connect_dest (e);
 289
 290   execute_on_growing_pred (e);
 291   return e;
 292 }
 293
 294 /* Create an edge connecting SRC and DST with FLAGS optionally using
 295    edge cache CACHE.  Return the new edge, NULL if already exist.  */
 296
 297 edge
 298 cached_make_edge (sbitmap edge_cache, basic_block src, basic_block dst, int flags)
 299 {
 300   if (edge_cache == NULL
 301       || src == ENTRY_BLOCK_PTR
 302       || dst == EXIT_BLOCK_PTR)
 303     return make_edge (src, dst, flags);
 304
 305   /* Does the requested edge already exist?  */
 306   if (! TEST_BIT (edge_cache, dst->index))
 307     {
 308       /* The edge does not exist.  Create one and update the
 309          cache.  */
 310       SET_BIT (edge_cache, dst->index);
 311       return unchecked_make_edge (src, dst, flags);
 312     }
 313
 314   /* At this point, we know that the requested edge exists.  Adjust
 315      flags if necessary.  */
 316   if (flags)
 317     {
 318       edge e = find_edge (src, dst);
 319       e->flags |= flags;
 320     }
 321
 322   return NULL;
 323 }
 324
 325 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
 326    created edge or NULL if already exist.  */
 327
 328 edge
 329 make_edge (basic_block src, basic_block dest, int flags)
 330 {
 331   edge e = find_edge (src, dest);
 332
 333   /* Make sure we don't add duplicate edges.  */
 334   if (e)
 335     {
 336       e->flags |= flags;
 337       return NULL;
 338     }
 339
 340   return unchecked_make_edge (src, dest, flags);
 341 }
 342
 343 /* Create an edge connecting SRC to DEST and set probability by knowing
 344    that it is the single edge leaving SRC.  */
 345
 346 edge
 347 make_single_succ_edge (basic_block src, basic_block dest, int flags)
 348 {
 349   edge e = make_edge (src, dest, flags);
 350
 351   e->probability = REG_BR_PROB_BASE;
 352   e->count = src->count;
 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   /* This is probably not needed, but it doesn't hurt.  */
 368   redirect_edge_var_map_clear (e);
 369
 370   free_edge (e);
 371 }
 372
 373 /* Redirect an edge's successor from one block to another.  */
 374
 375 void
 376 redirect_edge_succ (edge e, basic_block new_succ)
 377 {
 378   execute_on_shrinking_pred (e);
 379
 380   disconnect_dest (e);
 381
 382   e->dest = new_succ;
 383
 384   /* Reconnect the edge to the new successor block.  */
 385   connect_dest (e);
 386
 387   execute_on_growing_pred (e);
 388 }
 389
 390 /* Like previous but avoid possible duplicate edge.  */
 391
 392 edge
 393 redirect_edge_succ_nodup (edge e, basic_block new_succ)
 394 {
 395   edge s;
 396
 397   s = find_edge (e->src, new_succ);
 398   if (s && s != e)
 399     {
 400       s->flags |= e->flags;
 401       s->probability += e->probability;
 402       if (s->probability > REG_BR_PROB_BASE)
 403         s->probability = REG_BR_PROB_BASE;
 404       s->count += e->count;
 405       redirect_edge_var_map_dup (s, e);
 406       remove_edge (e);
 407       e = s;
 408     }
 409   else
 410     redirect_edge_succ (e, new_succ);
 411
 412   return e;
 413 }
 414
 415 /* Redirect an edge's predecessor from one block to another.  */
 416
 417 void
 418 redirect_edge_pred (edge e, basic_block new_pred)
 419 {
 420   disconnect_src (e);
 421
 422   e->src = new_pred;
 423
 424   /* Reconnect the edge to the new predecessor block.  */
 425   connect_src (e);
 426 }
 427
 428 /* Clear all basic block flags, with the exception of partitioning and
 429    setjmp_target.  */
 430 void
 431 clear_bb_flags (void)
 432 {
 433   basic_block bb;
 434
 435   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 436     bb->flags = (BB_PARTITION (bb)
 437                  | (bb->flags & (BB_DISABLE_SCHEDULE + BB_RTL + BB_NON_LOCAL_GOTO_TARGET)));
 438 }
 439 \f
 440 /* Check the consistency of profile information.  We can't do that
 441    in verify_flow_info, as the counts may get invalid for incompletely
 442    solved graphs, later eliminating of conditionals or roundoff errors.
 443    It is still practical to have them reported for debugging of simple
 444    testcases.  */
 445 void
 446 check_bb_profile (basic_block bb, FILE * file)
 447 {
 448   edge e;
 449   int sum = 0;
 450   gcov_type lsum;
 451   edge_iterator ei;
 452
 453   if (profile_status == PROFILE_ABSENT)
 454     return;
 455
 456   if (bb != EXIT_BLOCK_PTR)
 457     {
 458       FOR_EACH_EDGE (e, ei, bb->succs)
 459         sum += e->probability;
 460       if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
 461         fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
 462                  sum * 100.0 / REG_BR_PROB_BASE);
 463       lsum = 0;
 464       FOR_EACH_EDGE (e, ei, bb->succs)
 465         lsum += e->count;
 466       if (EDGE_COUNT (bb->succs)
 467           && (lsum - bb->count > 100 || lsum - bb->count < -100))
 468         fprintf (file, "Invalid sum of outgoing counts %i, should be %i\n",
 469                  (int) lsum, (int) bb->count);
 470     }
 471   if (bb != ENTRY_BLOCK_PTR)
 472     {
 473       sum = 0;
 474       FOR_EACH_EDGE (e, ei, bb->preds)
 475         sum += EDGE_FREQUENCY (e);
 476       if (abs (sum - bb->frequency) > 100)
 477         fprintf (file,
 478                  "Invalid sum of incoming frequencies %i, should be %i\n",
 479                  sum, bb->frequency);
 480       lsum = 0;
 481       FOR_EACH_EDGE (e, ei, bb->preds)
 482         lsum += e->count;
 483       if (lsum - bb->count > 100 || lsum - bb->count < -100)
 484         fprintf (file, "Invalid sum of incoming counts %i, should be %i\n",
 485                  (int) lsum, (int) bb->count);
 486     }
 487 }
 488 \f
 489 /* Write information about registers and basic blocks into FILE.
 490    This is part of making a debugging dump.  */
 491
 492 void
 493 dump_regset (regset r, FILE *outf)
 494 {
 495   unsigned i;
 496   reg_set_iterator rsi;
 497
 498   if (r == NULL)
 499     {
 500       fputs (" (nil)", outf);
 501       return;
 502     }
 503
 504   EXECUTE_IF_SET_IN_REG_SET (r, 0, i, rsi)
 505     {
 506       fprintf (outf, " %d", i);
 507       if (i < FIRST_PSEUDO_REGISTER)
 508         fprintf (outf, " [%s]",
 509                  reg_names[i]);
 510     }
 511 }
 512
 513 /* Print a human-readable representation of R on the standard error
 514    stream.  This function is designed to be used from within the
 515    debugger.  */
 516
 517 DEBUG_FUNCTION void
 518 debug_regset (regset r)
 519 {
 520   dump_regset (r, stderr);
 521   putc ('\n', stderr);
 522 }
 523
 524 /* Emit basic block information for BB.  HEADER is true if the user wants
 525    the generic information and the predecessors, FOOTER is true if they want
 526    the successors.  FLAGS is the dump flags of interest; TDF_DETAILS emit
 527    global register liveness information.  PREFIX is put in front of every
 528    line.  The output is emitted to FILE.  */
 529 void
 530 dump_bb_info (basic_block bb, bool header, bool footer, int flags,
 531               const char *prefix, FILE *file)
 532 {
 533   edge e;
 534   edge_iterator ei;
 535
 536   if (header)
 537     {
 538       fprintf (file, "\n%sBasic block %d ", prefix, bb->index);
 539       if (bb->prev_bb)
 540         fprintf (file, ", prev %d", bb->prev_bb->index);
 541       if (bb->next_bb)
 542         fprintf (file, ", next %d", bb->next_bb->index);
 543       fprintf (file, ", loop_depth %d, count ", bb->loop_depth);
 544       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
 545       fprintf (file, ", freq %i", bb->frequency);
 546       /* Both maybe_hot_bb_p & probably_never_executed_bb_p functions
 547          crash without cfun. */
 548       if (cfun && maybe_hot_bb_p (bb))
 549         fputs (", maybe hot", file);
 550       if (cfun && probably_never_executed_bb_p (bb))
 551         fputs (", probably never executed", file);
 552       if (bb->flags)
 553         {
 554           static const char * const bits[] = {
 555             "new", "reachable", "irr_loop", "superblock", "disable_sched",
 556             "hot_partition", "cold_partition", "duplicated",
 557             "non_local_goto_target", "rtl", "forwarder", "nonthreadable",
 558             "modified"
 559           };
 560           unsigned int flags;
 561
 562           fputs (", flags:", file);
 563           for (flags = bb->flags; flags ; flags &= flags - 1)
 564             {
 565               unsigned i = ctz_hwi (flags);
 566               if (i < ARRAY_SIZE (bits))
 567                 fprintf (file, " %s", bits[i]);
 568               else
 569                 fprintf (file, " <%d>", i);
 570             }
 571         }
 572       fputs (".\n", file);
 573
 574       fprintf (file, "%sPredecessors: ", prefix);
 575       FOR_EACH_EDGE (e, ei, bb->preds)
 576         dump_edge_info (file, e, 0);
 577
 578       if ((flags & TDF_DETAILS)
 579           && (bb->flags & BB_RTL)
 580           && df)
 581         {
 582           putc ('\n', file);
 583           df_dump_top (bb, file);
 584         }
 585    }
 586
 587   if (footer)
 588     {
 589       fprintf (file, "\n%sSuccessors: ", prefix);
 590       FOR_EACH_EDGE (e, ei, bb->succs)
 591         dump_edge_info (file, e, 1);
 592
 593       if ((flags & TDF_DETAILS)
 594           && (bb->flags & BB_RTL)
 595           && df)
 596         {
 597           putc ('\n', file);
 598           df_dump_bottom (bb, file);
 599         }
 600    }
 601
 602   putc ('\n', file);
 603 }
 604
 605 /* Dump the register info to FILE.  */
 606
 607 void
 608 dump_reg_info (FILE *file)
 609 {
 610   unsigned int i, max = max_reg_num ();
 611   if (reload_completed)
 612     return;
 613
 614   if (reg_info_p_size < max)
 615     max = reg_info_p_size;
 616
 617   fprintf (file, "%d registers.\n", max);
 618   for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
 619     {
 620       enum reg_class rclass, altclass;
 621
 622       if (regstat_n_sets_and_refs)
 623         fprintf (file, "\nRegister %d used %d times across %d insns",
 624                  i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
 625       else if (df)
 626         fprintf (file, "\nRegister %d used %d times across %d insns",
 627                  i, DF_REG_USE_COUNT (i) + DF_REG_DEF_COUNT (i), REG_LIVE_LENGTH (i));
 628
 629       if (REG_BASIC_BLOCK (i) >= NUM_FIXED_BLOCKS)
 630         fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
 631       if (regstat_n_sets_and_refs)
 632         fprintf (file, "; set %d time%s", REG_N_SETS (i),
 633                  (REG_N_SETS (i) == 1) ? "" : "s");
 634       else if (df)
 635         fprintf (file, "; set %d time%s", DF_REG_DEF_COUNT (i),
 636                  (DF_REG_DEF_COUNT (i) == 1) ? "" : "s");
 637       if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
 638         fputs ("; user var", file);
 639       if (REG_N_DEATHS (i) != 1)
 640         fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
 641       if (REG_N_CALLS_CROSSED (i) == 1)
 642         fputs ("; crosses 1 call", file);
 643       else if (REG_N_CALLS_CROSSED (i))
 644         fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
 645       if (REG_FREQ_CALLS_CROSSED (i))
 646         fprintf (file, "; crosses call with %d frequency", REG_FREQ_CALLS_CROSSED (i));
 647       if (regno_reg_rtx[i] != NULL
 648           && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
 649         fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
 650
 651       rclass = reg_preferred_class (i);
 652       altclass = reg_alternate_class (i);
 653       if (rclass != GENERAL_REGS || altclass != ALL_REGS)
 654         {
 655           if (altclass == ALL_REGS || rclass == ALL_REGS)
 656             fprintf (file, "; pref %s", reg_class_names[(int) rclass]);
 657           else if (altclass == NO_REGS)
 658             fprintf (file, "; %s or none", reg_class_names[(int) rclass]);
 659           else
 660             fprintf (file, "; pref %s, else %s",
 661                      reg_class_names[(int) rclass],
 662                      reg_class_names[(int) altclass]);
 663         }
 664
 665       if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
 666         fputs ("; pointer", file);
 667       fputs (".\n", file);
 668     }
 669 }
 670
 671
 672 void
 673 dump_flow_info (FILE *file, int flags)
 674 {
 675   basic_block bb;
 676
 677   /* There are no pseudo registers after reload.  Don't dump them.  */
 678   if (reg_info_p_size && (flags & TDF_DETAILS) != 0)
 679     dump_reg_info (file);
 680
 681   fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
 682   FOR_ALL_BB (bb)
 683     {
 684       dump_bb_info (bb, true, true, flags, "", file);
 685       check_bb_profile (bb, file);
 686     }
 687
 688   putc ('\n', file);
 689 }
 690
 691 DEBUG_FUNCTION void
 692 debug_flow_info (void)
 693 {
 694   dump_flow_info (stderr, TDF_DETAILS);
 695 }
 696
 697 void
 698 dump_edge_info (FILE *file, edge e, int do_succ)
 699 {
 700   basic_block side = (do_succ ? e->dest : e->src);
 701   /* both ENTRY_BLOCK_PTR & EXIT_BLOCK_PTR depend upon cfun. */
 702   if (cfun && side == ENTRY_BLOCK_PTR)
 703     fputs (" ENTRY", file);
 704   else if (cfun && side == EXIT_BLOCK_PTR)
 705     fputs (" EXIT", file);
 706   else
 707     fprintf (file, " %d", side->index);
 708
 709   if (e->probability)
 710     fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
 711
 712   if (e->count)
 713     {
 714       fputs (" count:", file);
 715       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
 716     }
 717
 718   if (e->flags)
 719     {
 720       static const char * const bitnames[] = {
 721         "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
 722         "can_fallthru", "irreducible", "sibcall", "loop_exit",
 723         "true", "false", "exec", "crossing", "preserve"
 724       };
 725       int comma = 0;
 726       int i, flags = e->flags;
 727
 728       fputs (" (", file);
 729       for (i = 0; flags; i++)
 730         if (flags & (1 << i))
 731           {
 732             flags &= ~(1 << i);
 733
 734             if (comma)
 735               fputc (',', file);
 736             if (i < (int) ARRAY_SIZE (bitnames))
 737               fputs (bitnames[i], file);
 738             else
 739               fprintf (file, "%d", i);
 740             comma = 1;
 741           }
 742
 743       fputc (')', file);
 744     }
 745 }
 746 \f
 747 /* Simple routines to easily allocate AUX fields of basic blocks.  */
 748
 749 static struct obstack block_aux_obstack;
 750 static void *first_block_aux_obj = 0;
 751 static struct obstack edge_aux_obstack;
 752 static void *first_edge_aux_obj = 0;
 753
 754 /* Allocate a memory block of SIZE as BB->aux.  The obstack must
 755    be first initialized by alloc_aux_for_blocks.  */
 756
 757 static void
 758 alloc_aux_for_block (basic_block bb, int size)
 759 {
 760   /* Verify that aux field is clear.  */
 761   gcc_assert (!bb->aux && first_block_aux_obj);
 762   bb->aux = obstack_alloc (&block_aux_obstack, size);
 763   memset (bb->aux, 0, size);
 764 }
 765
 766 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
 767    alloc_aux_for_block for each basic block.  */
 768
 769 void
 770 alloc_aux_for_blocks (int size)
 771 {
 772   static int initialized;
 773
 774   if (!initialized)
 775     {
 776       gcc_obstack_init (&block_aux_obstack);
 777       initialized = 1;
 778     }
 779   else
 780     /* Check whether AUX data are still allocated.  */
 781     gcc_assert (!first_block_aux_obj);
 782
 783   first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
 784   if (size)
 785     {
 786       basic_block bb;
 787
 788       FOR_ALL_BB (bb)
 789         alloc_aux_for_block (bb, size);
 790     }
 791 }
 792
 793 /* Clear AUX pointers of all blocks.  */
 794
 795 void
 796 clear_aux_for_blocks (void)
 797 {
 798   basic_block bb;
 799
 800   FOR_ALL_BB (bb)
 801     bb->aux = NULL;
 802 }
 803
 804 /* Free data allocated in block_aux_obstack and clear AUX pointers
 805    of all blocks.  */
 806
 807 void
 808 free_aux_for_blocks (void)
 809 {
 810   gcc_assert (first_block_aux_obj);
 811   obstack_free (&block_aux_obstack, first_block_aux_obj);
 812   first_block_aux_obj = NULL;
 813
 814   clear_aux_for_blocks ();
 815 }
 816
 817 /* Allocate a memory edge of SIZE as E->aux.  The obstack must
 818    be first initialized by alloc_aux_for_edges.  */
 819
 820 void
 821 alloc_aux_for_edge (edge e, int size)
 822 {
 823   /* Verify that aux field is clear.  */
 824   gcc_assert (!e->aux && first_edge_aux_obj);
 825   e->aux = obstack_alloc (&edge_aux_obstack, size);
 826   memset (e->aux, 0, size);
 827 }
 828
 829 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
 830    alloc_aux_for_edge for each basic edge.  */
 831
 832 void
 833 alloc_aux_for_edges (int size)
 834 {
 835   static int initialized;
 836
 837   if (!initialized)
 838     {
 839       gcc_obstack_init (&edge_aux_obstack);
 840       initialized = 1;
 841     }
 842   else
 843     /* Check whether AUX data are still allocated.  */
 844     gcc_assert (!first_edge_aux_obj);
 845
 846   first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
 847   if (size)
 848     {
 849       basic_block bb;
 850
 851       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 852         {
 853           edge e;
 854           edge_iterator ei;
 855
 856           FOR_EACH_EDGE (e, ei, bb->succs)
 857             alloc_aux_for_edge (e, size);
 858         }
 859     }
 860 }
 861
 862 /* Clear AUX pointers of all edges.  */
 863
 864 void
 865 clear_aux_for_edges (void)
 866 {
 867   basic_block bb;
 868   edge e;
 869
 870   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 871     {
 872       edge_iterator ei;
 873       FOR_EACH_EDGE (e, ei, bb->succs)
 874         e->aux = NULL;
 875     }
 876 }
 877
 878 /* Free data allocated in edge_aux_obstack and clear AUX pointers
 879    of all edges.  */
 880
 881 void
 882 free_aux_for_edges (void)
 883 {
 884   gcc_assert (first_edge_aux_obj);
 885   obstack_free (&edge_aux_obstack, first_edge_aux_obj);
 886   first_edge_aux_obj = NULL;
 887
 888   clear_aux_for_edges ();
 889 }
 890
 891 DEBUG_FUNCTION void
 892 debug_bb (basic_block bb)
 893 {
 894   dump_bb (bb, stderr, 0);
 895 }
 896
 897 DEBUG_FUNCTION basic_block
 898 debug_bb_n (int n)
 899 {
 900   basic_block bb = BASIC_BLOCK (n);
 901   dump_bb (bb, stderr, 0);
 902   return bb;
 903 }
 904
 905 /* Dumps cfg related information about basic block BB to FILE.  */
 906
 907 static void
 908 dump_cfg_bb_info (FILE *file, basic_block bb)
 909 {
 910   unsigned i;
 911   edge_iterator ei;
 912   bool first = true;
 913   static const char * const bb_bitnames[] =
 914     {
 915       "new", "reachable", "irreducible_loop", "superblock",
 916       "nosched", "hot", "cold", "dup", "xlabel", "rtl",
 917       "fwdr", "nothrd"
 918     };
 919   const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
 920   edge e;
 921
 922   fprintf (file, "Basic block %d", bb->index);
 923   for (i = 0; i < n_bitnames; i++)
 924     if (bb->flags & (1 << i))
 925       {
 926         if (first)
 927           fputs (" (", file);
 928         else
 929           fputs (", ", file);
 930         first = false;
 931         fputs (bb_bitnames[i], file);
 932       }
 933   if (!first)
 934     putc (')', file);
 935   putc ('\n', file);
 936
 937   fputs ("Predecessors: ", file);
 938   FOR_EACH_EDGE (e, ei, bb->preds)
 939     dump_edge_info (file, e, 0);
 940
 941   fprintf (file, "\nSuccessors: ");
 942   FOR_EACH_EDGE (e, ei, bb->succs)
 943     dump_edge_info (file, e, 1);
 944   fputs ("\n\n", file);
 945 }
 946
 947 /* Dumps a brief description of cfg to FILE.  */
 948
 949 void
 950 brief_dump_cfg (FILE *file)
 951 {
 952   basic_block bb;
 953
 954   FOR_EACH_BB (bb)
 955     {
 956       dump_cfg_bb_info (file, bb);
 957     }
 958 }
 959
 960 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
 961    leave the block by TAKEN_EDGE.  Update profile of BB such that edge E can be
 962    redirected to destination of TAKEN_EDGE.
 963
 964    This function may leave the profile inconsistent in the case TAKEN_EDGE
 965    frequency or count is believed to be lower than FREQUENCY or COUNT
 966    respectively.  */
 967 void
 968 update_bb_profile_for_threading (basic_block bb, int edge_frequency,
 969                                  gcov_type count, edge taken_edge)
 970 {
 971   edge c;
 972   int prob;
 973   edge_iterator ei;
 974
 975   bb->count -= count;
 976   if (bb->count < 0)
 977     {
 978       if (dump_file)
 979         fprintf (dump_file, "bb %i count became negative after threading",
 980                  bb->index);
 981       bb->count = 0;
 982     }
 983
 984   /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
 985      Watch for overflows.  */
 986   if (bb->frequency)
 987     prob = edge_frequency * REG_BR_PROB_BASE / bb->frequency;
 988   else
 989     prob = 0;
 990   if (prob > taken_edge->probability)
 991     {
 992       if (dump_file)
 993         fprintf (dump_file, "Jump threading proved probability of edge "
 994                  "%i->%i too small (it is %i, should be %i).\n",
 995                  taken_edge->src->index, taken_edge->dest->index,
 996                  taken_edge->probability, prob);
 997       prob = taken_edge->probability;
 998     }
 999
1000   /* Now rescale the probabilities.  */
1001   taken_edge->probability -= prob;
1002   prob = REG_BR_PROB_BASE - prob;
1003   bb->frequency -= edge_frequency;
1004   if (bb->frequency < 0)
1005     bb->frequency = 0;
1006   if (prob <= 0)
1007     {
1008       if (dump_file)
1009         fprintf (dump_file, "Edge frequencies of bb %i has been reset, "
1010                  "frequency of block should end up being 0, it is %i\n",
1011                  bb->index, bb->frequency);
1012       EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
1013       ei = ei_start (bb->succs);
1014       ei_next (&ei);
1015       for (; (c = ei_safe_edge (ei)); ei_next (&ei))
1016         c->probability = 0;
1017     }
1018   else if (prob != REG_BR_PROB_BASE)
1019     {
1020       int scale = RDIV (65536 * REG_BR_PROB_BASE, prob);
1021
1022       FOR_EACH_EDGE (c, ei, bb->succs)
1023         {
1024           /* Protect from overflow due to additional scaling.  */
1025           if (c->probability > prob)
1026             c->probability = REG_BR_PROB_BASE;
1027           else
1028             {
1029               c->probability = RDIV (c->probability * scale, 65536);
1030               if (c->probability > REG_BR_PROB_BASE)
1031                 c->probability = REG_BR_PROB_BASE;
1032             }
1033         }
1034     }
1035
1036   gcc_assert (bb == taken_edge->src);
1037   taken_edge->count -= count;
1038   if (taken_edge->count < 0)
1039     {
1040       if (dump_file)
1041         fprintf (dump_file, "edge %i->%i count became negative after threading",
1042                  taken_edge->src->index, taken_edge->dest->index);
1043       taken_edge->count = 0;
1044     }
1045 }
1046
1047 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1048    by NUM/DEN, in int arithmetic.  May lose some accuracy.  */
1049 void
1050 scale_bbs_frequencies_int (basic_block *bbs, int nbbs, int num, int den)
1051 {
1052   int i;
1053   edge e;
1054   if (num < 0)
1055     num = 0;
1056
1057   /* Scale NUM and DEN to avoid overflows.  Frequencies are in order of
1058      10^4, if we make DEN <= 10^3, we can afford to upscale by 100
1059      and still safely fit in int during calculations.  */
1060   if (den > 1000)
1061     {
1062       if (num > 1000000)
1063         return;
1064
1065       num = RDIV (1000 * num, den);
1066       den = 1000;
1067     }
1068   if (num > 100 * den)
1069     return;
1070
1071   for (i = 0; i < nbbs; i++)
1072     {
1073       edge_iterator ei;
1074       bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1075       /* Make sure the frequencies do not grow over BB_FREQ_MAX.  */
1076       if (bbs[i]->frequency > BB_FREQ_MAX)
1077         bbs[i]->frequency = BB_FREQ_MAX;
1078       bbs[i]->count = RDIV (bbs[i]->count * num, den);
1079       FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1080         e->count = RDIV (e->count * num, den);
1081     }
1082 }
1083
1084 /* numbers smaller than this value are safe to multiply without getting
1085    64bit overflow.  */
1086 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
1087
1088 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1089    by NUM/DEN, in gcov_type arithmetic.  More accurate than previous
1090    function but considerably slower.  */
1091 void
1092 scale_bbs_frequencies_gcov_type (basic_block *bbs, int nbbs, gcov_type num,
1093                                  gcov_type den)
1094 {
1095   int i;
1096   edge e;
1097   gcov_type fraction = RDIV (num * 65536, den);
1098
1099   gcc_assert (fraction >= 0);
1100
1101   if (num < MAX_SAFE_MULTIPLIER)
1102     for (i = 0; i < nbbs; i++)
1103       {
1104         edge_iterator ei;
1105         bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1106         if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
1107           bbs[i]->count = RDIV (bbs[i]->count * num, den);
1108         else
1109           bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1110         FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1111           if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
1112             e->count = RDIV (e->count * num, den);
1113           else
1114             e->count = RDIV (e->count * fraction, 65536);
1115       }
1116    else
1117     for (i = 0; i < nbbs; i++)
1118       {
1119         edge_iterator ei;
1120         if (sizeof (gcov_type) > sizeof (int))
1121           bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1122         else
1123           bbs[i]->frequency = RDIV (bbs[i]->frequency * fraction, 65536);
1124         bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1125         FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1126           e->count = RDIV (e->count * fraction, 65536);
1127       }
1128 }
1129
1130 /* Data structures used to maintain mapping between basic blocks and
1131    copies.  */
1132 static htab_t bb_original;
1133 static htab_t bb_copy;
1134
1135 /* And between loops and copies.  */
1136 static htab_t loop_copy;
1137 static alloc_pool original_copy_bb_pool;
1138
1139 struct htab_bb_copy_original_entry
1140 {
1141   /* Block we are attaching info to.  */
1142   int index1;
1143   /* Index of original or copy (depending on the hashtable) */
1144   int index2;
1145 };
1146
1147 static hashval_t
1148 bb_copy_original_hash (const void *p)
1149 {
1150   const struct htab_bb_copy_original_entry *data
1151     = ((const struct htab_bb_copy_original_entry *)p);
1152
1153   return data->index1;
1154 }
1155 static int
1156 bb_copy_original_eq (const void *p, const void *q)
1157 {
1158   const struct htab_bb_copy_original_entry *data
1159     = ((const struct htab_bb_copy_original_entry *)p);
1160   const struct htab_bb_copy_original_entry *data2
1161     = ((const struct htab_bb_copy_original_entry *)q);
1162
1163   return data->index1 == data2->index1;
1164 }
1165
1166 /* Initialize the data structures to maintain mapping between blocks
1167    and its copies.  */
1168 void
1169 initialize_original_copy_tables (void)
1170 {
1171   gcc_assert (!original_copy_bb_pool);
1172   original_copy_bb_pool
1173     = create_alloc_pool ("original_copy",
1174                          sizeof (struct htab_bb_copy_original_entry), 10);
1175   bb_original = htab_create (10, bb_copy_original_hash,
1176                              bb_copy_original_eq, NULL);
1177   bb_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1178   loop_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1179 }
1180
1181 /* Free the data structures to maintain mapping between blocks and
1182    its copies.  */
1183 void
1184 free_original_copy_tables (void)
1185 {
1186   gcc_assert (original_copy_bb_pool);
1187   htab_delete (bb_copy);
1188   htab_delete (bb_original);
1189   htab_delete (loop_copy);
1190   free_alloc_pool (original_copy_bb_pool);
1191   bb_copy = NULL;
1192   bb_original = NULL;
1193   loop_copy = NULL;
1194   original_copy_bb_pool = NULL;
1195 }
1196
1197 /* Removes the value associated with OBJ from table TAB.  */
1198
1199 static void
1200 copy_original_table_clear (htab_t tab, unsigned obj)
1201 {
1202   void **slot;
1203   struct htab_bb_copy_original_entry key, *elt;
1204
1205   if (!original_copy_bb_pool)
1206     return;
1207
1208   key.index1 = obj;
1209   slot = htab_find_slot (tab, &key, NO_INSERT);
1210   if (!slot)
1211     return;
1212
1213   elt = (struct htab_bb_copy_original_entry *) *slot;
1214   htab_clear_slot (tab, slot);
1215   pool_free (original_copy_bb_pool, elt);
1216 }
1217
1218 /* Sets the value associated with OBJ in table TAB to VAL.
1219    Do nothing when data structures are not initialized.  */
1220
1221 static void
1222 copy_original_table_set (htab_t tab, unsigned obj, unsigned val)
1223 {
1224   struct htab_bb_copy_original_entry **slot;
1225   struct htab_bb_copy_original_entry key;
1226
1227   if (!original_copy_bb_pool)
1228     return;
1229
1230   key.index1 = obj;
1231   slot = (struct htab_bb_copy_original_entry **)
1232                 htab_find_slot (tab, &key, INSERT);
1233   if (!*slot)
1234     {
1235       *slot = (struct htab_bb_copy_original_entry *)
1236                 pool_alloc (original_copy_bb_pool);
1237       (*slot)->index1 = obj;
1238     }
1239   (*slot)->index2 = val;
1240 }
1241
1242 /* Set original for basic block.  Do nothing when data structures are not
1243    initialized so passes not needing this don't need to care.  */
1244 void
1245 set_bb_original (basic_block bb, basic_block original)
1246 {
1247   copy_original_table_set (bb_original, bb->index, original->index);
1248 }
1249
1250 /* Get the original basic block.  */
1251 basic_block
1252 get_bb_original (basic_block bb)
1253 {
1254   struct htab_bb_copy_original_entry *entry;
1255   struct htab_bb_copy_original_entry key;
1256
1257   gcc_assert (original_copy_bb_pool);
1258
1259   key.index1 = bb->index;
1260   entry = (struct htab_bb_copy_original_entry *) htab_find (bb_original, &key);
1261   if (entry)
1262     return BASIC_BLOCK (entry->index2);
1263   else
1264     return NULL;
1265 }
1266
1267 /* Set copy for basic block.  Do nothing when data structures are not
1268    initialized so passes not needing this don't need to care.  */
1269 void
1270 set_bb_copy (basic_block bb, basic_block copy)
1271 {
1272   copy_original_table_set (bb_copy, bb->index, copy->index);
1273 }
1274
1275 /* Get the copy of basic block.  */
1276 basic_block
1277 get_bb_copy (basic_block bb)
1278 {
1279   struct htab_bb_copy_original_entry *entry;
1280   struct htab_bb_copy_original_entry key;
1281
1282   gcc_assert (original_copy_bb_pool);
1283
1284   key.index1 = bb->index;
1285   entry = (struct htab_bb_copy_original_entry *) htab_find (bb_copy, &key);
1286   if (entry)
1287     return BASIC_BLOCK (entry->index2);
1288   else
1289     return NULL;
1290 }
1291
1292 /* Set copy for LOOP to COPY.  Do nothing when data structures are not
1293    initialized so passes not needing this don't need to care.  */
1294
1295 void
1296 set_loop_copy (struct loop *loop, struct loop *copy)
1297 {
1298   if (!copy)
1299     copy_original_table_clear (loop_copy, loop->num);
1300   else
1301     copy_original_table_set (loop_copy, loop->num, copy->num);
1302 }
1303
1304 /* Get the copy of LOOP.  */
1305
1306 struct loop *
1307 get_loop_copy (struct loop *loop)
1308 {
1309   struct htab_bb_copy_original_entry *entry;
1310   struct htab_bb_copy_original_entry key;
1311
1312   gcc_assert (original_copy_bb_pool);
1313
1314   key.index1 = loop->num;
1315   entry = (struct htab_bb_copy_original_entry *) htab_find (loop_copy, &key);
1316   if (entry)
1317     return get_loop (entry->index2);
1318   else
1319     return NULL;
1320 }