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