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