gcc/cfg.c

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