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 "toplev.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_CNEW (struct control_flow_graph);
  88   n_edges_for_function (the_fun) = 0;
  89   ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)
  90     = GGC_CNEW (struct basic_block_def);
  91   ENTRY_BLOCK_PTR_FOR_FUNCTION (the_fun)->index = ENTRY_BLOCK;
  92   EXIT_BLOCK_PTR_FOR_FUNCTION (the_fun)
  93     = GGC_CNEW (struct 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_CNEW (struct 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_CNEW (struct 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       remove_edge (e);
 406       redirect_edge_var_map_dup (s, 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 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       fputs (".\n", file);
 553
 554       fprintf (file, "%sPredecessors: ", prefix);
 555       FOR_EACH_EDGE (e, ei, bb->preds)
 556         dump_edge_info (file, e, 0);
 557
 558       if ((flags & TDF_DETAILS)
 559           && (bb->flags & BB_RTL)
 560           && df)
 561         {
 562           putc ('\n', file);
 563           df_dump_top (bb, file);
 564         }
 565    }
 566
 567   if (footer)
 568     {
 569       fprintf (file, "\n%sSuccessors: ", prefix);
 570       FOR_EACH_EDGE (e, ei, bb->succs)
 571         dump_edge_info (file, e, 1);
 572
 573       if ((flags & TDF_DETAILS)
 574           && (bb->flags & BB_RTL)
 575           && df)
 576         {
 577           putc ('\n', file);
 578           df_dump_bottom (bb, file);
 579         }
 580    }
 581
 582   putc ('\n', file);
 583 }
 584
 585 /* Dump the register info to FILE.  */
 586
 587 void
 588 dump_reg_info (FILE *file)
 589 {
 590   unsigned int i, max = max_reg_num ();
 591   if (reload_completed)
 592     return;
 593
 594   if (reg_info_p_size < max)
 595     max = reg_info_p_size;
 596
 597   fprintf (file, "%d registers.\n", max);
 598   for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
 599     {
 600       enum reg_class rclass, altclass;
 601
 602       if (regstat_n_sets_and_refs)
 603         fprintf (file, "\nRegister %d used %d times across %d insns",
 604                  i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
 605       else if (df)
 606         fprintf (file, "\nRegister %d used %d times across %d insns",
 607                  i, DF_REG_USE_COUNT (i) + DF_REG_DEF_COUNT (i), REG_LIVE_LENGTH (i));
 608
 609       if (REG_BASIC_BLOCK (i) >= NUM_FIXED_BLOCKS)
 610         fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
 611       if (regstat_n_sets_and_refs)
 612         fprintf (file, "; set %d time%s", REG_N_SETS (i),
 613                  (REG_N_SETS (i) == 1) ? "" : "s");
 614       else if (df)
 615         fprintf (file, "; set %d time%s", DF_REG_DEF_COUNT (i),
 616                  (DF_REG_DEF_COUNT (i) == 1) ? "" : "s");
 617       if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
 618         fputs ("; user var", file);
 619       if (REG_N_DEATHS (i) != 1)
 620         fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
 621       if (REG_N_CALLS_CROSSED (i) == 1)
 622         fputs ("; crosses 1 call", file);
 623       else if (REG_N_CALLS_CROSSED (i))
 624         fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
 625       if (REG_FREQ_CALLS_CROSSED (i))
 626         fprintf (file, "; crosses call with %d frequency", REG_FREQ_CALLS_CROSSED (i));
 627       if (regno_reg_rtx[i] != NULL
 628           && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
 629         fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
 630
 631       rclass = reg_preferred_class (i);
 632       altclass = reg_alternate_class (i);
 633       if (rclass != GENERAL_REGS || altclass != ALL_REGS)
 634         {
 635           if (altclass == ALL_REGS || rclass == ALL_REGS)
 636             fprintf (file, "; pref %s", reg_class_names[(int) rclass]);
 637           else if (altclass == NO_REGS)
 638             fprintf (file, "; %s or none", reg_class_names[(int) rclass]);
 639           else
 640             fprintf (file, "; pref %s, else %s",
 641                      reg_class_names[(int) rclass],
 642                      reg_class_names[(int) altclass]);
 643         }
 644
 645       if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
 646         fputs ("; pointer", file);
 647       fputs (".\n", file);
 648     }
 649 }
 650
 651
 652 void
 653 dump_flow_info (FILE *file, int flags)
 654 {
 655   basic_block bb;
 656
 657   /* There are no pseudo registers after reload.  Don't dump them.  */
 658   if (reg_info_p_size && (flags & TDF_DETAILS) != 0)
 659     dump_reg_info (file);
 660
 661   fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
 662   FOR_ALL_BB (bb)
 663     {
 664       dump_bb_info (bb, true, true, flags, "", file);
 665       check_bb_profile (bb, file);
 666     }
 667
 668   putc ('\n', file);
 669 }
 670
 671 void
 672 debug_flow_info (void)
 673 {
 674   dump_flow_info (stderr, TDF_DETAILS);
 675 }
 676
 677 void
 678 dump_edge_info (FILE *file, edge e, int do_succ)
 679 {
 680   basic_block side = (do_succ ? e->dest : e->src);
 681   /* both ENTRY_BLOCK_PTR & EXIT_BLOCK_PTR depend upon cfun. */
 682   if (cfun && side == ENTRY_BLOCK_PTR)
 683     fputs (" ENTRY", file);
 684   else if (cfun && side == EXIT_BLOCK_PTR)
 685     fputs (" EXIT", file);
 686   else
 687     fprintf (file, " %d", side->index);
 688
 689   if (e->probability)
 690     fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
 691
 692   if (e->count)
 693     {
 694       fputs (" count:", file);
 695       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
 696     }
 697
 698   if (e->flags)
 699     {
 700       static const char * const bitnames[] = {
 701         "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
 702         "can_fallthru", "irreducible", "sibcall", "loop_exit",
 703         "true", "false", "exec"
 704       };
 705       int comma = 0;
 706       int i, flags = e->flags;
 707
 708       fputs (" (", file);
 709       for (i = 0; flags; i++)
 710         if (flags & (1 << i))
 711           {
 712             flags &= ~(1 << i);
 713
 714             if (comma)
 715               fputc (',', file);
 716             if (i < (int) ARRAY_SIZE (bitnames))
 717               fputs (bitnames[i], file);
 718             else
 719               fprintf (file, "%d", i);
 720             comma = 1;
 721           }
 722
 723       fputc (')', file);
 724     }
 725 }
 726 \f
 727 /* Simple routines to easily allocate AUX fields of basic blocks.  */
 728
 729 static struct obstack block_aux_obstack;
 730 static void *first_block_aux_obj = 0;
 731 static struct obstack edge_aux_obstack;
 732 static void *first_edge_aux_obj = 0;
 733
 734 /* Allocate a memory block of SIZE as BB->aux.  The obstack must
 735    be first initialized by alloc_aux_for_blocks.  */
 736
 737 void
 738 alloc_aux_for_block (basic_block bb, int size)
 739 {
 740   /* Verify that aux field is clear.  */
 741   gcc_assert (!bb->aux && first_block_aux_obj);
 742   bb->aux = obstack_alloc (&block_aux_obstack, size);
 743   memset (bb->aux, 0, size);
 744 }
 745
 746 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
 747    alloc_aux_for_block for each basic block.  */
 748
 749 void
 750 alloc_aux_for_blocks (int size)
 751 {
 752   static int initialized;
 753
 754   if (!initialized)
 755     {
 756       gcc_obstack_init (&block_aux_obstack);
 757       initialized = 1;
 758     }
 759   else
 760     /* Check whether AUX data are still allocated.  */
 761     gcc_assert (!first_block_aux_obj);
 762
 763   first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
 764   if (size)
 765     {
 766       basic_block bb;
 767
 768       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 769         alloc_aux_for_block (bb, size);
 770     }
 771 }
 772
 773 /* Clear AUX pointers of all blocks.  */
 774
 775 void
 776 clear_aux_for_blocks (void)
 777 {
 778   basic_block bb;
 779
 780   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 781     bb->aux = NULL;
 782 }
 783
 784 /* Free data allocated in block_aux_obstack and clear AUX pointers
 785    of all blocks.  */
 786
 787 void
 788 free_aux_for_blocks (void)
 789 {
 790   gcc_assert (first_block_aux_obj);
 791   obstack_free (&block_aux_obstack, first_block_aux_obj);
 792   first_block_aux_obj = NULL;
 793
 794   clear_aux_for_blocks ();
 795 }
 796
 797 /* Allocate a memory edge of SIZE as BB->aux.  The obstack must
 798    be first initialized by alloc_aux_for_edges.  */
 799
 800 void
 801 alloc_aux_for_edge (edge e, int size)
 802 {
 803   /* Verify that aux field is clear.  */
 804   gcc_assert (!e->aux && first_edge_aux_obj);
 805   e->aux = obstack_alloc (&edge_aux_obstack, size);
 806   memset (e->aux, 0, size);
 807 }
 808
 809 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
 810    alloc_aux_for_edge for each basic edge.  */
 811
 812 void
 813 alloc_aux_for_edges (int size)
 814 {
 815   static int initialized;
 816
 817   if (!initialized)
 818     {
 819       gcc_obstack_init (&edge_aux_obstack);
 820       initialized = 1;
 821     }
 822   else
 823     /* Check whether AUX data are still allocated.  */
 824     gcc_assert (!first_edge_aux_obj);
 825
 826   first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
 827   if (size)
 828     {
 829       basic_block bb;
 830
 831       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 832         {
 833           edge e;
 834           edge_iterator ei;
 835
 836           FOR_EACH_EDGE (e, ei, bb->succs)
 837             alloc_aux_for_edge (e, size);
 838         }
 839     }
 840 }
 841
 842 /* Clear AUX pointers of all edges.  */
 843
 844 void
 845 clear_aux_for_edges (void)
 846 {
 847   basic_block bb;
 848   edge e;
 849
 850   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 851     {
 852       edge_iterator ei;
 853       FOR_EACH_EDGE (e, ei, bb->succs)
 854         e->aux = NULL;
 855     }
 856 }
 857
 858 /* Free data allocated in edge_aux_obstack and clear AUX pointers
 859    of all edges.  */
 860
 861 void
 862 free_aux_for_edges (void)
 863 {
 864   gcc_assert (first_edge_aux_obj);
 865   obstack_free (&edge_aux_obstack, first_edge_aux_obj);
 866   first_edge_aux_obj = NULL;
 867
 868   clear_aux_for_edges ();
 869 }
 870
 871 void
 872 debug_bb (basic_block bb)
 873 {
 874   dump_bb (bb, stderr, 0);
 875 }
 876
 877 basic_block
 878 debug_bb_n (int n)
 879 {
 880   basic_block bb = BASIC_BLOCK (n);
 881   dump_bb (bb, stderr, 0);
 882   return bb;
 883 }
 884
 885 /* Dumps cfg related information about basic block BB to FILE.  */
 886
 887 static void
 888 dump_cfg_bb_info (FILE *file, basic_block bb)
 889 {
 890   unsigned i;
 891   edge_iterator ei;
 892   bool first = true;
 893   static const char * const bb_bitnames[] =
 894     {
 895       "new", "reachable", "irreducible_loop", "superblock",
 896       "nosched", "hot", "cold", "dup", "xlabel", "rtl",
 897       "fwdr", "nothrd"
 898     };
 899   const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
 900   edge e;
 901
 902   fprintf (file, "Basic block %d", bb->index);
 903   for (i = 0; i < n_bitnames; i++)
 904     if (bb->flags & (1 << i))
 905       {
 906         if (first)
 907           fputs (" (", file);
 908         else
 909           fputs (", ", file);
 910         first = false;
 911         fputs (bb_bitnames[i], file);
 912       }
 913   if (!first)
 914     putc (')', file);
 915   putc ('\n', file);
 916
 917   fputs ("Predecessors: ", file);
 918   FOR_EACH_EDGE (e, ei, bb->preds)
 919     dump_edge_info (file, e, 0);
 920
 921   fprintf (file, "\nSuccessors: ");
 922   FOR_EACH_EDGE (e, ei, bb->succs)
 923     dump_edge_info (file, e, 1);
 924   fputs ("\n\n", file);
 925 }
 926
 927 /* Dumps a brief description of cfg to FILE.  */
 928
 929 void
 930 brief_dump_cfg (FILE *file)
 931 {
 932   basic_block bb;
 933
 934   FOR_EACH_BB (bb)
 935     {
 936       dump_cfg_bb_info (file, bb);
 937     }
 938 }
 939
 940 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
 941    leave the block by TAKEN_EDGE.  Update profile of BB such that edge E can be
 942    redirected to destination of TAKEN_EDGE.
 943
 944    This function may leave the profile inconsistent in the case TAKEN_EDGE
 945    frequency or count is believed to be lower than FREQUENCY or COUNT
 946    respectively.  */
 947 void
 948 update_bb_profile_for_threading (basic_block bb, int edge_frequency,
 949                                  gcov_type count, edge taken_edge)
 950 {
 951   edge c;
 952   int prob;
 953   edge_iterator ei;
 954
 955   bb->count -= count;
 956   if (bb->count < 0)
 957     {
 958       if (dump_file)
 959         fprintf (dump_file, "bb %i count became negative after threading",
 960                  bb->index);
 961       bb->count = 0;
 962     }
 963
 964   /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
 965      Watch for overflows.  */
 966   if (bb->frequency)
 967     prob = edge_frequency * REG_BR_PROB_BASE / bb->frequency;
 968   else
 969     prob = 0;
 970   if (prob > taken_edge->probability)
 971     {
 972       if (dump_file)
 973         fprintf (dump_file, "Jump threading proved probability of edge "
 974                  "%i->%i too small (it is %i, should be %i).\n",
 975                  taken_edge->src->index, taken_edge->dest->index,
 976                  taken_edge->probability, prob);
 977       prob = taken_edge->probability;
 978     }
 979
 980   /* Now rescale the probabilities.  */
 981   taken_edge->probability -= prob;
 982   prob = REG_BR_PROB_BASE - prob;
 983   bb->frequency -= edge_frequency;
 984   if (bb->frequency < 0)
 985     bb->frequency = 0;
 986   if (prob <= 0)
 987     {
 988       if (dump_file)
 989         fprintf (dump_file, "Edge frequencies of bb %i has been reset, "
 990                  "frequency of block should end up being 0, it is %i\n",
 991                  bb->index, bb->frequency);
 992       EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
 993       ei = ei_start (bb->succs);
 994       ei_next (&ei);
 995       for (; (c = ei_safe_edge (ei)); ei_next (&ei))
 996         c->probability = 0;
 997     }
 998   else if (prob != REG_BR_PROB_BASE)
 999     {
1000       int scale = RDIV (65536 * REG_BR_PROB_BASE, prob);
1001
1002       FOR_EACH_EDGE (c, ei, bb->succs)
1003         {
1004           /* Protect from overflow due to additional scaling.  */
1005           if (c->probability > prob)
1006             c->probability = REG_BR_PROB_BASE;
1007           else
1008             {
1009               c->probability = RDIV (c->probability * scale, 65536);
1010               if (c->probability > REG_BR_PROB_BASE)
1011                 c->probability = REG_BR_PROB_BASE;
1012             }
1013         }
1014     }
1015
1016   gcc_assert (bb == taken_edge->src);
1017   taken_edge->count -= count;
1018   if (taken_edge->count < 0)
1019     {
1020       if (dump_file)
1021         fprintf (dump_file, "edge %i->%i count became negative after threading",
1022                  taken_edge->src->index, taken_edge->dest->index);
1023       taken_edge->count = 0;
1024     }
1025 }
1026
1027 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1028    by NUM/DEN, in int arithmetic.  May lose some accuracy.  */
1029 void
1030 scale_bbs_frequencies_int (basic_block *bbs, int nbbs, int num, int den)
1031 {
1032   int i;
1033   edge e;
1034   if (num < 0)
1035     num = 0;
1036
1037   /* Scale NUM and DEN to avoid overflows.  Frequencies are in order of
1038      10^4, if we make DEN <= 10^3, we can afford to upscale by 100
1039      and still safely fit in int during calculations.  */
1040   if (den > 1000)
1041     {
1042       if (num > 1000000)
1043         return;
1044
1045       num = RDIV (1000 * num, den);
1046       den = 1000;
1047     }
1048   if (num > 100 * den)
1049     return;
1050
1051   for (i = 0; i < nbbs; i++)
1052     {
1053       edge_iterator ei;
1054       bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1055       /* Make sure the frequencies do not grow over BB_FREQ_MAX.  */
1056       if (bbs[i]->frequency > BB_FREQ_MAX)
1057         bbs[i]->frequency = BB_FREQ_MAX;
1058       bbs[i]->count = RDIV (bbs[i]->count * num, den);
1059       FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1060         e->count = RDIV (e->count * num, den);
1061     }
1062 }
1063
1064 /* numbers smaller than this value are safe to multiply without getting
1065    64bit overflow.  */
1066 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
1067
1068 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1069    by NUM/DEN, in gcov_type arithmetic.  More accurate than previous
1070    function but considerably slower.  */
1071 void
1072 scale_bbs_frequencies_gcov_type (basic_block *bbs, int nbbs, gcov_type num,
1073                                  gcov_type den)
1074 {
1075   int i;
1076   edge e;
1077   gcov_type fraction = RDIV (num * 65536, den);
1078
1079   gcc_assert (fraction >= 0);
1080
1081   if (num < MAX_SAFE_MULTIPLIER)
1082     for (i = 0; i < nbbs; i++)
1083       {
1084         edge_iterator ei;
1085         bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1086         if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
1087           bbs[i]->count = RDIV (bbs[i]->count * num, den);
1088         else
1089           bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1090         FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1091           if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
1092             e->count = RDIV (e->count * num, den);
1093           else
1094             e->count = RDIV (e->count * fraction, 65536);
1095       }
1096    else
1097     for (i = 0; i < nbbs; i++)
1098       {
1099         edge_iterator ei;
1100         if (sizeof (gcov_type) > sizeof (int))
1101           bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1102         else
1103           bbs[i]->frequency = RDIV (bbs[i]->frequency * fraction, 65536);
1104         bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1105         FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1106           e->count = RDIV (e->count * fraction, 65536);
1107       }
1108 }
1109
1110 /* Data structures used to maintain mapping between basic blocks and
1111    copies.  */
1112 static htab_t bb_original;
1113 static htab_t bb_copy;
1114
1115 /* And between loops and copies.  */
1116 static htab_t loop_copy;
1117 static alloc_pool original_copy_bb_pool;
1118
1119 struct htab_bb_copy_original_entry
1120 {
1121   /* Block we are attaching info to.  */
1122   int index1;
1123   /* Index of original or copy (depending on the hashtable) */
1124   int index2;
1125 };
1126
1127 static hashval_t
1128 bb_copy_original_hash (const void *p)
1129 {
1130   const struct htab_bb_copy_original_entry *data
1131     = ((const struct htab_bb_copy_original_entry *)p);
1132
1133   return data->index1;
1134 }
1135 static int
1136 bb_copy_original_eq (const void *p, const void *q)
1137 {
1138   const struct htab_bb_copy_original_entry *data
1139     = ((const struct htab_bb_copy_original_entry *)p);
1140   const struct htab_bb_copy_original_entry *data2
1141     = ((const struct htab_bb_copy_original_entry *)q);
1142
1143   return data->index1 == data2->index1;
1144 }
1145
1146 /* Initialize the data structures to maintain mapping between blocks
1147    and its copies.  */
1148 void
1149 initialize_original_copy_tables (void)
1150 {
1151   gcc_assert (!original_copy_bb_pool);
1152   original_copy_bb_pool
1153     = create_alloc_pool ("original_copy",
1154                          sizeof (struct htab_bb_copy_original_entry), 10);
1155   bb_original = htab_create (10, bb_copy_original_hash,
1156                              bb_copy_original_eq, NULL);
1157   bb_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1158   loop_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1159 }
1160
1161 /* Free the data structures to maintain mapping between blocks and
1162    its copies.  */
1163 void
1164 free_original_copy_tables (void)
1165 {
1166   gcc_assert (original_copy_bb_pool);
1167   htab_delete (bb_copy);
1168   htab_delete (bb_original);
1169   htab_delete (loop_copy);
1170   free_alloc_pool (original_copy_bb_pool);
1171   bb_copy = NULL;
1172   bb_original = NULL;
1173   loop_copy = NULL;
1174   original_copy_bb_pool = NULL;
1175 }
1176
1177 /* Removes the value associated with OBJ from table TAB.  */
1178
1179 static void
1180 copy_original_table_clear (htab_t tab, unsigned obj)
1181 {
1182   void **slot;
1183   struct htab_bb_copy_original_entry key, *elt;
1184
1185   if (!original_copy_bb_pool)
1186     return;
1187
1188   key.index1 = obj;
1189   slot = htab_find_slot (tab, &key, NO_INSERT);
1190   if (!slot)
1191     return;
1192
1193   elt = (struct htab_bb_copy_original_entry *) *slot;
1194   htab_clear_slot (tab, slot);
1195   pool_free (original_copy_bb_pool, elt);
1196 }
1197
1198 /* Sets the value associated with OBJ in table TAB to VAL.
1199    Do nothing when data structures are not initialized.  */
1200
1201 static void
1202 copy_original_table_set (htab_t tab, unsigned obj, unsigned val)
1203 {
1204   struct htab_bb_copy_original_entry **slot;
1205   struct htab_bb_copy_original_entry key;
1206
1207   if (!original_copy_bb_pool)
1208     return;
1209
1210   key.index1 = obj;
1211   slot = (struct htab_bb_copy_original_entry **)
1212                 htab_find_slot (tab, &key, INSERT);
1213   if (!*slot)
1214     {
1215       *slot = (struct htab_bb_copy_original_entry *)
1216                 pool_alloc (original_copy_bb_pool);
1217       (*slot)->index1 = obj;
1218     }
1219   (*slot)->index2 = val;
1220 }
1221
1222 /* Set original for basic block.  Do nothing when data structures are not
1223    initialized so passes not needing this don't need to care.  */
1224 void
1225 set_bb_original (basic_block bb, basic_block original)
1226 {
1227   copy_original_table_set (bb_original, bb->index, original->index);
1228 }
1229
1230 /* Get the original basic block.  */
1231 basic_block
1232 get_bb_original (basic_block bb)
1233 {
1234   struct htab_bb_copy_original_entry *entry;
1235   struct htab_bb_copy_original_entry key;
1236
1237   gcc_assert (original_copy_bb_pool);
1238
1239   key.index1 = bb->index;
1240   entry = (struct htab_bb_copy_original_entry *) htab_find (bb_original, &key);
1241   if (entry)
1242     return BASIC_BLOCK (entry->index2);
1243   else
1244     return NULL;
1245 }
1246
1247 /* Set copy for basic block.  Do nothing when data structures are not
1248    initialized so passes not needing this don't need to care.  */
1249 void
1250 set_bb_copy (basic_block bb, basic_block copy)
1251 {
1252   copy_original_table_set (bb_copy, bb->index, copy->index);
1253 }
1254
1255 /* Get the copy of basic block.  */
1256 basic_block
1257 get_bb_copy (basic_block bb)
1258 {
1259   struct htab_bb_copy_original_entry *entry;
1260   struct htab_bb_copy_original_entry key;
1261
1262   gcc_assert (original_copy_bb_pool);
1263
1264   key.index1 = bb->index;
1265   entry = (struct htab_bb_copy_original_entry *) htab_find (bb_copy, &key);
1266   if (entry)
1267     return BASIC_BLOCK (entry->index2);
1268   else
1269     return NULL;
1270 }
1271
1272 /* Set copy for LOOP to COPY.  Do nothing when data structures are not
1273    initialized so passes not needing this don't need to care.  */
1274
1275 void
1276 set_loop_copy (struct loop *loop, struct loop *copy)
1277 {
1278   if (!copy)
1279     copy_original_table_clear (loop_copy, loop->num);
1280   else
1281     copy_original_table_set (loop_copy, loop->num, copy->num);
1282 }
1283
1284 /* Get the copy of LOOP.  */
1285
1286 struct loop *
1287 get_loop_copy (struct loop *loop)
1288 {
1289   struct htab_bb_copy_original_entry *entry;
1290   struct htab_bb_copy_original_entry key;
1291
1292   gcc_assert (original_copy_bb_pool);
1293
1294   key.index1 = loop->num;
1295   entry = (struct htab_bb_copy_original_entry *) htab_find (loop_copy, &key);
1296   if (entry)
1297     return get_loop (entry->index2);
1298   else
1299     return NULL;
1300 }