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