gcc/cfg.c

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