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