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