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