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