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