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 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /* This file contains low level functions to manipulate the CFG and
  23    analyze it.  All other modules should not transform the datastructure
  24    directly and use abstraction instead.  The file is supposed to be
  25    ordered bottom-up and should not contain any code dependent on a
  26    particular intermediate language (RTL or trees).
  27
  28    Available functionality:
  29      - Initialization/deallocation
  30          init_flow, clear_edges
  31      - Low level basic block manipulation
  32          alloc_block, expunge_block
  33      - Edge manipulation
  34          make_edge, make_single_succ_edge, cached_make_edge, remove_edge
  35          - Low level edge redirection (without updating instruction chain)
  36              redirect_edge_succ, redirect_edge_succ_nodup, redirect_edge_pred
  37      - Dumping and debugging
  38          dump_flow_info, debug_flow_info, dump_edge_info
  39      - Allocation of AUX fields for basic blocks
  40          alloc_aux_for_blocks, free_aux_for_blocks, alloc_aux_for_block
  41      - clear_bb_flags
  42      - Consistency checking
  43          verify_flow_info
  44      - Dumping and debugging
  45          print_rtl_with_bb, dump_bb, debug_bb, debug_bb_n
  46  */
  47 \f
  48 #include "config.h"
  49 #include "system.h"
  50 #include "coretypes.h"
  51 #include "tm.h"
  52 #include "tree.h"
  53 #include "rtl.h"
  54 #include "hard-reg-set.h"
  55 #include "basic-block.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 "alloc-pool.h"
  65
  66 /* The obstack on which the flow graph components are allocated.  */
  67
  68 struct obstack flow_obstack;
  69 static char *flow_firstobj;
  70
  71 /* Basic block object pool.  */
  72
  73 static alloc_pool bb_pool;
  74
  75 /* Edge object pool.  */
  76
  77 static alloc_pool edge_pool;
  78
  79 /* Number of basic blocks in the current function.  */
  80
  81 int n_basic_blocks;
  82
  83 /* First free basic block number.  */
  84
  85 int last_basic_block;
  86
  87 /* Number of edges in the current function.  */
  88
  89 int n_edges;
  90
  91 /* The basic block array.  */
  92
  93 varray_type basic_block_info;
  94
  95 /* The special entry and exit blocks.  */
  96
  97 struct basic_block_def entry_exit_blocks[2]
  98 = {{NULL,                       /* head */
  99     NULL,                       /* end */
 100     NULL,                       /* head_tree */
 101     NULL,                       /* end_tree */
 102     NULL,                       /* pred */
 103     NULL,                       /* succ */
 104     NULL,                       /* local_set */
 105     NULL,                       /* cond_local_set */
 106     NULL,                       /* global_live_at_start */
 107     NULL,                       /* global_live_at_end */
 108     NULL,                       /* aux */
 109     ENTRY_BLOCK,                /* index */
 110     NULL,                       /* prev_bb */
 111     EXIT_BLOCK_PTR,             /* next_bb */
 112     0,                          /* loop_depth */
 113     NULL,                       /* loop_father */
 114     0,                          /* count */
 115     0,                          /* frequency */
 116     0                           /* flags */
 117   },
 118   {
 119     NULL,                       /* head */
 120     NULL,                       /* end */
 121     NULL,                       /* head_tree */
 122     NULL,                       /* end_tree */
 123     NULL,                       /* pred */
 124     NULL,                       /* succ */
 125     NULL,                       /* local_set */
 126     NULL,                       /* cond_local_set */
 127     NULL,                       /* global_live_at_start */
 128     NULL,                       /* global_live_at_end */
 129     NULL,                       /* aux */
 130     EXIT_BLOCK,                 /* index */
 131     ENTRY_BLOCK_PTR,            /* prev_bb */
 132     NULL,                       /* next_bb */
 133     0,                          /* loop_depth */
 134     NULL,                       /* loop_father */
 135     0,                          /* count */
 136     0,                          /* frequency */
 137     0                           /* flags */
 138   }
 139 };
 140
 141 void debug_flow_info (void);
 142 static void free_edge (edge);
 143 \f
 144 /* Called once at initialization time.  */
 145
 146 void
 147 init_flow (void)
 148 {
 149   static int initialized;
 150
 151   n_edges = 0;
 152
 153   if (!initialized)
 154     {
 155       gcc_obstack_init (&flow_obstack);
 156       flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
 157       initialized = 1;
 158     }
 159   else
 160     {
 161       free_alloc_pool (bb_pool);
 162       free_alloc_pool (edge_pool);
 163       obstack_free (&flow_obstack, flow_firstobj);
 164       flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
 165     }
 166   bb_pool = create_alloc_pool ("Basic block pool",
 167                                sizeof (struct basic_block_def), 100);
 168   edge_pool = create_alloc_pool ("Edge pool",
 169                                sizeof (struct edge_def), 100);
 170 }
 171 \f
 172 /* Helper function for remove_edge and clear_edges.  Frees edge structure
 173    without actually unlinking it from the pred/succ lists.  */
 174
 175 static void
 176 free_edge (edge e)
 177 {
 178   n_edges--;
 179   pool_free (edge_pool, e);
 180 }
 181
 182 /* Free the memory associated with the edge structures.  */
 183
 184 void
 185 clear_edges (void)
 186 {
 187   basic_block bb;
 188   edge e;
 189
 190   FOR_EACH_BB (bb)
 191     {
 192       edge e = bb->succ;
 193
 194       while (e)
 195         {
 196           edge next = e->succ_next;
 197
 198           free_edge (e);
 199           e = next;
 200         }
 201
 202       bb->succ = NULL;
 203       bb->pred = NULL;
 204     }
 205
 206   e = ENTRY_BLOCK_PTR->succ;
 207   while (e)
 208     {
 209       edge next = e->succ_next;
 210
 211       free_edge (e);
 212       e = next;
 213     }
 214
 215   EXIT_BLOCK_PTR->pred = NULL;
 216   ENTRY_BLOCK_PTR->succ = NULL;
 217
 218   if (n_edges)
 219     abort ();
 220 }
 221 \f
 222 /* Allocate memory for basic_block.  */
 223
 224 basic_block
 225 alloc_block (void)
 226 {
 227   basic_block bb;
 228   bb = pool_alloc (bb_pool);
 229   memset (bb, 0, sizeof (*bb));
 230   return bb;
 231 }
 232
 233 /* Link block B to chain after AFTER.  */
 234 void
 235 link_block (basic_block b, basic_block after)
 236 {
 237   b->next_bb = after->next_bb;
 238   b->prev_bb = after;
 239   after->next_bb = b;
 240   b->next_bb->prev_bb = b;
 241 }
 242
 243 /* Unlink block B from chain.  */
 244 void
 245 unlink_block (basic_block b)
 246 {
 247   b->next_bb->prev_bb = b->prev_bb;
 248   b->prev_bb->next_bb = b->next_bb;
 249 }
 250
 251 /* Sequentially order blocks and compact the arrays.  */
 252 void
 253 compact_blocks (void)
 254 {
 255   int i;
 256   basic_block bb;
 257
 258   i = 0;
 259   FOR_EACH_BB (bb)
 260     {
 261       BASIC_BLOCK (i) = bb;
 262       bb->index = i;
 263       i++;
 264     }
 265
 266   if (i != n_basic_blocks)
 267     abort ();
 268
 269   last_basic_block = n_basic_blocks;
 270 }
 271
 272 /* Remove block B from the basic block array.  */
 273
 274 void
 275 expunge_block (basic_block b)
 276 {
 277   unlink_block (b);
 278   BASIC_BLOCK (b->index) = NULL;
 279   n_basic_blocks--;
 280   pool_free (bb_pool, b);
 281 }
 282 \f
 283 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
 284    created edge.  Use this only if you are sure that this edge can't
 285    possibly already exist.  */
 286
 287 edge
 288 unchecked_make_edge (basic_block src, basic_block dst, int flags)
 289 {
 290   edge e;
 291   e = pool_alloc (edge_pool);
 292   memset (e, 0, sizeof (*e));
 293   n_edges++;
 294
 295   e->succ_next = src->succ;
 296   e->pred_next = dst->pred;
 297   e->src = src;
 298   e->dest = dst;
 299   e->flags = flags;
 300
 301   src->succ = e;
 302   dst->pred = e;
 303
 304   return e;
 305 }
 306
 307 /* Create an edge connecting SRC and DST with FLAGS optionally using
 308    edge cache CACHE.  Return the new edge, NULL if already exist.  */
 309
 310 edge
 311 cached_make_edge (sbitmap *edge_cache, basic_block src, basic_block dst, int flags)
 312 {
 313   int use_edge_cache;
 314   edge e;
 315
 316   /* Don't bother with edge cache for ENTRY or EXIT, if there aren't that
 317      many edges to them, or we didn't allocate memory for it.  */
 318   use_edge_cache = (edge_cache
 319                     && src != ENTRY_BLOCK_PTR && dst != EXIT_BLOCK_PTR);
 320
 321   /* Make sure we don't add duplicate edges.  */
 322   switch (use_edge_cache)
 323     {
 324     default:
 325       /* Quick test for non-existence of the edge.  */
 326       if (! TEST_BIT (edge_cache[src->index], dst->index))
 327         break;
 328
 329       /* The edge exists; early exit if no work to do.  */
 330       if (flags == 0)
 331         return NULL;
 332
 333       /* FALLTHRU */
 334     case 0:
 335       for (e = src->succ; e; e = e->succ_next)
 336         if (e->dest == dst)
 337           {
 338             e->flags |= flags;
 339             return NULL;
 340           }
 341       break;
 342     }
 343
 344   e = unchecked_make_edge (src, dst, flags);
 345
 346   if (use_edge_cache)
 347     SET_BIT (edge_cache[src->index], dst->index);
 348
 349   return e;
 350 }
 351
 352 /* Create an edge connecting SRC and DEST with flags FLAGS.  Return newly
 353    created edge or NULL if already exist.  */
 354
 355 edge
 356 make_edge (basic_block src, basic_block dest, int flags)
 357 {
 358   return cached_make_edge (NULL, src, dest, flags);
 359 }
 360
 361 /* Create an edge connecting SRC to DEST and set probability by knowing
 362    that it is the single edge leaving SRC.  */
 363
 364 edge
 365 make_single_succ_edge (basic_block src, basic_block dest, int flags)
 366 {
 367   edge e = make_edge (src, dest, flags);
 368
 369   e->probability = REG_BR_PROB_BASE;
 370   e->count = src->count;
 371   return e;
 372 }
 373
 374 /* This function will remove an edge from the flow graph.  */
 375
 376 void
 377 remove_edge (edge e)
 378 {
 379   edge last_pred = NULL;
 380   edge last_succ = NULL;
 381   edge tmp;
 382   basic_block src, dest;
 383
 384   src = e->src;
 385   dest = e->dest;
 386   for (tmp = src->succ; tmp && tmp != e; tmp = tmp->succ_next)
 387     last_succ = tmp;
 388
 389   if (!tmp)
 390     abort ();
 391   if (last_succ)
 392     last_succ->succ_next = e->succ_next;
 393   else
 394     src->succ = e->succ_next;
 395
 396   for (tmp = dest->pred; tmp && tmp != e; tmp = tmp->pred_next)
 397     last_pred = tmp;
 398
 399   if (!tmp)
 400     abort ();
 401   if (last_pred)
 402     last_pred->pred_next = e->pred_next;
 403   else
 404     dest->pred = e->pred_next;
 405
 406   free_edge (e);
 407 }
 408
 409 /* Redirect an edge's successor from one block to another.  */
 410
 411 void
 412 redirect_edge_succ (edge e, basic_block new_succ)
 413 {
 414   edge *pe;
 415
 416   /* Disconnect the edge from the old successor block.  */
 417   for (pe = &e->dest->pred; *pe != e; pe = &(*pe)->pred_next)
 418     continue;
 419   *pe = (*pe)->pred_next;
 420
 421   /* Reconnect the edge to the new successor block.  */
 422   e->pred_next = new_succ->pred;
 423   new_succ->pred = e;
 424   e->dest = new_succ;
 425 }
 426
 427 /* Like previous but avoid possible duplicate edge.  */
 428
 429 edge
 430 redirect_edge_succ_nodup (edge e, basic_block new_succ)
 431 {
 432   edge s;
 433
 434   /* Check whether the edge is already present.  */
 435   for (s = e->src->succ; s; s = s->succ_next)
 436     if (s->dest == new_succ && s != e)
 437       break;
 438
 439   if (s)
 440     {
 441       s->flags |= e->flags;
 442       s->probability += e->probability;
 443       if (s->probability > REG_BR_PROB_BASE)
 444         s->probability = REG_BR_PROB_BASE;
 445       s->count += e->count;
 446       remove_edge (e);
 447       e = s;
 448     }
 449   else
 450     redirect_edge_succ (e, new_succ);
 451
 452   return e;
 453 }
 454
 455 /* Redirect an edge's predecessor from one block to another.  */
 456
 457 void
 458 redirect_edge_pred (edge e, basic_block new_pred)
 459 {
 460   edge *pe;
 461
 462   /* Disconnect the edge from the old predecessor block.  */
 463   for (pe = &e->src->succ; *pe != e; pe = &(*pe)->succ_next)
 464     continue;
 465
 466   *pe = (*pe)->succ_next;
 467
 468   /* Reconnect the edge to the new predecessor block.  */
 469   e->succ_next = new_pred->succ;
 470   new_pred->succ = e;
 471   e->src = new_pred;
 472 }
 473
 474 void
 475 clear_bb_flags (void)
 476 {
 477   basic_block bb;
 478
 479   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 480     bb->flags = 0;
 481 }
 482 \f
 483 void
 484 dump_flow_info (FILE *file)
 485 {
 486   int i;
 487   int max_regno = max_reg_num ();
 488   basic_block bb;
 489   static const char * const reg_class_names[] = REG_CLASS_NAMES;
 490
 491   fprintf (file, "%d registers.\n", max_regno);
 492   for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
 493     if (REG_N_REFS (i))
 494       {
 495         enum reg_class class, altclass;
 496
 497         fprintf (file, "\nRegister %d used %d times across %d insns",
 498                  i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
 499         if (REG_BASIC_BLOCK (i) >= 0)
 500           fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
 501         if (REG_N_SETS (i))
 502           fprintf (file, "; set %d time%s", REG_N_SETS (i),
 503                    (REG_N_SETS (i) == 1) ? "" : "s");
 504         if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
 505           fprintf (file, "; user var");
 506         if (REG_N_DEATHS (i) != 1)
 507           fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
 508         if (REG_N_CALLS_CROSSED (i) == 1)
 509           fprintf (file, "; crosses 1 call");
 510         else if (REG_N_CALLS_CROSSED (i))
 511           fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
 512         if (regno_reg_rtx[i] != NULL
 513             && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
 514           fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
 515
 516         class = reg_preferred_class (i);
 517         altclass = reg_alternate_class (i);
 518         if (class != GENERAL_REGS || altclass != ALL_REGS)
 519           {
 520             if (altclass == ALL_REGS || class == ALL_REGS)
 521               fprintf (file, "; pref %s", reg_class_names[(int) class]);
 522             else if (altclass == NO_REGS)
 523               fprintf (file, "; %s or none", reg_class_names[(int) class]);
 524             else
 525               fprintf (file, "; pref %s, else %s",
 526                        reg_class_names[(int) class],
 527                        reg_class_names[(int) altclass]);
 528           }
 529
 530         if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
 531           fprintf (file, "; pointer");
 532         fprintf (file, ".\n");
 533       }
 534
 535   fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
 536   FOR_EACH_BB (bb)
 537     {
 538       edge e;
 539       int sum;
 540       gcov_type lsum;
 541
 542       fprintf (file, "\nBasic block %d: first insn %d, last %d, ",
 543                bb->index, INSN_UID (bb->head), INSN_UID (bb->end));
 544       fprintf (file, "prev %d, next %d, ",
 545                bb->prev_bb->index, bb->next_bb->index);
 546       fprintf (file, "loop_depth %d, count ", bb->loop_depth);
 547       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
 548       fprintf (file, ", freq %i", bb->frequency);
 549       if (maybe_hot_bb_p (bb))
 550         fprintf (file, ", maybe hot");
 551       if (probably_never_executed_bb_p (bb))
 552         fprintf (file, ", probably never executed");
 553       fprintf (file, ".\n");
 554
 555       fprintf (file, "Predecessors: ");
 556       for (e = bb->pred; e; e = e->pred_next)
 557         dump_edge_info (file, e, 0);
 558
 559       fprintf (file, "\nSuccessors: ");
 560       for (e = bb->succ; e; e = e->succ_next)
 561         dump_edge_info (file, e, 1);
 562
 563       fprintf (file, "\nRegisters live at start:");
 564       dump_regset (bb->global_live_at_start, file);
 565
 566       fprintf (file, "\nRegisters live at end:");
 567       dump_regset (bb->global_live_at_end, file);
 568
 569       putc ('\n', file);
 570
 571       /* Check the consistency of profile information.  We can't do that
 572          in verify_flow_info, as the counts may get invalid for incompletely
 573          solved graphs, later eliminating of conditionals or roundoff errors.
 574          It is still practical to have them reported for debugging of simple
 575          testcases.  */
 576       sum = 0;
 577       for (e = bb->succ; e; e = e->succ_next)
 578         sum += e->probability;
 579       if (bb->succ && abs (sum - REG_BR_PROB_BASE) > 100)
 580         fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
 581                  sum * 100.0 / REG_BR_PROB_BASE);
 582       sum = 0;
 583       for (e = bb->pred; e; e = e->pred_next)
 584         sum += EDGE_FREQUENCY (e);
 585       if (abs (sum - bb->frequency) > 100)
 586         fprintf (file,
 587                  "Invalid sum of incomming frequencies %i, should be %i\n",
 588                  sum, bb->frequency);
 589       lsum = 0;
 590       for (e = bb->pred; e; e = e->pred_next)
 591         lsum += e->count;
 592       if (lsum - bb->count > 100 || lsum - bb->count < -100)
 593         fprintf (file, "Invalid sum of incomming counts %i, should be %i\n",
 594                  (int)lsum, (int)bb->count);
 595       lsum = 0;
 596       for (e = bb->succ; e; e = e->succ_next)
 597         lsum += e->count;
 598       if (bb->succ && (lsum - bb->count > 100 || lsum - bb->count < -100))
 599         fprintf (file, "Invalid sum of incomming counts %i, should be %i\n",
 600                  (int)lsum, (int)bb->count);
 601     }
 602
 603   putc ('\n', file);
 604 }
 605
 606 void
 607 debug_flow_info (void)
 608 {
 609   dump_flow_info (stderr);
 610 }
 611
 612 void
 613 dump_edge_info (FILE *file, edge e, int do_succ)
 614 {
 615   basic_block side = (do_succ ? e->dest : e->src);
 616
 617   if (side == ENTRY_BLOCK_PTR)
 618     fputs (" ENTRY", file);
 619   else if (side == EXIT_BLOCK_PTR)
 620     fputs (" EXIT", file);
 621   else
 622     fprintf (file, " %d", side->index);
 623
 624   if (e->probability)
 625     fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
 626
 627   if (e->count)
 628     {
 629       fprintf (file, " count:");
 630       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
 631     }
 632
 633   if (e->flags)
 634     {
 635       static const char * const bitnames[] = {
 636         "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
 637         "can_fallthru", "irreducible", "sibcall"
 638       };
 639       int comma = 0;
 640       int i, flags = e->flags;
 641
 642       fputs (" (", file);
 643       for (i = 0; flags; i++)
 644         if (flags & (1 << i))
 645           {
 646             flags &= ~(1 << i);
 647
 648             if (comma)
 649               fputc (',', file);
 650             if (i < (int) ARRAY_SIZE (bitnames))
 651               fputs (bitnames[i], file);
 652             else
 653               fprintf (file, "%d", i);
 654             comma = 1;
 655           }
 656
 657       fputc (')', file);
 658     }
 659 }
 660 \f
 661 /* Simple routines to easily allocate AUX fields of basic blocks.  */
 662
 663 static struct obstack block_aux_obstack;
 664 static void *first_block_aux_obj = 0;
 665 static struct obstack edge_aux_obstack;
 666 static void *first_edge_aux_obj = 0;
 667
 668 /* Allocate a memory block of SIZE as BB->aux.  The obstack must
 669    be first initialized by alloc_aux_for_blocks.  */
 670
 671 inline void
 672 alloc_aux_for_block (basic_block bb, int size)
 673 {
 674   /* Verify that aux field is clear.  */
 675   if (bb->aux || !first_block_aux_obj)
 676     abort ();
 677   bb->aux = obstack_alloc (&block_aux_obstack, size);
 678   memset (bb->aux, 0, size);
 679 }
 680
 681 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
 682    alloc_aux_for_block for each basic block.  */
 683
 684 void
 685 alloc_aux_for_blocks (int size)
 686 {
 687   static int initialized;
 688
 689   if (!initialized)
 690     {
 691       gcc_obstack_init (&block_aux_obstack);
 692       initialized = 1;
 693     }
 694
 695   /* Check whether AUX data are still allocated.  */
 696   else if (first_block_aux_obj)
 697     abort ();
 698   first_block_aux_obj = (char *) obstack_alloc (&block_aux_obstack, 0);
 699   if (size)
 700     {
 701       basic_block bb;
 702
 703       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 704         alloc_aux_for_block (bb, size);
 705     }
 706 }
 707
 708 /* Clear AUX pointers of all blocks.  */
 709
 710 void
 711 clear_aux_for_blocks (void)
 712 {
 713   basic_block bb;
 714
 715   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 716     bb->aux = NULL;
 717 }
 718
 719 /* Free data allocated in block_aux_obstack and clear AUX pointers
 720    of all blocks.  */
 721
 722 void
 723 free_aux_for_blocks (void)
 724 {
 725   if (!first_block_aux_obj)
 726     abort ();
 727   obstack_free (&block_aux_obstack, first_block_aux_obj);
 728   first_block_aux_obj = NULL;
 729
 730   clear_aux_for_blocks ();
 731 }
 732
 733 /* Allocate a memory edge of SIZE as BB->aux.  The obstack must
 734    be first initialized by alloc_aux_for_edges.  */
 735
 736 inline void
 737 alloc_aux_for_edge (edge e, int size)
 738 {
 739   /* Verify that aux field is clear.  */
 740   if (e->aux || !first_edge_aux_obj)
 741     abort ();
 742   e->aux = obstack_alloc (&edge_aux_obstack, size);
 743   memset (e->aux, 0, size);
 744 }
 745
 746 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
 747    alloc_aux_for_edge for each basic edge.  */
 748
 749 void
 750 alloc_aux_for_edges (int size)
 751 {
 752   static int initialized;
 753
 754   if (!initialized)
 755     {
 756       gcc_obstack_init (&edge_aux_obstack);
 757       initialized = 1;
 758     }
 759
 760   /* Check whether AUX data are still allocated.  */
 761   else if (first_edge_aux_obj)
 762     abort ();
 763
 764   first_edge_aux_obj = (char *) obstack_alloc (&edge_aux_obstack, 0);
 765   if (size)
 766     {
 767       basic_block bb;
 768
 769       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 770         {
 771           edge e;
 772
 773           for (e = bb->succ; e; e = e->succ_next)
 774             alloc_aux_for_edge (e, size);
 775         }
 776     }
 777 }
 778
 779 /* Clear AUX pointers of all edges.  */
 780
 781 void
 782 clear_aux_for_edges (void)
 783 {
 784   basic_block bb;
 785   edge e;
 786
 787   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 788     {
 789       for (e = bb->succ; e; e = e->succ_next)
 790         e->aux = NULL;
 791     }
 792 }
 793
 794 /* Free data allocated in edge_aux_obstack and clear AUX pointers
 795    of all edges.  */
 796
 797 void
 798 free_aux_for_edges (void)
 799 {
 800   if (!first_edge_aux_obj)
 801     abort ();
 802   obstack_free (&edge_aux_obstack, first_edge_aux_obj);
 803   first_edge_aux_obj = NULL;
 804
 805   clear_aux_for_edges ();
 806 }
 807
 808 /* Verify the CFG consistency.
 809
 810    Currently it does following checks edge and basic block list correctness
 811    and calls into IL dependent checking then.  */
 812 void
 813 verify_flow_info (void)
 814 {
 815   size_t *edge_checksum;
 816   int num_bb_notes, err = 0;
 817   basic_block bb, last_bb_seen;
 818   basic_block *last_visited;
 819
 820   last_visited = (basic_block *) xcalloc (last_basic_block + 2,
 821                                           sizeof (basic_block));
 822   edge_checksum = (size_t *) xcalloc (last_basic_block + 2, sizeof (size_t));
 823
 824   /* Check bb chain & numbers.  */
 825   last_bb_seen = ENTRY_BLOCK_PTR;
 826   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 827     {
 828       if (bb != EXIT_BLOCK_PTR
 829           && bb != BASIC_BLOCK (bb->index))
 830         {
 831           error ("bb %d on wrong place", bb->index);
 832           err = 1;
 833         }
 834
 835       if (bb->prev_bb != last_bb_seen)
 836         {
 837           error ("prev_bb of %d should be %d, not %d",
 838                  bb->index, last_bb_seen->index, bb->prev_bb->index);
 839           err = 1;
 840         }
 841
 842       last_bb_seen = bb;
 843     }
 844
 845   /* Now check the basic blocks (boundaries etc.) */
 846   FOR_EACH_BB_REVERSE (bb)
 847     {
 848       int n_fallthru = 0;
 849       edge e;
 850
 851       if (bb->count < 0)
 852         {
 853           error ("verify_flow_info: Wrong count of block %i %i",
 854                  bb->index, (int)bb->count);
 855           err = 1;
 856         }
 857       if (bb->frequency < 0)
 858         {
 859           error ("verify_flow_info: Wrong frequency of block %i %i",
 860                  bb->index, bb->frequency);
 861           err = 1;
 862         }
 863       for (e = bb->succ; e; e = e->succ_next)
 864         {
 865           if (last_visited [e->dest->index + 2] == bb)
 866             {
 867               error ("verify_flow_info: Duplicate edge %i->%i",
 868                      e->src->index, e->dest->index);
 869               err = 1;
 870             }
 871           if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
 872             {
 873               error ("verify_flow_info: Wrong probability of edge %i->%i %i",
 874                      e->src->index, e->dest->index, e->probability);
 875               err = 1;
 876             }
 877           if (e->count < 0)
 878             {
 879               error ("verify_flow_info: Wrong count of edge %i->%i %i",
 880                      e->src->index, e->dest->index, (int)e->count);
 881               err = 1;
 882             }
 883
 884           last_visited [e->dest->index + 2] = bb;
 885
 886           if (e->flags & EDGE_FALLTHRU)
 887             n_fallthru++;
 888
 889           if (e->src != bb)
 890             {
 891               error ("verify_flow_info: Basic block %d succ edge is corrupted",
 892                      bb->index);
 893               fprintf (stderr, "Predecessor: ");
 894               dump_edge_info (stderr, e, 0);
 895               fprintf (stderr, "\nSuccessor: ");
 896               dump_edge_info (stderr, e, 1);
 897               fprintf (stderr, "\n");
 898               err = 1;
 899             }
 900
 901           edge_checksum[e->dest->index + 2] += (size_t) e;
 902         }
 903       if (n_fallthru > 1)
 904         {
 905           error ("Wrong amount of branch edges after unconditional jump %i", bb->index);
 906           err = 1;
 907         }
 908
 909       for (e = bb->pred; e; e = e->pred_next)
 910         {
 911           if (e->dest != bb)
 912             {
 913               error ("basic block %d pred edge is corrupted", bb->index);
 914               fputs ("Predecessor: ", stderr);
 915               dump_edge_info (stderr, e, 0);
 916               fputs ("\nSuccessor: ", stderr);
 917               dump_edge_info (stderr, e, 1);
 918               fputc ('\n', stderr);
 919               err = 1;
 920             }
 921           edge_checksum[e->dest->index + 2] -= (size_t) e;
 922         }
 923     }
 924
 925   /* Complete edge checksumming for ENTRY and EXIT.  */
 926   {
 927     edge e;
 928
 929     for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
 930       edge_checksum[e->dest->index + 2] += (size_t) e;
 931
 932     for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
 933       edge_checksum[e->dest->index + 2] -= (size_t) e;
 934   }
 935
 936   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 937     if (edge_checksum[bb->index + 2])
 938       {
 939         error ("basic block %i edge lists are corrupted", bb->index);
 940         err = 1;
 941       }
 942
 943   num_bb_notes = 0;
 944   last_bb_seen = ENTRY_BLOCK_PTR;
 945
 946   /* Clean up.  */
 947   free (last_visited);
 948   free (edge_checksum);
 949   err |= cfg_hooks->cfgh_verify_flow_info ();
 950   if (err)
 951     internal_error ("verify_flow_info failed");
 952 }
 953
 954 /* Print out one basic block with live information at start and end.  */
 955
 956 void
 957 dump_bb (basic_block bb, FILE *outf)
 958 {
 959   edge e;
 960
 961   fprintf (outf, ";; Basic block %d, loop depth %d, count ",
 962            bb->index, bb->loop_depth);
 963   fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
 964   putc ('\n', outf);
 965
 966   cfg_hooks->dump_bb (bb, outf);
 967
 968   fputs (";; Successors: ", outf);
 969   for (e = bb->succ; e; e = e->succ_next)
 970     dump_edge_info (outf, e, 1);
 971   putc ('\n', outf);
 972 }
 973
 974 void
 975 debug_bb (basic_block bb)
 976 {
 977   dump_bb (bb, stderr);
 978 }
 979
 980 basic_block
 981 debug_bb_n (int n)
 982 {
 983   basic_block bb = BASIC_BLOCK (n);
 984   dump_bb (bb, stderr);
 985   return bb;
 986 }