contrib/gcc-3.4/gcc/cfg.c

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