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