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 #include "tree-flow.h"
  71
  72 /* The obstack on which the flow graph components are allocated.  */
  73
  74 struct bitmap_obstack reg_obstack;
  75
  76 void debug_flow_info (void);
  77 static void free_edge (edge);
  78 \f
  79 #define RDIV(X,Y) (((X) + (Y) / 2) / (Y))
  80
  81 /* Called once at initialization time.  */
  82
  83 void
  84 init_flow (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   /* This is probably not needed, but it doesn't hurt.  */
 364   redirect_edge_var_map_clear (e);
 365
 366   free_edge (e);
 367 }
 368
 369 /* Redirect an edge's successor from one block to another.  */
 370
 371 void
 372 redirect_edge_succ (edge e, basic_block new_succ)
 373 {
 374   execute_on_shrinking_pred (e);
 375
 376   disconnect_dest (e);
 377
 378   e->dest = new_succ;
 379
 380   /* Reconnect the edge to the new successor block.  */
 381   connect_dest (e);
 382
 383   execute_on_growing_pred (e);
 384 }
 385
 386 /* Like previous but avoid possible duplicate edge.  */
 387
 388 edge
 389 redirect_edge_succ_nodup (edge e, basic_block new_succ)
 390 {
 391   edge s;
 392
 393   s = find_edge (e->src, new_succ);
 394   if (s && s != e)
 395     {
 396       s->flags |= e->flags;
 397       s->probability += e->probability;
 398       if (s->probability > REG_BR_PROB_BASE)
 399         s->probability = REG_BR_PROB_BASE;
 400       s->count += e->count;
 401       remove_edge (e);
 402       redirect_edge_var_map_dup (s, e);
 403       e = s;
 404     }
 405   else
 406     redirect_edge_succ (e, new_succ);
 407
 408   return e;
 409 }
 410
 411 /* Redirect an edge's predecessor from one block to another.  */
 412
 413 void
 414 redirect_edge_pred (edge e, basic_block new_pred)
 415 {
 416   disconnect_src (e);
 417
 418   e->src = new_pred;
 419
 420   /* Reconnect the edge to the new predecessor block.  */
 421   connect_src (e);
 422 }
 423
 424 /* Clear all basic block flags, with the exception of partitioning and
 425    setjmp_target.  */
 426 void
 427 clear_bb_flags (void)
 428 {
 429   basic_block bb;
 430
 431   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 432     bb->flags = (BB_PARTITION (bb)
 433                  | (bb->flags & (BB_DISABLE_SCHEDULE + BB_RTL + BB_NON_LOCAL_GOTO_TARGET)));
 434 }
 435 \f
 436 /* Check the consistency of profile information.  We can't do that
 437    in verify_flow_info, as the counts may get invalid for incompletely
 438    solved graphs, later eliminating of conditionals or roundoff errors.
 439    It is still practical to have them reported for debugging of simple
 440    testcases.  */
 441 void
 442 check_bb_profile (basic_block bb, FILE * file)
 443 {
 444   edge e;
 445   int sum = 0;
 446   gcov_type lsum;
 447   edge_iterator ei;
 448
 449   if (profile_status == PROFILE_ABSENT)
 450     return;
 451
 452   if (bb != EXIT_BLOCK_PTR)
 453     {
 454       FOR_EACH_EDGE (e, ei, bb->succs)
 455         sum += e->probability;
 456       if (EDGE_COUNT (bb->succs) && abs (sum - REG_BR_PROB_BASE) > 100)
 457         fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
 458                  sum * 100.0 / REG_BR_PROB_BASE);
 459       lsum = 0;
 460       FOR_EACH_EDGE (e, ei, bb->succs)
 461         lsum += e->count;
 462       if (EDGE_COUNT (bb->succs)
 463           && (lsum - bb->count > 100 || lsum - bb->count < -100))
 464         fprintf (file, "Invalid sum of outgoing counts %i, should be %i\n",
 465                  (int) lsum, (int) bb->count);
 466     }
 467   if (bb != ENTRY_BLOCK_PTR)
 468     {
 469       sum = 0;
 470       FOR_EACH_EDGE (e, ei, bb->preds)
 471         sum += EDGE_FREQUENCY (e);
 472       if (abs (sum - bb->frequency) > 100)
 473         fprintf (file,
 474                  "Invalid sum of incoming frequencies %i, should be %i\n",
 475                  sum, bb->frequency);
 476       lsum = 0;
 477       FOR_EACH_EDGE (e, ei, bb->preds)
 478         lsum += e->count;
 479       if (lsum - bb->count > 100 || lsum - bb->count < -100)
 480         fprintf (file, "Invalid sum of incoming counts %i, should be %i\n",
 481                  (int) lsum, (int) bb->count);
 482     }
 483 }
 484 \f
 485 /* Write information about registers and basic blocks into FILE.
 486    This is part of making a debugging dump.  */
 487
 488 void
 489 dump_regset (regset r, FILE *outf)
 490 {
 491   unsigned i;
 492   reg_set_iterator rsi;
 493
 494   if (r == NULL)
 495     {
 496       fputs (" (nil)", outf);
 497       return;
 498     }
 499
 500   EXECUTE_IF_SET_IN_REG_SET (r, 0, i, rsi)
 501     {
 502       fprintf (outf, " %d", i);
 503       if (i < FIRST_PSEUDO_REGISTER)
 504         fprintf (outf, " [%s]",
 505                  reg_names[i]);
 506     }
 507 }
 508
 509 /* Print a human-readable representation of R on the standard error
 510    stream.  This function is designed to be used from within the
 511    debugger.  */
 512
 513 void
 514 debug_regset (regset r)
 515 {
 516   dump_regset (r, stderr);
 517   putc ('\n', stderr);
 518 }
 519
 520 /* Emit basic block information for BB.  HEADER is true if the user wants
 521    the generic information and the predecessors, FOOTER is true if they want
 522    the successors.  FLAGS is the dump flags of interest; TDF_DETAILS emit
 523    global register liveness information.  PREFIX is put in front of every
 524    line.  The output is emitted to FILE.  */
 525 void
 526 dump_bb_info (basic_block bb, bool header, bool footer, int flags,
 527               const char *prefix, FILE *file)
 528 {
 529   edge e;
 530   edge_iterator ei;
 531
 532   if (header)
 533     {
 534       fprintf (file, "\n%sBasic block %d ", prefix, bb->index);
 535       if (bb->prev_bb)
 536         fprintf (file, ", prev %d", bb->prev_bb->index);
 537       if (bb->next_bb)
 538         fprintf (file, ", next %d", bb->next_bb->index);
 539       fprintf (file, ", loop_depth %d, count ", bb->loop_depth);
 540       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
 541       fprintf (file, ", freq %i", bb->frequency);
 542       /* Both maybe_hot_bb_p & probably_never_executed_bb_p functions
 543          crash without cfun. */
 544       if (cfun && maybe_hot_bb_p (bb))
 545         fprintf (file, ", maybe hot");
 546       if (cfun && probably_never_executed_bb_p (bb))
 547         fprintf (file, ", probably never executed");
 548       fprintf (file, ".\n");
 549
 550       fprintf (file, "%sPredecessors: ", prefix);
 551       FOR_EACH_EDGE (e, ei, bb->preds)
 552         dump_edge_info (file, e, 0);
 553
 554       if ((flags & TDF_DETAILS)
 555           && (bb->flags & BB_RTL)
 556           && df)
 557         {
 558           fprintf (file, "\n");
 559           df_dump_top (bb, file);
 560         }
 561    }
 562
 563   if (footer)
 564     {
 565       fprintf (file, "\n%sSuccessors: ", prefix);
 566       FOR_EACH_EDGE (e, ei, bb->succs)
 567         dump_edge_info (file, e, 1);
 568
 569       if ((flags & TDF_DETAILS)
 570           && (bb->flags & BB_RTL)
 571           && df)
 572         {
 573           fprintf (file, "\n");
 574           df_dump_bottom (bb, file);
 575         }
 576    }
 577
 578   putc ('\n', file);
 579 }
 580
 581 /* Dump the register info to FILE.  */
 582
 583 void
 584 dump_reg_info (FILE *file)
 585 {
 586   unsigned int i, max = max_reg_num ();
 587   if (reload_completed)
 588     return;
 589
 590   if (reg_info_p_size < max)
 591     max = reg_info_p_size;
 592
 593   fprintf (file, "%d registers.\n", max);
 594   for (i = FIRST_PSEUDO_REGISTER; i < max; i++)
 595     {
 596       enum reg_class class, altclass;
 597
 598       if (regstat_n_sets_and_refs)
 599         fprintf (file, "\nRegister %d used %d times across %d insns",
 600                  i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
 601       else if (df)
 602         fprintf (file, "\nRegister %d used %d times across %d insns",
 603                  i, DF_REG_USE_COUNT (i) + DF_REG_DEF_COUNT (i), REG_LIVE_LENGTH (i));
 604
 605       if (REG_BASIC_BLOCK (i) >= NUM_FIXED_BLOCKS)
 606         fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
 607       if (regstat_n_sets_and_refs)
 608         fprintf (file, "; set %d time%s", REG_N_SETS (i),
 609                  (REG_N_SETS (i) == 1) ? "" : "s");
 610       else if (df)
 611         fprintf (file, "; set %d time%s", DF_REG_DEF_COUNT (i),
 612                  (DF_REG_DEF_COUNT (i) == 1) ? "" : "s");
 613       if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
 614         fprintf (file, "; user var");
 615       if (REG_N_DEATHS (i) != 1)
 616         fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
 617       if (REG_N_CALLS_CROSSED (i) == 1)
 618         fprintf (file, "; crosses 1 call");
 619       else if (REG_N_CALLS_CROSSED (i))
 620         fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
 621       if (REG_FREQ_CALLS_CROSSED (i))
 622         fprintf (file, "; crosses call with %d frequency", REG_FREQ_CALLS_CROSSED (i));
 623       if (regno_reg_rtx[i] != NULL
 624           && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
 625         fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
 626
 627       class = reg_preferred_class (i);
 628       altclass = reg_alternate_class (i);
 629       if (class != GENERAL_REGS || altclass != ALL_REGS)
 630         {
 631           if (altclass == ALL_REGS || class == ALL_REGS)
 632             fprintf (file, "; pref %s", reg_class_names[(int) class]);
 633           else if (altclass == NO_REGS)
 634             fprintf (file, "; %s or none", reg_class_names[(int) class]);
 635           else
 636             fprintf (file, "; pref %s, else %s",
 637                      reg_class_names[(int) class],
 638                      reg_class_names[(int) altclass]);
 639         }
 640
 641       if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
 642         fprintf (file, "; pointer");
 643       fprintf (file, ".\n");
 644     }
 645 }
 646
 647
 648 void
 649 dump_flow_info (FILE *file, int flags)
 650 {
 651   basic_block bb;
 652
 653   /* There are no pseudo registers after reload.  Don't dump them.  */
 654   if (reg_info_p_size && (flags & TDF_DETAILS) != 0)
 655     dump_reg_info (file);
 656
 657   fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
 658   FOR_ALL_BB (bb)
 659     {
 660       dump_bb_info (bb, true, true, flags, "", file);
 661       check_bb_profile (bb, file);
 662     }
 663
 664   putc ('\n', file);
 665 }
 666
 667 void
 668 debug_flow_info (void)
 669 {
 670   dump_flow_info (stderr, TDF_DETAILS);
 671 }
 672
 673 void
 674 dump_edge_info (FILE *file, edge e, int do_succ)
 675 {
 676   basic_block side = (do_succ ? e->dest : e->src);
 677   /* both ENTRY_BLOCK_PTR & EXIT_BLOCK_PTR depend upon cfun. */
 678   if (cfun && side == ENTRY_BLOCK_PTR)
 679     fputs (" ENTRY", file);
 680   else if (cfun && side == EXIT_BLOCK_PTR)
 681     fputs (" EXIT", file);
 682   else
 683     fprintf (file, " %d", side->index);
 684
 685   if (e->probability)
 686     fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
 687
 688   if (e->count)
 689     {
 690       fprintf (file, " count:");
 691       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
 692     }
 693
 694   if (e->flags)
 695     {
 696       static const char * const bitnames[] = {
 697         "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
 698         "can_fallthru", "irreducible", "sibcall", "loop_exit",
 699         "true", "false", "exec"
 700       };
 701       int comma = 0;
 702       int i, flags = e->flags;
 703
 704       fputs (" (", file);
 705       for (i = 0; flags; i++)
 706         if (flags & (1 << i))
 707           {
 708             flags &= ~(1 << i);
 709
 710             if (comma)
 711               fputc (',', file);
 712             if (i < (int) ARRAY_SIZE (bitnames))
 713               fputs (bitnames[i], file);
 714             else
 715               fprintf (file, "%d", i);
 716             comma = 1;
 717           }
 718
 719       fputc (')', file);
 720     }
 721 }
 722 \f
 723 /* Simple routines to easily allocate AUX fields of basic blocks.  */
 724
 725 static struct obstack block_aux_obstack;
 726 static void *first_block_aux_obj = 0;
 727 static struct obstack edge_aux_obstack;
 728 static void *first_edge_aux_obj = 0;
 729
 730 /* Allocate a memory block of SIZE as BB->aux.  The obstack must
 731    be first initialized by alloc_aux_for_blocks.  */
 732
 733 inline void
 734 alloc_aux_for_block (basic_block bb, int size)
 735 {
 736   /* Verify that aux field is clear.  */
 737   gcc_assert (!bb->aux && first_block_aux_obj);
 738   bb->aux = obstack_alloc (&block_aux_obstack, size);
 739   memset (bb->aux, 0, size);
 740 }
 741
 742 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
 743    alloc_aux_for_block for each basic block.  */
 744
 745 void
 746 alloc_aux_for_blocks (int size)
 747 {
 748   static int initialized;
 749
 750   if (!initialized)
 751     {
 752       gcc_obstack_init (&block_aux_obstack);
 753       initialized = 1;
 754     }
 755   else
 756     /* Check whether AUX data are still allocated.  */
 757     gcc_assert (!first_block_aux_obj);
 758
 759   first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
 760   if (size)
 761     {
 762       basic_block bb;
 763
 764       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 765         alloc_aux_for_block (bb, size);
 766     }
 767 }
 768
 769 /* Clear AUX pointers of all blocks.  */
 770
 771 void
 772 clear_aux_for_blocks (void)
 773 {
 774   basic_block bb;
 775
 776   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 777     bb->aux = NULL;
 778 }
 779
 780 /* Free data allocated in block_aux_obstack and clear AUX pointers
 781    of all blocks.  */
 782
 783 void
 784 free_aux_for_blocks (void)
 785 {
 786   gcc_assert (first_block_aux_obj);
 787   obstack_free (&block_aux_obstack, first_block_aux_obj);
 788   first_block_aux_obj = NULL;
 789
 790   clear_aux_for_blocks ();
 791 }
 792
 793 /* Allocate a memory edge of SIZE as BB->aux.  The obstack must
 794    be first initialized by alloc_aux_for_edges.  */
 795
 796 inline void
 797 alloc_aux_for_edge (edge e, int size)
 798 {
 799   /* Verify that aux field is clear.  */
 800   gcc_assert (!e->aux && first_edge_aux_obj);
 801   e->aux = obstack_alloc (&edge_aux_obstack, size);
 802   memset (e->aux, 0, size);
 803 }
 804
 805 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
 806    alloc_aux_for_edge for each basic edge.  */
 807
 808 void
 809 alloc_aux_for_edges (int size)
 810 {
 811   static int initialized;
 812
 813   if (!initialized)
 814     {
 815       gcc_obstack_init (&edge_aux_obstack);
 816       initialized = 1;
 817     }
 818   else
 819     /* Check whether AUX data are still allocated.  */
 820     gcc_assert (!first_edge_aux_obj);
 821
 822   first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
 823   if (size)
 824     {
 825       basic_block bb;
 826
 827       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 828         {
 829           edge e;
 830           edge_iterator ei;
 831
 832           FOR_EACH_EDGE (e, ei, bb->succs)
 833             alloc_aux_for_edge (e, size);
 834         }
 835     }
 836 }
 837
 838 /* Clear AUX pointers of all edges.  */
 839
 840 void
 841 clear_aux_for_edges (void)
 842 {
 843   basic_block bb;
 844   edge e;
 845
 846   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 847     {
 848       edge_iterator ei;
 849       FOR_EACH_EDGE (e, ei, bb->succs)
 850         e->aux = NULL;
 851     }
 852 }
 853
 854 /* Free data allocated in edge_aux_obstack and clear AUX pointers
 855    of all edges.  */
 856
 857 void
 858 free_aux_for_edges (void)
 859 {
 860   gcc_assert (first_edge_aux_obj);
 861   obstack_free (&edge_aux_obstack, first_edge_aux_obj);
 862   first_edge_aux_obj = NULL;
 863
 864   clear_aux_for_edges ();
 865 }
 866
 867 void
 868 debug_bb (basic_block bb)
 869 {
 870   dump_bb (bb, stderr, 0);
 871 }
 872
 873 basic_block
 874 debug_bb_n (int n)
 875 {
 876   basic_block bb = BASIC_BLOCK (n);
 877   dump_bb (bb, stderr, 0);
 878   return bb;
 879 }
 880
 881 /* Dumps cfg related information about basic block BB to FILE.  */
 882
 883 static void
 884 dump_cfg_bb_info (FILE *file, basic_block bb)
 885 {
 886   unsigned i;
 887   edge_iterator ei;
 888   bool first = true;
 889   static const char * const bb_bitnames[] =
 890     {
 891       "new", "reachable", "irreducible_loop", "superblock",
 892       "nosched", "hot", "cold", "dup", "xlabel", "rtl",
 893       "fwdr", "nothrd"
 894     };
 895   const unsigned n_bitnames = sizeof (bb_bitnames) / sizeof (char *);
 896   edge e;
 897
 898   fprintf (file, "Basic block %d", bb->index);
 899   for (i = 0; i < n_bitnames; i++)
 900     if (bb->flags & (1 << i))
 901       {
 902         if (first)
 903           fprintf (file, " (");
 904         else
 905           fprintf (file, ", ");
 906         first = false;
 907         fprintf (file, bb_bitnames[i]);
 908       }
 909   if (!first)
 910     fprintf (file, ")");
 911   fprintf (file, "\n");
 912
 913   fprintf (file, "Predecessors: ");
 914   FOR_EACH_EDGE (e, ei, bb->preds)
 915     dump_edge_info (file, e, 0);
 916
 917   fprintf (file, "\nSuccessors: ");
 918   FOR_EACH_EDGE (e, ei, bb->succs)
 919     dump_edge_info (file, e, 1);
 920   fprintf (file, "\n\n");
 921 }
 922
 923 /* Dumps a brief description of cfg to FILE.  */
 924
 925 void
 926 brief_dump_cfg (FILE *file)
 927 {
 928   basic_block bb;
 929
 930   FOR_EACH_BB (bb)
 931     {
 932       dump_cfg_bb_info (file, bb);
 933     }
 934 }
 935
 936 /* An edge originally destinating BB of FREQUENCY and COUNT has been proved to
 937    leave the block by TAKEN_EDGE.  Update profile of BB such that edge E can be
 938    redirected to destination of TAKEN_EDGE.
 939
 940    This function may leave the profile inconsistent in the case TAKEN_EDGE
 941    frequency or count is believed to be lower than FREQUENCY or COUNT
 942    respectively.  */
 943 void
 944 update_bb_profile_for_threading (basic_block bb, int edge_frequency,
 945                                  gcov_type count, edge taken_edge)
 946 {
 947   edge c;
 948   int prob;
 949   edge_iterator ei;
 950
 951   bb->count -= count;
 952   if (bb->count < 0)
 953     {
 954       if (dump_file)
 955         fprintf (dump_file, "bb %i count became negative after threading",
 956                  bb->index);
 957       bb->count = 0;
 958     }
 959
 960   /* Compute the probability of TAKEN_EDGE being reached via threaded edge.
 961      Watch for overflows.  */
 962   if (bb->frequency)
 963     prob = edge_frequency * REG_BR_PROB_BASE / bb->frequency;
 964   else
 965     prob = 0;
 966   if (prob > taken_edge->probability)
 967     {
 968       if (dump_file)
 969         fprintf (dump_file, "Jump threading proved probability of edge "
 970                  "%i->%i too small (it is %i, should be %i).\n",
 971                  taken_edge->src->index, taken_edge->dest->index,
 972                  taken_edge->probability, prob);
 973       prob = taken_edge->probability;
 974     }
 975
 976   /* Now rescale the probabilities.  */
 977   taken_edge->probability -= prob;
 978   prob = REG_BR_PROB_BASE - prob;
 979   bb->frequency -= edge_frequency;
 980   if (bb->frequency < 0)
 981     bb->frequency = 0;
 982   if (prob <= 0)
 983     {
 984       if (dump_file)
 985         fprintf (dump_file, "Edge frequencies of bb %i has been reset, "
 986                  "frequency of block should end up being 0, it is %i\n",
 987                  bb->index, bb->frequency);
 988       EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
 989       ei = ei_start (bb->succs);
 990       ei_next (&ei);
 991       for (; (c = ei_safe_edge (ei)); ei_next (&ei))
 992         c->probability = 0;
 993     }
 994   else if (prob != REG_BR_PROB_BASE)
 995     {
 996       int scale = RDIV (65536 * REG_BR_PROB_BASE, prob);
 997
 998       FOR_EACH_EDGE (c, ei, bb->succs)
 999         {
1000           /* Protect from overflow due to additional scaling.  */
1001           if (c->probability > prob)
1002             c->probability = REG_BR_PROB_BASE;
1003           else
1004             {
1005               c->probability = RDIV (c->probability * scale, 65536);
1006               if (c->probability > REG_BR_PROB_BASE)
1007                 c->probability = REG_BR_PROB_BASE;
1008             }
1009         }
1010     }
1011
1012   gcc_assert (bb == taken_edge->src);
1013   taken_edge->count -= count;
1014   if (taken_edge->count < 0)
1015     {
1016       if (dump_file)
1017         fprintf (dump_file, "edge %i->%i count became negative after threading",
1018                  taken_edge->src->index, taken_edge->dest->index);
1019       taken_edge->count = 0;
1020     }
1021 }
1022
1023 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1024    by NUM/DEN, in int arithmetic.  May lose some accuracy.  */
1025 void
1026 scale_bbs_frequencies_int (basic_block *bbs, int nbbs, int num, int den)
1027 {
1028   int i;
1029   edge e;
1030   if (num < 0)
1031     num = 0;
1032
1033   /* Scale NUM and DEN to avoid overflows.  Frequencies are in order of
1034      10^4, if we make DEN <= 10^3, we can afford to upscale by 100
1035      and still safely fit in int during calculations.  */
1036   if (den > 1000)
1037     {
1038       if (num > 1000000)
1039         return;
1040
1041       num = RDIV (1000 * num, den);
1042       den = 1000;
1043     }
1044   if (num > 100 * den)
1045     return;
1046
1047   for (i = 0; i < nbbs; i++)
1048     {
1049       edge_iterator ei;
1050       bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1051       /* Make sure the frequencies do not grow over BB_FREQ_MAX.  */
1052       if (bbs[i]->frequency > BB_FREQ_MAX)
1053         bbs[i]->frequency = BB_FREQ_MAX;
1054       bbs[i]->count = RDIV (bbs[i]->count * num, den);
1055       FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1056         e->count = RDIV (e->count * num, den);
1057     }
1058 }
1059
1060 /* numbers smaller than this value are safe to multiply without getting
1061    64bit overflow.  */
1062 #define MAX_SAFE_MULTIPLIER (1 << (sizeof (HOST_WIDEST_INT) * 4 - 1))
1063
1064 /* Multiply all frequencies of basic blocks in array BBS of length NBBS
1065    by NUM/DEN, in gcov_type arithmetic.  More accurate than previous
1066    function but considerably slower.  */
1067 void
1068 scale_bbs_frequencies_gcov_type (basic_block *bbs, int nbbs, gcov_type num,
1069                                  gcov_type den)
1070 {
1071   int i;
1072   edge e;
1073   gcov_type fraction = RDIV (num * 65536, den);
1074
1075   gcc_assert (fraction >= 0);
1076
1077   if (num < MAX_SAFE_MULTIPLIER)
1078     for (i = 0; i < nbbs; i++)
1079       {
1080         edge_iterator ei;
1081         bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1082         if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
1083           bbs[i]->count = RDIV (bbs[i]->count * num, den);
1084         else
1085           bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1086         FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1087           if (bbs[i]->count <= MAX_SAFE_MULTIPLIER)
1088             e->count = RDIV (e->count * num, den);
1089           else
1090             e->count = RDIV (e->count * fraction, 65536);
1091       }
1092    else
1093     for (i = 0; i < nbbs; i++)
1094       {
1095         edge_iterator ei;
1096         if (sizeof (gcov_type) > sizeof (int))
1097           bbs[i]->frequency = RDIV (bbs[i]->frequency * num, den);
1098         else
1099           bbs[i]->frequency = RDIV (bbs[i]->frequency * fraction, 65536);
1100         bbs[i]->count = RDIV (bbs[i]->count * fraction, 65536);
1101         FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1102           e->count = RDIV (e->count * fraction, 65536);
1103       }
1104 }
1105
1106 /* Data structures used to maintain mapping between basic blocks and
1107    copies.  */
1108 static htab_t bb_original;
1109 static htab_t bb_copy;
1110
1111 /* And between loops and copies.  */
1112 static htab_t loop_copy;
1113 static alloc_pool original_copy_bb_pool;
1114
1115 struct htab_bb_copy_original_entry
1116 {
1117   /* Block we are attaching info to.  */
1118   int index1;
1119   /* Index of original or copy (depending on the hashtable) */
1120   int index2;
1121 };
1122
1123 static hashval_t
1124 bb_copy_original_hash (const void *p)
1125 {
1126   const struct htab_bb_copy_original_entry *data
1127     = ((const struct htab_bb_copy_original_entry *)p);
1128
1129   return data->index1;
1130 }
1131 static int
1132 bb_copy_original_eq (const void *p, const void *q)
1133 {
1134   const struct htab_bb_copy_original_entry *data
1135     = ((const struct htab_bb_copy_original_entry *)p);
1136   const struct htab_bb_copy_original_entry *data2
1137     = ((const struct htab_bb_copy_original_entry *)q);
1138
1139   return data->index1 == data2->index1;
1140 }
1141
1142 /* Initialize the data structures to maintain mapping between blocks
1143    and its copies.  */
1144 void
1145 initialize_original_copy_tables (void)
1146 {
1147   gcc_assert (!original_copy_bb_pool);
1148   original_copy_bb_pool
1149     = create_alloc_pool ("original_copy",
1150                          sizeof (struct htab_bb_copy_original_entry), 10);
1151   bb_original = htab_create (10, bb_copy_original_hash,
1152                              bb_copy_original_eq, NULL);
1153   bb_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1154   loop_copy = htab_create (10, bb_copy_original_hash, bb_copy_original_eq, NULL);
1155 }
1156
1157 /* Free the data structures to maintain mapping between blocks and
1158    its copies.  */
1159 void
1160 free_original_copy_tables (void)
1161 {
1162   gcc_assert (original_copy_bb_pool);
1163   htab_delete (bb_copy);
1164   htab_delete (bb_original);
1165   htab_delete (loop_copy);
1166   free_alloc_pool (original_copy_bb_pool);
1167   bb_copy = NULL;
1168   bb_original = NULL;
1169   loop_copy = NULL;
1170   original_copy_bb_pool = NULL;
1171 }
1172
1173 /* Removes the value associated with OBJ from table TAB.  */
1174
1175 static void
1176 copy_original_table_clear (htab_t tab, unsigned obj)
1177 {
1178   void **slot;
1179   struct htab_bb_copy_original_entry key, *elt;
1180
1181   if (!original_copy_bb_pool)
1182     return;
1183
1184   key.index1 = obj;
1185   slot = htab_find_slot (tab, &key, NO_INSERT);
1186   if (!slot)
1187     return;
1188
1189   elt = (struct htab_bb_copy_original_entry *) *slot;
1190   htab_clear_slot (tab, slot);
1191   pool_free (original_copy_bb_pool, elt);
1192 }
1193
1194 /* Sets the value associated with OBJ in table TAB to VAL.
1195    Do nothing when data structures are not initialized.  */
1196
1197 static void
1198 copy_original_table_set (htab_t tab, unsigned obj, unsigned val)
1199 {
1200   struct htab_bb_copy_original_entry **slot;
1201   struct htab_bb_copy_original_entry key;
1202
1203   if (!original_copy_bb_pool)
1204     return;
1205
1206   key.index1 = obj;
1207   slot = (struct htab_bb_copy_original_entry **)
1208                 htab_find_slot (tab, &key, INSERT);
1209   if (!*slot)
1210     {
1211       *slot = (struct htab_bb_copy_original_entry *)
1212                 pool_alloc (original_copy_bb_pool);
1213       (*slot)->index1 = obj;
1214     }
1215   (*slot)->index2 = val;
1216 }
1217
1218 /* Set original for basic block.  Do nothing when data structures are not
1219    initialized so passes not needing this don't need to care.  */
1220 void
1221 set_bb_original (basic_block bb, basic_block original)
1222 {
1223   copy_original_table_set (bb_original, bb->index, original->index);
1224 }
1225
1226 /* Get the original basic block.  */
1227 basic_block
1228 get_bb_original (basic_block bb)
1229 {
1230   struct htab_bb_copy_original_entry *entry;
1231   struct htab_bb_copy_original_entry key;
1232
1233   gcc_assert (original_copy_bb_pool);
1234
1235   key.index1 = bb->index;
1236   entry = (struct htab_bb_copy_original_entry *) htab_find (bb_original, &key);
1237   if (entry)
1238     return BASIC_BLOCK (entry->index2);
1239   else
1240     return NULL;
1241 }
1242
1243 /* Set copy for basic block.  Do nothing when data structures are not
1244    initialized so passes not needing this don't need to care.  */
1245 void
1246 set_bb_copy (basic_block bb, basic_block copy)
1247 {
1248   copy_original_table_set (bb_copy, bb->index, copy->index);
1249 }
1250
1251 /* Get the copy of basic block.  */
1252 basic_block
1253 get_bb_copy (basic_block bb)
1254 {
1255   struct htab_bb_copy_original_entry *entry;
1256   struct htab_bb_copy_original_entry key;
1257
1258   gcc_assert (original_copy_bb_pool);
1259
1260   key.index1 = bb->index;
1261   entry = (struct htab_bb_copy_original_entry *) htab_find (bb_copy, &key);
1262   if (entry)
1263     return BASIC_BLOCK (entry->index2);
1264   else
1265     return NULL;
1266 }
1267
1268 /* Set copy for LOOP to COPY.  Do nothing when data structures are not
1269    initialized so passes not needing this don't need to care.  */
1270
1271 void
1272 set_loop_copy (struct loop *loop, struct loop *copy)
1273 {
1274   if (!copy)
1275     copy_original_table_clear (loop_copy, loop->num);
1276   else
1277     copy_original_table_set (loop_copy, loop->num, copy->num);
1278 }
1279
1280 /* Get the copy of LOOP.  */
1281
1282 struct loop *
1283 get_loop_copy (struct loop *loop)
1284 {
1285   struct htab_bb_copy_original_entry *entry;
1286   struct htab_bb_copy_original_entry key;
1287
1288   gcc_assert (original_copy_bb_pool);
1289
1290   key.index1 = loop->num;
1291   entry = (struct htab_bb_copy_original_entry *) htab_find (loop_copy, &key);
1292   if (entry)
1293     return get_loop (entry->index2);
1294   else
1295     return NULL;
1296 }