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   if (reg_n_info)
 495     for (i = FIRST_PSEUDO_REGISTER; i < max_regno; i++)
 496       if (REG_N_REFS (i))
 497         {
 498           enum reg_class class, altclass;
 499
 500           fprintf (file, "\nRegister %d used %d times across %d insns",
 501                    i, REG_N_REFS (i), REG_LIVE_LENGTH (i));
 502           if (REG_BASIC_BLOCK (i) >= 0)
 503             fprintf (file, " in block %d", REG_BASIC_BLOCK (i));
 504           if (REG_N_SETS (i))
 505             fprintf (file, "; set %d time%s", REG_N_SETS (i),
 506                      (REG_N_SETS (i) == 1) ? "" : "s");
 507           if (regno_reg_rtx[i] != NULL && REG_USERVAR_P (regno_reg_rtx[i]))
 508             fprintf (file, "; user var");
 509           if (REG_N_DEATHS (i) != 1)
 510             fprintf (file, "; dies in %d places", REG_N_DEATHS (i));
 511           if (REG_N_CALLS_CROSSED (i) == 1)
 512             fprintf (file, "; crosses 1 call");
 513           else if (REG_N_CALLS_CROSSED (i))
 514             fprintf (file, "; crosses %d calls", REG_N_CALLS_CROSSED (i));
 515           if (regno_reg_rtx[i] != NULL
 516               && PSEUDO_REGNO_BYTES (i) != UNITS_PER_WORD)
 517             fprintf (file, "; %d bytes", PSEUDO_REGNO_BYTES (i));
 518
 519           class = reg_preferred_class (i);
 520           altclass = reg_alternate_class (i);
 521           if (class != GENERAL_REGS || altclass != ALL_REGS)
 522             {
 523               if (altclass == ALL_REGS || class == ALL_REGS)
 524                 fprintf (file, "; pref %s", reg_class_names[(int) class]);
 525               else if (altclass == NO_REGS)
 526                 fprintf (file, "; %s or none", reg_class_names[(int) class]);
 527               else
 528                 fprintf (file, "; pref %s, else %s",
 529                          reg_class_names[(int) class],
 530                          reg_class_names[(int) altclass]);
 531             }
 532
 533           if (regno_reg_rtx[i] != NULL && REG_POINTER (regno_reg_rtx[i]))
 534             fprintf (file, "; pointer");
 535           fprintf (file, ".\n");
 536         }
 537
 538   fprintf (file, "\n%d basic blocks, %d edges.\n", n_basic_blocks, n_edges);
 539   FOR_EACH_BB (bb)
 540     {
 541       edge e;
 542       int sum;
 543       gcov_type lsum;
 544
 545       fprintf (file, "\nBasic block %d: first insn %d, last %d, ",
 546                bb->index, INSN_UID (BB_HEAD (bb)), INSN_UID (BB_END (bb)));
 547       fprintf (file, "prev %d, next %d, ",
 548                bb->prev_bb->index, bb->next_bb->index);
 549       fprintf (file, "loop_depth %d, count ", bb->loop_depth);
 550       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, bb->count);
 551       fprintf (file, ", freq %i", bb->frequency);
 552       if (maybe_hot_bb_p (bb))
 553         fprintf (file, ", maybe hot");
 554       if (probably_never_executed_bb_p (bb))
 555         fprintf (file, ", probably never executed");
 556       fprintf (file, ".\n");
 557
 558       fprintf (file, "Predecessors: ");
 559       for (e = bb->pred; e; e = e->pred_next)
 560         dump_edge_info (file, e, 0);
 561
 562       fprintf (file, "\nSuccessors: ");
 563       for (e = bb->succ; e; e = e->succ_next)
 564         dump_edge_info (file, e, 1);
 565
 566       fprintf (file, "\nRegisters live at start:");
 567       dump_regset (bb->global_live_at_start, file);
 568
 569       fprintf (file, "\nRegisters live at end:");
 570       dump_regset (bb->global_live_at_end, file);
 571
 572       putc ('\n', file);
 573
 574       /* Check the consistency of profile information.  We can't do that
 575          in verify_flow_info, as the counts may get invalid for incompletely
 576          solved graphs, later eliminating of conditionals or roundoff errors.
 577          It is still practical to have them reported for debugging of simple
 578          testcases.  */
 579       sum = 0;
 580       for (e = bb->succ; e; e = e->succ_next)
 581         sum += e->probability;
 582       if (bb->succ && abs (sum - REG_BR_PROB_BASE) > 100)
 583         fprintf (file, "Invalid sum of outgoing probabilities %.1f%%\n",
 584                  sum * 100.0 / REG_BR_PROB_BASE);
 585       sum = 0;
 586       for (e = bb->pred; e; e = e->pred_next)
 587         sum += EDGE_FREQUENCY (e);
 588       if (abs (sum - bb->frequency) > 100)
 589         fprintf (file,
 590                  "Invalid sum of incomming frequencies %i, should be %i\n",
 591                  sum, bb->frequency);
 592       lsum = 0;
 593       for (e = bb->pred; e; e = e->pred_next)
 594         lsum += e->count;
 595       if (lsum - bb->count > 100 || lsum - bb->count < -100)
 596         fprintf (file, "Invalid sum of incomming counts %i, should be %i\n",
 597                  (int)lsum, (int)bb->count);
 598       lsum = 0;
 599       for (e = bb->succ; e; e = e->succ_next)
 600         lsum += e->count;
 601       if (bb->succ && (lsum - bb->count > 100 || lsum - bb->count < -100))
 602         fprintf (file, "Invalid sum of incomming counts %i, should be %i\n",
 603                  (int)lsum, (int)bb->count);
 604     }
 605
 606   putc ('\n', file);
 607 }
 608
 609 void
 610 debug_flow_info (void)
 611 {
 612   dump_flow_info (stderr);
 613 }
 614
 615 void
 616 dump_edge_info (FILE *file, edge e, int do_succ)
 617 {
 618   basic_block side = (do_succ ? e->dest : e->src);
 619
 620   if (side == ENTRY_BLOCK_PTR)
 621     fputs (" ENTRY", file);
 622   else if (side == EXIT_BLOCK_PTR)
 623     fputs (" EXIT", file);
 624   else
 625     fprintf (file, " %d", side->index);
 626
 627   if (e->probability)
 628     fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE);
 629
 630   if (e->count)
 631     {
 632       fprintf (file, " count:");
 633       fprintf (file, HOST_WIDEST_INT_PRINT_DEC, e->count);
 634     }
 635
 636   if (e->flags)
 637     {
 638       static const char * const bitnames[] = {
 639         "fallthru", "ab", "abcall", "eh", "fake", "dfs_back",
 640         "can_fallthru", "irreducible", "sibcall", "loop_exit"
 641       };
 642       int comma = 0;
 643       int i, flags = e->flags;
 644
 645       fputs (" (", file);
 646       for (i = 0; flags; i++)
 647         if (flags & (1 << i))
 648           {
 649             flags &= ~(1 << i);
 650
 651             if (comma)
 652               fputc (',', file);
 653             if (i < (int) ARRAY_SIZE (bitnames))
 654               fputs (bitnames[i], file);
 655             else
 656               fprintf (file, "%d", i);
 657             comma = 1;
 658           }
 659
 660       fputc (')', file);
 661     }
 662 }
 663 \f
 664 /* Simple routines to easily allocate AUX fields of basic blocks.  */
 665
 666 static struct obstack block_aux_obstack;
 667 static void *first_block_aux_obj = 0;
 668 static struct obstack edge_aux_obstack;
 669 static void *first_edge_aux_obj = 0;
 670
 671 /* Allocate a memory block of SIZE as BB->aux.  The obstack must
 672    be first initialized by alloc_aux_for_blocks.  */
 673
 674 inline void
 675 alloc_aux_for_block (basic_block bb, int size)
 676 {
 677   /* Verify that aux field is clear.  */
 678   if (bb->aux || !first_block_aux_obj)
 679     abort ();
 680   bb->aux = obstack_alloc (&block_aux_obstack, size);
 681   memset (bb->aux, 0, size);
 682 }
 683
 684 /* Initialize the block_aux_obstack and if SIZE is nonzero, call
 685    alloc_aux_for_block for each basic block.  */
 686
 687 void
 688 alloc_aux_for_blocks (int size)
 689 {
 690   static int initialized;
 691
 692   if (!initialized)
 693     {
 694       gcc_obstack_init (&block_aux_obstack);
 695       initialized = 1;
 696     }
 697
 698   /* Check whether AUX data are still allocated.  */
 699   else if (first_block_aux_obj)
 700     abort ();
 701   first_block_aux_obj = obstack_alloc (&block_aux_obstack, 0);
 702   if (size)
 703     {
 704       basic_block bb;
 705
 706       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 707         alloc_aux_for_block (bb, size);
 708     }
 709 }
 710
 711 /* Clear AUX pointers of all blocks.  */
 712
 713 void
 714 clear_aux_for_blocks (void)
 715 {
 716   basic_block bb;
 717
 718   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 719     bb->aux = NULL;
 720 }
 721
 722 /* Free data allocated in block_aux_obstack and clear AUX pointers
 723    of all blocks.  */
 724
 725 void
 726 free_aux_for_blocks (void)
 727 {
 728   if (!first_block_aux_obj)
 729     abort ();
 730   obstack_free (&block_aux_obstack, first_block_aux_obj);
 731   first_block_aux_obj = NULL;
 732
 733   clear_aux_for_blocks ();
 734 }
 735
 736 /* Allocate a memory edge of SIZE as BB->aux.  The obstack must
 737    be first initialized by alloc_aux_for_edges.  */
 738
 739 inline void
 740 alloc_aux_for_edge (edge e, int size)
 741 {
 742   /* Verify that aux field is clear.  */
 743   if (e->aux || !first_edge_aux_obj)
 744     abort ();
 745   e->aux = obstack_alloc (&edge_aux_obstack, size);
 746   memset (e->aux, 0, size);
 747 }
 748
 749 /* Initialize the edge_aux_obstack and if SIZE is nonzero, call
 750    alloc_aux_for_edge for each basic edge.  */
 751
 752 void
 753 alloc_aux_for_edges (int size)
 754 {
 755   static int initialized;
 756
 757   if (!initialized)
 758     {
 759       gcc_obstack_init (&edge_aux_obstack);
 760       initialized = 1;
 761     }
 762
 763   /* Check whether AUX data are still allocated.  */
 764   else if (first_edge_aux_obj)
 765     abort ();
 766
 767   first_edge_aux_obj = obstack_alloc (&edge_aux_obstack, 0);
 768   if (size)
 769     {
 770       basic_block bb;
 771
 772       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 773         {
 774           edge e;
 775
 776           for (e = bb->succ; e; e = e->succ_next)
 777             alloc_aux_for_edge (e, size);
 778         }
 779     }
 780 }
 781
 782 /* Clear AUX pointers of all edges.  */
 783
 784 void
 785 clear_aux_for_edges (void)
 786 {
 787   basic_block bb;
 788   edge e;
 789
 790   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
 791     {
 792       for (e = bb->succ; e; e = e->succ_next)
 793         e->aux = NULL;
 794     }
 795 }
 796
 797 /* Free data allocated in edge_aux_obstack and clear AUX pointers
 798    of all edges.  */
 799
 800 void
 801 free_aux_for_edges (void)
 802 {
 803   if (!first_edge_aux_obj)
 804     abort ();
 805   obstack_free (&edge_aux_obstack, first_edge_aux_obj);
 806   first_edge_aux_obj = NULL;
 807
 808   clear_aux_for_edges ();
 809 }
 810
 811 /* Verify the CFG consistency.
 812
 813    Currently it does following checks edge and basic block list correctness
 814    and calls into IL dependent checking then.  */
 815 void
 816 verify_flow_info (void)
 817 {
 818   size_t *edge_checksum;
 819   int num_bb_notes, err = 0;
 820   basic_block bb, last_bb_seen;
 821   basic_block *last_visited;
 822
 823   last_visited = xcalloc (last_basic_block + 2, sizeof (basic_block));
 824   edge_checksum = xcalloc (last_basic_block + 2, sizeof (size_t));
 825
 826   /* Check bb chain & numbers.  */
 827   last_bb_seen = ENTRY_BLOCK_PTR;
 828   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, NULL, next_bb)
 829     {
 830       if (bb != EXIT_BLOCK_PTR
 831           && bb != BASIC_BLOCK (bb->index))
 832         {
 833           error ("bb %d on wrong place", bb->index);
 834           err = 1;
 835         }
 836
 837       if (bb->prev_bb != last_bb_seen)
 838         {
 839           error ("prev_bb of %d should be %d, not %d",
 840                  bb->index, last_bb_seen->index, bb->prev_bb->index);
 841           err = 1;
 842         }
 843
 844       last_bb_seen = bb;
 845     }
 846
 847   /* Now check the basic blocks (boundaries etc.) */
 848   FOR_EACH_BB_REVERSE (bb)
 849     {
 850       int n_fallthru = 0;
 851       edge e;
 852
 853       if (bb->count < 0)
 854         {
 855           error ("verify_flow_info: Wrong count of block %i %i",
 856                  bb->index, (int)bb->count);
 857           err = 1;
 858         }
 859       if (bb->frequency < 0)
 860         {
 861           error ("verify_flow_info: Wrong frequency of block %i %i",
 862                  bb->index, bb->frequency);
 863           err = 1;
 864         }
 865       for (e = bb->succ; e; e = e->succ_next)
 866         {
 867           if (last_visited [e->dest->index + 2] == bb)
 868             {
 869               error ("verify_flow_info: Duplicate edge %i->%i",
 870                      e->src->index, e->dest->index);
 871               err = 1;
 872             }
 873           if (e->probability < 0 || e->probability > REG_BR_PROB_BASE)
 874             {
 875               error ("verify_flow_info: Wrong probability of edge %i->%i %i",
 876                      e->src->index, e->dest->index, e->probability);
 877               err = 1;
 878             }
 879           if (e->count < 0)
 880             {
 881               error ("verify_flow_info: Wrong count of edge %i->%i %i",
 882                      e->src->index, e->dest->index, (int)e->count);
 883               err = 1;
 884             }
 885
 886           last_visited [e->dest->index + 2] = bb;
 887
 888           if (e->flags & EDGE_FALLTHRU)
 889             n_fallthru++;
 890
 891           if (e->src != bb)
 892             {
 893               error ("verify_flow_info: Basic block %d succ edge is corrupted",
 894                      bb->index);
 895               fprintf (stderr, "Predecessor: ");
 896               dump_edge_info (stderr, e, 0);
 897               fprintf (stderr, "\nSuccessor: ");
 898               dump_edge_info (stderr, e, 1);
 899               fprintf (stderr, "\n");
 900               err = 1;
 901             }
 902
 903           edge_checksum[e->dest->index + 2] += (size_t) e;
 904         }
 905       if (n_fallthru > 1)
 906         {
 907           error ("Wrong amount of branch edges after unconditional jump %i", bb->index);
 908           err = 1;
 909         }
 910
 911       for (e = bb->pred; e; e = e->pred_next)
 912         {
 913           if (e->dest != bb)
 914             {
 915               error ("basic block %d pred edge is corrupted", bb->index);
 916               fputs ("Predecessor: ", stderr);
 917               dump_edge_info (stderr, e, 0);
 918               fputs ("\nSuccessor: ", stderr);
 919               dump_edge_info (stderr, e, 1);
 920               fputc ('\n', stderr);
 921               err = 1;
 922             }
 923           edge_checksum[e->dest->index + 2] -= (size_t) e;
 924         }
 925     }
 926
 927   /* Complete edge checksumming for ENTRY and EXIT.  */
 928   {
 929     edge e;
 930
 931     for (e = ENTRY_BLOCK_PTR->succ; e ; e = e->succ_next)
 932       edge_checksum[e->dest->index + 2] += (size_t) e;
 933
 934     for (e = EXIT_BLOCK_PTR->pred; e ; e = e->pred_next)
 935       edge_checksum[e->dest->index + 2] -= (size_t) e;
 936   }
 937
 938   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
 939     if (edge_checksum[bb->index + 2])
 940       {
 941         error ("basic block %i edge lists are corrupted", bb->index);
 942         err = 1;
 943       }
 944
 945   num_bb_notes = 0;
 946   last_bb_seen = ENTRY_BLOCK_PTR;
 947
 948   /* Clean up.  */
 949   free (last_visited);
 950   free (edge_checksum);
 951   err |= cfg_hooks->cfgh_verify_flow_info ();
 952   if (err)
 953     internal_error ("verify_flow_info failed");
 954 }
 955
 956 /* Print out one basic block with live information at start and end.  */
 957
 958 void
 959 dump_bb (basic_block bb, FILE *outf)
 960 {
 961   edge e;
 962
 963   fprintf (outf, ";; Basic block %d, loop depth %d, count ",
 964            bb->index, bb->loop_depth);
 965   fprintf (outf, HOST_WIDEST_INT_PRINT_DEC, (HOST_WIDEST_INT) bb->count);
 966   putc ('\n', outf);
 967
 968   cfg_hooks->dump_bb (bb, outf);
 969
 970   fputs (";; Successors: ", outf);
 971   for (e = bb->succ; e; e = e->succ_next)
 972     dump_edge_info (outf, e, 1);
 973   putc ('\n', outf);
 974 }
 975
 976 void
 977 debug_bb (basic_block bb)
 978 {
 979   dump_bb (bb, stderr);
 980 }
 981
 982 basic_block
 983 debug_bb_n (int n)
 984 {
 985   basic_block bb = BASIC_BLOCK (n);
 986   dump_bb (bb, stderr);
 987   return bb;
 988 }