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