gcc/cfg.c

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