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