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